数据结构 | 晴天ぺ小窝

王道教程

怎么信息化、怎么高效处理信息

数据结构中很多map、list我们平时经常使用，以为它原本就有了，因此没什么用，其实真正的计算机里，系统只给了我们基本的物理存储方式，这些写好的map、array、list等pyhon、go中的结构，其实是程序员用数据结构帮我们封装好的，而如果你要自己写一种编程语言，数据结构无疑是最基本的，或者你要在基础上封装一个更高级的数据结构，方便自己直接使用，数据结构也是最根本的

1 绪论

数据结构概念、算法概念、时间复杂度、空间复杂度

数据，是信息的载体，是描述事物属性并能被计算机程序识别和处理的符号的集合
数据元素，是数据的基本单位，常作为一个整体来处理
一个数据元素由数据项构成，数据项是构成数据元素的不可分割的最小单位
数据对象，是具有相同性质的数据元素的集合，是数据的一个子集(有点像类的概念)
数据结构，是相互之间存在一种或多种特定关系的数据元素的集合(强调的是关系)

数据结构的三要素、逻辑结构、物理结构、数据的运算
逻辑结构：集合(408已删除)、线性、树、图
基本运算：查找、插入、删除、
存储结构：顺序存储、(非顺序存储)链式、索引、散列
顺序存储是连续的，非顺序存储是离散的
存储结构影响存储空间分配的方便程度，影响对数据运算的速度

数据类型，是一个值的集合和定义在此集合上的一组操作的总称
1)原子类型，值不可再分的数据结构，如布尔值
2)结构类型，值可以再分解为若干成分的数据类型，如坐标
抽象数据类型，是抽象数据组织及与之相关的操作

算法：对特定问题求解步骤的一种描述
算法的特性：有穷性、确定性(相同的输入要得到相同的输出)、可行性(可以用代码实现)、输入和输出
好的算法：正确性、可读性、健壮性(非法输入时不会出现异常)、高效率和低存储量需求

时间复杂度

时间复杂度
忽略低阶、常数、系数
T(n)=O(n)
O(1)<O(log2 n)<O(n)<O(nlog2 n)<O(n2)<O(2^n)<O(n!)<O(n^n)
可以用洛必达法则比较，常对幂指阶(常对n幂指阶n^n)
结论：顺序代码可以忽略，只关注循环和嵌套循环，循环次数可能是对数
主要考察最差和平均时间复杂度

空间复杂度
S(n) = O(1) 和n无关称为算法原地工作
结论:关注数组和函数递归调用

2 线性表

线性表，是具有相同类型的n个数据元素的有限序列，
n为表长，n=0时为空表，用L=(a1,a2,...an)表示
位序从1开始，表头元素、表尾元素、直接前驱、直接后继

基本操作：初始化、销毁、插入、删除、按值查找、按位查找、求表长、输出所有、判空
函数名：参考严蔚敏版initList、destroyList、listInsert、listDelete、locateElem、getElem、length、printList、empty
带回来：使用引用类型变量&，C不支持引用类型变量

顺序表

顺序表，用顺序存储实现线性表，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元，可以用动态数组来实现
静态分配和动态分配
特点：
1)随机访问，在O(1)时间内即能找到第i个元素
2)存储密度高，每个节点只存储数据元素
3)拓展不方便
4)插入、删除不方便，需要复制大量数据

实现代码：1定义顺序表、2初始化、3增加长度、4插入元素、5删除

注意健壮性：插入的超过了length，插入时已经满了
删除的不在length范围内
要点：注意位序和下标区别、健壮性、用&带回来

顺序表的查找
6按位查找
如果是用静态数组存储，直接return data[i-1]即可
如果是malloc动态分配数组，也是return data[i-1]，计算机背后会用变量类型所占空间去计算地址

7按值查找
通过for循环，判断相等后返回结果
如果是结构体类型，C语言不能直接==去判断相同，需要逐个比较元素
(初试中不严格要求，可以用==，但如果考的是C语言，则语法要严格)
时间复杂度，最好O(1)最坏O(n),平均是O(n)

实现代码

#include <malloc.h>
#include <stdio.h>
#include <stdbool.h>

#define InitSize 10
//1 定义顺序表
typedef struct {
    int *data;//data指向一个数组
    int size;
    int length;
} SqList;

//2 初始化,C++语言这里要传引用SqList &L，但是C不支持，但可以用指针来实现传引用
// 为了传引用不用SqList L声明L;而用SqList* L,C++里可以用前一种
void init(SqList * L) {
    L->size = InitSize;
    L->data = (int *) malloc(L->size * sizeof(int));
    L->length = 0;
    for (int i = 0; i < InitSize; i++) {
        L->data[i] = 0;
    }
}

//3 增加长度
void resize(SqList * L, int len) {
    int *p = L->data;
    L->data = (int *) malloc((L->size + len) * sizeof(int));
    L->size = L->size + len;
    for (int i = 0; i < L->length; ++i) {
        L->data[i] = p[i];
    }
    free(p);
}
//4 插入
bool insert(SqList * L, int i, int e) {
    if (i < 0 || i > L->length) {
        return false;
    }
    if (L->length > L->size) {
        return false;
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i] = e;
    L->length++;
    return true;
}
//5 删除
bool delete(SqList * L, int i) {
    if (i < 0 || i > L->length) {
        return false;
    }
    for (int j = i; j < L->length; ++j) {
        L->data[j] = L->data[j + 1];
    }
    L->length--;
    return true;
}
//main里传指针来改变值
int main() {
    SqList L;
    init(&L);
    resize(&L,20);
    insert(&L,5,100);
    delete(&L,5);
    printf("%d",L.size);
    return 0;
}

单链表

链式存储实现的线性表，分为单链表、双链表、循环链表、静态链表
优点：改变容量方便，缺点：不支持随机存取

定义单链表，
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;
用typedef重命名，写起来更简洁，类型LinkList等价于LNode*
单链表只需要声明一个头指针L，2个别名中，虽然是等价的，但LinList表示链表，LNode表示节点，可读性更高

实现代码：初始化、
插入-1按位序带头节点:查找第i-1个元素,再插入元素
	2按位序不带头节点：(需要处理头结点)
	3指定结点后插：直接删除后一个即可
	4指定结点前插
前插：a是根据头结点循环遍历找到p的前一个结点，b是在p后插入后，交换和p的数据元素的值

删除-5按位序删除：查找第i-1个元素的方式和插入一样
	6指定结点删除：和后一个交换值，把后一个free掉，但如果没有后一个了，只能从头结点顺序查找了

单链表的查找
7按位查找
和前边的插入查找第i-1的操作一样，只不过要返回第i个结点，
边界情况i=0时，返回的是头结点，i>length时，retun最后一个元素的next=NULL

8按值查找
依次遍历，判断值相等，则返回该结点，注意如果比较的是复杂类型，要自己去判断内部的值

建立单链表
9尾插法
第一种，每有一个元素就循环到末尾执行插入，需要设置一个length变量存储链表长度
创建一个长度n的单链表，时间复杂度为1+2+...+(n-1)为O(n2)
第二种,设置一个指针存储末尾结点，创建长度n的时间复杂度为O(n)
10头插法
每次都对头结点进行后插，和上边第2种相似
养成习惯，初始化时，把头结点next设为NULL
这种方式，获取的单链表是一种逆序的，这是一个经常考察点-链表的逆置

实现代码

#include <malloc.h>
#include <stdbool.h>

//1 定义单链表
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,LinkList;//这里可以理解为，把struct LNode * 命名为LinkList

//2 初始化
void init(LinkList* L){
    //L=NULL;不带头节点
    //带头结点
    L=(LNode *) malloc(sizeof (LNode));
    L->next = NULL;
}
//3 按位序插入
bool insert(LinkList* L,int i,int e){//这里L是指针
    if(i<1) return false;
    //不带头结点时，需要处理头结点
//    if(i==1){
//        LNode *S =(LNode*) malloc(sizeof (LNode));
//        S->data=e;
//        S->next = L;
//        L= S;
//    }
    //以上
    LNode *p;
    p=L;
    int j=0;//p初始指向头节点，不带头结点时j=1开始
    while(p!=NULL && j<i-1){//带头结点的位序从1开始存储
        p=p->next;
        j++;
    }
    if(p==NULL) return false;//i超过了链表长度
    LNode *S =(LNode*) malloc(sizeof (LNode));
    S->data = e;
    S->next = p->next;
    p->next = S;
    return true;
}
//4 指定结点后插和前插
bool insert2(LNode * p,int e){
    if(p==NULL) return false;
    LNode *S =(LNode*) malloc(sizeof (LNode));
    if(S=NULL) return false;//可能内存分配失败，可写可不写
    S->data = e;
    S->next = p->next;
    p->next=S;
//    如果是前插，再交换一下值
    int tmp = p->data;
    p->data=S->data;
    S->data=tmp;
    return false;
}
//5 按位序删除，找元素和插入一样，这里默认是带头结点的
bool delete(LinkList* L, int i, int* e){
    //这里e用引用类型，可以把删除的内容带回去，给调用者
    if (i < 1) return false;
    LNode *p;
    p = L;
    int j = 0;//p初始指向头节点
    while (p != NULL && j < i - 1) {//找到第i-1个
        p = p->next;
        j++;
    }
    if (p == NULL) return false;//i超过了链表长度
    if(p->next=NULL) return false; //i是最后一个元素
    LNode* q = p->next;
    e=&(q->data);//这里有点问题，后边都free了，这里怎么还能留住值呢，建议改成return e
    p->next=q->next;
    free(q);
    return true;
}
//6 指定结点删除:和后一个交换值，把后一个free掉，但如果是最后一个，只能从头结点顺序查找了
bool delete2(LNode *p){
    LNode *q = p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);
    return true;
}
int main() {
    LinkList L;//等同于struct LNode * L
    init(&L);
    insert(&L,1,8);
    LNode p = *(LNode*) malloc(sizeof (LNode));
    insert2(&p,5);
    int e;
    delete(&L,3,&e);
    delete2(&p);
    return 0;
}

双链表

有前驱和后继指针

实现代码：1定义双链表，2初始化，
3对指定结点后插，注意没有后继结点的情况
4按位序插入，找到位序的前一个结点，对他进行后插操作
5对指定结点删除其后一个结点，注意没有后继结点的情况

6销毁：遍历依次删除
7遍历：后向p=p->next,前向p=p->prior
8查找：双链表不支持随机存取，可以设一个计数，依次遍历来实现按位、按值查找

实现代码

//1定义双链表
typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

//2 初始化，带头结点，传入的是指针类型
bool init(DLinkList L){
    L=(DNode*)malloc(sizeof (DNode));
    if(L=NULL) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}
//3 按指定结点插入,注意执行顺序：q后- p后结点的前=q - q前=p -p后
bool insert(DNode *p,DNode *q){
    q->next = p->next;
    if(p->next !=NULL){
        p->next->prior =q;//注意边界：p无后继结点，这句不执行
    }
    q->prior=p;
    p->next = q->prior;
    return true;
}
//4 删除指定p后的q
bool delete(DNode *p){
    if(p==NULL) return false;//异常处理
    if(p->next==NULL) return false;//注意边界：p没有后结点
    DNode *q = p->next;
    p->next = q->next;//q可能是最后一个，此时为null不影响
    if(q->next !=NULL){//q不是最后一个结点时才执行
        q->next->prior=p;
    }
    free(q);
    return true;
}

循环链表?

循环单链表
定义结点不变，初始化时，让L->next=L
判空和判断是否最后一个结点，不再是NULL，而是判断是否指向L
循环单链表，只要有一个结点，可以循环遍历到任意结点

若想操作表头表尾的前插、后插，之前都是L(链表的起点)指向头结点的，可以让L指向表尾元素，这样，找到表头的前或后一个结点都非常容易

循环双链表
定义结点不变，初始化时，让L->next=L，L->prior=L
前边处理后插时，要处理最后结点next=NULL,这里就不存在这种空指针

静态链表?

先分配一大块区域，它的每个结点都由（data和数组下标）构成
用数组下标替换了之前单链表的指针,最后一个元素的下标设为-1
因为是连续区域，可以用数组定义静态链表
typedef struct{
    int data;
    int index;
} SLinkList[10];
等价于
typedef struct Node{
    int data;
    int index;
};
typedef struct Node SLinkList[10];

插入位序为i的结点，
1从头结点循环，找到一个空结点比如k存数据
2找到位序i-1的结点，它的next改成k
3把空结点的next改成位序i-1的之前的next
找空结点为防止脏数据，初始化时应该把next都设为某个值，如-2

删除某个结点：
1从头结点循环，找到前驱结点，修改它的next为要删的结点的next
2把要删的next改成-2

优缺点：
增删不需要移动元素指针，容量是固定的

对比总结

顺序表和链表都是线性结构
优缺点：随机存取、存取密度、连续空间、改变容量
基本操作：创建、销毁、扩容、增删改查、判空、判结尾、

注意边界、时间复杂度、修改指针顺序、
顺序查找按值查找为O(n),如果有序，使用算法为log2N
malloc声明的存在堆区，必须手动free，静态数组是系统自动回收

3 栈和队列

栈是只允许在一端进行插入和删除的线性表，stack
栈顶、栈底、空栈，特点：后进先出LIFO

实现：创建、销毁、进栈、出栈、读栈顶元素、判空、判满
常见考题：abcde合法的出栈顺序

n个元素，出栈排列个数为1/n+1 *C2n n 卡特兰数

顺序栈

顺序栈：用顺序存储实现的栈，可以用数组定义
注意审题：top指针指向栈顶元素，还是栈顶的下一个元素
缺点：空间不可变，解决：链式存储或共享栈(栈满top0+1 =top1)

链栈：只能在单链表的一头(如表头)增加删除,写一下实现代码，可使用单链表实现

顺序栈实现代码

//1定义栈
typedef struct{
    int data[10];//静态数组来存储栈
    int top;//栈顶指针
} SqStack;
//2初始化栈
void initStack(SqStack *S){
    S->top = -1;
}
// 3入栈
bool push(SqStack *S,int e){
    if(S->top == 10-1)return false;
    S->data[++S->top]=e; //注意先++相当于写2行代码，先加一，再使用，top++; data[top]=e
    return true;
}
// 4出栈、读栈顶
bool pop(SqStack *S,int* e){
    if(S->top==-1) return false;
    e = &(S->data[S->top--]);
    return true;
}

// 传入指针变量
int main(){
    SqStack S;
    initStack(&S);
    push(&S,10);
    int e;
    pop(&S,&e);
    printf("%d\n",S.top);
    printf("%d\n",e);
    return 0;
}

链式栈?

1	长度不固定，可以无限扩展

顺序队列

队列：只能在一端插入，另一端删除，称为入队和出队
是一种操作受限的线性表
先进先出FIFO，后进先出LIFO

顺序实现的队列：可用数组定义，包含队头、队尾指针
插入：当rear指针到数组末尾时，下次插入让rear+1%length,取余后指向数组起始端，这叫循环队列，
循环队列：
方案1：判空front==rear，判满(rear+1)%arr.len ==front,队尾的后一个是对头指针时，这里已满时会有一个空间被浪费，无法插入
方案2：考题要求不能浪费空间时，需要增加一个size参数，判空和判满都是front==rear，但空时size=0
方案3：增加一个操作类型参数tag，只有删除才能变空，增加才能变满

注意审题，以上都是rear指向队尾元素的下一个位置，先在rear写入元素，再rear加1
		也有队尾指向队尾元素的考题，先rear加1，再在rear写入元素，这种方式初始化front=0,rear=len-1比如9,不浪费空间的：判空(rear+1)%len=front且size=0,  判满(rear+1)%len=front且size=10，如果浪费的，就是+2

实现代码

//1定义顺序队列
typedef struct {
    int data[10];
    int front,rear;
} SqQueue;
//2初始化
bool init(SqQueue *Q){
    Q->front = Q->rear = 0;//判空，2者相等时
}
//3 入队
bool enter(SqQueue *Q,int e){
    if( (Q->rear +1)%10 == Q->front ) return false;//已满：下一个位置等于front
    Q->data[Q->rear]=e;
    Q->rear = (Q->rear +1)%10;//循环队列
    return true;
}
//4 出队
bool leave(SqQueue *Q,int *e){
    if( Q->rear == Q->front) return false;//对空，当前位置等于front
    e = &(Q->data[Q->front]);
    Q->front = (Q->front+1)%10;//只获取对头，不需要出队时，不用这一步
    return true;
}
//3 入队-不带头结点
bool enterNull(SqQueue *Q,int e){
}
//4 出队-不带头结点
bool leaveNull(SqQueue *Q,int *e){
}
// 传入指针变量
int main(){
    SqQueue Q;
    enter(&Q,99);
    int e;
    leave(&Q,&e);
    return 0;
}

链式队列

1 2	可以用插入删除有限制的单链表实现带头结点/不带头结点的初始化、插入、删除

实现代码

typedef struct LinkNode{
    int data;
    struct LinkNode* next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear;
}LinkQueue;
//1初始化
void init(LinkQueue *Q){
    Q->front =Q->rear= (LinkNode*)malloc(sizeof (LinkNode));
    Q->front->next=NULL;
}
//2判空
bool isEmpty(LinkQueue *Q){
    if(Q->front ==Q->rear){
        return true;
    }else{
        return false;
    }
}
//3入队，带头结点，在表尾添加节点
void enter(LinkQueue *Q,int e){
    LinkNode *S = (LinkNode*) malloc(sizeof (LinkNode));
    S->next=NULL;
    S->data = e;
    Q->rear->next = S;
    Q->rear = S;
}
//4出队,带头，头不变，删除其后第一个节点
bool leave(LinkQueue *Q,int *e){
    if(Q->front ==Q->rear){ return false;}
    LinkNode *p=Q->front->next;//第一个节点是p，删除p
    e=&(p->data);
    Q->front->next=p->next;//删除p
    if(Q->rear==p){
        Q->rear=Q->front;//注意当删除的是最后一个节点时，需要队尾指针指向
    }
    free(p);
    return true;
}
int main(){
    LinkQueue Q;
    int *e;
    init(&Q);
    enter(&Q,10);
    leave(&Q,&e);
}

双端队列?

栈：一端插入和删除，队列：一端插入，另一端删除
双端队列：两端插入，两端删除，(1端插入2端删除)、(2端插入1端删除)
考点：当输入为1234，判断哪些输出序列合法(栈也常考这种题)

栈中合法的，双端里也一定合法(双端多了一些输入端或输出端)

//字符数组传参：可用指针或数组2种方式接收
bool bracketCheck1(char *str,int length){
    for (int i = 0; i < length; ++i) {//这两种接收方式都可以
        printf("%c\n", str[i]);
    }
}
bool bracketCheck2(char str[],int length){
    for (int i = 0; i < length; ++i) {
        printf("%c\n", str[i]);
    }
}
int main(){
    char str[]="1312313aad";//这两种定义方式都可以
    char str[10]={'1','2','{','3','4','5','}','6','[',']'};
    bracketCheck1(str, 10);//注意这里只需要写数组名
    bracketCheck2(str, 10);
}

栈和队列应用?

1 括号匹配问题(IDE检查缺少括号的错误)
最后出现的左括号最先被匹配，把所有左括号依次入栈
每输入一个右括号，把一个左括号配对出栈

算法：开始->是否还有未处理的括号(循环)->是左还是右->左入栈，右先判空，再匹配出栈->匹配是否成功
考试中可以直接使用一些基本操作，只需要对接口进行说明

2 表达式求值问题
分3种：前缀表达式、中缀表达式，后缀表达式(后缀常考)
一般表达式为 (1+2)*3-6/3
波兰表达式=前缀，逆波兰=后缀，在不使用限定符()情况下求表达式的值
a+b,分别表示为前缀+ab,中缀a+b,后缀ab+

上式用后缀表示 12+3*63/-,
写的时候可以加括号帮助理解，最后再去掉(((12+)3*)(63/)-) 
由于a+b+c，先算a+b还是b+c结果一样，但为了确定性，应当按照“左优先原则”，只要左边的可以先运算，就优先算左边

手算：从左往右扫描，每遇到一个运算符，就计算其前边的2个操作数，合体为1个操作数
后缀的机算：1从左到右扫描元素 2遇到数字则入栈 3遇到运算符则弹出2个栈顶的数计算，再把计算结果入栈(注意先弹出的右操作数)
中缀转成前缀，采用右优先原则(机算时，先弹出的是左操作数)

算法实现：1中缀转后缀 2使用栈计算后缀
1遇到操作数，直接加入后缀表达式
2遇到括号，左(直接入栈，右)依次弹出栈内运算符，直到左(为止
3遇到运算符，依次弹出栈内优先级>或=的，加入到后缀表达式，直到左(或栈空为止。再把当前遇到的运算符入栈
简单来说，就是:数入式，左入栈，右弹到左，符号先判断弹到左再入栈

中缀的机算：1初始化数栈和运算符栈
2扫到数，入数栈 3扫到运算符，和上边逻辑一样，先弹出优先级高于等于的，再入栈 4每弹出一个，需要弹出2个数计算，再把结果压入数栈

3 递归
递归的本质是函数调用，最后被调用的先执行LIFO
使用栈存储：调用返回地址，实参，局部变量
可以解决：把原始问题转为 属性相同，规模较小的问题

4 队列的使用
树的遍历
图的广度优先遍历
进程的先来先服务FCFS

实现代码

//括号匹配
typedef struct {
    char data[100];
    int top;
}SqStack;//也可以使用链栈
bool init(SqStack *S); //初始化栈
bool isEmpty(SqStack *S); //栈的判空
bool push(SqStack *S,char *e); //入栈
bool pop(SqStack *S,char *e); //出栈
bool bracketCheck(char str[],int length){
    SqStack S;
    init(&S);
    for (int i = 0; i < length; ++i) {//循环检查元素
        if(str[i]=='{'||str[i]=='('||str[i]=='['){//左括号入栈
            push(&S,&str[i]);
        }else{
            if(str[i]==')'||str[i]==')'||str[i]==')' && isEmpty(&S)) return false;//匹配到右括号，但栈空，说明有多余的右括号
            char topE;
            pop(&S,&topE);//右括号出栈
            if(str[i]==')'&&topE !='(') return false;
            if(str[i]==']'&&topE !='[') return false;
            if(str[i]=='}'&&topE !='{') return false;
        }
    }
    return isEmpty(&S);//最后栈若不空，说明有多余的左括号
}

int main(){
    char str[10]={1,2,'{',3,4,5,'}',6,'[',']'};
    bracketCheck(&str[10],10);
}
//中缀转后缀

//后缀的机算

//中缀的机算

4 串

矩阵

一维数组
二位数组：行优先和列优先的地址计算

对称矩阵：
1压缩存储空间大小 
2按行优先+下三角，矩阵下标转一维数组的算法(注意数组下标减1)

三角矩阵：同上，多一个常数

对角矩阵(带状矩阵)：
根据下标aij计算数组位置arr[k]，根据数组arr[k]求出下标aij
k=2i+j-3
反求，下标k是第k+1个元素，在i-1和i行之间，
3(i-1)< k+1 <= 3i-1
取整 i=|(k+2)/3|,再根据kij关系求出j

稀疏矩阵：
采用三元组压缩存储，每个元素为(i,j,v)，用数组直接存
还是三元组，但采用十字链表存 ？？？P32

字符串

主串、子串、
位置：是字符在串中的序号，从1开始，可以是空格
串是限制了字符的线性表，通常以子串为操作对象(增删改查)

实现操作：赋值、复制、判空、求串长、清空、销毁、
串联接、求子串、定位(子串在主串中的位置)、比较(逐个比较字符，ac比ab大)

静态数组(定长顺序存储)、动态数组(堆分配存储)
可以采用舍弃char[0],从1开始，末尾存储length值
链式的串：可以采用每4个char存一个节点

求子串：
比较串：当都比较了且相同，最后返回长度的差
定位：循环求子串，再利用比较串

//定位：循环使用了基本操作--求子串和比较子串
int getIndex(String S,String T){
    for (int i = 0; i <= n-m+1; ++i) {
        String Q = subString(i,S,m);//求长度一样的子串
        int index = compare(T,q);//比较子串
        if(index>0) return index;
    }
}

字符串模式匹配

1 朴素模式匹配
主串长n,模式串长m,将所有长m的子串和模式串比较，最多有n-m+1个子串
最坏时间复杂度O(nm)

2 KMP算法(重点)
优化：i不回退，只让j回退
考题：求next[]:*它只和模式串有关*
思想：S长100，T长6，当检查到第6个不符时，此时i=6,前5个的值是可知的，此时比较·前5个的后缀和T的前缀，即求next[]

当长为4的后缀和T的长为4的后缀一样时，让j=5和i=6比较,再比较后边的
当长为3的后缀和T的长为3的后缀一样时，让j=4和i=6比较,再比较后边的

这里有几个关键值，第k个匹配失败，最大匹配的前后缀长度t,next[k]=t+1
,其中设next[1]=0

2种边界情况:
第1个就匹配失败时，令next[1]=0，再i++,j++比较下一个元素
最大匹配前后缀长为0时,next[k]=1,这种不需要特殊处理

next[1]无脑等于0,next[2]无脑等于1
next[3]它的前边2个的前后缀长度只能是0和1，因此可以等于1或2
不管第几个匹配失败，前边k-1个肯定和模式串一致，因此next[]是确定的

最坏时间复杂度O(m+n),其中求next为O(m),模式匹配最坏O(n)

考题：求nextval[]: next优化
abaabc
当第3个字符a匹配失败，它对应的next字符即第1个也是a，让它对应的next值等于第1个的next值
当第4个字符b匹配失败，它对应的next字符即第2个也是b, 则让它对应的next值等于第2个的next值

实现代码

//使用朴素模式匹配
//S长度n，T长度m
int getIndex(String S, String T){//主串S，模板串T，T在S中的位置
    int i=1,j=1;
    while(i<=n-m+1 && j<=m ){//原教程这里写的i<=n
        if(S.ch[i]==T.ch[j]){//注意是i和j
            ++i;++j;//此数j同步,方便回退到起始位置
        }else{
            i=i-j+2;//回退到下一个要检查的子串起始位置
            j=1;//回退到子串的第一个位置
        }
    }
    if(j>m){
        return i-m;//当检查完与模板串一样，返回位置，即i-m
    }else{
        return 0;//如果前边循环完了，j<m即没有子串与模板串一样
    }
}
//KMP算法
typedef struct String {
    char * data;
    int length;
}String;

//最坏时间复杂度O(m+n),其中求next为O(m),模式匹配最坏O(n)
int getIndex(String S, String T,int next[]){
    int i=1,j=1;
    while(i<=S.length && j<T.length){
        if(S.data[i]==T.data[j] || j==0){//这里添加了next[1]=0
            ++i;++j;
        }else{
            j=next[j];//这里改变了j移动，朴素算法i和j都回退了
        }
    }
    if(j>T.length){
        return i-T.length;
    }else{
        return 0;
    }
}

5 树

根结点、边、分支结点、叶子结点、空树、子树
非空树有且仅有1个根节点、
叶子结点没有后继、
根结点没有前驱，
任何结点(除了根节点)有且仅有1个前驱

术语
关系：
祖先结点-只要更接近根的(二叔也算)，子孙结点-由它分出去的，
父节点(双亲结点)-直接前驱，孩子结点-直接后继，
兄弟结点-二叔和三叔(它们的父节点一样)，堂兄弟结点-同一个爷爷，但不一定是同一个爸爸(你和二叔的孩子)

路径：只能从上到下，路径长度：经过几条边
结点的深度(层次)：从上往下数，可能从0或1开始
结点的高度：：从下往上数
树的高度：总共多少层

结点的度：有几个分支(直接后继的个数)
树的度：各结点度中取最大值

有序树：各子树左右有次序的，不能互换
无序树：左右可以互换
森林：几个互不相交的独立的树的集合

高频考点：
1 结点数=总度数+1

2 树的度和几叉树
树为3度，则至少有1个为3度
三叉树，则只要度都不超过3，可以是空树

3 三叉树或者度为3的树，它的第i层最多有3的i-1次方个结点(m叉树同理)

4 高为h,度为m,则至多有(1-m^h)/(1-m) 

5 n个结点的m叉树，其高度最小为【logm( n(m-1)+1 )】向上取整
 由第4式 f(m,h-1) < n <= f(m,h)推出

二叉树

二叉树：1每个结点至多有2个子树，2左右子树不能颠倒，3左右子树可以是空树，二叉树也可以是空树

满二叉树：1只有最后一层有叶子结点 2叶子的度为0其余都是2 3高h的结点数为2^h-1 4结点i的左孩子为2i右孩子为2i+1

完全二叉树：1 在满二叉树上可以去掉一些最大的结点，2最多有1个度为1的结点，3总共n个结点，则i<=[n/2]为分支结点，i>[n/2]为叶子结点，向下取整

二叉排序树：左子树都小于根节点，右子树都大于根节点

平衡二叉树：任一结点的左子树和右子树的深度之差不超过1，可用来优化排序树

高频考点
1 度0，1，2的分为有n0,n1,n2个，则n0=n2+1
由 n=n0+n1+n2结点数 和n=n1+2n2+1总度数 推出

2 二叉树第i层，最多2^(i-1)个结点
  高度h的二叉树，结点最多有2^h-1个
3 完全二叉树有n个结点，则其高度为 [log2 (n+1)] 或[log2 n]+1
  由n个结点，可推出n0,n1,n2个数
  有完全二叉树最多1个度为1的结点，可知n1=0或1
  有n0=n2+1，可知n0+n2为奇数，
  当n=2k为偶数时，n1=1,n0=k,n2=k-1
  当n=2k-1为奇数时，n1=0,n0=k,n2=k-1

顺序存储

完全二叉树，可以反应其对应关系
i的左孩子2i，右孩子2i+1,父节点[i/2]向下取整
是否有左孩子 2i<=n,右孩子2i+1<=n,是否是分支结点i>[n/2]

普通二叉树，按完全二叉树来存储，可以反应其关系，但无法直接判断是否有左右孩子
i是否有左孩子，需要找到2i，判断2i是否为空

typedef  struct TreeNode{
    int data;
    bool isEmpty;
}TreeNode;

void init(){
    TreeNode t[100];
    for (int i = 0; i < 100; i++) {
        t[i].data = 0;
        t[i].isEmpty = true;
    }

链式存储

二叉链表，找左右孩子很容易，找父节点不容易，可以再增加一个父指针，变为三叉链表
    
typedef struct TreeNode{
    int data;
    struct TreeNode *leftChid,*rightChid;
}TreeNode,*Tree;

void init(){
    Tree root = NULL;
    root = (Tree)malloc(sizeof (Tree));
    root->leftChid =NULL;
    root->rightChid = NULL;
}

遍历算法

考点：先序：根左右，中序：左根右，后序：左右根
算数表达式的分析树：对应前中后缀表达式

递归遍历
void PreOrder(Tree T){
    if(T!=NULL){
        visit(T);//先序，如果是中序把这个方法放在中间，visit可以是打印方法
        PreOrder(T->leftChid);
        PreOrder(T->rightChid);
    }
}
时间复杂度O(h)
    
考题一般是这个算法的变种，比如求树的深度
int treeDepth(Tree T){
    if(T=NULL){
        return 0;
	}else{
        int l = treeDepth(T->leftChild);
        int r = treeDepth(T->rightChild);
		return l>r ? l+1 :r+1;
    }
}

层序遍历

初始化一个辅助队列，
从根开始，每次父节点出队时，让它的子结点入队

typedef struct LinkNode{
    Tree *p;//保存的是子树的指针
    struct LinkNode *next;
} LinkNode;//队列的结点
typedef  struct {
    LinkNode *front,*rear;
} LinkQueue;//队列，只保持队头和队尾指针

void LevelOrder(Tree T){
    LinkQueue Q;
    initQueue();
    EnQueue(Q,T);
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->leftChild !=NULL) EnQueue(Q,p->leftChild);
        if(p->rightChild !=NULL) EnQueue(Q,p->rightChild);
    }
}

由树写出先序序列是唯一的，但由序列写出树是不唯一的，需要由中序+另外一种，才能唯一确定树
考题，已知中序ABCDE，先序BACDE，则可以确定树的形态

线索二叉树

普通二叉树，查找孩子结点容易，但查找一个任意结点或查找基于遍历序列的前驱后继，必须从根节点开始，依次遍历所有结点

中序线索二叉树：把叶子结点的原本空着的左右指针，指向前驱后继结点，用标志位区分指向的是孩子还是线索

考点：中序前驱、中序后继、先序前驱、先序后继、后序前驱、后序后继
typedef struct TreeNode{
    int data;
    struct TreeNode *leftChid,*rightChid;
    int ltag,rtag;//0表示孩子，1表示线索
}TreeNode,*Tree;

//土办法中序遍历找到指定结点的前驱
void visit(TreeNode q){
    if(q==p){
        final = pre;
    }else{
        pre=q;
    }
}

void InOrder(Tree T){
    if(T!=NULL){
        InOrder(T->leftChid);
        visit(T);
        InOrder(T->rightChid);
    }
}

//利用上边这种土方法的逻辑进行线索化
typedef struct TreeNode{
    int data;
    struct TreeNode *leftChid,*rightChid;
    int ltag,rtag;//0表示孩子，1表示线索
}TreeNode,*Tree;
//1线索化
void visit(TreeNode *q){
    if(q->leftChid==NULL){
        q->leftChid = pre;
        q->ltag=1;
    }
    if(pre->rightChid==NULL && pre !==NULL){
        pre->leftChid=q;
        pre->rtag=1;
    }
    pre=q;
}
//2中序遍历
void InOrder(Tree T){
    if(T!=NULL){
        InOrder(T->leftChid);
        visit(T);
        InOrder(T->rightChid);
    }
}
//3线索化完，要处理最后一个结点
TreeNode *pre = NULL
void Create(Tree T){
    pre =NULL;
    if(T!=NULL){
        InOrder(T);//调用线索化
        if(pre->rightChild ==NULL){//教材版由于中序遍历最后肯定是NULL，因此省去了判断，写成了pre->rightChild=NULL;
            pre-rtag=1;//处理最后有个节点
		}
	}
}
//教材版，把visit代码直接写在了InOrder里，同时把pre定义成InOrder的引用变量
    
//先序线索化，大致都一样，但是存在死循环的问题，中后序不存在这种问题
typedef struct TreeNode{
    int data;
    struct TreeNode *leftChid,*rightChid;
    int ltag,rtag;//0表示孩子，1表示线索
}TreeNode,*Tree;
void PreThread(Tree q,Tree &pre){
    if(q!=NULL){
        if(q->leftChid==NULL){
            q->leftChid = pre;
            q->ltag=1;
        }
        if(pre->rightChid==NULL && pre !==NULL){
            pre->leftChid=q;
            pre->rtag=1;
        }
        pre=q;

        if(q->ltag==0){//上边线索化时把左子树设为了前驱线索，这里再遍历就会回去遍历前驱结点,加上判断防止死循环
            PreThread(q->leftChid,pre);
        }
        PreThread(q->rightChid,pre);
    }
}
void Create(Tree T){
    Tree pre=NULL;
    if(T!=NULL){
        PreThread(T,pre);
        if(pre->rightChid==NULL){
            pre->rtag==1;
        }
    }
}

//易错点：1先序的死循环问题，2要处理最后一个结点

前驱后继

//中序线索二叉树，查找指定结点的后继

//一个树的第一个中序结点
TreeNode *FirstNode(Tree p){
    while(p->ltag==0) p=p->leftChid;
    return p;
}
//找到后继
TreeNode *NextNode(TreeNode *p){
    if(p->rtag==0) return FirstNode(p->rightChid);//没有线索化,就是右子树的第一个元素，即其最左下角的结点
    else return p->rightChid;//如果线索化，就是后驱线索
}
//有了上边的方法，就可以不断的找后继，来实现中序遍历
void InOrder(TreeNode *T){
    for (TreeNode *p= FirstNode(T);p!=NULL;p= NextNode(p))
        visit(p);
}

//中序线索二叉树，查找指定结点的前驱

//一个树的最后一个中序结点
TreeNode *LastNode(Tree p){
    while(p->rtag==0) p=p->rightChid;
    return p;
}
//找到前驱
TreeNode *PreNode(TreeNode *p){
    if(p->ltag==0) return LastNode(p->leftChid);
    else return p->leftChid;
}
//利用它可以逆向遍历
void RevInOrder(TreeNode *T){
    for (TreeNode *p= LastNode(T);p!=NULL;p= PreNode(p))
        visit(p);
}

先序后继
如果线索化，就是后继，没有线索化，根据 根左右，有左就是左，无左就是右孩子
先序前驱
如果线索化，就是前驱，没有线索化，根据 根左右，找不到根的前一个元素，必须改成三叉链表，利用父节点找
分3种情况，根据父左右，
1如果父p右，p是左孩子，则p的前驱就是父
2如果父左p，左是空的，则p的前驱也是父
3如果父左p，左不是空子树，则p的前驱是左的最后一个先序结点
4p是根节点，则没有先序前驱，代码中要判断

后序前驱
后序后继，如果没有线索化，找不到，必须用三叉链表借助父节点找

普通树

双亲表示法，顺序存储
typedef struct TreeNode{
    int data;
    int parentIndex;//保存父结点的存储位置
}TreeNode;
typedef struct Tree{
    TreeNode nodes[100];//用数组存储
    int count;//结点数
}Tree;
//增删改查，删除一个带有非叶子结点比较麻烦，要依次把子孙全删了

孩子表示法，顺序存储+链式存储
struct childNode{
    int child;//这个孩子在数组中的下标
    struct childNode *next;//下一个孩子
}childNode;

typedef struct TreeNode{
    int data;
    struct childNode *firstChild;//只存第一个孩子，孩子和孩子之间用链表表示
}TreeNode;
typedef struct Tree{
    TreeNode nodes[100];//用数组存储
    int count,r;//结点数和根的位置
}Tree;

孩子兄弟表示法
总结：本质：任意结点，左孩子右兄弟

森林和二叉树转换(重要考点)
把森林里每个树表示成上边的孩子表示法，然后把这些不相干的树当成兄弟连起来

树和森林遍历

1 先根遍历，后根遍历
若树非空，先访问根结点，再对子树依次先根遍历
void PreOrder(R){
	if(R!=NULL){
		visit(R);//先根遍历，和转成二叉树的先序序列一样
		while(R还有子树T) PreOrder(T);
		visit(R)//后根遍历，和转成二叉树的中序序列一样
	}
}
这两种都是深度优先遍历

2 层次遍历
借助辅助队列，先让根入队，然后父出队时，让其孩子入队

3 先序遍历森林
就是对每个树依次先根遍历，等同于转成孩子表示法二叉树的先序遍历
4 中序遍历森林
就是对每个树依次进行后根遍历，等同于转成孩子表示法二叉树后的中序遍历

哈夫曼树

每个结点给一个权值
带权路径长度：某个结点的路径长度(根到结点的边数)*权值
树的带权路径长度：所有叶子结点的带权路径长度之和

哈夫曼树就是带权长度最小的树，也称最优二叉树
方法：让最小的2个权值成为兄弟，他们的权和作为它们父节点的权值，再和别的结点依次结合

哈夫曼树结点总数为2n-1,不存在度为1的结点
应用：哈夫曼编码(可变长度编码)，任何一个编码都是前缀编码，不是其它字符的前缀，每个字符都必须是叶子结点

并查集？

把每个集合分别表示为树，组成森林
常用操作
1查属于哪个集合：找到它的根
2比较是否同一个集合：比较他们的根
3并-把2个集合合并：让一个树成为另一棵的子树

6 图

概念

图G由顶点集V和边集E组成，G=(V,E)

无向图中，E是无向边，用小括号(v,w)表示边
有向图中，E是有向边，用尖括号<v,w>表示边

简单图：不存在顶点到自身的边
多重图：可以存在这种边

顶点的度TD(v),入度ID(v)，出度OD(v),无向图中，度和为2|E|,有向图入度=出度=|E|边数

路径-顶点序列，回路-起点和终点一样，简单路径-顶点不重复，简单回路-顶点不重复，
路径长度-边的个数，点到点距离-最短路径，
连通-2顶点有路径，强连通-正反向都有路径，
子图-原图的子集，生成子图-和原图顶点数一样，可以少一些边
连通分量-无向图的极大连通子图，要求连通的，还要包含尽可能多的顶点和边
强连通分量-有向图
连通图的生成树-包含全部顶点的极小连通子图，可能有多种，但都有n-1条边
生成森林-所有连通分量的生成树的集合
边的权，带权图，带权路径长度-一条路径所有边的权值和

几种特殊形态
无向完全图-任意2顶点都有边，有向完全图
稀疏图-边比较少，稠密图
树-不存在回路，且连通的无向图
有向树-除了顶点入度为0，其余入度都为1

G是连通图，最少有n-1条边，不连通，最多有C2 n-1条边
G是强连通图，最少n条边

邻接矩阵

用矩阵表示，缺点是空间复杂度O(n2),适合稠密图
typedef struct {
    char Vex[100];//顶点集
    bool Edge[100][100];//边集，如果是带权图，这里存int权值
    int vexnum,arcnum;//顶点数、边数
}Graph;

当用0/1存储无向图时，A^n[i][j],表示从顶点i到顶点j，长度为n的路径的数量

邻接表

用顺序+链式存储，类似孩子表示法，
求度，只要遍历*first链表的长度，对于有向图就是出度
缺点：对于有向图，求入度比较麻烦，需要遍历所有边，找到所有指向A顶点的
//边。每个边存储指向的顶点，和下一条兄弟边
typedef struct Arcode{
    int adjvex;//边指向哪个顶点
    struct ArcNode *next;//指向的下一条边
}ArcNode;
//顶点。每个顶点存储当前顶点数据(权),和第一条边
typedef struct VNode{
    int data;//顶点信息
    ArcNode *first;//第一条边
}VNode,AdjList[100];
//图，
typedef struct {
    AdjList vertices;//顶点集合
    int vexnum,arcnum;
}ALGraph;

十字链表

只能用于存储有向图
在邻接表基础上再增加一条链表，2条链表分别表示入度和出度的弧指针
typedef struct VNode{
    int data;//顶点信息
    ArcNode *head;//入度的第一条弧
    ArcNode *tail;//出度的第一条弧
}VNode,AdjList[100];

邻接多重表

只能用于存储无向图
类似十字链表，也是2条链表，只是AB和BA会指向相同的边结点

删除边
删除顶点(还要删除对应的边)

基本操作

主要考邻接表和邻接矩阵，常用的是找第1个和下一个邻接点，FirstNeighbor和NextNeighbor,可以用接口

是否存在边<x,y>
列出顶点V的边、入边、出边
插入顶点
删除顶点
添加边、入边、出边
删除边、入边、出边
*找到顶点X的第一个邻接顶点Y：遍历矩阵的第1个，遍历邻接表的第1个(找入边邻接点比较麻烦)
*找到顶点X的下一个邻接点(除了Y)：遍历矩阵的第2个，遍历邻接表的第2个
对某个边设置权值和获取权值：主要还是查找边

图的遍历

广度优先遍历BFS
1类似树的广度优先(层次遍历)，2用辅助队列父出子入，3用数组标记已访问过的顶点(访问过的顶点出现时，不再重复遍历)，4用FirstNeighbor和NextNeighbor作为for循环的条件
    
void BFS(Graph G,int v){
    visit(v);//访问v顶点
    visited[v]=true;//把v顶点标记为已访问
    Enqueue(Q,v);//把v放进队列Q
    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]=true;
                Enqueue(Q,w);
            }
        }
    }
}
//对于非连通图，还要对visited[]进行循环，对未访问过的调用BFS(G，v)
void BFSTraverse(G){
    for(i=0;i<G.vexnum;i++){//初始化数组
        visited[i]=false;
    }
    initQueue(Q);//初始化队列
    for(i=0;i<G.vexnum;i++){
        if(!visited[i]) BFS(G,i);//执行循环遍历
    }
}
时间复杂度分析
=访问顶点的时间O(v)+访问所有边的时间(邻接矩阵和邻接表不同)
//邻接矩阵的每个顶点的所有边都要遍历一次，为O(v2)
//邻接表的每个顶点的边即NextNeighbor它最好情况是没有边为0，最差情况是都有边为v-1,总体次数取决于边的数量，为O(2|E|)
 
广度优先遍历序列，邻接矩阵顺序是固定的，邻接表则不唯一
    
广度优先生成树
上边的广度优先算法，会丢弃一些回路的边，只能保证每个顶点都被访问

如果是有向图，算法不变，只不过一般不能一次BFS访问完所有顶点，如果是强连通图，则可以一次BFS遍历完所有顶点

深度优先遍历DFS
1类似树的先根遍历，根左右
void PreOrder(Tree R){
    if(R!=NULL){
        visit(R);
        while(R还有子树T){
            PreOrder(T);
        }
    }
}
void DFS(Graph G,int v){
    visit(v);//访问v顶点
    visited[v]=true;//把v顶点标记为已访问
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){//还有下一个邻接点
        if(!visited[w]) DFS(G,w);
    }
}
void DFSTraverse(G){
    for(i=0;i<G.vexnum;i++){
        visited[i]=false;
    }
    for(i=0;i<G.vexnum;i++){
        if(!visited[i]) DFS(G,i);
    }
}

时间复杂度分析
//空间复杂度最坏为调用v层递归，O(v),最好的只有1层，O(1)
//时间复杂度，邻接矩阵为O(v)+O(v2)=O(V2),邻接表为O(v)+O(2E)=O(v)+O(E)

深度优先遍历序列
邻接表如果链表顺序不唯一，则遍历序列不唯一

深度优先生成树
通过深度优先遍历算法，访问完所有顶点时，经过的边组成的树

连通性
无向图，调用DFS次数=连通分量数
有向图，若起点到其他点都有路径，则只需要1次DFS，如果是强连通图，只需要1次DFS

最小生成树

连通图的生成树：是包含所有顶点的极小连通子图
最小生成树：带权连通无向图，边的权值之和最小的生成树

Prim算法：从某顶点开始，每次把权值最小的顶点纳入，直到所有顶点都包含
时间复杂度=O(|v|2),适合边稠密的，E大的

Kruskal算法：每次选择权值最小的边，使两头连通，如果已经连通的就不选，直到都连通
时间复杂度=O(|E|log2|E|),适合边稀疏的，E小的

实现代码？

选择V0开始，计算出其他顶点加入的代价数组lowCast
从中选择未加入顶点中，代价最小的
加入后更新lowCast
再从lowCast中选择代价最小的顶点


把所有边按权值排序，得到一个数组
遍历数组，判断边的2顶点是否同属于一个集合，如果不是，就选择这条边，让它们变成同属一个集合(判断是否同属，可采用并查集)

最短路径

单源最短路径-BFS算法(无权图)和Dijkstra算法(带权图和无权图)


各顶点间的最短路径-Floyd算法(带权图、无权图)

P64

恋上教程

斐波那契

int fbnq(int n){
    if(n<=1)return n;
    return fbnq(n-2)+fbnq(n-1);
}
第一种时间复杂度为O(2^n),非常耗时
int fbnq(int n){
    if(n<=1) return n;
    int first=0;
    int second =1;
    while (n-->1){
        second+=first;
        first = second-first;
    }
    return second;
}

2 复杂度

1 评估算法好坏:
正确性、可读写(简洁易懂)、健壮性(输入不合理情况时程序不崩溃)
时间复杂度(指令执行次数)、空间复杂度(占用的存储空间)

2 估算时间复杂度
func1(int n){
	for(int i=0;i<n;i++){
		System.out.println("hello")
}}
int i=0执行1次，i<n判断n次，i++执行n次，打印n次
时间复杂度为1+3n，大O表示法为O(n)

func2(int n){
	while(n=n/2 >0){
		System.out.println("hello")
}}
除数取整8时3次，4时2次，因此是log2(n)次
大O表示法为O(logn)
for(int i=1;i<n;i*=2) 也是log2(n)次

大O表示法：忽略常量、系数、低阶，n比logn高阶
n+logn次的复杂度为O(n)
O(1)<O(logn)<log(n)<log(nlogn)<O(n^2)<O(n^3)<(2^n)<O(n!)<O(n^n)

3 斐波纳契分析
两种算法复杂度分别为O(2^n)和O(n)
算法优化方向:更少的耗时和内存，耗时和内存互换
传多个参数决定复杂度的优化方法:
最好最坏复杂度、均摊复杂度、平均复杂度、复杂度震荡
leetcode站点可练习算法，并查看别人的耗时少的算法

绪论

线性表

栈和队列

串数组广义表

树和二叉树

图

查找

排序

动态内存管理

文件

菜鸟教程

8种结构

8种：树和堆，数组、链表、栈和队列、哈希表、图
排列方式：集合-同属于无关系、线性-一对一、树-一对多，图-多对多
逻辑分类：线性、非线性

特征:
1 数组-查询快，增删慢，要修改其他的索引
2 链表-查询慢，增删快，只改1个节点的索引
3 栈-只能在栈顶操作，先进后出
4 队列-线性的一头插入，在另一头删除，先进先出
5 树-每个非根节点都只有1个父节点，0或多个子节点
6 堆-用数组表示的树，没有用指针，根据堆特性就可以确定排序，
特性：如果一个结点的位置为k，则它的父结点的位置为[k/2]取整，而它的两个子结点的位置则分别为2k和2k+1
定义：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆，(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1)
分类：满足前者的表达式的成为小顶堆（小根堆），满足后者表达式的为大顶堆（大根堆），很明显我们上面画的堆数据结构是一个大根堆，即2级的树节点值都小于3级，3级小于4级...为大根堆，逐层增加

7 散列表-根据key计算value的位置HashValue=hash(key)
通过hash算法，把key变为整数，对数组长度取余，结果当作数组下标，value就存储在该下标的数组空间里
想想计算出的下标会不会出现相同的，那么同一个位置怎么可以存2个value？于是数组就拓展为，在数组的每个位置存一个链表，链表就可以存多个value了，因此散列表=数组+链表
问题:散列表的数组怎么扩容，其他解决哈希冲突的方法，散列表的链表太长怎么办
8 图，一些顶点的集合，他们通过边相连接，分有向图和无向图，
图有2种算法:广度优先搜索算法、深度优先搜索算法
图有5大存储结构:邻接矩阵、邻接表、十字链表、邻接多重表、边集数组

5种图

1 【邻接矩阵】:1个1维数组存储顶点信息，1个2维数组的矩阵存储连接信息
无向图是对称矩阵，只计算度，即这个顶点和几个顶点相连接
有向图是非对称矩阵，计算入度和出度
#define MAXNum  100		  		 //顶点的最大值 
typedef  char  VertexType;  	 //顶点信息为字符类型
typedef  struct
{   
    VertexType   Vex[MAXNum];    //顶点表 
    int   arcs[MAXNum][MAXNum];  //邻接矩阵
    int   vexnum,arcnum;         //顶点数和边数
}MGraph;

2 【邻接表】:1个1维数组或链表存储顶点信息，每个顶点指向一个链表，存储该顶点相连接的所有顶点(有点像散列表)
稀疏图用邻接矩阵浪费空间，用邻接表更好，但顶点指向的链表顺序不唯一，因此邻接表也不唯一
无向图
有向图
#define MAXVEX 100	//图中顶点数目的最大值
typedef char VertexType;	
typedef int EdgeType;	
//边表结点
typedef struct EdgeNode{
	int adjvex;	                //该弧所指向的顶点的下标或者位置
	EdgeType weight;	        //权值，对于非网图可以不需要
	struct EdgeNode *next;	    //指向下一个邻接点
}EdgeNode;
 
//顶点表结点
typedef struct VertexNode{
	Vertex data;	            //顶点域，存储顶点信息
	EdgeNode *firstedge	        //边表头指针
}VertexNode, AdjList[MAXVEX];
 
//邻接表
typedef struct{
	AdjList adjList;
	int numVertexes, numEdges;	//图中当前顶点数和边数
}

3 【十字链表】：只用于有向图的链式存储，
1个数组或链表存储顶点信息，1个链表存储弧(边信息)
弧结点包括5个信息:头顶点、尾顶点，弧头一样的下一条弧，弧尾一样的下一条弧，弧信息
顶点结点包括3个信息:以顶点为弧头的弧，以顶点为弧尾的弧，顶点信息
因为顺序也不唯一，因此十字链表表示也不唯一
#define MAXVEX 100	            //图中顶点数目的最大值
typedef char VertexType;	
typedef int EdgeType;	        
//边表结点
typedef struct EdgeNode{
	int adjvex;	                //该弧所指向的顶点的下标或者位置
	EdgeType weight;	        //权值
	struct EdgeNode *next;	    //指向下一个邻接点
}EdgeNode;
 
//顶点表结点
typedef struct VertexNode{
	Vertex data;	            //顶点域，存储顶点信息
	EdgeNode *firstedge	        //边表头指针
}VertexNode, AdjList[MAXVEX];
 
//邻接表
typedef struct{
	AdjList adjList;
	int numVertexes, numEdges;	//图中当前顶点数和边数
}

4 【邻接多重表】:只用于无向图的链式存储，
类比邻接表，用1个数组或链表存储顶点，每个顶点指向1个存储弧的链表(实际这些链表合并为1个)邻接表中不合并，因此表示同1边会出现2次，而这里只有1次
弧结点：mark是否搜索过，该结点依附的2个顶点AB，下一条依附A顶点的边，下一条依附B顶点的边，info和边相关的各种信息的指针域
顶点结点：顶点信息，第一条依附于该顶点的边
与十字链表对比，弧和顶点都是结点
与邻接表对比，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点

邻接表-无向图-每条边存储2次优化-十字链表
邻接表-有向图-获取顶点的度困难优化-邻接多重表

5 【边集数组】，由2个1维数组组成，1个数组存储顶点，1个数组存储边，只不过这里的每个边的信息包括3个:开始顶点，结束顶点，权重

算法

1
2
3

增删改查排序
二分查找、分治算法、动态规划
KMP、贪心算法、普利姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、骑士周游算法