目录

第1部分基 础 知 识

第1章绪论3

1.1数据结构的基本概念3

1.2算法和算法分析4第2章线性表6

2.1线性表的逻辑结构6

2.2线性表的顺序存储结构7

2.3线性表的链式存储结构7第3章栈和队列9

3.1栈9

3.2队列10

3.3优先队列12第4章串13

4.1串类型的定义13

4.2字符串模式匹配算法13第5章数组和广义表16

5.1数组16

5.2矩阵17

5.3广义表19第6章树和二叉树22

6.1树的基本概念22

6.2二叉树23

6.3二叉树遍历25

6.4线索二叉树26

6.5树和森林的实现27

6.6哈夫曼树与哈夫曼编码32

6.7树的计数33第7章图35

7.1图的定义和术语35

7.2图的存储表示38

7.3图的遍历40

7.4连通无向网的最小代价生成树40

7.5有向无环图及应用41

7.6最短路径41第8章查找43

8.1查找的基本概念43

8.2静态查找表43

8.3动态查找表43

8.4哈希表47第9章排序50

9.1概述50

9.2插入排序51

9.3交换排序51

9.4选择排序51

9.5归并排序52

9.6基数排序52

9.7外部排序53

第10章文件55

10.1主存储器和辅助存储器55

10.2各种常用文件结构55

第11章算法设计与分析56

11.1算法设计56

11.2算法分析58

第2部分实验

实验1石头、剪刀、布61

实验221点70

实验3不带头节点形式的单链表80

实验4任意大非负整数的任意大非负整数次方93

实验5病人就医管理102

实验6利用后缀表达式计算中缀表达式的值107

实验7文本串的加密115

实验8改造串类120

实验9螺旋方阵130

实验10引用数使用空间表法广义表存储结构134

实验11用二叉树表示表达式147

实验12改进哈夫曼树类153

实验13求最小生成树的Kruskal的算法改进161

实验14图的根顶点166

实验15链地址法处理冲突的哈希表170

实验16字符统计177

实验17改造快速排序算法181实验18改造基数排序算法186

实验19学生基本信息管理193

实验20电话号码的查找205

实验21农夫过河问题216

实验22n皇后问题225

第3部分课 程 设 计

项目1算术表达式求值233

项目2停车场管理系统237

项目3电话客户服务模拟器244

项目4简单文本编辑器250项目5压缩软件260

项目6排课软件271

项目7公园导游系统282

项目8理论计算机科学家族谱的文档／视图模式288

项目9动物游戏296

项目10简单个人图书管理系统302

项目11词典变位词检索系统311

参考文献316

附录A本书配套软件包318

附录B实验报告格式324

附录C课程设计报告格式325

附录D流行C++开发环境的使用方法326