数据结构实验报告任务书

《数据结构》实验指导书重庆大学数学与统计学院PAGEPAGE10前言各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。二、实验内容1、动态创建单链表2、实现线性表链式存储结构中元素的插入。3、实现线性表链式存储结构中元素的删除。三、具体要求1、单链表的存储结构定义typedef struct LNodeElemType data; //数据域struct LNode *next; //指针域}LNode,*LinkList;2、从键盘上依次输入21、18、30、75、42、56，逆序创建单链表，并输出单链表中的各元素值。3396710或失败的信息，并输出单链表中的各元素值。468败的信息，并输出单链表中的各元素值。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验二 栈、队列算法设计一、实验目的1、熟悉栈这种特殊线性结构的特性；2、熟练掌握栈在顺序存储结构和链表存储结构下的基本运算；3、熟悉队列这种特殊线性结构的特性；4、熟练掌握队列在链表存储结构下的基本运算。二、 实验内容1、动态创建栈和队列2、实现实现栈和队列中元素的插入。3、实现实现栈和队列中元素的的删除。三、具体要求1判空、置空等操作，生成sqStack.h文件和LinkStack.h文件；编写main函数调用。2、用链式存储结构实现队列的初始化、进队、出队操作，生成LinkQueue.h文件，编写main函数调用。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验三、二叉树的遍历一、实验目的1、掌握二叉树的特点及其存储方式。2、掌握二叉树的创建。3、掌握二叉树遍历的基本方法：前序、中序、后序。二、实验内容1、用前序方法建立一棵二叉树。2、编写前序遍历、中序遍历、后序遍历二叉树的程序。三、具体要求typedefstructBiTNode{datatype data;structBiTNode*lchild,*rchild;}BiTNode，*BiTree;建立下图所示的二叉树aabcdef编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列统计以上二叉树中叶子结点的个数四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验四、折半查找和二叉排序树一、实验目的1、掌握查找的特点。2、掌握折半查找的基本思想及其算法。3、熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作。二、实验内容1、设有关键字序列k={5,14,18,21,23,29,31,35}，查找key=21和key=25的数据元素。2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树，并完成删除关键字53和24的操作。三、具体要求1、折半查找（1）85,14,18,21,23,29,31,3bub[8]中，并输出其值。21，素在表中的位置，否则给出查找失败的信息。25，素在表中位置，否则给出查找失败的信息。2、二叉排序树二叉排序树结点定义typedefstructBiTNode{//结点结TElemType data;structBiTNode *lchild,*rchild; //}BiTNode,*BiTree;45、24、53、12、37、9输出其中序遍历结果。24，输出其中序遍历结果。53，输出其中序遍历结果。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验五、内部排序一、实验目的1、掌握排序的有关概念和特点。2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。。3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。二、实验内容设有关键字序列k={12,45,21,12,30,2,68,33},试用各种排序算法进行排序。三、具体要求18quick[8]中，并输出值。2、输出各种排序算法每一趟排序的结果，观察关键字次序的变化。38k1={2121221303345,68}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。48k2={68453330211212,2}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。5、测试各排序算法的执行时间，比较执行效率。6、随机产生3万个数，对其进行排序，观察其结果。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验六、图及其应用一、实验目的1、掌握图的有关概念和特点。2、熟练掌握最短路径算法的基本思想。。二、实验内容已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道：是否有公共汽车到达指定的目的地?若有，告诉乘车路线。如需中途换车，应指示再那里换车三、 实验要求（1）数据结构： 将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶(站)之间的邻接关系外，还应反映途经的路线号。注意，站之间可能存在往返两个方向，每个方向又可能对应多个路线号。（2）算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目数据结构可以采用链接结构：typestptr=^node；node=recordstname：string；link：stptrend；hdtp=array[1..max]ofvarhead：hdtp；数据结构也可以采用顺序结构：typenode=recordgo，back：integerend；goback=array[1..max，1..max]node；var a：goback；其中，a[I，j].go>0ijj].back>0ijjia[i，j