第1章 预备知识 1
1.1软件开发过程与设计原理 1
1.1.1软件开发的一般步骤 1
1.1.2软件设计的基本原理 1
1.2 C语言程序的组织与管理 3
1.2.1 C语言程序的构成 4
1.2.2较大程序的实现方法和 4
项目管理 4
1.2.3程序的生成与调试 4
1.3程序测试初步 5
1.3.1程序测试的基本概念 6
1.3.2软件测试的技术分类 6
1.3.3测试环境的构建 8
1.3.4测试用例设计 10
1.4程序效率的事前估算与 16
事后统计 16
1.4.1程序的时间复杂度 17
1.4.2程序运行时间获取 17
1.5实验环境 18
1.5.1 Linux实验环境 18
1.5.2 Windows实验环境 24
第2章 线性表 33
2.1知识点 33
2.1.1线性表的逻辑结构 33
2.1.2线性表的物理结构 34
2.2基础实验 38
2.2.1实验一：顺序表操作实验 38
2.2.2实验二：单链表操作实验 42
2.3简单应用实验 47
2.3.1适用线性表结构的一般特征分析 47
2.3.2在C/C+++环境下，应用基础实验中已实现的线性表结构的几点提示 47
2.3.3应用实验一：一元多项式的相加 48
2.3.4应用实验二：城市链表 54
2.4小结 61
第3章 栈与队列 63
3.1知识点 63
3.1.1栈的逻辑结构 63
3.1.2栈的物理结构 64
3.1.3队列的逻辑结构 65
3.1.4队列的物理结构 65
3.2基础实验 67
3.2.1实验一：顺序栈的操作实验 67
3.2.2实验二：顺序循环队列的操作实验 70
3.3简单应用实验 75
3.3.1适用栈和队列结构的一般特征分析 75
3.3.2在C/C+++环境下，应用基础实验中已实现的栈与队列的几点提示 75
3.3.3应用实验一：迷宫问题 76
3.3.4应用实验二：病人看病模拟程序 81
3.4小结 84
第4章 字符串 85
4.1知识点 85
4.1.1串的逻辑结构 85
4.1.2串的物理结构 86
4.2基础实验 87
4.2.1实验一：串的动态数组存储表示操作实验 87
4.2.2实验二：串的模式匹配实验 95
4.3简单应用实验 101
4.3.1适用串结构的一般特征分析 101
4.3.2在C/C+++环境下，应用基础实验中已实现的串结构的几点提示 101
4.3.3应用实验：建立词索引表（说明：具体内容要求满足课本p86内容） 101
4.4小结 111
第5章 数组 113
5.1知识点 113
5.1.1数组的逻辑结构 113
5.1.2数组的物理结构 114
5.1.3矩阵的压缩存储 115
5.1.4广义表的逻辑和存储结构 119
5.2基础实验 120
5.2.1实验一：稀疏矩阵的三元组顺序存储结构的基本操作 120
5.2.2实验二：稀疏矩阵的十字链表存储结构的基本操作 127
5.2.3实验三：广义表的操作实验 136
5.3简单应用实验 147
5.3.1适用数组结构和广义表结构的一般特征分析 147
5.3.2在C/C+++环境下，应用基础实验中已实现的数组和广义表的几点提示 147
5.3.3应用实验：广义表的应用 147
5.4小结 159
第6章 二叉树与树 161
6.1知识点 161
6.1.1二叉树和树的逻辑结构 161
6.1.2二叉树和树的物理结构 163
6.2基础实验 164
6.2.1实验一：二叉树的二叉链表存储表示操作实验 164
6.2.2实验二：树的孩子-兄弟链表存储表示操作实验 168
6.3简单应用实验 172
6.3.1适用二叉树结构的一般特征分析 172
6.3.2在C/C+++环境下，应用基础实验中已实现的二叉树结构的几点提示 172
6.3.3应用实验一：赫夫曼树和赫夫曼编码 172
6.3.4应用实验二：联赛的构造 177
6.4小结 180
第7章图 181
7.1知识点 181
7.1.1图的逻辑结构 181
7.1.2图的物理结构 182
7.2基础实验 185
7.2.1实验一：图的邻接矩阵存储结构的操作实验 185
7.2.2实验二：图的邻接表存储结构的操作实验 203
7.3简单应用实验 220
7.3.1适用图结构的一般特征分析 220
7.3.2在C/C+++环境下，应用基础实验中己实现的图结构的几点提示 220
7.3.3应用实验一：最小生成树（Prim算法） 221
7.3.4应用实验二：最短路径问题 224
7.4小结 231
第8章 查找表 233
8.1知识点 233
8.1.1静态查找表 233
8.1.2动态查找表 234
8.1.3哈希表 237
8.2基础实验 238
8.2.1实验一：折半查找操作实验 238
8.2.2实验二：二叉排序树操作实验 240
8.3简单应用实验 245
8.3.1在C/C+++环境下，应用基础实验中已实现的查找方法的几点提示 245
8.3.2应用实验：装箱问题 246
8.4小结 254
第9章 排序 255
9.1知识点 255
9.1.1排序的基本概念 255
9.1.2排序算法基本性能比较 255
9.2基础实验 256
9.2.1实验一：插入排序操作实验 256
9.2.2实验二：选择排序操作实验 260
9.2.3实验三：交换排序操作实验 266
9.2.4实验四：归并排序与基数排序操作实验 270
9.3简单应用实验 277
9.4小结 286
第10章 课程设计 287
10.1课程设计的目的和要求 287
10.2课程设计的实施步骤 287
10.3课程设计总结报告的撰写规范 288
10.4课程设计案例 289
10.4.1设计一：五泉山公园导游系统的设计与实现 289
10.4.2设计二：航空票务管理系统的设计与实现 299
附录 实验报告格式 309
参考文献 311