数据结构C++描述

所需积分/C币:23 2017-09-28 19:51:25 20.88MB PDF

是享有盛誉的数据结构教科书 它完整地包含了基本数据结构的内容,是CS2课程的理想用书。
和多态性,并简单介绍了用C++进行面向对象程序设计的方法。第12章中将对继承性 和多态性进行全而介绍。 第2章基本数据类型 程序设计语言提供最基本的数值和字符类型—整型浮点型、字符型和用户定义的 枚举型,并用这些基本类型组合产了数组、记录、甲和文件类型。本章以C++为例描 述了这些基本数据类型的ADT 第3章抽象数据类型和类 本书描述∫抽象数据结构及其用C++类的表示。本章定义了类的基本概念及其建 立和使用的方法。 第4章集合类 集合是具有增加、删除修改数据项功能的存储类。本书重点是对集合类的研究。本 章给出了同集合类型的例子。另外,还引人了衡量算法复杂虔的大Q方法。4书使用 该方法来比较不同的算法。木书最后以一个 Seqlist类的研究结束,这是一个普通表结构 的典型示例。 第5章栈和队列 本章讨论栈和队列,它们分别以后进先出〔FO)和先进先出(門FQ)顺序处理数据。 另外,还讨论具有优先级的队列,这是一种特殊的队列,它每次从队列中剽除权限最高的 元组 第6章抽象运算 抽象数据类型定义了初始化和处理数据的方法。本章扩屐C++语言定义的运算符 <<等)应用于抽象数据类型,这被称为运算符重载,它重新定义标准运 算符使之适用于ADT的拙象运算。最后,用有理数类作为例子说明如何进行运算符重载 及类型转换,并介绍了用友函教重载标准C++的输人/输出运算符的方法c 第T章形式数据类型 C++使用模板机制提供支持不同数据类型的模板函数和类。模板为数据结构提供 了强大的概括能力。本章以基于模板的Sak类及其对中缀表达式求值的应用为例说明 了这些概念。 第8章类和动态存储 的态数据结构使用运行时才由系统分配的内存,这可以让用户定义没有大小限制的 结构,增强了类的可用性。当然,在使用它们时需要特别小心。本章介绍复制构造函数、 重载赋值运算和析构函数方法,用它们可以正确地复制和賦值动态数据,并在对象被删除 时秤放内存空间。我们用Aray,Snig和sa类说明动态数据的掘大功能。这些类的使用 将贯穿于本书 第9章链表 ll 由于许多应用可用表来实现,用表来存储和查找数据是贯穿本的一个论题。本章 绍可动态处理的链表。建立链衣的种方法是,首先定义一个基本的结点类,然后创建 函数来增加或删除表中的数据项;另一种方法是建立一个包含遍历机制的链表类。类 linkedList用来实规类 Seqlist和类qhuu。这些方法提供了开发数据结构的有大工具。 第10章递归 递归在计算杌科学和数学中都是一个重要的问题求解工具。本章介绍递归并给出它 的多个应用,如数学公式计算、组合算法遍历迷宫和猜谜。最后,以 Fibonacci队列为例 玩较∫递归算法、交互算法和直接计算三种算法 第1章树 链表是从表头顺序存取的结点集,这种数据结构称为线件表。在许多应用中,对象中 的个成员可产生多个后代,不具备线性性质。本章介绍一种基本的非线性结内——树, 它的所有结点都由称为根(w)的结点产生的、树是用来描述继承关系,如计算机文件系 统和商业报表的理想绡构。首先集中讨论二叉树,即每个结点最多有两个后代。我们给 出类 Treenode来实现叉树及其应用,包括前序、中序和后序避历算法。最后,在应用举 例中,给出了以类 Bins]ree实现的叉查找树的结构它可用于高效地存取大批量数据a 第12章继承和抽象类 继承是面向对象程序设计的基本概念。本章讨论绻承的主要性质,给出其在C++ 中的应用,并引人虚两数作为使用继承的工具。另外,它还给出了只有虚数的基类。虚 函数是面向对象程序设计的基础,在本书的后续章节中将会用到。本章引人迭代算子的 概念,定义了对本书中出现的不同的表进行遍历的一个通用的算法。最后给出了以继承 和虚函数实现的异构数组及链表的例子 第13章高级非线性结构 本章继续讨论二叉树,并介绍其它的非线性结构,描述了基于数组的树,即将数组看 成完全二又树。本章对堆进行了研究,用它来实现雄排序及有权队州。尽管在一般情况 下,二叉查找树是实现表的最好结构,但也存在一些不足。数据绪构提供不同的深度平衡 结构来保证最快的查找时间。通过维承,派生了一个新的查找树类,称为AvL树。本章 最后介绍图的基本性质及关于图的一些传统算法。 第14章集合数据的组织 本章介绍一般的数据集合的查找和排序算法,包括传统的以树组为基础的选择排序、冒 泡排序和插入排序算法,以友著名的快排( QuickSort)算法。本书主要讨论的是石放在内存 中的内部数据但大量数据可能存放在外存上需要相应的查找和排序算钛。为此我们为 文件直接查找给出类 BinFile,并用它实现了外部索引顺序查找及外部归并排序算法。 背景知识 本书假定谋者已修完程序设计方面的先修课,并熟悉基本的C↓+语言。第2章给 出了C++的初级数括结构,用个完整的例子给出了它们的应用。该章可作为学习本 书所需C++知识的概述。对感兴趣的读者,作者还给出C+十语音中初级类型的定义 数组、流程控制、Ⅳ0、函数和指针等的何法a并分别给出了一些例子、程序和习题 补充材料 本书用到的所有类和程序的完整的源代码可通过 Intemet的从作者所在的 Pacitic 大学得到。小书所闬G++代码已在最新的and编诨器上测试过。除了极少蚍例外, 这些程序也可在用 SyHHnLee C的Mεci系统和用GⅦUC++的UNⅨ系统上编译 和运行 在 Internet上,用fp联结動.csup.sdu,联上后,用 anonymous用广名登录,山令是用 户白己的 Internel电了邮件地址。所有的软件均在/pub/C++目录下 需要上述C十+辅导材料的读者,可和作者直接联系,通过电子邮件和普通郇件均 可。电子邯件地址:hi回wp.ehu。逼信地址: ill Topp,,456S. Regent,scku, CA9204。 教师指导书给出了每草的讲课要点、大多数习题的答案和考试的样趣,还给出了多数 上机题的解题愿路。需要教师指影书的任课教师可联络本地 Prentice hal公司的代表 (使用本书中文版作为教材授课的教卵,请联络 Prentice hal公司北京代表处,电子邮 件地址; asbj@ bupt. edu,cn,通信地址:北京100086,知春里28号开源商务写字楼102室 目前教师指导书仅能免费提供英文版。) 致谢 作者在准备《数据结构C++语言描述》的过程中,得到许多朋友、学生和同事的支 持。 Pacifi大学慷慨地提供了许多资源支持完成此项工作。 Prentice hall出版公司派出精 F趴位完成本书的设计和出版。我们要特划感谢縞辑 Elizabeth Jonee, Bill zobrist和Aln Apt, Bayani de Leon本书由 Prentice hal和 Spectrum出版服务公司共同完成,作者也得到 Spectrum的 Kelly Rice和 Kristin Miller的大力支持 学生们通过直接和间接的反馈给我们的初稿提出了许多有价值的意见,我们的编审 对初稿从内容到组织方式都给出了许多指导和建议。在此,我们要特别列出他们的姓名 GeOrgia大学的 Hamid r. Arabnia; Fiorida技术学院的 Rhoda a.Ba8 s; Michigan- An1 Arbor 大学的 SHdr l.Buru美国海岸鲁队学院的RhrT. Close;美国空军学院妇Dvd Cok; Catonsville( Baltimore县)社会学院的 Charles j. Dowling; Mank州立大学的 David J Hagi; Califonia州大学 Chicag分校的 Jim Murphy和 Herker schildt作者的两位同事, Texas-EI Paso大学的 Ralph Elon和 Pacific大学的 Douglas smith对本书的出版做出了巨大 的贡献。他们敏锐的洞察力和对作者的全力支持是无法估量的,并极大地提高了本书的 质量 WiLin ford Wii to Ⅳ 目录 第1章概述……………………………14.1线性群林 1.1抽象数据类型 4.2非线性群体… .2C+-类和轴象数据类型 4.3算法分析 l18 13C++应川中的对象 4.4贩序查找与折半査找 14对象设计………… 6867 4.5基本的顺序表类 1.5类繼的应用 书面作业 …………:136 1.6面向对象程序设计 上机题 17程序测试与维护 笫5章栈和队列 …143 18C++程序设计语言……………24 5.栈 t.9抽象基类及多态性………… 5.2奖 Stack 书面作业 53表迟式求值 第2章基本数据关型 5.4队列 l靠型 5.5兆 22字符类型… 唱争即D甲P导 5.6优先级臥列… 2,3实数类型… 5.7实例研究:事件驱动模拟 2.4枚苹类型 书面作业 2,5指针…… 上机题 195 2.6数组类想… 第“章抽象操作 ?文本串及变量 6.1运算符重载…… 2.8记录…………… 6.2有理数… 2.9文件…… 6.3有理数类 2,10数網和记录的癒用 64作为成员函数的有埋数运算 书矿作业 6.5作为友元函数的自理数流运萍符 上机题 第3章抽隶数据类型和类………,……69 66有理数的转换 3,l用户类型类……1 7有理数的使用 211 3,2类的举例… 书面作业 33对象郡信息传递 83 上虮题 3.4对象数组 第T章形式嫩据类型 ■■■ 3.5多构造函数 7.1模板函数……………… 225 3.6应用举例:角矩阵 7.2模饭类… 229 书作业 .3表的模板类 上机题 100 74中表达式求伯 第4章群体类 书面作业 240 上机题… 11.5二又搜索树的使用 第8享类和动姦存储…………………245 11.6 Binsetnee的实现 8.【指针与动杰数据结构… 11.7实例研究;素引( Cungurdlance) 8.幼态中请对象 248 书面作业……… 8.賦值与初始化 上机题 通■■ 8.4安全数纽 257第1章继承和抽象类 8.5串类… 12.1承概站 86模式匹配 273 12.2C++中的继敷 87肥型集合 278 23多恋件和惠函数 书雨作业 +44■ 124抽象基类…… 上机题 29 2.5迭代算子… 9 第9章链表… 126有并表… Jll 9.结点类 2.7导构丧 514 92构造链 书而作业… 9.3设计链表类……………321 止机题 94类 Linkedlist………………324第13章高级非绿性结构 9.5 LinkedList龔的实現 1.1基于数组的二叉树… 9.6用馁表实现集合 337 13.2堆 9?实例研究:钉印纓冲池……… 3.3Hup类的实现… 98循环表 伏先级队列 99双向链表 13.5AⅥL树… 910实例研究:窗管理…360 13.6AⅥL树类 书面作业 13.7树迭代算子… 上饥题 138图… 13.9Grp袭… 鲁鲁 第10章递归 ■血山由山■■■11评「■ 10.1逆归的概念 马面作业 10.2设计递归函数 t机题… 606 10.3逃归代码和运行时堆栈… 第14章群体数埚的组织 104用递归进行问题求解 392 14.1数组序的基本算法…… 61 10.5逃归评佔…… 410 14.2快速排序〔 QuickSort) 617 书面作业……………… 14.3希法(Hsli") 上机题 144哈希表类… ? 第11树 l4.5搜索方法的忙能 11.1二叉树结构 426 l4.6二进制文件和外部数据操作……64! 112设计 Treenode函数 14.7辞典………… 113树扫描算法的使片… 书面作业 1].4二叉搜索树 445 上机题… 即鲁口唱 附录部分书面作业答案…………679 第章概述 11抽象数据类数 12C++类和抽象数据类型 1.3C++应用中的对象 14对象设计 1.5类继承的应用 6面向对象程序设计 I7程序测试与维护 18C++程序设计语 19抽象基类和多态性 书面作业 本书使用邮向对象的程序设计语言C++介绍数据结梅和算法。我们把每种数据结 构均视为抽象类型:它不但定义了数据的组织方式,还给出了处理数据的运算这种结 构,称为抽象数据类型( Abstract Data Type,ADT),是一种描述用户和数据之间接口的抽象 模型。本书用C++语言来表示每种轴象数据结构,即用类(as)来表示ADT,在具体 应用中用对象( cbject)来存储和处理数据 本书介绍AD的基本概念及其相关属性——数据封装和信息隐藏,并通过一系列实 例来阚述ADI的设计方法佃定义数据组织及运算的-般途径 C++类的创建是我们学习数据结构的基础,本书第3章将对其进行详细讨论。在本 章中,我们讲述C++类的概砒奴其如何表示ADT;在带星号(兴)的选读节中,给出了 些C++类的实例;概述了对象设计的基内容及其继承性,这是由问对象程序设计的基 石:还综述了本书所用到的程序设计方法。继承性和多态性扩充了面向对象程序设计的 能力,使其可用于开发基」类库的大型软件系统。我们将有第12章中进一步刚述继承性 和多态性,并有选择地将其用在一业高级数祸结构中。 本章是对书中所用概念的预习,在正式学习关键数据结构和面向对象这些概念之前 读者就可以逐渐熟悉它们 1.1抽象数据类型 数据拙象是拜序设计的中心内容。这种抽象被称为抽象数据类型(AD),它义了 数据取值范国和表现结构,以及对数据的操作集。也就是说,AD给出∫一种用户定义的 数据类型,其运算符指明了用户如何操作数据ADT与具体应用无关,这可使程序员把注 意力集屮在数据及其操作的埋想模型上 例1.1 1.小型公司维护进貨信息的程序。每项进货由一条何括货号、当前库存、单价 及进货级别的薮毡记录描述,其操作应包括修改上述不同数据,并在库存量低于一定 数量时修改进货级刿。数据抽象应该描述一条忽哲上述信息域的记录及可供库妾经 理维护进货记录的一系列操作。这些操作应包括在售出货物耐修改库存量、调价时 修改阶格及在库存小于应再进货级别賦给出需进贷的信息 货号当前库存单价进货别 操作 改厍 Upda∈ stockLey 调单价 Adis= UniLPr⊥e 订货信息 ReorderItem 2.掷散子的游戏程序。在设计中,骰子可描述下述AD:其数据包括被拐散 子数目、掷出骰子的总点数和每个骰子的点数;操作包括掷骰子、返回该次投掷的散 子的总点数以及打啉所擗每个骰子的点数。 数据 总点数 单个骰子忒数表 操作 掷骰子 求骰子总点数ToLd 打印点数 Displaying ADT描述规范 下面给出一种描述ADT的规范。它包括由AD名称组成的头,对数据类型的描述及 操作列表。对每种操作,我们用iapu(输入)取指足由用户给定的输值, precondition(前 根)表示该操作可执行前必须具有的数据,pme加工)表示由该操作完成的动作。执行 操作后,用otpu(输出)米示返回给用户的值,用 postcondition(结果)来表小在数据内部 所仵的任何改变。大多数ADT都有 initialize(初始化)操作来对数据赋訶值。在C+H语 吉环境下,初始化操作称为构造函数( Constructor)。我们用它来简化从ADT到E在C+ 中的表示的转变。 综上所述,ADT的描述规范为: 名称 捎述敷据为结构 杓造函嫩 Tn主iaLⅴalu妇s:用永初始化对象的数据 初始化对象 作1 用户输入的敬值 系统执行本揲作前数据所需的状 对歌据进行的动 返回给用户的数据 HE亡C啁itir 桑统执行操作后数据的状感 操作 操作n edi AdT AD.名称 例1 1.抽象数据类型Die的数据包拒每次所擰骰子数N,所掷出的总愿数和一个有 N项的存放每个骰子被掷出点数的表 AYT

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源