数据结构实验指导书
一、实验目的
《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因，使得掌握这门课程具有较大的难度：
1）理论艰深，方法灵活，给学习带来困难；
2）内容丰富，涉及的知识较多，学习有一定的难度；
3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度；
根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。
课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面：
（1）加深对课堂讲授内容的理解
实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。
不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出
现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。
(2) 培养学生软件设计的综合能力
平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。
通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。
(3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行
程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。
完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。
二、实验要求
常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目：
1) 问题分析和任务定义
在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的
形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。
2) 逻辑设计和详细设计在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义( 包括数据结构的描述和每
个基本操作的功能说明) ，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。
3) 编码实现和静态检查编码是把详细设计的结果进一步求精为程序设计语言程序。如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。
然而，不管你是否写出编码的程序，在上机之前，认真的静态检查是必不可少的。静态检查主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查) ；二是通过对程序深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。
4) 上机准备和上机调试
上机准备包括以下几个方面：
(1) 注意同一高级语言文本之间的差别;
(2) 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动;
(3) 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。应该能够
熟练运用高级语言的程序调试器DBBU调试程序；
(4) 上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层函数。在调试过程中可以不断借助DEBU(的各种功能，提高调试效率。调试
中遇到的各种异常现象往往是预料不到的，此时应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。
5) 总结和整理实验报告
实验结束后，要整理实验结果并认真分析和总结，根据教师要求写出实验报告。
实验报告一般包括如下内容：
(1) 实验内容
(2) 实验目的
(3) 程序清单
(4) 调试步骤
(5) 分析与思考:调试过程及调试中遇到的问题及解决办法；调试程序的心得与体会其他算法的存在与实践等。若最终未完成调试，要认真找出错误并分析原因等。
三、实验内容
实验一Joseph 问题求解算法的设计与实现
1、实验学时
3 学时
2、实验目的
掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。
3、问题描述
约瑟夫(Joseph)问题的一种描述是：编号为1, 2,…，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。开始任选一个正整数作为报数上限值m从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
4、基本要求
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
5、测试数据
m的初值为20; n=7, 7个人的密码依次为：3, 1, 7, 2, 4, 8, 4,首先m值为6 （正
确的出列顺序应为6，1，4，7，2，3，5）。
6、实现提示
程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n W 30。此题所用的循环链表中不需要“头结点” ,请注意空表和非空表的界限。
7、选作内容
向上述程序中添加在顺序结构上实现的部分。
实验二停车场管理
1 、实验学时
5 学时
2、实验目的
1）深入了解栈和队列的特性,掌握栈和队列的存储方法。
2）掌握栈和队列的基本操作,如初始化、入栈（队列）、出栈（队列）等,并能在实际问题背景下灵活运用。
3、问题描述
设停车场是一个可以停放n 辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列（大门在最南端,最先到达的第一辆车停放在车场的最北端） ,若车场内已经停满n 辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时,在它之后进入的车辆必须先退出场为它让路,待该辆车开出大门外, 其他车辆再按次序进入车场, 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用,试为停车场编制按上述要求进行管理的模拟程序。
4、基本要求以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序
列进行
模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对一组输入数据进行操作后的输出信息为：若是车辆到达, 则输出汽车在停车场内或便道上的停车位置；若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现。队列以链表结构实现。
5、测试数据
设n=2,输入数据为：（’A' 1, 5）, （' A', 2, 10）, （' D' 1, 5）, （' A , 3, 20），（‘ A'，4，25），（‘ A'，5，30），（‘ D'，2，35），（‘ D'，4，40），（‘ E'，0, 0）。其中：‘ A'表示到达（Arrival ）, ‘ D 表示离去
（Departure ）, ‘ E'表示输入结束（End）。
6、实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽
车，也用顺
序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
7、选作内容
1 ）两个栈共享空间，思考应开辟数组的空间是多少？2）汽车可以有不同种类，则他
们的占地面积不同，收费标准也不同，如 1 辆客车
和 1 。5辆小汽车的占地面积相同， 1 辆十轮卡车占地面积相当于3辆小汽车的占地面
积。
3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次
排到队尾。
4）停放在便道上的汽车业收费，收费标准比停放在停车场的车低，请思考如何修改
结构以满足这种要求。
实验三基于哈夫曼编码的通信系统的设计与实现
1 、实验学时
8 学时
2、实验目的
1 ）掌握二叉树的存储结构及其相关操作。
2）掌握构造哈夫曼树的基本思想，及其编码/ 译码过程。
3、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都
需要
一个完整的编/ 译码系统。试为这样的信息收发站设计一个基于哈夫曼编码的通信系统
4、基本要求
一个完整的系统应具有以下功能：
1）初始化处理：建立通信系统
（1）建立有100 句中文的信息集合，每个句子称为一条信息。
（2）输入编码参数：
①从终端输入编码字符集大小n,字符编码长度m （设n为4, m为8）;
②从终端输入编码字符（设为A，B，C，D）；
（3）生成每条信息的字符编码,构造字符编码集合;
（4）计算每个字符在字符编码集合中出现的概率;
（5）根据字符概率构造哈夫曼树,求出每个字符的二进制编码。
2）发送端信息编码
（1）用户从信息集合中选择一条信息,找到该信息对应的字符编码;
（2）根据该信息的字符编码,哈夫曼树求出的每个字符的二进制编码,构造出该信息的二进制编码,记录该二进制编码。（由于是软件模拟,没有发送设备,发送端的编码工作完成）。
3）接受端信息译码
（1）根据得到的信息的二进制编码,利用哈夫曼树求出的每个字符的二进制编码, 还原出信息的字符编码;
（2）根据信息的字符编码,找到对应的信息。
5、实现提示
1）本试验涉及到通讯学科的编码理论和信息学科的数据压缩技术。
2）根据参数生成的通信系统的所有信息的有效存储问题。
3）信息字符编码可参考随机数的方式生成,且要求保持唯一性。
实验四基于二叉排序树的商品信息查询算法的设计与实现
1、实验学时
8 学时
2、实验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入
和删除的方法。
3、问题描述
查找是数据处理的重要操作。请设计并实现基于二叉排序树的商品信息查询算法。完成信息的查询、插入、删除、查询频度的统计等功能。
4、基本要求
1）以链表作为存储结构，设计并实现基于二叉排序树的商品信息查询算法。
2）根据二叉排序树的动态变化，进行二叉树的平衡化处理。
3）实现信息的查询、插入、删除、查询频度的统计等功能。
5、测试数据随机生成。
6、实现提示
1）初始化：以商品名称为关键字，建立二叉排序树。
2）用户输入查询商品名称，在二叉排序树上查找，若找到，则显示商品的相关信息，并在相应的表上的相关字段上增加该商品查找次数。若未找到，则显示未找到信息给用户，并在相应的表上的相关字段上增加该商品查找次数。
3）根据商品的查找次数，形成商场的经营决策信息，反馈给决策者。
4）进行二叉树的平衡化处理，提高查找效率。
实验五内部排序算法效率比较平台的设计与实现
1、实验学时
6 学时
2、实验目的
掌握多种排序方法的基本思想，如直接插入、起泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。
3、问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。设计和实现内部排序算法效率比较平台，通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观的感受。
4、基本要求
1）对以下6 种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选
择排序、快速排序、希尔排序、堆排序。
2）待排序的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动）。
3）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。
5、测试数据
由随机数产生器生成。
6、实现提示
主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。
7、选作内容
1）增加折半插入排序、基数排序等。
2）对不同的输入表长作实验，观察检查两个指标相对于表长的变化关系。还可以对稳定性作验证。