作者：圣才学习网
出版社：圣才教育
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
李春葆《数据结构教程》（第4版）笔记和课后习题详解试读：
第1章 绪 论
1.1 复习笔记
一、数据结构概述
1．数据结构的定义（1）基本概念
数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。（2）相关术语
①数据元素
数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候，一个数据元素可以由若干个数据项组成。
②数据项
数据项又称字段或域，它是具有独立含义的最小数据单位。
③数据对象
数据对象是性质相同的数据元素的集合，它是数据的子集。（3）数据结构的内容
①数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
②数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。
③施加在数据上的操作，即数据的运算。（4）逻辑结构
数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。（5）存储结构
数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。
数据的运算最终需在对应的存储结构上用算法实现。
总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。（6）数据结构的表示
对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
描述数据结构通常采用二元组表示：B=（D，R）
其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d | 1≤i≤n，n≥0}iR={r | 1≤j≤m，m≥0}j
其中d表示集合D中的第i个数据元素（或节点），n为D中数据元i素的个数，特别地，若n=0，则D是一个空集。r表示集合R中的第j个j关系，m为R中关系的个数，特别地，若m=0，则R是一个空集，表明集合D中的数据元素间不存在任何关系，彼此是独立的，这和数学中集合的概念是一致的。
R中的一个关系r是序偶的集合，对于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）的增长率相同。各种不同数量级对应的值存在着如下关系：23O（1） 算法的时间复杂度（用f（n）表示）采用这种数量级的形式表示后，只需要分析算法中影响算法执行时间的主要部分即可，不必对每一步都进行详细的分析。 一般情况下，计算一个算法的基本运算次数是相当困难的，甚至是不可能的（因为一个算法的不同输入往往产生不同的运算次数，而一个算法的所有不同输入的数目可能十分庞大）。一种可行的方法是计算算法的平均运算次数。 定义 设一个算法的输入规模为n，D是所有输入的集合，任一n输入I∈D，P（I）是I出现的频率，有，T（I）是算法在输n入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。 1.2 课后习题详解
1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数据的基本单位，是数据的个体。数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？
答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：32f（n）=100n+n+100032g（n）=25n+5000n1.5h（n）=n+5000nlogn2
求它们对应的时间复杂度。323
答：f（n）=100n+n+1000=O（n），g（n）323=25n+5000n=O（n），1.51.5
当n→∞时，√n>logn，所以h（n）=n+5000nlogn= O（n）。22
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。（1）求一个n阶方阵的所有元素之和。（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：2
本算法的时间复杂度为O（n）。（2）算法如下：
本算法的时间复杂度为O（1）。（3）算法如下：
本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。（1）（2）（3）
答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：
则
6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：
求mergesort（a，0，n－1）的时间复杂度。其中，merge（a，i，j，m）用于两个有序子序列a[i．．m]和a[m+l．．j]的合并，是一个非递归函数，它的时间复杂度为O（合并的元素个数）。
答：设mergesort（a，0，n-1）的执行次数为T（n），分析得到以下递归关系：
O（n）为merge（）所需的时间，设为cn（c为常量）。因此：
由于趋近于1，则k=logn。所以2
上机实验题1
实验题1设计一个程序expl-1.cpp，输出所有小于等于n（n为一个大于2的正整数）的素数。要求：（1）每行输出10个素数；（2）尽可能采用较优的算法。’
实验题2编写一个程序expl-2.cpp，计算任一输入的正整数的各位数字之和，并分析算法的时间复杂度。
实验题3编写一个程序expl-3.cpp，判断一个字符串是否为“回文”（顺读和倒读都一样的字符串称为“回文”），并分析算法的时间复杂度。
第2章 线性表
2.1 复习笔记
一、线性表及其逻辑结构
1．线性表的定义
线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。当n=0时，表示线性表是一个空表，即表中不包含任何元素。
2．线性表的表示
设序列中第i（i表示逻辑序号）个元素为a（1≤i≤n），则线性表i的一般表示为：（a，a，…，a，a，…，a）12ii+1n
其中a为第一个元素，又称做表头元素，a为第二个元素，…，12a为最后一个元素，又称做表尾元素。n
一个线性表可以用一个标识符来命名，如用L命名上面的线性表，则：L=（a，a，…，a，a，…，a）12ii+1n
线性表中的元素是与位置有关的，即第i个元素a处在第i-1个元素ia的后面和第i+1个元素a的前面。这种位置上的有序性就是一种i-1i+1线性关系，所以线性表是一种线性结构，用二元组表示为：L=（D，R），其中：
对应的逻辑结构如图2-1所示。图2-1 线性表的逻辑结构示意图
3．线性表的抽象数据类型描述
抽象数据类型线性表的定义如下：
二、线性表的顺序存储结构
1．顺序表（1）线性表的存储结构
线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中，如图2-2所示。图2-2 线性表到顺序表的映射
由于线性表中逻辑上相邻的两个元素在对应的顺序表中的存储位置也相邻，所以这种映射称为直接映射。
这样，线性表中第一个元素的存储位置就是指定的存储位置，第i+1个元素（1≤i≤n-1）的存储位置紧接在第i个元素的存储位置的后面。假定线性表的元素类型为ElemType，则每个元素所占用存储空间大小（即字节数）为sizeof（ElemType），整个线性表所占用存储空间的大小为n×sizeof（ElemType），其中n表示线性表的长度。
在C／C++语言中，线性表的顺序存储结构是利用数组来实现的，数组的基本类型就是线性表中元素的类型，数组的大小要大于等于线性表的长度。
线性表中的第一个元素存储在数组的起始位置，即下标为0的位置上，第二个元素存储在下标为1的位置上，依次类推，第n个元素存储在下标为n-1的位置上。假定用具有ElemType类型的数组data[MaxSize]存储线性表L=（a，a，…，a，a，…，a），并假l2ii+1n设线性表L存储在数组A中，A的起始存储位置为LOC（A），则L所对应的顺序存储结构如图2-3所示。图2-3 顺序表的示意图
MaxSize一般定义为一个整型常量。如估计一个线性表不会超过50个元素，则可把 MaxSize定义为50：“#define MaxSize 50”。（2）线性表的顺序存储类型
在定义一个线性表的顺序存储类型时，除了定义一个数组来存储线性表中的所有元素外，还需要定义一个整型变量来存储线性表的实际长度。假定数组用data[-MaxSize-]表示，长度对应的整型变量用length表示，则采用结构体类型表示，元素类型为通用类型标识符 ElemType的线性表的顺序存储类型可描述如下：
typedef struct
{ ElemType data[Maxsize]； //存放顺序表中的元素
int length； //存放顺序表的长度
}Sqlist； //顺序表的类型定义
2．顺序表基本运算的实现
假设ElemType为int类型，使用如下自定义类型语句：
typedef int ElemType；
本节采用顺序表指针方式建立和使用顺序表，其结构如图2-4（a）所示，也可以直接使用顺序表，如图2-4（b）所示。图2-4 顺序表（1）建立顺序表
其方法是将给定的含有n个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度域。算法如下：（2）顺序表基本运算算法
①初始化线性表InitList（L）
该运算的结果是构造一个空的线性表L。实际上只需分配线性表的存储空间并将length域设置为0即可。
本算法的时间复杂度为O（1）。
②销毁线性表DestroyList（L）
该运算的结果是释放线性表L占用的内存空间。
试读结束[说明：试读内容隐藏了图片]