数据结构C语言严蔚敏版(第二版)超详细笔记附带课后习题

手机目录功能受限，可利用下方链接跳转到各章知识点： 第一章绪论知识点 第二章线性表知识点 第三章栈和队列知识点 第四章串、数组和广义表知识点 第五章树和二叉树知识点 第六章图知识点 第七章查找知识点 第八章排序知识点  

电脑可直接利用侧方目录或下方目录跳转知识点 另外给同学们一个学习建议，重难点看不懂的可以去mooc或者b站看一下同学或者优秀老师讲的课，结合笔记懂得更快些

根据此书所做随笔笔记，当然不是这本书也能学。 md版本和word版，此书pdf和习题答案都在网盘里。百度网盘下载慢的话可以去阿里云盘下。（但是！！！有一些东西）

链接：https://pan.baidu.com/s/1dSTeIQCagyotKvY2ObvBPw 提取码：e9s0 复制这段内容后打开百度网盘手机App，操作更方便哦

阿里云网盘下载： https://www.aliyundrive.com/s/uTWQiarmNz4

另外这笔记算是自己写了一些，也有网上粘的一些。如果有需要，可以将原链接放到里面。

根据例子理解：假设有两张表，上表为人员表，下表为课程表， 表的格式如下：

这两张表就是数据 而单独的一张表就称为数据对象，即人员表是一个数据对象，课程表也是一个数据对象 而每张表中的每一行就称为数据元素 而姓名，性别，身高，课程代号，课程名就称为数据项

数据结构包括逻辑结构和存储结构两个层次。

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合 

逻辑结构分为四种类型：集合结构，线性结构，树形结构，图形结构。

集合结构：数据元素同属一个集合，单个数据元素之间没有任何关系。

线性结构：类似于线性关系，线性结构中的数据元素之间是一对一的关系。

树形结构：树形结构中的数据元素之间存在一对多的关系。（各元素及元素关系所组成图形类似于树状图）。

图形结构：数据元素之间是多对多的关系。如下图所示。

物理结构又叫存储结构，分为两种，一种是顺序存储结构一种是链式存储结构。  

顺序存储结构是把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。之前学习的数组就是一种顺序存储结构。（如图所示）

链式存储结构：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。

根据指针找出相邻元素的位置

一般包括整型、实型、字符型等原子类型外，还有数组、结构体和指针等结构类型。  

抽象数据类型（Abstract Data Type,ADT），类似C语言中的结构体以及C++、java语言中的类。

通俗的讲，抽象数据类型，泛指除基本数据类型以外的数据类型。

抽象数据类型的概念与面向对象的思想是一致的。

算法 + 数据结构 = 程序  

  算法是为了解决某类问题而规定的一个有限长的操作序列。   一个算法必须满足以下五个重要特性： 有穷性、 确定性 、 可行性、 输入 、输出  

正确性 、 可读性 、 健壮性 、 高效性  

详细可以看这个：一套图搞懂“时间复杂度”  

看下列代码的时间复杂度：

最好、最坏和平均时间复杂度

空间复杂度只需要分析辅助变量所占的额外空间。

空间复杂度：S(n) = O(f(n))

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1) 举例：

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

我们再看一个代码：

答案：O(1)

解释：程序的执行次数为常数阶。

（2）

答案：O(m*n)

解释：语句a[i] [j]=0; 的执行次数为m*n。

3）

答案：O(n2)

解释：语句 s+=B[i] [j]; 的执行次数为n2。

（4）

答案：O( n \sqrt{n} n ​)

解释： x≥(y+1)*(y+1) = n≥(y+1)2

开根号： n ≥ ( y + 1 ) \sqrt{n}≥(y+1) n ​≥(y+1)

n − 1 ≥ y \sqrt{n}-1≥y n ​−1≥y

则 y ≤ n − 1 y≤\sqrt{n}-1 y≤n ​−1

x=n; //n>1

y=0;

while( y ≤ n − 1 y≤\sqrt{n}-1 y≤n ​−1){

​ y++; }

y++;执行了 n \sqrt{n} n ​ 次。则时间复杂度为：O( n \sqrt{n} n ​)

伪码书上讲的也很详细，笔记中有些就不再打了。可以看后面的案例分析中的完整代码。

由n (n≥0)个数据特性相同的元素构成的有限序列称为线性表，(n=0)的时候被称为空表。

略

线性表的顺序存储又被称为顺序表

顺序存储表示：用一组地址连续的存储单元依次存储线性表的数据元素的方式，具有顺序存储结构的特点（数据间的逻辑关系和物理关系是一致的）

假设线性表 L 存储的起始位置为 LOC(A) ，sizeof(ElemType) 是每个数据元素所占用存储空间的大小，则表 L 所对应的顺序存储如下图：

注意：线性表中的位序是从 1 开始的，而数组中元素的下标是从 0 开始的

线性表的顺序存储结构是一种随机存取的存储结构，即通过首地址和元素序号可以在O(1) 时间内找到指定的元素

由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，在C语言中通常使用动态分配的一维数组表示线性表

一、顺序表初始化 ①、为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。 ②、将表的当前长度设为0。

二、顺序表取值

①、判断指定的位置序号 i 值是否合理 (1≤i≤L.length), 若不合理，则返回ERROR。

②、若 i 值合理，则将第 i 个数据元素 L.elem[i-1] 赋给参数 e, 通过 e返回第 i 个数据元素的传值。

顺序表取值算法的时间复杂度为 ：O(1)

三、顺序表的按值查找

①、从第一个元素起，依次和 e相比较，若找到与 e相等的元素 L.elem[i], 则查找成功，返回该元素的序号 i+l (数组下标从 0 开始)

②、若查遍整个顺序表都没有找到，则查找失败， 返回0

顺序表按值查找算法的平均时间复杂度为 O(n)

四、顺序表插入元素

在第 i 个位置插入一个元素时，需从最后一个元素即第 n 个元素开始，依次向后移动一个位置，直至第 i 个元素。

①、判断插入位置 i 是否合法(i 值的合法范围是 1≤i≤n+ I), 若不合法 则返回 ERROR。

②、判断顺序表的存储空间是否已满，若满则返回 ERROR。

③、将第n个至第 i 个位置的元素依次向后移动一个位置，空出第 i 个位置 ( i =n+l 时无需移动）。

④、将要插入的新元素e放入第i个位置。

⑤、表长加1

顺序表插入算法的平均时间复杂度为O(n)

五、顺序表删除元素

删除第 i 个元素时需将第 i+ 1 个至第 n 个元素依次向前移动一个位置 (i = n 时无需移动）

①、判断删除位置 i 是否合法（合法值为 1 ≤ i ≤n), 若不合法则返回 ERROR。

②、将第 i个至第n个的元素依次向前移动一个位置 (i = n时无需移动）

③、表长减 1

一、单链表的初始化

①、生成新结点作为头结点，用头指针L 指向头结点。

②、头结点的指针域置空。

二、单链表的取值

①、用指针p指向首元结点，用 j 做计数器初值赋为1

②、从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 p 不为空(NULL), 并且没有到达序号为 i 的结点，则循环执行以下操作：

③、退出循环时， 如果指针p为空， 或者计数器 j 大于 i, 说明指定的序号 i 值不合法（i 大于表长n或 i 小于等于0), 取值失败返回ERROR; 否则取值成功， 此时 j=i 时，p所指的结点就是要找的第 i 个结点，用参数 e 保存当前结点的数据域， 返回OK。

单链表的按值查找算法的平均时间复杂度为 O(n)

四、单链表的插入

将值为e的新结点插入到表的第 i 个结点的位置上，即插入到结点 ai-1与ai之间。

①、查找结点 ai-1 并由指针p指向该结点

②、生成一个新结点*s

③、将新结点*s 的数据域置为 e

④、将新结点*s 的指针域指向结点ai

⑤、将结点 * p 的指针域指向新结点*s

top 指栈顶元素后一位置

S.top == 0时，栈空

S.top == stacksize 时，栈满

一、 顺序栈的初始化

二、顺序栈的入栈：

三、顺序栈的出栈：

四、顺序栈取栈顶元素：

链栈示意图：

链栈的存储结构：

一、链栈的初始化

二、链栈的入栈

三、链栈的出栈

四、链栈取栈顶元素

栈与递归知识点看小结思维导图

队列的操作与栈类似，不同的是，删除时在表的头部(即队头)进行。

队列也有两种存储表示，顺序表示和链表表示。

队列的顺序存储结构表示：一组地址连续的存储单元存储

单纯的顺序队列有"假溢出"的问题。

尾指针无法插入元素，队列的实际可用空间并未占满，这种现象称为 “假溢出＂

为了避免 ”假溢出“，可以将顺序队列变为 一 个环状的空间

在这种情况下， 如何区别队满还是队空呢？

1、少用一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变， 即当头、 尾指针的值相同时， 则认为队空；而当尾指针在循环意义上加1后是等于头指针， 则认为队满。

如图 3.14 (d)所示， 当J7、 J8、 J9 进入图 3.14(a)所示的队列后， (Q.rear+ 1)%MAXQSIZE 的值等于 Q.front, 此时认为队满。

2、另设一个标志位以区别队列是 “空” 还是 “满＂。

一、循环队列的初始化

二、循环队列求队列长度

三、循环队列入队

四、循环队列出队

五、循环队列取队头元素

队列的链式存储结构

一、链队的初始化

二、链队的入队

三、链队的出队

链队在出队前也需要判断队列是否为空，不同的是，链队在出队后需要释放出队头元素的所占空间

①、判断队列是否为空，若空则返回ERROR。

②、临时保存队头元素的空间，以备释放。

③、修改队头指针，指向下一个结点。

④、判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值， 指向头结点。

⑤、释放原队头元素的空间。

需要注意的是，在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）

四、取链队的队头元素

顺序栈的基本操作

链栈的基本操作

循环队列的基本操作

链队的基本操作

栈是限定仅在表尾进行插入或删除的线性表，又称为后进先出的线性表。栈有两种存储表示，顺序表示（顺序栈） 和链式表示（链栈）。栈的主要操作是进栈和出栈，对于顺序栈的进栈和出栈操作要注意判断栈满或栈空

队列是一种先进先出的线性表。它只允许在表的一端进行插入， 而在另一端删除元素。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）

栈和队列的逻辑结构都和线性表一样，数据元素之间存在一对一的关系

循环队列中少用一个元素判断对空或对满时：

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。

A．5，4，3，2，1

B．2，1，5，4，3

C．4，3，1，2，5

D．2，3，5，4，1

答案：C

解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。

A．i B．n-i C．n-i+1 D．不确定

答案：C

解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n

答案：D

解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。

A．x=top->data;top=top->link； B．top=top->link;x=top->link；

C．x=top;top=top->link； D．x=top->link；

答案：A

解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

（5）设有一个递归算法如下

①、定长顺序存储：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 例如

C语言约定在串尾加结束符 ‘ \0’，以利操作加速，但不计入串长；

若字符串超过Maxstrlen 则自动截断（因为静态数组存不进去）

想存放超长字符串怎么办？——静态数组有缺陷。 改用动态分配的一维数组 堆

②、堆分配存储：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态按需分配而得

三、链式存储

课时缩短，计划中不讲也不学这个。

想学的话跳转链接：串的总结

串、数组和广义表知识点

数组是线性表的推广，特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型

1．一维数组 一维数组可看成是一个线性表或一个向量，存储在一块连续的存储单元中，适合于随机查找。一维数组记为A[n]或A=(a0，al，…ai，…，an-1) ，一维数组中ai的存储地址LOC(ai)可由下式求出： LOC(ai)=LOC(a0)+i*L (0≤i=1）

性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0 = n2+1

一棵二叉树，除了终端结点（叶子结点），就是度为1或2的结点。假设n1表示度为1的结点数，则树 T 的结点总数

n=n0+n1+n2 ,我们再换个角度，看一下树T的连接线数，除了根节点，其他结点都有一根线表示分支进入，所以连接线数为结点总数减去1。按连接线树算的话：n-1=n1+2n2，可推导出n0+n1+n2-1 = n1+2n2，继续推导可得n0 = n2+1

满二叉树：深度为 k 且含有 2k-1个结点

性质4：具有n个结点的完全二叉树的深度为[log2n ] + 1

性质5：如果对一颗有n个结点的完全二叉树（其深度为[log2n ] + 1）的结点按层序编号（从第1层到第[log2n ] + 1层，每层从左到右），对任一结点i(1n,则结点 i 无孩子（结点i为叶子结点）；否则其左孩子是结点 2i

如果2i+1>n,则结点 i 无右孩子；否则其右孩子是结点 2i+1

①、顺序存储结构

二叉树的顺序存储结构缺点很明显：不能反应逻辑关系；对于特殊的二叉树（左斜树、右斜树），浪费存储空间。所以二叉树顺序存储结构一般只用于完全二叉树。

②、链式存储结构

二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次

如果限定先左后右，则二叉树遍历方式有三种： 先序（根）：DLR； 中序（根）：LDR ；后序（根）：LRD

中序遍历的递归算法：

中序遍历的非递归算法：

根据遍历序列确定二叉树

根据前序可知 A 为根节点，再看中序可知 BC 是在根节点 A 左子树，EDGHFI 是在根节点 A 右子树

再看前序和中序可知，B 为 根节点 A 的左孩子，C为B的右孩子，由此类推。

已知一棵二叉树的后序序列和中序序列，分别是DECBHGFA 和BDCEAFHG 是否可以唯一确定这棵树？

①由后序遍历特征，根结点必在后序序列尾部（即A）；

②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）；

③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；

二叉树遍历算法的应用

对于n个结点的二叉树，则在二叉链存储结构中就会有n+1个空链域

对于一个有 n 个结点的二叉链表，每个结点指向左右孩子的两个指针域，故共有 2n 个指针域，而 n 个结点的二叉树共有 n-1 条分支，即存在 2n-(n-1) = n+1 个空链域

如果一个结点的左孩子为空，则指向它的前驱结点。

如果一个结点右孩子为空，则指向它的后继。

怎么理解这句话，我们来看一个例子

它的后序遍历为: DBEFCA

那么它的后序线索二叉树是怎么画的呢？

我们根据它的后序遍历的结果来画后序线索二叉树

先来看D： D的左孩子为空，则指向它的前驱，它没有前驱。 D的右孩子为空，则指向它的后继，也就是B。

再来看B：B的左孩子为空，则指向它的前驱，它的前驱根据后序遍历的结果是D，所以B的左孩子指向D B的右孩子不为空

再来看E，E的左孩子为空，则指向它的前驱结点B,E的右孩子为空，则指向它的后继结点F

再来看F，它的左孩子为空，则指向它的前驱结点E。它的右孩子为空，则指向它的后继节点C

线索二叉树的结点形式：

LTag是在 lchild 不存储指针的时候才有其作用，说到底，是利用那 n-1 个空链域存储LTag和RTag，并没有开辟新的内存空间用来存储前驱和后继

和双向链表结点一样，在二叉树链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根结点（图中第一步），其rchild域的指针指向中序遍历访问时的最后一个结点（图中第二步）。反之，令二叉树的中序序列中第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中第三和第四步）。这样的好处是：我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

线索二叉树的遍历和构造伪码点超链接

线索二叉树的遍历和构造伪码

双亲表示法

  孩子表示法

略  

孩子兄弟表示法(常用)

（1）转换：把每棵树转换为二叉树。（即根结点没有右孩子的二叉树）

（2）连接：第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。

（3）旋转

二叉树转换为森林

（1）逆旋转

（2）抹线：从根结点开始，依次抹掉结点与右孩子的连线，直到结点没有右孩子为止

（3）转换：将二叉树转换成树（也可以省略该步骤）

1、树的遍历前面写了

2、森林的遍历

先序遍历森林。

中序遍历森林：普通的树构成的森林是不存在中序遍历的，这里的中序遍历必然指代的是化成二叉树的森林。

后序遍历也可以相似定义

哈弗曼树又被称为最优树

​ 路径：从一个结点到另一个结点之间的分支序列

​ 路径长度：从一个结点到另一个结点所经过的分支数目

​ 结点的权：根据应用的需要可以给树的结点赋权值

​ 结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积

​ 树的带权路径长度：树中所有叶子结点的带权路径之和

​ 哈夫曼树：由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树

哈弗曼树不存在度为 1 的结点。 n个叶子结点的哈弗曼树有 2n-1 个结点

在构造哈弗曼树时，是从叶子结点向根节点的方向进行的，每次都是两个两个成对的结点来形成一个新的分支结点，所以不存在度为1的结点。

其中第三个树的WPL最小，根据验证，其为哈弗曼树。

示例：w={5,29, 7, 8, 14, 23, 3, 11}

前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀，则称该编码系统中的编码是前缀码。例如，一组编码01,001,010,100,110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。

哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。

哈夫曼编码是最优前缀码

二叉树案例

（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。

A．唯一的 Ｂ．有多种

C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子

答案：A

解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

（2）由3个结点可以构造出多少种不同的二叉树？（ ）

A．2 B．3 C．4 D．5

答案：D

解释：五种情况如下：

（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。

A．250 B． 500 C．254 D．501

答案：D

解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

（4）一个具有1025个结点的二叉树的高h为（ ）。

A．11 B．10 C．11至1025之间 D．10至1024之间

答案：C

解释：若每层仅有一个结点，则树高h为1025；且其最小树高为[ log21025] + 1=11，即h在11至1025之间。

（5）深度为h的满m叉树的第k层有（ ）个结点。(1=, , }

无向图

若E是无向边（简称边）的有限集合时，则G为无向图。边是顶点的无序对，记为 (v,w) 或(w,v) ，且有 (v,w) =(w,v) 。其中 v，w 是顶点。

无向图

如上图所示，无向图G可表示为：

若有两个图G=(V,E),G1=(V1,E2)，若V1是V的子集且E2是E的子集，称G1是G的子图。

如下面的有向完全图是有向图的一个子图。

1.无向图中任意两点之间都存在边，称为无向完全图；如无向图中的示例就是完全图。无向完全图具有 n(n-1)/2 条边

2.有向图中任意两点之间都存在方向向反的两条弧，称为有向完全图；有向完全图具有 n(n-1)条弧

如示例中的有向图就不是完全图，但如果没有顶点3和指向顶点3 的边，就是一个完全图。即下图是一个完全图。

有向完全图

边树小于 nlogn 的图称为稀疏图，反之称为稠密图

E是边的有限集合

对于下面的无向图G，边 (1,2) ∈ E ,则称顶点 1 和 2 互为邻接点，即 1 和 2 相邻接

边 (1,2) 依附于顶点 1 和 2，或者说边 (1,2) 与顶点 1 和 2 相关联

顶点的度为以该顶点为一个端点的边的数目

对于无向图，顶点的边数为度，度数之和是顶点边数的两倍

对于有向图，入度是以顶点为终点（即箭头所指方向），出度是以顶点为起点 （即箭尾巴所指方向） 。

有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和

注意：入度与出度是针对有向图来说的

路径：在图中，两点间边构成的序列

在无向图中，比如图中0到6中一条路径0 -> 1 -> 3 -> 2 -> 6。一般图中两点之间的路径不止一条。这里的路径只要找到一条就返回。

对于有向图,则路径也是有向的

第一个顶点和最后一个顶点相同的路径称为回路或环

顶点不重复出现的路径称为简单路径。

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或简单环

在无向图中，两顶点有路径存在，就称为连通的。

若图中任意两顶点都连通，同此图为连通图。无向图中的极大连通子图称为连通分量。

以下面两个图为例，下面的图是上面的图的连通分量，并且下面的图是连通图。上面图中 I与J 也是连通的。

上图的两个连通分量

在有向图中，两顶点两个方向都有路径，两顶点称为强连通。若任一顶点都是强连通的，称为强连通图

有向图中极大强连通子图为有向图的强连通分量

连通图的生成树是包含图中全部顶点的一个极小连通子图，若图中有n个顶点，则生成树有n-1条边，仅有足以构成一颗树的 n-1 条边

所以对于生成树而言，若砍去一条边，就会变成非连通图，若加上一条边，则构成一个环，因为这条边使得他依附的那两个顶点之间有了第二条路径

有一个顶点的入度为0，其余顶点的入度均为1的有向图称作有向树。如下图：

有向树

一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧

略

略

图的邻接矩阵的存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息（可分别称他们为顶点数组和边数组）。

在无向图中，求某个顶点的度，即计算此顶点vi在邻接矩阵中第i行（或第i列）的元素之和。若vi到vj之间有通路，则记为1，反之为0。在有向图中，求某个顶点vi的出度，即求此顶点所在行的元素之和，若求某个顶点的度，即求顶点所在列的元素之和。

设图G有n个顶点，则邻接矩阵是一个n×n的方阵

邻接矩阵表示法的优缺点：

伪码等因为课时缩短不学，可以看下方超链接

图的存储结构伪码

对图中的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设有一个表头结点

把从一个顶点出发的所有边链接在一个单链表（又名边链表）中

把所有边链表的表头结点放在一个顺序表（又名顶点表）中

对于有向图，邻接表又称正邻接表或出度表

有向图的逆邻接表又称入度表

邻接表表示法的优缺点：

优点

缺点

创建邻接表等伪码、图的数据结构伪码

十字链表和邻接多重表跳转链接

图解图的四种存储结构

算法思想

**深度优先搜索思想：**假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

算法特点

深度优先搜索是一个递归的过程。首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。若不能继续前进，则回退一步再前进，若回退一步仍然不能前进，则连续回退至可以前进的位置为止。重复此过程，直到所有与选定点相通的所有顶点都被遍历。

深度优先遍历类似于二叉树的先序遍历

深度优先遍历通常借助栈来实现算法

图解过程

无向图深度优先搜索

以下图中所示无向图说明深度优先搜索遍历过程。

有向图深度优先搜索

以图中所示有向图说明深度优先搜索遍历过程

算法思想

**广度优先搜索思想：**从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

算法特点

广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。

广度优先遍历通常借助队列来实现算法

图解过程

无向图的广度优先搜索

图所示的无向图，采用广度优先搜索过程。

（1）选取A为起始点，输出A，A入队列，标记A，当前位置指向A。

（2）队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，将B和E入队，并标记B、E。当前位置指向A。

（3）队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。

（4）队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。

（5）队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。

（6）队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。

（7）队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。

（8）队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。

（9）队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。

（10）队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

则访问次序为：A、B、E、C、D、F、G、H

有向图的广度优先搜索

以图所示的有向图为例进行广度优先搜索。

（1）选取A为起始点，输出A，将A入队列，标记A。

（2）队列头为A，A出队列。以A为尾的边有两条，对应的头分别为B、C，则A的邻接顶点有B、C。输出B、C，将B、C入队列，并标记B、C。

（3）队列头为B，B出队列。B的邻接顶点为C，C已经被标记，因此无新元素入队列。

（4）队列头为C，C出队列。C的邻接顶点有E、F。输出E、F，将E、F入队列，并标记E、F。

（5）队列头为E，E出队列。E的邻接顶点有G、H。输出G、H，将G、H入队列，并标记G、H。

（6）队列头为F，F出队列。F无邻接顶点。

（7）队列头为G，G出队列。G无邻接顶点。

（8）队列头为H，H出队列。H邻接顶点为E，但是E已被标记，无新元素入队列。

（9）队列为空，以A为起始点的遍历过程结束，此时图中仍有D未被访问，则以D为起始点继续遍历。选取D为起始点，输出D，将D入队列，标记D。

（10）队列头为D，D出队列，D的邻接顶点为B，B已被标记，无新元素入队列。

（11）队列为空，且所有元素均被访问，广度优先搜索遍历过程结束。广度优先搜索的输出序列为：A->B->E->C->D->F->G->H。

转载于：图的两种遍历方式

案例：

DFS：首先从 1 链表开始找，找到 2 ，再根据链表2 找到 4（1已经被找到，所以跳过），然后根据链表4 找到 3，再根据链表3 找到 5 ，然后根据链表5找到6。 即：1,2,4,3,5,6

BFS：1为起始点，输出1，1入队列

队列头为1，1出队列，与1的邻接顶点为2,3.输出2,3。将2,3入队

队列头为2,2出队列，与2的邻接顶点为1,4，但是1已经输出，输出4，将4入队

队列头为3,3出队列，与3的邻接顶点为 1,4,5，但是1，4已经输出，输出5，将5入队

队列头为4,4出队列，与4的邻接顶点为2,3,6，但是2,3已经输出，输出6，将6入队

队列头为5,5出队列，与5的邻接顶点都已经输出

队列头为6,6出队列，与6的邻接顶点都已经输出

队列为空，BFS遍历结束

首先关于树的生成树：

广度：1邻接2，3，然后2邻接4,5，然后3邻接6,7，最后4邻接8

深度：1后2, 2后4, 4后8, 8后5, 5后面没有，然后返回8, 8后6， 6后3, 3后7

普利姆算法从始至终始终是一整棵树

算法的时间复杂度为O(n2)，与图中边数无关，该算法适合于稠密图

首先随意找一个顶点，一般都是v1，然后找到与v1相连的权值最小的边（若有多条，则随机选取一条），然后找与这两个点相连的有最小权值的边，然后与找这三个点相连权值最小的边，一直重复，直到有n-1条边，并且连接完所有的顶点，注意，不能形成环。

基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

时间复杂度为：O（eloge） 边数e越大，所耗费时间越长，则适合稀疏图

因为课时原因，伪码略，具体可以看超链接

最小生成树伪码

最短路径问题：如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小

以D为开头，求D到各个点的最短距离。

第1步：初始化距离，其实指与D直接连接的点的距离。dis[c]代表D到C点的最短距离，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其余为无穷大。设置集合S用来表示已经找到的最短路径。此时，S={D}。现在得到D到各点距离**{D(0)，C(3)，E（4），F（*），G（*），B（*），A(*)}**，其中*代表未知数也可以说是无穷大，括号里面的数值代表D点到该点的最短距离。

第2步：不考虑集合S中的值，因为dis[C]=3，是当中距离最短的，所以此时更新S，S={D,C}。接着我们看与C连接的点，分别有B，E，F，已经在集合S中的不看，dis[C-B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C-F]=9，dis[E]=dis[C]+dis[C-E]=3+5=8>4**(初始化时的dis[E]=4)不更新。此时{D(0)，C(3)，E（4），F（9），G（*），B（13），A(*)}。**

第3步：在第2步中，E点的值4最小，更新S={D，C，E}，此时看与E点直接连接的点，分别有F，G。dis[F]=dis[E]+dis[E-F]=4+2=6（比原来的值小，得到更新），dis[G]=dis[E]+dis[E-G]=4+8=12（更新）。此时**{D(0)，C(3)，E（4），F（6），G（12），B（13），A(*)}**。

第4步：在第3步中，F点的值6最小，更新S={D，C，E，F}，此时看与F点直接连接的点，分别有B，A，G。dis[B]=dis[F]+dis[F-B]=6+7=13，dis[A]=dis[F]+dis[F-A]=6+16=22，dis[G]=dis[F]+dis[F-G]=6+9=15>12（不更新）。此时**{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.**

第5步：在第4步中，G点的值12最小，更新S={D，C，E，F，G}，此时看与G点直接连接的点，只有A。dis[A]=dis[G]+dis[G-A]=12+14=26>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第6步：在第5步中，B点的值13最小，更新S={D，C，E，F，G，B}，此时看与B点直接连接的点，只有A。dis[A]=dis[B]+dis[B-A]=13+12=25>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第6步：最后只剩下A值，直接进入集合S={D，C，E，F，G，B，A}，此时所有的点都已经遍历结束，得到最终结果**{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.**

文字转载于：https://zhuanlan.zhihu.com/p/40338107

图转载于：https://blog.csdn.net/heroacool/article/details/51014824

伪码等也在其中

因为课时原因：跳转链接自学

弗洛伊德算法

一个无环的有向图称作为有向无环图，简称DAG图。

AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网

在AOV网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件

所谓拓扑排序就是将AOV网中所有顶点排成一个线性序列

举个例子，学习java系列的教程

就比如学习java系类(部分)从java基础，到jsp/servlet，到ssm，到springboot，springcloud等是个循序渐进且有依赖的过程。在jsp学习要首先掌握java基础和html基础。学习框架要掌握jsp/servlet和jdbc之类才行。那么，这个学习过程即构成一个拓扑序列。当然这个序列也不唯一，你可以对不关联的学科随意选择顺序(比如html和java可以随便先开始哪一个。)

那上述序列可以简单表示为：

其中五种均为可以选择的学习方案，对课程安排可以有参考作用，当然，五个都是拓扑序列。只是选择的策略不同！

规则：

图中每个顶点只出现一次。 A在B前面，则不存在B在A前面的路径。(不能成环！！！！) 顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！

拓扑排序算法分析

正常步骤为(方法不一定唯一)：

从DGA图中找到一个没有前驱的顶点输出。(可以遍历，也可以用优先队列维护) 删除以这个点为起点的边。(它的指向的边删除，为了找到下个没有前驱的顶点) 重复上述，直到最后一个顶点被输出。如果还有顶点未被输出，则说明有环！ 对于上图的简单序列，可以简单描述步骤为：

1：删除1或2，并输出

2：删除2或3以及对应边

3：删除3或者4以及对应边

4：重复以上规则步骤

这样就完成一次拓扑排序，得到一个拓扑序列，但是这个序列并不唯一！从过程中也看到有很多选择方案，具体得到结果看你算法的设计了。但只要满足即是拓扑排序序列。

另外观察 1 2 4 3 6 5 7 9这个序列满足我们所说的有关系的节点指向的在前面，被指向的在后面。如果完全没关系那不一定前后(例如1,2)

转载于：拓扑排序

AOE网：在一个表示工程的带权有向图中，用顶点表示事件（如V0），用有向边表示**活动（如 = a1），**边上的权值表示活动的持续时间，称这样的有向图为边表示的活动的网，简称AOE网（activity on edge network）

AOE网是一个带权的有向无环图

源点：

在AOE网中，没有入边的顶点称为源点；如顶点V0

终点：

在AOE网中，没有出边的顶点称为终点；如顶点V3

AOE网的性质：

【1】只有在进入某顶点的活动都已经结束，该顶点所代表的事件才发生；

​ 例如：a1和a2活动都结束了，顶点V2所代表的事件才会发生。

【2】只有在某顶点所代表的事件发生后，从该顶点出发的各活动才开始；

​ 例如：只有顶点V1所代表的事件结束之后，活动a2和a4才会开始。

在AOE网中，所有活动都完成才能到达终点，因此完成整个工程所必须花费的时间（即最短工期）应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动

事件的最早发生时间：ve[k]

从源点向终点方向计算   ve[0] = 0   ve[1] = ve[0] + a0 = 0 + 4 = 4   ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 )= 6   ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 6+4) = 10

事件的最迟发生时间：vl[k]

从终点向源点方向计算   vl[3] = ve[3] = 10   vl[2] = vl[3] - a3 = 10 - 4 = 6   vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4

vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0

活动的最早发生时间：e[i]

共有五个活动：   e[0] = ve[0] = 0   e[1] = ve[0] = 0   e[2] = ve[1] = 4   e[3] = ve[2] = 6   e[4] = ve[1] = 4

活动的最迟发生时间：el[i]

l[0] = v[1] - a0 = 4 - 4 = 0   l[1] = vl[2] - a1 = 6 - 3 = 3   l[2] = vl[2] - a2 = 6 - 2 = 4   l[3] = vl[3] - a3 = 10 - 4 = 6   l[4] = vl[3] - a4 = 10 - 6 = 4

活动的最早开始时间和最晚开始时间相等，则说明该活动时属于关键路径上的活动，即关键活动。

经过比较，得出关键活动有：a0, a2, a3, a4，因为不能有环，画出示意图如下：

该AOE网有两条关键路径。

所以，通过此案例也可以发现，一个AOE网的关键路径可能有多条。

转载于：关键路径

原博客有一点点错误，这里更改了一点：ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10 应改为：ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 6 + 4) = 10

案例：

（1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。

A．1/2 B．1 C．2 D．4

答案：C

（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。

A．1/2 B．1 C．2 D．4

答案：B

解释：有向图所有顶点入度之和等于所有顶点出度之和。

（3）具有n个顶点的有向图最多有（ ）条边。

A．n B．n(n-1) C．n(n+1) D．n2

答案：B

解释：有向图的边有方向之分，即为从n个顶点中重复选取2个顶点有序排列，结果为n(n-1)。

（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。

A．n B．2(n-1) C．n/2 D．n2

答案：B

所谓连通图一定是无向图，有向图叫强连通图

连通n个顶点,至少只需要n-1条边就可以了，由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素

（5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。

A．7 B．8 C．9 D．10

答案：C

解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。

（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。

A．非连通 B．连通 C．强连通 D．有向

答案：B

解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。

（7）下面（　）算法适合构造一个稠密图G的最小生成树。

A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法

答案：A

解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。

（8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。

A．栈 B. 队列 C. 树 D．图

答案：B

解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。

（9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。

A．栈 B. 队列 C. 树 D．图

答案：A

解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。

（10）深度优先遍历类似于二叉树的（ ）。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历

答案：A

（11）广度优先遍历类似于二叉树的（ ）。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历

答案：D

（12）图的BFS生成树的树高比DFS生成树的树高（ ）。

A．小 B．相等 C．小或相等 D．大或相等

答案：C

解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。

（13）已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果是（ ）。

​ 图6.30 邻接矩阵

答案：C

因为是深度优先,找到与顶点0直接相连的结点,由邻接矩阵知道是顶点1（多个相邻节点取第一个找到的未遍历到的结点）,然后再在邻接矩阵中找与顶点1直接相连的结点,得到顶点3.相同方法找到后续结点为：顶点4,顶点2.因为顶点2的相连结点都已被遍历,所以退回到顶点4继续遍历,遍历到顶点5,然后是顶点6

（14）已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。

图6.31 邻接表

A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3

答案：D、D

广度：访问V0，依次访问其未访问的邻接顶点（顺着链表）

深度：首先邻的结点 1，然后找到 2，然后找到 3

（15）下面（ ）方法可以判断出一个有向图是否有环

A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径

答案：B

查找表：用于查找的数据元素集合。查找表由同一类型的数据元素（或记录）构成

​ 对查找表经常进行的操作

查找表是否存在某元素

从查找表中检索某特定元素的属性

在查找表中插入一个元素

在查找表中删除一个元素

静态查找表：只做查找表是否存在某元素，从查找表中检索某特定元素的属性操作的称为静态查找表

在查找过程中只是对数据元素进行查找

动态查找表：在查找表中插入一个元素，在查找表中删除一个元素操作的称为动态查找表

在实施查找的同时，插入找不到的元素，或从查找表中删除已查到的某个元素，即允许表中元素变化

关键字： 是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，这种关键字称为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字

查找：在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功；若表中不存在关键字等于给定值的记录，则称查找不成功。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一

顺序查找的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败

顺序查找方法既适用于线性表的顺序存储结构（线性表），又适用于线性表的链式存储结构（线性链表）

下面只介绍以顺序表作为存储结构时实现的顺序查找算法

在此定义下，顺序查找算法便与第2章的算法2.2 一样。在此假设元素从 ST.R[1] 开始顺序向后存放，ST.R[0]设置为哨兵，查找时从表的最后开始比较，如下面算法所示

ST.R[0] 称为 “哨兵”。引入它的目的是使循环不用判断数组是否会越界，从而提高程序的效率

平均查找长度为： A S L = n + 1 2 ASL=\frac{n+1}{2} ASL=2n+1​

时间复杂度为：O(n)

当静态查找表的关键字有序时，可以用折半查找来实现

折半查找也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构， 而且表中元素按关键字有序排列

基本思想：key 值与中间元素比较，相等则成功；key 大则比较右半边；key 小则比较左半边

分别用low和high来表示当前查找区间的下界和 上界，mid为区间的中间位置