第一部分 数据结构与算法基础知识和实验 3
第1章 绪论 3
1.1基础知识 3
数据结构的基本概念 3
算法和算法分析 4
实用程序软件包 5
1.2上机实验 7
石头、剪刀、布游戏 7
纸牌游戏——“21点” 7
第2章 线性表 17
2.1基础知识 17
线性表的逻辑结构 17
线性表的顺序存储结构 18
线性表的链式存储结构 19
2.2上机实验 22
不带头结点形式的单链表 22
任意大非负整数的任意大非负整数次方 34
第3章 栈和队列 35
3.1基础知识 35
栈 35
队列 37
优先队列 39
3.2上机实验 40
病人就医管理 40
利用后缀表达式计算中缀表达式的值 44
第4章 串 53
4.1基础知识 53
串类型的定义 53
字符串的实现 53
字符串模式匹配算法 54
4.2上机实验 55
文本串的加密 55
改造串类 60
第5章 数组和广义表 70
5.1基础知识 70
数组 70
矩阵 72
广义表 76
5.2上机实验 79
螺旋方阵 79
引用数使用空间表法广义表存储结构 82
第6章 树和二叉树 95
6.1基础知识 95
树的基本概念 95
二叉树 95
二叉树遍历 99
线索二叉树 99
树和森林 101
哈夫曼树与哈夫曼编码 107
树的计数 109
6.2上机实验 109
用二叉树表示表达式 109
改进哈夫曼树类 114
第7章 图 123
7.1基础知识 123
图的定义和述语 123
图的存储表示 125
图的遍历 129
图的最小代价生成树 130
有向无环图及应用 130
最短路径 131
7.2上机实验 132
改进最小生成树的Kruskal算法的实现 132
图的根顶点 136
第8章 查找 141
8.1基础知识 141
查找的基本概念 141
静态表的查找 141
动态查找表 141
散列表 146
8.2上机实验 147
链地址法处理冲突的散列表 147
字符统计 153
第9章 排序 157
9.1基础知识 157
概述 157
插入排序 157
交换排序 157
选择排序 158
归并排序 158
基数排序 158
外部排序 159
用堆实现优先队列 159
9.2上机实验 160
改造快速排序算法的实现 160
改造基数排序算法 164
第10章 文件 170
10.1基础知识 170
主存储器和辅助存储器 170
各种常用文件结构 170
10.2上机实验 171
学生基本信息管理 171
电话号码查找系统 183
第11章 算法设计与分析 184
11.1基础知识 184
算法设计 184
算法分析 186
可计算性问题 186
11.2上机实验 187
农夫过河问题 187
n皇后问题 194
第二部分 数据结构与算法课程设计 201
第12章 课程设计 201
12.1算术表达式求值 201
12.2停车场管理 205
12.3电话客户服务模拟 210
12.4简单本文编辑器 216
12.5压缩软件 225
12.6排课软件 235
12.7公园导游系统 245
12.8理论计算机科学家族谱的文档／视图模式 250
12.9专家系统应用——动物游戏 257
12.10简单个人图书管理系统 262
12.11词典变位词检索系统 271
附录A 配套软件包 276
附录B 实验报告格式 282
附录C 课程设计报告格式 283
参考文献 284