新编数据结构及算法教程.pdf
华北电力大学844数据结构参考用书，林碧英数据结构，网上资源很难找等学校计算机专业规划教材
新编数据结构
及算法教程
林碧英主编
石敏焦润海编著
清华大学出版社
北京
内容简介
本书介绍了数据结构的基本概念、基本知识以及数据结构的应用。全书按照三部分编写。第一部
分是线性结构,包括线性表栈与队列、数组和特殊矩阵;第二部分是非线性结构,包括树和二叉树图;
第三部分是数据处理技术,包括查找和排序内容涵盖了全国硕士研究生计算机综合考试课程的数据结
构知识。
本书适合作为各类高等院校、高等职业技术学校与计算机相关的各类专业的数据结构与算法的教
学用书,也是从事软件设计人员一本难得的参考书
本书封面贴有清华大学出版杜防伪标签,无标签者不得销售。
版权所有,侵权必究。侵权举报电话:010-6278298913701121933
图书在版编目(cP)数据
新编数据结构及算法教程/林碧英主编,一北京:清华大学出版社,2012.9
(高等学校计算机专业规划教材)
IsBN978-7-30229370-5
I.①新…Ⅱ.①林…Ⅲ.①数据结构一高等学校一教材②算法分析一高等学校一教学参考
资料Ⅳ.①TP311.12
中国版本图书馆CIP数据核字(2012)第158276号
责任编辑:龙啟铭
封面设计:常雪影
责任校对:梁毅
责任印制:李红英
出版发行:清华大学出版社
sate:http://www.tup.com.cn,http://www.wgbook.com
地址:北京清华大学学研大厦A座
邮编:100084
投稿与读者服务:0106276969, c-service@tup. tsinghua.euO1062786544
杜总机:010-62770175
邮购
质量反傻:010-6272015,zhiliang@tup.tsinghua,edu.cn
课件下载http://www.tup.comcn,010-62795954
印刷者:北京市人民文学印刷厂
装订者:三河市溧源装订厂
经销:全国新华书店
开本:185mm×260mm
印张:25.75
字数:614千字
版次:2012年9月第1版
印次:2012年9月第1次印刷
印数:1~3000
定价:39.50元
产品编号:048357-01
前言
“数据结构”是计算机及相关专业的一门核心专业基础课,在计算机课
程的教学计划中,它起着核心主导、承上启下的作用,是培养学生程序设计
能力的一门重要课程,也是计算机及相关专业的大学生应聘、考研的一门必
需课程。
长期以来,数据结构课程由于其抽象与动态性,使得在教学过程中始终
存在“能听懂,编不了程,不会应用”的现象。目前大部分学生在学数据结构
之前,只学了一门程序设计语言。受学时的限制,数据结构需要的链表基
础,学生知之甚少,几乎没有编写过有关链表的程序,因此造成了学生学习
“数据结构”的困难。另外,目前国内外的很多数据结构教科书都是在抽象
层次上阐述,它们在介绍典型数据结构之前,虽然也使用了一些实际问题作
为切入点,但最后并没有针对这些问题给出具体的解决方案,学生还是没有
弄清楚为什么要学习这种结构,怎样用这种结构来解决实际问题。
由于以上问题,我们认为数据结构的教学改革势在必行。为此,我们对
传统的教学方法进行改革尝试,以应用为主线,用案例驱动的教学方式,对
每一种典型的数据结构教学采用以下方法:
(1)引入实际问题。
(2)分析实际间题中的数据和数据之间的关系,以及对数据需要做的常
用操作。
(3)抽象出实际问题涉及数据的逻辑结构、存储结构和基本操作的设计
与实现。
(4)用所学的数据结构设计和实现解决这些实际问题的算法
(5)编码、调试并分析运行结果。
上述例驱动的教学模式,我们已经实践了4年,取得了可喜的成绩。
我们边教学边总结,编写了这本以案例驱动为主导,以解决实际问题为主
线,以激发学生学习热情为目标的教材,目的是使得原本难教难学的课程变
得生动形象,更贴近实际,从而切实提高学生的程序设计能力。
此外,本教材还具有以下特点:
(1)加强对基本操作实现的函数形参的分析。每个基本操作都配以示
意图,显示存放在内存中的数据对象在操作完成前后的变化,分析操作的对
象,需要的输入和输出,以及操作是否引起数据对象的变化,帮助读者熟练
掌握基本操作的设计与实现
新编数据结焖及算法教酲
(2)数据结构中的很多算法涉及递归操作,初学者很难理解递归算法的执行过程,为
此我们对较难理解的递归算法,配以图表,揭示每一步的变化,将抽象的想象变为可以看
到的具体过程,提升读者对递归算法的设计能力。
(3)对复杂的算法,我们用实际数据,采用图表结合的方式,将存储结构的变化和逻
辑结构的变化同步展现,加强读者对算法的理解,使读者进一步掌握复杂算法的设计与
实现。
(4)各章内容均与授课对象进行过多次交流,广泛听取学生的意见,及时进行内容的
更新和修改。
全书共8章,由林碧英老师统一编排、审核。第1章、第7章和第8章由石敏老师编
写;第2章和第3章由焦润海老师编写;第4章、第5章和第6章由林碧英老师编写。各
章的习题由苏辰隽、莫瑞芳整理。
我们只是在例教学做了一些学试,在教材的编写中可能还有很多不尽人意的地方,
恳请广大读者多提宝贵意见。
编写组
2012年8月于北京
算1章绪论/1
1.1数据结构的起源与发展……
1.2基本概念和术语
1.3理解数据结构
234
1.4数据的逻辑结构和存储结构……
罪章音自·音自·音音自●···,···身
1.4.1逻辑结构
1.4.2存储结构…
1.5抽象数据类型
1.5.1数据类型
.s·····.·······.4····.a··.◆
6888
1.5.2抽象数据类型
春看鲁曹自e
1.6算法分析与评价
1.6.1数据结构与算法的关系……………………………11
1.6.2算法的定义
11
1.6.3算法的5大特性……
1.6.4算法设计的要求
12
6.5算法效率分析
13
1.6.6算法的时间复杂度…………………………14
1.6.7算法存储空间需求
●D血·●
1.7本章小结
…………17
1.8习题
·。
17
旦章线性表少20
2.1问题的提出…………………………………
20
2.1.1问题中的数据分析
。非
…………20
2.1.2问题中的功能分析
21
2.1.3问题中的数据结构
22
2.2线性表
22
2.2.1线性表的定义……………
t●·自·●自自曹·鲁●非·●·自非D即。音
22
2.2.2线性表的存储结构和基本操作的实现
24
2.2.3线性表的两种存储结构的区别…………………47
新编数据结帕及算法教酲
2.3案例实现…
∴…………………………………48
2.3.1基于顺序表的新生成绩管理系统
2.3.2基于单向链表的新生成绩管理系统
52
24其他形式的链表…
■春●t鲁
54
24.1单向循环链表………………
54
2.4.2双向循环链表
57
2.5线性表的应用
60
2.5.1两个线性表的合并
60
2.5.2一元多项式的应用……
63
2.6本章小结
69
2.7习题与实验……
咖鲁鲁
………70
第3章栈与队列/74
3.1问题的提出…
74
3.1.1问题中的数据分析…
74
3.1.2问题中的功能分析
3.1.3问题中的数据结构
75
3.2栈…
自4垂
76
3.2.1栈的定义
76
32.2栈的存储结构和基本操作的实现…
77
3.2.3栈的两种存储结构的区别…
87
3.2.4案例实现:基于栈的括号匹配
87
3.3栈的应用
∴………………………89
3.3.1表达式求值
89
3.3.2栈与递归………………………………………………………………94
34队列
…103
3.4.1队列的定义………
。DDD曹看
身······吾···4·····4°
103
3.4.2队列的存储结构和基本操作的实现………
电。非···鲁··t非··非鲁·
105
3.4.3队列的两种存储结构的区别
116
3.4.4案例实现:基于队列的医院挂号模拟系统…………………116
队列的应用
120
3.6共用栈和双队列
··非自.。自非自息·自e·。节非“···普命·香卧自·····
124
3.6.1共用栈
124
3.6.2双端队列…………
126
3.7本章小结
127
3.8习题与实验…
127
目录
第4章数组和特森矩阵/133
4.1多维数组
…………………………………133
4.1.1数组的逻辑结构……………
………133
4.1.2数组的内存映像
133
2特殊矩阵的压缩存储
136
4.2.1对称矩阵…
136
4.2.2三角矩阵
·看·啬
酯·看音省。●看当看。看看··.曹·鲁P看·击。·●·“画
138
4.2.3带状矩阵
…139
4.3稀疏矩阵
140
43.1稀疏矩阵的三元组表存储
·非P鲁。。
140
4.3.2稀疏矩阵的十字链表存储
………146
4.4本章小结
■·
52
4.5习题
152
第5章树和二叉树/155
5.1问题的提出
昨●中●●春自电●要要。曹由●看··看看·看●
155
5.1.1问题中的数据分析
155
5.1.2问题中的功能分析
156
5.1.3问题中的数据结构
··.·····.·.·..····:..···s·.·············
156
5.2树的定义和基本术语……
…156
5.2.1树的递归定义……………………………………………………………156
5.2.2树的基本术语
5.2.3树的表示…
158
5.2.4树的抽象数据类型描述
····.·→·日:a.·:·◆
159
5.3二叉树
159
5.3.1二叉树的定义…
…………………………………159
5.3.2二叉树的性质
…………………………161
5.3.3二叉树的抽象数据类型
162
5.3.4二叉树的存储结构
b自D4b
…163
5.3.5二叉树的遍历及其应用………………………………………………166
5.3.6案例实现:基于表达式二又树的动态表达式计算
192
5.4线索二叉树………
192
5.4.1线索二叉树的定义…………………………………………………193
54.2线索二叉树的基本操作实现
■办曾p量自。口●·D看P鲁
…………194
54.3基于中序线索二叉树的遍历算法…
●·●
………200
5.5树、森林与二叉树的转换及其应用…
203
5.5.1树、森林与二叉树的转换………
203
新编数据结构及算法教酲
5.5.2树的存储结构
··b自·aap
204
5.5.3树和森林的遍历
209
5.5.4树的简单应用
也曲即春曹自。音中t量
……………………210
5.5.5案例实现:基于树结构的行政机构管理
………217
5.6哈夫曼树及其应用
220
5.6.1最优二叉树—哈夫曼树……
∴…220
56.2哈夫曼树及哈夫曼编码的构建算法
224
5.7本章小结
229
58习题与实验…
229
第6章图34
6.1问题的提出
234
6.1.1问题中的数据分析…
235
6.1.2问题中的功能分析
……235
6.1.3问题中的数据结构……
235
6.2图的定义和基本术语
235
6.2.1图的定义
235
6.2.2图的基本术语…………………………………………………………235
6.2.3图的分类与连通性
237
6.2.4图的抽象数据类型定义
238
6.3图的存储结构
239
6.3.1图的邻接矩阵表示………………………………………………240
6.3.2图的邻接表表示
·非
243
6.3.3有向图的十字链表表示……
246
6.3.4无向图的邻接多重表表示
247
6.4图的遍历
249
6.4.1连通图的深度优先搜索( Depth-First Search)
249
6.4.2连通图的广度优先搜索( Breadth-First Search)
………253
6.4.3非连通图的深度(广度)优先遍历………………………………255
6.4.4图的遍历算法应用
…………255
6.5图的连通性………………………………………………………………261
6.5.1无向图的连通分量和生成树…………………………………261
6.5.2最小生成树及应用
…261
6.6最短路径
·●
………………………………………272
6.6.1求从某个源点到其余各点的最短路径
………………272
6.6.2每一对顶点之间的最短路径……
278
6.7有向无环图及其应用
鲁着非鲁鲁會音自着自卷·。即D
283
6.7.1拓扑排序………
…284
**** Hidden Message *****
6666666666666 666666666666666666 新编数据结构及算法教程 xxxxxxxxxxxxxxx
6666666666666 666666666666666666 每一对顶点之间的最短路径 1111111111 6666666666666