数据结构实验指导书

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

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

实验1 顺序表

一、实验目的

（1）掌握顺序表的逻辑结构、存储结构及描述方式。 （2）掌握顺序表的定位、插入、删除等操作。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）编写一个函数print_all_data，该函数的作用是逐个输出顺序表中所有数据元素的值。编写主函数，从键盘输入顺序表，调用函数print_all_data，测试结果。

（2）编写顺序表定位操作函数locata，该函数的作用是在顺序表中查找是否存在数据元素的值与变量x的值相等。如果存在满足条件的数据元素，则返回顺序表中和x值相等的第1个数据元素在表中的下标；如果不存在，则返回－1。编写主函数，从键盘输入顺序表，以及变量x的值，调用函数locate，测试结果。

（3）编写一个函数insert，该函数的作用是在递增有序的顺序表中插入一个新结点x，要求保持顺序表的有序性，输出插入前后顺序表状态。编写主函数，从键盘输入顺序表以及变量x的值，调用函数insert，测试结果。

（4）编写一个函数delete，该函数的作用是删除顺序表中所有等于X的数据元素。若顺序表中没有满足条件的数据元素，则输出合适的信息。若有满足条件的数据元素，则输出删除前后顺序表状态。编写主函数，从键盘输入顺序表以及变量x的值，调用函数

153

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

delete，测试结果。

五、讨论、思考题

1、如何在排列有序的顺序表中插入新元素，而保证顺序表的有序性？ 2、如何在排列有序的顺序表中删除某元素，而保证顺序表的有序性？

实验2 单链表

一、实验目的

（1）掌握单链表的逻辑结构、存储结构及描述方式。 （2）掌握单链表的定位、插入、删除等操作。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。 3．撰写各实验报告。 实验内容：

（1）编写函数print_all_data，该函数的作用是逐个输出单链表中所有数据元素的值。编写主函数，从键盘输入单链表的内容，调用函数print_all_data，测试结果。 （2）编写函数insert，在递增有序的单链表中插入一个新结点x，保持单链表的有序性。编写主函数，从键盘输入单链表以及变量x的值，调用函数insert，测试结果。

五、讨论、思考题

1、如何在排列有序的单链表表中插入新元素，而保证顺序表的有序性？ 2、如何在排列有序的单链表中删除某元素，而保证顺序表的有序性？

3、如何计算带有头结点的单链表的长度，将计算结果记录在头结点的数据域中？

154

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

实验3 堆栈和队列

一、实验目的

（1）掌握应用栈解决问题的方法。 （2）掌握利用栈进行表达式求和的算法。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1． 根据题目，编写程序。 2． 上机调试通过。

3． 按照实验报告格式，撰写各实验报告。 实验内容：

（1）判断一个算术表达式中开括号和闭括号是否配对。

提示：对表达式进行扫描，凡是遇到‘（’就进栈，遇到‘）’就退掉栈顶的‘（’，表达式被扫描完毕时，栈应为空。此时，开闭括号为配对，否则不配对。

（2）假设算术表达式仅由加减乘除运算符组成，编写一个函数对用后缀表达式表示的算术表达式求值。要求使用顺序堆栈。

五、讨论、思考题

1、如何判断堆栈（顺序栈、链栈）栈满和栈空？

2、如何判断队列（顺序队列、循环队列、链队列）队满和队空？ 3、如何在堆栈（顺序栈、链栈）中压入和弹出元素？

4、如何在队列（顺序队列、循环队列、链队列）中插入和删除元素？

155

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

实验4 串、递归算法

一、实验目的

（1）掌握串的应用。

（2）掌握递归算法的设计方法。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）设字符串采用静态数组存储结构。编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。 （2）测试“汉诺塔”问题。 （3）Ackerman函数的定义如下：

n+1 当m=0时 AKM(m,n)= AKM(m-1,1) 当m<>0,n=0时 AKM(m-1,AKM(m,n-1)) 当m<>0,n<>0时 请写出递归算法。

五、讨论、思考题

1、串是如何存储的？ 2、递归算法是如何执行的？

156

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

实验5 二叉树

一、实验目的

（1）掌握二叉树的生成，以及前、中、后序遍历算法。 （2）掌握应用二叉树递归遍历思想解决问题的方法。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2）求二叉树中叶结点的个数。

（3）假设通讯电文由8个字母组成，字母在电文中出现的频率分别为：7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

五、讨论、思考题

1、二叉树是如何存储的？

2、二叉树有哪些遍历算法？这些遍历算法有何特点？ 3、找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； （2）前序序列和后序序列相同； （3）后序序列和中序序列相同；

4、若以二叉链表作存储结构，如何求二叉树高度？提示：用递归的方法。

157

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

实验6 图

一、实验目的

（1）熟练掌握图的基本概念、构造及其存储结构。

（2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

1．构造一个无向图，要求用邻接矩阵表示存储结构。

2．对上面构造的无向图，进行深度优先遍历和广度优先遍历，分别输出遍历序列。 3．构造一个连通网络，分别用PRIM算法和KRUSKAL算法构造该网络的最小生成树。

五、讨论、思考题

1、图是如何存储的？

2、如何从一个无向图的邻接矩阵（或邻接表）中，判断图中有多少条边？任意两个顶点i和j是否有边相连？任意一个顶点的度是多少？ 3、图有哪些遍历算法，这些算法之间有何区别？

158

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

实验7 排序

一、实验目的

（1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。 （3）区分以上不同排序的优、缺点。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。

五、讨论、思考题

1、排序方法有哪些？各有哪些特点？

2、什么是排序方法的稳定性？哪些排序方法是稳定的，哪些又是不稳定的？

159

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

实验8 查找

一、实验目的

（1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。 （2）掌握哈希表设计。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）在一个递增有序的线性表中利用二分查找法查找数据元素X。

（2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。

五、讨论、思考题

1、二分查找的前提是什么？ 2、如何合理设计哈希函数？

160

本文来源：https://www.bwwdw.com/article/etp8.html