《普通高等教育"十一五"国家级规划教材:C/C++与数据结构(上册)(第4版)》由清华大学出版社出版。《普通高等教育"十一五"国家级规划教材:C/C++与数据结构(上册)(第4版)》特色有:1、综合连贯。把C、C++和C++标准类模板贯穿起来,一气呵成,系统地展示了从C到C++、再到C++标准类模板的必然发展。2、对比易懂。不仅学习,而且将C++与C进行对照,因为只有这样,才会使人感到心智在生长、在扩展。3、标准规范。实现了类模板库的string、vector和list及适配器,高屋建瓴。4、课件配套。《普通高等教育"十一五"国家级规划教材:C/C++与数据结构(上册)(第4版)》配有基于Authorware开发的多媒体助学助教软件,所有程序在课件中都有数据结构、算法、代码、运行及结果的跟踪演示,而且数据自由输入,为微课和MOOC的建设给予应有的技术支撑。
纵观短暂的计算机发展史,算法和数据结构这两个主要方面一直保持不变。发展演化的只是它们之间的关系,就是所谓的程序设计。——Stanley B.Lippman当一门学科的实证的知识材料积累到相当丰富的时候,就需要依据这些材料的内在联系把它们条理化、系统化,以便更有效地把握和运用这些知识。因此,这门学科就走进了逻辑思维(即理论思维)的领域。
每一个中学毕业生都学过几何学,即来自《几何原本》的几何学。它就是对人类四百多年的几何知识材料进行系统化的结果。它从几个公理出发,按照形式逻辑规则,推导出所有几何定理。这便是著名的数学公理化方法,也称为形式逻辑。这种方法是把学科的知识材料系统化的一种有效手段。
但是,某一学科的公理化方法只有在这个学科成熟的时候才会出现。如果一个学科在不断的发展中,例如,计算机程序语言,尽管有机器语言、汇编语言、C语言、C++语言、C#和Java,但每年还有几十种程序语言出现,对这种学科的知识材料进行系统化,就需要另一种逻辑——辩证逻辑,因为辩证逻辑是从事物的发展和变化中来观察事物。
辩证逻辑的出现主要依赖于自然科学和工业的强大而日益迅猛的发展,例如,细胞、能量转换和进化论的发现。这些发现使人们不仅能够说明自然界中各个领域内的过程之间的联系,而且总的说来也能够说明各个领域之间的联系。
辩证逻辑的核心是对立统一规律:一切事物都存在矛盾,矛盾的双方既对立又统一,从而推动着事物的发展。
程序语言的矛盾实质上是程序设计的矛盾,这个矛盾是数据结构和算法。数据结构是一组有组织的数据和对数据的基本操作,算法是用基本操作表示的对数据进行处理的有限步骤。而程序语言是表示某类数据结构的语言,因此数据结构和算法的矛盾,也是程序语言和算法的矛盾。
为什么说数据结构和算法是一对矛盾呢?因为没有不依赖数据结构的算法,也没有不支持算法的数据结构,这是它们的相互统一;数据结构是相对稳定的,就像程序语言是相对稳定的一样,而算法是越来越复杂的, 当算法复杂到一定程度的时候, 就要求数据结/C/C++与数据结构(第4版)(上册)前言/构继续发展,这是它们的相互对立。
因为C和C++属于核心的程序语言,所以本书把它们和数据结构作为研究对象,对它们的知识进行系统化。本书不从概念出发,而从算法的需要出发,一个问题解决了,新的问题又出现了,一个问题的链条,对应一个解答的链条;每一个问题都是程序设计中的问题,每一个问题的解决都产生新的程序,并产生新的概念;因此,从C到C++,再到C++标准模板库,其概念都是在针对具体问题而精心设计的程序链条中,沿着必然的发展过程,以一个扩展一个、一个转换一个的方式彼此联系着。在这个过程中,你感受最深的不是有一个高高在上的思想者的存在,他要你做什么,而是实实在在的你个人的存在,你知道要做什么,你可以清楚地描述出每一个问题是如何产生又如何解决的,而且这个过程不因人而异。
本书的脉络如下。
(1) 第1章机器语言模式。机器语言并不是本书要具体学习的内容,而仅仅是作为全书的逻辑起点,在这个起点上,计算机仅仅是可以逐条执行机器指令的工具。
为此,本章仅用很少的、虚拟的机器指令构成一台计算机,同时通过执行一个简单的求和程序,引入存储器、地址、寄存器、程序计数器等基本概念,它们属于计算机体系结构的内容。
例1.1和例1.2阐述了数据结构和算法在机器语言层面上的相互作用,在这个过程中产生的程序入口地址、子程序调用、断口地址、现场保护、栈等基本概念。
机器语言的局限性首先是不易阅读,克服这个局限性产生了汇编语言和汇编程序。
机器语言的另一个局限性是算法描述力不足,一个简单的算法就需要很多条机器指令,为了克服这个局限性,产生了高级语言。
(2) 第2章C语言模式。C语言主要用基本数据类型表示数据结构,基本操作的形式主要是运算符表达式。每一个运算符表达式都对应一个机器语言程序,这是数据结构和算法在不同层面上的相互转换。
(3) 第3章函数。函数是对运算符表达式的扩展,即对运算符表达式的局限性的克服。程序设计由此进入过程化。
(4) 第4章一维数组和指针。由处理一个对象扩展到处理一组对象,即数组,使对象的访问方式由基于对象名称的直接访问方式发展到基于对象指针的间接访问方式。
(5) 第5章C字符串。C字符串不仅是一个构造类型,也是C语言提供的过程化程序设计的范例。
(6) 第6章结构体、联合体和枚举。C语言提供了半类型自定义机制。所谓半类型,是指因为不能封装和不能深复制等原因,所以不能和基本类型一样使用的自定义类型。
(7) 第7章顺序表。顺序表是改进的数组。
(8) 第8章链表。顺序表是线性连续结构,链表是线性非连续结构,与顺序表相比,链表在插入和删除操作方面提高了效率。
(9) 第9章C的流与文件。每一个文件都对应一个指针,在标准文件的读写函数中,这个指针被隐藏了。把隐藏的指针显式地表示出来,通过类比,轻松地进入磁盘文件的读写操作。
(10) 第10章二维数组和指针。它是一维数组和指针的自然推广。
(11) 第11章从C到C++。顺序表暴露出C语言固有的局限性,由此产生了C++的基本概念,逐一克服了这些局限性。
(12) 第12章顺序表类。综合运用第11章的C++基本概念,把C顺序表转换为C++顺序表类。
(13) 第13章String类。把C字符串转换为C++的String类。
(14) 第14章Date类。把C结构体Date扩展为C++的Date类。
(15) 第15章非线性结构与递归。把递归与树形结构联系起来讲解,是本书的特色之一。
(16) 第16章继承和多态性。由C过程化程序设计进入C++面向对象程序设计。
(17) 第17章向量类模板。把顺序表类扩展为向量类模板。
(18) 第18章链表类模板和适配器。把C链表扩展为C++链表类模板,并以此为底层结构,生成链队列和链栈。
(19) 第19章C++综合设计实例。
(20) 第20章C++的流与文件。把C的文件读写函数转换为C++的文件读写函数。
(21) 第21章名字空间。
编者2015年9月
第1章机器语言模式1
1.1模拟机器指令集与程序设计举例1
1.2机器语言的局限性7
问题与练习8第2章C语言模式9
2.1基于基本类型的编程模式9
2.2基本数据类型19
2.2.1整型19
2.2.2实型21
2.2.3字符型22
2.3运算符和表达式25
2.3.1自增、自减运算符和表达式25
2.3.2复合赋值运算符和表达式26
2.3.3条件表达式和逗号表达式26
2.3.4关系运算符和逻辑运算符27
2.3.5运算符优先级29
2.4类型转换29
2.5程序流程控制结构30
2.5.1ifelse语句31
2.5.2switchcase语句32
2.5.3break语句和continue语句34
问题与练习35/C/C++与数据结构(第4版)(上册)目录/第3章函数38
3.1函数自定义与调用38
3.2函数声明与定义43
3.3函数与变量的存储类别44
3.3.1自动局部变量45
3.3.2静态局部变量48
3.3.3外部变量49
3.4函数应用设计举例51
3.4.1阶乘累加51
3.4.2求π的近似值52
3.4.3求最大公约数53
3.4.4判断质数54
3.4.5数制转换55
3.5模块化程序设计56
3.5.1全局外部函数57
3.5.2静态外部函数58
3.5.3全局外部变量59
3.5.4静态外部变量60
3.6编译预处理61
3.6.1无参宏指令61
3.6.2带参宏指令62
3.6.3条件编译指令64
3.6.4文件包含指令66
问题与练习68第4章一维数组和指针70
4.1指针和指针传递70
4.2一维数组和指针75
4.2.1一维数组75
4.2.2指向一维数组的指针78
4.2.3数组类型和数组首元素类型81
4.3const型指针83
4.4动态数组86
4.5数组和指针应用举例90
4.5.1Josephus问题90
4.5.2选择排序93
4.5.3起泡排序96
4.5.4划分数组元素98
4.5.5删除数组中的重复数据101
4.5.6筛法求质数102
4.5.7顺序搜索和二分搜索104
4.6索引和指针107
4.7指针和左值108
4.8函数指针108
问题与练习109第5章C字符串111
5.1字符串常量和字符串变量111
5.2字符串基本操作函数原型117
5.3字符串基本操作函数实现118
5.4字符串基本操作函数的补充122
5.4.1取子串123
5.4.2子串插入125
5.4.3子串删除127
5.4.4字符查找128
5.5模式匹配129
问题与练习131第6章结构体、联合体和枚举133
6.1结构体133
6.1.1结构体定义133
6.1.2结构体变量和typedef名字134
6.1.3结构体变量的初始化和赋初值135
6.1.4结构体数组136
6.1.5结构体的嵌套138
6.1.6结构体返回值和指针传递139
6.1.7数组和含有数组的结构体变量140
6.2联合体142
6.3枚举145
6.4结构体应用设计举例147
6.4.1模拟洗牌147
6.4.2Date结构体149
6.4.3三天打鱼,两天晒网153
问题与练习154第7章顺序表158
7.1数组的局限性158
7.2顺序表声明与实现159
7.2.1顺序表声明160
7.2.2顺序表实现164
7.3索引和指针169
7.4数据抽象和封装171
问题与练习171第8章链表173
8.1链表的结构分析173
8.2链表的声明和实现179
问题与练习185第9章C的流与文件186
9.1文件指针186
9.2文件打开与关闭187
9.3文件的读写191
9.3.1字符的读写 191
9.3.2字符串的读写193
9.3.3无格式读写194
9.3.4格式读写197
9.3.5文件的随机访问199
问题与练习201第10章二维数组和指针204
10.1二维数组和指针204
10.2二维数组和一维数组211
10.3马鞍点213
10.4指针数组和二级指针215
10.5指针数组与二维数组217
问题与练习219第11章从C到C++221
11.1C语言的固有局限性221
11.2内联函数224
11.3运算符重载和函数重载225
11.3.1运算符重载225
11.3.2函数重载227
11.4引用型230
11.4.1概念的由来230
11.4.2引用型及其应用233
11.5函数模板235
11.6提取符和插入符237
11.7默认参数239
11.8深入讨论——函数模板实例化中的问题241
问题与练习242第12章顺序表类243
12.1从C顺序表到C++顺序表类243
12.2new和delete操作符249
12.3需要增加、删除和修改的成员函数250
12.4顺序表类的声明和实现258
12.5类模板259
12.6基本类型赋值形式的扩展264
问题与练习265第13章String类266
13.1String类的声明266
13.2String类的实现269
13.2.1构造函数和析构函数269
13.2.2成员赋值运算符271
13.2.3成员转换272
13.2.4串连接274
13.2.5关系运算278
13.2.6求子串279
13.2.7子串插入280
13.2.8子串删除284
13.2.9下标运算符285
13.2.10字符查找285
13.2.11输入输出287
13.3模式匹配289
13.4String类的深入讨论291
13.4.1转换赋值运算符函数的替代291
13.4.2成员函数“类串+C串”的替代291
13.4.3explicit修饰符292
问题与练习293第14章Date类295
14.1Date类的声明295
14.2Date类的实现299
14.3静态数据成员和静态成员函数304
14.4封装的典型应用307
问题与练习309第15章非线性结构与递归310
15.1树形结构与递归310
15.2C++递归函数315
15.3汉诺塔问题316
15.4快速排序320
15.5八皇后321
问题与练习326第16章继承和多态性327
16.1构造函数的参数初始化表327
16.2继承330
16.3受保护成员332
16.4多态性和虚函数333
16.5虚析构函数337
16.6纯虚函数和抽象类338
问题与练习342第17章向量类模板344
17.1向量类模板的声明和实现344
17.2函数对象351
问题与练习354第18章链表类模板和适配器356
18.1链表类模板List356
18.2链表和链表类模板的代码对比368
18.3适配器371
18.3.1链栈371
18.3.2链队列372
18.3.3优先级链队列373
问题与练习374第19章C++综合设计实例375
19.1中缀表达式求值375
19.2事件驱动模拟380
问题与练习391第20章C++的流与文件392
20.1格式化输入输出393
20.1.1设置流的格式化标志393
20.1.2格式输出函数395
20.1.3操作算子396
20.2文件的读写399
20.2.1字符读写函数400
20.2.2字符串读写函数402
20.2.3无格式读写函数402
20.2.4格式读写404
20.2.5随机访问406
20.3文件错误处理407
问题与练习408第21章命名空间409
21.1命名空间的定义409
21.2using namespace语句410
21.3命名空间的成员412
21.4命名空间的别名414
问题与练习414附录A命名规则415附录B常用的ANSI C标准库函数416参考文献423