数据结构思维导图模板_ProcessOn思维导图、流程图

1.0绪论

1.1数据结构的基本概念

数据

数据元素

数据对象

数据类型

原子类型

其值不可再分的数据类型

结构类型

其值可以再分解为若干成分(分量)的数据类型

抽象数据类型

抽象数据组织及与之相关的操作

数据类型是一个值的集合和定义在此集合上的一组操作的总称

数据结构

逻辑结构

定义

线性结构

一般线性结构

受限线性结构

栈

队列

串

线性表推广

数组

非线性结构

集合

树形结构

一般树

二叉树

图状结构（网状结构）

有向图

无向图

存储结构

顺序存储

链式存储

索引存储

散列存储

数据的运算

1.2 算法和算法评价

1.2.1算法的基本概念

有穷性

确定性

可行性

输入

输出

优秀算法的目标

正确性

可读性

健壮性

高效率月低存储量需求

1.2.2算法效率的度量

时间复杂度

加法规则

乘法规则

常见的渐近时间复杂度为

空间复杂度

算法原地工作是指算法所需的辅助空间为常量，即 O(1)

2.0线性表

2.1线性表的定义和基本操作

2.1.1线性表的定义

概念

线性表是具有相同数据类型的 n (n>=0 ) 个数据元素的有限序列 ,其中 n 为表长，当 n = 0时线性表是一个空表

特点

1.表中元素的个数有限

2.表中元素具有逻辑上的顺序性，表中元素有其先后次序

3.表中元素都是数据元素，每个元素都是单个元素

4.表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间

5.表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容

注意

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构

2.1.2线性表的基本操作

InitList(&L)

初始化表。构造一个空的线性表

DestroyListf&L)

销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间

Listinsert (&L, i, e)

插入操作。在表 L 中的第 i 个位置上插入指定元素 e

ListDelete (&L, i, &e)

删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值

LocateElem(L,e)

按值查找操作。在表 L 中查找具有给定关键字值的元素

GetElem(L,i)

按位查找操作。获取表 L 中第 i 个位置的元素的值

Length (L)

求表长。返回线性表 L 的长度，即 L 中数据元素的个数

PrintList(L)

输出操作。按前后顺序输出线性表 L 的所有元素值

Empty (L)

判空操作。若 L 为空表，则返回 true, 否则返回 false

2.2线性表的顺序表示

2.2.1顺序表的定义

概念

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元
素，使逻辑上相邻的两个元素在物理位置上也相邻

特点

随机访问，通过首地址和元素序号可在时间 0(1) 内找到指定的元素

存储密度高，每个结点只存储数据元素

逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素

一维数组空间分配

静态分配

数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃

动态分配

存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的

C 的初始动态分配语句为:
L . data=(ElemType* ) malloc(sizeof(ElemType)*InitSize) ;

注意

动态分配是顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定

2.2.2顺序表上基本操作的实现

插入操作

在顺序表指定位置插入新元素，表中的物理位置是相邻的，插入新元素时后方元素整体都需要移动

实现情况

最好情况：在表尾插入(即 i = (n +1), 元素后移语句将不执行，时间复杂度为 O(1)

最坏情况：在表头插入(即 i=1), 元素后移语句将执行 ” 次，时间复杂度为 O(n)

平均情况

假设 (Pi = 1/(n + l)) 是在第 i 个位置上插入一个结点的概率

则在长度为n的线性表中插入一个结点时，所需移动结点的平均次数为

平均时间复杂度为 O (n)

删除操作

删除顺序表指定位置元素，操作删除元素后方元素，对想要删除的元素覆盖，后方元素整体移动

实现情况

最好情况：删除表尾元素(i = n), 元素无需移动，时间复杂度为 O(1)

最坏情况：删除表头元素(i = 1),需要移动第一个元素外的所有元素，时间复杂度为 O(n)

平均情况

假设 (Pi = 1/n) 是在第 i 个位置上删除一个结点的概率

则在长度为n的线性表中删除一个结点时，所需移动结点的平均次数为

平均时间复杂度为 O (n)

按值查找（顺序查找）

查询顺序表中第一个元素值为e的元素

实现情况

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为 0(1)

最坏情况：查找的元素在表尾(或不存在)时，需要比较n次，时间复杂度为 O(n)

平均情况

假设 (Pi = 1/n) 是查找的元素在第 i (l<=i<=L. length) 个位置上的概率

则在长度为n的线性表中查找值为 e 的元素所需比较的平均次数为

平均时间复杂度为 O (n)

2.3线性表的链式表示

2.3.1 单链表的定义

概念

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针

结构

结点结构

data为数据域，存放数据元素；next指针域，存放其后继结点的地址

头指针

标识一个单链表，指向单链表的第一个结点

头结点

单链表第一个结点之前附加一个结点，头结点的数据域可以不设任何信息，也可以记录表长等信息；头结点的指针域指向线性表的第一个元素结点

引入头结点后：链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊

引入头结点后：无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域为空),因此空表和非空表的处理也就得到了统一

优点

解决顺序表需要大量连续存储单元的缺点

插入和删除不需要移动元素，只需要修改指针

缺点

单链表附加指针域，浪费存储空间

查找某个特定的结点时，需要从表头开始遍历，依次查找

2.3.2单链表上基本操作实现

采用头插法建立单链表

思路

从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后

示意图

时间复杂度

每个结点插入的时间为 0(1), 设单链表长为n，则总时间复杂度为 O(n)

注意

采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的

采用尾插法建立单链表

思路

增加一个尾指针 r，使其始终指向当前链表的尾结点

示意图

时间复杂度

因为设置了一个指向表尾结点的指针，故时间复杂度和头插法的相同

注意

读入数据的顺序与生成的链表中的元素的顺序是一致的

按序号查找结点

思路

在单链表中从第一个结点出发，顺指针 next 域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点指针域 NULL

时间复杂度

O(n)

按值查找表节点

从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值 e, 则返回该结点的指针；若整个单链表中没有这样的结点，则返回 NULL

时间复杂度

O(n)

插入结点操作

思路:后插操作

插入结点操作将值为 x 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第 i-1 个结点，再在其后插入新结点

首先调用按序号查找算法 GetElem(L,i-1), 查找第 i-1 个结点。假设返回的第 i-1个结点为* P，然后令新结点* s的指针域指向* P的后继结点，再令结点* P的指针域指向新插入的结点 *s

示意图

实现代码段

p=GetElem(L,i-1) ; // 查找插入位置的前驱结点

s->next=p->next; //连接后继节点

p->next=s; //连接前驱节点

时间复杂度

本算法主要的时间开销在于查找第 i-1 个元素，时间复杂度为 O (n)。若在给定的结点后面插入新结点，则时间复杂度仅为 0(1)

前插操作

思路

使用后插操作，然后交换数据域

设待插入结点为*s,将*s插入到*p的前面。我们仍然将*s插入到*p的后面，然后将p->data与s->data交换，这样既满足了逻辑关系，又能使得时间复杂度为 O(1)

实现代码段

s->next=p->next; //连接后继节点

p->next=s; //连接前驱节点

temp=p->data;//交换数据域
p->data=s->data;
s->data=temp;

删除结点操作

思路

删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性，后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除

假设结点*p为找到的被删结点的前驱结点，为实现这一操作后的逻辑关系的变化，仅需修改*p的指针域，即将 *p 的指针域 next 指向* q 的下一结点

示意图

实现代码段

p=GetElem(L,i-1) ; // 查找插入位置的前驱结点

q=p->next;//令 q 指向被删除结点

p->next=q->next;//将*q从节点断开

free(q) ;//释放结点的存储空间

时间复杂度

和插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为 O(n)

扩展

思路

获取后一个结点的数据域，赋予自身，然后删除后一个节点

删除结点*p的操作可用删除*p 的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为 0(1)

代码实现

结

p->data=q->data;//用后继结点的数据域覆盖

p->next=q->next;//将*q结点从链“表断开”

free(q);//释放后继结点的存储空间

求表长操作

思路

计算单链表中数据结点(不含头结点)的个数，需要从第一个结点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加 1, 直到访问到空结点为止。

算法的时间复杂度为 O(n)

含头结点

int getLength(Node *head) { int length = 0; Node *p = head->next; while (p != NULL) { length++; p = p->next; } return length; }

不含头结点

int getLength(Node *head) { int length = 0; Node *p = head; while (p != NULL) { length++; p = p->next; } return length; }

2.3.3双链表

概念

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next,分别指向其前驱结点和后继结点

插入过程

示意图

实现代码段

删除过程

示意图

实现代码段

2.3.4循环链表

循环单链表

概念

循环单链表和单链表的区别在于，表中最后一个结点的指针不是 NULL，而改为指向头结点，从而整个链表形成一个环

判空条件

头结点是否等于头指针

有时对循环单链表不设头指针而仅设尾指针，以使得操作效率更高

循环双链表

概念

循环双链表对比循环单链表，头结点的 prior 指针还要指向表尾结点

判空条件

当循环双链表为空表时，其头结点的 prior 域和 next 域都等于L

2.3.5静态链表

概念

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next,与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组下标)，又称游标

注意

静态链表要预先分配一块连续的内存空间

静态链表以 next==-1作为其结束的标志

静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素

优点

增、删操作不需要大量移动元素

不能随机存取，只能从头结点开始依次查找，容量固定不变

适用场景

不支持指针的低级语言

数据袁术数量固定不变的场景（操作系统的文件分配表FAT）

2.3.6顺序表和链表的比较

比较

存取(读写)方式

顺序表可以顺序存取，也可以随机存取

链表只能从表头顺序存取元素

逻辑结构与物理结构

顺序存储：逻辑上相邻的元素，对应的物理存储位置也相邻

链式存储：逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的

查找、插入和删除操作

按值查找

顺序表有序：可采用折半查找，此时的时间复杂度为

顺序表无序：两者的时间复杂度均为O(n)

按序号查找

顺序表支持随机访问，时间复杂度仅为 O (1)

链表的平均时间复杂度为O(n)

插入、删除

顺序表：平均需要移动半个表长的元素

链表：只需修改相关结点的指针域即可

缺点:由于链表的每个结点都带有指针域，故而存储密度不够大

空间分配

顺序存储

静态分配：存储空间装满就不能扩充，会出现内存溢出

动态分配：需要移动大量元素，操作效率降低

链式存储

空间分配灵活高效

存储结构的选择

基于存储的考虑

难以估计线性表的长度或存储规模时，不宜采用顺序表

链表不用事先估计存储规模，但链表的存储密度较低

基于运算的考虑

按序号访问数据元素——顺序表优于链表

插入、删除操作——链表优于顺序表

基于环境的考虑

顺序表基于数组类型，容易实现

链表基于指针，部分编程语言不适合（例如：Java、Python）

3.0栈、队列和数组

3.1栈(Stack)

3.1.1栈的基本概念

概念

只允许在一端进行插入或删除操作的线性表

栈顶 ( Top) ：线性表允许进行插入删除的那一端

栈底 ( Bottom) : 固定的,不允许进行插入和删除的另一端

空栈 : 不含任何元素的空表

栈的基本操作

InitStack(&S) : 初始化一个空栈 S

StackEmpty (S) : 判断一个栈是否为空，若栈 S 为空则返回 true, 否则返回 false

Push (&S, x) : 进栈，栈 S 未满，则将 x 加入使之成为新栈顶

Pop(&S,&x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回

GetTop(S,&x) ：读栈顶元素，若栈 S 非空，则用 x 返回栈顶元素

DestroyStack(&S) ：销毁栈，并释放栈 S 占用的存储空间 ( "& ” 表示引用调用)

特性

后进先出；n 个不同元素进栈，出栈元素不同排列的个数为

3.1.2栈的顺序存储结构

1.顺序栈的实现

概念

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针 (top) 指示当前栈顶元素的位置

基本结构与操作

#define Elemtype int
#define MaxSize 50
typedef struct {
Elemtye data[MaxSize];
int top;
}SqStack;

栈顶指针：S->top,初始化S->top=-1

栈顶元素：S->data[S.top]

进栈操作：栈不满时，栈顶指针先加 1, 再送值到栈顶元素

出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减 1

栈空条件： S-> top==-1 ；栈满条件： S->top==MaxSize-1；栈长： S->top+1

2.顺序栈的基本运算

初始化

void InitStack(SqStack *S) { S->top = -1; //初始化指针 }

判栈空

bool StackEmpty(SqStack *S) {
    if (S->top == -1) {     //栈空
        return true;
    }
    else //栈不空
    {
        return true;
    }
}

进栈

//进栈
bool Push(SqStack *S,Elemtype x){
    if (S->top == MaxSize - 1)      //栈满
        return false;
    S->data[++S->top] = x;          //指针先+1，然后入栈
    return true;
}

出栈

//出栈
bool Pop(SqStack* S, Elemtype *x) {
    if (S->top == -1)              //栈空
        return false;
    *x=S->data[S->top--];          //先出栈，然后指针-1
    return true;
}

读取栈顶元素

//读栈顶元素
bool GetTop(SqStack* S, Elemtype *x) {
    if (S->top == -1) //栈空
        return false;
    *x=S->data[S->top];          //x记录栈顶元素
    return true;
}

3.2队列（Queue）

3.2.1队列的基本概念

概念

一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除

队头 ( Front) ：允许删除的一端，又称队首

队尾 ( Rear) ：允许插入的一端

空队列：不含任何元素的空表

队列的基本操作

InitQueue (&Q) : 初始化队列，构造一个空队列 Q

QueueEmpty (Q) ：判队列空，若队列 Q 为空返回 true, 否则返回 false

EnQueue (&Q, x) ：入队，若队列 Q 未满，将 x 加入，使之成为新的队尾

DeQueue (&Q, &x) ：出队，若队列 Q 非空，删除队头元素，并用 x 返回

GetHead(Q,&x) ：读队头元素，若队列 Q 非空，则将队头元素赋值给 X

3.2.2 队列的顺序存储结构

队列的顺序存储结构

概念

分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置

基本结构域操作

#define ElemTpye int //定义队列中元素的最大个数
#define MaxSize 50
typedef struct {
ElemTpye date[MaxSize]; //存放队列元素
int front, rear; //对头指针和队尾指针
}SqQueue;

初始时：Q->front=Q->rear=0

进队操作：队不满时，先送值到队尾元素，再将队尾指针加 1

出队操作：队不空时，先取队头元素值，再将队头指针加 1

假溢出

Q->rear==MaxSiz并不能作为判断队列满的条件

队列中仅有一个元素，但仍满足该条件。这时入队出现“ 上溢出 ”，但这种溢出并不是真正的溢出，在data 数组中依然存在可以存放元素的空位置，所以是一种“ 假溢出 ”

循环队列

概念

把存储队列元素的表从逻辑上视为一个环，称为循环队列

基本操作

初始时： Q->f ront=Q ->rear=0

队首指针进 1 : Q->front= (Q->front+1 ) %MaxSize

队尾指针进 1 : Q->rear=(Q->rear+1 ) %MaxSize

队列长度: ( Q->rear+MaxSize - Q->front ) %MaxSize

队空队满情况

牺牲一个单元来区分队空和队满，约定以“ 队头指针在队尾指针的下一位置作为队满的标志”

队满：(Q->rear+1) %MaxSize==Q->front

队空：Q->front==Q->rear

类型中增设表示元素个数的数据成员

队满Q->size==MaxSize

队空: Q->size==0

类型中增设 tag 数据成员

队空：tag==0时，因删除导致Q->front==Q->rear

队满：tag==1时，因插入导致Q->front==Q->rear

基本运算实现

初始化

//初始化 void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; //初始化首尾指针 }

判队空

//判队空——牺牲一个单元
bool QueueEmpty(SqQueue* Q) {
if (Q->front == Q->rear) //队空条件
return true;
else
return false;
}

//判队空——增加表示元素个数的数据成员 bool QueueEmpty(SqQueue* Q) { if (Q->size==0) //队空条件 return true; else return false; }

//判队空——牺牲一个单元 bool QueueEmpty(SqQueue* Q) { if (Q->front == Q->rear && Q->tag==1) //队空条件 return true; else return false; }

入队

//入队【牺牲一个单元】
bool EnQueue(SqQueue *Q,ElemTpye x) {
if ((Q->rear + 1) % MaxSize == Q->front) return false; // 队满则报错
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxSize; //队尾指针加 1 取模
return true;
}

出队

//出队【牺牲一个单元】 bool DeQueue(SqQueue *Q,ElemTpye x){ if(Q->front == Q->rear) return false; //对空报错 x = Q->data[Q->front]; Q->front = (Q->front + 1) % MaxSize; //队头指针加 1 取模 return true; }

3.2.3 队列的链式存储结构

概念

一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点；当 Q->front==NULL 且 Q->rear==NUL 时，链式队列为空

优点

队列的链式表示不存在队列满且溢出的问题，适合数据元素变动比较大的情形

3.2.4 双端队列

概念

双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构

分类

两端都可以入队和出队

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列

3.3 栈和队列的应用

331 栈在括号匹配中的应用

算法的思想如下： 1 ）初始设置一个空栈，顺序读入括号。 2 ）若是右括号，则或使置于栈顶的最急迫期待得以消解，或是不合法的情况（括号序列不匹配，退出程序）。 3 ）若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性降了一级。算法结束时，栈为空，否则括号序列不匹配

3.3.2 栈在表达式求值中的应用

中缀表达式

直观的数学表达式

后缀表达式，运算符入栈，遇到同级别或者更小的运算符既出栈，并弹出两个元素计算

具体还是看王道视频课程

前缀表达式

3.3.3 栈在递归中的应用

递归

递归调用时，函数调用栈可称为“递归工作栈”

每进入一层递归，就将递归调用所需信息压入栈顶

没退出一层递归，就从栈顶弹出相应的信息

3.3.4 队列在层次遍历中的应用

参考“树”章节

3.3.5 队列在计算机系统中的应用

解决主机与外部设备之间速度不匹配的问题

利用队列先进先出的性质，实现对打印机与主机速度不匹配的协调功能

解决由多用户引起的资源竞争问题

将多个用户排成一个队列，利用先进先出的性质，将CPU分配给不同的用户使用

3.4 数组和特殊矩阵

3.4.1 数组的定义

定义

数组是由n(n>=1) 个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界

数组与线性表的关系

数组是线性表的推广

一维数组可视为一个线性表

二维数组可视为其元素也是定长线性表的线性表

数组一旦被定义，其维数和维界就不再改变。因此,除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作

3.4.2 数组的存储结构

概念

逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间

一维数组

二维数组（多维）

3.4.3 特殊矩阵的压缩存储

对称矩阵

上三角区的所有元素和下三角区的对应元素相同

三角矩阵

三对角矩阵

3.4.4 稀疏矩阵

定义

矩阵中非零元素的个数t,相对矩阵元素的个数 s 来说非常少，即s>>t的矩阵称为稀疏矩阵。
例如，一个矩阵的阶为 100x100, 该矩阵中只有少于 100 个非零元素

存储方式

将非零元素及其相应的行和列构成一个三元组(行标，列标，值)

注意

稀疏矩阵压缩存储后便失去了随机存取特性

4.0串

*4.1 串的定义和实现

4.1.1 串的定义

串（ string ）是由零个或多个字符组成的有限序列。一般记为

S 是串名，单引号括起来的字符序列是串的值；％可以是字、数字或其他字符；串中字符的个数n称为串的长度。n=0 时的串称为空串

子串

串中任意多个连续的字符组成的子序列称为该串的子串

主串

包含子串的串称为主串

4.1.2 串的存储结构

位置

某个字符在串中的序号称为该字符在串中的位置

4.1.2 串的存储结构

定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列

代码实现

#define MaxSize 50 //预定义最大字符个数 typedef struct { char ch[MaxSize]; //每个分量存储一个字符 int length; //串的实际长度 }SString;

截断

串的实际长度只能小于或等于 MAXLEN, 超过预定义长度的串值会被舍去，称为截断

串长的表示

用额外的变量length表示

在串值后面加一个不计入串长的结束标记字符 "\0 ”

堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的

代码实现

typedef struct { char *ch; //每个分量存储一个字符 int length; //串的实际长度 }HString;

块链存储表示

每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构

示意图

4.1.3 串的基本操作

StrAssign (&T, chars) ：赋值操作。把串 T 赋值为 chars

StrCopy (&T, S) : 复制操作。由串 S 复制得到串 T

StrEmpty(S) : 判空操作。若 S 为空串，则返回 TRUE, 否则返回 FALSE

StrCompare (S,T) :比较操作。若 S>T, 则返回值 >0; 若 S=T, 则返回值 =0; 若 S<T,则返回值 <0

StrLength (S) ：求串长。返回串 S 的元素个数

SubString (&Sub, S,pos, len) : 求子串。用 Sub 返回串 S 的第 pos 个字符起长度为len 的子串

Concat(&T,Sl,S2) ：串联接。用 T 返回由 S1 和 S2 联接而成的新串

Index (S,T) ：定位操作。若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为 0

ClearString (&S) : 清空操作。将 S 清为空串

DestroyString (&S) ：销毁串。将串 S 销毁

4.2 串的模式匹配

4.2.1 简单的模式匹配算法

概念

子串的定位操作通常称为串的模式匹配，它求的是子串(常称模式串)在主串中的位置

算法思想

将主串中与模式串长度相同的子串“取出”，逐个与模式串对比，当子串与模式串某个对应字符不匹配时，就立即放弃当前子串

缺点：主串指针会回溯，导致时间开销增加，最坏时间复杂度：O(nm),其中n和m分别为主串和模式串的长度

4.2.2 串的模式匹配算法——KMP 算法

基本概念

前缀

除最后一个字符以外，字符串的所有头部子串

后缀

除第一个字符外，字符串的所有尾部子串

部分匹配

字符串的前缀和后缀的最长相等前后缀长度

时间复杂度

O(m+n)

优点

主串不会进行回溯

4.2.3 KMP 算法的进一步优化

在KMP的基础上，计算出 next[ ] 数组后，在next[ ]数组中，若子串的前缀中，前部分有与失败子串位置的字符前字符相同，则可以回溯到重复的字符next[ ]值中

5.0树与二叉树

5.1 树的基本概念

5.1.1 树的定义

树是一种逻辑结构，也是一种分层结构

树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱

树中所有结点都可以有零个或多个后继

在n个结点的树中有（n-1）条边

5.1.2 基本术语

示意图

考虑结点 K

结点 K 的祖先：根 S 到结点 K 的唯一路径上的任意结点

子孙：结点 B 是结点 K 的祖先，而结点 K 是结点 B 的子孙

双亲与孩子：路径上最接近结点 K 的结点 E 为双亲，而 K 为 E 的孩子结点

兄弟：有相同双亲的结点

结点的度：树中一个结点的孩子个数，树中结点的最大度数称为树的度

分支结点：度大于0的结点

叶子结点：度为0的结点

结点的层次：从树根开始定义，根结点为第1层

结点的深度：从根结点开始自顶向下逐层累加

结点的高度：从也结点开始自底向上逐层累加

树的高度（深度）：树种节点的最大层数

有序树和无序树：树种结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树

路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数

森林：森林是 n(n>0) 棵互不相交的树的集合

5.1.3 树的性质

树中的结点数等于所有结点的度数之和加 1

度为 m 的树中第 i 层上至多有 m'T 个结点（ i^Do

高度为 h 的 m 叉树至多有

具有 n 个结点的 m 叉树的最小高度为

5.2 二叉树的概念

5.2.1 二叉树的定义及其主要特性

二又树的定义

二叉树是n（ n>=0）个结点的有限集合

空二叉树，即 "=0

由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树

二叉树与度为 2 的有序树的区别

度为 2 的树至少有 3 个结点，而二叉树可以为空

度为 2 的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子,则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为 2, 均需确定其左右次序

特殊的二叉树

满二叉树

一棵高度为h,且含有 2^h- 1 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点

对于编号为 i 的结点

可以对满二叉树按层序编号：约定编号从根结点（根结点编号为 1 ）起，自上而下，自左向右

若有双亲，则其双亲为

若有左孩子，则左孩子为 2 i

有右孩子，则右孩子为 2i+1

完全二叉树

高度为h有n个结点的二叉树，当且仅当其每个结点都与高度为介的满二叉树中编号为 1 〜 n的结点一一对应时，称为完全二叉树

特点

则结点 i 为分支结点，否则为叶结点

叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上

若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）

按层序编号后，一旦出现某结点（编号为 i ）为叶结点或只有左孩子，则编号大于 i 的结点均为叶结点

若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为 n/2 ）只有左孩子，没有右孩子，其余分支结点左、右孩子都有

二叉排序树

左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字

左子树和右子树又各是一棵二叉排序树

平衡二叉树

树上任意一个结点的左子树和右子树的深度之差不超过 1

二叉树的性质

非空二叉树上的叶结点数等于度为 2 的结点数加 1

非空二叉树上第k层上至多有 2^k-1 个结点（K>=1）

高度为 h 的二叉树至多有 2^h - 1 个结点(h>=1)

对完全二叉树按从上到下、从左到右的顺序依次编号 1,2, •••,n, 则有以下关系

当 2i<=n 时，结点 i 的左孩子编号为 2i, 否则无左孩子

当 27+1<=n 时，结点 i 的右孩子编号为 2i + 1, 否则无右孩子

结点 i 所在层次（深度）为

具有n个（ n>0 ）结点的完全二叉树的高度为

5.2.2 二叉树的存储结构

顺序存储结构

用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为的结点元素存储在一维数组下标为的分量中

完全二叉树和满二叉树采用顺序存储比较合适

注意：这种存储结构建议从数组下标 1 开始存储树中的结点

链.式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点

代码实现

typedef struct {
ElemTpye data; //数据域
struct BiTNode* lchild, * rchild; //左右孩子指针
}BiTNode,*BiTree;

注意

在含有n个结点的二叉链表中，含有 n + 1 个空链域

5.3 二叉树的遍历和线索二叉树

5.3.1 二叉树的遍历

概念

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次

先序遍历

操作过程

访问根结点

先序遍历左子树

先序遍历右子树

代码实现

//先序遍历
void PreOrder(BiTree T){
if (T != NULL) {
  Visit(T);    //访问根结点
  PreOrder(T->lchild); //遍历左子树
  PreOrder(T->rchild); //遍历右子树
}
}

中序遍历

操作过程

先序遍历左子树

访问根结点

先序遍历右子树

代码实现

//中序遍历
void InOrder(BiTree T){
if (T != NULL) {
  PreOrder(T->lchild); //遍历左子树
Visit(T);    //访问根结点
  PreOrder(T->rchild); //遍历右子树
}
}

后序遍历

操作过程

先序遍历左子树

先序遍历右子树

访问根结点

代码实现

//后序遍历
void PostOrder(BiTree T){
if (T != NULL) {
  PreOrder(T->lchild); //遍历左子树
  PreOrder(T->rchild); //遍历右子树
Visit(T);    //访问根结点
}
}

递归算法和非递归算法的转换

先续遍历

中序遍历

后续遍历

层次遍历

示意图

实现原理

要进行层次遍历，需要借助一个队列。首先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队完成入队后出队，访问出队结点 … … 如此反复，直至队列为空

代码实现

由遍历序列构造二叉树

由二叉树的“先序序列”和“中序序列”可以唯一地确定一棵二叉树

由二叉树的“后序序列”和“中序序列”也可以唯一地确定一棵二叉树

5.3.2 线索二叉树

线索二叉树的基本概念

概念

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

代码实现

结构

规定：若无左子树，令 Ichild 指向其前驱结点；若无右子树，令 rchild 指向其后继结点

typedef struct ThreadNode{
ElemType data; // 数据元素
struct ThreadNode* lchild, * rchild; //左、右孩子指针
int Itag, rtag; // 左、右线索标志
} ThreadNode, * ThreadTree;

中序线索二叉树的构造

概念

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树

中序线索二叉树的建立

附设指针 pre 指向刚刚访问过的结点，指针 p 指向正在访问的结点，即 pre 指向 p 的前驱

在中序遍历的过程中

检查 p 的左指针是否为空，若为空就将它指向 pre

检查 pre 的右指针是否为空，若为空就将它指向 p

通过中序遍历对二叉树线索化的递归算法如下：

通过中序遍历建立中序线索二叉树的主过程算法如下:

先序线索化

后续线索化

中序线索二叉树的遍历

若其右标志为 "1 ” ，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点(右子树中最左下的结点)为其后继

求中序线索二叉树中中序序列下的第一个结点：

求中序线索二叉树中结点 p 在中序序列下的后继：

对中序线索二叉树进行中序遍历

5.4 树、森林

5.4.1 树的存储结构

双亲表示法

概念

这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。根结点下标为0, 其伪指针域为 -1

示意图

代码实现

优点

利用了每个结点（根结点除外），只有唯一双亲的性质，可以很快的找到每个结点的双亲结点

缺点

求结点的孩子时则需要遍历整个结构

孩子表示法

概念

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表(叶结点的孩子链表为空表)

示意图

优点

寻找子女的操作非常直接

缺点

而寻找双亲的操作需要遍历 n 个结点中孩子链表指针域所指向的n个孩子链表

孩子兄弟表示法

概念

以二叉链表作为树的存储结构，孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指，以及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)

示意图

树第一个孩子变为二叉树的左孩子，兄弟指针变为第一个孩子结点的右孩子，下一个兄弟为前一个兄弟的右孩子

优点

可以方便地实现树转换为二叉树的操作，易于查找结点的孩子

缺点

从当前结点查找其双亲结点比较麻烦（若为每个结点增设一个 parent域指向其父结点，则查找结点的父结点也很方便）

5.4.2 树、森林与二叉树的转换

树转化为二叉树规则

每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟（左孩子右兄弟）

森林转化为二叉树规则

将森林中的每棵树转换成相应的二叉树，每棵树的根也可视为兄弟关系

二叉树转化为森林

二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形
式，故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树,
应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二叉树依次转换成
树，就得到了森林（二叉树转换为树或森林是唯一的。）

5.4.3树和森林的遍历

先根遍历

若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵
循先根后子树的规则
其遍历序列与这棵树相应二叉树的“先序序列”相同

后根遍历

若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵
循先子树后根的规则
其遍历序列与这棵树相应二叉树的“中序序列”相同

示意图

注意：部分教材也将森林的中序遍历称为后序遍历，称中序遍历是相对其二叉树而言的，称后序遍历是因为根确实是最后才访问的，如遇到这两种称谓，那么都可以理解为同一种遍历方法。

5.5 树与二叉树的应用

5.5.1 哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义

概念

在含有 n 个带权叶结点的二叉树中，其中带权路径长度（ WPL ）最小的二叉树称为哈夫曼树，也称最优二叉树

带权路径长度
Wi 是第i个叶结点所带的权值， Li是该叶结点到根结点的路径长度

2. 哈夫更树的构造

构造原理

构造一个新结点，选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和（新的数作为一个子树重复上叙操作）

特点

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。

构造过程中共新建了 n-1 个结点（双分支结点），因此哈夫曼树的结点总数为 2n-1

每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点

3. 哈夫曼编码

将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为 0 表示“转向左孩子 ”，标记为 1 表示“转向右孩子”

字符集中的每个结点都要作为一个叶子结点，各个字符出现的频度作为结点的权值

示意图

前缀编码

没有一个编码是另一个编码的前缀（不会重复的编码集合）

5.5.2 并查集

基本实现思路

基本操作

Initial (S)

将集合 S 中的每个元素都初始化为只有一个单元素的子集合

Union (S, Rootl , Root2 )

把集合 S 中的子集合 Root2 并入子集合 Rootlo 要求 Rootl 和 Root2 互不相交，否则不执行合并

优化后的Union操作

Find(S,x)

查找集合 S 中单元素 x 所在的子集合，并返回该子集合的根结点

6.0图

6.1 图的基本概念

6.1.1 图的定义

图 G 由顶点集 V 和边集 E 组成，记为 G =（ V,E ） , 其中V（G ）表示图 G 中顶点的有限非空集;
E（G）表示图 G 中顶点之间的关系（边）集合。若 V={ v 1，v 2 ,……, vn}＞则用 |V| 表示图 G 中顶点的个
数， E={ （ u, v ） |u属于V，v属于V＞用 |E| 表示图 G 中边的条数

注意

线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点
也没有，图的顶点集 V一定非空，但边集 E 可以为空，此时图中只有顶点而没有边

图的基本概念及术语

1.有向图

若 E 是有向边(也称弧)的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 <v,w>,
其中 v, w 是顶点，v 称为弧尾，w 称为弧头， <v, w> 称为从 v 到 w 的弧，也称 v 邻接到 w 。

示例图

1.

2.

2.无向图

若 E 是无向边(简称边)的有限集合时，则图 G 为无向图。边是顶点的无序对，记为 (v, w)
或 ( w, v ) 。可以说 w 和 v 互为邻接点。边 ( v, w ) 依附于 w 和 v, 或称边 ( v, w ) 和 v, w 相关联

示例图

1.

2.

3. 简单图、多重图

简单图

一个图 G 如果满足： ①不存在重复边； ②不存在顶点到自身的边，那么称图 G 为简单图

多重图（非核心）

若图 G 中某两个顶点之间的边数大于 1 条，又允许顶点通过一条边和自身关联，则称图 G 为多重图

4. 完会图(也称简单完全图)

完全无向图

对于|E|的取值范围为 0 到 n (n- 1)/2, 有 n(n-1)/2条边的无向图为“完全无向图”

完全有向图

对于|E|的取值范围为 0 到 n (n- 1), 有 n(n-1)条弧的有向图为“完全有向图”

5. 子图

设有两个图 G = (V,E) 和 G' = (V',E'), 若V'是V的子集，且 E" 是 E 的子集，则称 G' 是 G 的
子图。若有满足 V(G') = V(G) 的子图 G', 则称其为 G 的生成子图

6 . 连通、连通图和连通分量

连通

在无向图中，若从顶点 V 到顶点 W 有路径存在，则称 V 和 W 是连通的。

连通图

若图 G 中任意两个顶点都是连通的，则称图 G 为连通，否则称为非连通图

有路径，未必有弧

连通分量

无向图中的极大连通子图称为连通分量

示意图

7. 强连通图、强连通分量

强连通

有向图中，如果有两个顶点互相都有指向的路径，则称这两个顶点是强连通的

强连通图

若图中任何一对顶点都是强连通的，则称此图为强连通图

强连通分量

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

8. 生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n-1 条边

9. 顶点的度、入度和出度

无向图

顶点 v 的度是指依附于顶点 v 的边的条数，记为 TD(v)

全部顶点的度的和等于边数的 2 倍，因为每条边和两个顶点相关联。

有向图

入度

入度是以顶点 v 为终点的有向边的数目，记为 ID(v)

出度

出度是以顶点 v 为起点的有向边的数目，记为 OD(v

10. 边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

11. 稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密
图常常是相对而言的。一般当图 G 满足|E| ＜ |V| log |V| 助时，可以将 G 视为稀疏图

12. 路径、路径长度和回路

路径

顶点 Vp 到顶点 Vq 之间的一条路径是指顶点序列 Vp, Vi1 , Vi2 , ... , Vim , Vq , 当然关联的边也可理解为路径的构成要素

路径长度

路径上边的数目称为路径长度

回路

第一个顶点和最后一个顶点相同的路径称为回路或环
若一个图有n个顶点，并且有大于 n -1 条边，则此图一定有环

13. 简单路径，简单回路

简单路径

在路径序列中，顶点不重复出现的路径称为简单路径

简单回路

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

14. 距离

从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。
若从 u 到 v 根本不存在路径，则记该距离为“无穷”

15. 有向树

一个顶点的入度为 0 、其余顶点的入度均为 1 的有向图，称为有向树

6.2 图的存储及基本操作

6.2.1领接矩阵法

概念

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵

构成

代码实现

#define MaxVertexNum 100       //顶点数目最大值
typedef char VertexType;       //顶点数据类型
typedef int EdgeType;        //带权图中边上权值的数据类型
typedef struct {
VertexType Vex[MaxVertexNum];     //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum];  //领接矩阵边表
int vexnum, arcnum;        //图的当前顶点数和弧数
}MGraph;

邻接矩阵表示法的空间复杂度为 O(n^2 ), 其中 n 为图的顶点数|V|

特点

1.无向图的邻接矩阵一定是一个对称矩阵(并且唯一) 。因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素

2.对于无向图，邻接矩阵的第 i 行(或第 i 列)非零元素(或非 “无穷” 元素)的个数正好是顶点 i 的度 TD(vi)

3.对于无向图，邻接矩阵的“第 i 行”非零元素(或非 “无穷” 元素)的个数正好是顶点 i 的 “出度 OD(vi)”，
“第 i 列”非零元素(或非 “无穷” 元素)的个数正好是顶点 i 的 “入度 ID(vi)”

4.用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图
中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大

5.稠密图适合使用邻接矩阵的存储表示

6.2.2 邻接表法

概念

每个顶点 Vi建立一个单链表，第 i 个单链表中的结点表示依附于顶点 Vi的边(对于有向图则是以顶点 Vi 为尾的弧) ，这个单链表就称为顶点 Vi的边表(对于有向图则称为出边表) 。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)

结构图

顶点表

边表

无向图

有向图

代码实现

#define MaxVertexNum 100       //图中顶点数目最大值
typedef char VertexType;       //顶点数据类型
typedef int InfoType;        //带权图中边上权值的数据类型

typedef struct ArcNote{        //边表结点
int adjvex;          //该弧所指向的顶点的位置
ArcNote *next;         //指向下一条弧的指针
//InfoType info;        //网的边权值
}ArcNote;

typedef struct VNote{        //顶点表结点
VertexType date;        //顶点信息
ArcNote* next;         //指向下一条依附该顶点的指针
}VNote,AdjList[MaxVertexNum];

typedef struct {
AdjList vertices;        //邻接表
int vexnum, arcnum;        //图的当前顶点数和弧数
}ALGraph;           //ALGraph 是以邻接表存储的图类型

特点

1. 若 G 为无向图，则所需的存储空间为 O（|V|+ 2 |E| ）；若 G 为有向图，则所需的存储空间为O（|V|+|E| ）。前者的倍数 2 是由于无向图中，每条边在邻接表中出现了两次

2. 对于稀疏图，采用邻接表表示将极大地节省存储空间

3. 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表

4. 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表

5. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序

6.2.3 十字链表

概念

十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一结点

结构

弧结点域结构

尾域（tilvex）：弧尾

头域（headvex）：弧头

链域（hink）：指向弧头相同的下一条弧

链域（tink）：指向弧尾相同的下一条弧

info域：指向弧的相关信息

顶点结点域结构

data域：存放该顶点的数据信息

firstin域：指向以该顶点为弧头的第一个弧结点

fristout域：指向以该顶点为弧尾的第一个弧结点

注意

顶点的结点之间是顺序存储的

6.2.4 邻接多重表

概念

邻接多重表是无向图的另一种链式存储结构

结构

弧结点域结构

ivex 和 jvex 这两个域指示该边依附的两个顶点的编号

ilink 域指向下一条依附于顶点 ivex 的边

jlink 域指向下一条依附于顶点 jvex 的边

info 域存放该边的相关信息

顶点结点域结构

data 域存放该顶点的相关信息

firstedge 域指向第一条依附于该顶点的边

6.2.5 图的基本操作

Adjacent （ G, x, y ） : 判断图 G 是否存在边< x , y > 或（ x , y ）

Neighbors (G, x) : 列出图 G 中与结点 x 邻接的边

Insertvertex (G, x) : 在图 G 中插入顶点 x

DeleteVertex (G, x) : 从图 G 中删除顶点 x

AddEdge (G, x, y) ：若无向边 (x,y) 或有向边< x , y >不存在，则向图 G 中添加该边

RemoveEdge (G, x, y) : 若无向边 (x,y) 或有向边< x , y >存在，则从图 G 中删除该边

FirstNeighbor (G, x) ：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x, 则返回 -1

NextNeighbor (G, x, y) : 假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 外顶点
x 的下一个邻接点的顶点号，若y是 x 的最后一个邻接点，则返回 -1

Get_edge_value (G, x, y) ：获取图 G 中边< x , y > 或（ x , y ）对应的权值

Set_edge_value (G, x, y, v) : 设置图 G 中边< x , y > 或（ x , y ）对应的权值为 V

6.3 图的遍历

6.3.1 广度优先搜索BFS

实现

概念

类似于二叉树的层序遍历算法

实现思想

1.先访问起始顶点 v, 接着由 v 出发，依次访问 v 的各个未访问过的邻接顶点w1,w2,w3 ...... ,wi

2.后依次访问 w1,w2,w3 ...... ,wi 的所有未被访问过的邻接顶点

3.再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止

代码实现

BFS 算法的柱能分析

时间复杂度

邻接表存储方式

顶点：O( |V| )

边：O( |E| )

邻接矩阵存储方式

顶点：O( |V| )

总复杂度O( |V|^2 )

空间复杂度

无论是邻接表还是邻接矩阵的存储方式， BFS 算法都需要借助一个辅助队列 Q, n 个顶点均
需入队一次，在最坏的情况下，空间复杂度为O( |V| )

BFS 算法求解单源最短路径问题

思想

若图 G = (V, E) 为非带权图，定义从顶点 u 到顶点 v 的最短路径 d(u, v) 为从 u 到 v 的任何路径
中最少的边数；若从 u到 v 没有通路，则 d( u ,v)=∞

代码实现

广度优先生成树

1.在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树

2.同一个图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的

3.邻接表存储表示不唯一，故其广度优先生成树也是不唯一的

6.3.2 深度优先搜索DFS

实现

类似于树的先序遍历；

代码实现

DFS 算法的性能分析

时间复杂度

邻接表

顶点：O( |V| )

边：O( |E| )

邻接矩阵

顶点：O( |V| )

总复杂度O( |V|^2 )

空间复杂度

DFS 算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为 O( |V| )

深度优先的生成树和生成森林

1.广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树

2.对连通图调用 DFS 才能产生深度优先生成树，否则产生的将是深度优先生成森林

3.基于邻接表存储的深度优先生成树是不唯一

6.4 图的应用

最小生成树

Prim算法（普里姆）

实现过程（图片）

1.

2.

3.

4.

时间复杂度O( |V|^2 )

计算结果示意图

适合稠密图

Kruskal算法（克鲁斯卡尔）

实现过程（图片）

1.将边按照权值大小排序

2.循环遍历每条边，判断两个顶点是否连通，是否同属于一个集合

时间复杂度O( log2 e )

计算结果示意图

适合稀疏图

单源最短路径

BFS算法（无权图）

实现（图片）

1.

2.

Dijkstra 算法

实现（图片）

1.

2.

3.

4.

时间复杂度O( |V|^2 )

计算结果示意图

各顶点间的最短路径

Floyd 算法

实现思想

实现（图片）

1.

2.

3.

时间复杂度O( |V|^3 )

空间复杂度O( |V|^2 )

有无向图表达式

计算（图片）

个人理解计算

结点（变量，去重）+ 需要计算的符号 - 相同变量和计算方式的数量

拓扑排序

示意图（图片，代码）

深度优先算法 - 实现逆拓扑排序

概念

AOV网：顶点表示活动，以有向边表示事件

关键路径

概念

AOE网：顶点表示事件，以有向边表示活动

示意图

事件Vk的最早发生时间 Ve(k)

事件Vk的最迟发生时间讨 Vl(k)

活动ai的最早开始时间 e(i)

活动ai的最迟开始时间 l(i)

一个活动 ai 的最退开始时间 l(i) 和其最早开始时间 e(i) 的差额 d(i) = l(i) - e(i)

注意

关键活动：l(i) - e(i) = 0, 即l(i) = e(i) 的活动 ai 是关键活动

7.0查找

7.1 查找的基本概念

查找

查找成功：即在数据集合中找到了满足条件的数据元素

查找失败

查找表（查找结构）

静态查找表

关键字

平均查找长度

概念

在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值

n 是查找表的长度

Pi是查找第 i 个数据元素的概率

Ci是找到第 i 个数据元素所需进行的比较次数

7.2 顺序查找和折半查找

7.2.1 顺序查找

概念

顺序查找又称线性查找，它对顺序表和链表都是适用

顺序表：通过数组下标递增来顺序扫描每个元素

链表：通过指针 next 来依次扫描每个元素

代码实现

顺序表结构

#include<stdio.h>
#define Elemtype int

typedef struct {   //查找表数据结构（顺序表）
Elemtype* elem;   //动态数组地址
int Tablelen;   //表的长度
}SSTable;

从前往后

//顺序查找-从前往后
int Search_Seq1(SSTable *ST,Elemtype key) {
int i;
for (i = 0; i < ST->Tablelen && ST->elem[i]!=key; i++);
return i == ST->Tablelen ? -1 : i; //查找成功-返回元素下标，查找失败-返回-1
}

从后往前

//顺序查找-从前往后
int Search_Seq1(SSTable *ST,Elemtype key) {
int i;
for (i = 0; i < ST->Tablelen && ST->elem[i]!=key; i++);
return i == ST->Tablelen ? -1 : i; //查找成功-返回元素下标，查找失败-返回-1
}

平均查找长度

1.

2.

时间复杂度O(n)

7.2.2 折半查找

概念

折半查找又称二分查找，它仅适用于有序的顺序表

代码实现

折半查找-有序的顺序表(升序)

int Half_Seq(SSTable* ST, Elemtype key) {
int low=0, high = ST->Tablelen - 1,mid;
while (low<=high)
{
  mid = (low + high) / 2;
  if (ST->elem[mid] == key)
   return mid;
  else if (ST->elem[mid] < key)  //如果是降序排列，修改此行
   low = mid + 1;
  else
   high = mid - 1;
}
return -1;        //查找成功-返回元素下标(mid)，查找失败-返回-1
}

平均查找长度

1.

2.

3.

7.2.3 分块查找

实现思路（图片）

平均查找长度

1.

2.

7.3 树型查找

7.3.1 二叉排序树 (BST)

概念

目的

构造一棵二叉排序树的目的并不是为了排序，而是为了提高查找、插入和删除关键字的速度，二叉排序树这种非线性结构也有利于插入和删除的实现

定义

二叉排序树(也称二叉查找树)或者是一棵空树

左子树结点值 < 根结点值 < 右子树结点值

1.若左子树非空，则左子树上所有结点的值均小于根结点的值

2.若右子树非空，则右子树上所有结点的值均大于根结点的值

3.左、右子树也分别是一棵二叉排序树

对二叉排序树进行中序遍历，可以得到一个递增的有序序列

查找

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程

代码实现

二叉排序树的非递归查找算法：

插入

找到对应的插入位置（一定是叶子结点），注意修改父节点指针

代码实现

删除

被删除结点为叶子结点

被删除结点只有左或只有右子树，用其子树顶替其位置

被删除结点有左、右子树

用其后继节点顶替，再删除后继结点

或者用其前驱结点顶替，再删除前驱结点

前驱：左子树最右下的结点

后继：右子树最左下的结点

查找效率分析

取决于树的高度，最好O(log2ⁿ)，最坏O(n)

平均查找长度（ASL）计算

成功：

失败：

7.3.2 平衡二叉树（AVL）

概念

目的

为了避免树的高度增长过快，降低二叉排序树的性能

定义

规定在插入和删除结点时，要保证任意结点的左、右子树“高度差”的绝对值不超过1

平衡因子

左子树与右子树的高度差，平衡因子的值只可能是 -1、0 或 1

注意：平衡二叉树可以是一棵空树

插入

和二叉排序树一样，找到合适的位置插入，新结点可能导致先祖结点平衡因子改变，导致失衡

LL

在A的 “左孩子”的“左子树”插入导致A不平衡，将A的“左孩子”“右上旋”

RR

在A的 “右孩子”的“右子树”插入导致A不平衡，将A的“右孩子”“左上旋”

LR

在A的 “左孩子”的“右子树”插入导致A不平衡，将A的“左孩子”的“右孩子”“先左上选再右上旋”

LL

在A的 “右孩子”的“左子树”插入导致A不平衡，将A的“右孩子”的“左孩子”“先右上选再左上旋”

查找效率分析

最大深度为O(log2ⁿ)，平均查找长度/查找的时间复杂度为O(log2ⁿ)

删除

删除结点（和二叉排序树一样）

被删除结点为叶子结点

被删除结点只有左或只有右子树，用其子树顶替其位置

被删除结点有左、右子树

用其后继节点顶替，再删除后继结点

或者用其前驱结点顶替，再删除前驱结点

前驱：左子树最右下的结点

后继：右子树最左下的结点

未改变平衡

一路向北找到最小不平衡子树，找不到就未改变平衡

改变平衡

找到最小不平衡自树，“个头”最高的儿子、孙子

调整平衡：根据“孙子的位置”调整平衡

LL

儿子右单旋

RR

儿子左单旋

LR

孙子左旋，再右旋

RL

孙子右旋，再左旋

平衡二叉树删除操作时间复杂度=O(log2ⁿ)

7.3.3 红黑树

概念

目的

为了保持 AVL 树的平衡性，插入和删除操作后，非常频繁地调整全树整体拓扑结构
代价较大。为此在 AVL 树的平衡标准上进一步放宽条件，引入了红黑树的结构

定义

1.每个结点或是红色，或是黑色的

2.根结点是黑色的

3.叶结点(外部结点、NULL结点、失败结点)均是黑色的

4.不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)

5.对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

插入

先查找，确定插入位置(原理同二叉排序树)，插入新结点

新结点

是根 —— 染为黑色

非根 —— 染为红色

若插入新结点后依然满足红黑树定义，则插入结束
若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义

如何调整，根据叔叔的颜色

黑叔：旋转+染色

LL型：右单旋，父换爷+染色

RR型：左单旋，父换爷+染色

LR型：左、右双旋，儿换爷+染色

RL型：右、左双旋，儿换爷+染色

红叔：染色+变新

结论

从根到叶结点的最长路径不大于最短路径的 2 倍

有n个内部结点的红黑树的高度

图片

7.4 B 树和 B+ 树

B 树

概念

又称多路平衡査找树，B树中所有结点的子个数的最大值称为B树的阶，通常用m表示

特点

1.树中每个结点至多有m棵子树，即至多含与m-1个关键字

2.若根结点不是终端结点，则至少有两棵子对

3.

4.所有的叶结点都出现在同一层次上，并且不带信息

5.B树是所有结点的平衡因子均等于0的多平衡查找树

图片

1.

2.

3.

B树的高度

最小高度h>=logm(n+1)

最大高度

高度区间

查询

在B树上查找到某个结点后，先在有序表中进行查找

若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找

查找到叶结点时(对应指针为空指针)，则说明树中没有对应的关键字，查找失败

插入

定位：利用前述的B树查找算法，抄出插入该关键字的最低层中的某个非叶结点(注意:插入位置一定是最低层中的某个非叶结点)

插入：在B树中，每个非失败结点的关键字个数都在区间

插入后的结点关键字个数小于m，可以直接推插入；
插入后检查被插入结点内关键字的个数，当插入后的结点关键字八数大于m-1时，必须对结点进行分裂

图片

删除

直接删除关键字：若被删除关键字行在结点的关键字个数≥[m/2]（向上取整），表明删除该关键字后仍满足B树的定义，则直接删去该关键字

兄弟够借：若被删除关键字所在结，删除前的关键字个数 =[m/2]-1（向上取整）且与此结点相邻的右(或左)兄弟结点的关键字个数 ≥[m/2]（向上取整）

则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)，以达到新的平衡

兄弟不够借：若被删除关键字所在结点助除前的关键字个数=[m/2]-1（向上取整）且此时与该结点相邻的左、右兄弟结点的关键字个数均=[m/2]- 1（向上取整）

则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并

B+树

每个分支结点最多有m棵子树（孩子结点）

非叶根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树（向上取整）

结点的子树个数与关键字个数相等

所有叶结点包含全部关键字及指向相应记头的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大八顺序相互链接起来

所有分支结点(可视为索引的索引)中仅包含它的各个子结点（即下一级的索引快）中关键字的最大值及指向其子结点的指针

7.5 散列查找

概念

散列表、散列函数H(key)

装填因子 a = 表中记录个数/散列表表长

常见的散列函数（此处采用“拉链法”）

除留余数法 H(key)=key % p

散列表表长为m，取一个不大于m但最接近或等于m的质数p

直接定址法 H(key)=key 或 H(key)=a*key+b

数字分析法——选取数码分布较为均匀的若干位作为散列地址

平方取中法——取关键字的平方值的中间几位作为散列地址

冲突的处理

拉链法（链地址法）

同义词串成一个链表

开放定址法

线性探索法

di = 0,1,2,3, ... ,m-1

平方探索法

di = 0^2，1^2，-1^2，2^2，-2^2

伪随机序列法

di = 一个伪随机序列

再散列法

准备多个散列函数，一个发生冲突了就用下一个

查找效率

取决于散列函数、处理冲突的方法、装填因子a

8.0排序

8.1 排序的基本概念

排序的定义

概念

重新排列表中的元素，使表中的元素满足按关键字有序的过程

算法的稳定性

若待排序表中有两个元素 R1 和 R2 ，其对应的关键字相同即 key1 = key2，且在排序前R1 在 R2的前面，若使用某一排序算法排序后， R1 仍然在 R2 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的

根据数据是否在内存中进行分类

内部排序

在排序期间元素全部存放在内存中的排序

外部排序

排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序

8.2 插入排序

直接插入排序

代码示意图

空间复杂度：O(1)

时间复杂度

最好时间复杂度（全部有序）：O(n)

最坏时间复杂度（全部逆序）：O(n^2)

平均时间复杂度：O(n^2)

折半插入排序

代码示意图

稳定性

稳定的

希尔排序

代码示意图

稳定性

不稳定

8.3交换排序

冒泡排序

稳定性

稳定的

每趟排序都，比较出一个最小的数，放在第一个，一边比较一边排序

快速排序

快速排序是所有内部排序算法中平均性能最优的排序算法

代码示意图

空间复杂度=O（递归的层数）

最好空间复杂度：O(log 2n)

最坏空间复杂度：O(n)

时间复杂度=O（n*递归的层数）

最好时间复杂度：O(n log 2n)

最坏时间复杂度：O(n^2)

稳定性

不稳定

8.4选择排序

简单选择排序

特点：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

代码实现

示意图

时间复杂度O（n^2）

稳定性

不稳定

堆排序

堆

大根堆

在完全二叉树中：根>=左、右

建立大根堆示意图

时间复杂度O（n log2 n）

示意图

小根堆

在完全二叉树中：根<=左、右

插入

新元素放到表尾（堆底）

根据大/小根堆的要求，新元素不断“上升”，直到无法继续上升为止

删除

被删除元素用表尾（堆底）元素替代

根据大/小根堆的要求，新元素不断“下坠”，直到无法继续下坠为止

稳定性

不稳定

8.5归并排序和基数排序

归并排序

含义

将两个或两个以上的有序表合并成一个新的有序表

多个数列相互比较，较大（小）的取出放入新的序列中

代码实现

示意图

归并

完整的归并排序

时间复杂度O(nlog2 n)

空间复杂度O(n)

稳定性

稳定的

基数排序（手算就可以，不考代码）

实现原理图

要求：得到按照关键字“递减”的有序序列

具体步骤

算法的效率

代码逻辑结构图

时间复杂度O( d (n+r) )

空间复杂度O(r)

稳定性

稳定的

使用场景：基数排序擅长解决的问题

1.数据元素的关键字可以方便地拆分为 d组，且 d 较小
2.每组关键字的取值范围不大，即r较小反
3.数据元素个数 n较大

8.7外部排序

基本概念

外部排序通常采用归并排序法

①根据内存缓冲区大小，将外存上的文件分成若干长度 “定量” 的子文件，依次入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串

②对这些归并段进行逐趟归并，使归并段(有序子文件)逐渐由小到大，直至得到整个有序文件为止

示意图

结论

注意

败者树

置换选择排序

通过置换的方式，使用更小的内存空间，得到大的初始归并断

最佳归并树

添加虚段的数量