李春葆《数据结构教程》（第4版）笔记和课后习题详解

下载地址:http://free.100xuexi.com/Ebook/88771.html
目录                                                                                        封面
内容简介
目录
第1章　绪　论
　1.1　复习笔记
　1.2　课后习题详解
第2章　线性表
　2.1　复习笔记
　2.2　课后习题详解
第3章　栈和队列
　3.1　复习笔记
　3.2　课后习题详解
第4章　串
　4.1　复习笔记
　4.2　课后习题详解
第5章　递　归
　5.1　复习笔记
　5.2　课后习题详解
第6章　数组和广义表
　6.1　复习笔记
　6.2　课后习题详解
第7章　树和二叉树
　7.1　复习笔记
　7.2　课后习题详解
第8章　图
　8.1　复习笔记
　8.2　课后习题详解
第9章　查　找
　9.1　复习笔记
　9.2　课后习题详解
第10章　内排序
　10.1　复习笔记
　10.2　课后习题详解
第11章　外排序
　11.1　复习笔记
　11.2　课后习题详解
第12章　文　件
　12.1　复习笔记
　12.2　课后习题详解
第13章　采用面向对象的方法描述算法
　13.1　复习笔记
　13.2　课后习题详解（无）
                                                                                                                                                                                                    内容简介                                                                                            


　　我国各大院校一般都把国内外通用的权威教科书作为本科生和研究生学习专业课程的参考教材，这些教材甚至被很多考试（特别是硕士和博士入学考试）和培训项目作为指定参考书。为了帮助读者更好地学习专业课，我们有针对性地编著了一套与国内外教材配套的复习资料，并提供配套的名师讲堂和题库。
　　李春葆所著的《数据结构教程》（第4版，清华大学出版社）是我国高校采用较多的计算机专业优秀教材，也被众多高校指定为计算机专业考研参考书目。
　　作为该教材的辅导书，本书具有以下几个方面的特点：
　　1．整理名校笔记，浓缩内容精华。在参考了国内外名校名师讲授李春葆《数据结构教程》的课堂笔记基础上，本书每章的复习笔记部分对该章的重难点进行了整理，同时对重要知识点进行点拨，因此，本书的内容几乎浓缩了配套教材的知识精华。
　　2．解析课后习题，提供详尽答案。本书参考大量数据结构相关资料对该教材的重难点课（章）后习题进行了详细的分析和解答，并对相关重要知识点进行了延伸和归纳。
　　要深深牢记：考研不同一般考试，概念题（名词解释）要当作简答题来回答，简答题要当作论述题来解答，而论述题的答案要像是论文，多答不扣分。有的论述题的答案简直就是一份优秀的论文（其实很多考研真题就是选自一篇专题论文），完全需要当作论文来回答！
　　圣才学习网│计算机类（www.100xuexi.com）提供全国各高校计算机类专业考研考博辅导班【保过班、网授班、3D电子书、3D题库等】、全套资料（历年真题及答案、笔记讲义等）、计算机类国内外经典教材名师讲堂、考研教辅图书等。本书特别适用于参加研究生入学考试指定考研参考书目为李春葆主编的《数据结构教程》的考生，也可供各大院校学习数据结构的师生参考。
　　与传统图书相比，本书具有以下七大特色：
1．互动学习：摇一摇，找学友，交友学习两不误　　摇一摇，找到学习本书的所有学友，可精确查找学友的具体位置；与学友互动，交流学习（视频、语音等形式），交友学习两不误；学习圈内有学霸解答本书学习中的问题，并配有专职教师指导答疑解惑。

2．720度立体旋转：好用好玩的全新学习体验　　圣才电子书带给你超逼真的3D学习体验，720度立体场景，任意角度旋转，模拟纸质书真实翻页效果，让你学起来爱不释手！

3．手机扫码即可阅读，精彩内容，轻松分享　　圣才电子书扫码即可在手机阅读，随处随学。可以不用客户端不用账号，简单方便！
4．质量保证：每本电子书都经过图书编辑队伍多次反复修改，年年升级　　我们拥有一支强大图书编辑团队，他们专门从事图书的编辑工作，对各类职称考试、考研考博等教材教辅深入研究，以及各类职称考试、考研考博的历年真题进行详尽仔细研究与分析，掌握考试命题的规律和方向，并结合行业最新前沿动态，不断分析整理各个科目的考试要点，把重要考点全部固化为试题形式，形成精准领先及时的备考电子书。同时，依托北京高校资源，我们聘请知名高校众多专家组成顾问团队严格审核圣才电子书，确保质量。
5．免费升级：更新并完善内容，终身免费升级　　如购买本书，可终生使用。免费自动升级指我们一旦对该产品的内容有所修订、完善，系统立即自动提示您免费在线升级您的产品，您将自动获得最新版本的产品内容。真正做到了一次购买，终身使用。当您的电子书出现升级提示时，请选择立即升级。
6．功能强大：记录笔记、答案遮挡等十大功能　　本书具有“知识点串联列举”“划线添加笔记”、“答案自动遮挡”、“全文检索”等功能。
　　（1）知识点串联列举——相同知识点内容列表呈现，便于读者记忆和复习，举一反三，触类旁通。【为考试教辅量身定做】

　　（2）划线添加笔记——使用颜色笔工具，划一条线，写笔记，提交纠错。【圣才电子书独家推出】

　　（3）全文检索——输入关键词，本书相关内容一览无余。【圣才电子书独家推出】

7．多端并用：电脑手机平板等多平台同步使用　　本书一次购买，多端并用，可以在PC端（在线和下载）、手机（安卓和苹果）、平板（安卓和苹果）等多平台同步使用。同一本书，使用不同终端登录，可实现云同步，即更换不同设备所看的电子书页码是一样的。

　　特别说明：本书的部分内容参考了部分网络资料及相关资料。但由于特殊的原因，比如作者姓名或出处在转载之前已经丢失，或者未能及时与作者取得联系等，因而可能没有注明作者的姓名或出处。如果原作者或出版人对本书有任何异议，请与我们联系，我们会在第一时间为您处理！
　　圣才学习网（www.100xuexi.com）是一家为全国各类考试和专业课学习提供辅导方案【保过班、网授班、3D电子书、3D题库】的综合性学习型视频学习网站，拥有近100种考试（含418个考试科目）、194种经典教材（含英语、经济、管理、证券、金融等共16大类），合计近万小时的面授班、网授班课程。
　　如您在购买、使用中有任何疑问，请及时联系我们，我们将竭诚为您服务！
　　全国热线：400-900-8858（8:30-00:30）
　　咨询QQ：4009008858(8:30-00:30)

　　详情访问：http://it.100xuexi.com/（圣才学习网|计算机类）
圣才学习网编辑部
                                                                                                                                    本书更多内容>>
                                                                                                                                                                                                                    使用说明                                                                                                   
                                                                                    

内容预览
第1章　绪　论
1.1　复习笔记
一、数据结构概述
1．数据结构的定义
（1）基本概念
数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。
（2）相关术语
①数据元素
数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候，一个数据元素可以由若干个数据项组成。
②数据项
数据项又称字段或域，它是具有独立含义的最小数据单位。
③数据对象
数据对象是性质相同的数据元素的集合，它是数据的子集。
（3）数据结构的内容
①数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
②数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。
③施加在数据上的操作，即数据的运算。
（4）逻辑结构
数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（5）存储结构
数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。
数据的运算最终需在对应的存储结构上用算法实现。
总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。
（6）数据结构的表示
对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
描述数据结构通常采用二元组表示：
B=（D，R）
其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：
D={di | 1≤i≤n，n≥0}
R={rj | 1≤j≤m，m≥0}
其中di表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D是一个空集。rj表示集合R中的第j个关系，m为R中关系的个数，特别地，若m=0，则R是一个空集，表明集合D中的数据元素间不存在任何关系，彼此是独立的，这和数学中集合的概念是一致的。
R中的一个关系r是序偶的集合，对于r中的任一序偶（x，y∈D），把x称作序偶的第一节点，把y称作序偶的第二节点，称序偶的第一节点为第二节点的前驱节点，称第二节点为第一节点的后继节点。若某个节点没有前驱节点，则称该节点为开始节点；若某个节点没有后继节点，则称该节点为终端节点。
对于对称序偶，即∈R，且∈R（x，y∈D），可用圆括号代替尖括号，即（x，y）∈R。
数据结构还可以利用图形形象地表示出来，图形中的每个节点对应一个数据元素，两节点之间的连线对应关系中的一个序偶。
2．逻辑结构类型
（1）集合
集合是指数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
（2）线性结构
线性结构是指该结构中的节点之间存在一对一的关系。其特点是开始节点和终端节点都是惟一的，除了开始节点和终端节点以外，其余节点都有且仅有一个前驱，有且仅有一个后继。线性表就是一种典型的线性结构。
（3）树形结构
树形结构是指该结构中的节点之间存在一对多的关系。其特点是每个节点最多只有一个前驱，但可以有多个后继，且终端节点可以有多个。二叉树就是一种典型的树形结构。
（4）图形结构
图形结构是指该结构中的节点之间存在多对多的关系。其特点是每个节点的前驱和后继的个数都可以是任意的。图形结构可能没有开始节点和终端节点，也可能有多个开始节点、终端节点。
树形结构和图形结构统称为非线性结构。
3．存储结构类型
（1）顺序存储结构
①存储方式
该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元里，节点之间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。
②优点
a．节省存储空间；
b．可实现对节点的随机存取。
③缺点
不便于修改，对节点进行插入、删除运算时，可能要移动一系列的节点。
（2）链式存储结构
①存储方式
该结构不要求逻辑上相邻的节点在物理位置上也相邻，节点间的逻辑关系是由附加的指针字段表示的。通常链式存储结构要借助于计算机程序设计语言的指针类型来描述。
②优点
便于修改，在进行插入、删除运算时，仅需修改相应节点的指针域，不必移动节点。
③缺点
a．与顺序存储方法相比，链式存储方法的主要缺点是存储空间的利用率较低；
b．由于逻辑上相邻的节点在存储空间中不一定相邻，所以不能对节点进行随机存取。
（3）索引存储结构
①存储方式
该结构通常是在存储节点信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中关键字惟一标识一个节点，地址是指向节点的指针。
②优点
a．这种带有索引表的存储结构可以大大提高数据查找的速度；
b．可以对节点进行随机访问；
c．仍保持较高的数据修改运算效率。
③缺点
增加了索引表，降低了存储空间的利用率。
（4）散列（或哈希）存储结构
①存储方式
该结构的基本思想是根据节点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作为该节点的存储地址。
②优点
查找速度快。
③缺点
哈希存储方法只存储节点的数据，不存储节点之间的逻辑关系。哈希存储方法一般只适合要求对数据进行快速查找和插入的场合。
上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映像。
4．数据类型和数据结构
（1）数据类型
①C／C++语言的基本数据类型
a．int型
int型是整型，可以有三个限定词short、long和unsigned，分别对应短整数、长整数和无符号整数。
b．bool型
bool型是逻辑型，其取值只能是false（假）和true（真）。
c．float型
float型是单精度浮点型。
d．double型
double型是双精度浮点型。
e．char型
char型是字符型，用于存放单个字符。
②C／C++语言的指针类型
存放地址的变量称作指针变量。有关指针的两个操作是：
a．定义了int i，则&i操作是取变量i的地址；
b．定义了int*p（这里的p是指向一个整数的指针），则*p操作是取p指针所指的值，即取p所指地址的内容。
③C／C++语言的数组类型
数组是同一类型的一组有序数据元素的集合。
数组有一维数组和多维数组。数组名标识一个数组，下标指示一个数组元素在该数组中的顺序位置。数组下标的最小值称为下界，在C／C++中数组下界总为0。数组下标的最大值称为上界，在C／C++中数组上界为数组大小减1。
④C／C++语言中的结构体类型
结构体由一组称作结构体成员的项组成，每个结构体成员都有自己的标识符。
⑤C／C++语言中的共用体类型
共用体是把不同的成员组织为一个整体，在存储器中共享一段存储单元，但不同的成员以不同的方式被解释。
⑥C／C++语言中的自定义类型
C／C++语言中允许使用typedef关键字来指定一个新的数据类型名。
⑦引用运算符
C++语言中提供了一种引用运算符“&”，当建立引用时，程序用另一个已定义的变量或对象（目标）的名字初始化它，从那时起，引用就作为目标的别名使用，对引用的改动实际就是对目标的改动。
引用常用于函数形参中，采用引用型形参时，在函数调用时会将形参的改变回传给实参。
（2）抽象数据类型
①抽象数据类型定义
抽象数据类型（ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算。
②表示方法
其基本格式如下：
ADT抽象数据类型名
{
数据对象：数据对象的声明
数据关系：数据关系的声明
基本运算：基本运算的声明
}ADT抽象数据类型名
其中基本运算的声明格式为：
a．基本运算名（参数表）：运算功能描述；
b．基本运算有两种参数：赋值参数，只为运算提供输入值；引用参数，以&打头，除可提供输入值外，还将返回运算结果。
③特征
抽象数据类型有两个重要特征：
a．数据抽象：强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）；
b．数据封装：是指将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）如C++中的类来实现。
二、算法及其描述，
1．算法概述
（1）定义
数据元素之间的关系有逻辑关系和物理关系，对应的运算有逻辑结构上的运算（抽象运算）和具体存储结构上的运算（运算实现）。算法是在具体存储结构上实现某个抽象运算。
算法是对特定问题的求解步骤的一种描述。.
（2）特点
①有穷性；
②确定性；
③可行性；
④有输入；
⑤有输出。
程序可以无穷循环，不一定满足有穷性，但算法必须满足有穷性。
2．算法描述
常用于描述算法的C／C++语言基本语句：
（1）输入语句
scanf（格式控制字符串，输入项表）；
（2）输出语句
printf（格式控制字符串，输出项表）；
（3）赋值语句
变量名=表达式；
（4）条件语句
if（条件）语句；
或者
if（条件）语句1 else语句2；
（5）循环语句
while（表达式）循环体语句；
do循环体语句；
while表达式；
或者
for（赋初值表达式1；条件表达式2；步长表达式3）循环体语句；
（6）返回语句
return（返回表达式）；
（7）定义函数语句
函数返回值类型函数名（类型名形参1，类型名形参2，…）
函数返回值类型 函数名（类型名 形参1，类型名 形参2，…）
{
说明部分；
函数语句部分；
}
（8）调用函数语句
函数名（实参1，实参2，…）；
三、算法分析
1．算法设计的目标
（1）正确性；
（2）可使用性；
（3）可读性；
（4）健壮性；
（5）高效率与低存储量需求。
2．算法效率分析
通常有两种衡量算法效率的方法：事后统计法和事前分析估算法。一般采用事前分析估算法来分析算法效率。
一个算法的执行时间可以由其中基本运算的执行次数来计量。
算法中基本运算执行次数T（n）是问题规模n的某个函数f（n），记作：
T（n）=O（f（n））
记号“O”读作“大O”（是Order的简写，意指数量级），它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。各种不同数量级对应的值存在着如下关系：
O（1）2n）2n）2）3）n）n是所有输入的集合，任一输入I∈Dn，P（I）是I出现的频率，有

，T（I）是算法在输入I下所执行的基本运算次数，则该算法的期望时间复杂度为：

该算法的最坏时间复杂度为：

3．算法存储空间分析
一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：
S（n）=O（g（n））
若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。
对于递归算法，为了实现递归过程用到一个递归栈，所以需要根据递归深度得到算法的空间复杂度。
四、数据结构+算法=程序
1．程序和数据结构
著名的计算机科学家沃思（N．Wirth）指出，程序就是在数据的某些特定的表示方法和结构的基础上，对抽象算法的具体表述，所以程序离不开数据结构。
程序是通过某种程序设计语言描述的，程序设计语言有实现数据结构和算法的机制，类型定义与对象说明和语句是其主要部分。程序设计语言中的类型定义与对象说明实现数据结构；程序设计语言中语句实现算法，描述了程序的行为。
2．算法和程序
由程序设计语言描述的算法就是计算机程序。对求解一个问题而言，算法就是解题的方法，没有算法，程序就成了无本之末，无源之水。算法在程序设计、软件开发甚至在整个计算机科学中的地位都是极其重要的。
3．算法和数据结构
通过分析算法的时间复杂度和空间复杂度等，可以得到好的算法，如图1-1所示。

图1-1　设计好算法的过程
存储结构对算法的影响主要在两方面：
（1）存储结构的存储能力
如果存储结构存储能力强、存储信息多，算法将会较好设计。反之对于过于简单的存储
结构，可能就要设计一套比较复杂的算法。在这一点上，经常存在时间与空间的矛盾，因为存储能力往往是与所使用的空间大小成正比的。
（2）存储结构应与所选择的算法相适应
设计算法与选择合适的数据结构是程序设计中相辅相成的两方面，缺一不可。
算法通常是决定程序效率的关键，但一切算法最终都要在相应的数据结构上实现，许多算法的精髓就是在于选择了合适的数据结构作为基础。在程序设计中，不但要注重算法设计，也要正确地选择数据结构，这样往往能够事半功倍。
4．数据结构的发展
早期的计算机主要应用于科学计算，随着计算机的发展和应用范围的拓宽，要求人们对计算机加工处理的对象进行系统的研究，即研究数据的特性、数据之间存在的关系，以及如何有效地组织、管理存储数据，从而提高计算机处理数据的效率。数据结构这门学科就是在这样的背景下逐渐形成和发展起来的。
数据结构的概念最早由C.A.R.Hoare和N.Wirth于1966年提出，而对数据结构发展作出杰出贡献的是D.E.Kunth和C.A.R.Hoare。

下载地址:http://free.100xuexi.com/Ebook/88771.html