绪论

概念

数据：所有能输入到计算机中并被计算机程序加工、处理的符号的总称。如：整数、实数、字符、声音、图象、图形等。

数据项：数据的不可分割的最小单位

数据元素：数据的基本单位，一个数据元素可以由若干个数据项组成

数据对象：性质相同的数据元素的集合，是数据的一个子集

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

结构：数据元素之间的关系称为结构。

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

原子类型(如：int,char,float等)
结构类型(如：数组,结构,联合体等）

抽象数据类型

抽象数据类型（ADT）：与计算机的实现无关的数据类型

形式定义：

ADT 抽象数据类型名 {

数据对象
数据关系:一个或多个关系
基本操作：一组基本操作/运算

} ADT 抽象数据类型名

其中数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：

基本操作名（参数表）

初始条件：<初始条件描述>

操作结果：<操作结果描述>

参数表中有两种操作：

赋值参数：只为操作提供输入值
引用参数：以&打头，除可提供输入值外，还将返回操作结果

算法与算法分析

算法的特征：

有穷性
确定性
可行性
输入：有0或多个输入量
输出：至少有一个输出量

算法设计要求：

正确性
可读性
健壮性
高效与低存储量

时间复杂度比较

线性表

ADT

ADT List

{

数据对象：\(D=\left\{a_i|a_i∈ElemSet,i=1,2,...n,n>=0\right\}\)

数据关系：\(R1=\left\{<a_{i-1},a_i>| a_{i-1},a_i∈D,i=2,...n\right\}\)

基本操作：

1.InitList(&L) //构造空表L。
2.DestroyList(&L) //销毁线性表L
3.ClearList(&L) //置L为空表
4.ListEmpty(L) //判断L是否为空表
5.ListLength(L) //求表L的长度
6.GetElem(L,i,&e) //取元素ai,由e返回ai
7.LocateElem(L,e,compare()) //查找符合条件的元素
8.ListInsert(&L,i,e) //元素ai之前插入新元素e
9.ListDelete(&L,i,&e) //删除第i个元素

}ADT List

顺序存储结构

#define ADD 10
#define LIST_INIT_SIZE 100
typedef struct
{
    ElemType *elem;//存储空间基址
    int length;//当前长度
    int listsize;//当前分配的存储容量
}Sqlist

插入操作

伪码：

//在顺序表L中的第i个位置之前插入新的元素e
Status ListInsert_Sq(SqList &L,int i, ElemType e)
{
    if(i < 1 || i > L.length + 1) return ERROR;//i不合法
    if(L.length > L.listsize)//当前存储空间已满，增加存储空间
    {
        newbase = (ElemType*)realloc(L.elem,(L.listsize + ADD)*sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);//如果分配失败
        L.elem = newbase;
        L.listsize += ADD;
    }
    q = &(l.elem[i - 1]);//q是待插入的位置
    for(p = &(L.elem[L.length - 1]); p >= q; p--)
    	*(p + 1) = *p;
    *q = e;
    ++L.length;
    return OK;
}

分析：

设共有n个元素，在各个位置插入元素的概率相同，为\(p=\frac{1}{n + 1}\)，则插入一个元素时移动的平均值为\(\sum\limits_{i=1}^{n+1}p(n-i+1)=\frac{n}{2}\)

删除操作

伪码：

//在顺序表L中删除第i个元素，并用e返回其值
Status ListDelte_Sq(Sqlist& L, int i, ElemType & e)
{
    if(i < 1 || i > L.length) return ERROR;//如果i不合法
    p = &(L.elem[i - 1]);
    e = *p;
    q = L.elem + L.length - 1;
    for(++p; p <= q; ++p)
        *(p - 1) = *p;
    --L.length;
    return OK;
}

分析：

设共有n个元素，在各个地方删除元素的概率为\(p=\frac{1}{n}\)，则删除一个元素时移动元素的平均值为\(\sum\limits_{i=1}^{n}p(n-i) = \frac{n-1}{2}\)

合并操作

伪码：

//将线性表Lb中的且不再La中的元素合并到La中
void union(Sqlist& La, Sqlist& Lb)
{
    La_len = La.length; Lb_len = Lb.Length;
    for(int i = 1; i <= Lb_len; i++)
    {
        GetElem(Lb, i, e);//从Lb中取第i个元素赋值给e
        if(!LocateElem(La, e, equal))
        	ListInsert(La, ++La_len, e);
    }
}

合并并排序操作

伪码：

//归并非递减排序线性表La和Lb，得到Lc并且Lc按非递减排序
void MergeList(Sqlist La, Sqlist Lb, Sqlist& Lc)
{
	i = j = k = 0;
    La_len = La.length; Lb_len = Lb.Length;
    while(i <= La_len && j <= Lb_len)
    {
        Getelem(La, i, ai); Getelem(Lb, j, bj);
        if(ai <= bj) 
        {
			ListInsert(Lc, ++k, ai);
            i++;
        }
        else
        {
            ListInsert(Lc, ++k, bj);
            j++;
        }
        while(i <= La_len)
        {
            GetElem(La, i++, ai);
            ListInsert(Lc, ++k, ai);
        }
        while(j <= Lb_len)
        {
            GetElem(Lb, j++, bj);
            ListInsert(Lc, ++k, bj);
        }
    }
}

顺序结构存储的评价

优点
1. 是一种随机存取结构，存取任何元素的时间是一个常数，速度快
2. 结构简单，逻辑上相邻的元素，物理上也是相邻的
3. 不使用指针，节省存储空间
缺点
1. 插入和删除需要移动大量数据，消耗大量时间
2. 需要一块连续的空间
3. 插入元素时可能会“溢出”
4. 自由区中的存储空间不能被其他数据占用（共享）

链式存储结构

typedef struct node
{
    ElemType data;
    struct node* next;
}node, *Linklist;

建立单链表

伪码：

//“先进先出”（尾插）
struct node* create1()
{
    struct node* head, tail, p;
    int e;
    head = (struct node*)malloc(sizeof(LENG));
    tail = head;
    scanf("%d", &e);
    while(e != 0)
    {
        p = (struct node*)malloc(sizeof(LENG));
        p->data = e;
        tail->next = p;
        tail = p;
        scanf("%d", &e);
    }
    tail->next = NULL;
    return head;
}
//“后进先出"（头插）
struct node* create2
{
    struct node* head, p;
    int e;
    head = (struct node*)malloc(sizeof(LENG));
    head->next = NULL;
    scanf("%d", &e);
    while(e != 0)
    {
        p = (struct node*)malloc(sizeof(LENG));
        p->data = e;
        p->next = head->next;
        head->next = p;
        scanf("%d", &e);
    }
    return head;
}

建立递增有序链表

伪码：

//不带头结点
struct node* create3(struct node* head, ElemType e)
{
    q = NULL, p = head;//扫描，找到插入位置
    while(p && e > p->data)
    {
        q = p;
        p = p->next;
    }
    s = (struct node*)malloc(sizeof(node));
    s->data = e;
    if(p == NULL)
    {
        if(q == NULL)//空表
            head = s;
        else//尾插
            q->next = s;
    }
    else if(q == NULL)//头插
    {
        s->next = p;
        head = s;
    }
    else//其他正常情况的插入
    {
        s->next = p;
        q->next = s;
    }
    return head;
}
//带头节点
void create4(struct node* head, ElemType e)
{
    q = head;
    p = head->next;
    while(p && e > p->data)
    {
        q = p;
        p = p->next;
    }
    s = (struct node*)malloc(sizeof(node));
    s->data = e;
    //可以直接插入，不讨论
    q->next = s;
    s->next = p;
}

插入操作

伪码：

//在i之前插入
Status ListInsert_L(Linklist& L, int i, ElemType e)
{
    p = L;
    j = 0;
    while(p && j < i)//找到第i-1个结点
    {
        p = p->next;
        j++;
    }
    if(!p || j > i) return ERROR;
    s = (Linklist)malloc(sizeof(node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
//在i之后插入
Status ListInsert_L(Linklist& L, int i, ElemType e)
{
    p = L;
    j = 0;
    while(p && j < i)//找到第i个结点
    {
        p = p->next;
        j++;
    }
    if(!p || j > i) return ERROR;
    s = (Linklist)malloc(sizeof(node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

删除操作

//在带表头节点的链表中删除值为e的元素
Status ListDelete1(stuct node* head, ElemType e)
{
    struct node* p, *q;
    q = head;
    p = head->next;
    while(p && p->data != e)
    {
        q = p;
        p = p->next;
    }
    if(p)
    {
        q->next = p->next;
        free(p);
        return YES;
    }
    else
        return NO;
}
//在单链表中删除指定位置的元素
Status ListDelete2(struct node* head, int i, ElemType& e)
{
    p = head;
    j = 1;
    while(p->next && j < i)
    {
        p = p->next;
        j++;
    }
    if(i <1 || p->next == NULL) return ERROR;
    q = p->next;//q是待删除结点
    p->next = q->next;
    free(q);
    return YES;
}

合并操作

//合并两个带头节点的链表
struct node* Merge(struct node* La, struct node* Lb)
{
    struct node* pa, pb, pc;
    pa = La->next, pb = Lb->next;
    pc = La;
    free(Lb);//释放Lb的头指针
    while(pa && pb)
    {
        if(pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    if(pa) pc->next = pa;
    else  pc->next = pb; 
    return La;
}

链式存储结构评价

优点：灵活地增加/插入，删除操作
缺点：使用显式顺序指针代替隐式的相邻存储的位置关系，增加了存储空间

循环链表

一般形式
1. 带头结点的非空循环单链表，有：
  
  head->next != head, head != NULL
1. 带表头结点的空循环单链表，有：
  
  head->next == head, head != NULL
只有尾节点（带头）
1. 非空表，有：
  
  tail->data ==an
  
  tail->next指向表头结点
  
  tail->next->next指向首节点
  
  tail->next->next->data == a1
1. 空表，有：
  
  tail->next == tail

两循环链表首尾相连(时间复杂度O(1))

p2 = tail2->next

tail2->next = tail1->next

tail1->next = p2->next

free(p2)

双向链表

非空表

L为头指针，L指向表头结点，L->next指向首节点L->next->data == a1

L->prior指向尾节点，L->prior->data == an

L->next->prior == L->prior->next == NULL
空表

L->next == L->prior == NULL

双向循环链表

非空表

L为头指针，L指向表头结点，L->next指向首节点L->next->data == a1

L->prior指向尾节点，L->prior->data == an

L->next->prior == L->prior->next == L
空表

L->next == L->prior == L

各链表比较

栈

栈：限定在表尾做插入、删除的线性表 ---“后进先出”

ADT

ADT Stack

{

数据对象：\(D=\left\{a_i|a_i∈ElemSet,i=1,2,...n,n\geq 0\right\}\)

数据关系：\(R1=\left\{<a_{i-1},a_i>| a_{i-1},a_i∈D,i=2,...n\right\}\)，约定\(a_n\)端为栈顶端，\(a_1\)端为栈底

基本操作：

1.InitStack(&S) //构造一个空栈。 
2.ClearStack(&S) //置s为空栈。
3.DestroyStack(&S) //栈s被销毁
4.Push(&S,e) //元素e进栈S。
5.Pop(&S,&e) //删除栈S的顶元素，并送入e 。
6.GetTop(S,&e) //将非空栈S的栈顶元素拷贝到e（与（4）的Pop操作是不同的）。
7.StackEmpty(&S) //判断s是否为空栈。若s为空栈,则返回值为true；否则为false。
8.StackLength(S) //栈S的长度

}ADT Stack

栈的输出特点

一般地，输入序列\((...,a_i,...,a_j,...,a_k)\)到栈中，不能得到\((...,a_k,...,a_i,...,a_j)\)

栈的存储结构

栈的范围为s[0...maxlen- 1]

顶指针指向栈顶元素所在的位置

栈顶元素：s[top]

进栈：先对top + 1，再将新数据指向top

出栈：先取栈顶元素，再对top - 1

空栈：top == -1

非空栈：top >= 0

满栈：top == maxlen - 1
顶指针指向顶元素上的一空位置

栈顶元素：s[top - 1]

进栈：先将新数据指向top，再对top + 1

出栈：先对top - 1，再取栈顶元素

空栈：top == 0

非空栈：top >= 0

满栈：top == maxlen

\(\color{red}{顺序栈规定top指向栈元素上一空位置}\)

顺序栈

存储表示：

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

初始化栈：

Status InitStack(SqStack &S)
{
    S.base =(SElemType*)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    if(S.base) exit(OVERFLOW);//内存分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

进栈：

Status Push(SqStack &S, SElemType e)
{
    //如果内存不够
    if(S.top - S.base >= S.stacksize) 
    {
        S.base = (SElemType*)realloc(S.base,(S.stacksize + STACK_INIT_SIZE)*sizeof(SElemType));
        if(!S.base) exit(OVERFLOW);//如果分配失败
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINITSIZE;
    }
    *(S.top++) = e;
    return OK;
}

出栈：

Status Pop(SqStack &S, SElemType &e)
{
    if(S.top == S.base) return ERROR;//如果栈为空
    e = *--S.top;
    return OK;
}

链式栈

让top指向an，进栈将新节点作为首节点，出栈删除首节点，保证进出栈时间为常数

栈的应用

数制转换

伪码：

void conversion()
{
    InitStack(S);
    scanf("%d",N);
    while(N)
    {
        Push(S, N % 8);
        N /= 8;
    }
    while(!StackEmpty(S))
    {
        Pop(S, e);
        printf("%d",e);
    }
}

括号匹配

表达式求值

伪码：

OperandType EvaluateExpression()
{
    InitStack(OPTR); Push(OPTR, '#');//初始化操作符的栈
    InitStack(OPND); c = getchar();//初始化操作数的栈
    while(c != '#' || GetTop(OPTR) != '#')
    {
        if(!In(c, OP))//如果不是运算符就进栈
        {
            Push(OPND, c);
            c = getchar();
        }
        else
        {
            switch(Precede(GetTop(OPTR), c))/*判断优先级*/
             	/*栈顶优先级低*/
                case'<':
            		Push(OPRT, c);
            		c = getchar();
            		break;
            	/*脱括号并接收下一个字符*/
            	case'=':
            		Pop(OPRT, x);
            		c = getchar();
            		break;
               /*退栈并将运算符结果入栈*/
            	case'>':
            		Pop(OPRT, theta);
            		Pop(OPND, b);
            		Pop(OPND, a);
            		Push(OPND, Operate(a, theta, b));
            		break;
        }
    }
    return GetTop(OPND);
}

队列

队列：只允许在表的一端插入一端删除的数据结构 ---“先进先出”

ADT

ADT Queue

{

数据对象：\(D=\left\{a_i|a_i∈ElemSet,i=1,2,...n,n\geq 0\right\}\)

数据关系：\(R1=\left\{<a_{i-1},a_i>| a_{i-1},a_i∈D,i=2,...n\right\}\)，约定\(a_n\)端为队列尾，\(a_1\)端为队列头

基本操作：

1.InitQueue(&Q) //初始化,构造空队列。
2.DestroyQueue(&Q) //销毁Q队列。
3.ClearQueue(&Q) //置Q为空队列。
4.QueueEmpty(Q) //判断Q是否为空队列。
5.EnQueue(&Q,e) //将e插入队列Q的尾端。
6.DeQueue(&Q,&e) //取走队列Q的首元素,送e。
7.GetHead(Q,&e) //读取队列Q的首元素,送e。
8.QueueLengrh(Q) //返回队列长度

}ADT Queue

链式队列

用带头节点的单链表表示队列

存储表示：

typedef struct QNode
{
    QElemType data;
    struct QNode* next;
}QNode, *QueuePtr;
typedef struct
{
    QueuePtr front;//队头指针
    QueuePtr rear;//队尾指针
}LinkQueue;

初始化队列：

Status InitQueue(LinkQueue& Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

插入元素：

Status EnQueue(LinkQueue& Q, QElemType e)
{
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

删除元素：

Status DeQueue(LinkQueue& Q, QElemType& e)
{
    if(Q.front == Q.rear) return ERROR;
    p = Q.front->next;//头插
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;//如果是只有一个节点的情况
    free(p);
    return OK;
}

循环队列

参考此篇blog

分辨队满&队空

rear指向的为空，留一个空位置
1. 队空：q.rear == q.front
2. 队满：q.rear + 1 == q.front
设置flag标志
1. 入队时如果q.rear == q.front，则队满，设置flag为true
2. 出队时如果q.rear == q.front，则队空，设置flag为false
记录length

找到front, rear, length的关系

front = (rear + MAXSIZE - length) % MAXSIZE

数组

数组的递归定义

一维数组：\((a_1,a_2,...,a_n)\)，其中\(a_i\)为数据元素\(1\leq i\leq n\)
二维数组：\((\alpha_1,\alpha_2,...,\alpha_m)\)，其中\(\alpha_i = (a_{i1}, a_{i2},...,a_{in})\)为行向量，\(1\leq i\leq m\)
三维数组：\((\beta_1,\beta_2,...,\beta_p)\)，其中\(\beta_k=(\alpha_1,\alpha_2,...,\alpha_m)\)，\(1\leq k\leq p\)

数组的顺序表示

以行序为主序的顺序存储方式

\(\color{red}{左边的下标后变化，右边的下标先变化}\)
以列序为主序的顺序存储方式

\(\color{red}{左边的下标先变化，右边的下标后变化}\)

数组的映像函数

以行序为主序，\(a[i][j]\)的地址为：

\(Loc(i, j) = Loc(1, 1)+((i - 1)*n +(j - 1))*s\)
以列序为主序，\(a[i][j]\)的地址为：

\(Loc(i,j)=Loc(1,1)+((j-1)*m+(i-1))*s\)

以行序为主序，\(a[k][i][j]\)的地址为：

\(Loc(k,i,j)=Loc(1,1,1)+((k-1)*m*n+(i-1)*m+(j-1))*s\)
以列序为主序，\(a[k][i][j]\)的地址为：

\(Loc(k,i,j)=Loc(1,1,1)+((j-1)*p*m+(i-1)*p+k-1)*s\)

矩阵的压缩存储

\(a_{ij}\)在SA中的序号：

\(k(i,j) =\) \(\left\{\begin{aligned}i(i-1)/2 + j& &i \geq j\\ j(j-1)/2+i& &i<j\end{aligned}\right.\)

任意\(a_{ij}\neq 0\)，在SA中的序号：\(k=((i-1)*3-1)+(j-i+2)=2i+j-2\)

\(A[i,j]=\) \(\left\{\begin{aligned}k& &|i-j|\leq 1\\ 0& &其他\end{aligned}\right.\)

稀疏矩阵的存储

//定义的存储结构
#define MAXSIZE 12500
typedef struct
{
    int i, j;//非零元的下标
    ElemType e;
}Triple;
typedef struct 
{
    Triple data[MAXSIZE + 1];//非零元三元组表
    int mu, nu, tu;//矩阵的行数、列数和非零元的个数
}TSMatrix;
//求稀疏矩阵的转置
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)
{
    T.mu = M.nu, T.nu = M.mu, T.tu = M.tu;
    if(T.tu)
    {
        for(col = 1; col <= M.nu; col++) num[col] = 0;
        for(t = 1; t <= M.tu; t++) ++num[M.data[t].j];
        cpot[1] = 1;
        for(col = 2;col <= M.nu; ++col) cpot[col] = cpot[col - 1] + num[col - 1];
        for(p = 1; p <= M.tu; p++)
        {
            col = M.data[p].j;
            q = cpot[col];
            T.data[q].i = M.data[p].j;
            T.data[q].j = M.data[p].i;
            T.data[q].e = M.data[p].e;
            ++cpot[col];
        }
    }
}

十字链接表

[见此篇blog](稀疏矩阵的十字链表存储表示和实现（第五章 P104 算法5.4）_用十字链表实现稀疏矩阵的存储,写出其创建和输出算法-CSDN博客

广义表

二叉树

二叉树的性质

二叉树第i层，最多有\(2^{i-1}\)个结点
深度为k的二叉树，最多有\(2^k - 1\)个结点
\(n_0=n_2+1\)
n个结点的满二叉树深度为\(log_2(n+1)\)
顺序编号的满二叉树\(1,2,...,n\)
- 结点i的左孩子为2i，右孩子为2i+1
- 结点i的双亲为\(\lfloor i/2\rfloor\)
- 结点i的层号\(\lfloor log_2i\rfloor+1=\lceil log_2(n+1)\rceil\)
n个结点可以组成\(\frac{(2n)!}{(n+1)!n!}\)棵形态不同的二叉树

二叉树的存储

顺序存储

链式存储

二叉链表

struct BitNode
{
    struct BitNode* lcild;
    struct BitNode* rchild;
    ElemType data;
}

三叉链表

struct BitNode
{
    struct BitNode* parent;
    struct BitNode* lcild;
    struct BitNode* rchild;
    ElemType data;
}

静态链表

二叉树的遍历

时间复杂度\(O(n)\)，空间复杂度\(O(n)\)

前序+中序 / 中序+后序可以唯一确定一个二叉树

前序+后序不能唯一确定一个二叉树(eg: 先序ABC 后序CBA)

先序遍历

typedef struct BitNode* BitTree;
void PreOrderTraverse(BiTree T)
{
    if(T)
    {
        printf("%c", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    return;
}

中序遍历

typedef struct BitNode* BitTree;
void MidOrderTraverse(BitTree T)
{
    if(T)
    {
        MidOrderTraverse(T->lchild);
        printf("%c", T->data);
        MidOrderTraverse(T->rchild);
    }
    return;
}

后序遍历

typedef struct BitNode* BitTree;
void PostOrderTraverse(BitTree T)
{
    if(T)
    {
		PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c", T->data);
    }
    return;
}

非递归遍历

中序遍历：

第一次访问到根节点不访问，直接入栈
中序遍历左子树，左子树遍历结束之后，第二次遇到根节点，退栈进行访问，然后中序遍历右子树
退栈时栈为空结束

typedef struct BitNode* BitTree;
void MidOrder(BitTree t)
{
    BitTree st[max_length];
    int top = 0;
    do
    {
        while(t)//遍历完左孩子
        {
            if(top == max_length) exit(OVERFLOW);
            st[top++] = t;
            t = t->lchild;
        }
        if(top)
        {
            t = st[--top];
            printf("%c", t->data);//访问根节点
            t = t->rchild;
        }
    }while(top || t);//如果还有右子树 或者 栈非空（父节点未访问）
}

前序遍历：

typedef struct BitNode* BitTree;
void PreOrder(BitTree t)
{
    BitTree st[max_length];
    int top = 0;
    do
    {
        while(t)//遍历完左孩子
        {
            if(top == max_length) exit(OVERFLOW);
            st[top++] = t;
            printf("%c", t->data);//访问根节点
            t = t->lchild;
        }
        if(top)
        {
            t = st[--top];
            t = t->rchild;
        }
    }while(top || t);//如果还有右子树 或者 栈非空（父节点未访问）
}

后序遍历：

沿着根的左孩子依次入栈，直到左孩子为空
如果没有右孩子，或者右孩子已经访问过，就访问该根节点
栈顶元素出栈

void PostOrder(BitTree t)
{
    BitTree last;//上一个访问的节点
    BitTree st[maxlength];
    int top = 0;
    while(t)
    {
        st[top++] = t;
        t = t->lchild;
    }
    while(top)
    {
		BitTree tmp = st[--top];
        if((tmp->lchild ==NULL && tmp->rchild == NULL)
            /*如果左右孩子均为空*/
           ||(tmp->rchild == last)/*右孩子已经访问完*/
           ||(tmp->rchild == NULL && tmp->lchild == last))/*右孩子为空，左孩子访问了*/
        {
            printf("%d", tmp->data);//访问
            last = tmp;
        }
        else
        {
            BitTree r = tmp->rchild;
            while(r)
            {
                st[top++] = r;
                r = r->l·child;
            }
        }
    }
}

层序遍历

原理：使用队列进行存储，将根节点放入队列中，并且访问之后将该节点的左右孩子加入队列中

创建二叉树

递归法

void CreateBiTree(BiTree& root)
{
	char ch;
    scanf("%c", &ch);
    if(ch == #) root = NULL;
    else
    {
        root = (BiTree)malloc(SIZE);
        root->data = ch;
        CreateBiTree(root->lchild);
        CreateBiTree(root->rchild);
    }
}

非递归法

BiTree CreateTree()
{
	int i, j;
    ElemType e;
    scanf("%d%d", &i, &e);
    while(i)
    {
        q = (BiTNode*)malloc(sizeof(BiTNode));
        q->data = e;
        q->lchild = NULL, q->rchild = NULL;
        s[i] = q;
        if(i == 1) root = q;
        else
        {
            j = i/2;
            if(j % 2) s[j]->rchild = q;
            else s[j]->lchild = q;
        }
        scanf("%d%d", &i, &e);
    }
    return root;
}

线索二叉树

概念

规则：

若结点的左子树为空，则该结点的左孩子指向其前驱结点
若结点的右子树为空，则该结点的右孩子指针指向其后继结点

为了区别lchild/rchild是指向左右孩子还是前/后驱结点，添加标志位ltag, rtag：

ltag == 0，指向左孩子；ltag == 1，指向前驱结点
rtag == 0，指向右孩子；rtag == 1，指向后继结点

线索化二叉树

struct Thread
{
    struct Thread* lchild, rchild;
    int data;
    int ltag, rtag;
}
void InitThreadTree(struct Thread* node, struct Thread* pre)
{
    if(node == NULL) return ;
    InitThreadTree(node->lchild, pre);
    if(node->lchild != NULL) node->ltag = 0;//左孩子不是线索
    else node->ltag = 1, node->lchild = pre;
    //处理前驱结点
    if(pre != NULL && pre->rchild == NULL) 
        pre->rchild = node, pre->rtag = 1;
    pre = node;
    InitThreadTree(node->rchild, pre);
    
}

遍历线索二叉树

前序遍历：

void PreOrder(struct BitNode* node)
{
	struct BitNode *p = node;
    while(p)
    {
		printf("%d", p->data);
        if(p->ltag == 0)//有左孩子
            p = p->lchild;
        else//没有左孩子，指向右孩子或者后继结点
            p = p->rchild;
    }
}

中序遍历：

void MidOrder(struct BitNode* node)
{
	struct BitNode* p = node;
    while(p)
    {
		while(p->ltag == 0) p = p->lchild;//找到最左边的节点
        printf("%d", p->data);
        while(p->rchild)//存在后继结点
        {
            if(p->rtag == 1) p = p->rchild;
            else
            {
                p = p->rchild;
                while(p->ltag == 0)//找到最左边的结点
                {
                    p = p->lchild;
                }
            }
            printf("%d", p->data);
        }
        
    }
}

树和森林

树的表示形式

广义表

2. 嵌套集合

树的存储结构

双亲表示法/数组表示法/顺序表示法

struct snode
{
    char data;
    int parent;
}t[maxlength + 1];

孩子表示法/链接表表示法

孩子兄弟表示法/二叉树表示法/二叉链表

孩子链表表示法/单链表表示法

带双亲的孩子链表表示法

森林、树和二叉树的转换

树和森林的遍历

哈夫曼树

树T的路径长度：PL(T)从树T的跟到其余每个结点的路径长度之和

树的带权路径长度：WPL(T)每个叶子的权与根到该叶子的路径长度的乘积之和

typedef struct 
{
	unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanCode;//动态分配数组存储哈夫曼树
typedef char** HuffmanCode;//存储哈夫曼编码

void HuffmanCoding(HuffmanTree& HT, HuffmanCode &HC, int *w, int n)/*w存放n个字符的权值*/
{
	if(n <= 1) return;
    m = 2 * n - 1;
    HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));
    for(p = HT + 1, i = 1; i <= n; i++, p++, w++)//0号单元未用
    	*p = {*w, 0, 0, 0};
    for(;i <= m; i++, p++) *p = {0, 0, 0, 0};
    for(int i = n + 1; i <= m; i++)
    {
        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].lchild = s1, HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight +HT[s2].weight;
    }
    /*从叶子到根逆向求每个字符的哈夫曼编码*/
    HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
    cd = (char*)malloc(n * sizeof(char));
    cd[n - 1] = '\0';
    for(i = 1; i <= n; i++)
    {
        start = n - 1;
        for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[i].parent)
        	if(HT[f].lchild == c) cd[--start] = '0';
        	else cd[--start] = '1';
        HC[i] = (char*)mallov(sizeof(char) * (n - start));//为编码开辟空间
        strcpy(HC[i], &cd[start]);
    }
    free(cd);
}

图

概念

强连通图：图G中每对结点都存在路径

强连通分量：图G'是图G的极大连通子图，G'是G的一个强连通分量

图的存储结构

邻接矩阵
- 无向图中\(v_i\) 的度\(TD=\sum\limits_{j=1}^{n}M[i][j]=\sum\limits_{i=1}^{n}M[i][j]\)
- 有向图中\(v_i\) 的入度\(ID = \sum\limits_{i=1}^{n}M[i][j]\)(每一列的和)，出度\(OD = \sum\limits_{j=1}^{n}M[i][j]\)(每一行的和)
邻接表/逆邻接表
十字链表

邻接多重表

具体步骤见这个视频

存储结构的优缺点

邻接矩阵

优点：

简单直观，好理解
便于计算一对顶点间是否有边，并且找到所有的邻接点
方便计算一个顶点的度

缺点：

不利于增加或者删除节点
存储稀疏图\((e<nlogn)\)较浪费空间
在统计边数等操作方面时间复杂度大

邻接表

缺点：

求节点度困难
每条边都要存两遍（无向图）

图的遍历

DFS/BFS时间复杂度

邻接矩阵存储\(O(n^2)\)
邻接表存储\(O(n+e)\)

最小生成树

Prim

时间复杂度：\(O(n^2)\)，适合稠密图

void Prim(MGraph G, int start)
{
    for(i = 0; i < G.vertexNum; i++)//遍历所有点
    {
        shortEdge[i].lowcost = G.arc[start][i];//初始化最短路的数组
        shortEdge[i].adjvex = start;//存储这个路径距离中这个节点的上一个节点  
    }
    shortEdge[start].lowcost = 0;//将start放入集合U
    for(i = 0;i < G.vertexNum - 1; i++)
    {
        k = minEdge(shortEdge, G.vertexNum);//寻找最短边的邻接点k
        outputMST(k, shortEdge[k]);//输出最小生成树的路径
        shortEdge[k].lowcast = 0;//将k加入集合U
        for(j = 0; j < G.vertexNum; j++)//调整shortEdge数组
        {
            if(G.arc[k][j] < shortEdge[j].lowcast)
            {
                shortEdge[j].lowcast = G.arc[k][j];
                shortEdge[j].adjvex = k;
            }
        }
    }
}

Kruskal算法

时间复杂度：\(O(eloge)\)

拓扑排序

有回路的有向图不存在拓扑排序

AOE网

先求点，再求边

工程完成的最短时间是从开始点到完成点的最长路径长度，路径长度最长的路径叫做关键路径，关键路径上的点为关键点--开始时间等于结束时间

请参考这个视频

ve(事件/节点的最早开始时间)，拓扑排序，每次选取入度为0的点，更新与之相邻的结点，ve是最长的那条路径长度
vl(事件/节点的最晚开始时间)，初始化所有结点的vl为终点的ve，逆拓扑排序，每次选取出度为0的点，更新与之相邻的结点，vl是选择使vl最小的那条路
e(活动/边的最早开始时间)，与发出这条边的结点的ve一致
l(活动/边的最晚开始时间)，用这条边指向的结点的vl减去这条边的边权

最短路径

Dijkstra算法

解决单源最短路问题

请参考这个视频

int dijsktra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;//把起始点距离初始化为0
    
    for(int i = 0; i < n - 1; i++)
    {
        int t = -1;//用于找到当前距离起点最短的点
        for(int j = 1; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        st[t] = true;
        for(int j = 1; j <= n; j++)//更新节点距离
        {
            if(dist[j] > dist[t] + g[t][j]) dist[j] = dist[t] + g[t][j];
        }
        
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Floyd算法

请参考这个视频

求任意两个节点间的最短路径

void Floyd(MGraph G, PathMatrix& p[], DistanceMatrix& D)
{
    for(v = 0; v < G.vexnum; v++)
    {
        for(w = 0; w < G.vexnum; w++)
        {
            D[v][w] = G.arcs[v][w];
            for(u = 0; u < G.vexnum; u++)
            {
                P[v][w][u] = false;
                if(D[v][w] < INFINITY)
                {
                    P[v][w][v] = true;
                    P[v][w][w] = true;
                }
            }
        }
    }
    for(u = 0; u < G.vexnum; u++)
    {
        for(v = 0; v < G.vexnum; v++)
        {
            for(w = 0; w < G.vexnum; w++)
            {
                if(D[v][u] + D[u][w] < D[v][w])
                {
                    D[v][w] = D[v][u] + D[u][w];
                    for(i = 0; i < G.vexnum; i++)
                    {
                        P[v][w][i] = P[v][u][i] || P[u][w][i];
                    }
                }
            }
        }
    }
}

查找

静态查找表

顺序查找法

不设置监视哨

判断条件：

1 2	i = ST.length; while(i >= 1 && k != ST.elem[i].key) i--;

设置监视哨

elem[0].key = k;

1 2	i = ST.length; while(k != ST.elem[i].key) i--;

ASL成功 = (n + 1) / 2

ASL失败：使用监视哨 = n + 1, 不使用监视哨 = n

折半查找法

相当于二分查找

判定树

描述折半查找过程的二叉树(从1开始，放的是序号不是值)

若判定树为满二叉树：\(ASL = \frac{n+1}{n}log2(n + 1) - 1\)

证明：

动态查找表

二叉排序树（二叉查找树）

特点：如果二叉树的任一结点大于其非空左子树的所有结点，而小于其非空右子树的所有结点，则这棵二叉树称为二叉排序树。\({\color{red}(左小右大)}\)

平均ASL= O(logn)

删除二叉排序树中的结点

设被删除的结点为*p，其双亲结点为*f，*s为*p的前驱结点，*p是*f的左孩子，有三种情况：

*p为叶子结点：直接删除
*p只有左孩子PL或者右孩子PR：让PL/PR为*f的左孩子
*p的左孩子PL和右孩子PR均不为空：

算法实现：

//p是待删除的结点
void Delete(BiTree &p)
{
    if(!p->lchild)//如果左子树为空，或者为叶子结点
    { q = p; p = p->rchild; free(q);}
    else if(!p->rchild)//如果右子树为空
    { q = p; p = p->lchild; free(q);}
    else//如果左右子树均不为空 以方法二为例
    {
        q = p;
        s = p->lchild;
        while(s->rchild)
        {
            q = s;//设置s的双亲结点是q
            s = s->rchild;//遍历直到找到p的前驱结点
        }
        p->data = s->data;//将p替换成s
        //要判断是因为如果删除结点的左子树有右子树那么中序遍历的前驱结点是右孩子，否则前驱结点是左孩子，就会导致移动的不同
        if(p != q)//表明删除节点的左子树有右子树
            q->rchild = s->lchild;//不需要free因为原来的s占的是q->left，现在已经被替换了
        else
        {
            q->lchild = s->lchild;
            free(S);
        }
    }
}

平衡二叉树(\(AVL\)树)

结点的平衡因子：结点的左右子树深度之差（左子树高度-右子树高度）
平衡二叉树：任意结点平衡因子的绝对值小于等于1的二叉树

高度一定的AVL树所含最小节点个数

S(h)表示深度为h的平衡二叉树所含有的最少节点个数

构造平衡二叉搜索树的方法

左旋：向作左旋转，冲突的左孩变右孩
右旋：向右旋转，冲突的右孩变左孩
\(LL\)型，\(RR\)型，\(LR\)型，\(RL\)型
- \(LL\)型：右旋
- \(RR\)型：左旋
- \(LR\)型：先左旋左孩子，再右旋
- \(RL\)型：先右旋右孩子，再左旋
插入结点时平衡失调，调整离删除结点最近的失衡结点即可

删除结点时平衡失调，依次对每个祖先进行检查和调整

哈希表

构造哈希函数的方法

直接定址法：取关键字或者关键字的某个线性函数值作为哈希地址
除留余数法：设哈希表HT[0,1,..,m-1]的表长为m，哈希地址为key除以p所得余数（ p为接近m的素数或为不包含20以内质因数的合数）
平方取中法：取关键字平方后的中间某几位为哈希地址
折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为哈希地址
1. 边界折叠法：\(eg: k1 = 056439527\)对应的地址为\(650+439+725\)
2. 移位折叠法：\(eg: k1 = 056439527\)对应的地址为
  
  \(056+439+527\)
数字分析法：如果哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干分布均匀的位组成哈希地址
随机数法：利用\(random(key)\)

解决哈希冲突的方法

开放地址法
1. 线性嗅探再散列
2. 二次嗅探再散列
链地址法
建立公共溢出区
再哈希法

哈希化的效率

哈希表的平均查找长度

见此篇BLOG

散列表

查找成功的概率：

分母：所有待插入的元素的个数
分子：每个位置元素出现的个数

查找失败的概率：

分母：mod的大小
分子：从0-m-1的每一个位置到下一个空位置需要查找的个数

排序

插入排序（朴素版--稳定排序折半版--不稳定）

第n趟排序，保证前n + 1个元素有序

操作：将新的元素插入到已排序的数组中

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

最好的情况：原n个记录递增有序

比较关键字次数：\(n-1\)次

移动记录次数：\(2(n-1)\)次（将数据复制到a[0]又复制回来）
最坏的情况：原n个记录递减有序

比较关键字次数：\(\sum_\limits{i = 2}^n i = 2+3+...+n = \frac{(n-1)(n+2)}{2}\)

移动记录次数：\(\sum_\limits{i=2}^{n} (i-1+2)=3+4+...+n=\frac{(n-1)(n+4)}{2}\)

（+2是因为监视哨，先复制一遍，再加到合适的位置）

朴素版本：

//升序 
//对1-n进行排序(n表示的是数组的最后一个元素的下标，不是元素个数) 
//在a[0]设置监视哨
void InsertSort(int* a, int n)
{
	int cur;
	for (int i = 2; i <= n; i++)
	{
		a[0] = a[i];
		cur = i - 1;
		while (a[cur] > a[0])
		{
			a[cur + 1] = a[cur];
			cur--;
		}
		a[cur + 1] = a[0];
	}
}

折半插入排序（不稳定）：

//折半插入排序
//优化了比较次数，但是只有当n很大时使用折半插入效率更高
void InsertSort(int* a, int n)
{
	for (int i = 2; i <= n; i++)
	{
		a[0] = a[i];
		int low = 1, high = i - 1, m = (low + high) >> 1;
		while (low <= high)//利用二分法折半查找
		{
			m = (low + high) >> 1;
			if (a[0] < a[m])	high = m - 1;
            //插入的位置可能在high左边
			else low = m + 1;
            //插入的位置可能在low的右边
		}
        //high + 1即是待插入的位置
		for (int j = i - 1; j >= high + 1; j--)
		{
			a[j + 1] = a[j];
		}
		a[high + 1] = a[0];
	}
}

二路插入排序：

优点：可以减少移动的次数

操作：（排序长度为n的序列）相当于先开辟长度为n的数组，将该数组当做一个循环的空间，进行插入。

表插入排序：

希尔排序\(\color{red} {（不稳定排序）}\)

第n趟排序后，能找到n个gap使元素每隔gap个元素就有序

操作：每次排序相隔gap的元素，不断缩小gap，直至gap == 1，排序后退出循环

时间复杂度：\(O(n ^{1.3})\)

//升序--希尔排序  O(n^1.3)
//1. gap > 1 预排序
//2. gap == 1 插入排序
void ShellSort(int gap, int n)
{
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = gap + 1; i <= n; i++)
		{
			a[0] = a[i];
			int cur = i - gap;
			while (a[cur] > a[0])
			{
				a[cur + gap] = a[cur];
				cur -= gap;
			}
			a[cur + gap] = a[0];
		}
	}
}

伪代码版：

//前后记录位置的增量为dk
void shellInsert(Sqlist& L, int dk)
{
    for(i = dk + 1; i <= L.length; i++)
    {
         if(LT(L.r[i].key, L.r[i - dk].key))//将L.r[i]插入有序增量子表
         {
             L.r[0] = L.r[i];//暂存在L.r[0]中，不是哨兵位
             for(j = i - dk; j > 0 && (LT(L.r[j].key, L.r[0].key)); j -= dk)
             {
                 L.r[j + dk] = L.r[j];
             }
             L.r[j + dk] = L.r[0];
         }
    }
}
void ShellSort(Sqlist& L, int delta[], int t)
{
    for(k = 0; k < t; k++)
    {
        ShellInsert(L, delta[k]);
    }
}

快速排序\(\color{red}{(不稳定排序)}\)

第n趟排序之后，有n个元素在它应该在的位置上

操作：随机在数组中找一个数，利用递归，让左边的数都小于该数，右边的数都大于该数

时间复杂度：\(O(nlogn)\)，最坏的情况下（序列基本有序）时间复杂度为\(O(n^2)\)
空间复杂度：快排需要一个栈做辅助空间，平均情况下需要\(O(nlogn)\)的空间，最坏的情况下，要递归n次，需要\(O(n)\)的空间

int PartSort(int* a, int left, int right)
{
	int keyi = GetMidIndex(a, left, right);//找到在left，mid，right三个下标下大小是中间的那个的下标
	Swap(a + keyi, a + left);
	//左边当key 右边先走 ；右边当key 左边先走
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(a + left, a + right);
	}
	Swap(a + left, a + keyi);
	return left;
}
void QuickSort(int begin, int end)
{
	if (begin > end) return;
	int part = PartSort(a, begin, end);
	QuickSort (part + 1, end);
	QuickSort(begin, part - 1);
}

伪码：

int partition(Sqlist& L, int low, int high)
{
	L.r[0] = L.r[low];//选最左边为pivotkey
    pivotkey = L.r[low];
    while(low < high)
    {
        while(low < high && L.r[high].key >= pivotkey)
           	high--;
        L.r[low] = L.r[high];
        while(low < high && L.r[low].key <= pivotkey)
            low++;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}

递归版：

void Qsort(Sqlist& L, int low, int high)
{
	if(low < high)
    {
		pivotloc = partition(L, low, high);
        Qsort(L, low, pivotloc - 1);
        Qsort(L, pivotloc + 1, high);
    }
}

优化版：

//三路划分的优化快排
void QuickSortThree(int* a, int begin, int end)
{
	if (begin > end)
		return;
	int keyi = GetMidIndex(a, begin, end);
	Swap(a + keyi, a + begin);
	int left = begin, right = end, cur = begin + 1, key = a[begin];
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(a + cur, a + left);
			++cur, ++left;
		}
		else if (a[cur] == key)
		{
			++cur;
		}
		else
		{
			Swap(a + cur, a + right);
			--right;
		}
	}
	QuickSortThree(a, begin,left - 1);
	QuickSortThree(a, right + 1, end);
}

选择排序\(\color{red}{(不稳定排序)}\)

排序n趟之后，前n个元素应该是整个序列中最小的n个元素，并且顺序排列

操作：每次选择未选择序列中最小的（最大的），放在已经排序的序列之后时间复杂度：

比较次数：\(\frac{n(n-1)}{2}\)即\(O(n^2)\)
移动次数：
- 最好的情况，一开始就是升序，不需要移动
- 最坏的情况：每次都需要移动（不是降序的时候），交换记录数为n-1对，移动记录数为3(n-1)（因为swap里面有三条语句）

void SelectSort(int n)
{
	for (int i = 1; i < n; i++)
	{
		int mini = i;
		for (int j = i + 1; j <= n; j++)
		{
			if (a[j] < a[mini]) mini = j;
		}
		Swap(&a[mini], &a[i]);
	}
}

堆排序\(\color{red}{(不稳定排序)}\)

排序n趟之后，数组的最后n个元素应该是最大且有序的

对n较大的文件有效

操作：升序建大堆，降序建小堆

//升序--堆排序
void AdjustDown(int *a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
			++child;
		if (a[child] > a[parent])
		{
			Swap(a + child, a + parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
void AdjustUp(int* a, int child)//造大堆
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(a + child, a + parent);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}

}
void HeapSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
		AdjustUp(a, i);
	int end = n - 1;
	while (end > 0)
	{
		Swap(a, a + end);
		AdjustDown(a, end , 0);
//因为end是交换过去的最后一个 所以循环应该到这个就结束 不应该传end+1
		end--;
	}
}

伪码：

typedef Sqlist HeapType;
//H[s...m]中除了H.r[s].key其他都满足堆的定义
void HeapAdjust(HeapType& H, int s, int m)
{
    rc = H.r[s];
    for(j = 2 * s; j < m; j++)
    {
        if(j < m && LT(H.r[j].key, H.r[j + 1].key)) j++;
        if(!(rc.key, H.r[j].key)) break;
        H.r[s] = H.r[j]; s = j;//向下遍历
    }
    H.r[s] = rc;
}
void HeapSort(HeapType& H)
{
    for(i = H.length / 2; i > 0; i--)
        HeapAdjust(H, i, H.length);
    for(i = H.length; i > 0; i--)
    {
        H.r[i]<-->H.r[1];
        HeapAdjust(H, 1, i - 1);
    }
}

归并排序（稳定排序）

第1趟排序之后，从开始起相邻两个元素为升序排列；第二趟排序之后，相邻4个元素为升序排列……第n趟排序之后，相邻\(2^n\)个元素为升序排列

操作：将它们划分为长度均为1的子序列，然后逐步二路归并

时间复杂度：

对n个记录的文件进行归并排序，共需要\(log_2n\)趟，每趟所需要比较的关键字次数不超过n，所以总比较次数为\(O(nlogn)\)
每趟移动n个记录，移动次数为\(O(nlogn)\)
归并排序需要一个大小为n的辅助空间

void MergeSort(int *a, int begin, int end, int* tmp)
{
	if (begin == end) return;
	int mid = (begin + end) >> 1;
	MergeSort(a, begin, mid, tmp);
	MergeSort(a, mid + 1, end, tmp);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

伪码：

void Merge(RcdType SR[], RcdType& TR[], int i, int m, int n)
{
	//将有序的SR[i...m]和SR[m + 1...n]归并为有序的TR[i...n]
    for(j = m + 1, k = i; i <= m && j <= n; k++)
    {
        if(LQ(SR[i].key, SR[j].key)) TR[k] = SR[i++];
        else TR[k] = SR[j++];
    }
    if(i <= m) TR[k...n] = SR[i...m];
    if(j <= n) TR[k...n] = SR[j...n];
}
void MSort(RcdType SR[], ScdType& TR1[], int s, int t)
{
    //将SR[s...t]归并为TR1[s...t]
    if(s == t) TR1[s] = SR[s];
    else
    {
        m = (s + t)/2;
        Msort(SR, TR2, s, m);
        Msort(SR, TR2, m + 1, t);
        Merge(TR2, TR1, s, m, t);
    }
}
void MergeSort(Sqlist &L)
{
    Msort(L.r, L.r, 1, L.length);
}