数据结构实验指导书

数据结构实验指导书

前 言

数据结构是计算机程序设计的重要理论技术基础，不仅是计算机学科的核心课程，而且己成为其它理工专业的热门选修课程。数据结构课程主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现，其教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，但由于这门课程相对抽象且内容复杂，因此，在数据结构的整个教学过程中，辅助课堂教学的实验非常有助于帮助学生学好这门课程，培养学生思考和解决问题的能力，锻炼学生的动手能力。为帮助老师和学生开展实验，我们编写了这本实验指导书，希望能对我校的《数据结构》教学工作有所帮助。

数据结构实验指导书

目 录

实验1 线性表及其应用 ......................................................................................................... 2 实验2 栈和队列 ....................................................................................................................... 5 实验3 串及其应用 ................................................................................................................... 7 实验5 二叉树及其应用 ....................................................................................................... 11 实验6 图的应用 ..................................................................................................................... 13 实验7 查找、排序 ................................................................................................................. 15

数据结构实验指导书

实验1 线性表及其应用

一．实验目的

帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。

二．问题描述

1． 构造一个空的线性表L；

2． 在线性表L的第i个元素之前插入新的元素e； 3． 在线性表L中删除第i个元素，并用e返回其值。

三．实验要求

1．分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。

2．在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1．用学生选择的语言，设计出线性表的顺序和链表存储结构； 2. 设计出这两种存储结构下的线性表的插入、删除算法； 3. 用所选择的语言实现算法；

4. 测试程序,并对不同存储结构下的算法分析。

六．测试数据和分析

1．插入操作：

输入数据：L = ( ) ListInsert (L, 1, 'k'), 正确结果：L = (k)

输入数据：L = (EHIKMOP) ListInsert (L, 9, 't'), 正确结果：return ERROR; L = (EHIKMOP)

输入数据：L = (ABCEHKNPQTU) ListInsert(L, 4, 'u'), 正确结果： L = (ABCuEHKNPQTU) 2．删除操作：

数据结构实验指导书

输入数据：L = () ListDelete (L, 1, e) 正确结果：ERROR, L = ()

输入数据：L = (DEFILMNORU) ListDelete_Sq(L, 5, e) 正确结果： L = (DEFIMNORU), e='L' 输入数据：L = (CD) ListDelete_Sq(L, 1, e) 正确结果： L = (D), e = 'C'

3．如线性表有n个结点，对两种存储结构下插入和删除的时间复杂度进行分析。

七．实验报告要求

实验报告应包括以下几个部分： 1． 题描述；

2． 计两种存储结构与核心算法描述；

3． 测试结果的分析与讨论，在测试过程中遇到的主要问题及采取的解决措施； 4． 设计与实现过程中的体会，进一步的改进设想； 5． 实现算法的程序清单，应有足够的注释。

八．思考题

1．如何实现链表的逆置算法？

数据结构实验指导书

实验2 栈和队列

一．实验目的

深入了解栈和队列的特性，学会在实际问题下灵活运用它们。

二．问题描述

表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。

三．实验要求

1．算法优先级别如下：

'+', '-', '*', '/', '(', ')', '#' '+' '>', '>', '<', '<', '<', '>', '>', '-' '>', '>', '<', '<', '<', '>', '>', '*' '>', '>', '>', '>', '<', '>', '>', '/' '>', '>', '>', '>', '<', '>', '>', '(' '<', '<', '<', '<', '<', '=', ' ', ')' '>', '>', '>', '>', ' ', '>', '>', '#' '<', '<', '<', '<', '<', ' ', '='

2．以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1． 根据给出的算符优先级，设置运算符栈和运算数栈；

2． 在读入表达式的同时，完成运算符和运算数的识别处理，并将运算数的字符序列形式转换成整数形式，并进行相应的运算；

3． 调试程序，检查输出结果； 4． 实验小结。

六．测试数据

1．输入数据：1+（20+4）/（4-1） 正确结果：9

2．输入数据：2*9-6-（20+4）/（4-1）

数据结构实验指导书

正确结果：4

七．实验报告要求

实验报告应包括以下几个部分： 1． 问题描述； 2． 算法的设计描述； 3． 测试结果的分析与讨论；

4． 设计与实现过程中的体会，进一步的改进设想； 5． 实现算法的程序清单，应有足够的注释。

八．思考题

1、试着扩充运算符集，如增加乘方、单目加等； 2．如何增强计数器的功能和仿真界面；

3．如何实现前缀算术表达式、后缀表达式的求解？

数据结构实验指导书

实验3 串及其应用

一．实验目的

掌握串类型的实现方法和文本模式匹配方法，熟悉一般文字处理软件的设计方法。

二．问题描述

全屏幕文本编辑器通过终端对文本文件进行创建、插入、删除、修改、存储等操作。用户可完成对文本的插入、删除、修改等功能。

三．实验要求

1．对光标实现如下操作：上、下、左、右移动一个字符位置；向前、后翻页；光标移至文件首、尾；光标移至本行首、尾。

2．实现基本编辑命令：

I----在当前光标前插入内容，按ESC结束 F----在当前光标后插入内容，按ESC结束 D----删除光标所在行

ND---删除光标位置开始的n行 N-----删除光标上的字符 W----将修改后的文本保存下来 Q----退出编辑状态。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1． 在内存开辟可容纳80行大小的编辑工作区和buffer 的修改缓冲区；

2．要求用户输入编辑文件名，对读入的文件建立相应的页表和行表，在文本编辑程序中设立页指针、行指针、字符指针，分别指示当前操作的页、行、字符

3．执行插入、删除、修改操作时，将本次操作内容放到缓冲区； 4．操作确定后，将修改后的文本存到文件中。

六．测试数据

自行设定。

七．实验报告要求

实验报告应包括以下几个部分：

数据结构实验指导书

1．问题描述； 2．算法的设计描述； 3．测试结果的分析与讨论；

4．设计与实现过程中的体会，进一步的改进设想； 5．实验总结。

八．思考题

1．对命令格式非法等错误做严格检查和适当处理。 2．扩充编辑操作，如对某行进行串替换？

数据结构实验指导书

实验4 数 组

一．实验目的

深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。

二．问题描述

稀疏矩阵是指那些多数元素为零的矩阵。利用‘稀疏’特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。

三．实验要求

1．要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵；

2． 计矩阵的逆置算法，实现矩阵的逆置； 3． 实现两个稀疏矩阵的相加、相减和相乘等运算； 4． 要求运算结果的矩阵则以通常的阵列形式出现。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1．首先应输入矩阵的行数和列数、并判别给出的两个矩阵的行、列数对于所要求的运算是否相匹配；

2．以三元组的形式输入矩阵；

3．调用矩阵的逆置子函数、相加函数和相乘函数； 4．分析输出结果，并进行总结。

六．测试数据

输入数据：

2 1 0 0 0 0 0 0 3

+ 0 0 0 0 0 0 0 0 2

=

2 1 0 0 0 0 0 0 5

2 1 0 0 0 0 0 0 3

-1 2 0 0 1 0 0 0 0 3

数据结构实验指导书

2 1 0 0 0 3

╳ 0 0 0 0 0 2

= 0 0 0 6 七．实验报告要求

实验报告应包括以下几个部分： 1． 问题描述和算法设计； 2． 程序运行流程； 3． 程序的测试结果和问题； 4． 实验总结。

八．思考题

1．如何提高矩阵转置算法效率？

2．如果用十字链表方式表示稀疏矩阵的话，如何来实现矩阵的相加操作呢？

数据结构实验指导书

实验5 二叉树及其应用

一．实验目的

树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二．问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。

如算术表达式：a+b*(c-d)-e/f

b

C

-

d

a

*

e

-

+

/

f

三．实验要求

1．如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算

1）统计叶子结点的个数； 2）求二叉树的深度。

2．十进制的四则运算的计算器可以接收用户来自键盘的输入； 3．由输入的表达式字符串动态生成算术表达式所对应的二叉树； 4．自动完成求值运算和输出结果。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1．根据二叉树的各种存储结构建立二叉树； 2．设计求叶子结点个数算法和树的深度算法；

3．根据表达式建立相应的二叉树，生成表达式树的模块；

数据结构实验指导书

4．根据表达式树，求出表达式值，生成求值模块； 5．程序运行效果，测试数据分析算法。

六．测试数据

1．输入数据：2．2*（3．1+1．20）-7．5/3 正确结果：6．96

2．输入数据：(1+2)*3+(5+6*7); 正确输出：56

七．实验报告要求

实验报告应包括以下几个部分： 1． 设计算术表达式树的存储结构；

2． 给出二叉树中叶子结点个数算法和树的深度算法描述； 3． 给出生成表达式树算法和求解算法描述； 4． 相应的程序要给出足够的注释部分； 5． 给出程序的测试结果； 6． 实验总结。

八．思考题

1．分析利用完全二叉树的性质和二叉链表存储有什么不同？分析其优缺点。 2．增加输入表达式进行语法判错的功能。

数据结构实验指导书

实验6 图的应用

一．实验目的

图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。

二．问题描述

给出一张某公园的导游图，游客通过终端询问可知：

a) 从某一景点到另一个景点的最短路径。 b) 游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。

三．实验要求

1．将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。

2．为游客提供图中任意景点相关信息的查询；

（1） 为游客提供任意两个景点之间的一条最短的简单路径； （2） 为游客选择最佳游览路径。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境 五．实验步骤

1．设计公园平面图，图中顶点表示公园的各个景点，存放名称、代号、简介等信息；边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构；

2．设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；

3．设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；

4．选择适当语言实现算法； 5．调试程序。

六．测试数据

可根据实际情况指定。

七．实验报告要求

实验报告应包括以下几个部分： 1．问题描述； 2．图的最短路径算法；

数据结构实验指导书

3．图的深度优先搜索算法； 4．公园平面图；

5．程序的测试结果和问题； 6．实验总结。

八．思考题

1．扩充景点数和道路；

2．试着提供图的多个景点的最佳访问路线查询。

数据结构实验指导书

实验7 查找、排序

一．实验目的

深入了解各种内部排序方法及效率分析。

二．问题描述

各种内部排序算法的时间复杂度分析，试通过随机数据比较算法的关键字比较次数和关键字移动次数。

三．实验要求

1．对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序这六种常用排序算法进行比较；

2．待排序表的表长不超过100；其中数据用伪随机数产生程序产生； 3．至少要用6组不同的输入数据做比较； 4．要对实验结果做简单分析。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1．根据问题描述写出基本算法； 2．设计六种排序算法并用适当语言实现；

3．输入几组随机数据，并对其关键字比较次数和关键字移动次数的比较； 4．对结果进行分析； 5．进行总结。

六．测试数据

数据有随机数产生器产生。

七．实验报告要求

实验报告应包括以下几个部分： 1．问题描述； 2．六种排序算法描述； 3．实现算法的程序； 4．调试程序；

5．比较各算法中的关键字比较次数和关键字移动次数。

数据结构实验指导书

八．思考题

1．试着将数据按散列法存储，并设计好解决冲突的方法，在此基础上实现增、删查询等操作。

2．试构造存放C语言中32个关键字的查找表，并希望达到的平均查找长度不超过2。

数据结构实验指导书