《数据结构》实验指导书(修订版)(总39页).doc
39页
《数据结构》实验指导书郑州轻工业学院2016.02.20目 录前 言 3实验01 顺序表的基本操作 7实验02 单链表的基本操作 19实验03 栈的基本操作 32实验04 队列的基本操作 35实验05 二叉树的基本操作 38实验06 哈夫曼编码 40实验07 图的两种存储和遍历 42实验08 最小生成树、拓扑排序和最短路径 46实验09 二叉排序树的基本操作 48实验10 哈希表的生成 50实验11 常用的内部排序算法 52附：实验报告模板 54前 言《数据结构》是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构，从而提高其程序设计能力通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。
另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力学习这门课程，习题和实验是两个关键环节学生理解算法，上机实验是最佳的途径之一因此，实验环节的好坏是学生能否学好《数据结构》的关键为了更好地配合学生实验，特编写实验指导书一、实验目的本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力；另一方面培养学生从实际问题中抽象出对应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后课程的学习、大型软件的开发、实际工程问题打下良好的软件开发基础二、实验要求1、每次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果 3、实验结束后总结实验内容、书写实验报告4、遵守实验室规章制度、不缺席、按时上、下机 5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。
三、实验环境 VC++6.0或其他C++相关的编译环境四、说明1、本实验的所有算法中元素类型应根据实际需要合理选择2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备4、好的算法决定了好的程序，要有效地实现算法，就需要设计能够有效表达和简化算法的数据结构，因此数据结构是有效进行程序设计的基础，是每个程序员的必修课五、实验报告的书写要求1、明确实验的目的及要求2、记录实验的输入数据和输出结果 3、说明实验中出现的问题和解决过程4、写出实验的体会和实验过程中没能解决的问题5、实验程序请构建为多文件程序，每一个算法对应的函数原型声明存放在头文件*.h中，对应的函数实现存放在源文件*.c中；main()函数存放在另一个源文件中，该文件包含头文件*.h即可六、成绩考评办法1、期末考试占70分，闭卷2、平时考评占30分其中实验环节占20分（实验准备、上机、报告、验收等）；平时占10分（出勤、作业、测验等）。
七、参考书目1、《数据结构》（Ｃ语言版） 严蔚敏等 清华大学出版社 2、《数据结构题集》 （C语言版） 严蔚敏等 清华大学出版社 3、《数据结构与算法分析——C语言描述》，Mark Allen Weiss著，机械工业出版社，2012实验01 顺序表的基本操作实验学时：2学时实验类型：上机背景知识：顺序表的插入、删除及应用目的要求： 1．掌握顺序存储结构的特点 2．掌握顺序存储结构的常见算法实验内容：编写一个完整的程序，实现顺序表的生成、插入、删除、输出等基本运算1） 建立一个顺序表，含有n个数据元素2） 输出顺序表3） 在顺序表中删除值为x的结点或者删除给定位置i的结点4） 实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数5） 输入整型元素序列，利用有序表插入算法建立一个有序表6） *利用算法5建立两个非递减有序表A和B，并把它们合并成一个非递减有序表C7） 在主函数中设计一个简单的菜单，分别测试上述算法8） *综合训练： 利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）实验说明：1．请构建多文件程序，算法1至算法6对应的函数原型声明存放在头文件SqList.h中，对应的函数实现存放在源文件SqList.c中；main()函数存放在另一个源文件中，该文件包含头文件SqList.h即可。
2．类型定义 #define MAXSIZE 100 //表中元素的最大个数 typedef int ElemType; //元素类型 typedef struct { ElemType *elem; //线性表 int length; //表的实际长度 int listsize; //当前分配的存储容量 }SqList; //顺序表的类型名3．建立顺序表时可利用随机函数自动产生数据注意问题：1、 插入、删除时元素的移动原因、方向及先后顺序2、 理解函数形参与实参的传递关系部分源代码：DS.h#include
