C++与数据结构.pdf

I 高等学校规划教材 C+与数据结构（第 4 版）高 飞 主编 白 霞 胡 进 吴 浩 聂 青 副主编 Publishing House of Electronics Industry 北京BEIJING II 内 容 简 介 本书是国家级（网络教育）精品课程的教学成果，也是北京市高等教育精品教材，根据教育部高等学校大学计算机课程教学指导委员会大学计算机基础课程教学基本要求中有关理工类专业的计算机基础课程教学要求组织编写而成，内容由浅入深，案例丰富，通俗易懂，实用性强。本书在介绍了 C+语言的程序设计方法的基础上，采用面向对象的思想和抽象数据类型的概念，用 C+语言有效地组织和描述了线性表、堆栈、队列、树和图等各种典型的数据结构和相关类的实现，并介绍了每一种数据结构的不同存储方法、典型操作及其应用。全书共 11 章，包括数据结构的基本概念，数组与指针，函数，C+编程基础，继承和多态，模板和 STL，线性表，堆栈与队列，树与二叉树，图，查找与散列结构，排序等。本书各章配有习题和实验训练题，方便实践教学，并为任课教师提供了电子课件和示例源代码。本书可作为高等院校电子信息类以及其他相关专业本科生教材和教学参考书，也可供从事程序设计的工程人员参考使用。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 C+与数据结构/高飞主编.4 版.北京：电子工业出版社，2018.2 ISBN 9787121315794.C.高.C 语言程序设计高等学校教材数据结构高等学校教材.TP312.8TP311.12 中国版本图书馆 CIP 数据核字（2017）第 116800 号 策划编辑：章海涛 责任编辑：裴 杰 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编 100036 开 本：7871092 1/16 印张：22.75 字数：582.4 千字 版 次：2006 年 9 月第 1 版 2018 年 2 月第 4 版 印 次：2018 年 2 月第 1 次印刷 定 价：52.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888，88258888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。本书咨询联系方式：192910558（QQ 群）。III 前 言 本书是北京市高等教育精品教材北京市高等教育精品教材，是北京市精品课程和国家级精品课程北京市精品课程和国家级精品课程“数据结构与算法设计”的配套教材配套教材。编写者是国家级优秀教学团队国家级优秀教学团队和北京市优秀教学团队“计算机公共课教学团队”北京市优秀教学团队“计算机公共课教学团队”的主要成员。本书的编写以教育部高等学校大学计算机课程教学指导委员会大学计算机基础课程教学基本要求 中有关理工类专业的计算机基础课程教学要求为指导思想，借鉴了教育部大学计算机课程改革项目关于培养计算思维的相关成果，结合具体教学改革实践，总结了国家级精品课程和北京市精品课程“数据结构与算法设计”的建设经验，坚持以培养学生解决实践问题的能力为特色，以适应信息时代的人才培养模式。1.本书的写作特点 本书是C+与数据结构（第 3 版）的修订版，其写作在延续第 3 版的特点的基础上，根据实际教学的要求，做了相应的改进。数据结构是计算机算法的设计基础，在计算机科学中占有非常重要的地位。深入研究数据结构对构造完美算法结构和设计具有重要的作用。程序设计语言是实现算法的载体，语言只有满足算法实现的需求，才能被认识和掌握，数据结构只有通过程序语言才能在应用中发挥作用。因此，本书力求以算法为中介，以实现读者学习程序设计语言和学习数据结构的共同进步。本书在介绍了 C+程序设计方法的基础上，采用 C+程序设计语言描述算法。C+是一种既支持面向过程程序设计，又支持面向对象程序设计的混合型语言，它独特的面向对象特征，可以为面向对象技术提供全面支持，是描述算法的一种较为理想的语言。采用面向对象程序设计语言描述施加于数据结构之上的算法，不仅有利于与面向对象技术相结合，也为上机实践提高高级语言程序设计水平提供了方便。本书共包括 11 章。第 1 章是对数据结构和面向程序设计方法的概述。第 2 章第 5 章是C+语言程序设计基础，主要内容是 C+编程基础，精炼地介绍了数组与指针、函数、C+类及其对象的封装性、引用、友元和重载、继承与派生、多态性与虚函数、模板以及 STL 的相关内容。第 6 章第 11 章重点介绍典型的数据结构，主要内容包括线性表、堆栈与队列、树与二叉树、图、查找与散列结构、排序。全书每章都配有习题以及相应的程序例题和实验训练题。本次改版修订，针对读者特点和计算机教学的要求，加强了对编程基础的介绍。在介绍数据结构的同时，在合适的时机引入相关的编程技术的基本原理、原则、实用技巧，以期培养读者良好的编程风格、编程思路，为今后继续深入学习和应用高级编程技巧打下基础。2.本书的编排特点 1）本书每章安排有习题和实验训练题习题和实验训练题，可方便实践教学。2）书中重要内容采用黑体标注。3）本书强调可读性强调可读性。书中程序全部采用统一的设计风格。例如，类名和变量名的定义做到“望名知义”；采用缩进格式组织程序；对程序中的语句尽可能多地使用注释。4）本书包含大量的程序示例，给出了运行结果。凡是程序开头带有程序名编号的程序，都是可以直接在计算机上编译运行的程序。IV3.教学支持 本书的电子教案可以在讲课时用多媒体投影演示。教师不仅可以使用本教案，还可以方便地修改和重新组织其中的内容以适应自己的教学需要。使用本教案可以减少教师备课时编写教案的工作量，从而提高教学效果和效率。本书为教师免费提供电子课件和程序示例源代码。需要的教师可以直接登录华信教育资源网 http:/ 注册后免费下载。本书由高飞设计总体架构。胡进编写第 1 章和第 6 章，并负责各章节中编程风格、代码改进等；第 25 章由白霞编写；第 7 章和第 8 章由高飞编写；第 9 章由聂青编写；第 10 章和第 11 章由吴浩编写。全书由高飞、吴浩统稿、定稿。感谢北京理工大学“计算机公共课教学团队”中从事教学工作多年的同仁对本书的建议和帮助。电子工业出版社对本书的编写提出了宝贵的意见，在此表示衷心的感谢。由于计算机算法和程序设计技术发展迅速，编者水平有限，书中的疏漏与不足在所难免，敬请广大读者和同仁不吝赐教，拔冗指正。感谢大家选用本书，欢迎大家对本书提出意见和建议，编者 E-mail：。编 者 于北京理工大学 V目 录 第 1 章 数据结构的基本概念 1 1.1 数据结构的概念和术语 1 1.2 抽象数据类型 3 1.2.1 数据类型 3 1.2.2 数据抽象与抽象数据类型 4 1.3 算法和算法分析 5 1.3.1 算法 5 1.3.2 算法设计的要求 5 1.3.3 算法效率的度量 6 1.4 面向对象概述 8 1.4.1 面向对象的思想 9 1.4.2 面向对象程序设计 9 1.4.3 面向对象的语言 9 1.4.4 面向对象的基本概念 10 1.4.5 面向对象的基本特性 11 1.5 本章小结 13 习题 1 13 第 2 章 C+初步知识 14 2.1 C+语言 14 2.2 数组 14 2.2.1 一维数组 15 2.2.2 二维数组 17 2.2.3 字符数组和字符串 20 2.3 指针 24 2.3.1 指针的概念 24 2.3.2 指针的定义 24 2.3.3 指针的运算 25 2.4 指针和数组 27 2.4.1 指针与数组名 27 2.4.2 指向数组的指针 28 2.4.3 存储指针的数组 31 2.4.4 动态存储 32 2.5 结构 34 2.5.1 结构类型的定义 34 2.5.2 结构变量的说明 35 2.5.3 结构成员的引用 36 2.5.4 结构数组和结构指针 37 2.6 函数 39 2.6.1 函数的声明、定义和调用 40 2.6.2 函数的参数传递 41 2.6.3 带默认参数的函数 42 2.6.4 内置函数 43 2.6.5 函数的重载 44 2.7 本章小结 45 习题 2 45 实验训练题 2 45 第 3 章 C+类及其对象的封装性 48 3.1 类的声明和对象的定义 48 3.1.1 声明类类型 48 3.1.2 定义对象的方法 50 3.1.3 对象成员的引用 51 3.2 类的成员函数 52 3.2.1 成员函数的访问属性 52 3.2.2 在类外定义成员函数 52 3.2.3 内置成员函数 53 3.2.4 成员函数的存储方式 54 3.3 构造函数和析构函数 55 3.3.1 对象的初始化 55 3.3.2 构造函数的作用 55 3.3.3 带参数的构造函数 57 3.3.4 构造函数的重载 58 3.3.5 拷贝构造函数 58 3.3.6 析构函数 59 3.4 相关特性 61 3.4.1 引用 61 3.4.2 友元 67 3.4.3 运算符重载 70 3.5 本章小结 77 VI习题 3 77 实验训练题 3 78 第 4 章 继承性和多态性 81 4.1 继承与派生的概念 81 4.1.1 派生类的声明与构成 81 4.1.2 派生类成员的访问 83 4.2 派生类的构造函数和析构函数 87 4.2.1 简单的派生类的构造函数 87 4.2.2 有子对象的派生类的构造函数 88 4.2.3 多级派生时的构造函数 90 4.2.4 派生类的析构函数 91 4.3 多继承 92 4.3.1 多继承的声明与使用 92 4.3.2 多继承引起的二义性问题 94 4.3.3 虚基类的概念与使用 96 4.4 多态性与虚函数 99 4.4.1 多态的概念 99 4.4.2 虚函数的定义与使用 99 4.4.3 虚析构函数 103 4.4.4 纯虚函数与抽象类 104 4.5 本章小结 107 习题 4 107 实验训练题 4 107 第 5 章 模板与标准模板库 112 5.1 模板 112 5.1.1 模板的概念 112 5.1.2 函数模板 112 5.1.3 类模板 117 5.2 标准模板库 120 5.3 序列式容器 121 5.3.1 vector 容器 121 5.3.2 使用迭代器 123 5.3.3 list 容器 124 5.4 关联式容器 125 5.4.1 pair 类型 126 5.4.2 map 容器 127 5.4.3 set 容器 128 5.5 本章小结 130 习题 5 131 实验训练题 5 131 第 6 章 线性表 133 6.1 线性表的定义 133 6.1.1 线性表的逻辑结构 133 6.1.2 线性表的抽象类定义 134 6.2 线性表的顺序表示和实现 135 6.2.1 线性表的顺序表示 135 6.2.2 顺序表类的定义 135 6.2.3 顺序表类的实现 136 6.3 线性表的链式表示和实现 140 6.3.1 线性表的链式表示 140 6.3.2 抽象链表类的定义 140 6.3.3 抽象链表类各成员函数的实现 142 6.4 单链表 143 6.4.1 单链表的定义 143 6.4.2 单链表类的定义 144 6.4.3 单链表的常用成员函数的实现 144 6.4.4 单链表举例一元多项式加法 147 6.5 循环链表 150 6.5.1 循环链表的定义 150 6.5.2 循环链表类的定义 150 6.5.3 循环链表常用函数的实现 151 6.5.4 循环链表举例约瑟夫问题 155 6.6 双向链表 155 6.6.1 双向链表的定义 155 6.6.2 双向链表类的定义 156 6.6.3 双向链表的常用成员函数的实现 157 6.7 本章小结 161 习题 6 161 实验训练题 6 162 第 7 章 堆栈、队列和递归 169 7.1 堆栈的概念及其运算 169 7.2 抽象堆栈