| 词条 | 数据结构实用教程（C++版） |
| 释义 | 简介本书为国家级优秀教学团队教学成果。根据教育部高等学校计算机科学与技术教学指导委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》编写，首先介绍了数据结构的核心基础知识——数据、数据类型、数据结构等基本概念和算法、算法的性能度量等知识，然后集中讨论了四种基本的数据结构——集合、线性表、树和图，同时介绍了栈、队列、串、数组以及广义表等数据结构，最后介绍了排序和查找的几种基础算法及实现（用C 语言）。强调数据结构的工程应用，以模板的形式给出各种不同数据对象应用数据结构的多个实例，从而实现数据结构与工程应用的有机结合。本书可以作为高等院校计算机及相关专业学生的教材，也可供培训机构及自学者参考。 图书信息书名：数据结构实用教程（C++版） 主编： 万健 副主编：王立波 赵葆华 吴志芳 策划编辑：章海涛 责任编辑：章海涛 特约编辑：曹剑锋 印刷：北京市顺义兴华印刷厂 装订：三河市双峰印刷装订有限公司 出版发行：电子工业出版社 ISBN号： 9787121110764 出版日期： 2011-1-1 字数：446千字 定价：￥32.00元 页码：280 开本：16 目录第1章 绪 论1.1 数据与数据类型 1 1.1.1 数据 1 1.1.2 数据的计算机表示与数据类型 2 1.1.3 抽象数据类型 5 1.2 数据结构 7 1.3 算法与算法分析 10 1.3.1 算法 10 1.3.2 算法的性能分析与度量 11 1.3.3 算法的时间复杂度 11 1.3.4 算法的空间复杂度 14 习题1 14 第2章 线性表2.1 线性表的类型定义及结构特征 15 2.2 线性表类型的实现——顺序映像 17 2.3 线性表类型的实现——链式存储映像 26 2.3.1 单链表 26 2.3.2 其他形式的链表 35 2.4 线性表的应用 37 2.4.1 两个有序表的合并 38 2.4.2 集合运算 40 2.4.3 一元多项式的表示和相加 42 习题2 47 第3章 其他线性结构3.1 栈 48 3.1.1 栈的定义和基本操作 48 3.1.2 栈的存储结构及操作实现 49 3.1.3 栈的应用举例 55 3.2 队列 68 3.2.1 队列的定义和基本操作 68 3.2.2 队列的存储结构及操作实现 70 3.2.3 队列应用举例 77 3.3 串 83 3.3.1 串的基本概念和基本操作 83 3.3.2 串的存储结构 85 3.4 数组 87 3.4.1 数组的定义和基本操作 87 3.4.2 数组的存储表示 89 3.4.3 特殊矩阵的压缩存储 90 3.4.4 稀疏矩阵的压缩存储 92 3.5 广义表 96 3.5.1 广义表的基本概念和基本操作 97 3.5.2 广义表的存储结构 99 习题3 101 第4章 树型结构4.1 树、森林的定义及基本术语 104 4.2 二叉树 105 4.2.1 二叉树的结构定义 105 4.2.2 几种特殊形态的二叉树 106 4.2.3 二叉树的性质 107 4.2.4 二叉树的存储结构 108 4.2.5 二叉链表类的定义 110 4.2.6 二叉树的递归遍历 114 4.2.7 几个二叉树基本操作的例子 116 4.2.8 二叉树的非递归遍历 118 4.2.9 其他部分成员函数的实现 121 4.2.10 主函数（演示二叉链表类部分基本操作的执行结果） 123 4.2.11 线索二叉树 126 4.3 树与森林的再讨论 129 4.3.1 树的存储结构 129 4.3.2 树和森林的遍历 132 4.4 树型结构的应用 134 4.4.1 算术表达式求值 134 4.4.2 树与等价问题 139 4.4.3 赫夫曼树及赫夫曼编码 145 习题4 154 第5章 图5.1 图的定义和术语 156 5.2 图的存储结构 160 5.2.1 邻接矩阵表示法 160 5.2.2 邻接表表示法 162 5.2.3 十字链表表示法 164 5.2.4 邻接多重表表示法 165 5.3 图的基本操作 167 5.3.1 类的定义与实现 167 5.3.2 图的遍历 175 5.3.3 图的连通性 181 5.4 最小生成树 182 5.4.1 Prim算法 183 5.4.2 Kruskal算法 186 5.5 拓扑排序和关键路径 187 5.5.1 有向无环图 187 5.5.2 拓扑排序 188 5.5.3 关键路径 190 5.6 最短路径 194 5.6.1 单源最短路径 194 5.6.2 每对顶点间的最短路径 197 习题5 199 第6章 查 找6.1 查找表的定义 201 6.2 静态查找表 202 6.2.1 顺序查找 202 6.2.2 折半查找 203 6.2.3 分块查找 206 6.3 动态查找表 207 6.3.1 二叉排序树 207 6.3.2 平衡二叉排序树 213 6.3.3 B?树和B+树 221 6.4 哈希查找 226 6.4.1 哈希表的定义 226 6.4.2 哈希函数的构造方法 227 6.4.3 处理冲突的办法 229 6.4.4 哈希表的查找及分析 231 6.4.5 哈希表的构建与查找算法 233 习题6 236 第7章 排 序7.1 插入类排序 237 7.1.1 直接插入排序 238 7.1.2 折半插入排序 239 7.1.3 2-路插入排序 240 7.1.4 希尔排序 241 7.2 分划类排序 242 7.2.1 冒泡排序 242 7.2.2 快速排序 243 7.3 选择类排序 247 7.3.1 简单选择排序 247 7.3.2 树形选择排序 248 7.3.3 堆排序 249 7.4 归并类排序 252 7.5 基数排序 254 7.5.1 多关键字的排序 254 7.5.2 基数排序 254 7.6 内部排序的比较 259 7.7 外部排序 262 7.7.1 外部存储设备 262 7.7.2 外部排序的方法 262 7.7.3 败者树 263 习题7 264 附录A 266参考文献 269前言数据结构的概念最早由C.A.R.Hoare于1966年提出。在他的经典论文《数据结构笔记》中，他首次系统地论述了一组数据结构的构造、表示和操作等问题。1973年，D.E.Knuth在《计算机程序设计技巧》第一卷中给出了关于“信息结构”的系统论述。1976年，N.Wirth用“算法+数据结构=程序”这个公式表达了算法与数据结构的联系和它们在程序设计中的地位。从此确立了数据结构在计算机相关专业中的核心基础课程地位。 “数据结构”是一门关于非数值数据在计算机中表示、变换及处理的课程。这里指的“数据”实质是指计算机所能表示的各种不同数据对象的集合。对于每一具体的数据对象，其数据元素之间的关系都不是孤立的。数据元素之间的内在联系被称为结构。从数据元素之间的关系特征分析，各种数据对象的数据元素之间的关系仅呈以下四种结构之一：集合结构、线性结构、树型结构、图型结构。 “数据结构”课程的主要内容是针对以上四种结构，先从逻辑层面讨论结构的关系特征及抽象操作，再讨论结构在计算机中的存储表示（映像），并在存储表示的基础上给出相应结构的基本操作及实现，在此基础上讨论各种结构的应用。 目前的《数据结构》教材大体上按上述结构，在描述算法时大多采用类C或Pascal的算法描述语言。算法描述语言具有简洁和更关注于算法本身的优点，但对许多刚学完计算机程序设计语言、编程能力尚且不足的学生，将这些算法转变为可编译运行的程序时，会碰到一些困难。 在长期的教学过程中，我们认为，“数据结构”是一门兼具理论性与实践性的课程，在掌握程序设计语言后，本课程还是一门加强与提高学生程序设计能力的重要课程。因此，本书以传统的数据结构的主要内容为主线，在充分讨论结构的逻辑特征与存储表示的基础上，用C++语言完成数据结构与描述和实现。同时，我们更加强调数据结构的应用，对不同的结构类型设计多个应用实例，每一算法或程序的编写力求高效、易读，并遵循程序设计的规范，从而帮助读者将数据结构与工程应用有机结合起来。 本书另一个特点是将面向对象的方法引入到数据结构领域。面向对象技术不仅是一种程序设计方法学，而且是一种认识方法学，“数据结构”讨论的正是数据的描述和处理，与面向对象的认知方法具有天然的联系。面向对象程序设计语言提供的封装、继承、多态和泛型程序设计等机制，为数据结构抽象数据类型的程序实现提供了很好的描述工具。本书以C++为程序设计语言，因此课程讲授时，可针对学生的具体情况，重点复习一下类与对象、运算符重载、模板、STL等相关知识。 历经30多年的发展，“数据结构”课程的主要讨论范畴基本已取得共识。尽管计算机应用领域仍在不断地扩大并产生了许多新的数据结构和算法，但数据结构最基本和最核心的内容还是各种经典教材中反复强调的最具有代表性的那些知识。2006年，教育部高等学校计算机科学与技术教学指导委员会编制了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》。其中，算法与数据结构涉及AL1、AL2、AL3、AL4、AL5、PF2、PF3、PF4等多个知识单元，知识点包括：递归、面向对象程序设计的基本理论、基本数据结构（包括：堆栈、队列、链表、哈希表串、数组和广义表、树型结构及应用、图型结构及应用）、常用排序算法、常用查找技术、算法分析基础等。2009年，教育部考试中心制定了全国硕士研究生入学统一考试关于“数据结构”科目的考试大纲。以上内容构成了我们编写本书的大纲依据。 本书的编写团队是国家级优秀教学团队的重要成员，在科学研究、工程软件开发方面具有长期的工作经验，特别是在长期的计算机专业教学中，针对教与学环节上的问题，形成了编写《数据结构》教材的共识。历经一年多的时间，编写团队反复讨论研究，精心选取案例，相信对读者会有所帮助。 本书的编写将做到“三个结合”的原则：与现代软件开发技术相结合、与工程应用背景相结合、与提高学生的程序设计能力相结合，以C++为程序设计工具，避免传统的采用伪算法语言造成的与实际程序设计相脱节的现象，突出数据组织与算法的具体实现以及工程问题的数据结构表达，从而实现将“数据结构”回归为程序设计与软件开发基础课程的目标。 本书第1章由万健编写，第2、4章由王立波编写，第3章由赵葆华编写，第5～7章由周丽、徐翀、沈静及吴志芳编写，李卫明审阅并修改了全书的案例程序，任雪萍审阅了全书内容并编写了教学课件。全书的内容由上述编写者共同多次讨论定稿。 适用对象研究生本科教育、工科、计算机、编程语言 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。