数据结构上机实验.doc

上机实验要求及规范
《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下：
1.问题分析与系统结构设计
充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。
2.详细设计和编码
详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。
编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。
3.上机准备
熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。
4.上机调试程序
调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。
5.整理实习报告
在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。

注意：1.算法中元素类型根据实际需要选择。
2.实验题目前带*者难度较高，学生可自选；其余部分为基本内容，应尽量完成（至少完成80%，否则实验不合格）。
实验一 线性表
一、实验目的
1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。
2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。
二、实验内容
1. 输入整型元素序列利用插入算法建立一个非递减有序表。请设计程序实现。要求：采用顺序存储结构实现；采用链式存储结构实现；比较两种方法的优劣。
2. 设计程序实现把题1建立的顺序表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。
3. 设计程序实现把题1建立的单链表中值相同的多余结点的删除。
4. 约瑟夫环问题。有n个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人又出列，如此下去，直到所有人都出列为止。试设计确定他们出列次序的程序。要求选择单向循环链表作为存储结构模拟整个过程，并依次输出出列人的编码。
*5. 用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。要求：通讯录是按姓名项的字母顺序排列的；能查找通讯录中某人的信息。
*6. 超长正整数的加法，设计一个程序实现两个任意长的整数求和运算
【提示】 可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位开始每四位组成的数字，依次放在链表的第一个、第二个、……第n个结点中，不足四位的最高位存放在链表的最后一个结点中，表头结点值规定为-1。
-1
4321
8765
8909
567
head
例如：大整数“567890987654321”可用如下的头结点的链表表示：

按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其代入下一个结点进行运算。
*7. 综合训练。利用单链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。

实验二 栈和队列
一、实验目的
1. 掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
2. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
3. 了解和掌握递归程序设计的基本原理和方法。
二、实验内容
1．采用顺序存储实现栈的初始化、入栈、出栈操作。
2．采用顺序存储实现循环队列的初始化、入队、出队操作。
3. 设单链表中存放着n个字符，利用栈结构，试设计算法判断字符串是否中心对称。例如xyzzyx即为中心对称的字符串。
4. 假设一个一维向量data[0…maxsize-1]存放一个循环队列中的元素，同时设变量rear和len分别指示循环队列中队尾元素的位置和内含元素的个数。试写出此循环队列的队满条件，并设计出相应的入队和出队的算法。
*5. 阿克曼函数（Ackermann’s function）定义如下：
n+1 当 m=0 时
akm(m-1,1) 当 m>0,n=0 时
akm(m-1,akm(m,n-1)) 当 m>0,n>0 时
akm(m,n)=
人们之所以研究该函数，是因为m和n值的较小增长都会引起函数值的极快增长。
（1）设计一个递归算法的源程序，上机运行。
（2）设计一个非递归算法的源程序，上机运行。并进行比较。
*6．综合训练。利用栈实现表达式求值算法。
1
1 1
1 2 1
1 3 3 1

*7．二项式(a+b)n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。

实验三 串
一、实验目的
1. 熟悉串类型的实现方法，了解简单文字处理的设计方法。
2. 熟悉C语言的字符和把字符串处理的原理和方法。
3. 熟悉C语言常见的字符串处理函数。
二、实验内容
1. 输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计此文本中单词的个数。
2. 设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置，否则输出0。
3. 设计可以在主串s中第i个位置插入一个子串t的程序。
4. 串的置换。将主串s中的t串，置换为v串。

实验四 数组
一、实验目的
1. 熟悉数组的存储结构及应用。
2. 熟悉稀疏矩阵的“三元组表”和“十字链表”存储结构，运用它们进行矩阵简单运算处理。
二、实验内容
1. 编写用“三元组表”存储稀疏矩阵，进行矩阵处理的程序。
（1）矩阵转置 （2）矩阵相加
2. 给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，…，n组成。魔阵的每行元素之和，每列元素之和以及主、副对角线元素之和均相等。即对于给定的奇整数n以及i=l，2，3，…，n，魔阵a满足条件。

要求输出结果的格式要具有n阶方阵的形式。
*3. 迷宫实验。迷宫实验是取自心理学的一个古典实验，在该实验中，把一只老鼠从一个无顶大盒子的口放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找出路以到达出口，对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步，老鼠经多次实验终于得到它学习走通迷宫的路线。
试设计一个算法，寻找一条从迷宫入口到出口的最短路径。要求程序输出：（1）一条通路的二元组( i,j)数据序列，(i,j)表示通路上某一点的坐标。（2）用一种标志(如数字8)在二维数组中标出该条通路，并在屏幕上输出二维数组。

实验五 树与二叉树
一、实验目的
1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序递归遍历。
2. 用树解决实际问题，如哈夫曼编码等。
3. 加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。
二、实验内容
1. 一棵具有n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。
1
7
8
6
9
5
4
2
3
2. 二叉树的建立和操作。
（1）对右图所示的二叉树建立二叉链表存储结构。
（2）采用递归算法中序遍历该二叉树。
（3）采用非递归算法中序遍历该二叉树。
（4）求该二叉树的高度 。
（5）求该二叉树的叶子个数。
（6）对该二叉树，建立相应的中序线索二叉树，并实现中序遍历。
3. 已知一棵二叉树的先序遍历序列和中序遍历序列，写出可以唯一确定一棵二叉树的算法。
*4. 哈夫曼树问题。
利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）。对于双工信道（即可以双向传输的信道），每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。
要求：（1）从终端读入字符集大小为n（即n个字符和n个权值），建立哈夫曼树，进行编码并且输出，并将它存于文件hfmtree中。
（2）利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。
请用下表中给出的字符集和频度的实际统计数据建立哈夫曼树：
字符
A
B
C
D
E
F
G
H
I
J
K
L
M
N
频度
64
13
22
32
103
21
15
47
57
1
5
32
20
57
字符
O
P
Q
R
S
T
U
V
W
X
Y
Z
空格

频度
63
15
1
48
51
80
23
8
18
1
16
1
168

并实现以下报文的译码和输出：“THIS PROGRAM IS MY FAVORITE”。

实验六 图
一、实验目的
1. 熟悉图的两种常用的存储结构（邻接矩阵、邻接表），以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。
2. 掌握图的经典算法。
二、实验内容
1. 设计一个程序，为下图的建立邻接矩阵，并进行深度优先遍历。
2. 设计一个程序，为题1的图建立邻接表，并进行广度优先遍历。620
412
355
298
1552
1554
615
298
340
石家庄
西安
郑州
太原
济南
北京
大同
379
283

3. 试写一个算法判别以邻接表方式存储的有向图G中是否存在由顶点vi到顶点vj的路径(i≠j)。
4. 假设以—个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价。试设计一个交通指南系统，指导前来咨询者以最低的票价从区域中的某一场所到达另一场所。
*5. 软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表：
课程编号
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1，C2
C4
汇编语言
C1
C5
语言的设计和分析
C3，C4
C6
计算机原理
C11
C7
编译原理
C3，C5
C8
操作系统
C3，C6
C9
高等数学
无
C10
线性代数
C9
C11
普通物理
C9
C12
数值分析
C1，C9，C10
假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。
实验七 查找
一、实验目的
1. 掌握几种典型的查找方法（折半查找、二叉排序树的查找、哈希查找）。
2. 了解各种查找算法的特点、使用范围和效率。
二、实验内容
1. 二叉排序树的建立、查找和删除。设有一组数据(33，88，22，55，90，11，66，99)，边输入边插入建立二叉排序树。然后查找78，删除90。
2.编写折半查找的算法的递归调用程序。
*3.设有一组关键字(19,14,23,1,68,20,84,27,56,11,10,79),建立一个哈希查找表。
（1）哈希函数采用: H(key)= key % P(其中P=11)，若发生冲突后，用链地址法解决冲突。
（2）哈希函数采用: H(key)= key % P(其中P=11)，若发生冲突后，用线性探测再散列方法解决冲突。

实验八 排序
一、实验目的
1. 熟悉几种典型的排序方法。
2. 了解各种排序算法的特点、使用范围和效率。
二、实验内容
1. 输入一组关键字序列分别实现下列排序:
（1）直接插入排序、直接选择排序和冒泡排序
（2）希尔排序
（3）堆排序
（4）快速排序
2. 统计成绩。给出n个学生的考试成绩表，每条信息由姓名与分数组成，试设计—个算法：
（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；
（2）要求学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。
（3）分别用冒泡排序和快速排序算法实现。
*3. 综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。

数据结构实验报告
实验名称：_______________________________ 评分：________
专业：___________ 班级：___________ 小组编号：_______
实验内容：

实验目的：

实验源程序：（源程序必须调试通过；需有必要的注释；源程序可打印，附在本实验报告之后。）
实验程序执行结果：（实验结果可以手写，也可以截屏打印出来。）

实验过程中出现的问题及解决方法：