《数据结构与算法综合实验》讲义----2017版[PDF版]

《数据结构与算法综合实验》讲义

金英编写

黑龙江大学

计算机科学技术学院

软件学院

2017年 3月

综合实验又称为课程设计，需要学生综合运用所学知识解决与实际应用紧密结合的、规模较大的问题，通过分析、设计、编码和调试等各环节的训练，使学生深刻理解、牢固掌握、综合运用数据结构和算法设计技术，增强分析问题、解决问题的能力，培养项目管理与团队合作精神。

整体要求：（1）系统应具有合理的界面设计，并易于操作，若具有可视化界面更佳；（2）编码风格良好；（3）该系统用控制台程序即可实现；（4）编程语言不限。

本课程要求实验采用基本的软件工程开发方法，将软件开发过程分为需求分析、系统设计、编码实现、系统测试4个阶段。每个阶段设置相应的里程碑进行检查，对学生的设计过程进行评价。

（1）需求分析阶段

首先要充分分析和理解问题，明确要求做什么？限制条件是什么？即要确定需要实现那些功能（任务），并对所需完成的任务做出明确的回答，如，输入数据的类型、值的范围及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式输入，结束标志是什么？是否接受非法输入？对非法输入的回答方式是什么等。另外，还应该为调试程序准备好测试数据，包括合法的输入数据与非法的输入数据。同时，实验小组应该对设计工作进行分工，并形成小组成员通过的书面记录。

（2）概要设计和详细设计阶段

设计通常分为概要设计与详细设计两步。

在进行概要设计时，确定数据的逻辑结构，并要求按照自顶向下逐步求精的原则划分模块，画出模块间的调用关系图。

在进行详细设计时，要求定义数据的存储，并画出各模块（函数）的程序流程图或写出伪代码。

（3）编码实现阶段

在详细设计的基础上，用特定的程序设计语言编写程序。良好的程序设计风格可以保证较快地完成程序测试。程序的每行不要太长，每个函数不要太大，当一个函数太大时，可以考虑将其分解为较小的函数。对函数功能、核心语句、重要的类型和变量等应给出注释。一定要按凹入格式书写程序，分清每条语句的凹入层次，上下对齐层次的括号，以便发现语法错误。

（4）测试阶段

采用测试数据进行测试，列出实际的输入、输出结果、预期结果。

（5）总结与整理报告阶段

调试正确后认真整理源程序及注释，提交带有完整注释且格式良好的源程序，并撰写课程设计报告。

课程设计报告中除了上面提到的分析、设计过程外，还用给出下面几方面的内容。

①调试分析：调试过程中主要遇到哪些问题？如何解决的？

②算法分析：核心算法的时间复杂性与空间复杂性分析。

③改进设想、经验和体会。

本课程修读要求

本课程分为三个阶段实施，第一阶段：综合实验一，占40分，个人项目，完成题目1，在课程的第2-3周考核系统实现和报告撰写情况；第二阶段：综合实验二，占20分，个人项目，完成题目2，在课程的第4周考核系统实现；第三阶段：综合实验三，占40分，团队项目，每个团队由3人构成，题目自选，选题要求是具有创新性、实用性、运用到数据结构与算法（也鼓励运用高级数据结构与算法或创造新算法），工作量适合3人3周内完成，在课程的第5-6周答辩。具体的成绩构成见表1。

表1. 《数据结构与算法综合实验》成绩构成表

一、农夫过河问题

1. 问题描述

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。

2. 设计要求

求出农夫将所有东西运过河的方案后，具体的输出格式要求如表1所示。

表2 农夫过河问题的一个可行性方案

3．设计思想

农夫过河问题的搜索过程可采用广度优先搜索和深度优先搜索（递归的回溯）或其他优化的搜索策略（如A*算法、爬山法等）实现。

(1) 数据结构设计

模拟农夫过河需要对问题中每个角色的位置进行描述。可用一个整数来表示一个4位二进制数，该4位二进制数顺序分别表示农夫、狼、羊和白菜的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。

还需要一个数据结构记录已被访问过的各种状态，以及已被发现的能够到达当前这个状态的路径（可通过记每个状态的前驱实现）。可通过构造一个包含16个元素的整数顺序表route来列举所有16种状态（二进制0000到1111）。顺序表route的每个分量初始值为-1，第i个元素记录状态i是否被访问过，若已被访

问过，则在这个顺序表元素中记录前驱状态值。表route中的元素具有非负值表示这个状态已被访问过或者正被考虑。最后可以通过表route中元素的值建立正确的状态路径。

求解农夫过河问题的广度优先搜索算法，需要用到一个整数队列，它的每个元素表示一个可以安全到达的中间状态。（农夫过河问题若采用非递归的深度优先搜索算法求解，则需要用到一个整数栈，它的每个元素表示一个可以安全到达的中间状态。）

(2)算法设计

①搜索算法设计

搜索过程可利用广度优先搜索算法或深度优先算法（递归的回溯算法）从初始状态二进制0000（全部在河的南岸）出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111（全部到达河的北岸）为最终目标，并且在序列中的每一个状态都可以从前一个状态得到。为避免重复，要求在序列中不出现重复的状态。

②确定状态的安全有效性的功能模块设计

通过位置分布的代码来判断当前状态是否安全，使用“异或”位操作来考察狼和羊、羊和白菜是否在同一侧，且它们与农夫不一侧。若是，该状态即为不安全状态，否则为安全状态。若一个状态已经被访问过，或只有农夫一人从南岸过到北岸，则该状态被判为无效状态。若状态安全且有效，则返回1，否则返回0。

③输出模块设计

输出农夫过河问题的可行性方案时，可从目标状态（1111）开始，将其记入栈中，然后再找出其前驱，记入栈中，然后在找其前驱，…，直到找到的是开始状态（0000）为止。要求输出时根据位置分布代码（即4位二进制数）各个位置上的0、1代码所表示的含义输出容易理解的文字。

4．评价标准

若本实验项目占40分，其中，

（1）实现第一种搜索算法（如广度优先搜索算法）得15分。

（2）实现第二种搜索算法得5分。

（3）实现优化的搜索算法得2分。

（4）界面友好、美观，最好能有可视化界面，得3分。

（5）设计报告占15分。

二、划分江湖上大侠门派问题----等价类划分问题

-----（并查集的应用）1. 问题描述

如果某种关系具有自反性，对称性和传递性，那么就称这种关系为等价关系。自反性就是任何一个事物总可以和自己有这样的关系；比如：血型相同的关系，自己和自己总是血型相同的关系；对称性是如果A事物和B事物有这样的关系，则B事物也和A事物有这种关系；比如：血型相同的关系，显然是满足这个条件的；传递性则是说如果A事物和B事物有此关系，B事物和C事物也有这种关系，那么A和C有此关系。又比如：血型相同关系，A与B血型相同，B与C血型相同，则A与C血型相同，所以血型相同关系是等价关系。若将同一种血型看成是一个等价类，划分出不同血型的群体就变成了等价类划分问题。

传说江湖散落着各种大侠，整天没事儿干，背个剑走来走去，碰到和自己不是同一门派的人，就打一架。但是他们很讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”。只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人，江湖上就形成了一个一个的门派，通过两两之间的朋友关系串联起来。于是在同一个门派的人就可以放心往死了打。我们可以在每个门派内推举出一个比较有名望的人，作为该门派的掌门人，这个人就是他们的老大。

例如：有10个大侠，编号分别是1-10，有11条朋友关系：（6,1），（5,4），（4,9），（7,6），（10,5），(3,2)，(9,10)，（8,3），（7,2），（2,1），（7,8），其中（6,1）表示编号6的人与编号1的人是，其余类似。可以得出（1,2,3,6,7,8）这六个人属于同一个门派，（4,5,9,10）这4个人属于同一个门派，整个江湖共有2个门派。

我们的任务是找出江湖上大侠的门派划分。显然一门派可以看成是一个等价类，因而划分门派问题就变成了等价类划分问题。

2. 设计要求

输入设计：输入等价关系对（即朋友关系对）。

输出设计：找出江湖上共有多少个门派，并按门派输出所有大侠。

3. 设计思想

本问题可以利用并查集实现。并查集是一种抽象数据类型，它是若干个不相交的动态集合的集合S={A，B，…}，支持以下的运算：

?MakeSet(x): 构造一个集合，它只包含一个元素x;

?Union(x,y): 将x所在集合和y所在的集合合并成一个集合;

?Find (x): 找出元素x所在集合。

（1）数据结构设计

在本问题中，可以将每个门派（等价类）描述为一个树，树中每个非根结点都指向其双亲结点（直接上司），用根元素（掌门人）作为门派（等价类）的标识，整个江湖可看成是一个森林。例如现在江湖有两个门派，分成如图1所示的层次关系。该森林可用双亲表示法存储表示。

图1 江湖门派层次示意图

为了最后能按帮派输出大侠, 可为每个帮派设一条链，每条链都设首尾指针，从而使得合并两个链表时效率较高。

（2）算法设计

假设江湖上共有n个大侠，初始时，每个人都是一个独立的门派（等价类），可用MakeSet(x)实现。

有一天，蓝炳走在路上，碰到了杨再宁，两人一言不合就想开打，但在开打之前他们需要先逐级查询自己的老大。发现老大不是一个人，于是今日注定不太平。打完以后决定认个朋友。每加入一个朋友关系（x，y），先查看x和y都属于哪个门派（等价类），可用Find (x)和Find(y)实现，即分别找出x与y所在树的根结点（门派老大）。

若每次查询都做优化处理，使整个门派树的层数都会维持在比较低的水平上，则检索效率会更高。比如，蓝丙和冯旭都直接做掌门人的直接下属，如图2所示。

如果x和y属于同一个门派（等价类），即他们的老大（所在的树根）是同一

个，则关系（x，y）不用处理；否则，将x所在的门派（等价类）和y所在的门派（等价类）合并成一个门派（等价类），可用Union(x,y)实现，即将x所在的树与x所在的树合并为一棵树。

图2 查询时进行处理的示意图

有一天，蓝炳走在路上，碰到了杨再宁，两人一言不合就想开打，但在开打之前他们需要先逐级查询自己的老大。发现老大不是一个人，于是今日注定不太平。打完以后决定认个朋友，从而导致两个门派合并，那么谁当老大呢？一种方案是原来的两个老大中谁当合并后门派的老大都可以。还有一种方案是按江湖规矩，大帮派的老大成为合并后新帮派的老大，如图3和图4所示。第二种方案有利于提高检索速度。

图3 未压缩路径时小门派合并到大门派示意图

图4 压缩路径时小门派合并到大门派示意图

合并两个帮派时，可将两个帮派对应的链表首尾相连。

4.评价标准

本实验项目占20分，其中，

（1）实现基本功能。（10分）

（2）分别输出没个门派的所有大侠。（5分）

（3）算法时间复杂度与空间复杂度尽可能低。（2分）

（4）界面友好，使用方便，最好能有可视化界面。（3分）

三、全国交通咨询系统

1. 问题描述

处于不同目的的旅客对交通工具有不同的城市间的交通咨询系统，为游客提供两种或三种最优决策的交通咨询。

2. 整体要求

●该系统应具有合理的界面设计，并易于操作，若能有图形界面更好；

●编码风格良好；

●该系统即可用控制台程序实现，也可用可视化界面程序实现；

●编程语言不限。

3.设计要求

①提供对城市信息进行编辑（增、删、改等）的功能。

②城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班

表进行编辑（增、删、改等）的功能。

③提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。

旅途中耗费的总时间应该包括中转站的等候时间。

④提供中转次数最少的最优决策。【选做】

⑤咨询以人机交互方式进行。

输入信息：起始站、终点站、最优决策原则。

输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明于何时乘坐哪一趟列车或哪一次航班到何地。

⑥参考全国交通图，自行设计列车时刻表和飞机航班。

4. 设计思想

（1）数据结构设计

以邻接表作为交通图（有向网络）的存储结构，表示边的结点内除了含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费，以及出发和到达时间等多种属性。

飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；

列车时刻表则需根据交通图给出各个路段的详细信息。

对全国城市交通图和列车时刻表及飞机航班表进行编辑，应该提供文件形式输入和键盘输入两种方式。

（2）算法设计

解决提供最快到达或最省钱到达方案问题，可用弗洛伊德算法实现。也可依次把有向网络中的每个顶点作为源点，重复调用迪杰斯特拉算法n次实现。

解决提供中转次数最少的最优决策问题，可用图的广度优先搜索算法实现。

5. 评价标准

本设计是一个比较综合的练习，涉及图的存储、迪杰斯特拉算法、弗洛伊德算法，图的广度优先搜索算法。此外，还涉及到线性表的存储及其增、删、改等操作。本设计的目的是培养学生的综合设计能力、编程与调试能力。评分标准如下。

若本实验项目占40分，其中，

（1）实现基本功能，界面友好，使用方便，最好能有可视化界面。（15分）（2）实现第二个求最短路径的算法。（3分）

（3）实现广度优先搜索算法。（2分）

（4）创新性；3分。

（5）实用性：3分。

（6）团队合作：4分。

（7）PPT及答辩情况：10分。