数据结构C++殷人昆

所需积分/C币:27 2016-11-19 22:34:53 9.56MB PDF
收藏 收藏 1
举报

数据结构C++殷人昆
京)新登字158号 内容简介 数据结构是计算机专业的筷心课程是从事计算机教件开发应用人员应当必备的专业基础。随着计 算机的日益普及、简单的效据构知识已下敢到中学的计环机课程中,并已成为计算机歌件考域的必考 课程之一。4书是根据作者在北京清华大学及美国西根州 Grand valley州立大学多年敦学的经验,并参 考了近钾出版的多种国外大学效据结构和画向对软件工程教科书写的。内答包指:效组、髓接表、栈 和队列递归、树与森林、图、唯与优先级队列、集合与摸紫结构排序、紫引结构与散列等。书中采用面向 对象的观点讨论数据练构技术,并以兼有面向过程和面向对象双量特色的C++语首作为算法的抽述工 具,强化本知识和基本飴力的双基训练。全书条理清斯,還恰易懂,文并龙,适于白学。 本书适全作大专院校中计算机或敦件专业的教材,也可供计算机软件人员和计算机用户圆读。 版权所有翻印必究。 本书封而贴有清华大学出版社激光防伪标签无标签者不得销售。 图书在版编目(cMP据 数据结构用面向对象方法与C++描述/股人屁等编著.一北京:清华大学出版社,199 清华大学计算机系列教材) IBN73n203405-2 I.数…Ⅱ,殷…Ⅲ.数据结构ⅣTY311.12 中国版本图书馆cP数据核字(1999)第07546号 出版者:清华大学出版社北京清华大学校内邮缤10004) http://www.tupp.tsinghuaeduten 印刷者:清华园胶印厂 发行者:新华书店总店北京没行所 开本:77×1091/6印张:26字教:646千字 版次;1999年7月第1版199年7月第1次印刷 书号:IsN7302034052/T-1845 印数:0001~8000 定价:5.00元 前言 由于计算机的普及,极大地改变了人们的生活。目前各个行业各个领城都与计算机建 立了紧密的联系。这也随之带来了开发各种软件的需求。为了能够以最少的成本,最快的 速度,量好的质最开发出合乎需要的软件不能再像以前那样,把软件看作是个人雕鄢的精 品,必须遂循软件工程的原则把软件的开发维护活动标准化、工程化。就软件产品而言, 最重要的就是建立合理的软件体系结构和程序结构,设计有效的数据结构。因此,为能做好 件开发工作1必须了解应如何组织各种数据在计算机中的存储传递和转换。这样,《数据 结构》这门课程显得格外重要。自1978年美籍华裔学者冀中田在国内首开这门谍程以来 (当时作者也在场)经过20余年的发展这门课程已成为各大学计算机专业本科的主千谋 程,也成为非计算机类学生和研究生学习计算机的必修课程。 《数据结构》课程脱胎于《离散效学结构)它涉及各种离散结构(如向量集合树图、代 数方程多顶式等)在计算机上如何有储和处理。其内容丰寓,涉及面广泛,而且还在随各种 基于计算机的应用技术e发展,不断增加新的内容。特别是面向对象技术出现以后,人们认 识到,用它开发出来的软件体系结构更加符合人们的习惯,质量更容易得到保证,尤其是对 使用者和用户不断提出的新的需求,更容易适应。因此,在国际上,面向对象技术得到迅速 普及,出现了大批面向对象的软件开发工具。为了适合形势的要求,有必要开设结合面向对 象技术的效据结构课程。 用面向对象的观点讨论数据结构,与传统的面向过程的讲法相比变化软大。各神数据 结构的讨论都是基于批象教据类型和软件复用的。有新意也有继承。我们力图与过去的 讲授体系保持一致,但又必须引人一些新的榄念。为了能够让读者容易学习,我们对内容进 行了精选。许多概念,如双端堆、二项堆、最小一最大堆、变波那契堆左斜树、刷树、红-题 树B*树这些从基本数据结构派生出来的都舍去了。同时,把动态存储管理部分妇到《操 作系统课程,把文件组织部分归到《数据库原理》,只保留重要的应用最广泛的一些结构。 对这些结构做全面探人的讲解。阐明数据结构内在的逻辑关系,讨论它们在计算机中的存 储表示,并结合各种典型事例说明它们在解决应用问题时的动态行为和各种必要的操作。 并以C+语盲为衰述手段介绍在面向对象程序设计过程中各种数捐结构的表达和实现。 只妥是学过C或 PASCA语言就能够很容易地阅读和理解。并因此学习C十+语言提高 读者的教件设计和编程能力。 本书是作为清华大学计算机泰的《据铛构》教科书编写的。它的作者是在清华大学和 美国密西截州 Crand valley州立大学从事《数据结构》第一线教学的教师。他们有着丰富的 数据结构和软件工程教学的经验,教学效果良好。陶水雷教授1997年春专程回国参加教材 的编写工作。陶教授根据他在美国讲授软件工程和数据结构课程的经验就内容选择讲授 体系、习题选编提出了很多建议并帮助我们搜集了多种在美国受欢迎的数据结构方面的参 考书和实验指导书亲自审查和修改了全书的类声明和程序。北方交通大学盛绚华教授 亲自带领该校通控系一些同学对这些程序进行了验证。全书的我笔由清华大学计算机系 数据结构】课程讲殷人昆和谢若阳担任。 全书共分10章,第1章是预备知识,主要介绍什么是数据,数据与信息的关系;什么是 数据结构数据结构的分类。通过学习,读者能够了解抽象数据类型和面向对象的概念,并 对对象类继承消总以及其它关系的定义、使用有基本认识。由于我们选择了具有面向过 程和面向对象双重特点的C++语言,可以看助碳者自然而轻松地从传统程序设计观念向画 向对象方法转变。在这一章的最后还讨论了算法设计和简单的算法分析方法 第2章和第3章是全书的基础讨论了数和链表结构,以及利用它们定义出来的各种 结构如顺序表代数多项式稀硫矩阵字符串等。通过学习,读者可以了解对象和类的基 本实现,并通过模板繼承、多态性等的使用以及游标类的引人,对数据抽象慨念有进步 的解。 第4章引人三种存取受限的表即栏、队列和优先级队列。通过对它们的定义、实现和 应用的深入介绍使读者能够了解在什么场合使用它们为以后更复杂数据结构和算法的实 现提供了多种辅助手段。 第5章介绍在许多领中经常遇到的递归程序设计概念,以及递归的非递归实现问题a 在本章的后半部分重点介绍了广义表,这是→种应用广泛又十分灵活的结构。它射递归續 构导致f它的许多操作的邋归实现,从而加深对递归的认识。 第6章和第8章介绍在实际应用中最重要的非线性结构—树与图。在管、电子设 计、机设计、日常生活中许多方面都会用劲它们。 第7章和第10章介绍集合、查找、案引、散列。在实际与信息处理相关的应用中,这些 结构十分重要。许多非数值处理都沙及到这些结构,它们与内存、外存上的数据组织关系害 切,如在外存组织文件时全面应用了这些结构。它们又是许多新结构的生长点。因此读者 学习这些内容将获投匪浅。 第9章介纲排序。这也是应用十分广泛的技术。只要是教据处理就少不了排序。如 何才能高就地完成排序,本章分别就内外存使用的多种排序方法进行介绍和讨论,读者可 以深人了解排序的机制,并也能从中学到许多程序设计的技巧。 本书的篇幅虽较大,但给读者一个选择,可以根据时间、能力,当对全书需要学习的 内睿加以剪裁。本着少讲多练的原则,可以对每种结构是介绍类定义和关健操作的实现,其 它内容可以让同学自学。通过上机练习,加深理解。在本书目录中加新的章节可以酌情 不讲。 在本书的成书过程中得到计算机系领导的关心,清华大学出版杜的支持。此外,清华大 学计算机系194级全体150多位同学和中文系1994级6位同学参加了资料的翻译、整理 工作。 作者 1998年12月于北京 目录 第章绪论… 最■ 日日4甲罪罪■自 11什么是数据结构 唱p自·息咖想_即即看pD即即■咖即聊唱■■唱■■物咱口自血·加■卓D即聊自口D罪鲁罪唱·自『■■曾音 12抽象效据类型及面向对象桃念 咖■p啁看p自■甲谭咖p聊;■■血司罪鲁曲自會自■省加幽4會 12.1数据类型 晶日口罾昏凸曾昏1晋普■曾甲■晋号自平甲甲如自自血血·日··自·即自。· 122数据抽象与抽象数据类型(ADTs; Abstract Duta Typed) 12.3画向对象的念 T=看吾h由血画幽d画4甲看吾早看早三早警号 124用于描述数据绪构的语言 鲁■■■ 13数据结构的抽象层次 1,4用C++描述面向对象程序……… 14.1C+的函数特征………………………9 14.2C++的据声明…… d■■dd酗d■矗画bbb 1+ 143C++的作用城 冒q鲁■■■■罩日■■■酽■罩晕冒■冒■■■■冒■■冒■■■冒冒冒■■普■■即■冒■■■暑■冒冒■冒q■■曾q冒 14.4C++的类 …………11 14.5C++中的对象 ………13 14,6C++的轴人轴出 b吾西晶4如b西4b西Hbb日暴b吾如日吾4西品卧日4由· 13 14.7c++中的函数 15 14.8C++中的参数传递 15 14.9C++中的函数名重载和操作符重赣 16 14.10C↓+中的动态存储分配 14.11友元( friend)函效………""…M18 1.4,12内联( inline)函数 "s…ssss"ssa18 L.413结构(帥ut)与类 b晶bm甲4mmv智bm甲v口白m甲·要1警甲甲警P曾曾曾雪曾P晋曾甲■ 18 1.4.l4联合( Union)与类 甲■↓國晶b■■晷晶通■ ………19 5算法定又……………………………………………………………………19 1.6模板( template) 幽■罪司自■■罪看D■阜即目pD自咖命唱D自自咱p即口唱D鲁自幽自■命自咖自自司D自中■即聊即自山即聊即即自■命司D日山■卓 17性能分析与度量… 幽血■罪自■■■即罪隐■冒即。跏。珈d個隐自自口园啁D口山盘画■虚 ▲咖罪自自自■甲■自自■甲p罪白■甲 71算法的性能标准 1.7.2算活的后期测试 1鲁血·血口■口幽血d包■ 17.3算法的事前估计 174空复杂度度量 ψ罾曾◆■■斗甲罾d鲁昏甲晋罾■昏■凵鲁昏罾4晋■舀p■■晉 1.75时间复杂度度量 P司平曾曾『噌曾曾甲冒 27 1.76时阿复杂度的渐进表示法…… 177渐进的空间复杂度 ■口■郾自··■■哥■■■歌唱國凸即■晶凸昌晶凸 习题 如ttP34 第2章数组 ■■■■■晋■唱■即■■t■冒昏■■■自4自自自自■·■p鲁唱口P望唱P要甲日■■即■■日即■日即自日自日·音自自自自自D自D即 2.1作为抽象数据类型的数组…… ■■『■■·女■血啬山啬山音鲁 ↓個卧备個【 2.1.1在C++中数组的定义和初始化………… 2.1.2作为抽象数据类型的数组· 数组的顺序存储方式·44444446 2.2顺序衰… ■『冒『■冒■口q個『冒■『■■■ 22.1顺序表的定义和特点 222顺序表的类定义……44441643 223顺序表的查找、插人和删除…………………………………45 23,4作为抽象效据类型使用顺序表的事例 罩●。唱哈·4·B即apa4b·4即4p44 2.3多项式抽象数据类型 亡會血自『血幽個■血■■■■口■■世 即聊食咖■聊■即■着血即■咖■即■仙咖自■即1即即鲁鲁售即即罪即 47 23.1多项式抽象效据类型 中■中智血中中曾曾中甲中中自甲“ 48 232多项式的表示…4 23.3多项式的相加…s…"…51 24稀疏矩阵 24.1稀疏矩阵的抽拿数据类型 24.2稀就矩阵的压缩表示 暑2,43希疏矩阵的转置 兴24.4希疏矩阵相乘… 幽自血督 25字符串… atPsmTra1.+asme+aatmmt.ue, 59 25.1宁符串抽象数据类型和类定义………………59 2.52字符串操作的实现 鲁自自■■鲁■自音鲁自音■■■口■■晶■■■■■■备凸■■■■■画■晶晶凸晶日晶晶凸凸晶山▲〓〓··聊 25,3宇符申的模式匹配……1.6 苦254模式匹配的改进算法—KMP( D. Kmtr-J. H. Morrig-V.R.Pt 算法 习题……………………" 第3章继… ■■ψ■b44西孙■血◆即甲即即●p即唱唱p 31单链表( Sind linked L) 血··白甲钾曾曾甲平『曾■■冒『曾冒曾■■警■■曾■■■冒■■b罪D■■昌 3.1.1单链表的绪构… 自自自·中血冒中『冒雪曾■自自曲 3.12单表的类定义………………………………72 3.13单链表中的插入与删除 ■■■■●■■b■■■晶晶七遇 73 3⊥4带表头结点的单链表………………15 3.15用模板定义的单链表类… ■■■鲁■■冒■■咱啁D自噜■中血■血甲 7 31.6单链表的游标( Iterator)类 ■■■画·▲血■口■冒亡甲個曾個曾曾曾■曾■自血@■即即聊即4郾■看↓郾西山bmm 79 31.7静恋链衰 ■中中唱鲁會唱會會曾鲁申■■昏■■备□聊bdb 32循环链表 平晋■昏晶日吾晶古日甲可日即即日即即目日日早即?唱曾p自↓自自鲁p血血自晋画 国b聊●矗■■■即D即■Dpt N 32.1循环链表的类定义 482 32.2循环锉表求解约瀝夫问题 ■聊·〓女吾吾量甲·命。·即 #3.3多项式及其相加………… mm晶dm备晶I4■■即当■p自P罾俨m自■ 3.3.1多项式的类定叉… n命自vp=rP当B山自日白『画日鲁+b舀甲号早早自■日自日 94 3.3.2多项式的加法 ■鲁咱白■自看聊■音■西山■b司■■『■■曾P■冒冒FT甲冒甲日 3,4双向链表 目■。鲁■自自血 电■白■血中p中 35稀矩阵…………… 山■画通晶b凸■画愚■司■是 35.1稀疏矩阵的类定义 ■■ 352稀骁矩阵的建立 353删除新疏矩阵 凸凸晶■画■普画■↓■鲁自會血■ 3.6C++中的虚函数和动态联編… 3.6.1C++中的继承( inhertance) dppD即p■司血■司_自口音血音学曾十唱警自即b■ 22斗5%叨 362基类与派生类对象指针的转换 3.6.3虚函数( virtual function) ■聊·血■聊b血q暴口4面唱看晶b画聊4■罪■聊自-自■训—●■昏自會■鲁PP自 3.64缌虚函数和抽象基类 聊■晶■■血■昏山4■昏昏■早暑早引甲冒4冒■早日甲早■■ 99 3.65多态性( polynorphiEne)和动态聪编 h■b■■郾山b晶bbLb r 习题………………………………………………………101 第4章和队列… 4.1栈………… 4.1.1栈的抽象数据类型 鱼■會自白■會曲■1會口■會◆■ 會會曾會·甲·會冒■争 l03 4.12栈抽象数据类型的顺序存储表示与实现—顺序栈 4.13栈抽象数据类型的链接存储表示—链式栈………410 酱4.2表达式的计算( Expression Evaluation)……………""107 4.2.1表达式 17 422应用后缀表示计算表达式的值…-10 423中缀表达式转换为后缀表达式 4.3队列……………………………………………………113 4.3.l队列的抽象数据类型……113 4.3.2队列的顺序存储表示—循环队列…… Il 43.3队列的链接存储表示—铵式队列… ↓16 434列的应用举例—打印二项展开式(a+b)的系数 18 4.4优先级队列( Priority Queue)…"r"J9 44.1优先级趴列的定义… 【·辛·鲁即口鲁自日口口自会和自自命口日日a早中血■自自■■■自鲁■自 4.4.2优物级队列的存储表示和实现… 幽■▲鲁■■■即■■b■甲鲁●幽鲁画·鲁b■自D■幽即鱼■D即 45事件驱动模找( Event-Driven Simulation)… 噜■■自個晋幽鲁個自會會『■■會曲■個會『山-會曲鲁會 l21 习题…………………………………………………………………130 第5章邀归( NEUN}……………………………………………………………132 5.1递归的概念 ……-………132 52迷宫问题 鲁日画自個曾『·■『■日自自·自甲日一自 135 53递归过程与递归工作找…………………………138 54利用栈实现的迷官问题非递归解法… s4142 5.5广义表( Gereral liet)……………145 5.1广义表的概念… 自曾個自曲普曾鲁D甲号曾曾甲幽即自俨自自自自■·自·D·1即日与·号 146 5.52广义表的表示及操作……… ·47 553广义表存储结构的实现…49 554广义表的访问算法 鲁自备鲁■鲁 即唱會冒■早冒星中會 中p冒曾P甲争自口冒口甲● 15 555广义表的递归算法… 53 5.5.6三元多项式的表示 习题 算6章树与森林…………………163 61树和森秫的褫念………………………………………………163 51.1树的定义……………………………………………………163 612树的术语………………163 613树的抽象数据类型 冒■咖■q■■■动『『■■●■即唱聊■鲁唱咖■鲁司■咖司『即自看D『·唱■·D命跏 62二叉树( Binary The 噜唱咖■■■咖■■■『中即■■bp跏■『曲·〖p·■中■唱跏唱包即■■血■幽■血息■自·D■幽电 62.1二叉树的定义… 622二叉树的性质…………-…………-……"”*……………-166 623二叉树的抽杂数据类型 63二叉树的表示 63.1数组表示…-……… u168 632链表存储表示 r:169 64二叉树遍历( Binary Tree Traversal)………………12 64.1中序遐历( nonder Traversal) 血咱·■即■『■■■昌■昌■即■·■山■如▲晶晶晶。即 173 642前序遍历( preorder Trave Bal) 鲁自日■■·自血中甲甲曾甲■唱P即鲁甲留鲁-曲自P曲自鲁口_■■■■■ 173 643后序遄历( Postorder Traversal)……………………*…-…74 64.4应用二叉树逍历的事侧……………………………………y75 645叉树遍历的游标类( Thee iterator) 粱646不用的二又树中序遍历算法 wr182 6.5线家化二叉树( Threaded Binary Thee)…… 65.1线索〔Tha)… s182 652中序线索化二叉树………………………………--……1 653前序与后序的线索化二叉树 看Qd4早晶西h【晶山唱甲·甲·哈即当自鲁当一自曾 18 66堆(Heap)… 身聊■p■■自着血自■鲁自看L即 …189 66.I堆的定义… 會會會·P曾『『『■『『自自·自即身原即当身即口·D自自即氨聊自口即口■品口即b晶44↓== 662堆的建立 血曾曾個■曾會号■冒『『■冒目D即看鲁即画自●D 191 6.63堆的插人与除 6.7树与林 鲁『■ 671树的存储表示……………………………"…"1 672森林与二叉树的转换 673树的遍历… 200 674森林的遗历 1争■ ……202 68二叉树的计数s 69夫曼树( Hiriimgn Th 691瑞径长度( Path Lengt) ▲〓■凸凸山b看看b罪■■■即血咖 ……26 692霍夫曼树……………………27 693祖夫曼绺码… ■■■■■■即自■唱聊噜自口■■p自■■自 aoanneea ra+. 219 习题…… 罪『q章●冒d音■罩 -………-…--…4210 第7章集合与搜案 幽■■■■西■口■画·■■■■■■■■■■■■■画啬b山■■矗■■■山b自■女■凸4r昏 212 7.1集合及其表示… 如■■■画d 212 7.1.1集合基本慨念 ■噜鲁■■■鲁血恤鲁·音■個■【會噜■ 212 712以集合为基础的抽象数据类型 213 713用位向量实琥集合抽象教据类型… 213 7.14用有序链表实集合的抽梨数据类型 72等价类和并查集………………………………………219 7.2.1等价关系与等价类……………"……………………………………219 72.2确定等价类的链表方法 2720 723并查集…………… 〓·■〓q▲■■·d■■■·■·■晶画。p山■聊山凸·晶■如晶昌口画晶画 73静态搜索结构……...!227 7.3.1擭索的惭念 鲁自■■中自會血_鲁 鲁血·■鲁■■會自音申■自噜鲁鲁_口自中P鲁昏會鲁唱 2n7 732静态搜紫结构 228 73.3顺序搜紫… 734基于有序顺序表的折半搜索……… 21 73.5蒋于有序顺序表的妻渡那契搜素和插值搜索…… 234 74二叉搜紫树…… 235 7.4,1足义……… ■曾·鲁會曾曾曾個唱骨曾曾■會曾曾會會鲁血斷■自血■個曹■■會血■自會 742二叉瘦索树上的搜索 甲4-即4p山4.· 27 743二叉搜素树的插人…………………4238 744二叉搜索树的删條……s239 745与二叉搜索树相关的中序游标类 鲁咖 鱼●··■■恳·争曲看D曲血 240 餐了5最优二又搜索树 ………242 75,1扩兖二叉提索树… 242 52最优二叉搜索树 76AV树 ■■山■郾dd■备c■

...展开详情
试读 127P 数据结构C++殷人昆
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 领英

      绑定领英第三方账户获取
    • GitHub

      绑定GitHub第三方账户获取
    • 签到达人

      累计签到获取,不积跬步,无以至千里,继续坚持!
    • 分享王者

      成功上传51个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    数据结构C++殷人昆 27积分/C币 立即下载
    1/127
    数据结构C++殷人昆第1页
    数据结构C++殷人昆第2页
    数据结构C++殷人昆第3页
    数据结构C++殷人昆第4页
    数据结构C++殷人昆第5页
    数据结构C++殷人昆第6页
    数据结构C++殷人昆第7页
    数据结构C++殷人昆第8页
    数据结构C++殷人昆第9页
    数据结构C++殷人昆第10页
    数据结构C++殷人昆第11页
    数据结构C++殷人昆第12页
    数据结构C++殷人昆第13页
    数据结构C++殷人昆第14页
    数据结构C++殷人昆第15页
    数据结构C++殷人昆第16页
    数据结构C++殷人昆第17页
    数据结构C++殷人昆第18页
    数据结构C++殷人昆第19页
    数据结构C++殷人昆第20页

    试读已结束,剩余107页未读...

    27积分/C币 立即下载 >