《数据结构》实验义.docVIP

《数据结构》实验讲义 课程简介 课程名称：数据结构授课对象：计算机科学本科 授课班级：2005教材版本：《数据结构》（C语言版）清华大学出版社学时：90 其中：理论：72 实验：18授课教师：韩英杰电子邮箱：ieyjhan@zzu.edu.cn电话 实验一(选做, 设计性实验，2学时) 实验题目：学生成绩管理系统 学生记录结构如下： struct student_type{ char id[5];　　　/*学生学号*/ char name[11];　/*学生名字*/ int age;　　　　/*学生年龄*/　 int math;　　　/*数学成绩*/　 int eng;　　　　/*英语成绩*/　 int ds;　　　　/*数据结构成绩*/ int os;　　　　/*操作系统成绩*/ } 10个学生信息如下: 1001 zengliang 19 86 87 84 80 1002 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 69 1009 xiaoyu 19 84 74 70 80 1010 weikun 20 68 84 79 86 实验目的： 熟悉C语言的书写规范，注意输入、输出的方式及错误处理方式。 理解算法五个要素的确切含义，掌握计算语句频度和估算算法时间复杂度的方法。 熟悉C语言函数的定义、函数的调用，参数的传递等细节 熟悉C语言读写文件的函数及其使用。 实验要求： 将这10个学生信息存入到磁盘文件stu_list.in中。 将磁盘文件中的所有学生记录读入内存中一块静态顺序空间中（使用数组申请），求出所有学生数学的平均成绩。 将磁盘文件中的所有学生记录读入内存中一块动态申请的顺序空间中（使用函数malloc()申请），求出所有学生数学的平均成绩。 实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写） 实验二（必做, 设计性实验，2学时） 实验题目：顺序表的基本操作的实现 1、在非递减有序的顺序表中插入一个元素x，保持顺序表有序性。 2、顺序表元素的逆置 3、两个（有序或无序）顺序表的合并 实验目的： 熟悉将算法转换成程序代码的过程。 了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。 熟练掌握顺序表的基本操作：查找、插入、删除、合并等，掌握顺序表的随机存取特性。 实验要求： 1、要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。 2、对顺序表插入的算法，要求用两种方法实现：其一：自己编写实现函数；其二：调用顺序表基本操作ListInsert(SqList L,int i,ElemType x)，比较使用自己编写的插入函数和调用顺序表基本操作的函数两种实现方法之间的优缺点。 3、对所编写的算法进行时间复杂度分析。 实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写） 实验三（必做, 设计性实验，2学时） 实验题目：单链表的基本操作 1、在线性单链表中删除值介于mink和maxk之间的结点。 2、线性单链表逆置 3、两个（有序或无序）单链表的合并 实验目的： 了解线性表的链式存储结构和顺序存取特性，熟练掌握线性表的链式存储结构的C语言描述方法， 熟练掌握动态链表的基本操作查找、插入、定位等，能在实际应用中选择适当的链表结构。 掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。 实验要求： 1、与实验二比较，对于线性表的基本操作的实现，使用顺序存储结构和链式存储结构各有什么优缺点。 2、选做：使用书37页，一种带头结点的线性链表LinkList来完成以上题目。体会作为链表中位序的概念和位置的概念哪个更重要。 实验内容和实验步骤：（由学生填写） 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写） 实验四（必做, 设计性实验，2学时） 实验题目：栈的基本操作的实现 1、用栈实现括号匹配的检验 2、用栈实现形如a+b@b+a#的中心对称的字符序列的检验。 3、用栈和队列实现形如a+b@b+a#的中心对称的字符序列的检验。 实验目的： 熟练掌握栈这种抽象数据类型，能在相应的应用问