数据结构与算法

---

2022/10/24 14:35 数据结构的基本的知识点可以参考我的语雀笔记，语雀上面的知识点介绍的特别浅（当时是根据王道视频课和《大话数据结构》等教材整理的，但那会毕竟刚开始写博客写的比较差）；这篇文章主要做一个进阶学习，参考书籍是程洁的《大话数据结构》，在原有笔记的基础上增加、补充了一些缺失的概念（这篇博客可以看作是对语雀的补充和拓展）；

---

第一章 绪论

首先声明，这篇博客主要代码都是C语言（因为参考书用的就是C语言），部分拓展知识点可能会使用到C++代码，这里我们先复习一下C语言中常用的结构体定义

struct S{int i;} a,b; 
/*
定义结构 S和  S的变量a,b
*/
typedef struct S{int i;} a,b;  
/*
这里除了定义结构S,  又起了别名a和b,  a和b位置的标识符就都是别名而不是变量
a和b也像类型一样用来定义结构变量
因为起了别名 所以不起结构名也没问题 typedef struct {int i;} a
*/

1.数据和数据结构

• 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别并输入给计算机处理的符号集合。数据不仅仅只包括整型等数值类型，还包括字符以及声音等非数值类型。

• 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。数据元素也被称为记录

• 数据项：一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位

• 数据对象：是性质相同的数据元素的集合，是数据的子集。我们常称数据对象为数据（在不产生混淆的前提下）

• 结构：指各个组成部分相互搭配和排列的方式

• 数据结构：是一种相互之间存在一种或多种特定关系的数据元素的集合。我们把数据结构分为逻辑结构和物理结构

  • 逻辑结构：指数据对象中数据元素之间的相互关系，可分为以下四种

    • 集合结构：集合结构中的数据元素除了属于同一个集合外，没有任何关系
    • 线性结构：线性结构中的数据元素之间是一对一的关系
    • 树形结构：树型结构中的数据元素之间存在一种一对多的层次关系
    • 图形结构：图形结构的数据元素是多对多的关系

  • 物理结构：也称为存储结构，是指数据的逻辑结构在计算机中的存储形式，通俗来讲就是如何把数据元素存储到计算机的存储器中（存储器是针对内存而言，对于外存来说通常用文件结构来描述数据组织）。数据元素的存储结构形式有两种：顺序存储和链式存储

    • 顺序存储结构：是把数据元素放在地址连续的存储单元中，其数据间的逻辑关系和物理关系是一致的
    • 链式存储结构：是把数据元素存储在任意的存储单元中，这组存储单元可以是连续的也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系

2.数据类型和抽象数据类型

• 数据类型：是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称，在C语言中按照取值不同数据结构可以分为两类

  • 原子结构：不可再分的基本类型，包括整型、字符型等
  • 结构类型：由若干类型组合而成，可以分解，如整型数组、结构体等

• 抽象：是指“抽取出事物具有的普遍性的本质”这一行为，它隐藏了繁杂的细节，只保留实现目标必须的信息。对已有的数据类型进行抽象就可以得到抽象数据类型

• 抽象数据类型（ADT）：是指一个数学模型以及定义在该模型上的一组操作。一个抽象数据类型定义了：一个数据对象、数据对象中各数据元素之间的关系以及对数据元素的操作。ADT体现了程序设计中对问题的分解、抽象和信息隐藏的特性

抽象数据类型的标准格式如下

ADT 抽象数据类型名
Data 
    数据元素之间逻辑关系的定义
Operation
    操作1
    操作2
    操作3
    ......
endADT

3.算法和算法复杂度

• 算法：是“解决特定问题求解步骤的描述”，简单来说就是算法描述了解决问题的方法。在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。算法具有以下五个基本特征：

  • 输入&输出：算法具有零个或多个输入，至少有一个或多个输出
  • 有穷性：算法在执行有限的步骤之后会自动结束而不会出现无限死循环，且每一个步骤在可接受的时间内完成
  • 确定性：算法的每一个步骤都具有确定的含义，不会出现二义性
  • 可行性：算法的每一步都能够通过执行有限次数完成

• 函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是大于g(n)，则称f(n)的渐进增长快于g(n)

• 算法的时间复杂度：进行算法分析时，语句总的执行次数f(n)是关于问题规模的n的函数，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。记作T(n)=O(f(n))，我们称之为大O记法，由f(n)推到得到T(n)的方法如下

  • 用常数1取代语句执行次数中所有的加法常数（这是为了避免如常数阶一样根本没有最高阶）

  • 只保留最高阶的项

  • 如果最高阶的项存在且不是1，则将常数项除去

• 常见的时间复杂度大小关系如下：

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)<O(n^n^)

第二章 线性表

1.线性表的定义

线性表：零个或多个数据元素的有限序列

• 元素之间存在顺序，这里的顺序是指若元素存在多个则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且仅有一个前驱和后继；
• 线性表强调有限，即元素的个数有限；

2.线性表的ADT

ADT 线性表/List
Data
    线性表的数据对象集合为{a1,a2,a3...}，每个元素类型均为DataType。数据元素之间的关系是一对一的关系
Operation
    InitList(*L):初始化线性表，建立一个空的线性表L（即线性表元素个数为0，空表）
    ListEmpty(L):若线性表为空返回1，否则返回0
    ClearList(*L):将线性表清空
    GetElem(L,i,*e):将线性表中的第i个位置元素值返回给e
    LocateElem(L,e):在线性表L中查找值为e的元素，查找成功则返回给元素在表中的序号，否则返回0
    ListInsert(*L,i,e):在线性表L中的第i个位置插入新元素e
    ListDelete(*L,I,*e):删除线性表L中第i个位置的元素并用e返回该值
    ListLength(L):返回线性表L的元素个数
endADT

关于线性表更复杂的操作，可以由上述基本操作的组合来实现

3.线性表的物理结构

3.1 顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

• 可以使用C语言的一维数组来实现线性表的顺序存储结构，把第一个元素存储在下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置

#define MAXSIZE 20 //定义存储空间大小
typedef int Elemtype;//根据实际情况确定数据元素的类型
typedef struct
{//匿名结构体，只能使用一次
    ElemType data[MAXSIZE];//data数据组存储线性表的元素,它的存储位置就是存储空间的起始位置
    int length;//线性表当前长度   线性表长度！=数组长度，随着增删线性表长度会动态改变
}SqList;

(1)顺序表的时间复杂度：

• 对每个线性表位置的存入或取出数据对于计算机来说都是相等的时间，即存取时间性能为O(1)，我们将具有这一特点的存储结构称为随机存取结构
• 线性表的顺序存储结构在存取数据不管对哪个位置时间复杂度都是O(1)，插入或删除时时间复杂度都是O(n)

(2)顺序表的特点：

• 无需为表示表中元素之间的逻辑关系增加额外的存储空间
• 可以快速的存取表中任意位置的元素
• 插入和删除需要移动大量元素
• 当线性表长度变化较大时难以确定存储空间（数组）的容量
• 造成存储空间的“碎片化”（因为链表的存储空间是随机选取某一块连续空间）

3.2 链式存储结构

3.2.1 单链表

头指针和头结点：

• 头指针指向链表的第一个结点，若存在头结点则指向头结点，若不存在头结点则指向第一个结点
• 常用头指针冠以链表的名字，头指针是链表的必要元素
• 头结点不一定是链表必须要的元素（引入头结点为了方便单链表的特殊操作,保证在表头插入或者删除第一个结点与其他结点操作相同.保持了单链表操作的统一性）

typedef struct Node
{
    ElemType data;//数据域
    struct Node *next;//指针域，指向Node结构体的指针next
}Node;//在定义Node结构体类型的同时声明一个Node类型的变量Node

typedef struct Node *LinkList;//声明指向Node结构体的指针LinkList，也就是头指针，赋值为头结点/第一个结点的地址

单链表的时间复杂度：

• 查找、存取的时间复杂度为O(n)
• 插入删除的时间复杂度为O(1)

3.2.2 静态链表

当语言没有指针功能如Basic，就只能使用数组来代替指针描述单链表，称为静态链表

#define MAXSIZE 1000//假设链表最大长度为1000
typedef struct
{
    Elemtype data;//数据域
    int cur;//游标cursor，0表示无指向
}Component,StaticLinkList[MAXSIZE];//这里声明了两个结构体变量，分别是数组内容和静态链表数组

静态链表的特点：

• 在插入和删除式只需要修改游标不需要移动元素，改进了顺序表中插入和删除操作需要移动大量元素的缺点

• 失去了顺序表随机存取的特性，且与顺序表一样具有空间无法拓展的缺点

3.2.3 循环链表

将单链表的终端结点的指针端由空指针指向头结点，使得单链表形成一个环，也称为单循环链表

3.2.4 双向链表

typedef struct DulNode
{
    ElemType data;//数据域
    struct DulNode *prior;//前向指针
    struct DulNode *next;//后向指针
}DulNode,*DuLinkList;//声明了两个结构体变量，匿名结构体类型的结点和指向匿名结构体类型的指针（头指针）

第三章 栈

1.栈的定义

栈：限定仅在表尾进行插入和删除操作的线性表

• 把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈
• 栈对线性表的插入和删除的位置进行了限制，但是没有对元素进出的时间进行限制，只要保证式栈顶元素出栈即可

2.栈的ADT

ADT 栈（stack）
Data 
    元素具有相同类型，相邻元素具有前驱和后继的关系
Operation
    InitStack(*S):初始化栈，即建立一个空栈S
    DestroyStack(*S):若栈存在则销毁它
    ClearStack(*S):将栈清空
    StackEmpty(*S):若栈为空则返回1，否则返回0
    GetTop(S,*e):若栈存在且非空则用e返回S的栈顶元素
    Push(*S,e):若S存在，插入新元素e到S中使其成为栈顶元素
    Pop(*S,*e):删除S中的栈顶元素并用e返回它的值
    StackLength(S):返回栈S的元素个数
endADT

3.栈的物理结构

3.1 顺序存储结构

对于栈这种线性表，使用数组来实现就必须考虑选择哪段作为栈顶和栈底——选取下标为0的一端作为栈底，这样整个数组的受元素的变化影响最小

3.1.1 顺序栈

typedef int SElemType;//栈中元素的数据类型，我们可以使用这种方式将其设置为int
typedef struct
{
    SElemType data[MAXSIZE];//data数组，也就是创建顺序栈
    int top;//top变量用于指示栈顶元素在数组中的位置，空栈的top=-1
}SqStack;

3.1.2 共享栈

对于只有一个栈，我们只能选择一个合适的栈大小避免出现元素溢出的情况；对于两个相同类型的栈，我们可以使用共享栈的方式最大限度利用两个栈的空间——栈顶相连，令其中一个栈底下标为0，另外一个栈底下标为n-1。

当栈空时即top1=-1或者top2=n；当栈满时即top1+1=top2

typedef struct
{
    SElemType data[MAXSIZE];
    int top1;//栈1的栈顶指针
    int top2;//栈2的栈顶指针
}SqDoubleStack;

3.2 链式存储结构

• 将单链表的头指针和栈顶指针合并
• 对于链栈来说通常不需要头结点（因为链表在插入删除时有头部和其他部位的操作差别,引入头结点来统一操作,使对链表第一个位置上的操作和其他位置上的操作相同,不用特殊处理。而链栈只在头部插入删除,所以不必要用头结点）
• 链栈为空表示为top=NULL

typedef struct StackNode
{//链栈结点的结构体
    SElemType data;//数据域，元素的数据类型都是相同的，至此还没有出现过一个结构中数据类型不同的情况
    struct AtackNode *next;//指针域
}StackNode,*LinkStackPtr;//声明结点变量和指向StackNode结构体类型的指针LinkStackPtr

typedef struct LinkStack
{//链栈结构体
    LinkStackPtr top;//声明头指针
    int count;//统计栈内元素
}LinkStack;//声明链栈LinkStack，其实只有top指针的话就可以不用定义这个结构体了

第四章 队列

1.队列的定义

队列：只允许在一端进行插入操作，而在另一端进行删除的线性表

• 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头

2.队列的ADT

ADT 队列（Queue）
Data 
    元素具有相同类型，相邻元素具有前驱和后继关系
Operation
    InitQueue(*Q):初始化操作，建立一个空队列
    DestroyQueue(*Q):若队列Q存在则销毁它
    ClearQueue(*Q):将队列Q清空
    QueueEmpty(*Q):若队列为空则返回1否则返回0
    GetHead(Q,*e):若队列存在且非空，用e返回队列Q的队头元素
    EnQueue(*Q,e):若队列Q存在，插入新元素e到队列Q中并使其成为队尾元素
    DeQueue(*Q,*e):删除队列Q中的队头元素，并用e返回其值
    QueueLength(Q):返回队列Q的元素个数
endADT

3.队列的物理结构

3.1 顺序存储结构

实现队列的顺序存储结构和实现顺序表的方式完全相同（故此处不展示其代码），数组下标为0的一端是队头

• 入队列就是在队尾追加一个元素，不需要移动任何元素，时间复杂度为O(1)
• 出队列是使队头元素出队（下标为0的队列元素），这意味着需要将队列中所有的元素向前移动以保证数组下标为0的位置不为空，时间复杂度为O(n)；假如去除限制条件——队头一定要在下标为0的位置

3.1.1 循环队列

• 引入两个指针（称为指针实际上不准确，指针指向的是内存地址，这个指向的是数组位置），front指向队头元素，rear指向队尾元素的下一个位置（而不是队尾元素）

• 把头尾相接的顺序存储结构称为循环队列

• 当front==rear如何区分队列是空还是满

• • 设置标志变量flag，当flag==rear且flag=0时队列为空，当flag==rear且flag=1时队列满
  • 当队列空时条件为front==rear，当队列满时我们认为实际上队列还剩一个元素空间；判断队列满的条件为(rear+1)%QueueSize==front

• 通用计算队列长度公式(rear-front+QueueSize)%QueueSize

typedef int QElemType;//此处定义队列元素类型为int

typedef struct 
{
    QElemType data[MAXSIZE];
    int front;
    int rear;
}sqQueue;

3.2 链式存储结构

队列的链式存储结构实际上就是单链表，只不过它只能尾进头出；为了操作方便，将队头指针指向链队列的头结点，队尾指针指向终端结点；空队列时front和rear都指向头结点

typedef int QElemType;

typedef struct QNode
{//结点结构
    QElemType data;//数据域
    struct QNode *next;//指针域
}QNode,*QueuePtr;

typedef struct
{//队列的链表结构
    QueuePtr front,rear;
}LinkQueue;

第五章 串

1.串的定义

串：是由零个和多个字符组成的有限序列，又称为字符串

• 一般将串记为s=”a1a2a3…an”(n>=0)，其中s是串的名称，双引号括起来的字符序列是串的值，值可以是字母、数字或其他字符，i就是该字符在串中的位置，n称为串的长度
• 串的逻辑结构和线性表很相似，但是串中的元素都是字符。线性表更关注的是单个元素的操作，而串中更多的是针对子串（而不是单个字符）的操作

2.串的ADT

ADT 串（string）
Data 
    串中的元素仅由一个字符组成，相邻元素之间具有前驱和后继的关系
Operation
    StrAssign(T,*chars):生成一个值等于字符串常量chars的串T——这个地方指针的使用我不是很理解
    StrCopy(T,S):若串S存在，则将串S复制得到串T
    ClearString(S)：若串S存在，则将S清空
    StringEmpty(S):若串S为空则返回1，否则返回0
    StrLength(S):返回串S的元素个数，即串的长度
    StrCompare(S,T):比较两个串的大小
    Concat(T,S1,S2)：用T返回由S1和S2联接得到的新串
    SubString(Sub,S,pos,len):Sub返回串S的第pos个字符起长度为len的子串
    Index(S,T,pos):若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符后第一次出现的位置
    Replace(S,T,V):用V替换主串S中出现的所有与T相等的不重叠的子串
    StrInsert(S,pos,T):在串S的第pos个字符之前插入串T
    StrDelete(S,pos,len):从串S中删除第pos个字符起长度为len的子串
endADT

3.串的物理结构

3.1 顺序存储结构

用一组地址连续的存储单元来存储串中的字符序列，一般使用定长数组来定义

3.2 链式存储结构

串的链式存储结构与线性表类似，但是因为串结构的特殊性（结构中的每个元素数据是一个字符），假如使用一个结点存储一个字符会造成很大的浪费，故考虑一个结点存放多个字符。

4.模式匹配算法

4.1 朴素模式匹配算法

通常将子串的定位操作称为串的模式匹配，朴素的模式匹配算法就是将主串和模式串的字符一个个对比，如果不同则模式串向后移动一位，递归进行上述操作。

4.2 KMP模式匹配算法

KMP的主要思想是：当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了，因此记录已经匹配的文本内容是KMP的重点也是next数组需要做的事；

i值表示当前主串的第i个字符正在进行匹配，j值表示当前模式串的第j个字符正在进行匹配

next数组表示假如此时匹配失败，则当前模式串需要从第next[j]个字符开始重新匹配；主串的i值在此过程中保持不变，匹配到哪个字符就保持，待会还是从主串的这个字符开始进行匹配

把模式串各个位置的指针跳转位置定义为一个数组next，next数组的长度就是模式串的长度

• j=1时对应的变化值为next[0]=0
• j=i时，写出模式串的第1个到第i个字符串
  • 若该字符串中前缀字符串x与后缀字符串相等y，则next[i]=len(x)
  • 若该字符串中没有和前缀字符串相等的后缀，则next[i]=0

然而next数组并不是最好的解决办法，我们使用nextval数组对其进行改进（详见书本p144）

很多人可能看了上面的简介还是觉得云里雾里，所以这里我们分模块讲解KMP，参考链接代码随想录 (programmercarl.com)；

4.2.1 前缀表的作用

next数组实际就是一个前缀表；

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配；

下面我们举个例子，在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf；

第一次匹配的时候文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。如果暴力匹配，会发现不匹配，此时就要从头匹配；

如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配；

前缀表：记录下标为i之前（包括i）的模式串中有多大长度的相同前后缀

4.2.2 最长相等前后缀

字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；

字符串的后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串；

字符串a的最长相等前后缀为0，字符串aa的最长相等前后缀为1，字符串aaa的最长相等前后缀为2…(前缀表要求的就是相同长度的前后缀)

4.2.3 计算前缀表

前缀表的计算非常简单，只需要记住一句话“长度为i的子串，其最长相同前后缀的长度就是对应前缀表位置i-1的元素”

例如长度为前4个字符的子串aaba，最长相同前后缀的长度为1，长度为前5个字符的子串aabaa，最长相同前后缀的长度为2，长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0…

4.2.4 前缀表的使用

有了前缀表，我们就可以借助前缀表判断当字符不匹配的时候指针应该移动的位置

我们要看不匹配的模式串的位置的前一个字符的前缀表的数值是多少，本例中f的前一个字符的前缀表的数值是2，所以将模式串的指针移动到下标为2的位置继续匹配而不需要回溯文本串和模式串；

4.2.5 next数组和前缀表

实际上next数组就是前缀表，但是next数组是前缀表的具体实现，这意味着next数组可能需要在前缀表的元素统一减1（当然不变或者统一加1都是可以的）

前缀表减1实现next数组

void getNext(int* next, const string& s) {
    //1.初始化两个指针i和j，其中j指向前缀末尾位置，i指向后缀末尾位子，同时对next数组进行初始化赋值
    int j = -1;
    next[0] = -1;
    for(int i = 1; i < s.size(); i++) {      //注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { //2.处理前后缀不相同的情况，如果 s[i] 与 s[j+1]不相同，也就是遇到前后缀末尾不相同的情况，就要向前回退
            j = next[j];                     //向前回退，这里也用了next数组，有点类似于利用已经构造好的next数组来构造next数组
        }
        if (s[i] == s[j + 1]) {              //3.处理前后缀相同的情况，如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

前缀表实现next数组

void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j - 1];            // 注意这里，是要找前一位的对应的回退位置了
            }
            if (s[i] == s[j]) {             
                j++;
            }
            next[i] = j;
        }
    }

当然具体选择哪种实现就是使用者自己的习惯问题，需要注意的是不同的next数组对应的匹配代码也是有差距的，个人习惯更偏向于直接使用前缀表实现匹配

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

第六章 树

1.树的定义

树是n(n>=0)个结点的有限集。n=0时称为空树。

• n>0时，子树的个数没有限制但是子树不能相交

• 树的结点包含一个数据元素以及若干指向其子树的分支，结点拥有的子树的分支数称为结点的度，树的度是指树的结点的度的最大值

• 结点的分类

• • 度为0的结点称为叶结点
  • 度不为0的结点称为分支结点

• 结点的层次从根开始定义，根为第一层，根的孩子为第二层…树中结点的最大层次称为树的深度或高度

• 有序树是指子树从左至右有次序不能互换，否则为无序树

• 森林是互不相交的树的集合（注意不是子树相交形成树）

2.树的ADT

ADT 树（tree）
Data 
    树是由一个根节点和若干子树构成，树中结点具有相同的数据类型以及层次关系
Operation
    InitTree(*T):构造空树
    CreateTree(*T,definition):按照definition给出的树的定义来构造树
    Value(T,cur_e):cur_e是树T中的一个结点，返回此结点的值
    Assign(T,cur_e,value):给树T的结点cur_e赋值为value
    InsertChild(*T,*p,i,c):插入子树c作为树T中p指向的结点的第i棵子树，注意i只能是p的度+1
    DeleteChild(*T,*p,i):删除树T中p所指向的结点的第i棵子树，注意i只能是p的度

3.树的物理结构

简单的顺序存储结构不能满足树的实现要求（但顺序结构确实也能适用于图和树），结合顺序存储和链式存储的特点（借鉴静态链表、单链表等），可以得到下面三种表示方法

3.1 双亲表示法

静态链表

这样的存储结构，可以根据结点的parent指针很容易的找到它的双亲结点，所用时间复杂度为O(1)；然而要找到孩子结点则需要遍历该结构，或者增加结点最左边孩子（firstchild）域；假如需要找到兄弟结点则可以在此基础上增加一个右兄弟域

#define MAX_TREE_SIZE 100
typedef int TElemType;//树结点的数据类型，暂定为整型
typedef struct PTNode//结点结构
{
    TElemType data;//数据域
    int parent;//双亲指针域，存储该结点的双亲在数组中的下标
}PTNode；

typedef struct//树结构
{
    PTNode  nodes[MAX_TREE_SIZE];//结点数组
    int r,n;//根的位置和结点的数量
}PTree;

3.2 孩子表示法

顺序表和单链表的组合（书本p160）

这种结构对于查找孩子和兄弟都很方便，但是对于查找双亲只能遍历；可以考虑把双亲表示法和孩子表示法综合（书本p161）

#define MAX_TREE_SIZE 100
typedef struct CTNode//孩子结点
{
    int child;//数据域，存储该结点在表头数组中的下标
    struct CTNode *next;//指针域，存储指向该结点的下一个孩子结点的指针
}*ChildPtr;

typedef struct//表头结构
{
    TElemType data;//数据域，存储该结点的数据信息
    ChildPtr firstchild;//头指针域，存储该结点的孩子链表的头指针
}CTBox;

typedef struct//树结构
{
    CTBox nodes[MAX_TREE_SIZE];//结点数组
    int r,n;//根的位置和结点数量

}CTree;

3.3 孩子兄弟表示法

单链表（书本p162）

这种表示法的最大好处就是将复杂的树变为了一棵二叉树，就可以充分的利用二叉树的特性和算法来进行处理了

typedef struct CSNode
{
    TElemType data;//数据域
    struct CSNode *firstchild,*rightsib;//firstchild存储该结点的第一个孩子结点的存储地址，rightsib存储该节点的右兄弟结点的存储地址
}CSNode,*CSTree;

4.二叉树

4.1 二叉树的特点

• 每个结点最多有两棵子树（可以没有子树或者有一棵子树），所以二叉树中不存在度大于2的结点
• 左子树和右子树是有顺序的，次数不能颠倒
• 即使树中只有一棵子树，也要区分是左子树还是右子树（相当于左手和右手不能一概而论）

4.2 二叉树的性质

1. 在二叉树的第i层上至多有2^(i-1)个结点

…（详见书本p169）

4.3 二叉树的物理结构

4.3.1 顺序存储结构

前面提到的树无法使用简单的顺序存储结构实现，但是二叉树是一种特殊的树，所以可以使用顺序结构来实现

对于完全二叉树来说，因为其层序编号可以反映逻辑关系，所以可以直接使用一维数组存储二叉树中的结点；对于一般的二叉树，同样可以采用对其进行编号的方式，不存在的结点在数组中存入NULL即可。

考虑到对于一棵斜树如果采用顺序存储的话会导致浪费的空间过多，所以顺序存储结构一般只用于完全二叉树。

4.3.2 链式存储结构

使用顺序存储结构的适用性不强，我们考虑使用链式存储结构。二叉链表具有一个数据域和两个指针域，分别存放左孩子和右孩子的指针

typedef struct BiTNode
{
    TElemType data;//结点数据
    struct BiTnode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;//声明结点变量和头指针

4.4 二叉树的遍历

(1)前序遍历：先访问根节点，然后前序遍历左子树，接着前序遍历右子树（遍历树，访问结点）

(2)中序遍历：先中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树

(3)后序遍历：先后序遍历根节点的左子树，然后后序遍历根节点的右子树，最后访问根节点（其实用结点比较准确）

void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
    {return;}
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c",T->data);//显示结点数据，这一步可以更改为其他对结点的操作
}

(4)层序遍历：从上到下，从左至右逐个对结点进行访问

void LevelOreder(BiTree T){
    
    LinkQueue Q;
    InitQueue(Q);  //初始化队列
    
    EnQueue(Q,T); //根节点入列
    BiTree p;
    while(!isEmpty(Q)){
        DeQueue(Q,p);	//出一个结点访问一个
        visit(p);
        if(p->lchild != null){
            EnQueue(Q,p->lchild);	//左子树存在则入列
        }
        if(p->rchild != null){
            EnQueue(Q,p->rchild);   //右子树存在则入列
        }
    }
}

4.5 树、森林和二叉树的转换

(1)树转化为二叉树

• 在所有的兄弟结点之间加一条线
• 对树中每一个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线
• 旋转整棵树使之层次分明

(2)森林转化为二叉树

• 先把每棵树转化为二叉树
• 将森林中的每一棵树都理解为兄弟，于是可以按照兄弟的处理办法来操作已经转化好的二叉树。保持第一棵二叉树不动，依次把后面的每一棵二叉树的根节点作为前一棵二叉树根节点的右孩子，连线即可

(3)二叉树转化为树

• 若某结点的左孩子节点存在，则将该结点与其“左孩子的所有右后代”都作为该节点的孩子进行连线
• 删除原二叉树中所有结点与其右孩子的连线

(4)二叉树转化为森林

• 只要二叉树的根结点有右孩子则就是森林
• 从根结点开始若右孩子存在则去除根节点与右孩子的连线，依次递归
• 再将分离得到的二叉树都转化为树即可

5.哈夫曼树

哈夫曼树和哈夫曼编码都是二叉树的应用，常用于数据压缩的编码解码

构建方法：书本p204页

第七章 图

1.图的定义

图是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为G(V,E)，V是图G中顶点的集合，E是图G中边的集合

• 线性表中的数据元素称为元素，树中的数据元素称为结点，图中的数据元素称为顶点Vertex
• 线性表中可以没有数据元素（空表），树中可以没有结点（空树），但是在图结构中不允许没有顶点
• 图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，顶点集不能为空，但是边集可以为空

（更多详细有关图的介绍可以参考离散数学中的笔记）

2.图的ADT

ADT 图（graph）
Data 
    顶点的非空有穷集合和边的集合
Operation 	
    CreateGraph(*G,V,VR):按照顶点集和边弧集VR的定义构造图G
    LocateVex(G,u):若图G中存在顶点u则返回u在图中的位置
    GetVex(G,u):若图G中存在顶点u则返回u的值
    DeleteVex(*G,v):删除图G中顶点v以及其相关的弧
    DeleteArc(*G,v,w):删除图中的有向弧<v,w>，若G是无向图则还需要删除其对称弧<w,v>
    DFSTraverse(G):深度优先遍历
    HFSTraverse(G):广度优先遍历
endADT

3.图的物理结构

因为图中任意两个顶点之间都可能存在联系，所以无法用数据元素在内存中的物理位置来表示元素之间的关系，即图不可能用简单的顺序存储结构表示；而使用多重链表也会导致因为度数不同而浪费空间

3.1 邻接矩阵

图是由顶点和边两部分组成，合在一起存储较为困难，能否分为两个结构来分别存储呢？

顶点部分主次大小，所以使用一个一维数组来存储；

边是顶点与顶点之间的关系，无法用一维搞定，所以考虑使用二维数组来存储；

typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值类型
#define MAXVEX 100;//最大顶点数
#define INFINITY 65535;//用65535表示无穷
typedef struct
{
    VertexType vexs[MAXVEX];//一维顶点数组
    EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵二维数组
    int numVertexes,numEdges;//图中当前的顶点数和边数
}

3.2 邻接表

邻接矩阵是不错的图存储结构，但是对于边数相对顶点较少的图（稀疏图），这种结构会浪费大量存储空间；

借鉴树结构中的孩子表示法将数组和链表相结合的存储方法，我们在图中得到邻接表

• 图中顶点用一个一维数组存储（使用单链表来存储当然也可以），同时在该顶点数组中每个数据元素还需要存储指向第一个邻接点的指针以便于查找该顶点的边信息
• 图中每个顶点vi的所有邻接点构成一个线性表，因为邻接点的个数不定所以用单链表存储（有向图则使用弧尾作为顶点来存储边表）

typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值类型由用户定义

typedef struct EdgeNode
{//边表结点
    int adjvex;//邻接点域，存储该顶点对应的一维顶点表中的下标
    EdgeType weight;//权值，非网图可以不需要
    struct EdgeNode *next;//指针域，指向顶点的下一个邻接点（而不是邻接点的下一个邻接点）
}EdgeNode;

typedef struct VertexNode
{//顶点表结点
    VertexType data;//顶点域，存储顶点信息
    EdgeNode *firstedge;//边表头指针，指向边表的第一个结点，即该结点的第一个邻接点
}VertexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;//邻接表
    int numVertexes,numEdges;//图中当前顶点数和边数
}GraphAdjList;

3.3 十字链表

对于有向图来说邻接表是有缺陷的，如果关心出度问题则要了解入度只能遍历整个图，同理，使用逆邻接表就只能遍历才能了解到出度情况

• 重新定义顶点表的结点结构
• 重新定义边表的顶点结构（详见书本p233）

3.4 邻接多重表

十字链表是针对有向图的优化，对于无向图是否需要有优化的地方呢？

假如在无向图中关注的是顶点则邻接表是个不错的选择，但是如果我们关注边的操作即意味着需要找到这条边的两个边表结点进行操作，比如说需要删除边(v0,v2)则需要对邻接表结构中的边表的相应结点进行删除

4.图的遍历

（详见p237）

4.1 深度优先遍历

bool visited[MAX_VERTEX_NUM] //访问标记数组
void DFSTraverse(Graph G){
    for(int v = 0; v < G.vexnum ; v++){
        visited[v] = false ;  //初始化标记数组
    }
    for(int v = 0; v < G.vexnum ; v++){  //保证图中的每个联通分量都能被访问
        if(!visited[v])
            DFS(G,v);
    }

}

void DFS(Graph G,int v){	//G表示要遍历的图，v表示从哪个顶点开始
    
    visit(v);
    visited[v] = true;
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
           
        if(!visited[w])  //如果没有被访问过
            DFS(G,w);
        
    }

}

4.1.1 复杂度分析

• 邻接矩阵：O( |v|2) //一共需要访问v个结点，而访问v个结点都需要O(v)的时间
• 邻接表：O（ |v| + |E| ) //访问v个顶点要O(v)的时间，访问各个邻接点要O(E)的时间

4.1.2 深度优先生成树

• 由深度优先遍历确定
• 生成树不唯一
• 深度优先遍历非联通图，优先得到生成森林

4.2 广度优先遍历

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){
    for(int v = 0; v < G.vexnum ; v++){
        visited[v] = false ;  //初始化标记数组
    }
    InitQueue(Q);
    for(int v = 0; v < G.vexnum ; v++){  //保证图中的每个联通分量都能被访问
        if(!visited[v])
            BFS(G,v);
    }

}

void BFS(Graph G,int v){
    visit(v);
    visited[v] = false;	//访问第一个结点
    
    EnQueue(Q,v);	//第一个结点入队列
    
    while(!isEmpty(Q)){	  //若队列不为空则循环
        DeQueue(Q,v);
        for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w)){
            if(!visited[w]){
                visit(w);
                visited[w] = false;
                EnQueue(G,w)
             }        
        }
    }

}

4.2.1 复杂度分析

• 邻接矩阵：O( |v|2)
• 邻接表：O（ |v| + |E| )

4.2.2 广度优先生成树

• 由广度优先遍历确定
• 由于邻接表存储图不一致，由此确定的生成树不一致
• 遍历非联通图可以得到广度优先生成森林

其实这种就是无效笔记，做了和没做一样根本起不到提示的作用

5.最小生成树

将构造连通图的最小代价生成树称为最小生成树（详见p245）

最小生成树的几个特性:

• • 最小生成可能由多个,但权值之和只有一个
  • 边 = 顶点数 - 1
  • 如果一个联通图本身是树,其最小生成树就是其本身
  • 只有联通图才能生成树,非联通图只能生成森林

5.1 Prim算法

从某个点开始，每次将代价最小的顶点纳入生成树，生成树不唯一，时间复杂度：O(v^2^)

5.2 Kruskal算法

每次选择权值最小的边，使两头联通，原本已经联通的就不用选，时间复杂度: O(ElogE)

6.最短路径

对于网图来说，最短路径是指两顶点之间经过的边权值之和最少的路径，我们称起点为源点，最后一个顶点为终点（详见p257）

6.1 Dijistra算法

注意: 不适用于带负权图，时间复杂度为 O(v^2^)

6.2 Floyd算法

注意: 适用于于负权图，但不适用于带有”负权回路”的图，时间复杂度为 O(v^3^)

6.3 广度优先遍历(无权图)

void BFS_MIN_Distance(Graph G,int u){
    for(int i = 0 ; i<G.vexnum ; i++){
        d[i] = INF;   //d表示最短路径长度
        path [i] = -1;   //path表示最短路径从哪里来,初始为-1  
    }
    d[u] = 0;
    visited[u] = true;
    Enqueue(Q,u);
    
    while(!isEmpty(Q)){
        Dequeue(Q,u);
        for(w=FirstNeighbor(G,w) ; w>=0 ; w=NextNeighbor(G,u,w)){
            if(!visited[w]){
                d[w] = d[u] + 1;	//路径长度+1
                path[w] = u;		个
                visited[w] = true;
                Enqueue(Q,w);
            }
        }
    }
}

7.有向无环图(DAG图)

8.拓扑排序

AOV网:顶点表示活动，边上没有权值

• 拓扑排序的方法:

1. 1. 从AOV网中选择一个没有前驱的顶点输出
   2. 从网中删除改顶点和所有以它为起点的有向边
   3. 重复1和2直到AOV网为空，或者当前网中不存在前驱(即非连通图)

• 拓扑排序的性质:

1. 1. 不唯一
   2. 若图中有环，则不存在拓扑排序

• 拓扑排序的算法:

bool TopologicalSort(Graph G){
    InitStack(S);
    
    for(int i = 0; i < G.vexnum ; i++){
        if(indegree[i] == 0){  //indegree记录入度为0的结点
            Push(S,i)			//将入度为0的结点入栈
        }
    }
    
    int count = 0;//记录已经输出的定点数
    while(!isEmpty(S)){
        Pop(S,i);
        print[count++] = i; //输出i结点
        for(p=G.vertices;p;p=p->nextarc){
            v = p->adjvex;
            if(!--indegree[v]){//入度-1后变为0
                Push(S,v);
            } 
        }
    }//while
    
    if(count < G.vexnum)
        return false;
    else
        return true
}

9.关键路径

AOE网:用边表示活动的网络,用顶点表示事件

求关键路径步骤:

1. 求所有事件的最早发生时间(ve) : 即求源点到目的顶点的最长路径
2. 求所有时间的最迟发生时间(vl) : 不推迟整个工程的情况下,该事件最迟应该发生的时间
3. 求所有活动的最早发生时间(e) : 活动弧的起点最早应该发生的时间
4. 求所有活动的最迟发生时间(l) : 活动弧的终点所表示的事件的最迟时间与该活动所需的时间差.
5. 求d = l - e , d = 0即关键活动

关键活动,关键路径的特性:

1. 关键活动耗时增加,整个工程工期增加
2. 缩短关键活动时间,缩短整个工程时间
3. 当缩短到一定程度,关键活动可能变成非关键活动