数据结构实验教程

第一篇 数据结构基础

第1章 数据结构与算法分析基础

1.1 知识点概述

1.1.1 基本术语

1.1.2 算法和算法的量度

1.1.3 C++相关知识

1.2 实验项目

1.2.1 熟悉Project组织应用程序实验

1.2.2 抽象数据类型的表示和实现实验

1.2.3 算法和算法分析实验

1.3 习题范例解析

1.4 习题

1.4.1 选择题

1.4.2 填空题

1.4.3 应用题

第2章 线性表

2.1 知识点概述

2.1.1 线性表的定义和抽象数据类型

2.1.2 线性表的顺序存储表示

2.1.3 线性表的链接存储表示

2.2 实验项目

2.2.1 线性表的顺序存储实验

2.2.2 线性表的链式存储实验

2.2.3 约瑟夫环的实现

2.3 习题范例解析

2.4 习题

2.4.1 选择题

2.4.2 填空题

2.4.3 应用题

2.4.4 算法设计题

第3章 栈和队列

3.1 知识点概述

3.1.1 栈

3.1.2 队列

3.2 实验项目

3.2.1 栈的顺序表示和实现实验

3.2.2 FA-列（循环队列）的表示和实现实验

3.2.3 栈与队列的应用实验

3.3 习题范例解析

3.4 习题

3.4.1 选择题

3.4.2 填空题

3.4.3 应用题

3.4.4 算法设计题

第4章 树

4.1 知识点概述

4.1.1 树的定义和基本概念

4.1.2 二叉树的定义和基本概念

4.1.3 二叉树的存储结构

4.1.4 二叉树的遍历

4.2 实验项目

4.2.1 二叉链表的基本操作实验

4.2.2 二叉链表的进一步操作实验

4.3 习题范例解析

4.4 习题

4.4.1 选择题

4.4.2 填空题

4.4.3 应用题

4.4.4 算法设计题

第5章 图

5.1 知识点概述

5.1.1 图的定义

5.1.2 图的基本术语

5.1.3 图的抽象数据类型

5.1.4 图的存储结构

5.1.5 图的遍历

5.2 实验项目

5.2.1 图的基本操作实验——邻接矩阵存储结构

5.2.2 图的基本操作实验——邻接表存储结构

5.3 习题范例解析

5.4 习题

5.4.1 选择题

5.4.2 填空题

5.4.3 应用题

5.4.4 算法设计题

第二篇 数据结构进阶

第6章 线性表和栈的应用

6.1 知识点概述

6.1.1 线性表的应用——多项式计算

6.1.2 栈的应用——算术表达式的计算

6.2 实验项目

6.2.1 线性表的应用——多项式计算实验

6.2.2 栈的应用——算术表达式的计算实验

6.3 习题范例解析

6.4 习题

6.4.1 选择题

6.4.2 填空题

6.4.3 应用题

6.4.4 算法设计题

第7章 稀疏矩阵和广义表

7.1 知识点概述

7.1.1 稀疏矩阵

7.1.2 广义表

7.2 实验项目

7.2.1 稀疏矩阵的顺序存储实验

7.2.2 稀疏矩阵的链接存储实验

7.2.3 广义表运算实验

7.3 习题范例解析

7.4 习题

7.4.1 选择题

7.4.2 填空题

7.4.3 应用题

7.4.4 算法设计题

第8章 特殊二叉树

8.1 知识点概述

8.1.1 二叉搜索树

8.1.2 堆

8.1.3 哈夫曼树

8.2 实验项目

8.2.1 二叉搜索树的基本操作实现

8.2.2 堆的基本操作实现

8.2.3 哈夫曼树及其应用实验

8.3 习题范例解析

8.4 习题

8.4.1 选择题

8.4.2 应用题

8.4.3 算法设计题

第9章 图的应用

9.1 知识点概述

9.1.1 最小生成树

9.1.2 最短路径

9.1.3 拓扑排序

9.2 实验项目

9.2.1 图的最小生成树实验

9.2.2 图的最短路径实验

9.2.3 图的拓扑排序实验

9.3 习题范例解析

9.4 习题

9.4.1 选择题

9.4.2 填空题

9.4.3 应用题

9.4.4 算法设计题

第10章 查找

10.1 知识点概述

10.1.1 查找的概念

10.1.2 顺序查找

10.1.3 二分查找

10.1.4 索引查找

10.1.5 散列查找

10.2 实验项目

10.2.1 索引查找的实现

10.2.2 散列查找的实现

10.3 习题范例解析

10.4 习题

10.4.1 选择题

10.4.2 填空题

10.4.3 应用题

10.4.4 算法设计题

第11章 排序

11.1 知识点概述

11.1.1 排序的基本概念

11.1.2 插入排序

11.1.3 选择排序

11.1.4 交换排序

11.1.5 归并排序

11.1.6 内排序方法比较

11.2 实验项目

11.2.1 排序算法的应用（一）

11.2.2 排序算法的应用（二）

11.3 习题范例解析

11.4 习题

11.4.1 选择题

11.4.2 填空题

11.4.3 应用题

11.4.4 算法设计题

附录 实验报告格式

主要参考文献

《高等院校计算机技术“十二五”规划教材：数据结构实验教程》采用C++语言作为数据结构与算法的描述语言，对应于教科书中的各知识点，每一章首先对知识点进行概述，然后给出相应内容的若干个实验项目，最后再给出习题范例解析与习题。全书由2个篇章组成，第一篇章是数据结构的基础部分，内容涉及数据结构和算法分析基础、线性表、栈和队列、树和二叉树、图；第二篇章是数据结构的进阶部分，内容涉及线性表和栈的应用、稀疏矩阵和广义表、特殊二叉树、图的应用、查找与排序等。每个知识点均包含2至3个实验项目，实验内容的组织充分顾及了不同的难易程度，每个实验项目除给出基本实验内容外，还包含选做内容部分与实验提示，以符合不同层次的学生。此外，每一章还给出了习题范例解析、选择题、填空题、解答题、算法设计题，以及所有习题的参考答案，这些题目大多是作者长年教学积累的成果，通过习题，希望帮助读者加深对每一个知识点的理解和掌握。