-1：出分了。。说明确实应该多看课本上代码。。。所以这篇笔记很不错！来看看吧

认真复习，求求

*注：大量代码未经实际验证，出现bug为正常现象（）但是思想不会有问题

Chapter1.绪论

数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。（某个判断题）

数据：对客观事物的符号表示，在cs中指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。

数据（逻辑）结构：相互之间存在一种或多种特定关系的数据元素的集合。(D,S) D 是数据元素的有限集，S是D上关系的有限集；主要有集合结构，线性结构，树形结构，图状结构

数据（存储）结构：顺序结构、链式结构

数据类型：一个值的集合和定义在该集合上的一组操作的统称。

抽象数据类型：一个表示应用问题的数学模型以及定义在该模型之上的一组操作的统称。（？）

​ 抽象数据类型定义 ADT(D,S,P): D-数据对象 S-D上的关系集 P-D上的操作集

算法：对特定问题求解步骤的一种描述，是指令的有限序列；

算法满足特性：有穷性，确定性，可行性，输入，输出

算法评价：正确性，可读性，健壮性，效率和低存储量需求

算法分析：基本运算，问题规模，时间代价，空间代价。

Chapter2.线性表

1.顺序表

插入和删除都是O(n) 访问是O(1)

插入和删除都平均需要移动一半的元素，具体公式p25

0.结构体定义

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Elemtype;
typedef struct {
    Elemtype *elem;
    int length;
    int listsize;
}SqList;

1.建表

void initSqList(SqList &L){
    L.elem=(Elemtype*)malloc(sizeof(Elemtype)*LIST_INIT_SIZE);
    if(!L.elem) exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
}

2.插入

淦。。课本上代码把我看傻了

下标从0开始

void InsertSqList(SqList &L,int i,Elemtype e){//e插入到第i个位置之前
    if(i<1||i>L.length+1) return;
    if(L.length>=L.listsize){//再分配空间
        Elemtype *newbase=(Elemtype*) realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(Elemtype));
        if(!newbase) exit(OVERFLOW);
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
    }
    Elemtype *q=&L.elem[i-1];//取i-1元素的地址，q作为第
    Elemtype *p;
    for(p=&L.elem[L.length-1];p>=q;p--) *(p+1)=*p;//p>=q我直接好家伙
    //没有下标越界问题，插入之后表长会增1
//    for(int j=L.length-1;j>=i;j--) L.elem[j+1]=L.elem[j]; mytype
    *q=e;
    L.length++;
}

3.删除

void DeleteSqList(SqList &L,int i,Elemtype &e){//删除第i个元素，并用e返回其值
    if(i<1||i>L.length) return;
    e=L.elem[i-1];
    for(int j=i-1;j<L.length-1;j++) L.elem[j]=L.elem[j+1];
    L.length--;
}

另外还有一些操作没有写..

2.单链表

相比顺序表，插入和删除都是O(1)的，但是查询是O(n)

0.结构体定义

typedef struct LNode{
    Elemtype data;
    LNode *next;
}LNode,*LinkList;

头结点：在链表的第一个节点之前附设一个节点，头节点的指针域指向第一个节点（若为空表则NULL）

头指针：头节点中的指针域即头指针；指示链表中第一个结点的存储地址，通过头指针能够索引整个链表，整个链表的存取从头指针开始进行

首元节点：存储第一个元素的节点，可能在头节点中存储，也可能是头结点指向的下一个节点

1.建表

void CreateLinkList(LinkList &L,int n){
    //头插n个元素
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    while(n--){
        LinkList p=(LinkList)malloc(sizeof(LNode));
        cin>>p->data;
        p->next=L->next;
        L->next=p;
    }
}

2.插入

void InsertLinkList(LinkList &L,int i,Elemtype e){
    //在第i个位置之前插入元素e
    LinkList p=L;
    int j=0;
    while(p&&j<i-1) {
        p=p->next;
        j++;
    }//p是现在的第i-1个节点
    if(!p) return;
    LinkList newNode=(LinkList)malloc(sizeof(LNode));
    newNode->data=e;
    newNode->next=p->next;
    p->next=newNode;
}

3.删除

void DeleteLinkList(LinkList &L,int i,Elemtype &e){
    //删除第i个元素，存入e
    LinkList p=L;
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p||!p->next||j>i-1) return;
    LinkList q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
}

4.获取元素

void GetElemLinkList(LinkList L,int i,Elemtype &e){
    //获取第i个元素
    LinkList p=L;
    int j=0;
    while(p&&j<i){
        p=p->next;
        j++;
    }
    if(!p||j>i) return;//j>i应该不可能发生吧？啊假设i非常不合法（比如-1）还是有可能的。。
    e=p->data;
}

5.合并

void MergeLinkList(LinkList &L1,LinkList &L2,LinkList &L3){
    //有序表（升序）L1 L2合并为有序表L3
    LinkList p1=L1->next;
    LinkList p2=L2->next;
    LinkList p3;
    L3=p3=L1;//用L1作L3的头节点
    while(p1&&p2){
        if(p1->data<=p2->data){
            p3->next=p1;
            p1=p1->next;
            p3=p1;//p1和p3都向后移动
        }
        else{
            p3->next=p2;
            p2=p2->next;
            p3=p2;
        }
    }
    p3->next=p1?p1:p2;//剩下的部分直接怼上去
    free(L2);//L1的头节点用作L3的表头，那么L2没用了
}

3.静态链表

在不设指针的语言中使用链表结构

结构体定义：

typedef struct {
    Elemtype data;
    int cur;
}component,SLinkList[10010];

即数组下标指示位置，非常常用并且好用，不多说

4.循环链表

最后一个节点的指针域指向头结点，从表中任意一节点触发即可到达其他节点。

5.双向链表

增加一个前指的指针域prior

void DuLinkList(DuLinkList &L,int i,Elemtype &e){
    DuLinkList p=L;
    int j=0;
    while(p&&j<i){
        p=p->next;
        j++;
    }
    //插入：
    //j=i,插入到第i个，新节点在p前面
    DuLinkList newNode=()malloc(...);
    newNode->data=e;
    newNode->prior=p->prior;
    p->prior->next=newNode;
    newNode->next=p;
    p->prior=newNode;
    
    //删除：
    //删除第i个，即删除p这个节点
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
}

6.一元多项式

用若使用顺序结构，由于指数可能不连续并且很大可能需要非常冗余的空间

使用链式结构，并且可以进行多项式加法&乘法

typedef struct {//作为Linklist的数据元素Elemtype
    float coef;//系数
    int expn;//指数
}term,Elemtype;

Chapter3.栈和队列

以线性表作为基础的两种各具特点的结构

1.栈-顺序栈

0.结构体定义

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Elemtype;
typedef struct {
    Elemtype *base;
    Elemtype *top;
    int stacksize;
}SqStack;

1.建栈

void InitStack(SqStack &S){
    S.base=(Elemtype*)malloc(sizeof(Elemtype)*STACK_INIT_SIZE);
    if(!S.base) return;
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
}

2.push

void Push(SqStack &S,Elemtype e){
    if(S.top-S.base>=S.stacksize){
        //跟链表一样，realloc再分配
    }
    *(S.top++)=e;
    //只有一句话！
}

3.pop

void Pop(SqStack &S,Elemtype &e){
    if(S.top==S.base) return;//栈空
    e=*(--S.top);//只有一句话！
}

4.top

void GetTop(SqStack &S,Elemtype &e){
    if(S.base==S.top) return;
    e=*(S.top-1);
}

？没说过链栈

5.应用

1.数制转换

栈的作用是把从个位到十位的拆分倒过来输出

void Tranverse(int n,int mod){
    SqStack S;
    InitStack(S);
    while(n) {
        Push(S, n % mod);
        n /= mod;
    }
    while(!StackEmpty(S)){
        Elemtype e;
        Pop(S,e);
        cout<<e<<' ';
    }
}

2.括号匹配检验

（（（（（（（（（（（（（（（（（（

左括号直接进栈，右括号取栈顶看是不是与之匹配的左括号

以前写的将就看

int main(){
    Stack st;
    bool fl=true;
    int n;cin>>n;
    for(int i=0;i<n;i++){
        char c;cin>>c;
        if(c=='('||c=='['||c=='{') {
            push(st, c);
        }
        else{
            char t=top(st);
            if(t=='('&&c==')'){
                pop(st);
            }
            else if(t=='['&&c==']'){
                pop(st);
            }
            else if(t=='{'&&c=='}'){
                pop(st);
            }
            else{
                cout<<"Wrong!"<<endl;
                fl=false;
                break;
            }
        }
    }
    if(!empty(st)&&fl){
        cout<<"Wrong!"<<endl;
        fl=false;
    }
    if(fl) cout<<"Right!"<<endl;
}

3.行编辑程序

#表示退格，@表示退行

4.迷宫

见https://sterne012.github.io/2021/10/28/StackLabyrinth/

5.表达式求值

感觉可能有选择题

当前运算符a，栈顶b

1. 优先级a>b：当前运算符a进栈

2. 优先级a<b：栈顶运算符b出栈，进行运算，直到栈顶运算符不满足条件a<b，重复1

通常，同级运算a和b，使a<b，进行运算

6.递归算法

阶乘

小心爆栈爆int

汉诺塔

我对它的理解就是巨神奇

static int cnt=0;
void move(char x,int i,char z){
    printf("%d Move disk %d from %c to %c\n",++cnt,i,x,z);
}
void Hanoi(int n,char x,char y,char z){
    //将x上从小到大，自上而下编号1-n的n个盘子搬到z
    if(n==1) move(x,1,z);//将编号1的圆盘从x移到z//传参的x和z不一定就是实际的x柱和z柱
    else{
        Hanoi(n-1,x,z,y);
        move(x,n,z);
        Hanoi(n-1,y,x,z);
    }
}

2.队列-链队

0.结构体定义

typedef struct QNode{
    Elemtype data;
    QNode *next;
}QNode,*QueuePtr;
typedef struct {
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

1.建队列

void InitQueue(LinkQueue &Q){
    Q.front=(QueuePtr)malloc(sizeof(QNode));
    Q.rear=Q.front;
    Q.front->next=NULL;
}

2.入队

front是头指针，不放东西

void EnQueue(LinkQueue &Q,Elemtype e){
    QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
}

3.出队

当rear就是front->next时，说明队列为空，置成初始状态

void DeQueue(LinkQueue &Q,Elemtype &e){
    if(Q.front==Q.rear) return;
    QueuePtr p=Q.front->next;
    e=p->data;
    Q.front->next=Q.front->next->next;//删除p
    if(Q.rear==p) Q.rear=Q.front;//尾指针回指
    //如果删除的p是不是队尾的节点，那么rear不会受到影响
    free(p);
}

2.队列-循环队列

0.结构体定义

#define QUESIZE 10
typedef struct {
    Elemtype *base;
    int front;
    int rear;
}SqQueue;

1.建队

void InitSqQueue(SqQueue &Q){
    Q.base=(Elemtype*)malloc(sizeof(Elemtype)*);
    if(!Q.base) return;
    Q.front=Q.rear=0;
}
int QueueLength(SqQueue &Q){
    return (Q.rear-Q.front+QUESIZE)%QUESIZE;
}

2.入队

void EnQueue(SqQueue &Q,Elemtype e){
    if((Q.rear+1)%QUESIZE==Q.front) return;//队列满，不过此时rear中没有元素（rear总指向一个空的位置）
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%QUESIZE;
}

3.出队

先进先出啊出队操作front 傻了啊

入队出队操作方式相当像

void DeQueue(SqQueue &Q,Elemtype &e){
    if(Q.rear==Q.front) return;//队列空
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%QUESIZE;
}

Chapter4.串

书跟新的一样 不，就是新的

据说只有选择判断

比如说BF和KMP的比较次数？

const int maxn=1e4+7;
int kmp[maxn];
void kmp_pre(char x[],int m){
    int i,j;
    j=kmp[0]=-1;
    i=0;
    while(i<m){
        while(j!=-1&&x[i]!=x[j]) j=kmp[j];
        kmp[++i]=++j;
    }
}
int kmp_count(char x[],int m,char y[],int n){
    int i,j;
    kmp_pre(x,m);
    i=j=0;
    while(i<n){
        while(j!=-1&&y[i]!=x[j]) j=kmp[j];
        i++;j++;
        if(j>=m){
            return i-j+1;
        }
    } 	
}

Chapter5.数组和广义表

1.数组-矩阵压缩存储

多个数据的值相同，则只分配一个元素值的存储空间，零元素不占存储空间

1.对称矩阵

压缩在下三角矩阵中

n阶：

共需存储(n^2-n)/2+n=n(n+1)/2个元素（全部元素-对角线）/2再加对角线，我是这样理解

a[k]与原矩阵$a_{ij}$之间对应关系

一个等差数列求和加上另一个下标-1
$$
k=\begin{cases}
\frac {i(i-1)}{2}+j-1, &i>=j \ \
\frac {j(j-1)}{2}+i-1, &i<j
\end{cases}
$$

2.稀疏矩阵

用三元组顺序表存储

原矩阵遍历一遍存进去就行吧

#define MAXN 10000
typedef int Elemtype;
typedef struct {
    int i,j;
    Elemtype e;
}Triple;
typedef struct {
    Triple data[MAXN+1];//使用1...MAXN
    int mu,nu,tu;//行、列、非零元个数（相当于表长），离谱难记
}TSMatrix;

快速转置

空间换时间

num[col]：矩阵M中第col列中非零元的个数

cpot[col]：M中第col列第一个非零元在转置后三元组中的位置

cpot[1]=1;

cpot[col]=cpot[col-1]+num[col-1];

可以递推求出

最坏情况是t=mu*nu 即矩阵中全都是非零元（说好的稀疏矩阵呢） $O(mu*nu)$

int num[MAXN+1],cpot[MAXN+1];
void FastTransposeSMatrix(TSMatrix &M,TSMatrix &T){
    T.mu=M.mu;T.nu=M.nu;T.tu=M.tu;
    for(int i=0;i<M.tu;i++)
        num[M.data[i].j]++;
    cpot[1]=1;
    for(int i=2;i<=M.nu;i++){
        cpot[i]=cpot[i-1]+num[i-1];
    }
    //init
    for(int i=1;i<M.tu;i++){
        int col=M.data[i].j;
        int p=cpot[col]++;//!!!加了之后往后存
        T.data[p].i=M.data[i].j;
        T.data[p].j=M.data[i].i;
        T.data[p].e=M.data[i].e;
    }
}

十字链表

typedef struct OLNode{
    int i,j;
    Elemtype v;
    OLNode *right;
    OLNode *down;
}OLNode,*OLink;
typedef struct {
    OLink *rhead;//行链头指针 rhead[1...n]
    OLink *chead;
    int mu,nu,tu;
}CrossList;

有一个建表的算法，后面补上，其实和链表的操作差不多，不过要行列分别都插入一下

2.广义表

看会别的再写（这一看就是三天）

是线性表的推广（lists）

LS=(a1,a2,…,an)

表头：LS非空时，称第一个元素a1为表头

表尾：其余元素组成的表称为表尾

因此表头可能是原子或列表；但表尾一定是列表

GetHead() & GetTail() 操作取表头和表尾，可以套娃

0.结构体定义

typedef enum{ATOM,LIST}Elemtag;
typedef struct GLNode{
    Elemtag tag;
    union{
        Elemtype atom;
        struct {
            GLNode *hp,*tp;
        }ptr;//headptr tailptr
    };
}*GList;

1.建广义表

没讲过！那便自学！

看了看。。这个算法不太明确，没有给出很多函数的功能。。算了

2.广义表深度

定义为：广义表中括弧的重数

即，atom深度为0，list深度为1

int GListDepth(GList L){
    if(!L) return 1;//空表深度为1，递归最后在这里结束
    if(L->tag==ATOM) return 0;//atom深度为0
    
    GList p=L;
    int ans=0;
    while(p){
        ans=max(ans, GListDepth(p->ptr.hp));//找子表的最大深度
        p=p->ptr.tp;//到下一个表
    }//再次改写了书上的版本
    return ans+1;
}

3.m元多项式

$$
P(x,y,z)=((x^{10}+2x^6)y^3+3x^5y^2)z^2+((x^4+6x^3)y^4+2y)z+15 \ \
广义表表达：\
P=z((A,2),(B,1),(15,0))\
A=y((C,3),(D,2))\
C=x((1,10),(2,6))\
D=x((3,5))\
B=y((E,4),(2,1))\
E=x((1,4),(6,3))
$$

Chapter6.树

概念及性质

子树、孩子、父节点、层次、深度（max层次）

节点的度：节点拥有的子树数

叶子/终端节点：度为0的点

分支节点/非终端节点/内部节点：度不为0的点

树的度：max节点的度

祖先：从根到该节点所经分支上的所有节点

子孙：子树中的任意节点

堂兄弟：同一层的节点

有序树：树中节点的各子树从左至右是有序的

无序树：各子树节点无序，可以互换（似乎有个比较典型的题 3个节点可以组成几种有序树、几种无序树什么的）

森林：m棵互不相交的树的集合

二叉树：每个节点至多有两棵子树的有序树

满二叉树：深度为k且有$2^k-1$个节点的二叉树

完全二叉树：每个节点都与深度为k的满二叉树1-n个节点一一对应时，该树为完全二叉树（最后一层不满的满二叉树）

性质：

1. 第i层至多有$2^{i-1}$节点（归纳法可证）

2. 深度为k的二叉树至多有$2^k-1$个节点（1求和）

3. 对于任意二叉树T，若叶子节点数为$n_0$，度为2的节点数为$n_2$，则$n_0=n_2+1$

   节点总数$v=n_0+n_1+n_2$

   又$e=v-1$，并且在此定义中，$e=n_1+2n_2$（边由n1和n2的节点产生）

   联立得$n_0=n_2+1$

4. 有n个节点的完全二叉树深度为$\lfloor log_2n\rfloor +1$

0.结构体定义（二叉树）

typedef struct BiTNode{
    Elemtype data;
    BiTNode *left,*right;
}BiTNode,*BiTree;

1.建树

void CreateBiTree(BiTree &T){//递归版这么简单的吗
    //先序序列建树，孩子节点为空的地方用_
    char s;
    cin>>s;
    if(s=='_') T=NULL;
    else{
        if(!(T=(BiTree)malloc(sizeof(BiTNode)))) return;
        T->data=s;
        CreateBiTree(T->left);
        CreateBiTree(T->right);
    }
}

2.遍历（递归）

On

void PreOrderTraverse(BiTree T){
    if(T){
        cout<<T->data<<endl;//总之访问即可
        PreOrderTraverse(T->left);
        PreOrderTraverse(T->right);
    }
}
void InOrderTraverse(BiTree T){
    if(T){
        InOrderTraverse(T->left);
        cout<<T->data<<endl;
        InOrderTraverse(T->right);
    }
}
void PostOrderTraverse(BiTree T){
    if(T){
        PostOrderTraverse(T->left);
        PostOrderTraverse(T->right);
        cout<<T->data<<endl;
    }
}

2.遍历（非递归）

void InOrderTraverse_stack(BiTree T) {
    stack<BiTree> S;//建议搓个ctype的栈
    S.push(T);
    while(!S.empty()){
        BiTree p=T;
        while((p=S.top())!=NULL) S.push(p->left);
        S.pop();//栈顶空指针弹出
        if(!S.empty()){
            p=S.top();S.pop();
            cout<<p->data<<endl;
            S.push(p->right);
        }
    }
}

3.求深度

int GetDepth(BiTree T){
    if(!T) return 0;
    else return max(GetDepth(T->left), GetDepth(T->right))+1;
}

4.线索化

typedef enum {Link,Thread}PointerTag;
typedef struct BiThrNode{
    Elemtype data;
    BiThrNode *left,*right;
    PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre;
void InThreading(BiThrTree &p){
    if(p){
        InThreading(p->left);
        if(!p->left) {
            p->LTag=Thread;p->left=pre;
        }
        if(!pre->right){
            pre->RTag=Thread;
            pre->right=p;
        }
        InThreading(p->right);
    }
}
void InOrderThreading(BiThrTree &Thrt,BiThrTree T){
    //Thrt指向头节点T，类似链表的头指针
    if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
    Thrt->LTag=Link;//左边连T
    Thrt->RTag=Thread;//最终是中序遍历的最后一个节点right指向Thrt

    //下面两行迷惑
    Thrt->right=Thrt;//右指针回指 why?
    if(!T) Thrt->left=Thrt;//T为空，左指针回指
    
    else{
        Thrt->left=T;
        pre=Thrt;//指向前一个节点
        InThreading(T);
        
        //最后一个节点线索化（由于pre到不了最后）
        pre->RTag=Thread;
        pre->right=Thrt;
        Thrt->right=pre;
        //最终Thrt的后继是pre？
    }
}

5.森林

1.双亲表示法

连续空间存储树的节点，并附设一个区域存储双亲节点的下标

缺点：求节点的孩子需要遍历整个结构

2.孩子表示法

采用多重链表，每个节点指向多个孩子节点

缺点：求节点的双亲需要遍历整个结构

3.孩子兄弟表示法

两个指针域*firstchild指向第一个孩子节点，*nextsibling指向孩子节点的堂兄弟

4.森林与二叉树的转换

你会做

根节点一定没有右孩子

5.森林遍历

先序：

1. 访问森林中第一棵树的根节点
2. 先序遍历第一棵树中根节点的子树森林
3. 先序遍历除第一棵树之后剩余的树构成的森林

6.Huffman树

路径长度：从一个节点到另一个节点的分支数目

树的路径长度：从树根到每一个节点的路径长度之和

*完全二叉树是这种路径长度最短的二叉树

树的带权路径长度：树中所有叶子节点的带权路径长度之和（节点带权，分支无权值）
$$
WPL=\sum_{k=1}^{n} w_kl_k
$$
最优二叉树/哈夫曼树：WPL最小的树

huffman前缀码：任何一个字符的编码都不能是其他字符编码的前缀

正则二叉树：树中只有度为0和2的节点，没有度为1的节点，一棵有n个叶子节点的二叉树共有2n-1个节点

总之就是非常恐怖

typedef struct {
    int weight;
    int parent,left,right;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef char **HuffmanCode;//这是啥？
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
    //w为n个字符权值的数组，由w构建哈夫曼树HT并将编码结果存入HC
    if(n<=1) return;//一个点没法编
    int m=2*n-1;//正则二叉树的节点总数
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//不使用0号单元，节点序号均为正数
    HuffmanTree p=HT;
    for(int i=1;i<=n;i++,p++,w++) *p={*w,0,0,0};
    for(int i=n+1;i<=m;i++,p++) *p={0,0,0,0};
    for(int i=n+1;i<=m;i++){
        int s1,s2;
        select(HT,i-1,s1,s2);//在HT[1...i-1]选择parent为0且weight最小的两个节点，其序号为s1和s2
        HT[s1].parent=i;HT[s2].parent=i;
        HT[i].left=s1;HT[i].right=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    //输出编码
    //紧张刺激的拼字符串环节。。。。
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//n个字符编码的头指针向量
    char* cd=(char*)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(int i=1;i<=n;i++){
        int start=n-1;
        for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
            if(HT[f].left==c) cd[--start]='0';//从后面往前拼，从叶子到根
            else if(HT[f].right==c) cd[--start]='1';
            else return;
            HC[i]=(char*)malloc((n-start)*sizeof(char));//申请n-start的空间即这个字符串的长度
            strcpy(HC[i],&cd[start]);//strcpy传参为char*
        }
    }
    free(cd);
}

啊书上后面两节在讲什么？

不知道

Chapter7.图

<u,v> 有向图，u到v是一条弧，弧尾/起始点：u，弧头/终端点：v

(u,v) 无向图，u到v是一条边

在简单图中：（没有重边和自环）

无向完全图：有$C_n^2$即$\frac{n(n-1)}{2}$条边的图称为无向完全图

有向完全图：有$2C_n^2$即$n(n-1)$条边的图

稀疏图：边或弧数量少($e<nlogn$)的图

稠密图：边或弧数量多

权：图的边或弧具有与它相关的数

网：带权图通常又称为网

子图：类似子集的概念

邻接：u和v之间有一条边，则u和v邻接

关联：这条边关联u和v

入度、出度

路径：从u到v的一个顶点序列

回路：从u到u的一个顶点序列

简单路径：序列中顶点不重复的路径

连通：从u到v有路径，则称u和v是连通的

连通图：无向图，任意两顶点之间都连通

连通分量：无向图中极大连通子图

强连通图：有向图，从u到v和从v到u都存在路径

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

生成树：连通图的生成树是一个极小连通子图，含图中全部顶点和n-1条边，e=v-1

​ 若边大于v-1，则一定有环；若边小于v-1，则非连通

​ 有v-1条边也不一定是生成树

有向树：有向图恰有一个顶点入度为0（根），其余顶点入度均为1

生成森林：有向图，由若干棵有向树组成，每个顶点属于且仅属于一棵树

0.结构体定义

邻接矩阵

#define INF INT_MAX
#define MAX_VERTEX_NUM 20
typedef int Elemtype;
typedef int Infotype;
typedef struct ArcCell{
    Elemtype adj;//书上是VRType，顶点关系类型；无向图用1或0表示是否相邻，带权图则表示权值（有边为权值，无边为INF）
    Infotype *info;//其他相关信息
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
    Elemtype vexs[MAX_VERTEX_NUM];//顶点向量？什么东西？
    AdjMatrix arcs;//邻接矩阵
    int vexnum,arcnum;//vex顶点数量，arc弧数量
}MGraph;

邻接表

有点熟悉？啊写dijkstra用过

typedef struct ArcNode{
    int adjvex;
    ArcNode *nextarc;
    Infotype *info;
}ArcNode;
typedef struct VNode{
    Elemtype data;//顶点信息
    ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

十字链表

邻接多重表

1.DFS

应该没错吧？

初始点是i（为什么不用Elemtype）

bool vis[MAX_VERTEX_NUM];//记得初始化为false
void DFS(MGraph &G,int i){//邻接矩阵，On2
    vis[i]=true;
    for(int j=0;j<G.vexnum;j++){
        if(!vis[j]&&G.arcs[i][j].adj!=0) DFS(G,j);
    }
}
void DFS(ALGraph &G,int i){//邻接表，On
    vis[i]=true;
    for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc){
        if(!vis[p->adjvex]) DFS(G,p->adjvex);
    }
}

2.BFS

应该也没错吧

void BFS(MGraph &G,int i){
    //加vis数组初始化
    queue<int> que;
    vis[i]=true;
    que.push(i);
    while(!que.empty()){
        int temp=que.front();
        que.pop();
        cout<<temp<<endl;
        for(int j=0;j<G.vexnum;j++){
            if(G.arcs[temp][j].adj!=0&&!vis[j]) {
                que.push(j);        
                vis[j]=true;
            }
        }
    }
}
void BFS(ALGraph &G,int i){
    //加vis数组初始化
    queue<int> que;
    vis[i]=true;
    que.push(i);
    while(!que.empty()){
        int temp=que.front();
        que.pop();
        cout<<temp<<endl;
        for(ArcNode *p=G.vertices[temp].firstarc;p;p=p->nextarc){
            if(!vis[p->adjvex]) {
                que.push(p->adjvex);
                vis[p->adjvex]=true;
            }
        }
    }
}

对非连通图的遍历，多次调用遍历函数，可以得到图的连通分量

通过DFS和BFS能够得到图的生成树，分别就叫深度优先生成树/广度优先生成树

非连通图：深度/广度优先生成森林

3.最小生成树

Prim

On2，与边数无关，适合稠密图

蛮怪的。。书上这个closedge中adjvex邻接的顶点v根本没用到，那定义个这个结构到底是想干啥。。。

int closedge[MAX_VERTEX_NUM];//备选点集合 closedge[u]
void Prim(MGraph &G,Elemtype u){
    int ans=0;
    for(int i=0;i<G.vexnum;i++){//closedge初始化为u的关联边
        if(i!=u) //莫得自环
            closedge[i]=G.arcs[u][i].adj;
    }
    cout<<u<<endl;
    closedge[u]=0;//等于零表示u已经被选中，这样啊
    int temp;int cost=INF;
    for(int i=0;i<G.vexnum-1;i++){//选剩下的vexnum-1个点 On2
        for(int k=0;k<G.vexnum;k++) {//从closedge中选最短边
            if (closedge[k] != 0 && closedge[k] < cost) {
                temp = k;
                cost = closedge[k];
            }
        }
        //temp即选出的下一个点
        cout<<temp<<endl;
        ans+=cost;
        closedge[temp]=0;
        for(int j=0;j<G.vexnum;j++){
            if(closedge[j]>G.arcs[temp][j].adj)
                closedge[j]=G.arcs[temp][j].adj;
        }
        cost=INF;
    }
    cout<<"weight:"<<ans<<endl;
}

Kruskal

老Kruskal大师了Onlogn

这，书上没代码

用书上结构的话得加一个能对边进行排序同时存节点信息的结构体，然后用并查集

struct Kedge{
    int u,v,w;
};
Kedge kE[maxn];//Kruskal edge
//kruskal+并查集
int f[maxn];
void init(){
    for(int i=0;i<maxn;i++) f[i]=i;
}
int find(int x){
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
void merge(int a,int b){
    int temp=find(a);
    f[temp]=find(b);
}
bool check(int a,int b){
    if(find(a)==find(b)) return true;
    else return false;
}
bool comp(Kedge &a,Kedge &b){
    return a.w<b.w;
}
void Kruskal(int n,int v){
    init();//并查集初始化
    int ans=0;
    sort(kE,kE+v,comp);//边权从小到大排序
    for(int i=0;i<v;i++){
        if(!check(kE[i].u,kE[i].v)){//查询uv是否已经加入并查集
            merge(kE[i].u,kE[i].v);//若未加入,则合并uv的集合
            cout<<kE[i].u<<' '<<kE[i].v<<endl;
            ans+=kE[i].w;//ans+边权w
        }
    }
    cout<<ans<<endl;//最后输出图最小生成树的树权
}

4.拓扑排序

有向无环图：字面意思，这个环指不存在回路，图形是环并不一定有环。简称DAG图

AOV(Activity On Vertex Network)网，称为顶点表示活动的网

在AOV网中不应出现有向环，对于程序的数据流图来说，这代表一个死循环

拓扑排序：由一个集合上的偏序得到全序

偏序：关系R满足自反、反对称、传递

全序：偏序关系R对每个x，y属于R，必有xRy或yRx，则R是全序

int indegree[MAX_VERTEX_NUM];
void TopologySort(ALGraph &G){
    for(int i=0;i<MAX_VERTEX_NUM;i++) indegree[i]=0;
    for(int i=0;i<G.vexnum;i++){
        for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc){
            indegree[p->adjvex]++;
        }
    }//初始化indegree入度数组
    stack<int> st;//存零入度的顶点
    for(int i=0;i<G.vexnum;i++){
        if(!indegree[i]) st.push(i);
    }
    int cnt=0;
    while(!st.empty()){
        int temp=st.top();
        st.pop();
        cnt++;
        cout<<temp<<endl;
        for(ArcNode *p=G.vertices[temp].firstarc;p;p=p->nextarc){
            indegree[p->adjvex]--;
            if(!indegree[p->adjvex]) st.push(p->adjvex);
        }
    }
    if(cnt<G.vexnum) return;//不够，不是有向无环图
}

5.关键路径

AOE(Activity On Edge)网，即用边表示活动的网，顶点表示事件，弧表示活动，弧的权表示活动的持续时间

入度为0的点（开始点）称为源点，出度为0的点称为汇点

路径长度（权值之和）最长的路径称为关键路径

e(i)–活动ai（是某一条弧）最早开始时间

l(i)–活动ai最迟必须开始的时间（不推迟整个工程完成的前提下）

l(i)-e(i)–完成活动ai的时间余量

l(i)=e(i)–这样的活动称为关键活动， 即找一条全部由关键活动构成的路径

首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)

ve(j)：j前所有活动都已完成，事件j才能发生，因此是最大值

vl(j)：从后面倒着往前求，取最小值，否则会使工程完成时间延后

。。。我受到了欺骗，书上没有算法，焯

下学期补了一个，但是原题只需要拓扑输出最后一个点的权值就可以，所以拓扑的函数改成输出拓扑排序路径到tpo1和tpo2（逆拓扑排序）就可

#include<bits/stdc++.h>
using namespace std;

const int maxn=107;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
    int to,w;
    node(int to,int w):to(to),w(w){};
};
vector<node> fro[maxn],to[maxn];
int in[maxn];
bool vis[maxn];
queue<int>que;
vector<int>tpo1,tpo2;
int ve[maxn],vl[maxn];
void init(){
    memset(ve,0,sizeof(ve));
    memset(vl,inf,sizeof(vl));
}
void tpo(){
    int cnt=0,ans=0;
    init();
    for(int i=0;i<n;i++){
        if(!in[i]){
            que.push(i);
            vis[i]=true;
            cnt++;
        }
    }
    while(!que.empty()){
        int temp=que.front();
        que.pop();
        tpo1.push_back(temp);
        for(int i=0;i<fro[temp].size();i++){
            int t=fro[temp][i].to;
            ve[t]=max(ve[t],ve[temp]+fro[temp][i].w);
            ans=(ans,ve[t]);
            in[t]--;
            if(in[t]==0&&!vis[t]){
                que.push(t);
                vis[t]=true;
                cnt++;
            }
        }
    }
    if(cnt!=n){
        cout<<"Impossible";
    }
    else cout<<ans;
}


void critical_path(){
    init();
    int ans=0;
    for(int i=0;i<tpo1.size();i++){
        int temp=tpo1[i];
        for(int j=0;j<fro[temp].size();j++){
            if(ve[fro[temp][j].to]<ve[temp]+fro[temp][j].w){
                ve[fro[temp][j].to]=ve[temp]+fro[temp][j].w;
            }
        }
    }
    for(int i=0;i<n;i++){
        vl[i]=ve[i];
    }
    for(int i=0;i<tpo2.size();i++){
        int temp=tpo2[i];
        for(int j=0;j<to[temp].size();j++){
            if(vl[temp]-to[temp][j].w<vl[to[temp][j].to]){
                vl[to[temp][j].to]=vl[temp]-to[temp][j].w;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<fro[i].size();j++){
            int e=ve[i];
            int l=vl[fro[i][j].to]-fro[i][j].w;
            if(e==l){
                cout<<i<<' '<<fro[i][j].to<<' '<<fro[i][j].w<<endl;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        fro[x].emplace_back(y,z);
        to[y].emplace_back(x,z);
        in[y]++;
    }
    tpo();
    critical_path();
}

6.Dijkstra

画一个图理解循环：从a开始找到c的最短路

a—2—b—3—c

a—8—c

dis[a]=0,dis[b]=2,dis[c]=8（存a到a，a到b…）

选中b后

if(dis[c]>dis[b]+weight(b->c))

用链表做了个能On遍历选最小边的，可以用后边小根堆优化亿下

1.邻接表版

int vis[maxn];
int dis[maxn];
const int inf=0x3f3f3f3f;
typedef struct List{
    int v;
    InfoType w;
    List *next;
}*LinkList;
LinkList newNode(int v,int w){
    LinkList p=(LinkList)malloc(sizeof(List));
    p->v=v;
    p->w=w;
    p->next= nullptr;
    return p;
}
void init(ALGraph &G){
    for(int i=0;i<=G.vexnum;i++) {
        vis[i]=0;
        dis[i]=inf;
    }
}
void Dijkstra(ALGraph &G,int s){
    init(G);
    dis[s]=0;
    LinkList L=(LinkList)malloc(sizeof(List));
    LinkList newp= newNode(s,0);
    L->next=newp;
    while(L->next){
        LinkList m;
        m=L->next;
        for(LinkList p=L->next;p;p=p->next){
            m=p->w<m->w?p:m;
        }
        LinkList pre=L;
        for(;pre->next!=m;pre=pre->next);
        pre->next=pre->next->next;

        if(vis[m->v]) continue;
        vis[m->v]=1;
        for(ArcNode *p=G.vertics[m->v].firstarc;p;p=p->nextarc){
            int cost=p->info[0];
            if(!vis[p->adjvex]&&dis[p->adjvex]>dis[m->v]+cost) {
                dis[p->adjvex] = dis[m->v] + cost;
                LinkList newq= newNode(p->adjvex,dis[p->adjvex]);
                newq->next=L->next;
                L->next=newq;
            }
        }
    }
}

2.邻接矩阵版

来写写算法嘛！

7.Floyd

void Floyd(MGraph &G,AdjMatrix &D){
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            D[i][j]=G.arcs[i][j];//赋一下值
        }
    }
    //G为带权图，D为求得的最短路
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            for(int k=0;k<G.vexnum;k++){
                if(D[j][k].adj<D[j][i].adj+D[i][k].adj)
                    D[j][k].adj=D[j][i].adj+D[i][k].adj;

            }
        }
    }
}

Chapter9.查找

静态查找表：查询某个元素是否在表中、查找这个元素的各种属性

动态查找表：查找过程中同时插入查找表中不存在的数据元素、或删除某个已存在的元素

平均查找长度ASL

Average Search Length
$$
ASL=\sum_{i=1}^{n}P_iC_i
$$
Pi：查找表中第i条记录的概率（一般都是等概率查找）$\sum_{i=1}^{n}P_i=1$

Ci：找到符合条件的元素所需比较次数

又分为查找成功时的ASL和不成功的ASL

0.结构体定义

和排序一样（为什么不是排序和查找一样呢）

typedef int Keytype;
typedef int Infotype;
typedef struct Redtype{
    Keytype key;
    Infotype info;
}Redtype;
typedef struct SqList{
    Redtype r[maxn];
    int length;
}SqList;

1.顺序查找

注意哨兵的使用

找到第i个记录的比较次数为$n-i+1$

（比如找第1个，要比较n个；找第二个，比较n-1个，即n-i+1）

int SeqSearch(SqList &L,Keytype key){
    L.r[0].key=key;//0号单元中不存元素，作为哨兵
    int i;
    for(i=L.length;i>=0&&L.r[i].key!=key;i--);
    return i;
}

$$
ASL=\frac{1}{n} \cdot \frac{(1+n)n}{2}
=\frac{n+1}{2}
$$

2.二分查找/折半查找

在已经排序的表中使用（配合第十章的排序算法）

int BinSearch(SqList &L,Keytype key){
    int l=1,r=L.length;
    while(l<=r){
        int mid=(l+r)/2;
        if(L.r[mid].key==key) return mid;
        else if(L.r[mid].key>key) r=mid-1;
        else if(L.r[mid].key<key) l=mid+1;
    }
    return 0;//不存在要查找的key
}

看作二叉树（并且类似完全二叉树，但不一定是）

有n个元素则深度为$\lfloor log_2n\rfloor +1$

课本的描述感觉也不是很好啊。。我只知道是log阶

$h=log_2(n+1)$的满二叉树中：
$$
ASL=\frac{1}{n} \sum_{j=1}^{h}j \cdot 2^{j-1}
=\frac{n+1}{n}log_2(n+1)-1\
n较大时(n>50)，ASL=log_2(n+1)-1
$$

3.二叉排序树

动态查找表

递归定义：

1. 若左子树不空，则左子树所有节点的值均小于它的根节点的值；
2. 若右子树不空，则右子树所有节点的值均大于它的根节点的值；
3. 它的左右子树也分别为二叉排序树

中序遍历二叉排序树，可以得到一个关键字的有序序列。也就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造过程即一个排序过程

看到ppt上比课本优秀一百倍的代码然后改了

typedef int Elemtype;
typedef struct BiTNode{
    Elemtype data;
    BiTNode *left,*right;
}BiTNode,*BiTree;
BiTree BST(BiTree &T,Elemtype key){
    BiTree pre,p=T;
    while(p&&p->data!=key){
        pre=p;
        p->data>key?p=p->left:p=p->right;
    }
    if(p) return p;
    else{
        BiTree s=(BiTree)malloc(sizeof(BiTNode));
        s->data=key;
        s->left=NULL;
        s->right=NULL;
        pre->data>key?pre->left=s:pre->right=s;
        return s;
    }
}

$$
ASL_{min}=\lfloor log_2n\rfloor +1(完全二叉树深度)\
ASL_{max}=(n+1)/2(顺序表，树只有左/右子树)
$$

但一般来说计算具体二叉树深度，根据具体情况分析，$\sum$节点所在层/总节点数

没说删除，好耶

4.平衡二叉树

AVL树

性质：（AVL是空树或满足如下性质）

1. 左右子树深度之差（一般是用左深度-右深度）的绝对值≤1
2. 左右子树是平衡二叉树

来写写算法嘛！

好的，圣女大人！下次一定

不过后面这几个都没要求算法实现？

5.B-树B+树

m叉B-树性质：（B-树是空树或满足如下性质）

1. 树中每个节点至多有m棵子树（废话，要不然为啥叫m叉）

2. 若根节点不是叶子节点，则至少有两棵子树

3. 除根之外的分支点至少有$\lceil m/2\rceil$棵子树

4. 所有非终端节点中包含一个数据序列(n,A0,K1,A1,K2,A2,…,Kn,An)

   n为关键字K的个数

   K为关键字，满足升序排列

   A为指向子树根节点的指针，且Ai-1指向子树中所有节点的关键字均小于Ki，An指向子树中所有节点关键字均大于Kn（看那个序列的顺序可知）

5. 所有叶子节点均在同一层次

ppt上多做几遍

m叉B+树性质：（仅与B-树有差异的部分）

1. 有n棵子树的节点中含n个关键字
2. 所有叶子节点包含全部关键字信息，以及指向该关键字的指针；且叶子节点本身按关键字大小升序连接
3. 所有非终端节点看成是索引，节点中仅含子树中最大/最小的关键字（如果最大则统一最大）

6.hash表

建立关键字与存储位置的对应关系，由关键字决定数据的存储地址

散列函数H(key)

经典例题：给hash函数和数列和表长，计算成功和不成功的ASL

构造方法

1.直接定址法

$$
H(key)=key或akey+b
$$

2.数字分析法

听着很高端啊，举个例子 202000130088把后面三位掰下来做地址

3.平方取中法

$$
H(key)=key^2
$$

取其中几位做地址

4.折叠法

把key按位拆成数字加起来求一个地址

5.除留余数法

$$
H(key)=key \space mod \space p
$$

p选质数或不包含小于20的质因数的合数

6.随机数法

又要抽卡了吗？

冲突处理

1.开放定址法

寻找下一个空的哈希地址，并将数据存入

1.线性探测法

while(hash地址不为空){

​ hash+=d;}

d为增量

优点：只要hash表不满，一定能找到空地址单元存储有冲突的元素

缺点：容易产生二次聚集（一大堆堆在那，关键字频繁重复的地方一大堆，别的地方空）

2.二次探测法

while(hash地址不为空){

​ hash+=d或hash-=d}

3.伪随机探测法

继续抽卡，上头

d为随机数

2.链地址法

将具有相同地址的记录用单链表连接，m个hash地址则设m个单链表，形成动态的结构

3.再哈希法

再使用不同的hash函数RH(key)

优点：不易产生聚集

缺点：增加计算时间

4.公共溢出区

另设一个溢出表，发生冲突时把元素存入溢出表中

Chapter10. 排序 Sort

0.结构体定义

typedef int Keytype;
typedef int Infotype;
typedef struct Redtype{
    Keytype key;
    Infotype info;
}Redtype;
typedef struct SqList{
    Redtype r[maxn];
    int length;
}SqList;

1.直接插入排序

$time:O(n^2)\space space:O(1)$ 稳定的(指key值相同元素保持初始相对顺序不变)

void InsertSort(SqList &L){
    for(int i=2;i<=L.length;i++){
        L.r[0]=L.r[i];//哨兵，将i中元素暂时存储的单元，必须使用，否则在下一层for循环中i中元素被前一个覆盖
        if(L.r[i].key < L.r[i - 1].key){//其实不写也完全等价
            int j;
            for(j=i-1; L.r[j].key > L.r[0].key; L.r[j + 1]=L.r[j],j--);
            L.r[j + 1]=L.r[0];
        }
    }
}

1.1 折半查找直接插入排序

仅优化查找比j小的元素的位置，但是时间复杂度依旧On2 挺憨的，故不算做一个算法

void BInsertSort(SqList &L) {
    for (int i = 2; i <= L.length; i++) {
        L.r[0] = L.r[i];
        if (L.r[i].key < L.r[i - 1].key) {
            int low = 1, high = i - 1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (L.r[mid].key == L.r[0].key) break;
                if (L.r[mid].key > L.r[0].key) high = mid - 1;
                else if (L.r[mid].key < L.r[0].key) low = mid + 1;
            }
            for (int j = i - 1; j > (low + high) / 2; j--) L.r[j + 1] = L.r[j];
            L.r[1 + (low + high) / 2] = L.r[0];
        }
    }
}

1.2 2-路插入排序

将第一个元素作为mid，比mid小的插在mid前面的表中，比它大的放到后面，同样On2 憨憨 不写了

1.3 表插入排序

这是个什么东西？没仔细研究…

2.希尔排序（Shell’s Sort）

不要见啥都喊女儿啊拜托

又称缩小增量排序，由于直接插入排序在元素基本有序时速度接近On；在length较小时排序效率高而进行改进

约$time:O(n^{1.5})\space space:O(1)$ 不稳定

void ShellInsert(SqList &L,int dk){//dk为增量
    for(int i=1+dk;i<=L.length;i++){
        if(L.r[i].key<L.r[i-dk].key){
            L.r[0]=L.r[i];
            int j;
            for(j=i-dk;j>0&&L.r[j].key>L.r[0].key;L.r[j+dk]=L.r[j],j-=dk);
            L.r[j+dk]=L.r[0];//注意这里是j+dk，循环到这里的j<=0
        }
    }
}
void ShellSort(SqList &L,int dlta[],int t){
    //dlta为给定增量序列，例如｛5,3,1}（隔5个元素之间有序、隔3个、最终都有序）
    //t为增量序列的长度
    for(int i=0;i<t;i++){
        ShellInsert(L,dlta[i]);
    }
}

3.冒泡排序

每次两个元素相比较，若前面的更大，则两者交换，执行一次，一个最大的元素冒出来

$time:O(n^2)\space space:O(1)$ 稳定

void BubbleSort(SqList &L){
    for(int h=1;h<=L.length;h++) {
        bool fl=true;
        for (int i = 2; i <= L.length-h+1; i++) {
            if (L.r[i - 1].key > L.r[i].key){
                swap(L, i - 1, i);
                fl=false;
            }
        }
        if(fl) break;
    }
}

4.快速排序

大一没学好的东西，现在看来还挺简单的

$time:O(nlogn)\space space:O(logn)$（主要是栈空间） 不稳定

在表基本有序时退化为On2的冒泡排序

int Partition(SqList &L,int low,int high){
    L.r[0]=L.r[low];//枢轴
    Keytype pivot=L.r[0].key;
    while(low<high){
        while(low<high&&L.r[high].key>=pivot) high--;
        L.r[low]=L.r[high];
        while(low<high&&L.r[low].key<=pivot) low++;
        L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0];
    return low;
}
void QuickSort(SqList &L,int low,int high){
    if(low<high){
        int pivoc= Partition(L,low,high);
        QuickSort(L,low,pivoc-1);
        QuickSort(L,pivoc+1,high);
    }
}

5.选择排序

每次选取关键字最小的记录加入已经有序的序列最后

$time:O(n^2)\space space:O(1)$ 稳定

void SelectSort(SqList &L) {
    for (int i = 1; i <= L.length; i++) {
        L.r[0] = L.r[i];
        int temp = 0;//记录目前最小元素位置
        for (int j = i + 1; j <= L.length; j++) {
            if (L.r[0].key > L.r[j].key) {
                temp = j;
                L.r[0] = L.r[j];
            }
        }
        swap(L, temp, i);
    }
}

6.堆排序

父节点都比孩子节点小-小根堆，都比孩子节点大-大根堆

$time:O(nlogn) \space space:O(1)$ 不稳定

void HeapAdjust(SqList &H,int s,int m){//大根堆
    //已知H.r[s...m]中除s以外均满足大根堆定义，调整s使H.r[s...m]成为一个大根堆
    H.r[0]=H.r[s];
    while(2*s<=m){
        int j=2*s;//筛选s的两个孩子节点
        if(j<m&&H.r[j].key<H.r[j+1].key) j=j+1;
        if(H.r[0].key>H.r[j].key) break;//s的key值比两个孩子都大，不需要筛选
        H.r[s]=H.r[j];s=j;//再while时继续筛选原来j的两个孩子
    }
    H.r[s]=H.r[0];//现在的s是某个被移动过的节点，并且应该将原来的节点填在这里，不太好理解
}
void HeapSort(SqList &H){
    for(int i=H.length/2;i>0;i--){//建成大根堆
        HeapAdjust(H,i,H.length);
    }
    for(int i=H.length;i>0;i--){//按顺序输出的过程
        cout<<H.r[1].key<<' ';//输出根节点（必为最大元素）
        swap(H,1,i);//根节点放在最后一个位置并且不再参与排序；最后一个节点成为根节点
        HeapAdjust(H,1,i-1);//此时除根节点以外其他节点仍为大根堆结构，对根节点进行筛选
    }
    cout<<endl;
}

7.归并排序

题外话，我输得很彻底

$time:O(nlogn) \space space:O(nlogn)$ 稳定

“值得提醒的是，归并排序的递归算法在形式上较简洁，但实用性很差”

void Merge(SqList &SR,SqList &TR,int l,int m,int r){
    //将有序的SR.r[l...m] SR.r[m+1...r]归并为TR.r[l...r]
    int i=l,j=m+1,k=l;
    while(i<=m&&j<=r){//啊啊啊这落等号
        if(SR.r[i].key<SR.r[j].key) TR.r[k++]=SR.r[i++];
        else TR.r[k++]=SR.r[j++];
    }
    while(i<=m) TR.r[k++]=SR.r[i++];
    while(j<=r) TR.r[k++]=SR.r[j++];
}
void MergeSort(SqList &SR,SqList &TR1,int s,int t){
    if(s==t) TR1.r[s]=SR.r[s];//表中只有一个元素，直接赋值，不递归
    else{
        int m=(s+t)/2;//二分，二路归并
        SqList TR2;
        MergeSort(SR,TR2,s,m);//SR左边排成有序
        MergeSort(SR,TR2,m+1,t);//SR右边排成有序
        Merge(TR2,TR1,s,m,t);//TR2两边归并到TR1
    }
}

8.基数排序

d元组，元组中每个分量有radix种取值

例如：114514是6元组，每个分量有10种取值（0-9）

最高位优先/最低位优先

第i(i=1~d)趟分配，让第i位关键字为k的元组进入下标为k的链队中，然后按照关键字的顺序对链队进行收集，进入下一趟分配

$time:O(d(n+radix))$ n是待排序元素数量

$space:O(n+2radix)$ 附加链队指针数占据额外的存储空间

稳定

算法回头有时间写