《《数据结构》实验讲义》由会员分享，可在线阅读，更多相关《《数据结构》实验讲义（19页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验讲义课程简介课程名称：数据结构授课对象：计算机科学、软件工程教材版本：数据结构（C语言版）清华大学出版社学 时：102 （理论：74 实验：28）授课教师：韩英杰电子邮箱：实验题目：学生成绩管理系统学生记录结构如下：struct student_typechar id5;/*学生学号*/char name11; /*学生名字*/int age;/*学生年龄*/int math;/*数学成绩*/int eng;/*英语成绩*/int ds;/*数据结构成绩*/int os;/*操作系统成绩*/ 10 个学生信息如下:1001 zengliang 19 86 87 84 80 1002
2、 yaochang 18 75 85 79 68 1003 chuhua 20 85 98 76 89 1004 liuchang 21 69 85 75 88 1005 zhaoxia 19 89 85 75 84 1006 lina 20 89 84 95 75 1007 chenzhen 19 90 85 87 85 1008 wangkai 20 82 86 50 691009 xiaoyu 19 84 74 70 801010 weikun 20 68 84 79 86实验目的：1、熟悉 C 语言的书写规范，注意输入、输出的方式及错误处理 方式。2、理解算法五个要素的确切含义，掌握计
3、算语句频度和估算算法 时间复杂度的方法。3、熟悉 C 语言函数的定义、函数的调用，参数的传递等细节4、熟悉 C 语言读写文件的函数及其使用。实验要求：将这10个学生信息存入到磁盘文件stuist.in中。将磁盘文件中的所有学生记录读入内存中一块静态顺序空间 中（使用数组申请），求出所有学生数学的平均成绩。 将磁盘文件中的所有学生记录读入内存中一块动态申请的顺 序空间中（使用函数malloc（）申请），求出所有学生数学的平均 成绩。实验内容和实验步骤：（由学生填写）实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写）实验一（必做, 设计性实验，2 学时，来自第二章）实验题目：顺
4、序表基本操作1、在非递减有序顺序表中插入一个元素x,保持顺序表有序性（2.11）2、比较两个顺序表的大小（2.12）3、顺序表元素的逆置（2.21）4、两个（有序或无序）顺序表的合并（书上算法 2.1 和 2.2）实验目的：1、熟悉将算法转换成程序代码的过程。2、了解顺序表的逻辑结构特性,熟练掌握顺序表存储结构的 C 语言描述方法。3、熟练掌握顺序表的基本操作：查找、插入、删除、合并等,掌 握顺序表的随机存取特性。实验要求：1、要求用静态分配的一维数组和动态分配的一维数组来完成实验题 目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操 作实现上的共同点和区别。2、对顺序表插入的算法,
5、要求用两种方法实现：（1）自己编写函数实现；（2）调用顺序表基本操作 ListInsert（SqList &L,int i,ElemType x）,比较使用自己编写的插入函数和调用顺序表基本操作的函数两种实现方法之间的优缺点。3、对所编写的算法进行时间复杂度分析。 实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写）实验二（必做, 设计性实验，2 学时，来自第二章）实验题目：单链表的基本操作1、在线性单链表中删除值介于 mink 和 maxk 之间的结点（2.19）。2、线性单链表逆置（2.22）3、两个（有序或无序）单链表的合并（2.24
6、）实验目的：1、了解线性表的链式存储结构及其顺序存取特性，熟练掌握线性表的链式存储结构的 C 语言描述方法，2、熟练掌握动态链表的基本操作查找、插入、定位等，能在实际应用中选择适当的链表结构。3、掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。实验要求：1、与实验二比较，对于线性表的基本操作的实现，使用顺序存储结 构和链式存储结构各有什么优缺点。2、选做：使用书37页，一种带头结点的线性链表LinkList来完成以上题目。体会作为链表中位序的概念和位置的概念哪个更重要。实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写）实验三
7、（必做, 设计性实验，4 学时，来自第三章）实验题目：栈和队列的基本操作1、用栈实现括号匹配的检验2、用栈实现形如a+bb+a#的中心对称的字符序列的检验。3、用栈和队列实现形如a+bb+a#的中心对称的字符序列的检验。实验目的：1、熟练掌握栈这种抽象数据类型，能在相应的应用问题中正确选 用它。2、熟练掌握栈类型的两种实现方法（顺序栈和链式栈），两种存 储结构和基本操作的实现算法，注意栈空和栈满的判断条件及它 们的描述方法。3、熟练掌握队列这种抽象数据类型，能在相应的应用问题中正确 选用它。4、掌握循环队列与其它顺序结构实现上的不同及解决办法，熟悉 各种队列的基本操作在循环队列上的实现。实验要
8、求：1、选择合适的存储结构（顺序栈或链式栈）表示栈，给出其定义。2、在上述存储结构上实现栈的基本操作：初始化、置栈空、入栈、 出栈、取栈顶元素等。3、选择合适的存储结构（循环队列）表示队列，解决队空、队满判断条件相同的矛盾。4、实现基于循环队列的存储结构的基本操作，初始化、队空/满判断入队、出队、取队头元素，求队列长度等。5、对所写出的算法进行时间复杂度分析。 实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写）实验题目：字符串基本操作的实现1、假设串以堆分配存储结构表示，设计一个算法，完成串的替换操 作 Replace（&S,T,V）。2
9、、实现串匹配的KMP算法及它的改进算法。3、假设串以堆分配存储结构表示，设计一个算法，求串S和串T的 一个最长公共字串，并分析你的算法时间复杂度。实验目的：1、掌握串的三种存储结构。2、熟练掌握串的基本操作。3 、 熟悉串的应用。实验要求：1、定义串的堆分配存储结构2、熟练从键盘或文件中读入源字符串。3、实现对字符串的替换、查找、匹配等运算。4、比较并分析你的算法的时间复杂度。实验内容和实验步骤：（由学生填写）实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写）实验四（必做, 设计性实验，2 学时，来自第五章）实验题目：三元组表表示的稀疏矩阵的加法运算的实现1、设稀疏矩阵以三
10、元组顺序表为压缩存储结构，写出矩阵转置的算 法。转置后的矩阵以三元组顺序表表示。2、设稀疏矩阵以三元组顺序表为压缩存储结构，写出矩阵相加的算 法，用三元组表 C 存放和矩阵。实验目的：1、了解压缩的基本原理。2、了解稀疏矩阵的三元组表的压缩存储方法。3、熟悉三元组表表示的稀疏矩阵运算的实现。实验要求：1、定义稀疏矩阵压缩存储的存储结构-三元组顺序表2、将稀疏矩阵压缩到三元组顺序表中。3、实现矩阵转置的经典算法和三元组顺序表表示的稀疏矩阵的 转置运算，其中三元组顺序表表示的稀疏矩阵的转置算法需用普 通和快速转置算法来实现。4、实现矩阵相加的经典算法和三元组顺序表表示的稀疏矩阵的 加法运算。5、比
11、较并分析你的算法的时间复杂度。实验内容和实验步骤：（由学生填写）实验用测试数据和相关结果分析：（由学生填写）实验总结：（由学生填写）实验题目：二叉树的递归及非递归的遍历及其应用1、二叉树的前、中、后序遍历算法和非递归算法的实现2、求二叉树中叶子结点数目的递归算法。3、编写求二叉树深度的递归算法。实验目的：1、熟练掌握二叉树的二叉链表存储结构的C语言实现。2、掌握二叉树的基本操作-前序、中序、后序遍历二叉树的三种 方法。3、了解非递归遍历过程中“栈”的作用和状态，而且能灵活运用 遍历算法实现二叉树的其它操作。实验要求：1、创建二叉树的二叉链表结构、遍历先、中、后序的递归函数显示不同遍历序列，结合
12、习题了解二叉树遍历的应用实例。2、遍写前、中、后、层序遍历的非遍历函数，注意用以前作过的栈 和队列作辅助存储结构。3、思考遍历二叉树还有哪些应用？实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写）实验总结：（由学生填写）实验六（必做，验证性实验，2 学时，来自第六章）实验题目：Huffman树及Huffman编码的算法实现实验目的：1、了解该树的应用实例，熟悉掌握 Huffman 树的构造方法及Huffman 编码的应用，2、了解 Huffman 树在通信、编码领域的应用过程。实验要求：1、输入一段 100200 字的英文短文，存入一文件 a 中。2、写函数统计短
13、文出现的字母个数n及每个字母的出现次数3、写函数以字母出现次数作权值，建Haffman树（n个叶子），给出 每个字母的 Haffman 编码。4、用每个字母编码对原短文进行编码，码文存入文件b中。5、用 Haffman 树对 b 中码文进行译码，结果存入文件 c 中，比较 a,c 是否一致，以检验编码、译码的正确性。实验内容和实验步骤：（由学生填写）实验题目：图的深度优先遍历实验目的：1、 熟悉图的数组表示法和邻接表存储结构，2、 掌握构造有向图、无向图的算法 ，3、在掌握以上知识的基础上，熟悉图的深度优先遍历算法，并实 现。实验要求：1、图的数组表示法定义及基本操作的实现。2、图的邻接表表示
14、法定义及基本操作的实现。3、写函数实现图的深度优先遍历（分别在两种结构上）4、在邻接表上实现关键路径的求法，在邻接矩阵上实现最短路经、 最小生成树的求法。实验内容和实验步骤由学生填写）实验七（必做，验证性实验，2 学时，来自第九章）实验题目：查找实验目的：1、 熟练掌握顺序表和有序表的查找方法，2、 以一、两个算法为例，掌握其时间复杂度的分析方法。实验要求：1、验证并设计顺序表的查找（顺序查找、折半查找）算法2、验证二叉排序树上的查找（创建、查找、插入）算法3、验证Hash表查找（Hash函数定义、建立，查找，插入）算法（选 做）实验内容和实验步骤：（由学生填写）实验用测试数据和相关结果分析：
15、（由学生填写）实验总结：（由学生填写）实验八（必做，验证+设计，4 学时，来自第十章）实验题目：排序实验目的：1、 了解排序的方法、过程及原则。2、 掌握插入排序、快速排序、选择排序、归并排序的算法思想3、以一、两个算法为例，实现以上各类算法，掌握其时间复杂度的分析方法。实验要求：1、定义待排序序列的存储结构。2、验证插入排序、快速排序、选择排序、归并排序中各排序方法中的一、二个排序算法。实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写）附录：实验报告的要求实验报告是反映学生实验效果的最主要的依据，也是学生正确地 表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常 重要的内容，本课程的实验报告中要
