数据结构实验教程

第1章 抽象数据类型

1.1 实验目的

1.2 实验内容及要求

1.2.1 实验内容

1.2.2 实验要求

1.3 知识点提示

1.3.1 抽象类型定义

1.3.2 复数

1.3.3 抽象数据类型的复数例

1.3.4 结构体类型定义

1.3.5 程序的组织

1.4 实验步骤

1.5 实验程序参考

1.5.1 Complex.h

1.5.2 Complex.cpp

第1章 抽象数据类型

1.1 实验目的

1.2 实验内容及要求

1.2.1 实验内容

1.2.2 实验要求

1.3 知识点提示

1.3.1 抽象类型定义

1.3.2 复数

1.3.3 抽象数据类型的复数例

1.3.4 结构体类型定义

1.3.5 程序的组织

1.4 实验步骤

1.5 实验程序参考

1.5.1 Complex.h

1.5.2 Complex.cpp

1.5.3 main.cpp

1.5.4 运行截图

1.6 常见问题及思考

1.6.1 常见问题及解答

1.6.2 思考

1.7 选做：三元组

第2章 线性表

2.1 实验目的

2.2 实验内容及要求

2.2.1 实验内容

2.2.2 实验要求

2.3 知识点提示

2.3.1 线性表的基本定义

2.3.2 线性表的顺序存储结构

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

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

2.3.5 线性表的链式存储结构

2.3.6 线性链表的插入操作

2.4 实验步骤

2.5 实验程序参考

2.5.1 Common.h

2.5.2 LinkList.h

2.5.3 main.cpp

2.5.4 运行截图

2.6 常见问题及思考

2.7 选做：线性表的逆置

第3章 栈及其应用

3.1 实验目的

3.2 实验内容及要求

3.2.1 实验内容

3.2.2 实验要求

3.3 知识点提示

3.3.1 顺序栈的结构定义

3.3.2 链栈的结构定义

3.3.3 栈的基本操作

3.4 实验步骤

3.5 实验程序参考

3.5.1 SeqStack.h

3.5.2 main.cpp

3.5.3 结果截图

3.6 常见问题及思考

3.7 选做：迷宫问题

3.7.1 问题描述

3.7.2 参考程序Stack.h

3.7.3 参考程序Main.cpp

第4章 串的模式匹配

4.1 实验目的

4.2 实验内容及要求

4.2.1 实验内容

4.2.2 实验要求

4.3 知识点提示

4.3.1 ADT SString

4.3.2 字符串的存储结构

4.3.3 朴素匹配算法

4.3.4 KMP算法

4.4 实验步骤

4.5 实验程序参考

4.5.1 SString.cpp

4.5.2 main.cpp

4.5.3 结果截图

4.6 常见问题及思考

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

5.1 实验目的

5.2 实验内容及要求

5.2.1 实验内容

5.2.2 实验要求

5.3 知识点提示

5.3.1 ADT Tree

5.3.2 二叉树的存储结构

5.3.3 二叉树的遍历

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

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

5.4 实验步骤

5.5 实验程序参考

5.5.1 BiTree.cpp

5.5.2 main.cpp

5.5.3 运行截图

5.6 常见问题及思考

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

第6章 图及其应用

6.1 实验目的

6.2 实验内容及要求

6.2.1 实验内容

6.2.2 实验要求

6.3 知识点提示

6.3.1 图的抽象数据类型

6.3.2 邻接矩阵表示法

6.3.3 邻接表表示法

6.3.4 图的深度优先遍历

6.3.5 图的广度优先遍历

6.3.6 最短路径算法

6.4 实验步骤

6.5 实验程序参考

6.5.1 ArtinfoType.h

6.5.2 VertexlnfoType.h

6.5.3 Queue.h

6.5.4 ALGraph.h

6.5.5 Main.cpp

6.5.6 输入文件

6.5.7 运行截图

6.6 常见问题及思考

6.7 实验扩展

第7章 查找与排序

7.1 实验目的

7.2 实验内容及要求

7.2.1 实验内容

7.2.2 实验要求

7.3 知识点提示

7.3.1 直接插入排序

7.3.2 快速排序

7.3.3 堆排序

7.3.4 顺序查找

7.3.5 二分查找

7.4 实验步骤

7.5 实验程序参考

7.5.1 SortAPP.cpp

7.5.2 排序运行截图

7.5.3 SearchAPP.cpp

7.5.4 查找运行截图

7.6 常见问题及思考

7.7 实验扩展

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

8.1 课程设计目的

8.2 课程设计内容

8.3 课程设计过程

8.3.1 总体设计

8.3.2 数据结构定义

8.3.3 分配算法

8.4 实验程序参考

8.5 系统运行结果截图

附录一：实验报告规范

附录二：VS2008简单调试

参考文献

《数据结构实验教程（C/C++语言版）》主要内容包括：抽象数据类型；线性表；栈及其应用；串的模式匹配；二叉树的建立、遍历及常用运算；图及其应用；查找与排序；综合实例——内存分配模拟系统。

《数据结构实验教程（C\C++语言版）》第1章为抽象数据类型，该章以复数为例给出抽象数据类型的定义和实现；第2章至第7章分别是线性表、栈、串、二叉树、图、查找和排序六个重要结构的实现和应用；第8章则综合利用了所学结构和算法，给出一个综合实验。本书附录一是实验报告的基本格式和内容要求；附录二是一个在VS2008下进行调试程序、发现问题的实例。

　　《数据结构实验教程（C\C++语言版）》可以作为数据结构课程学习过程中的配套教材使用，也可以为爱好程序设计和自学程序设计的人员提供参考。教师可以根据具体情况调整各部分的课时分布。