数据结构教程用C++实现的方法 (2010 年度畅销榜NO.48150 )

这是一部关于数据结构(用C++实现的方法)的实用教科书。内容新颖全面，讲解深入细致，编写时，特别注重根据不同的教学对象定位不同的培养目标，各章、节的重难点，主次内容都做了恰当合理的安排。\r\n\r\n 全书由10章构成，其主要内容包括：数据结构课程的背景及有关的概念和术语、C++面向对象程序设计要点、线性表、栈和队列、数组、广义表和串、树和二叉树、图、集合和查找、各种常用的排序算法、文件的物理结构及其支持空间数据的索引文件——R树。此外，本书各章均配有一定的算法实例和丰富的习题供读者练习，巩固所学知识。\r\n\r\n 作者从事一线的教学二十余年，积累了丰富的教学经验，本书在整体结构安排、内容取舍以及整书的编写过程中，都充分考虑了教与学的特点，以及所面对的特定读者的具体需要。在内容上既注重了理论体系的完整性，又兼具系统性和先进性。结构清晰，概念准确，文字叙述简洁明了、可读性强，既便于教师课堂讲授，又便于自学者阅读。通过阅读本书，可对数据结构有全面的了解，并为进一步深入学习和研究计算机科学技术奠定基础。\r\n\r\n 本书可作为普通高校、高等职业学校计算机科学与技术专业本、专科学生的教材和教学参考书，也可以作为工程技术人员的自学教材或指导书。\r\n
\r\n

第1章 绪论 \r\n\r\n 1. 1 数据结构课程内容及其意义 \r\n\r\n 1. 2 基本概念及术语 \r\n\r\n 1. 3 抽象数据类型及面向对象概念 \r\n\r\n 1. 4 复型数据类型 \r\n\r\n 1. 5 程序设计方法及语言 \r\n\r\n 1. 6 算法与算法分析 \r\n\r\n 1. 7 递归函数 \r\n\r\n 习题一 \r\n\r\n 第2章 C++面向对象程序设计要点 \r\n\r\n 2. 1 C十十的函数 \r\n\r\n 2. 1. 1 函数类型 \r\n\r\n 2. 1. 2 函数名的重载 \r\n\r\n 2. 1. 3 函数参数 \r\n\r\n 2. 1. 4 成员函数的返回值 \r\n\r\n 2. 2 输入和输出 \r\n\r\n 2. 2. 1 键盘屏幕输入输出方式 \r\n\r\n 2. 2. 2 文件输入输出 \r\n\r\n 2. 3 C十十的类 \r\n\r\n 2. 3. 1 构造函数和析构函数 \r\n\r\n 2. 3. 2 操作符重载 \r\n\r\n 2. 3. 3 友元 \r\n\r\n 2. 3. 4 分辨符 \r\n\r\n 2. 3. 5 内联函双 \r\n\r\n 2. 3. 6 默认值 \r\n\r\n 2. 3. 7 多态性和虚函数 \r\n\r\n 2. 3. 8 纯虚函数和抽象类 \r\n\r\n 2. 3. 9 派生类继承方式 \r\n\r\n 2. 3. 10 结构体 \r\n\r\n 2. 3. 11 对象 \r\n\r\n 2. 4 抽象类型和模板 \r\n\r\n 2. 4. 1 抽象类型 \r\n\r\n 2. 4. 2 模板 \r\n\r\n 习题一 \r\n\r\n 第3章 线性表 \r\n\r\n 3. 1 线性表的抽象数据类型 \r\n\r\n 3. 2 线性表NJ吸序表示与实现 \r\n\r\n 3. 3 线性表的链式表示与实现 \r\n\r\n 3. 3. 1 单链表(Singly Linked List) \r\n\r\n 3. 3. 2 循环链表 \r\n\r\n 3. 3. 3 双向链表 \r\n\r\n 3. 4 一元多项式 \r\n\r\n 习题三 \r\n\r\n 第4章 栈和队列 \r\n\r\n 4. 1 栈 \r\n\r\n 4. 1. 1 栈的抽象数据类型 \r\n\r\n 4. 1. 2 顺序栈的表示与实现 \r\n\r\n 4. 1. 3 链式栈的表示与实现 \r\n\r\n 4. 1. 4 栈的应用--表达式计算 \r\n\r\n 4. 2 队列 \r\n\r\n 4. 2. 1 队列的抽象数据类型 \r\n\r\n 4. 2. 2 顺序队列的表示与实现 \r\n\r\n 4. 2. 3 链式队列的表示与实现 \r\n\r\n 4. 2. 4 队列的应用 \r\n\r\n 4. 2. 5 优先级队列(Priority Queue) \r\n\r\n 习题四 \r\n\r\n 第5章 数组. 广义表和串 \r\n\r\n 5. 1 数组 \r\n\r\n 5. 1. 1 一维数组 \r\n\r\n 5. 1. 2 二维数组 \r\n\r\n 5. 2 特殊矩阵的压缩存储 \r\n\r\n 5. 2. 1 对称矩阵 \r\n\r\n 5. 2. 2 对角矩阵 \r\n\r\n 5. 3 稀疏矩阵的压缩存储 \r\n\r\n 5. 3. 1 稀疏矩阵的三元组 \r\n\r\n 5. 3. 2 三元细顺序表表示 \r\n\r\n 5. 3. 3 三元组十字链表表示 \r\n\r\n 5. 4 广义表 \r\n\r\n 5. 4. 1 广义表的概念 \r\n\r\n 5. 4. 2 广义表的抽象数据类型 \r\n\r\n 5. 4. 3 广义表的的存储结构 \r\n\r\n 5. 5 字符串 \r\n\r\n 5. 5. 1 字符串抽象数据类型定义 \r\n\r\n 5. 5. 2 字符串的存储结构 \r\n\r\n 习题五 \r\n\r\n 第6章 树和二叉树 \r\n\r\n 6. 1 树 \r\n\r\n 6. 1. 1 树的定义和术语 \r\n\r\n 6. 1. 2 树的表示形式 \r\n\r\n 6. 1. 3 树的抽象数据类型 \r\n\r\n 6. 2 二叉树 \r\n\r\n 6. 2. 1 二叉树的定义 \r\n\r\n 6. 2. 2 二叉树阶性质 \r\n\r\n 6. 2. 3 二叉树的抽象数据类型 \r\n\r\n 6. 2. 4 二叉树的存储结构 \r\n\r\n 6. 3 三叉树的遍历 \r\n\r\n 6. 3. 1 先序遍历 \r\n\r\n 6. 3. 2 中序遍历 \r\n\r\n 6. 3. 3 后序遍历 \r\n\r\n 6. 3. 4 层次遍历 \r\n\r\n 6. 4 线索二叉树 \r\n\r\n 6. 4. 1 中序线索化二叉树 \r\n\r\n 6. 5 树和森林 \r\n\r\n 6. 5. 1 森林与二叉树的转换 \r\n\r\n 6. 5. 2 树和森林遍历 \r\n\r\n 6. 6 哈夫曼树和应用 \r\n\r\n 6. 6. 1 路径长度和哈夫曼树 \r\n\r\n 6. 6. 2 哈夫曼编码 \r\n\r\n 6. 6. 3 算法实现 \r\n\r\n 习题六 \r\n\r\n 第7章 图 \r\n\r\n 7. 1 图的基本概念及抽象数据类型 \r\n\r\n 7. 1. 1 图的基本概念 \r\n\r\n 7. 1. 2 图的抽象数据类型 \r\n\r\n 7. 2 图的存储结构 \r\n\r\n 7. 2. 1 邻接矩阵 \r\n\r\n 7. 2. 2 邻接表 \r\n\r\n 7. 2. 3 邻接多重表 \r\n\r\n 7. 2. 4 十字链表 \r\n\r\n 7. 3 图的遍历与连通性 \r\n\r\n 7. 3. 1 深度优先搜索 \r\n\r\n 7. 3. 2 广度优先搜索 \r\n\r\n 7. 3. 3 连通分量 \r\n\r\n 7. 4 最小生成树 \r\n\r\n 7. 4. 1 克鲁斯卡尔(Kryskal)算法 \r\n\r\n 7. 4. 2 普里姆(Prim)算法 \r\n\r\n 7. 5 最短路径 \r\n\r\n 7. 5. 1 从某源点到其余各定点的最短路径 \r\n\r\n 7. 5. 2 每对顶点之间的最短路径 \r\n\r\n 7. 6 拓扑排序与关键路径 \r\n\r\n 7. 6. 1 拓扑排序 \r\n\r\n 7. 6. 2 关键路径 \r\n\r\n 习题七 \r\n\r\n 第8章 集合和查找 \r\n\r\n 8. 1 集合的抽象数据类型 \r\n\r\n 8. 2 集合的位向量表示及查找 \r\n\r\n 8. 3 集合的顺序表示及查找 \r\n\r\n 8. 3. 1 无用顺序表查找 \r\n\r\n 8. 3. 2 有序顺序表查找 \r\n\r\n 8. 4 集合的树结构表示及查找 \r\n\r\n 8. 4. 1 二叉排序树 \r\n\r\n 8. 4. 2 平衡二叉树 \r\n\r\n 8. 5 哈希方法 \r\n\r\n 8. 5. 1 哈希函数的构造 \r\n\r\n 8. 5. 2 冲突处理 \r\n\r\n 8. 5. 3 基本集合操作实现 \r\n\r\n 习题八 \r\n\r\n 第9章 排序 \r\n\r\n 9. 1 排序的基本概念 \r\n\r\n 9. 2 插入排序 \r\n\r\n 9. 2. 1 直接插入排序 \r\n\r\n 9. 2. 2 折半插入排序 \r\n\r\n 9. 2. 3 链表插入排序 \r\n\r\n 9. 2. 4 希尔排序 \r\n\r\n 9. 3 交换排序 \r\n\r\n 9. 3. 1 冒泡排序 \r\n\r\n 9. 3. 2 快速排序 \r\n\r\n 9. 4 选择排序 \r\n\r\n 9. 4. 1 直接选择排序 \r\n\r\n 9. 4. 2 堆排序 \r\n\r\n 9. 5 归并排序 \r\n\r\n 9. 6 基数排序 \r\n\r\n 9. 6. 1 多关键字排序 \r\n\r\n 9. 6. 2 链式基数排序 \r\n\r\n 习题九 \r\n\r\n 第10章 文件 \r\n\r\n 10. 1 基本术语与概念 \r\n\r\n 10. 2 顺序文件 \r\n\r\n 10. 3 直接存取文件(Hash文件) \r\n\r\n 10. 4 索引文件 \r\n\r\n 10. 4. 1 B树 \r\n\r\n 10. 4. 2 B树 \r\n\r\n 10. 4. 3 R树 \r\n\r\n 10. 5 多关键字文件 \r\n\r\n 10. 5. 1 倒排文件 \r\n\r\n 10. 5. 2 多重表文件 \r\n\r\n 习题十 \r\n\r\n 参考文献 \r\n
\r\n

近年来计算机科学与技术的发展突飞猛进, 其应用范围之广, 对国民经济影响之大前所未有, 特别是计算机网络. 电子商务. 多媒体技术等发展, 正在彻底改变人类的工作方式与生活方式, 同时也彻底改变了传统产业与传统的工作模式. 目前, 计算机科学与技术是高新技术的主要标志, 是先进生产力的重要支柱, 因此, 发展计算机事业是摆在我们面前的重要任务. 有鉴于此, 我们特组织编辑了以大学本科学生为对象的《计算机科学与技术教材》丛书, 为我国信息化培养人才作一份贡献.

当前, 在我国计算机教学及教材建设中普遍存在着一些弊病与不足, 主要有如下几种：1. 在计算机教材特别是基础性教材中严重存在知识陈旧. 落后, 跟不上计算机科学与技术发展的步伐. 由于计算机技术的飞速发展, 内容更新要求极快, 一般三五年就需作重大调整而一二年需作必要调整, 而现有教材大都不能适应此种变化速度, 这种现象在基础性教材中尤为突出.

2. 现有教材很多以国外教材为蓝本, 存在着脱离我国具体应用实际的弊病. 如何根据我国国情并参考国外先进技术编写教材是当务之急.

3. 现有的教材大都适应面窄, 多数仅适应计算机本科专业而尤其仅适应少数重点院校与重要院校. 而目前, 由于计算机教育发展迅速, 各种与计算机相近与相关的专业蓬勃发展, 在计算机本科专业中也出现了不同层次的要求, 特别是以应用型人才为主的培养要求.

因此, 迫切需要有一套适应面较广的基础性教材以满足多种层次的要求.

根据以上分析, 本丛书编写原则是

1. 适应计算机科学与技术飞跃发展的需要, 本教材丛书具有先进性与时代特性, 并且每隔一二年作一次小的调整, 每隔四五年重新修订出版.

2. 本教材丛书具有适应面广, 基础性强的特点, 能满足多种层次. 多种类型的计算机专业本科学生的需要, 特别是满足计算机应用型人才培养的需要.

3. 本教材丛书具有密切结合我国应用实际. 反映我国计算机事业发展需求的基本特点, 并且能在实际应用中发挥作用.

4. 教材是有别于一般书籍的一种特殊读物, 它要求基本概念清楚, 基本理论扎实, 知识量大与实际应用联系紧密等特点, 它还要求教材的内容逻辑性强, 可读性好, 深入浅出, 并附有习题与参考资料等内容, 本教材丛书将突出体现这些特点使其适合于教材需要.

5. 本教材丛书选题是根据我国目前实际并参考国际最新动态而制订的. 本教材丛书第一批8本都是具有普遍性与基础性的教材, 在不久我们将分别推出第二批. 第三批教材满足不同的需要.

6. 本教材丛书聘请有深厚理论基础与应用实践经验且长期在教学. 科研第一线工作的高校教授编写, 特别是有专长的中. 青年教授是本丛书教材编写的主要力量.

我们感谢丛书编委会各位委员为本丛书出版所作出的贡献, 我们也感谢北京希望电子出版社为本丛书的立题. 编审所作出的努力, 最后我们感谢丛书的各位作者为本丛书编写发行与发展所作出的创造性的和富有成效的工作.

我们还期待广大读者为本丛书提出宝贵意见与建议, 我们将通过修订, 不断努力把本丛书办得更好.

计算机科学与技术教材编委会

2002年3月于南京大学

数据结构是计算机专业一门重要的核心基础课, 其内容主要是研究和解决非数值计算的问题, 讨论如何合理地组织. 存储和处理数据的方法与技术. 计算机领域内只要涉及到程序的地方, 均要用到数据结构的知识：许多课程, 例如操作系统. 编译原理. 数据库和人工智能等也均要用到数据结构的知识.

目前已出现了许多有价值的数据结构教材, 早期的描述语言主要是采用抽象语言. PASCAL语言. 类PASCAL语言或PL/1语言. 但是, 随着C语言在国内外的广泛普及, 不仅系统程序员而且越来越多的应用程序员也采用C语言作为编程工具. 在20世纪80年代末期, 国外出现了用C语言作为描述语言的数据结构教材, 立刻引起注意. 众所周知, C语言是入门容易, 真正掌握其精髓则较难. 为跟上教材更新的步伐, 保证学以致用, 更好地掌握C语言以及用C语言描述. 实现各种数据结构与算法, 我们于1992年12月编写了以C语言为描述语言的数据结构教材. 从1993年起, 我校计算机专业的学生就使用以C语言为描述语言的数据结构教材, 效果很好.

随着面向对象技术的不断成熟, C十十已被广泛使用, 事实上近年来在应用程序领域使用范围已超过C语言. 不少学校已把C十十作为第一门程序设计课程的语言, 也出现了一些用C十十为描述语言的数据结构教材. 虽然我校计算机专业的数据结构教材采用的C为描述语言, 但在作业, 尤其是上机实验和课程设计中, 相当比例的学生使用C十十作为编程语言.

为保证在新形势下的学以致用, 我们着手编写了这本教材, 希望能对该课程的教材起到一定的促进作用.

为了保证仅具有C语言基础的读者能够顺利使用该教材, 我们把C十十的基本内容作为一章介绍. 但如果具有了C十十程序设计语言的知识, 则可略过此章.

本书详细介绍了各种基本的数据结构：线性表. 栈. 队列. 串. 数组. 广义表. 树和图, 以及查找. 排序和文件结构等. 全书共分为10章. 第1章介绍了数据结构课程的背景及有关的概念和术语, 并讨论了抽象数据类型. 复合数据类型和递归函数等内容. 第2章简要介绍了C十十的基本知识. 第3章至第7章分别介绍了上述的各种数据结构. 第8章介绍了各种基本的查找方法, 同时, 还介绍了一种对算法进行简单时间复杂性分析的方法. 第9章讨论了各种常用的排序算法. 第10章讨论了文件的物理结构, 并介绍了支持空间数据的索引文件——R树. 在各章中均配有一定的算法实例, 借以训练灵活使用所学数据结构的能力.

本书的主要特色是没有简单地把一些算法从其他描述语言移植到C十十, 而是根据C十十的特点设计与实现了各种数据结构的存储结构和算法. 因此, 本教材有助于读者进一步掌握C十十的编程思想. 方法和技术.

本书可作为计算机专业的本科生教材, 学时安排大约为70一80学时. 数据结构是一门实践性很强的课程, 故每章均附有一定量的习题, 只有通过大量的编程及上机实习才能更好地熟练掌握该课程的内容. 除此之外, 还可以通过该课程的“课程设计”(大约一周时间), 把本教材内容尽可能多地溶进一个大的上机实习题中, 以加深. 巩固在课堂上所学的内容.

根据我们的教学经验, 在该课程的教学中必须要求学生养成良好的编程风格, 尽量多加注释语句, 最好在具体编程前先给出其算法思想. 学习本书前, 读者应具有C语言或C十十的基础, 若有离散数学和概率论的知识则更好.

本书第1, 8, 10章由秦小麟编写, 第2, 4, 6, 9章由叶延风编写, 第3, 5, 7章由高航编写. 全书由秦小麟统稿, 李立新教授审阅了本教材的初稿, 并提出了许多宝贵的意见. 在编写该教材过程中, 赵宝献做了大量的排版与输入工作, 在此表示衷心的感谢.

由于编者水平有限, 书中难免有错误及不妥之处, 恳请读者与同行批评指正.

编 者

2002年8月于南京航空航天大学