搜索
《数据结构》实验指导书肇庆学院计算机学院/软件学院编前言数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。本书是针对《数据结构》教程的上机实验指导书，内容包括线性表、栈和队列、串、数组和稀疏矩阵、递归、树状结构、图、查找、排序等。书后附录中给出了学生应提交的实验报告的格式。本上机实验指导书旨在通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。本实验指导书的内容都是基于C语言的，因此，要求学生对C语言要有一定的了解。建议使用TurboC2.0或VC++作为实验平台。根据学生的实际情况，本上机实验指导书的内容大多数为基本算法的综合验证，也包括部分算法设计。本上机实验指导书共有9个实验内容，每个实验约为4课时。由于作者对《数据结构》知识所知有限，书中难免存在错误，恳请读者及时加以指正，以便改进。如有对于本书的意见和建议，请与编者联系，E-mail：lg@zqu.edu.cn。衷心感谢！编者目录前言实验一顺序表......................................................................................................1实验二单链表......................................................................................................3实验三栈和队列.................................................................................................5实验四串...............................................................................................................7实验五数组...........................................................................................................8实验六树和二叉树...........................................................................................10实验七图.............................................................................................................12实验八查找.........................................................................................................14实验九排序.........................................................................................................16参考资料...................................................................................................................18附录1：肇庆学院计算机系实验报告格式..................................................19附录2：上机实习注意事项...............................................................................21肇庆学院计算机学院/软件学院《数据结构》实验指导书-1-实验一顺序表一、预备知识1.顺序表的存储结构形式及其描述2.顺序表的建立、查找、插入和删除操作二、实验目的1.掌握顺序表的存储结构形式及其描述2.掌握顺序表的建立、查找、插入和删除操作三、实验内容1.编写函数，输入一组整型元素序列，建立一个顺序表。2.编写函数，实现对该顺序表的遍历。3.编写函数，在顺序表中进行顺序查找某一元素，查找成功则返回其存储位置i，否则返回错误信息。4.编写函数，实现在顺序表的第i个位置上插入一个元素x的算法。5.编写函数，实现删除顺序表中第i个元素的算法。6.编写利用有序表插入算法建立一个有序表的函数。7.编写函数，利用以上算法，建立两个非递减有序表，并把它们合并成一个非递减有序表。8.编写函数，实现输入一个元素x，把它插入到有序表中，使顺序表依然有序。9.编写一个主函数，在主函数中设计一个简单的菜单，分别调试上述算法。四、实验说明1.顺序表的存储定义#defineMAXSIZE100//顺序表的最大元素个数typedefintElemType；//顺序表的元素类型typedefstructlist{ElemTypeelem[MAXSIZE]；//静态线性表intlength；//顺序表的实际长度}SqList；//顺序表的类型名五、注意问题肇庆学院计算机学院/软件学院《数据结构》实验指导书-2-1.插入、删除时元素的移动原因、方向及先后顺序。2.理解不同的函数形参与实参的传递关系。六、实验报告根据实验情况和结果撰写并递交实验报告。肇庆学院计算机学院/软件学院《数据结构》实验指导书-3-实验二单链表一、预备知识1.动态链表的存储结构形式及其描述2.单链表的建立、查找、插入和删除操作二、实验目的1.掌握单链表的存储结构形式及其描述2.掌握单链表的建立、查找、插入和删除操作三、实验内容1.编写函数，实现随机产生或键盘输入一组元素，建立一个带头结点的单链表（无序）。2.编写函数，实现遍历单链表。3.编写函数，实现把单向链表中元素逆置（不允许申请新的结点空间）。4.编写函数，建立一个非递减有序单链表。5.编写函数，利用以上算法，建立两个非递减有序单链表，然后合并成一个非递减链表。6.编写函数，在非递减有序单链表中插入一个元素使链表仍然有序。7.编写函数，实现在非递减有序链表中删除值为x的结点。8.编写一个主函数，在主函数中设计一个简单的菜单，分别调试上述算法。四、实验说明1.单链表的类型定义#includestdio.htypedefintElemType；//单链表结点类型typedefstructLNode{ElemTypedata；structLNode*next；}LNode，*LinkList；2.为了算法实现简单，最好采用带头结点的单链表。五、注意问题肇庆学院计算机学院/软件学院《数据结构》实验指导书-4-1.重点理解链式存储的特点及指针的含义。2.注意比较顺序存储与链式存储的各自特点。3.注意比较带头结点、无头结点链表实现插入、删除算法时的区别。4.单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。六、实验报告根据实验情况和结果撰写并递交实验报告。肇庆学院计算机学院/软件学院《数据结构》实验指导书-5-实验三栈和队列一、预备知识1.栈的顺序存储和链式存储结构的类型定义方法及其基本操作算法2.队列的顺序存储和链式存储结构的类型定义方法及其基本操作算法二、实验目的1.掌握栈、队列的思想及其存储实现2.掌握栈、队列的常见算法的程序实现三、实验内容1.编写函数，采用链式存储实现栈的初始化、入栈、出栈操作。2.编写函数，采用顺序存储实现栈的初始化、入栈、出栈操作。3.编写函数，采用链式存储实现队列的初始化、入队、出队操作。4.编写函数，采用顺序存储实现队列的初始化、入队、出队操作。5.编写一个主函数，在主函数中设计一个简单的菜单，分别调试上述算法。四、实验说明1.顺序栈的类型定义#defineMAX100//栈的最大值typedefstruct{ElemType*base；inttop；}SqStack；2.链栈的类型定义typedefstructSqNode{SElemTypedata；SqNode*Link；}*Sqptr；typedefstruct{Sqptrtop；//栈项指针}肇庆学院计算机学院/软件学院《数据结构》实验指导书-6-3.顺序队列的类型定义#defineMAX100//队列的最大长度typedefstruct{ElemType*base；intfront，rear；}SqQueue；4.单链队列的类型定义typedefstructQNode{QElemTypedata；structQNode*next；}*QueuePtr；typedefstruct{QueuePtrfrout；//队头指针QueuePtrrear；//队尾指针}五、注意问题1.重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。2.明确栈、队列均是特殊的线性表。3.栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。六、实验报告根据实验情况和结果撰写并递交实验报告。肇庆学院计算机学院/软件学院《数据结构》实验指导书-7-实验四串一、预备知识1.字符串的基本概念2.字符串的模式匹配算法二、实验目的1.理解字符串的模式匹配算法（包括KMP算法）三、实验内容1.编写函数，实现字符串的模式匹配算法。四、实验说明1.从键盘输入主串和子串元素，调用字符串的模式匹配算法，判断子串是否在主串中，若在，返回起始位置，否则显示否定信息。五、注意问题1.明确串也是特殊的线性表，掌握其特殊性所在。六、实验报告根据实验情况和结果撰写并递交实验报告。肇庆学院计算机学院/软件学院《数据结构》实验指导书-8-实验五数组一、预备知识1.稀疏矩阵的三元组表压缩存储结构2.稀疏矩阵的三元组表表示方法下的相乘算法二、实验目的1.掌握稀疏矩阵的三元组表存储结构的实现2.实现稀疏矩阵的三元组表表示下的相乘算法三、实验内容1.编写程序，实现利用三元组表进行两个稀疏矩阵相乘的算法。四、实验说明1.三元组表的类型定义#defineMAXSIZE1000//非零元素个数的最大值typedefstruct{introw，col；//非零元素的行下标和列下标ElemTypee；//非零元素的值}Triple；typedefstruct{Tripledata[MAXSIZE+1]；//非零元素的三元组表，data[0]未用intmu，nu，tu；//矩阵的行数、列数和非零元素个数}TSMatrix；五、注意问题1.首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。2.程序可以对三元组的输入顺序加以限制，例如，按行优先，以便提高计算效率。3.在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。4.三元组表是线性表的一种应用，通过它可以更好地理解线性表的存储结肇庆学院计算机学院/软件学院《数据结构》实验指导书-9-构。同时矩阵又是图的重要的存储方式，所以这个实验对更好地掌握线性表对将来对图的理解都有极大的帮助。六、实验报告根据实验情况和结果撰写并递交实验报告。肇庆学院计算机学院/软件学院《数据结构》实验指导书-10-实验六树和二叉树一、预备知识1.二叉树的二叉链表存储结构2.二叉树的常见算法二、实