数据结构每经典实验.doc

《数据结构每经典实验.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验实验一：线性表及其应用1．实验名称：线性表及其应用要求：a.掌握线性表的各种存储结构实现。b.掌握各种存储结构上进行插入、删除等操作的算法。c.通过线性表结构解决现实中的一些问题。实验内容：编写算法实现顺序表的逆置，即要求把顺序表A中的数据元素序列（a0,a1,…,an-1）就地逆置为（an-1,an-2,…,a0），并把逆置后的数据元素存储到顺序表中。2.将有序线性表La={2,4,6,7,9}，Lb={1,5,7,8}，合并为Lc={1,2,4,5,6,7,7,8,9}3通讯录管理–菜单内容–程序运行后，给出如下六个菜单的内容和输入提示：1.通讯录的建立2.通讯者

2、结点的插入3.通讯者结点的查询4.通讯者结点的删除5.通讯者结点的输出0.退出管理系统请选择0－5：Typedefstruct{charnum[5];//编号charname[9];//姓名charsex[3];//性别charaddr[31];//地址}实验2：顺序栈基本操作一、实验目的1．熟悉并能实现栈的定义和基本操作。2．了解和掌握栈在递归和非递归算法的应用。二、实验要求1．进行栈的基本操作时要注意栈“后进先出”的特性。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销

3、毁、入栈、出栈以及取栈顶元素操作。2.将从键盘输入的字符序列逆置输出.比如，从键盘上输入：tsetasisihT；算法将输出：Thisisatest3..对于给定的十进制正整数N，转换成对应的八进制正整数4．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：(1)、从键盘上输入表达式。(2)、分析该表达式是否合法：①是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。②是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。③若是其它字符，则返回错误信息。(3)、若上述处理过程中没有发现错误，则认为该表达式合

4、法，并打印处理结果。四、思考与提高1．如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？2．栈的顺序存储结构在判别栈空与栈满时，所依据的条件是什么？实验3:顺序循环队列基本操作一、实验目的1．熟悉并能实现顺序循环队列的定义和基本操作。2．了解用队列解决实际应用问题。二、实验要求1．进行队列的基本操作时要注意队列“先进先出”的特性。2．复习关于栈操作的基础知识。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。三、实验内容1．任意输入队列长度和队列

5、中的元素值，构造一个顺序循环队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。2．约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人

6、的编号。3．(选做实验)设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。程序编写提示：以栈模拟停车场，以队列模拟车场外

7、的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以顺序结构实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每