数据结构实验指导书2010.doc

《数据结构实验指导书2010.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华北电力大学科技学院实验报告实验名称数据结构试验课程名称数据结构专业班级：学生姓名：学号：成绩：指导老师：实验日期：2010年3月-5月（实验报告如打印，纸张用A4，左装订；页边距：上下2.5cm，左2.5cm，右2.0cm；字体：字体小四号，1.25倍行距。）验证性、综合性实验报告应包含的主要内容：一、实验目的及要求1．实验目的2．实验要求二、所用仪器、设备1．所需的硬件设备2．所需的软件列表三、实验原理1．实验所用到的原理或理论2．结合本实验阐述如何将理论与实验相结合四、实验步骤（附程序流程图）五、程序源代码六、讨论与结论（对实验现象、实验故障及处理方法、实验中存在的

2、问题等进行分析和讨论，对实验的进一步想法或改进意见）七、所附实验输出的结果或数据（按照以上格式书写报告）实验一顺序表及其应用一、实验目的及要求1、实验目的(1)熟悉VC++上机环境，进一步掌握C语言的结构特点。(2)掌握线性表的顺序存储结构的定义及C语言实现。(3)掌握线性表在顺序存储结构即顺序表中的各种基本操作的实现。(4)掌握栈和队列的顺序表示和实现。2、实验要求(1)用顺序存储结构实现栈和循环队列。(2)编写完整程序完成下面的实验内容并上机运行。(3)整理并上交实验报告。二、实验内容1.约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的

3、人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6编写程序选择循环队列（顺序存储方式）模拟整个过程，并依次输出出列的各人的编号。2、表达式的计算：1）问提描述：输入形如：某单字母变量=中缀表达式。其中中缀表达式可以包括整数、单字母变量、二元操作符+、-、*、/、以及括号（）。根据输入，

4、所有单字母变量都能够求得数值解，设计算法要求：①将等式右边的中缀表达式转换成后缀表达式，并求值。然后以单字母变量后缀表达式值的形式，存放在内存，并打印输出。②在①的基础上，对用户提出的中缀表达式求值，若变量在内存表格中，则算法返回表达式的值（若非整数，则四舍五入取整），若变量不在表中，则返回一个错误信息。2)例如：输入A=8*DB=3C=(A-10)*(B+D/2)D=6①求得的后缀表达式及值A8D*48B33CA10-BD2/+*228D66②用户输入算法返回D6B3B+C/A8C+D-A186A+D+Eerror实现提示：数据结构采用顺序存储实现线性表，在中缀表达式转

5、化为后缀表达式时，利用顺序存储实现栈。实验二链表及其应用一、实验目的及要求1、实验目的(1)熟悉VC++上机环境，进一步掌握C语言的结构特点。(2)掌握线性表的链式存储结构即单链表的定义及C语言实现。(3)掌握线性表在链式存储结构即单链表中的各种基本操作。(4)掌握栈和队列的链式存储结构的表示和实现。2、实验要求(1)用链式存储结构实现单链表（和单向循环链表）的建立、查找和删除等运算。(2)编写完整程序完成下面的实验内容并上机运行。(3)整理并上交实验报告。二、实验内容1.约瑟夫环的问题：设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。下一个人

6、，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6用单向循环链表存储结构模拟此过程。实现提示：typedefstructNode{  intdata;    structNode*next;}*nodetype;//定义指向链节点类型的指针1）先建立单向循环链表。构造一个结点需用到C语言的标准函数mall

7、oc()，如给指针变量p分配一个结点的地址：p=(nodetype)malloc(sizeof(structNode));该语句的功能是申请分配一个类型为结构体类型为Node的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。1）注意在删除第m个节点时，需要一个辅助指针指向删除节点的前驱节点，删除节点只需要修改指针即可。2.若已知非空线性链表第一个结点的指针为list（即非空不带头节点的单链表头指针为list），请写一个算法并实现,将该链表中数据域