数据结构实验教程 C/C++语言版PDF电子书下载

第1章 抽象数据类型 1

1.1实验目的 1

1.2实验内容及要求 1

1.2.1实验内容 1

1.2.2实验要求 1

1.3知识点提示 2

1.3.1抽象类型定义 2

1.3.2复数 2

1.3.3抽象数据类型的复数例 2

1.3.4结构体类型定义 3

1.3.5程序的组织 4

1.4实验步骤 4

1.5实验程序参考 5

1.5.1 Complex.h 5

1.5.2 Complex.cpp 6

1.5.3 main.cpp 8

1.5.4运行截图 9

1.6常见问题及思考 10

1.6.1常见问题及解答 10

1.6.2思考 10

1.7选做：三元组 10

第2章 线性表 11

2.1实验目的 11

2.2实验内容及要求 11

2.2.1实验内容 11

2.2.2实验要求 11

2.3知识点提示 12

2.3.1线性表的基本定义 12

2.3.2线性表的顺序存储结构 12

2.3.3线性表顺序表示的插入操作 13

2.3.4线性表顺序表示的删除操作 14

2.3.5线性表的链式存储结构 14

2.3.6线性链表的插入操作 15

2.4实验步骤 16

2.5实验程序参考 17

2.5.1 Common.h 17

2.5.2 LinkL.ist.h 17

2.5.3 main.cpp 21

2.5.4运行截图 23

2.6常见问题及思考 24

2.7选做：线性表的逆置 25

第3章 栈及其应用 26

3.1实验目的 26

3.2实验内容及要求 26

3.2.1实验内容 26

3.2.2实验要求 26

3.3知识点提示 27

3.3.1顺序栈的结构定义 27

3.3.2链栈的结构定义 27

3.3.3栈的基本操作 28

3.4实验步骤 28

3.5实验程序参考 29

3.5.1 SeqStack.h 29

3.5.2 main.cpp 31

3.5.3结果截图 32

3.6常见问题及思考 32

3.7选做：迷宫问题 33

3.7.1问题描述 33

3.7.2参考程序Stack.h 33

3.7.3参考程序Main.cpp 35

第4章 串的模式匹配 39

4.1实验目的 39

4.2实验内容及要求 39

4.2.1实验内容 39

4.2.2实验要求 39

4.3知识点提示 40

4.3.1 ADT SString 40

4.3.2字符串的存储结构 40

4.3.3朴素匹配算法 41

4.3.4 KMP算法 42

4.4实验步骤 43

4.5实验程序参考 44

4.5.1 SString.cpp 44

4.5.2 main.cpp 46

4.5.3结果截图 46

4.6常见问题及思考 47

第5章 二叉树的建立、遍历及常用运算 48

5.1实验目的 48

5.2实验内容及要求 48

5.2.1实验内容 48

5.2.2实验要求 49

5.3知识点提示 49

5.3.1 ADT Tree 49

5.3.2二叉树的存储结构 50

5.3.3二叉树的遍历 51

5.3.4二叉树遍历的非递归算法（中序） 52

5.3.5二叉树构造的递归算法（扩展先序） 53

5.4实验步骤 53

5.5实验程序参考 54

5.5.1 BiTree.cpp 54

5.5.2 main.cpp 59

5.5.3运行截图 60

5.6常见问题及思考 61

5.7选做：哈夫曼树与哈夫曼编码 61

第6章 图及其应用 62

6.1实验目的 62

6.2实验内容及要求 62

6.2.1实验内容 62

6.2.2实验要求 62

6.3知识点提示 63

6.3.1图的抽象数据类型 63

6.3.2邻接矩阵表示法 63

6.3.3邻接表表示法 64

6.3.4图的深度优先遍历 65

6.3.5图的广度优先遍历 66

6.3.6最短路径算法 67

6.4实验步骤 68

6.5实验程序参考 69

6.5.1 ArcInfoType.h 70

6.5.2 VertexInfoType.h 70

6.5.3 Queue.h 71

6.5.4 ALGraph. h 73

6.5.5 Main.cpp 82

6.5.6输入文件 83

6.5.7运行截图 84

6.6常见问题及思考 84

6.7实验扩展 85

第7章 查找与排序 86

7.1实验目的 86

7.2实验内容及要求 86

7.2.1实验内容 86

7.2.2实验要求 87

7.3知识点提示 88

7.3.1直接插入排序 88

7.3.2快速排序 89

7.3.3堆排序 90

7.3.4顺序查找 91

7.3.5二分查找 92

7.4实验步骤 93

7.5实验程序参考 94

7.5.1 SortApp.cpp 94

7.5.2排序运行截图 99

7.5.3 SearchApp.cpp 99

7.5.4查找运行截图 102

7.6常见问题及思考 103

7.7实验扩展 103

第8章 综合实例——内存分配模拟系统 104

8.1课程设计目的 104

8.2课程设计内容 104

8.3课程设计过程 104

8.3.1总体设计 104

8.3.2数据结构定义 104

8.3.3分配算法 105

8.4实验程序参考 108

8.5系统运行结果截图 119

附录一：实验报告规范 122

附录二：VS2008简单调试 124

参考文献 132