数据结构实验指导书
信息工程学院计算机系
实验一 线性表实验
实验目的
熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现，其中重点熟悉链表的各种操作。 时间要求：4学时 问题描述：
约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码〈正整数〉，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求: 利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。
实现提示：
程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码(小于30)。
选作内容：
在顺序存储结构上实现上述问题的操作。
Input 输入包括两行，第一行包括报数上限值m和人数n，第二行为n个人的密码，所有数据之间由空格分隔。 Output 输出一行，共n个整数，表示各编号人的出列顺序。各数之间由空格分隔。 Sample Input 20 7 3 1 7 2 4 8 4 Sample Output 6 1 4 7 2 3 5 2
实验二 栈和队列实验
实验目的
熟悉栈和队列的基本特性，掌握栈和队列基本运算的实现过程。 时间要求：4+4学时 问题描述：
设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候, 一旦有车开走，则排在便道上的第一辆车即可开入，当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，当便道上汽车要离开时，排在它前面的汽车要先开走让路，然后再依次排到队尾，并且在便道上停车不收费。试为停车场编制按上述要求进行管理的模拟程序。
基本要求：
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列管理，每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时间，对每一组输入数据进行操作后的输出数据为： 若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便递上停留的时间不收费），栈以顺序结构实现，队列以链表结构实现。 实现提示：
需另设一栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含有两个数据项：汽车牌照号码和进入停车场的时间。 选作内容：
（1）两个栈共享空间，思考应开辟数组的空间是多少 ? （2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如 1 辆客车和 1.5 辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积 。 （3）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这神要求。 Input 输入第一行，包括两个数据，第一个整数为停车场最多可停放车辆数，第二个浮点数表示单位时间的停车费用。接下来有多行数据，每行有三个整数，第一个为0或1，0表示进
3 入车场，1表示离开车场；第二个整数为车号；第三个整数为进入或离开的时间。当一行中三个数均为0时表示输入结束，所有数据之间由空格分隔。 Output 输出为三部分，第一部分为按离开停车场顺序打印出的各车费用，每车一行，包括车号和费用(保留小数点后两位)。第二部分占一行为当前停车场中的所有车辆，从北到南顺序输出各车车号。第三部分占一行为当前便道上的所有车辆，从前向后顺序输出各车车号。各车号之间由一个空格分隔。 Sample Input 2 1.5 0 1 5 0 2 10 1 1 15 0 3 20 0 4 25 0 5 30 0 6 35 1 2 40 0 7 45 1 6 50 0 0 0 Sample Output 1 15.00 2 45.00 3 4 7 5 4
实验三 哈夫曼树实验
实验目的
熟悉非线性结构的特点 , 掌握非线性结构的存储方式及各种操作的实现方法，同时对自顶向下的程序设计方法、应用程序界面的设计、非线性结构的文件存储方法等方面的辑程技术进行训练。 时间要求：4+4学时 问题描述：
利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。
基本要求：
一个完整的系统应具有以下功能：
（1） I： 初始化。从终端读入字符集大小 n ，及 n 个字符和 n 个权值，建立哈夫曼树，并将其存于文件hfmtree中。
（2） C： 编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。
（3） D： 译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。
（4） P： 打印代码文件。将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。
（5） T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。
实现提示：
（1）用户界面可以设计为“菜单”方式：显示上述功能号，再加上“E”表示结束运性行结束，用户键入一个选择功能字符，则执行相应的功能，此功能执行完毕后再显示此菜单，直至用户选择了“E”为止。
（1） 在程序的一次执行过程中，第一次执行了I、D 或 C 命令之后，哈夫曼树已经在内存中存在了，不必再读入。每次执行中不一定执行 I 命令，因为文件 hfmtree 可能早已建好。
5
选作内容：
（1） 修改你的系统，使系统实现对自身源程序的编码和译码（注意特殊符号的编/译码问题）。
（2）实现各个转换操作的源/目的文件均由用户自己指定。
实验四 图的搜索实验
实验目的
熟悉图的相关操作，掌握图的搜索算法及其应用，同时进一步练习栈与队列在实际问题中的应用。 时间要求：4+4学时 问题描述：
一只老鼠走进了一个迷宫，这个迷宫是由M行N列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。迷宫在（1，1）处有一个入口，在（M,N）处有一个出口，在入口和出口之间有通路相通。问题是让你帮助老鼠找出从入口到出口的一条最短路径。
00001000 11001010 00010000 00001010 10100000 00111011 10001000 基本要求：
为老鼠找出一条从入口到出口的最短路径。 实现提示：
1、迷宫用数组表示，1代表是墙走不通，0表示可以通行。边界可以扩充为墙，即M×N迷宫用(M+2)×(N+2)数组表示。
2、向4个方向前进时的位移量可以用以下数组表示，处理时方便。
int move[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
3、采用图的广度优先搜索算法。 选作内容：
对给定的迷宫，统计出共有多少条不同的路径。
实验五 排序实验
实验目的
熟练掌握各种排序算法的实现方法，以及不同算法的特点，掌握各种排序方法的时间效率。
时间要求：4+4学时 问题描述：
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。对一组给定的数据，设计出各不同排序算法对其进行排序，给出各算法在排序中的关键字比较次数和关键字移动次数，以取得直观感受。 基本要求：
（1）对以下各排序算法进行比较：直接插入排序、冒泡排序、快速排序、简单选择排序、归并排序。
（2）待排序表的表长为100；一共有n组不同的数据，对每组数据用以上各排序方法进行排序，比较的指标为有关键字参加的比较次数和关键字的移动次数。 实现提示：
在算法的适当地方加入计数操作，计算关键字的比较次数和移动次数。 选作内容：
对算法的稳定性作验证。
Input 输入部分第一行为待排关键字的组数n，接下来为n行待排关键字，第行有100个整数所有数据之间由空格分隔。 Output 输出共n行，每行共有10个整数，表示5种排序方法排序的关键字比较次数和移动次数，即为：直接插入排序比较次数 直接插入排序移动次数 冒泡排序比较次数 冒泡排序移动次数 快速排序比较次数、快速排序移动次数 简单选择排序比较次数、简单选择排序移动次数 归并排序比较次数 归并排序移动次数 （下例待排关键字为5，实际提交测试数据为100） Sample Input 3 1 2 3 4 5 5 4 3 2 1 4 2 5 1 3 Sample Output 4 0 4 0 10 16 10 0 7 12 14 18 10 30 12 16 10 6 5 12 10 12 10 18 11 14 10 6 7 12
数据结构实验报告
实验一 线性表实验
班级：____________ 姓名：____________ 学号：____________
实验目的：
熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现，其中重点掌握线性表的链式表示时各种操作的实现。 问题描述：
约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，„，n的n个人按顺时针方向围坐一圈，每人持有一个密码〈正整数〉，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
需求分析：（包括对问题的理解，解决问题的策略、方法描述）
系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）
调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）
测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）
基本操作的实现：（对各基本操作实现的描述）
数据结构实验报告
实验二 栈和队列实验
班级：____________ 姓名：____________ 学号：____________
实验目的：
熟悉栈和队列的基本特性，掌握栈和队列基本运算的实现过程。重点掌握栈和队列各种操作的实现。 问题描述：
设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候, 一旦有车开走，则排在便道上的第一辆车即可开入，当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。
需求分析：（包括对问题的理解，解决问题的策略、方法描述）
系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）
调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）
测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）
基本操作的实现：（对各基本操作实现的描述）
数据结构实验报告
实验三 哈夫曼树实验
班级：____________ 姓名：____________ 学号：____________
实验目的：
熟悉非线性结构的特点 , 掌握非线性结构的存储方式及各种操作的实现方法，同时对自顶向下的程序设计方法、应用程序界面的设计、非线性结构的文件存储方法等方面的辑程技术进行训练。 问题描述：
利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。 基本要求：
一个完整的系统应具有以下功能：
（1） I： 初始化。从终端读入字符集大小 n ，及 n 个字符和 n 个权值，建立哈夫曼树，并将其存于文件hfmtree中。
（2） C： 编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。
（3） D： 译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。
（4） P： 打印代码文件。将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。
（5） T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。
需求分析：（包括对问题的理解，解决问题的策略、方法描述）
13
系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）
调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）
测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）
14
基本操作的实现：（对各基本操作实现的描述）(后面可加页)
数据结构实验报告
实验四 图搜索实验
班级：____________ 姓名：____________ 学号：____________
实验目的：
熟悉图的相关操作，掌握图的搜索算法及其应用，同时进一步练习栈与队列在实际问题中的应用。 问题描述：
一只老鼠走进了一个迷宫，这个迷宫是由M行N列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。迷宫在（1，1）处有一个入口，在（M,N）处有一个出口，在入口和出口之间有通路相通。问题是让你帮助老鼠找出从入口到出口的一条最短路径。 基本要求：
为老鼠找出一条从入口到出口的最短路径。
需求分析：（包括对问题的理解，解决问题的策略、方法描述）
16
系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）
调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）
测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）
基本操作的实现：（对各基本操作实现的描述）(后面可加页)
数据结构实验报告
实验五 排序实验
班级：____________ 姓名：____________ 学号：____________
实验目的
熟练掌握各种排序算法的实现方法，以及不同算法的特点，掌握各种排序方法的时间效率。
时间要求：4+4学时 问题描述：
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。对一组给定的数据，设计出各不同排序算法对其进行排序，给出各算法在排序中的关键字比较次数和关键字移动次数，以取得直观感受。
需求分析：（包括对问题的理解，解决问题的策略、方法描述）
系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）
调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）
测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）
基本操作的实现：（对各基本操作实现的描述）
