第一部分 基础知识 1
1.1 绪论 1
1.1.1 数据结构的基本概念 1
1.1.2 算法和算法分析 2
1.1.3 实用程序软件包 3
1.2 线性表 6
1.2.1 线性表的逻辑结构 6
1.2.2 线性表的顺序存储结构 7
1.2.3 线性表的链式存储结构 8
1.3 栈和队列 9
1.3.1 栈 9
1.3.2 队列 11
1.4 串 13
1.4.1 串类型的定义 13
1.4.2 字符串模式匹配算法 13
1.5 数组和广义表 15
1.5.1 数组 15
1.5.2 矩阵 17
1.5.3 广义表 19
1.6 树和二叉树 21
1.6.1 树的基本概念 21
1.6.2 二叉树 23
1.6.3 二叉树遍历 25
1.6.4 线索二叉树 26
1.6.5 树和森林 27
1.6.6 哈夫曼树与哈夫曼编码 33
1.6.7 树的计数 34
1.7 图 35
1.7.1 图的定义和术语 35
1.7.2 图的存储表示 38
1.7.3 图的遍历 40
1.7.4 图的最小代价生成树 40
1.7.5 有向无环图及应用 41
1.7.6 最短路径 42
1.8 查找 43
1.8.1 查找的基本概念 43
1.8.2 静态表的查找 43
1.8.3 动态查找表 44
1.8.4 散列表 48
1.9 排序 50
1.9.1 概述 50
1.9.2 插入排序 51
1.9.3 交换排序 51
1.9.4 选择排序 51
1.9.5 归并排序 52
1.9.6 基数排序 52
1.9.7 外部排序 53
1.10 文件 54
1.10.1 主存储器和辅助存储器 54
1.10.2 各种常用文件结构 54
1.11 算法设计与分析 56
1.11.1 算法设计 56
1.11.2 算法分析 57
第二部分 实验 58
实验1 不带头结点形式的单链表 58
实验2 改造串类 69
实验3 引用数使用空间表法广义表存储结构 79
实验4 改进哈夫曼树类模板 92
实验5 改造最小生成树的Kruskal算法的实现 99
实验6 链地址法处理冲突的散列表 104
实验7 优化快速排序算法的实现 110
实验8 n皇后问题 114
第三部分 课程设计 119
项目1 算术表达式求值 119
项目2 简单文本编辑器 123
项目3 压缩软件 132
项目4 公园导游系统 138
项目5 专家系统应用——动物游戏 143
项目6 词典变位词检索系统 148
附录A 课本的软件包 154
附录B 实验报告格式 159
附录C 课程设计报告格式 160
参考文献 161