《数据结构》实验指导书.doc

实验一 线性结构：考试报名管理系统一、 实验目的1掌握线性表的链式存储结构的特点和定义；2熟练地利用线性表的链式存储结构实现线性表的基本操作；3熟练地掌握线性表的链式存储结构中算法的实现。二、实验内容1使用线性表的链式存储结构来存储考生信息：准考证号、姓名、性别、年龄、报考类别、考生居住地（用于就近安排考点）； 2实现下列功能：输入考生信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生信息；按性别、年龄和报考类别统计考生信息。三、实验要求1. 根据实验内容编写程序，上机调试，得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时4学时五、实验步骤1进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。 首先确定系统的数据结构，定义类的成员变量和成员函数；然后实现各成员函数以完成对数据操作的相应功能；最后完成主函数以验证各个成员函数的功能并得出运行结果。 参考程序（略）。六、选作实验1、约瑟夫生者死者游戏。利用单循环链表存储结构，实现约瑟夫生者死者游戏。游戏大意是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。设计一个程序，求出出列顺序，并输出结果。2、N皇后问题。利用栈的顺序存储结构，实现N皇后问题。N皇后问题的大意是：在NN格的国际象棋棋盘上，安放N个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即任意两个皇后都不能处于同一行、同一列或同一条对角线上，求解有多少种摆法。皇后个数N由用户输入。实验二 树形结构：报文编码及译码问题一、 实验目的 1掌握二叉树的数据类型描述及二叉树的性质；2掌握二叉树的链式存储结构(二叉链表)的建立算法；3掌握二叉树的二叉链表存储结构上的基本运算的实现。二、实验内容对一份长短不定的由ASCII字符构成的报文按照以下步骤进行编码和译码：编码：1. 扫描报文文件，完成ASCII字符频度的统计；2. 依据ASCII字符出现的频度建立哈夫曼树；3. 根据哈夫曼树的信息对报文文件进行编码并写入输出文件。译码：扫描由二进制符号构成的文件，根据哈夫曼树对其进行译码，并把译码后的信息写入另一输出文件。三、 实验要求1. 根据实验内容编程，上机调试、得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时4学时。五、实验步骤1. 进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。（1） 报文文件，进行ASCII字符频度统计；（2） 根据频度建立Huffman树；（3） 根据Huffman树的信息进行编码并将编码写入输出文件；（4） 扫描由二进制符号构成的文件，根据Huffman树对其进行译码，并把译码后的信息写入另一输出文件。参考程序（略）。 六、选作实验1、表达式求值问题：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，并利用给定的优先关系实现对算术四则混合表达式的求值，并演示在求值过程中运算符栈、操作数栈、输入字符和主要操作变化过程。用二叉树的结构来存储表达式。2、家谱管理系统：对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。采用孩子兄弟表示法链式存储结构来存储家谱信息。实验三 图形结构：公交路线管理模拟系统一、 实验目的1. 掌握图的数据类型描述及定义；2. 掌握用邻接表来存储图；3. 理解并掌握图的遍历等运算在邻接表上的实现。二、实验内容根据公交线路信息建立邻接表并实现查找路线、计算两站之间路线长度、修改路线长度、在两站之间插入路线、删除两站间的路线、判断两站之间是否存在路线、查找两站之间最短路线长度等功能。三、实验要求1. 根据实验内容编程，上机调试、得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时4学时。五、实验步骤1. 进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。（1） 根据公交线路信息建立邻接表；（2） 将每个功能写成一个函数来完成对数据的操作；（3） 完成主函数以验证各个函数功能并得出运行结果。六、选作实验1、设计一个交通导航咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。2、假设一个城市有n个小区，要实现n个小区之间的电网都能够相互接通，构造这个城市n个小区之间的电网，使总工程造价最低。请设计一个能满足要求的造价方案。可以用带权的无向图（即无向网）表示这n个小区之间的电网连接，其中顶点表示小区，权值表示城市之间电网建设的造价，构造一个无向网的最小生成树即是满足要求的最低电网连接造价方案。实验四 查找一、 实验目的1. 掌握各种查找算法的基本思想、适用条件及算法实现；2. 熟练掌握二叉排序树的构造和查找方法；3. 掌握散列存储结构的思想，能选择合适的散列函数，实现不同冲突处理方法的散列表的查找与建立；4. 掌握运用不同类型数据结构的查找算法解决应用问题。二、实验内容 从以下1、2和3、4中各选择一项内容1. 建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。（为了简化算法，数据元素只含一个整型量关键字字段，数据元素的其余数据部分忽略不考虑。）2. 查找表的存储结构为有序表，即表中记录按关键字大小排序存放。输入待查数据元素的关键字进行查找。（为了简化算法，记录只含一个整型量关键字字段，记录的其余数据部分略不考虑。程序要求对整型量关键字数据的输入按从小到大排序输入。）3. 编程实现二叉排序树的创建、查找、插入、输出等算法。4. 设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。三、实验要求1. 根据实验内容编程，上机调试、得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时2学时。五、实验步骤1进入编程环境，建立一新文件；2. 参考实践教程中的相关内容，编写程序，观察并分析输出结果。参考程序（略）。六、选作实验编程实现一个开放式的高校本科招生最低录取分数线的查询系统，供师生和家长查询。高校自愿放入该校的信息，可能随时有高校加入。要求实现的查询功能有：查询等于用户给定分数的高校；查询大于(或小于)用户给定分数的高校；查询最低录取分数线在用户给定的分数段中的高校。该实验主要的功能是查找，查找表为高校最低录取分数信息的集合。根据题意可知，该查找表中的元素个数可能随时增减，所以它是一个动态查找表，可采用树状结构保存。为了提高查询速度，可建立二叉排序树并在二叉排序树中实现查找。第一个要求可以直接利用一般的二叉排序树的查找算法实现。第二个要求可以利用比较二叉排序树根结点的关键字值和给定的分数实现，若前者大于或等于后者，根结点及其右子树中的结点全部满足要求，再在根结点的左子树中查找；否则只在根结点的右子树中查找即可。第三个要求可以利用比较二叉排序树根结点的关键字值和给定的分数段实现，若前者在给定的分数段中，根结点就满足要求，则在根结点的左、右子树中继续查找即可：若前者给定的分数段的左侧，只在根结点的右子树中查找即可；若前者在给定的分数段的右侧，只根节点的左子树中查找即可。实验五 排序一、 实验目的1. 掌握各种排序算法的基本思想、适用条件及算法实现；2. 掌握各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂性和稳定性的分析方法。二、实验内容 从以下1、2中各选择一项内容1 随机函数产生10000个随机数，用直接插入、二分插入、希尔、冒泡、直接选择等排序方法排序，并统计每一种排序所花费的时间。2 随机函数产生30000个随机数，用快速、堆、归并等排序方法排序，并统计每一种排序所花费的时间。三、实验要求1. 根据实验内容编程，上机调试、得出正确的运行程序。2. 写出实验报告（包括源程序和运行结果）。四、实验学时6学时。五、实验步骤1. 进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。 算法提示为了产生随机数，必须用到头文件stdlibh中的两个函数srand()和rand()来设置随机种子以及产生随机数。为了能够计时，必须用到头文件timeh中的time()和difftime()两个函数，time()用于截取计算机内的时钟，difftime()用于得到两次时钟间隔的时间(秒)。每一种排序方法都单独写成子函数形式，然后用主函数调用它。为了能查看排序前后的效果，可以单独写一个子函数输出数组结果，在排序前后分别调用它，可以看到排序前后的结果。 算法实现内容一参考程序（略）。内容二参考程序（略）。六、选作实验设计一个算法，指出一个无序序列中的任意一个元素是第几大元素（从小到大数），要求比较的次数最少。实验六 综合实验一、 实验目的1. 熟练掌握各种数据结构的逻辑结构和存储结构；2. 提高综合运用各种数据结构及其算法解决应用问题的能力；3. 扩大编程量，完成模块化程序设计的全过程。二、实验内容模拟一个航班订票系统，要求能够录入、修改、删除和查询航班信息，并为顾客提供订票和退票服务。三、实验要求航班信息包括航班号（具有惟一性）、起降时间、起飞城市、抵达城市、航班票价、票价折扣、总座位数和出票数。航班信息管理和客户服务要求完成以下功能：1. 录入航班信息：可成批录入（存于一个数据文件中），也可单个录入。2. 修改航班信息：根据航班号修改航班信息。3. 删除航班信息：根据航班号删除航班