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

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

实验课程编号：0731zk11 实验室名称：多媒体技术实验室 系（院）：数计学院 实验室地点：N5-406 实验课学时：28

实验类别：专业课 适用专业：软件工程 是否独立设课：否

执笔人：李文新 审批人： 一、实验课程教学目的和要求

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

《数据结构与算法》的实验与程序设计语言课程中的实验不同，后者更多的强调语言方面的功能实现，而前者更接近实际，需要同学们自己分析问题，设计模型和算法，再上机调试完成。 《数据结构与算法》的实验的目的主要有两个：

1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）；

2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。

h

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

1）验证性实验—主要是验证教材中已有的数据结构和算法。 2）设计性实验—针对具体问题，应用某一个知识点，自己设计数据结构和算法，培养对数据结构的简单运用能力。

3）综合性实验—针对具体问题，应用某几个知识点，自己设计数据结构和算法，培养对数据结构的综合运用能力。 《数据结构与算法》的实验安排 项目 一 二 实验题目 顺序表的保序插入操作 单链表的保序插入操作 学时 2 2 2 2 2 2 2 2 2 2 2 2 2 说明 设计 设计 设计 验证 设计 验证 验证 设计 设计 验证 设计 设计 验证 三 循环单链表的插入和删除 四 五 六 七 八 九 十 十一 十二 十三 栈与队的操作 栈与队的的应用 对称矩阵的压缩存储 二叉树的操作 二叉树的应用 二叉树的应用 图的操作 图的应用 图的应用 查找操作

h

十四 十五 十六

查找应用 排序操作 排序应用 2 2 2 设计 验证 设计 《数据结构与算法》实验的一般步骤

1）需求分析：要对简单的问题描述进行详细的分析，充分理解问题，明确问题要求做什么，有什么数据，边界条件……。

2）概要设计：针对问题描述中涉及到数据定义抽象数据类型，设计数据结构和算法模型。本部分不必考虑实现的细节。

3）详细设计：设计具体的存储结构（用C++实现抽象数据类型对应的类）。此外，还要设计对象间的调用关系及输入输出。 4）上机调试（运行代码，修正语法及逻辑错误） 5）结果与总结

《数据结构与算法》的实验要求： 1）完成实验预习； 2）完成并上交实验报告； 3）完成电子设计文档 预习/实验报告的格式要求： 1）实验名称 2）实验目的 3）实验内容及要求 4）概要设计：ADT

h

5）详细设计：C++类或C函数 6）调试分析： 7）结果与总结

实验一: 顺序表的保序插入操作

一、实验目的：

1）掌握线性表的顺序存储结构与算法实现； 3）掌握顺序表的逻辑插入方法。 二、实验内容及要求：

设计：主函数、构建n个整数的顺序表函数、保序插入函数、输出函数。

提示：主函数中调用构建n个整数的顺序表函数并调用输出函数；

调用保序插入函数实现插入操作并调用输出函数输出。

实验二: 单链表的保序插入操作

一、实验目的：

1）掌握线性表的链接存储结构与算法实现； 2）掌握线性表的逻辑插入操作方法。 二、实验内容及要求：

设计：主函数、构建一个带头结点的单链表A（值为整数并有序）的函数、保序插入函数、输出函数。

h

提示：主函数中调用构建单链表A函数并调用输出函数；

调用保序插入函数实现插入操作并调用输出函数输出。 结点结构： struct Node { int data; Node *next;

};

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

一、实验目的：

1）进一步掌握线性表的链接存储结构； 2）掌握循环单链表及其基本操作的实现。 二、实验内容及要求：

1）用头插法（或尾插法）建立带头结点的循环单链表； 2）在采用尾指针（rear）表示的循环单链表中，查找元素为x的结点，如果有则删除该结点；如果没有则插入到循环单链表的尾部。

操作接口 ：T LinkListLDI(T x)

实验四: 栈与队的操作

一、实验目的：

1）掌握栈和队的顺序与链接存储结构； 2）掌握栈和队的操作特性；

h

3) 掌握顺序栈和链队列的基本操作的实现方法。 二、实验内容及要求：

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

2）对已建立的顺序栈和链队列实现插入、删除、取栈顶元素、取队头元素及输出等基本操作。

3）利用栈的基本操作完成十进制数n向P进制数（P在2-9之间）的转换。

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

一、实验目的：

1）掌握栈和队列的存储结构； 2）掌握栈和队列的操作特性； 3）掌握栈和队列基本操作的实现。 二、实验内容及要求： 括号匹配问题

在算述表达式中，可能出现嵌套的大、中、小括号，设计一个算法，可以判断给定的表达式串中的括号是否是匹配的。

要求：首先，分别先定义一个栈和一个队；其次，将表达式串中的各种括号字符依次入队（其它字符不予考虑）；最后利用栈来判断队中的括号是否是匹配的。

无论是什么括号，最后出现的左括号，必须与其后最先出现的右括号匹配，这符合栈的后进先出的特点，故我们可以用栈和进行匹配

h

性判断

h

。

根据要求，串(括号) 队 栈 操作接口：bool match(char *s) 主要操作：

队，栈初始化

括号字符入队 出队为左括号：进栈 出队为右括号：弹栈 匹配？

注：利用实验五栈和队列基本操作

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

一、实验目的：

1）掌握对称矩阵的压缩存储方法； 2）掌握对称矩阵的压缩存储的寻址方法。 二、实验内容：

1) 建立一个n×n的对称矩阵； 2) 将对称矩阵用一维数组存储 三、实现提示：

首先建立一个n×n的对称矩阵A并初始化矩阵的元素。对称矩阵只须存储下三角部分，即将一个n×n的对称矩阵用一个大小为n×(n+1)/2的一维数组SA来存储，则对称矩阵中的元素aij(i≥j)在

h

SA中的下标k与i、j的关系为k=i

h

×(i+1)/2+j，元素aij(i实验七：二叉树的操作

一、实验目的：

1）掌握二叉树的二叉链表存储结构； 2）掌握二叉树的建立方法；

3）掌握二叉树的遍历操作的算法实现。 二、实验内容及要求：

1) 利用扩展二叉树的先序遍历序列

建立一个含有n个结点的二叉树，采用二叉链表存储； 2) 进行各种遍历（先序，中序，后序，层序）该二叉树； 3) 遍历算法分别用递归和非递归算法。

实验八：二叉树的应用 求二叉树叶子结点个数和深度

一、问题描述：

已知一棵二叉树，求该二叉树中的叶子结点的个数和深度。 二、基本要求：

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

2) 设计算法求二叉树中的叶子结点的个数和二叉树t的深度。

h

三、设计思想：

在实验七（二叉树的操作）的基础上设计算法求二叉树中的叶子结点个数和二叉树t的深度。

分别用递归和非递归算法。

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

一、问题描述：

设某编码系统共有n个字符，使用频率分别为（w1,w2,…,wn）。设计一个不等长的编码方案，使用该编码系统的空间效率最好。 二、基本要求：

1) 设计数据结构； 2) 设计编码算法；

3）分析算法的时间复杂度和空间复杂度。 三、设计思想：

利用Huffman编码树求得最佳的编码方案。

根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组Huffman，保存哈夫曼树中各结点的信息，每个结点包括权值、左孩子、右孩子和双亲。由于哈夫曼树中共有2n－1个结点。并且进行n－1次合并操作，所以该数组的长度为2n－1。

weigth lchild rchild parent 在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼树编码。

h

实验十：图的操作

一、实验目的：

1）掌握图的存储结构； 2）掌握构造邻接矩阵的方法； 3）掌握图的遍历算法的算法实现。 二、实验内容及要求：

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

实验十一：图的应用 求无向连通图的生成树

一、问题描述：

求无向连通图的一棵生成树。 二、基本要求：

1）采用邻接矩阵存储； 2) 求深度优先生成树； 3) 输出该生成树的每一条边。 三、设计思想：

在一个连通无向图G=(V,E)中，如果从任一个顶点开始进行深度优先遍历，必定将边集E分成两个集合T和B,其中T是遍历过程中经历的

h

边的集合，B是剩余的边的集合。显然，边集T和图G所有顶点一起构成连通图G的一棵生成树。因此，修改深度优先遍历算法，输出遍历所经过的边。

实验十二：图的应用

求有向图的路径

一、问题描述：

对于有向图G=(V,E),任意vi，vj (i≠j),判断从顶点vi到顶点vj是否存在路径。 二、基本要求：

1）有向图采用邻接矩阵存储； 2) 设计算法完成问题求解；

3) 设计存储结构存储从顶点vi到顶点vj的路径。 三、设计思想：

可以利用深度优先遍历，从顶点vi出发进行深度优先遍历，如果在遍历过程中，访问到顶点vj，则从顶点vi到顶点vj存在路径。 因此，修改深度优先遍历算法，判断在遍历中是否访问顶点vj。

实验十三：查找操作

一、实验目的：

h

1）掌握顺序查找技术和拆半查找技术； 2）掌握查找的算法实现； 二、实验内容及要求：

1、产生n个随机整数用顺序查找的方法进行查找操作，并统计查找的次数。

2、给定n个有序整数用折半查找的方法进行查找操作，并统计查找的次数。

要求分别用初始化函数，顺序查找函数，折半查找函数及输出函数来完成。

实验十四：查找应用 散列表的建立和查找

一、实验目的：

1）掌握散列查找的基本思想； 2）掌握闭散列表的构造方法； 3) 掌握线性探测处理冲突的方法； 4) 掌握散列技术的查找性能。 二、实验内容及要求：

1) 对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表；

2) 设计查找算法，验证查找性能。

实验十五：排序操作

h

一、实验目的：

1）深刻理解各种排序算法的设计思想； 2）掌握各种排序算法的执行过程； 3）掌握各种排序算法的设计实现。 二、实验内容及要求：

产生n个随机整数分别采用直接插入排序、希尔排序和冒泡排序的方法进行排序。

要求分别采用各排序函数和输出函数来完成。

实验十六：排序应用

一、问题描述：

一个班有n个学生，每个学生有学号（no）、姓名（name）、年龄（age）、成绩（score）。定义数据结构来描述学生信息。并按成绩进行降序排列。 二、基本要求：

1) 可任用一种排序算法，按成绩进行降序排列。 2) 输出已排序的学生数据；要求输出整齐。

欢迎您的下载，资料仅供参考！