数据结构与算法实验指导书

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

实验课程编号：07ZB101109实验室名称：多媒体技术实验室

系（院）：数计学院实验室地点：N5-408

理论课学时：60实验课学时：36

实验类别：尖业课适用专业：计算机科学与技术

是否独立设课：是

执笔人：审批人:

一、实验课程教学目的和要求

《数据结构与算法》是一门实践性很强的课程，光靠读书和做习

题是不能提高实践能力的。

《数据结构与算法》的实验与程序设计语言课程中的实验不同，

后者更多的强调语言方面的功能实现，而前者更接近实际，需要同学

们自己分析问题，设计模型和算法，再上机调试完成。

《数据结构与算法》的实验的目的主要有两个：

1）深化理解书本上的理论知识，将书本的知识变“活’’（为己掌

握，为已活用）；

2）理论和实践相结合，学会将相关的数据结构和算法应用于解

决实际问题，培养数据结构的应用能力和软件工程所需要的实践能

力。

《数据结构与算法》的实验类型

1）验证性实验一主要是验证教材中已有的数据结构和算法。

2）设计性实验一针对具体问题，应用某一个知识点，自己设计数据

结构和算法，培养对数据结构的简单运用能力。

3）综合性实验一针对具体问题，应用某几个知识点，自己设计数据

结构和算法，培养对数据结构的综合运用能力。

《数据结构与算法》的实验安排

项目实验题目学时说明

—顺序表的操作2验证

链表的操作2验证

循环单链表的插入和删除2设计

四栈与队的操作2验证

五栈与队的的应用2设计

六栈与队的的应用2设计

七对称矩阵的压缩存储2验证

八压缩矩阵的应用2设计

九二叉树的操作2验证

十二叉树的应用2设计

十一二叉树的应用2设计

十二图的操作2验证

十三图的应用2设计

十四图的应用2设计

十五查找操作2验证

十六查找应用2设计

十七排序操作2验证

十八排序应用2设计

《数据结构与算法》实验的一般步骤

1）需求分析：要对简单的问题描述进行详细的分析•，充分理解问

题，明确问题要求做什么，有什么数据，边界条件……。

2）概要设计：针对问题描述中涉及到数据定义抽象数据类型，设

计数据结构和算法模型。本部分不必考虑实现的细节。

3）详细设计：设计具体的存储结构（用C++实现抽象数据类型对

应的类）。此外，还要设计对象间的调用关系及输入输出。

4）上机调试（运行代码，修正语法及逻辑错误）

5）结果与总结

《数据结构与算法》的实验要求：

1）完成实验预习；

2）完成并上交实验报告；

3）完成电子设计文档

预习/实验报告的格式要求：

1）实验名称

2）实验目的

3）实验内容及要求

4）概要设计：ADT

5）详细设计：C++类或C函数

6）调试分析：

7）结果与总结

实验一：顺序表的操作

一、实验目的：

1）掌握线性表的顺序存储结构与算法实现；

2）掌握顺序表及其基本操作的实现。

二、实验内容及要求：

1）建立含有若干个元素的顺序表；

2）对已建立的顺序表实现插入、删除、查找、输出等基本操作。

实验二：链表的操作

一、实验目的：

1）掌握线性表的链接存储结构；

2）掌握链表及其基本操作的实现。

二、实验内容及要求：

I）用头插法（或尾插法）建立带头结点的单链表；

2）对已建立的单链表实现插入、删除、查找、输出等基本操作。

实验三：循环单链表的插入和删除

一、实验目的：

1）进一步掌握线性表的链接存储结构；

2）掌握循环单链表及其基本操作的实现。

二、实验内容及要求：

1）用头插法（或尾插法）建立带头结点的循环单链表；

2）在采用尾指针（rear）表示的循环单链表中，查找元素为x

的结点，如果有则删除该结点；如果没有则插入到循环单链表的尾部。

操作接口：TLinkListLDI（Tx）

实验四：栈与队的操作

一、实验目的：

1）掌握栈和队的顺序与链接存储结构；

2）掌握栈和队的操作特性；

3）掌握顺序栈和链队列的基本操作的实现方法。

二、实验内容及要求：

I）分别建立一个空的顺序栈和空的链队列；

2）对己建立的顺序栈和链队列实现插入、删除、取栈顶元素、

取队头元素及输出等基本操作。

实验五；栈与队的的应用（括号匹配问题）

一、实验目的:

1）掌握栈和队列的存储结构；

2）掌握栈和队列的操作特性；

3）掌握栈和队列基本操作的实现。

二、实验内容及要求：

括号匹配问题

在算述表达式中，可能出现嵌套的大、中、小括号，设计一个算

法，可以判断给定的表达式串中的括号是否是匹配的。

要求：首先，分别先定义一个栈和一个队；其次，将表达式串中

的各种括号字符依次入队（其它字符不予考虑）；最后利用栈来判断

队中的括号是否是匹配的。

无论是什么括号，最后出现的左括号，必须与其后最先出现的右

括号匹配，这符合栈的后进先出的特点，故我们可以用栈和进行匹配

性判断。

根据要求，串（括号）与队今栈

操作接口：boolmatch（char*s）

主要操作：

队，栈初始化

括号字符入队

出队为左括号：进栈

出队为右括号：弹栈

匹配？

实验六：栈与队的的应用（表达式求值）

一、问题描述：

1）对一个合法的中缀表达式求值；

2）假设表达式只包含+、一、义、+4个双目运算符，且运算符

本身不具有二义性。

二、基本要求：

1）正确解释表达式；

2）符合四则运算规则；

3）输出最后的计算结果。

三、设计思想：

对中缀表达式求值，通常使用“算苻优先算法”。根据四则运算

规则，在运算的每一步中，任意两个相继出现的运算符t和c之间的

优先关系至多是下面三种关系之一：

①t〈c：t的优先级低于c；

②t=C:t的优先级等于C;

③t>C：t的优先级高于C；

为实现算苻优先算法，可以使用两个工作栈：一个栈OPTR存放

运算符，另一个栈OPND存放操作数，中缀表达式用一个字符串数

组存储。

实验七：对称矩阵的压缩存储

一、实验目的:

1）掌握对称矩阵的压缩存储方法；

2）掌握对称矩阵的压缩存储的寻址方法。

二、实验内容：

1）建立一个nXn的对称矩阵；

2）将对称矩阵用一维存储

三、实现提示：

首先建立一个nXn的对称矩阵A并初始化矩阵的元素。对称矩

阵只须存储下三角部分，即将一个nXn的对称矩阵用一个大小为n

X（n+l）/2的一维数组SA来存储，则下三角中的元素au（i，j）在SA

中的下标k与i、j的关系为k=iX（i-D/2+j,

实验八：压缩矩阵的应用（稀疏矩阵的转置）

一、问题描述：

采用三元组顺序表存储稀疏矩阵并实现转置。

二、基本要求：

1）设计存储结构实现稀疏矩阵的压缩存储；

2）设计算法实现稀疏矩阵的转置；

3）分析算法的时间复杂度和空间复杂度。

三、设计思想：

将稀疏矩阵的非零元素对应的三元组（行号、列号、非零元素值）

所构成的集合，按行优先的顺序排列成一个线性表，对该线性表采用

顺序存储结构，同时该矩阵的行数、列数和非零元素的个数。

将稀疏矩阵A转置为矩阵B的基本思想是：在A的三元组顺序

表中依次找第。歹I」、第1列……最后一列的三元组，并将找到的每个

三元组的行、列交换后顺序存储到B的三元组顺序表中。

实验九：二叉树的操作

一、实验目的：

1）掌握二叉树的二叉链表存储结构；

2）掌握二叉树的建立方法；

3）掌握二叉树的遍历操作的算法实现。

二、实验内容及要求：

1）用随机数自动建立一个含有n个结点的二叉树，采用二叉链

表存储；

2）进行各种遍历（先序，中序，后序，层序）该二叉树；

3）遍历算法分别用递归和非递归算法。

实验十：二叉树的应用

求二叉树中叶子结点的个数

一、问题描述：

已知一棵二叉树，求该二叉树中的叶子结点的个数。

一、基本要求：

1）采用二叉链表存储结构；

2）设计递归算法求二叉树中的叶子结点的个数。

三、设计思想：

求二叉树中的叶子结点的个数，即求二叉树的所有结点中左、右

子树均为空的结点之和。因此可以将此问题转化为遍历问题，在遍历

中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。

实验十一：二叉树的应用（哈夫曼编码）

一、问题描述：

设某编码系统共有n个字符，使用频率分别为MW3…,wj。

设计一个不等长的编码方案，使用该编码系统的空间效率最好。

二、基本要求：

1）设计数据结构；

2）设计编码算法；

3）分析算法的时间复杂度和空间复杂度。

三、设计思想：

利用Huffman编码树求得最住的编码方案＜

根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个

结构型的一维数组Huffman,保存哈夫曼树中各结点的信息，每个结

点包括权值、左孩子、右孩子和双亲。由于哈夫曼树中共有2n—l个

结点。并且进行n—l次合并操作，所以该数组的长度为2n—l。

weigthIchildrchiidparent

在哈夫曼树中，设左分支为0,右分支为1,从根结点出发，遍

历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼树编码。

实验十二：图的操作

一、实验目的：

1）掌握图的存储结构；

2）掌握构造邻接矩阵的方法；

3）掌握图的遍历算法的算法实现。

二、实验内容及要求：

按给定的任一连通无向图构造邻接矩阵，再进行深度优先遍历

和广度优先遍历。

实验十三：图的应用

求无向连通图的生成树

一、问题描述：

求无向连通图的一棵生成树。

二、基本要求：

I）采用邻接矩防存储；

2）求深度优先生成树；

3）输出该生成树的每一条边。

三、设计思想：

在一个连通无向图G=（V,E）中，如果从任一个顶点开始进行深度

优先遍历，必定将边集E分成两个集合T和B,其中T是遍历过程中

经历的边的集合，B是剩余的边的集合。显然，边集T和图G所有

顶点一起构成连通图G的一棵生成树。因此，修改深度优先遍历算

法，输出遍历所经过的边。

实验十四：图的应用

求有向图的路径

一、问题描述：

对于有向图G=（V,E）,任意V,,%（iWj）,判断从顶点Vi到顶点vj

是否存在路径。

二、基本要求：

1）有向图采用邻接矩阵存储；

2）设计算法完成问题求解；

3）设计存储结构存储从顶点H到顶点门的路径。

三、设计思想：

可以利用深度优先遍历，从顶点w出发法行深度优先遍历，如

果在遍历过程中，访问到顶点则从顶点H到顶点门存在路径。

因此，修改深度优先遍历算法，判断在遍历中是否访问顶点Vj。

实验十五：查找操作

一、实验目的：

1）掌握顺序查找技术和拆半查找技术；

2）掌握查找的算法实现；

二、实验内容及要求：

1、产生n个随机整数用顺序查找的方法进行查