山东大学软件学院

《数据结构、算法与应用》实验指导书

一、            实验目的

《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

二、            实验要求

⒈ 问题分析

    充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。

2.概要设计

概要设计是对问题描述中涉及到的数据定义抽象数据类型，设计数据结构，设计算法的伪代码描述。在这个过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单，抽象数据类型尽可能做到数据封闭，基本操作的说明尽可能明确。而不必过早地考虑存储结构，不必过早地考虑语言的实现细节，不必过早地表述辅助数据结构和局部变量。

3.详细设计

在详细设计阶段，要设计具体的存储结构（即用C++描述抽象数据类型对应的类）以及算法所需的辅助数据结构，算法在伪代码的基础上要考虑细节问题并用C++描述。

此外，还要设计一定的用户界面。数据结构课程实验的主要目的是为了培养数据结构的应用能力，因此在实验中不要求图形界面，只要在屏幕上提示用户每一步操作的输入，并将结果物出即可。

4.编码实现和静态检查

将详细设计阶段的结果进一步优化为C++程序，并完成静态检查。

很多初学者在编写程序后都有这样的心态：确信自己的程序是正确的，认为上机前的任务已经完成，检查错误是计算机的事。这种心态是极为有害的，这样的上机调试效率是极低的。事实上，即使有几十年经验的高级软件工程师，也经常利用静态检查来查找程序中的错误。

注意： 采用良好的编程风格；关键操作要有注释。

5. 测试用例设计

    准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。

6.上机调试

    对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。

7.*为选做内容

三、  实习报告内容

⒈问题描述： 包括目标、任务、条件和约束的描述。

⒉设计：

⑴ 数据结构设计和核心算法设计描述；

⑵主控及功能模块层次结构；

⑶主要功能模块的输入、处理(算法框架描述)和输出；

⑷功能模块之间的调用与被调用关系等。

⒊测试： 测试范例，测试结果，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。

⒋使用说明和作业小结：

⑴使用说明主要描述如何使用你的程序以及使用时的主要事项；

⑵在小结中说明程序的改进思想、经验和体会，并回答教师布置的讨论题。

⒌提交一份程序清单及运行示例的结果。

  将以上各项文字材料及程序清单等整理成文档，形成一个完整的报告。

四、开发工具

              Microsoft Visual C++

Eclipse  IDE  For  C++

五、 实验时间、地点

   5-13周

实验一 递归练习

一、实验目的

1、熟悉开发工具的使用。

2、掌握递归的实现思想。

二、实验内容

1、输出n个整数的全排列。

2、输出n个整数的所有子集。

三．实现提示

实验二 排序算法

一、实验目的

掌握各种排序方法的实现思想。

二、实验内容

1、创建排序类。

2、提供操作:选择排序、冒泡排序、插入排序、基数排序、快速排序、归并排序。(快速排序、归并排序讲到之后再做)

3、*能够显示各种排序算法的中间过程。

实验三 线性表操作

一、实验目的

1、掌握线性表的基本操作：插入、删除、查找。

2、掌握链表遍历器的使用方法。

二、实验内容

1、创建线性表类。线性表的存储结构使用链表。

2、提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。

3、接收键盘录入的一系列整数（例10,25,8,33,60）作为节点的元素值，创建链表。输出链表内容。

4、输入一个整数（例33），在链表中进行搜索，输出其在链表中的位置。如果不存在输出0。

5、使用链表遍历器实现链表的反序输出。

6、创建两个有序链表，使用链表遍历器实现链表的合并。

实验四  堆栈的应用

一、实验目的

掌握堆栈的使用。

二、实验内容

1、计算数学表达式的值。

输入数学表达式，输出表达式的计算结果。数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、“)构成，例如 2 + 3 * ( 4 + 5 ) – 6 / 4。假定表达式输入格式合法。

*2、以一个 m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

   ⒈问题描述

         从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过， 数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。

⒉基本要求

(1)            输入数据

a.       输入迷宫的大小m行和n列，两者为整数

b.       由随机数产生0或1，建立迷宫。

(2)            输出数据

首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：

        (m，n)， ……， (I，j)， ……， (1，1)

如无通道，则打印：

        THERE IS NO PATH.

⒊实现提示

(1)            数据结构

a） 为了在程序中判断方便，把迷宫扩展成为MAZE(0：m+1，0：n+1)，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。

     b） 用二维数组MOVE(1：8，1：2)存放八个方向上的位置量，如

      图所示：

                       MOVE的设置情况

c)      为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻找路径的过程中，若通过了位置（I，j），则将MARK（I，J）置为为1。

d)     为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1， 0..2）数组，对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置I和j，Q(P，2)记下其出发点在Q数组中的下标。

（2）算法基本思想

  将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。

  具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(I，j)=0 且MARK(I，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m ，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。

实验五  二叉树操作

一、实验目的

1、掌握二叉树的基本概念，链表描述方法；遍历方法。

二、实验内容

1、创建二叉树类。二叉树的存储结构使用链表。

2、提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。

3、对建立好的二叉树，执行上述各操作。

4、接收键盘录入的二叉树前序序列和中序序列(各元素各不相同)，输出该二叉树的后序序列。

实验六  堆和搜索树

一、实验目的

1、掌握堆和搜索树的基本概念，插入、删除方法。

二、实验内容

1、创建最大堆类。最大堆的存储结构使用链表。

2、提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。

3、接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。

4、堆排序。

实验七  图的操作

一、实验目的

1、掌握图的基本概念，描述方法；遍历方法。

二、实验内容

1、创建图类。二叉树的存储结构使用邻接矩阵或链表。

2、提供操作:遍历、BFS、DFS

3、对建立好的图，执行上述各操作。

4、输出生成树。

5、输出最小生成树。

 

第二篇：20xx级数据结构实验指导书

《数据结构》

实验指导书

计算机学院数据结构课程组

20##-9

前言

　　

　　计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。

　　数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。
实验一  线性表的基本操作及其应用

一、实验目的

1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。

二、实验内容

本次实验提供3个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况任选一个！

题目一：单链表的基本操作（*）

[问题描述]

实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。

[基本要求]

（1）依次从键盘读入数据，建立带头结点的单链表；

    （2）输出单链表中的数据元素

（3）求单链表的长度；

（4）根据指定条件能够取元素和修改元素；

（5）实现在指定位置插入和删除元素的功能。

 [测试数据]

由学生任意指定。

题目二：约瑟夫环（**）
[问题描述]
　　约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

[基本要求]
　　利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
[测试数据]

由学生任意指定。
　　如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4；

（正确的输出结果应为6，1，4，7，2，3，5）。
    (报告上要求写出多批数据测试结果)
[实现提示]
　　程序运行后首先要求用户输入初始报数上限值m，人数n,(设n≤30)。然后输入各人的密码。

[选作内容]
　　向上述程序中添加在顺序结构上实现的部分。

题目三：多项式的表示及相加（***）

[问题描述]

设计一个算法，以实现一元稀疏多项式的加法运算。

[基本要求]

（1）输入并建立多项式；

（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，……，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；

（3）多项式a和b相加，建立多项式a+b。

[测试数据]

由学生任意指定。

[实现提示]
　　用带表头结点的单链表存储多项式。

[选作内容]
　　多项式a和b相减，建立多项式a-b。

三、实验前的准备工作

1、掌握线性表的逻辑结构。

2、掌握线性表的链式存储结构。

3、熟练掌握线性表的插入、删除等操作。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

实验二  栈和队列的基本操作及其应用

一、实验目的

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验内容

本次实验提供2个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况任选一个！

题目一：回文判断（*）

[问题描述]

对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。

[基本要求]

（1）数据从键盘读入；

（2）输出要判断的字符串；

    （3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。

[测试数据]

由学生任意指定。

题目二：商品货架管理（**）

[问题描述]

商店货架以栈的方式摆放商品。生产日期越近的越靠近栈底，出货时从栈顶取货。一天营业结束，如果货架不满，则需上货。入货直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，使生产日期越近的越靠近栈底。
[基本要求]

设计一个算法，保证每一次上货后始终保持生产日期越近的商品越靠近栈底。

[实现提示]

可以用一个队列和一个临时栈作为周转。

[测试数据]

由学生任意指定。

题目三：舞伴问题（**）

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

【实验提示】

先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。

【实验要求】

利用队列实现，存储结构采用顺序或链式均可

题目四：        Rails

Description

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

Input

The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0.

The last block consists of just one line containing 0.

Output

The output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null'' block of the input.

Sample Input

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

Sample Output

Yes

No

Yes

三、实验前的准备工作

1、掌握栈的逻辑结构和存储结构。

2、熟练掌握栈的出栈、入栈等操作。

3、掌握队列的逻辑结构和存储结构。

4、熟练掌握队列的出队、入队等操作

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

实验三  二叉树的基本运算

一、实验目的

1、使学生熟练掌握二叉树的逻辑结构和存储结构。

2、熟练掌握二叉树的各种遍历算法。

二、实验内容

[问题描述]

建立一棵二叉树，试编程实现二叉树的如下基本操作：
1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
3. 求二叉树的深度/结点数目/叶结点数目；(选做)
4. 将二叉树每个结点的左右子树交换位置。（选做）

 [基本要求]

从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），

[测试数据]

如输入：ABCффDEфGффFффф（其中ф表示空格字符）
　　则输出结果为

先序：ABCDEGF
　　中序：CBEGDFA
　　后序：CGEFDBA

层序：ABCDEFG

[选作内容]

采用非递归算法实现二叉树遍历。
三、实验前的准备工作

1、掌握树的逻辑结构。

2、掌握二叉树的逻辑结构和存储结构。

3、掌握二叉树的各种遍历算法的实现。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

实验四  哈夫曼树与哈夫曼编码

一、实验目的

1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

二、实验内容

[问题描述]

　　已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

[基本要求]

　　1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman

树。（具体算法可参见教材P147的算法6.12）
　　2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。

对给定的待编码字符序列进行编码。
[选作内容]

　　１. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。

译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。

　4. 打印 Huffman树。

［测试数据］

利用教材P.148 例6－2中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为 “CFBABBFHGH”(也可自己设定数据进行测试)。

三、实验前的准备工作

1、掌握树的逻辑结构。

2、掌握哈夫曼树的定义及生成算法。

3、掌握哈夫曼编码的方法。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

实验五  图的基本操作

一、实验目的

1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

二、实验内容

[问题描述]

　　对给定图，实现图的深度优先遍历和广度优先遍历。

[基本要求]

　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

【测试数据】
　　由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作

1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的两种遍历算法的实现。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

实验六  图的应用

一、实验目的

1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、掌握如何应用图解决各种实际问题。

二、实验内容

本次实验提供2个题目，学生可以任选一个！

题目一：最小生成树问题

[问题描述]

若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。

[基本要求]

1．利用克鲁斯卡尔算法求网的最小生成树。

2．要求输出各条边及它们的权值。

［实现提示］

通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数。

图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。

 ［测试数据］

由学生依据软件工程的测试技术自己确定。

题目二：拓扑排序的应用

    已知一个有向图，试编程判断该图是否

题目二：最短路径问题

[问题描述]

　　给定一个无向网，可以求得任意一对顶点之间的最短路径。

[基本要求]

　  以邻接矩阵为存储结构，实现弗洛伊德算法求解每一对顶点之间的最短路径及最短路径长度。

[测试数据]

　　由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作

1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的各种应用的实现。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

实验七  查找、排序的应用

一、实验目的

1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。

2、学会比较各种排序与查找算法的优劣。

3、学会针对所给问题选用最适合的算法。

4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。

二、实验内容

[问题描述]

　对学生的基本信息进行管理。

[基本要求]

设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：

1．总成绩要求自动计算；

2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；

排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。

[测试数据]

　　由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作

1、掌握哈希表的定义，哈希函数的构造方法。

2、掌握一些常用的查找方法。

1、掌握几种常用的排序方法。

2、掌握直接排序方法。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。