数据结构实验报告任务书.docx

1、数据结构实验指导书重庆大学数学与统计学院前言数据结构是计算机科学与技术、网络工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。数据结构是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力

2、，加深对数据结构相关概念和算法的理解。10实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。二、实验内容1、动态创建单链表2、实现线性表链式存储结构中元素的插入。3、实现线性表链式存储结构中元素的删除。三、具体要求1、单链表的存储结构定义typedefstructLNode ElemTypedata;/ 数据域structLNode*next;/ 指针域 LNode, *LinkList;2、从键盘上依次输入 21、18、30、75、42、56，逆序创建单链表，并输

3、出单链表中的各元素值。3、分别在单链表的第 3 个位置和第 9 个位置插入 67 和 10，给出插入成功或失败的信息，并输出单链表中的各元素值。4、删除单链表中的第 6 个数据元素和第 8 个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验二栈、队列算法设计一、实验目的1、熟悉栈这种特殊线性结构的特性；2、熟练掌握栈在顺序存储结构和链表存储结构下的基本运算；3、熟悉队列这种特殊线性结构的特性；4、熟练掌握队列在链表存储结

4、构下的基本运算。二、实验内容1、动态创建栈和队列2、实现实现栈和队列中元素的插入。3、实现实现栈和队列中元素的的删除。三、具体要求1、用顺序和链式存储结构分别实现栈的初始化、求长度、获取栈顶元素、压栈、出栈、判空、置空等操作，生成sqStack.h 文件和LinkStack.h 文件；编写main 函数调用。2、用链式存储结构实现队列的初始化、进队、出队操作，生成LinkQueue.h 文件，编写 main 函数调用。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验三、二叉树的遍历

5、一、实验目的1、掌握二叉树的特点及其存储方式。2、掌握二叉树的创建。3、掌握二叉树遍历的基本方法：前序、中序、后序。二、实验内容1、用前序方法建立一棵二叉树。2、编写前序遍历、中序遍历、后序遍历二叉树的程序。三、具体要求（1） 二叉树的二叉链表存储结构类型typedef struct BiTNode datatypedata;struct BiTNode *lchild ,*rchild ; BiTNode，*BiTree;（2） 建立下图所示的二叉树abcdef（3） 编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列（4） 统计以上二叉树中叶子结点的个数四、实验报告内容1、实验目的

6、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）从键盘输入上述 8 个整数

7、 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35，存放在数组 bub8中，并输出其值。（2） 从键盘输入 21，查找是否存在该数据元素，若存在，则输出该数据元素在表中的位置，否则给出查找失败的信息。（3） 从键盘输入 25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。2、二叉排序树（1） 二叉排序树结点定义typedef struct BiTNode / 结点结构TElemTypedata;struct BiTNode*lchild, *rchild;/ 左右孩子指针 BiTNode, *BiTree;（2） 从键盘上输入六个整数 45、24

8、、53、12、37、9 构造二叉排序树（3） 输出其中序遍历结果。（4） 删除数据元素 24，输出其中序遍历结果。（5） 删除数据元素 53，输出其中序遍历结果。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验五、内部排序一、实验目的1、掌握排序的有关概念和特点。2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。二、实验内容设有关键字序

9、列 k= 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 ,试用各种排序算法进行排序。三、具体要求1、从键盘输入上述 8 个整数，存放在数组 quick8中，并输出值。2、输出各种排序算法每一趟排序的结果，观察关键字次序的变化。3、如果上述 8 个整数按照升序输入，即k1= 2 , 12 , 12 , 21 , 30 , 33 ,45 , 68 ，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。4、如果上述 8 个整数按照降序输入，即k2= 68 , 45 , 33 , 30 , 21 , 12 ,12 , 2，输出各种排序算法每一趟排序的结果，观察关键字次序

10、的变化。5、测试各排序算法的执行时间，比较执行效率。6、随机产生 3 万个数，对其进行排序，观察其结果。四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果实验六、图及其应用一、实验目的1、掌握图的有关概念和特点。2、熟练掌握最短路径算法的基本思想。二、实验内容已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道：1. 是否有公共汽车到达指定的目的地?2. 若有，告诉乘车路线。如需中途换车，应指示再那里换车三、实验要求（1）数据结构：将公共汽车路线图看

11、成是一个有向图，选择合适的数据结构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。（2）算法： 按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。数据结构可以采用链接结构：type stptr=node； node=record stname：string； link：stptrend；hdtp=array1.max of node； var head：hdtp；数据结构也可以采用顺序结构：type node=record go，back：in

12、teger end；goback=array 1.max，1.max of node；vara：goback；其中，aI，j.go0 表示第 i 条线路上，向站j 去方向的下一站号；ai， j.back0 表示第 i 条线路 上，站 j 回来的下一站号。若站 j 不在第 i 条线路上，ai，j.go 和 ai，j.back 均为 0。另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；另一个是站号和站名对照表。（上面红色的内容可以不写在实验报告上。）四、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果