数据结构(AR版)

第1章绪论/1
1.1数据结构的重要性1
1.2数据结构基本术语2
1.3数据的逻辑结构4
1.4数据的存储结构5
1.5算法的基本概念5
1.6算法分析与度量6
1.6.1算法的评价标准6
1.6.2算法效率的度量7
1.7总结与提高13
1.8习题一13
第2章线性结构/16
2.1线性表及逻辑结构16
2.2线性表的顺序存储18
2.2.1顺序存储18
2.2.2顺序表的存储结构描述19
2.2.3顺序结构上的运算19
2.3线性表的链式存储26
2.3.1线性链表26
2.3.2线性链表的存储结构描述27
2.3.3线性链表的基本运算28
2.3.4线性链表操作的性能分析35
2.4顺序表与链表的比较35
2.5循环链表36
2.6双向链表37
2.7应用举例42
2.7.1顺序表的应用： 大整数求和42
2.7.2单链表的应用： 一元多项式加法运算44〖1〗数据结构(AR版)目录〖3〗〖3〗2.8总结与提高48
2.9习题二49
第3章栈和队列/51
3.1栈51
3.1.1栈的定义51
3.1.2栈的顺序存储结构52
3.1.3栈的链式存储结构57
3.1.4栈的特性分析63
3.2队列65
3.2.1队列的定义65
3.2.2循环队列66
3.2.3链式队列70
3.2.4双端队列74
3.3栈和队列的应用76
3.3.1括号匹配76
3.3.2表达式求解78
3.3.3队列在层次遍历中的应用86
3.4递归87
3.4.1递归的概念87
3.4.2递归算法的设计89
3.4.3转化递归算法为非递归算法91
3.5总结与提高95
3.6习题三95
第4章数组和字符串/98
4.1数组的定义98
4.2数组的顺序存储结构99
4.2.1一维数组的顺序存储100
4.2.2多维数组的顺序存储100
4.3矩阵的压缩存储104
4.3.1特殊矩阵的压缩存储105
4.3.2三对角矩阵的压缩存储106
4.3.3稀疏矩阵的压缩存储107
4.4稀疏矩阵的运算116
4.4.1稀疏矩阵的转置116
4.4.2稀疏矩阵的乘法119
4.5字符串124
4.5.1串的基本概念124
4.5.2串的存储结构124
4.5.3串的模式匹配算法126
4.6总结与提高133
4.7习题四133
第5章树/136
5.1树的定义及基本术语136
5.2N叉树138
5.2.1N叉树的概念138
5.2.2N叉树的性质139
5.3二叉树140
5.3.1二叉树的定义及性质140
5.3.2二叉树的基本操作142
5.4二叉树的存储结构143
5.4.1顺序存储结构143
5.4.2链式存储结构143
5.5二叉树的操作146
5.5.1二叉树的递归遍历146
5.5.2二叉树构造函数149
5.5.3二叉树析构函数150
5.5.4递归遍历算法的应用举例150
5.5.5由遍历序列恢复二叉树153
5.5.6二叉树遍历的非递归算法154
5.6线索二叉树158
5.6.1线索二叉树的定义158
5.6.2中序线索二叉树的建立和遍历160
5.6.3中序线索二叉树插入166
5.6.4中序线索二叉树删除170
5.6.5前序与后序线索二叉树174
5.6.6线索二叉树算法的应用举例174
5.7二叉排序树176
5.7.1二叉排序树的基本概念176
5.7.2二叉排序树的插入178
5.7.3二叉排序树的删除180
5.7.4二叉排序树查找分析184
5.7.5二叉排序树算法的应用举例187
5.8平衡二叉树188
5.8.1平衡二叉树基本概念188
5.8.2平衡化旋转188
5.8.3平衡二叉树的插入191
5.8.4平衡二叉树的删除194
5.8.5平衡二叉树算法的应用举例198
5.9树、森林与二叉树的关系207
5.9.1树的存储结构207
5.9.2森林与二叉树的转换211
5.9.3树与森林的遍历213
5.10Huffman树及其应用215
5.10.1带权路径长度的概念215
5.10.2Huffman树的构造216
5.10.3Huffman树结构定义及算法实现218
5.10.4Huffman编码219
5.11总结与提高222
5.12习题五223
第6章图/227
6.1图的基本概念227
6.1.1图的基本概念与术语227
6.1.2图的基本操作230
6.2图的存储结构232
6.2.1邻接矩阵232
6.2.2邻接表236
6.2.3有向图的十字链表表示240
6.2.4无向图的邻接多重表表示245
6.3图的遍历248
6.3.1深度优先搜索249
6.3.2广度优先搜索251
6.4生成树254
6.4.1MST性质254
6.4.2Kruskal算法255
6.4.3Prim算法261
6.5路径规划264
6.5.1*短路径265
6.5.2Dijkstra算法265
6.5.3Floyd算法269
6.6拓扑排序272
6.7关键路径278
6.8总结与提高288
6.9习题六288
第7章查找/292
7.1基本概念292
7.2线性表查找293
7.2.1顺序查找293
7.2.2线性链表上的顺序查找295
7.3折半查找法296
7.3.1一般的折半查找法296
7.3.2次优查找树： 折半查找的改进方法299
7.4索引查找305
7.4.1索引顺序表与分块查找305
7.4.2多级索引结构与m叉查找树307
7.4.3B树的概念308
7.4.4B树上的查找310
7.4.5B树上的插入312
7.4.6B树上的删除316
7.4.7B树析构函数322
7.4.8B树层序遍历输出322
7.4.9B树操作应用举例324
7.4.10B 树324
7.5散列表及其查找325
7.5.1散列的概念326
7.5.2散列函数设计326
7.5.3处理冲突的方法329
7.5.4散列表查找性能分析341
7.6总结与提高342
7.7习题七343
第8章排序/345
8.1基本概念345
8.2插入排序346
8.2.1直接插入排序347
8.2.2折半插入排序349
8.2.3希尔排序350
8.3交换排序352
8.3.1冒泡排序352
8.3.2快速排序354
8.4选择排序359
8.4.1简单选择排序360
8.4.2堆排序361
8.5归并排序366
8.5.1二路归并366
8.5.2二路归并递归排序算法368
8.6分配排序369
8.6.1桶排序369
8.6.2基数排序370
8.6.3关键字分解370
8.6.4链式基数排序371
8.7内部排序算法比较378
8.7.1排序方法的下界378
8.7.2各种内排序方法的比较379
8.8总结与提高382
8.9习题八382
参考文献/384
第1章面向对象程序设计概述/1
1.1面向过程程序设计1
1.2面向对象程序设计5
1.2.1面向对象程序设计的思想5
1.2.2面向对象的基本概念6
1.2.3面向对象程序设计的优点9
1.3面向对象的软件开发10
1.4图书馆图书借阅管理系统的面向对象分析与设计12
1.4.1面向对象分析12
1.4.2面向对象设计15
本章小结16
习题17
第2章面向过程程序设计概述/18
2.1从C语言到C 18
2.2简单C 程序19
2.3C 对C语言的扩充25
2.3.1C 的输入输出25
2.3.2C 对C语言数据类型的扩展26
2.3.3常变量26
2.3.4指针28
2.3.5引用38
2.3.6函数44
2.3.7名字空间53
2.3.8字符串变量56
2.3.9复数变量60
2.4C 程序的编写和实现63
本章小结64
习题64第3章类与对象/66
3.1类的声明和对象的定义66
3.1.1类和对象的概念及其关系66
3.1.2类的声明67
3.1.3对象的定义68
3.2类的成员函数70
3.2.1成员函数的性质70
3.2.2在类外定义成员函数70
3.2.3inline成员函数71
3.2.4成员函数的存储方式72
3.3对象成员的访问74
3.3.1通过对象名和成员运算符来访问对象的成员74
3.3.2通过指向对象的指针来访问对象的成员74
3.3.3通过对象的引用来访问对象的成员75
3.4构造函数与析构函数76
3.4.1构造函数76
3.4.2析构函数80
3.4.3构造函数和析构函数的调用次序81
3.5对象数组85
3.6对象指针88
3.6.1指向对象的指针88
3.6.2指向对象成员的指针88
3.6.3this指针90
3.7对象与const92
3.7.1常对象92
3.7.2常对象成员93
3.7.3指向对象的常指针94
3.7.4指向常对象的指针94
3.7.5对象的常引用96
3.8对象的动态创建与释放97
3.9对象的赋值与复制98
3.9.1对象的赋值98
3.9.2对象的复制102
3.9.3对象的赋值与复制的比较105
3.10向函数传递对象105
3.11图书馆图书借阅管理系统中类的声明和对象的定义108
本章小结115
习题115
第4章继承与派生/118
4.1继承与派生的概念118
4.2派生类的声明119
4.3派生类的构成120
4.4派生类中基类成员的访问属性121
4.4.1公用继承121
4.4.2私有继承123
4.4.3保护成员和保护继承125
4.4.4成员同名问题127
4.5派生类的构造函数和析构函数129
4.5.1派生类构造函数129
4.5.2派生类析构函数132
4.6多重继承134
4.6.1声明多重继承的方法134
4.6.2多重继承派生类的构造函数与析构函数134
4.6.3多重继承引起的二义性问题137
4.6.4虚基类139
4.7基类与派生类对象的关系143
4.8聚合与组合146
4.9图书馆图书借阅管理系统中继承与聚合的应用148
本章小结165
习题166
第5章多态性与虚函数/168
5.1什么是多态性168
5.2向上类型转换169
5.3功能早绑定和晚绑定171
5.4实现功能晚绑定——虚函数171
5.4.1虚函数的定义和作用172
5.4.2虚析构函数175
5.4.3虚函数与重载函数的比较177
5.5纯虚函数和抽象类177
5.6图书馆图书借阅管理系统中的多态性180
本章小结187
习题188
第6章友元与静态成员/189
6.1封装的破坏——友元189
6.1.1友元函数189
6.1.2友元类194
6.2对象机制的破坏——静态成员195
6.2.1静态数据成员196
6.2.2静态成员函数198
6.3图书馆图书借阅管理系统中友元与静态成员的应用201
本章小结202
习题202
第7章运算符重载/205
7.1为什么要进行运算符重载205
7.2运算符重载的方法207
7.3重载运算符的规则208
7.4运算符重载函数作为类的成员函数和友元函数210
7.4.1运算符重载函数作为类的成员函数210
7.4.2运算符重载函数作为类的友元函数214
7.5几种常用运算符的重载217
7.5.1单目运算符“ ”和“--”的重载217
7.5.2赋值运算符“=”的重载221
7.5.3流插入运算符“>”的重载223
7.6不同类型数据间的转换227
7.6.1系统预定义类型间的转换227
7.6.2转换构造函数228
7.6.3类型转换函数231
7.7图书馆图书借阅管理系统中的运算符重载233
本章小结238
习题239
第8章泛型编程/240
8.1函数模板240
8.1.1函数模板的定义241
8.1.2函数模板的实例化243
8.1.3模板参数244
8.1.4函数模板重载248
8.2类模板251
8.2.1类模板的定义252
8.2.2类模板的实例化253
8.2.3类模板参数256
8.3STL简介259
8.3.1容器 259
8.3.2迭代器269
8.3.3算法271
8.3.4函数对象273
8.4图书馆图书借阅管理系统中的泛型编程276
本章小结282
习题282
第9章输入输出/285
9.1C 的输入输出概述285
9.1.1C 的输入输出285
9.1.2C 的输入输出流286
9.2C 的标准输入输出流288
9.2.1C 的标准输出流288
9.2.2C 的标准输入流291
9.3输入输出运算符297
9.3.1输入运算符297
9.3.2输出运算符298
9.3.3输入与输出运算符的重载298
9.4C 格式输入输出299
9.4.1用流对象的成员函数控制输入输出格式299
9.4.2用控制符控制输入输出格式302
9.5文件操作与文件流304
9.5.1文件的概念304
9.5.2文件流类及文件流对象304
9.5.3文件的打开与关闭305
9.5.4对文本文件的操作306
9.5.5对二进制文件的操作308
9.6图书馆图书借阅管理系统中的文件操作312
本章小结313
习题313
第10章异常处理/315
10.1C 异常处理概述315
10.2C 异常处理的实现316
10.3异常与函数322
10.3.1在函数中处理异常322
10.3.2在函数调用中完成异常处理323
10.3.3限制函数异常324
10.4异常与类324
10.4.1构造函数、析构函数与异常处理324
10.4.2异常类327
10.5图书馆图书借阅管理系统中的异常处理330
本章小结332
习题333
第11章图形界面设计/334
11.1基于对话框的图形界面C 程序设计334
11.2基于单文档的图形界面C 程序设计345
11.3图书馆图书借阅管理系统的图形界面设计364
本章小结 364
习题365
参考文献/366第1章C语言程序设计概述/1
1.1程序设计语言1
1.1.1“存储程序”原理1
1.1.2程序设计语言的发展3
1.1.3语言处理程序4
1.2C语言的发展和特点5
1.3C语言的语法单位6
1.3.1C语言的基本符号6
1.3.2关键字6
1.3.3标识符6
1.3.4C语言语句8
1.4C语言程序的基本结构8
1.4.1简单的C语言程序介绍8
1.4.2C程序的结构与书写规则11
1.5程序设计与算法13
1.5.1程序设计13
1.5.2算法概述14
1.5.3算法的描述15
1.5.4结构化程序设计方法19
1.6C语言程序的上机调试20
1.6.1C语言的编译环境与运行程序的步骤20
1.6.2Turbo C开发环境21
1.6.3WinTC系统上机操作方法26
1.6.4Visual C 6.0系统上机操作方法28
本章小结34
习题34
上机实训36
实训项目: C语言开发环境的使用与程序调试 37
第2章数据类型、运算符与表达式/39
2.1C语言数据类型与数据的存储39〖1〗C语言程序设计实用教程目录〖3〗〖3〗2.1.1C语言的数据类型39
2.1.2数据在内存中的存储形式41
2.2变量与常量43
2.2.1常量43
2.2.2变量47
2.3C语言的运算符和表达式53
2.3.1概述53
2.3.2算术运算符和算术表达式55
2.3.3关系运算符和关系表达式57
2.3.4逻辑运算符和逻辑表达式58
2.3.5赋值运算符和赋值表达式60
2.3.6条件运算符和条件表达式61
2.4不同类型数据间的混合运算63
2.5位运算64
2.5.1位逻辑运算64
2.5.2位移运算65
2.5.3位运算赋值运算符65
2.6常用数学库函数的使用66
本章小结67
习题68
上机实训70
第3章顺序结构程序设计/72
3.1C语言简单语句72
3.2数据的输入与输出73
3.3格式化输入与输出75
3.3.1格式化输出函数printf()75
3.3.2格式化输入函数scanf()80
3.4字符数据的输入与输出84
3.4.1字符输出函数putchar()84
3.4.2字符输入函数getchar()85
3.5顺序结构程序设计举例87
本章小结90
习题90
上机实训93
第4章选择结构程序设计/95
4.1if语句95
4.1.1单分支if语句95
4.1.2双分支if语句96
4.1.3if语句的嵌套97
4.2switch语句100
4.3选择结构程序设计举例102
本章小结106
习题107
上机实训110
第5章循环结构程序设计/112
5.1循环的概念112
5.2for语句113
5.3while语句117
5.4do…while语句119
5.5break与continue语句121
5.5.1break语句121
5.5.2continue语句123
5.6循环的嵌套124
5.7程序举例126
本章小结128
习题128
上机实训134
第6章数组/136
6.1概述136
6.2一维数组137
6.2.1一维数组的定义137
6.2.2一维数组的引用138
6.2.3一维数组的初始化139
6.2.4应用举例141
6.3二维数组145
6.3.1二维数组的定义145
6.3.2二维数组的引用147
6.3.3二维数组的初始化147
6.3.4二维数组的应用举例148
6.4字符数组与字符串150
6.4.1字符数组150
6.4.2字符串152
6.4.3字符串处理函数153
本章小结156
习题157
上机实训160
第7章函数/162
7.1函数的定义与调用162
7.1.1函数的分类162
7.1.2函数定义的一般形式164
7.1.3函数的调用167
7.1.4函数的参数传递168
7.2函数的嵌套调用与递归调用172
7.2.1函数的嵌套调用172
7.2.2函数的递归调用173
7.3变量的作用域和存储类别175
7.3.1变量的作用域175
7.3.2变量的存储类别177
7.4内部函数与外部函数178
7.4.1内部函数179
7.4.2外部函数179
7.5程序的多文件结构180
7.6程序举例185
本章小结189
习题189
上机实训192
第8章编译预处理/194
8.1宏定义命令194
8.2文件包含200
8.3条件编译203
本章小结205
习题205
上机实训209
第9章指针/210
9.1地址与指针类型210
9.1.1地址及取地址运算210
9.1.2指针类型与指针运算211
9.2指针变量213
9.2.1指针变量的定义213
9.2.2指针变量的运算214
9.3指针与数组217
9.3.1指向数组元素的指针217
9.3.2用指针法引用数组元素218
9.3.3多维数组与指针220
9.4指针与字符串224
9.5指针与函数227
9.5.1指针变量作函数的参数227
9.5.2指向函数的指针变量232
9.5.3指针型函数235
9.6指针型数组237
9.7多级指针240
本章小结241
习题242
上机实训245
第10章结构体、共用体和枚举类型/247
10.1结构体类型247
10.1.1结构体类型的定义247
10.1.2结构体变量的说明与引用249
10.1.3位段253
10.2结构体数组255
10.2.1结构体数组的定义与初始化255
10.2.2应用举例257
10.3结构体与指针259
10.3.1结构体类型的指针变量259
10.3.2指向结构体数组的指针261
10.3.3结构体类型变量作函数的参数262
10.4动态数据结构与链表264
10.4.1链表的相关概念264
10.4.2动态内存分配函数265
10.4.3链表的建立与操作267
10.5共用体272
10.5.1共用体类型的定义与变量说明272
10.5.2共用体变量的引用273
10.6枚举类型275
10.7用typedef说明一种新类型名277
本章小结280
习题280
上机实训283
第11章文件操作/285
11.1C语言文件概述285
11.2文件的打开与关闭288
11.3文件的读写291
11.3.1字符的输入和输出291
11.3.2格式化输入和输出294
11.3.3字符串的输入和输出298
11.4随机文件的读写301
11.4.1文件的定位301
11.4.2fread函数与fwrite函数302
11.5出错检测函数305
11.5.1ferror()函数305
11.5.2clearerror()函数305
本章小结306
习题307
上机实训311
第12章课程设计/313
12.1课程设计的目的313
12.2课程设计的选题与实施过程314
12.2.1选题314
12.2.2实施过程314
12.3课程设计报告的内容315
12.4课程设计参考题目315
本章小结321
综合项目实训321
附录AC常用库函数/325
附录B全国计算机等级考试二级C语言考试大纲/333
附录C计算机二级C语言考试模拟题/336
模拟题参考答案350
附录D习题参考答案/351第1章习题解答351
第2章习题解答353
第3章习题解答354
第4章习题解答356
第5章习题解答359
第6章习题解答364
第7章习题解答367
第8章习题解答371
第9章习题解答372
第10章习题解答375
第11章习题解答378
参考文献/382