《数据结构》
实验指导书
成都信息工程大学
计算机学院
目 录
《数据结构》 .............................................................................................................................................................................. 0 实验一 顺序表实验 .................................................................................................................................................................... 1 实验二 单链表实验 .................................................................................................................................................................... 3 实验三 栈的实验 ........................................................................................................................................................................ 5 实验四 二叉树实验 .................................................................................................................................................................... 7 实验五 图的实验 ........................................................................................................................................................................ 9 实验六 查找与排序实验 .......................................................................................................................................................... 11
实验一 顺序表实验
一、实验环境
PC 1台，Turbo C/C++或Borland C/C++或Visual C++软件。
二、实验目的
1. 掌握线性表顺序存储结构的实现
2. 掌握顺序表基本运算的实现
3. 理解顺序表的随机存取特性
三、实验内容
1. 编程实现顺序表的创建InitList_Sq、打印PrintList_Sq、定位ListInsert_Sq、删除ListDelete_Sq等基本运算。
2. 用顺序表来表示集合A和B，求：A = A B。
四、实验步骤
1. 建立\"SqList.h\"文件，用于存放以下2-5内容
2. 定义线性表的顺序存储类型（顺序表）
第 1 页 共 14 页
LocateElem_Sq、插入3. 实现顺序表的基本运算
4. 其他辅助函数
5. 求A = A ∪ B
6. 编写主函数测试各功能（放入\"SqList_Test.cpp\"文件）
第 2 页 共 14 页
实验二 单链表实验
一、实验环境
PC 1台，Turbo C/C++或Borland C/C++或Visual C++软件。
二、实验目的
1. 掌握线性表链式存储结构的特点
2. 掌握单链表存储结构及基本运算的实现
3. 掌握顺序表和链表的适用场合
三、实验内容
1. 编程实现(带头结点的)单链表的创建InitList_Link、打印PrintList_Link、插入ListInsert_Link、删除ListDelete_Link、定位LocateElem_Link等基本运算。
2. 编写算法将两个带头结点的有序单链表La、Lb合并成一个带头结点的有序单链表Lc。
四、实验步骤
1. 建立\"LinkList.h\"文件，用于存放以下2-5内容
2. 定义带头结点的单链表类型
第 3 页 共 14 页
3. 实现单链表的基本运算
4. 其他辅助函数
5. 实现保序归并（Lc = La + Lb）
6. 编写主函数测试各功能（放入\"LinkList_Test.cpp\"文件）
第 4 页 共 14 页
实验三 栈的实验
一、实验环境
PC 1台，Turbo C/C++或Borland C/C++或Visual C++软件。
二、实验目的
1. 掌握栈的特点及其存储结构的实现
2. 掌握栈的基本运算的实现
3. 运用栈解决实际问题
三、实验内容
1. 编程实现栈及其基本操作。
2. 编程括号匹配检验算法。
四、实验步骤
1. 建立\"Stack.h\"文件，用于存放以下2-5内容
2. 定义栈类型（顺序栈或链栈选其一）
第 5 页 共 14 页
3. 实现栈的基本运算
4. 其他辅助函数
5. 实现括号匹配检验算法
6. 编写主函数测试各功能（放入\" Stack_Test.cpp\"文件）
第 6 页 共 14 页
实验四 二叉树实验
一、实验环境
PC 1台，Turbo C/C++或Borland C/C++或Visual C++软件。
二、实验目的
1. 掌握二叉树的链式存储结构：二叉链表
2. 掌握二叉树最重要的运算：遍历
三、实验内容
1. 建立链式结构的二叉树。
2. 实现先序、中序和后序遍历的递归算法。
3. 实现中序遍历非递归算法。
四、实验步骤
1. 建立\"BiTree.h\"文件，用于存放以下2-5内容
2. 定义二叉链表类型
第 7 页 共 14 页
3. 实现二叉链表的建树运算和释放运算
4. 实现先中后三种遍历的递归算法
5. 实现中序遍历非递归算法（若用到栈，可利用实验三的结果或重新设计）
6. 编写主函数测试各功能（放入\" BiTree_Test.cpp\"文件）
第 8 页 共 14 页
实验五 图的实验
一、实验环境
PC 1台，Turbo C/C++或Borland C/C++或Visual C++软件。
二、实验目的
1. 掌握图的两种常用存储方式：邻接矩阵和邻接表
2. 掌握图的DFS和BFS运算和其他基本运算
3. 掌握拓扑排序算法
三、实验内容
1. 实现图的邻接矩阵类型和邻接表类型及其基本运算。
2. 分别实现两种存储方式下的DFS和BFS算法。
3. 分别实现两种存储方式下的拓扑排序算法。
四、实验步骤
1. 建立\"MGraph.h\"文件，用于存放以下2-5内容
第 9 页 共 14 页
2. 定义邻接矩阵类型
3. 实现邻接矩阵类型的基本运算（包括建图运算）
4. 实现邻接矩阵类型的DFS和BFS算法
5. 实现邻接矩阵类型的拓扑排序算法（若用到栈，可利用实验三的结果）
6. 编写主函数测试4-5功能（放入\" MGraph_Test.cpp\"文件）
7. 建立\"AGraph.h\"文件，用于存放以下8-11内容
8. 定义邻接表类型
9. 实现邻接表类型的基本运算（包括建图运算和销毁运算）
10.实现邻接表类型的DFS和BFS算法
11.实现邻接表类型的拓扑排序算法（若用到栈，可利用实验三的结果）
12.编写主函数测试10-11功能（放入\" AGraph_Test.cpp\"文件）
第 10 页 共 14 页
实验六 查找与排序实验
一、实验环境
PC 1台，Turbo C/C++或Borland C/C++或Visual C++软件。
二、实验目的
1. 掌握二分查找的含义及实现
2. 掌握排序算法的实现
3. 掌握算法的效率分析
三、实验内容
1. 实现二分查找算法。
2. 实现直接插入排序算法和快速排序算法。
3. 分析各算法的时空效率。
四、实验步骤
1. 建立\"Sort.h\"文件，用于存放以下2-6内容
第 11 页 共 14 页
2. 定义顺序表类型（用静态或动态分配方式均可）
3. 实现建表运算（若表类型采用动态，则还需实现销毁运算）
4. 实现直接插入排序算法
5. 实现快速排序算法
6. 实现二分查找算法
7. 编写主函数测试各功能（放入\" Sort_Test.cpp\"文件）
8. 分析4-6算法的时空效率
第 12 页 共 14 页
因篇幅问题不能全部显示，请点此查看更多更全内容