java算法刷题00——数据结构基础知识回顾

迷南。 2023-10-01 09:34 1阅读 0赞

#### 数据结构基础知识回顾 ####

*   *   *  1、数据结构概述
         *   *  0.数据结构在学什么
             *  1.数据结构的基本概念（抓大放小）
             *   *  1）基本概念
                 *  2）数据结构的三要素
                 *  3）数据类型、抽象数据类型
             *  2.算法的基本概念
             *   *  1）什么是算法
                 *  2）算法的五大特性
                 *  3）“好算法”的特点
             *  3.算法的时间复杂度
             *  4.算法的空间复杂度
         *  2、线性表
         *   *  1.线性表的定义与基本操作
             *   *  1）定义
                 *  2）基本操作
             *  2.线性表的顺序表示
             *   *  1）顺序表的定义
                 *  2）顺序表的实现
                 *  3）顺序表的四大特点
                 *  4）顺序表的基本操作
                 *  5）练习题
             *  3.单链表
             *   *  1）顺序表与链式表的比较
                 *  2）单链表定义
                 *  3）单链表的插入
                 *  4）单链表的删除
                 *  5）单链表的查找
                 *  6）单链表的建立
             *  4.双链表
             *   *  1）双链表的定义
                 *  2）双链表的插入
                 *  3）双链表的删除
                 *  4）双链表的遍历
             *  5.循环链表
             *   *  1）循环单链表
                 *  2）循环双链表
             *  6.静态链表
             *   *  1）静态链表的定义
                 *  2）静态链表的基本操作
                 *  3）静态链表的优缺点
             *  7.顺序表与链表的对比
             *  8.练习题
         *  3、栈和队列
         *   *  1.栈
             *   *  1）栈的基本概念
                 *  2）栈的基本操作
                 *  3）顺序栈的实现
                 *  4）链式栈
             *  2.队列
             *   *  1）队列的基本概念
                 *  2）队列的顺序存储结构
                 *  3）队列的链式存储结构
             *  3.栈和队列的应用
             *   *  1）栈在括号匹配中的应用
                 *  2）栈在表达式中的应用
                 *  3）进制转换
             *  4.串
             *   *  1）串的基本操作
                 *  2）串的朴素模式匹配算法
         *  4、树
         *   *  1.二叉树
             *   *  1）树的顺序存储
                 *  2）树的链式存储
                 *  3）二叉树的层次遍历
                 *  4）线索二叉树的构造
                 *  5）线索二叉树的遍历
                 *  6）平衡二叉树
         *  5、图
         *   *  1.图的存储结构
             *   *  1）数组表示法
                 *  2）邻接表
                 *  3）十字链表法
             *  2.图的遍历
             *   *  1）广度优先遍历
                 *  2）深度优先遍历
             *  3.最小生成树（prim算法）
             *  4.最短路径
             *   *  1）单源最短路径
             *  5.拓扑排序
         *  6、排序
         *   *  1.插入排序
             *   *  1）直接插入排序
                 *  2）折半插入排序
                 *  3）希尔排序
             *  2.交换排序
             *   *  1）冒泡排序
                 *  2）快速排序
             *  3.选择排序
             *   *  1）简单选择排序
                 *  2）堆排序
             *  4.归并排序
             *  5.快速排序

#### 1、数据结构概述 ####

##### 0.数据结构在学什么 #####

##### 1.数据结构的基本概念（抓大放小） #####

###### 1）基本概念 ######

数据、数据元素（如一个账号）、数据项（密码、昵称）、数据结构（具有关系的一组数据元素集合，联想汉字的结构其实就是具有布局关系的符号组合）、数据对象（具有相同性质的数据元素的集合、一家海底捞的排队信息可以看作数据结构、全国所有门店排队信息看做同一个数据对象，它们虽无直接关系，但是具有同样的联系）

###### 2）数据结构的三要素 ######

逻辑结构、物理结构、数据运算

逻辑结构：集合、线性、树、图

物理结构：顺序存储、链式存储、索引存储（在存储数据的同时建立一张索引表，索引表中一般存放唯关键字+地址，比如海底捞中每个人取一个号）、散列存储（由关键字计算出其存储位置）。顺序存储数据是连续的，非顺序存储数据是离散的。数据存储的物理结构影响：增删与查找的便利度

数据运算的定义由逻辑结构定义，由物理结构实现。

###### 3）数据类型、抽象数据类型 ######

数据类型：一组同类型数据+操作，比如int类型数据，可以±\*/，比如boolean类型，可以与或非操作。

数据类型分类：原子类型、结构类型（结构体）

抽象数据类型：抽象数据组织及其操作，即定义一个理论的数据类型，讨论其元素的逻辑关系，不讨论其实际物理结构。

##### 2.算法的基本概念 #####

###### 1）什么是算法 ######

程序=数据结构+算法，数据结构把现实生活中的信息存储到了计算机中，算法提供了解决实际问题的方法。比如海底捞的顾客排队信息用数据结构存储到了计算机中，那怎么实现vip插队就由算法来实现。

###### 2）算法的五大特性 ######

有穷性（程序可以无穷，比如海底捞排队系统只要不关机就一直运行）、确定性（无二义）、可行性（可由基本运算执行有限次实现）、0个或多个输入、1个或多个输出

###### 3）“好算法”的特点 ######

正确性（能够正确解决问题）、可读性、健壮性（非法输入可处理）、高效率低存储

##### 3.算法的时间复杂度 #####

算法的时间复杂度：预估运行时间与问题规模的关系T（n）。大O法表示，本质是：时间与问题规模的函数，不考虑低阶，不考虑系数，只考虑其数量级。  
 T （ n ） = O （ f （ n ） ） T（n）=O（f（n）） T（n）=O（f（n））  
运算：加法规则、乘法规则（略）。

结论：

1.顺序执行的代码只影响常数项、忽略。

2.只需挑循环中的一个基本语句来判断其执行次数、分析时间复杂度即可。

3.多层嵌套只需关注最深层。

void loveYou（int flag[],int n）
    {
        
        int i;
        for(i=0;flag[i]<n;i++)
        {
        
            if(flag[i]==n)printf("I love U");
            break;
        }
    }

最好的情况：flag\[0\]等于n，最优时间复杂度O（1）；

最坏的情况：要查找至最后一个数，最坏时间复杂度O（n）；

平均情况：(1+2+…+n)/n=n\*(n+1)/2，平均时间复杂度O（n）。

##### 4.算法的空间复杂度 #####

算法原地工作：算法的空间复杂度是常量。

void loveYou(int n;)
    {
        
     	int flag[n];   
        int i;
    }

数据所占内存：4+4n+4 B；空间复杂度：S(n）=O(n）；

递归调用：

void loveYou(int n)
    {
        
        if(n>1) loveYou(n-1);
        printf("I love U %d\n");
    }
    
    int main(void){
        
        loveYou(5);
        return 0;
    }

每次执行loveYou需要使用k（常数）个存储空间存储数据，调用5次就会使用5k个存储空间，空间复杂度S(n)=O(n);

void loveYou(int n)
    {
        
    	int flag[n];
        if(n>1) loveYou(n-1);
        printf("I love U %d\n");
    }
    
    int main(void){
        
        loveYou(5);
        return 0;
    }

每一次执行loveYou占用4\*(n+(n-1)+…1)+个空间存储数据\[数组\]，S(n)=O(n^2);

#### 2、线性表 ####

##### 1.线性表的定义与基本操作 #####

###### 1）定义 ######

具有相同类型数据的有限序列（有次序）。表长、空表、位序（是线性表中第几个元素,从1开始）

###### 2）基本操作 ######

初始化:InitList(&L)；

增加元素:ListInsert(&L,i,e);

删除元素:LisDelete(&L,i,&e);//用e返回删除元素的值,要把数据“带回来”，传地址，其实也可以传e，用return语句带回来

销毁:DestroyList(&L);

按值查找:LacateElem(L,e);

按位查找:GetElem(L,i);

输出:PrintList(L);

判空:Empty(L);

##### 2.线性表的顺序表示 #####

###### 1）顺序表的定义 ######

顺序存储实现的线性表。第一个a1元素位置，LOC(L);后续元素ai位置，LOC(L)+(i-1)\*sizeof(ElemType)。

###### 2）顺序表的实现 ######

静态分配：

#define MaxSize 50
    typedef struct{
        
    	int data[MaxSize];
    	int length;
    }SqlList;
    
    void InitList(SqlList &L)
    {
        
    	int i;
    	for(i=0;i<L.length;i++) L.data[i]=0;
    	L.length=0;
    }
    
    int main(void)
    {
        
    	SqlList L;
    	InitList(L);
    	int i;
    	for(i=0;i<L.length;i++)printf("%d ",L.data[i]);
    	return 0;
    }

动态分配：

#include<stdio.h>
    #include<stdlib.h>
    #define InitSize 4 //默认长度
    typedef struct{
        
    	int * data;
    	int MaxSize;
    	int length;
    }SeqList;
    
    void InitList(SeqList &L)
    {
        
    	L.data=(int *)malloc(InitSize*sizeof(int));
    	L.length=0;
    	L.MaxSize=InitSize;
    }
    
    void IncreaseSize(SeqList &L,int len)
    {
        
    	int * p=L.data;
    	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    	for(int i=0;i<L.MaxSize;i++) L.data[i]=p[i];
    	free(p);
    	L.MaxSize=L.MaxSize+len;
    }
    int main(void)
    {
        
    	SeqList L;
    	InitList(L);
        //这种插入数据的方式不规范，并没有改变length
    	L.data[0]=1;
    	L.data[1]=2;
    	L.data[2]=3;
    	L.data[3]=4;
    	for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]);
    	printf("\n");
    	IncreaseSize(L,3);
    	for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]);
    	return 0;
    }

###### 3）顺序表的四大特点 ######

可以随机访问。

存储密度高，只需存数据，不需存指针。

扩展容量不方便，静态分配无法扩展，动态分配需要把存储的内容复制到新分配的区域。

插入、删除效率低。

###### 4）顺序表的基本操作 ######

插入

#include<stdio.h>
    #include<stdlib.h>
    #define InitSize 10
    
    typedef struct{
        
    int * data;
    int length;
    int MaxSize;
    }SeqList;
    
    void InitList(SeqList &L)
    {
        
    	int i=0;
    	L.data=(int *)malloc(InitSize*sizeof(int));
    	for(i=0;i<L.MaxSize;i++)L.data[i]=0;
    	L.length=0;
    	L.MaxSize=InitSize;
    }
    
    bool ListInsert(SeqList &L,int i,int e)//i是位序,不是数组下标
    {
        
    	if(i<1||i>L.length+1) return false;
    	if(i>L.MaxSize) return false;
    	int j;
    	for(j=L.length;j>=i;j--)
    		L.data[j]=L.data[j-1];  //1
    	L.data[i-1]=e;
    	L.length++;
    	return true;
    }
    
    
    int main(void)
    {
        
    	SeqList L;
    	InitList(L);
    	ListInsert(L,1,1);
    	ListInsert(L,2,2);
    	ListInsert(L,3,3);
    	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    	printf("\n");
    	ListInsert(L,1,0);
    	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    	return 0;
    }

最优时间复杂度：O（1），即插入到表尾——位序n+1处，不需要执行最深层的for循环（1处）；

最坏时间复杂度：O（n），插入到表头——位序为1处，最深层for循环执行n次；

平均复杂度：O（n），每个位序插入的可能性是1/（n+1）,(0+1+…+n)/(n+1)=n\*(n+1)/2 /(n+1)=n/2;

删除

#include <stdio.h>
    #include <stdlib.h>
    #define InitSize 10
    
    typedef struct{
        
    int * data;
    int MaxSize;
    int length;
    }SeqList;
    
    void InitList(SeqList &L)
    {
        
    	int i;
    	L.data=(int *)malloc(InitSize*sizeof(int));
    	L.MaxSize=InitSize;
    	for(i=0;i<L.MaxSize;i++) L.data[i]=0;
    	L.length=0;
    }
    
    bool ListInsert(SeqList &L,int i,int e)
    {
        
    	int j;
    	if(i<1||i>L.length+1)return false;
    	if(i>L.MaxSize)return false;
    	for(j=L.length;j>=i;j--)
    		L.data[j]=L.data[j-1];
    	L.data[i-1]=e;
    	L.length++;
    	return true;
    }
    //按位删除
    bool ListDelete(SeqList &L,int i,int &e) //此处传入的参数i是位序为i的元素，即删除对应下标为i-1的元素
    {
        
    	if(i<1||i>L.length)return false;
    	e=L.data[i-1]; 
    	int j;
    	for(j=i;j<L.length;j++)
    		L.data[j-1]=L.data[j];
    	L.length--;
    	return true;
    }
    
    int main(void)
    {
        
    	int e=-1;
    	SeqList L;
    	InitList(L);
    	ListInsert(L,1,1);
    	ListInsert(L,2,2);
    	ListInsert(L,3,3);
    	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    	printf("\n");
    	if(ListDelete(L,1,e))
    		printf("Delete %d\n",e);
    	else
    		printf("Failure!\n");
    	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    	return 0;
    }

最好时间复杂度：O（1);

最坏时间复杂度：O（n);

平均复杂度：O（n）;

按位查找

#include<stdio.h>
    # define MaxSize 10
    typedef struct{
        
    	int data[MaxSize];
    	int length;
    }SeqList;
    
    void InitList(SeqList &L)
    {
        
    	int i;
    	for(i=0;i<MaxSize;i++)L.data[i]=0;
    	L.length=0;
    }
    
    bool ListInsert(SeqList &L,int i,int e)
    {
        
    	int j;
    	if(i<1||i>L.length+1)return false;
    	if(i>MaxSize)return false;
    	for(j=L.length;j>=i;j--)
    		L.data[j]=L.data[j-1];
    	L.data[i-1]=e;
    	L.length++;
    	return true;
    }
    
    int GetElem(SeqList L,int i){
        
    	if(i<1||i>L.length) return -1;
    	return L.data[i-1];
    }
    
    int main(void)
    {
        
    	SeqList L;
    	InitList(L);
    	ListInsert(L,1,1);
    	ListInsert(L,2,2);
    	ListInsert(L,3,3);
    	printf("%d,",GetElem(L,1));
    	printf("%d\n",GetElem(L,0));
    	return 0;
    }

时间复杂度：O（1）

按值查找

int LocateElem(SeqList L,int e)
    {
        
    	int i;
    	for(i=0;i<L.length;i++)
    		if(L.data[i]==e)return i+1;
    	return 0;
    }

最好时间复杂度：O(1)

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

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

###### 5）练习题 ######

T1 删除顺序表中的最小值（假设唯一），并由函数返回被删元素的值。若顺序表为空则显示出错信息并退出运行

//删除最小元素，并返回该元素的值
    bool ListDelete(SeqList &L,int &min)
    {
        
    	int i; 
    	int index=0;//记录最小元素的位序
    	if(L.length==0) return false; //如果链表为空，则返回false
    	min=L.data[0];
    	//查找最小的元素
    	for(i=1;i<L.length;i++)
    	{
        
    		if(L.data[i]<min) min=L.data[i];
    		index=i+1;
    	}
    	//将空出来的位置由最小的元素代替
    	L.data[index]=L.data[L.length-1];
    	L.length--;
    	return true; 
    }

T2 设计算法将顺序表中的元素逆序，要求算法的空间复杂度O(1);

bool ReverseList(SeqList &L)
    {
        
    	if(L.length==0)return false;
    	int i;
    	int j;
    	int temp;
    	for(i=0;i<(L.length)/2;i++)
    	{
        
    		j=L.length-i-1;
    		temp=L.data[i];
    		L.data[i]=L.data[j];
    		L.data[j]=temp;
    	}
    	return true;
    }

\*T3 长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法。该算法删除线性表中所有值为x的元素。

void DeleteByValue(SeqList &L,int x)
    {
        
    	int k=0;//用来存储不是x的数的个数
    	for(int i=0;i<L.length;i++)
    	{
        
    		if(L.data[i]!=x)
    		{
        
    			L.data[k]=L.data[i];
    			k++;
    		}
    	}
    	L.length=k;
    }

T4 从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，如果s或者t不合理或顺序表为空，则显示出错信息并退出运行。

bool DeleteBetweenValue(SeqList &L,int s,int t,int &start,int &end)
    {
        
    	if(L.length==0) return false;
    	if(s>=t) return false;
    	int i;
    	for(i=0;i<L.length;i++)
    	{
        
    		if(L.data[i]==s)start=i+1;
    		if(L.data[i]==t)end=i+1;
    	}
    	return true;
    }
    
    int main(void)
    {
        
    	int e=0;
    	SeqList L;
    	InitList(L);
    	int start;
    	int end;
    	ListInsert(L,1,1);
    	ListInsert(L,2,2);
    	ListInsert(L,3,3);
    	for(int i=0;i<L.length;i++)printf("%d,",L.data[i]);
    	DeleteBetweenValue(L,1,2,start,end);
    	printf("\n");
    	int k=end-start+1;
    	for(int j=0;j<k;j++) ListDelete(L,start,e);
    	for(int i=0;i<L.length;i++)printf("%d,",L.data[i]);
    	return 0;
    }

##### 3.单链表 #####

###### 1）顺序表与链式表的比较 ######

顺序表：存储密度高、可以随机存取，但是扩展容量不方便，删除、插入元素开销大。

链式表：需要存储指针信息，不能随机存取，只能依次遍历，删除、插入元素开销小，扩展容量很容易。

###### 2）单链表定义 ######

不带头结点

#include <stdio.h>
    
    typedef struct LNode{
        
    	int data;
    	struct LNode * next;
    }LNode,*LinkList;
    
    //无头节点
    bool InitList(LinkList &L)
    {
        
    	L=NULL; //把头指针置空
    	return true;
    }
    
    //判断链表是否为空，如果为空，头指针指向NULL
    bool IsListEmpty(LinkList L)
    {
        
    	return (L==NULL);
    }
    
    int main(void)
    {
        
    	LinkList L; //声明一个指向单链表的指针
    	InitList(L);
    	printf("%d",IsListEmpty(L));
    	return 0;
    }

带头结点

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct LNode{
        
    	int data;
    	struct LNode * next;
    }LNode,*LinkList;
    
    //带头节点
    bool InitList(LinkList &L)
    {
        
    	L=(LNode *)malloc(sizeof(LNode));
    	if(L==NULL)return false; //上面头指针指向了头结点，头指针还指向NULL,说明内存空间不足，返回false；
    	L->next=NULL; //头结点置空
    	return true;
    }
    
    //判断链表是否为空，如果为空，头指针指向NULL
    bool IsListEmpty(LinkList L)
    {
        
    	return (L->next==NULL);
    }
    
    int main(void)
    {
        
    	LinkList L; //声明一个指向单链表的指针
    	InitList(L);
    	printf("%d",IsListEmpty(L));
    	return 0;
    }

###### 3）单链表的插入 ######

按序号插入——带头结点(推荐)

#include <stdio.h>
    #include <stdlib.h>
    typedef struct LNode{
        
    	int data;
    	LNode * next;
    }LNode,*LinkList;
    
    void InitList(LinkList &L)
    {
        
    	L=(LNode *)malloc(sizeof(LNode)); //分配一个空间作为头结点，头指针指向头结点
    	L->next=NULL; //头节点的next域置空
    }
    
    //按位序插入
    bool ListInsert(LinkList &L,int i,int e)
    {
        
    	if(i<1) return false;
    	LNode * p=L; //指针p指向头结点
    	int j=0; //下标j用来记录指针p指向第几个结点
    	while(p!=NULL&&j<i-1) //循环找到第i-1个结点
    	{
        
    		p=p->next;
    		j++;
    	}
    	if(p==NULL) return false; //i值超过了链表的范围，不合法
    	LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
    	s->data=e; //将要插入的数据e存到结点中
    	s->next=p->next;
    	p->next=s;
    	return true;
    }
    
    int main(void)
    {
        
    	LinkList L; //申请一个LinkList类型的头指针
    	InitList(L);
    	if(ListInsert(L,1,1))
    	{
        
    		printf("%d\n",L->next->data);
    	}
    	else
    		printf("Failed!\n");
    	return 0;
    }

最好时间复杂度：O(1),最坏时间复杂度：O(n),平均时间复杂度：O(n)

按序号插入——不带头结点

#include <stdio.h>
    #include <stdlib.h>
    typedef struct LNode
    {
        
    	int data;
    	LNode * next;
    }LNode,*LinkList;
    
    //不带头结点
    bool InitList(LinkList &L)
    {
        
    	L=NULL; //将头指针置空
    	return true;
    }
    
    //按位插入
    bool ListInsert(LinkList &L,int i,int e)
    {
        
    	if(i<1) return false; //非法输入
    	if(i=1)
    	{
        
    		LNode * s=(LNode *)malloc(sizeof(LNode));
    		s->data=e;
    		s->next=L;
    		L=s;
    		return true;
    	}
    	int j=1; //用来记录p指向第几个结点
    	//找到第i-1个结点
    	LNode * p=L;
    	while(p!=NULL&&j<i-1)
    	{
        
    		p=p->next;
    		j++;
    	}
    	if(p==NULL) return false;
    	LNode * s=(LNode *)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=p->next;
    	p->next=s;
    	return true;
    }
    
    int main(void)
    {
        
    	LinkList L;//声明一个头指针
    	InitList(L);
    	if(ListInsert(L,0,1))
    	{
        
    		printf("%d\n",L->data);
    	}
    	else
    		printf("Failed!\n");
    	return 0;
    }

指定结点后插操作

bool InsertNextNode(LNode * p,int e)
    {
        
    	if(p==NULL) return false; //i值超过了链表的范围，不合法
    	LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
    	s->data=e; //将要插入的数据e存到结点中
    	s->next=p->next;
    	p->next=s;
    	return true;
    }

时间复杂度:O（1）

指定结点前插操作

#include <stdio.h>
    #include <stdlib.h>
    typedef struct LNode
    {
        
    	int data;
    	LNode * next;
    }LNode,*LinkList;
    
    void InitList(LinkList &L)
    {
        
    	LNode * p;
    	L=(LNode *)malloc(sizeof(LNode));
    	p=L;
    	p->next=NULL;
    }
    
    //按位插入
    bool ListInsert(LinkList &L,int i,int e)
    {
        
    	if(i<1) return false; //非法输入
    	int j=0; //用来记录p指向第几个结点
    	//找到第i-1个结点
    	LNode * p=L;
    	while(p!=NULL&&j<i-1)
    	{
        
    		p=p->next;
    		j++;
    	}
    	if(p==NULL) return false;
    	LNode * s=(LNode *)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=p->next;
    	p->next=s;
    	return true;
    }
    
    //核心代码块，插入制定结点之前
    bool InsertPrioList(LNode * p,int e)
    {
        
    	if(p==NULL)return false;
    	LNode * s=(LNode *)malloc(sizeof(LNode));
    	if(s==NULL)return false;
    	//把s插入p结点之后
    	s->next=p->next;
    	p->next=s;
    	//把p的数据拷贝到s，再把要插入的数据存入p
    	s->data=p->data;
    	p->data=e;
    	return true;
    }
    
    int main(void)
    {
        
    	LinkList L;
    	InitList(L);
    	ListInsert(L,1,1);
    	LNode * r=L->next;
    	InsertPrioList(r,5);
    	printf("%d",L->next->data);
    	return 0;
    }

时间复杂度：O（1）

###### 4）单链表的删除 ######

#include <stdio.h>
    #include <stdlib.h>
    typedef struct LNode
    {
        
    	int data;
    	LNode * next;
    }LNode,*LinkList;
    
    bool InitList(LinkList &L)
    {
        
    	L=(LNode *)malloc(sizeof(LNode));
    	if(L==NULL)return false;
    	L->next=NULL;
    	return true;
    }
    
    //按位插入
    bool ListInsert(LinkList &L,int i,int e)
    {
        
    	if(i<1) return false; //非法输入
    	int j=0; //用来记录p指向第几个结点
    	//找到第i-1个结点
    	LNode * p=L;
    	while(p!=NULL&&j<i-1)
    	{
        
    		p=p->next;
    		j++;
    	}
    	if(p==NULL) return false;
    	LNode * s=(LNode *)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=p->next;
    	p->next=s;
    	return true;
    }
    
    //核心代码，按位序删除
    bool ListDelete(LinkList &L,int i,int &e)
    {
        
    	if(L->next==NULL)return false;
    	if(i<1)return false;
    	//找到第i-1个位置
    	LNode * p=L;
    	int j=0;
    	while(j<i-1&&p!=NULL)
    	{
        
    		p=p->next;
    		j++;
    	}
    	if(p==NULL) return false;
    	//在第i-1个位置后执行删除操作
    	LNode * q=p->next;
    	e=q->data;
    	p->next=q->next;
    	free(q);
    	return true;
    }
    
    void PrintList(LinkList L)
    {
        
    	LNode * p=L;
    	while(p->next!=NULL)
    	{
        
    		p=p->next;
    		printf("%d ",p->data);
    	}
    	printf("\n");
    }
    
    int main(void)
    {
        
    	LinkList L;
    	InitList(L);
    	ListInsert(L,1,1);
    	ListInsert(L,2,2);
    	ListInsert(L,3,3);
    	LNode * p=L;
    	PrintList(L);
    	int e;
    	ListDelete(L,2,e);
    	p=L;
    	PrintList(L);
    	return 0;
    }

最好时间复杂度：O（1）、最坏、平均时间复杂度O（n).

指定结点的删除

bool DeleteNode(LNode * p)
    {
        
    	if(p==NULL) return false;
    	LNode * q=p->next;
    	p->data=q->data;
    	p->next=q->next;
    	free(q);
    	return true;
    }

时间复杂度:O(1)

\[注\]若要删除最后一个结点，p->next为NULL，故q不存在data域，这种解法不适用了。

###### 5）单链表的查找 ######

按位查找

LNode * GetElem(LinkList L,int i)
    {
        
    	if(i<0) return NULL;
    	LNode * p=L;
    	int j=0;
    	while(j<i&&p!=NULL)
    	{
        
    		p=p->next;
    		j++;
    	}
    	return p;
    }

平均时间复杂度:O（n）

按值查找

表长

int ListLength(LinkList L)
    {
        
    	int i=0;
    	LNode * p=L->next;
    	while(p!=NULL)
    	{
        
    		p=p->next;
    		i++;
    	}
    	return i;
    }

###### 6）单链表的建立 ######

尾插法

可以通过每一次插入都调用

while 循环
    {
        
    	//取数据元素
    	ListInsert(LinkList,length+1,e); //插至链表尾部
        length++;
    }

但每次插入一个元素都要从头开始遍历，时间复杂度为O（n^2);可以通过一个指针来指向表尾，每次移动尾指针改良；

LinkList Link_TailInsert(LinkList &L) //正向建立单链表
    {
        
    	//初始化
    	L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
    	LNode * p=L; //指针p指向头结点
    	//用户输入数据、并依次生成结点,直至用户输入9999退出
    	int x;
    	scanf("%d",&x);
    	while(x!=9999)
    	{
        
    		LNode * q=(LNode *)malloc(sizeof(LNode));
    		p->next=q;
    		p=q;
    		p->data=x;
    		scanf("%d",&x);
    	}
    	p->next=NULL; //尾指针置空，不做这一步，最后尾指针会指向自己
    	return L;
    }

头插法

LinkList Link_HeadInsert(LinkList &L)
    {
        
    	int a;
    	LNode * p;
    	//初始化
    	L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
    	L->next=NULL; //必须指向NULL
    	//输入数据、并把输入的数据插入到头结点之后
    	scanf("%d",&a);
    	while(a!=9999)
    	{
        
    		p=(LNode *)malloc(sizeof(LNode));
    		p->data=a;
    		p->next=L->next;
    		L->next=p;
    		scanf("%d",&a)；
    	}
    	return L;
    }

头插法的应用：实现链表的逆置

//法一：通过新建一个链表实现
    LinkList ReverseList(LinkList &L)
    {
        
    	LNode * p; //指针
    	LinkList s=(LNode *)malloc(sizeof(LNode)); //生成一个新的链表
    	s->next=NULL;
    	while(L->next!=NULL)
    	{
        
    		//从头开始依次取下链表L的结点
    		p=L->next; //指向要被取下的结点
    		L->next=p->next;
    		//把取下的数据使用头插法插入到新的链表s
    		p->next=s->next;
    		s->next=p;
    	}
    	return s;
    }

//法二：就地转置，将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法），直到最后一个结点为止。 
    LinkList ReverseList2(LinkList &L)
    {
        
    	LNode *p,*q; //p指针指向位序为一的结点
    	p=L->next;
    	L->next=NULL; //取下头结点
    	//使用头插法把结点从头依次插入头结点后面
    	while(p!=NULL)
    	{
        
    		q=p->next; 
    		p->next=L->next;
    		L->next=p;
    		p=q;
    	}
    	return L;
    }

其实以上两个方法基本上原理是相同的，用法二更好，因为是原地转置，用法一也可以再最后把头指针L->s;

##### 4.双链表 #####

###### 1）双链表的定义 ######

typedef struct DNode{
        
    	int data;
    	DNode * next,* prior;
    }DNode,*DLinkList;
    
    bool InitList(DLinkList &L)
    {
        
    	L=(DNode *)malloc(sizeof(DNode));
    	if(L==NULL)
    		return false;
    	L->next=NULL;
    	L->prior=NULL;
    	return true;
    }
    
    bool Empty(DLinkList &L)
    {
        
    	return(L->next==NULL);
    }

###### 2）双链表的插入 ######

bool ListInsert(DNode * p,DNode * s)
    {
        
    	if(p==NULL||s==NULL) return false;
    	s->next=p->next; //1
    	if(p->next!=NULL)
    		p->next->prior=s; //2
    	s->prior=p; //3
    	p->next=s;  //4  1,2必须在4前
    	return true;
    }

这是指定结点的后插操作，按位序插入只需要设置尾指针，依次进行后插操作即可；前插操作只需要找到一个结点的前继结点，对其进行后插操作即可。

###### 3）双链表的删除 ######

bool ListDelete(DNode * p) //删除指定结点的后继节点
    {
        
    	if(p==NULL) return false;
    	DNode * q=p->next; 
    	if(q==NULL) return false;
    	p->next=q->next;
    	if(q->next!=NULL) q->next->prior=p;
    	free(q);
    	return true;
    }

销毁一个双链表

void DestroyList(DLinkList &L)
    {
        
    	while(L->next!=NULL) ListDelete(L);
    	free(L); //释放头结点
    	L->next=NULL; //头指针置空
    }

###### 4）双链表的遍历 ######

//后向遍历
    while(p!=NULL)
    {
        
        //...
        p=p->next;
    }
    
    //前向遍历
    while(p->pror!=NULL) //跳过了头结点
    {
        
        //...
        p=p->prior;
    }

##### 5.循环链表 #####

###### 1）循环单链表 ######

typedef struct LNode
    {
        
    	int data;
    	LNode * next;
    }LNode,*LinkList;
    
    bool InitList(LinkList L)
    {
        
    	L=(LNode *)malloc(sizeof(LNode));
    	if(L=NULL) return false;
    	L->next=L;
    	return true;
    }
    
    bool Empty(LinkList L)
    {
        
    	if(L->next=L) return true;
    	return false;
    }
    
    bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
    {
        
    	return(p->next==L);
    }

使用循环单链表时，如果经常需要对表头、表尾操作，可以使L指向表尾，这样找到表头、表尾的时间复杂度都是O（1）。

###### 2）循环双链表 ######

typedef struct LNode
    {
        
    	int data;
    	LNode * next;
    	LNode * prior;
    }LNode,*LinkList;
    
    bool InitList(LinkList L)
    {
        
    	L=(LNode *)malloc(sizeof(LNode));
    	if(L=NULL) return false;
    	L->next=L;
    	L->prior=L;
    	return true;
    }
    
    bool Empty(LinkList L)
    {
        
    	if(L->next=L) return true;
    	return false;
    }
    
    bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
    {
        
    	return(p->next==L);
    }
    
    bool ListInsert(DNode * p,DNode * s) 
    {
        
    	if(p==NULL||s==NULL) return false;
    	s->next=p->next; //1
    	p->next->prior=s; //2 尾节点会指向头结点，不会置空，因此不需要条件判断
    	s->prior=p; //3
    	p->next=s;  //4  1,2必须在4前
    	return true;
    }
    
    
    bool ListDelete(DNode * p) //删除指定结点的后继节点
    {
        
    	if(p==NULL) return false;
    	DNode * q=p->next; 
    	p->next=q->next;
        q->next->prior=p;
    	free(q);
    	return true;
    }

指针类链表小结

链表类代码在编写时需要考虑三个问题：

1.如何判空，知道空的状态如何判断就知道如何初始化

2.如何判断表头，表尾，知道怎么判断表头表尾就知道怎么遍历，就知道了怎么去查找、删除、增加

3.表尾、表头是否需要特殊处理

##### 6.静态链表 #####

###### 1）静态链表的定义 ######

#define MaxSize 10
    
    typedef struct Node
    {
        
    	int data;
    	int next;
    }SLinkList[MaxSize];
    
    void InitList()
    {
        
    	SLinkList a;
    }

###### 2）静态链表的基本操作 ######

初始化：要将a\[0\]置为-1；将其他空的结点游标置为-2（方便后续计算机判断哪些结点是空结点）；

查找：通过游标依次遍历元素，时间复杂度为O(n)

插入：

1.找到一个空的结点用来存放元素

2.找到位序为i-1的结点

3.修改新的结点的next游标

4.修改i-1结点的next

删除：

1.找到其前驱结点

2.修改前驱结点游标

3.被删除结点的游标置为-2；

###### 3）静态链表的优缺点 ######

优点：增删容易，不需要大量的移动数据

缺点：查找需要遍历，容量固定

##### 7.顺序表与链表的对比 #####

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th align="left">顺序表</th> 
   <th>链式表</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>逻辑结构</td> 
   <td align="left">均为线性表；</td> 
   <td>均为线性表；</td> 
  </tr> 
  <tr> 
   <td>存储结构</td> 
   <td align="left">1）基于静态分配的顺序表不能改变其大小，基于动态分配的顺序表改变容量不容易 。分配一片连续的存储区域不方便。2）存储密度较高。</td> 
   <td>1）结点无需申请一大片连续的存储空间，可以改变容量的大小。2）存储密度较低。</td> 
  </tr> 
  <tr> 
   <td>基本操作</td> 
   <td align="left">1）初始化容量大小不好确定。2）静态分配销毁由系统自动完成，动态分配手动销毁。3）插入、删除操作时间复杂度较大。4）可以随机访问元素，按位查找时间复杂度为O（1），按值查找时间复杂度为O（n）【无序】或者O（log2n）【有序】</td> 
   <td>1）销毁操作需要手动free。2）优点是插入、删除结点很方便 ，只需要改变next指针所指向的元素。3）不能够随机访问元素，只能够通过遍历的方式进行元素的访问。查找的时间复杂度为O(n)</td> 
  </tr> 
 </tbody> 
</table>

注：虽然顺序表、链式表的插入、删除操作时间复杂度都为O（n），但顺序表的时间开销来自于元素的移动，

链式的时间开销来自于结点遍历，故顺序表的时间花销其实更大。

##### 8.练习题 #####

T1 设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点

//设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点
    void Delete_x(LinkList &L,int x)
    {
        
    	LNode * p;
    	if(L==NULL)return;
    	while(L->data!=x)
    	{
        
    		Delete_x(L->next,x);
    		return;
    	}
    	p=L;
    	L=L->next;
    	free(p);
    	Delete_x(L,x);
    }

T21带头结点单链表，头指针为list。在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

1）描述算法的基本设计思想

2）描述算法的详细实现步骤

3）根据设计思想和步骤，采用程序设计语言描述算法，关键之处请给出简要注释。

解：

1）两个指针p，q分别指向位序为1的结点（头结点的后继结点），指针p依次移动直至指向位序为k的元素时，指针q随p同步移动，当指针p移动至表尾，指针q所指向元素即为倒数第k个元素。

2）算法的详细实现步骤如下：

//1.count=0,p,q指向链表头结点的后继结点；
    
    //2.若p为空，返回0；
    
    //3.若count<k,count累加，若count=k，指针q后移；
    
    //4.p结点后移，
    
    //5.若count等于k，则查找成功，输出该结点的data域，返回1;
    
    //6.算法结束

#### 3、栈和队列 ####

##### 1.栈 #####

###### 1）栈的基本概念 ######

只能从栈顶进行插入或者删除操作的线性表

###### 2）栈的基本操作 ######

InitStack(&S);

DestroyStack(&L);

Push(&S,x);

Pop(&S,&x);

GetTop(S,&x);

StackEmpty(S);

###### 3）顺序栈的实现 ######

#include <stdio.h>
    #define MaxSize 10
    typedef struct
    {
        
    	int data[MaxSize];
    	int top;
    }SeqStack;
    //初始化
    void InitStack(SeqStack &S)
    {
        
    	S.top=-1;
    }
    //栈空判断
    bool StackEmpty(SeqStack S)
    {
        
    	return(S.top==-1);
    }
    //入栈
    bool Push(SeqStack &S,int x)
    {
        
    	if(S.top==MaxSize-1) return false;
    	S.data[++S.top]=x;
    	return true;
    }
    //出栈
    bool Pop(SeqStack &S,int &x)
    {
        
    	if(S.top==-1) return false;
    	x=S.data[S.top--];
    	return true;
    }
    //读取栈顶元素
    bool GetTop(SeqStack S,int &x)
    {
        
    	if(S.top==-1) return false;
    	x=S.data[S.top];
    	return true;
    }
    
    //上述代码top指针初始指向栈顶
    int main()
    {
        
    	SeqStack S;
    	InitStack(S);
    	printf("%d\n",StackEmpty(S));
    	Push(S,2);
    	printf("%d\n",StackEmpty(S));
    	int x;
    	Pop(S,x);
    	printf("%d,%d\n",StackEmpty(S),x);
    	Push(S,3);
    	GetTop(S,x);
    	printf("%d,%d\n",StackEmpty(S),x);
    	return 0;
    }

缺点：存储容量不可改变

###### 4）链式栈 ######

#include <stdio.h>
    #include <stdlib.h>
    //定义栈结点
    typedef struct SNode{
        
    	int data;
    	SNode * next;
    }*LinkStack,SNode;
    //初始化栈（不带头结点）
    bool InitStack(LinkStack &S)
    {
        
    	S=NULL;
    	return true;
    }
    //判空
    bool StackEmpty(LinkStack S)
    {
        
    	return (S==NULL);
    }
    //入栈操作
    bool Push(LinkStack &S,int x)
    {
        
    	//在头部插入元素
    	SNode * p=(SNode *)malloc(sizeof(SNode));
    	//这里并不需要区分是不是第一个结点，两者操作时一致的！！！
    	p->data=x;
    	p->next=S;
    	S=p;
    	return true;
    }
    //出栈操作（不带头结点）
    bool Pop(LinkStack &S,int &x)
    {
        
    	if(S==NULL) return false;
    	SNode * p=S;
    	x=S->data;
    	S=S->next;
    	free(p);
    	return true;
    }
    //打印栈中元素（不带头结点）
    void PrintStack(LinkStack S)
    {
        
    	if(S==NULL) return;
    	while(S!=NULL)
    	{
        
    		printf("%d ",S->data);
    		S=S->next;
    	}
    	printf("\n");
    }
    
    //对于链式存储结构实现的栈（不带头结点）进行增删改查操作
    int main(void)
    {
        
    	int x;
    	LinkStack S;
    	InitStack(S);
    	printf("%d\n",StackEmpty(S));
    	Push(S,1);
    	Push(S,2);
    	Push(S,5);
    	Push(S,1);
    	PrintStack(S);
    	Pop(S,x);
    	Pop(S,x);
    	PrintStack(S);
    	return 0;
    }

##### 2.队列 #####

###### 1）队列的基本概念 ######

队头：允许删除元素的一端；

队尾：允许插入元素的一端。

###### 2）队列的顺序存储结构 ######

#include <stdio.h>
    #define MaxSize 10
    typedef struct SeQueue
    {
        
    	int data[MaxSize];
    	int front,rear;
    };
    //初始化队列，队头、队尾指针均指0
    void InitQueue(SeQueue &Q){
        
    	Q.front=0;
    	Q.rear=0;
    }
    //队列判空:队头与队尾指向相同空间，即差值为0，队空
    bool QueueEmpty(SeQueue Q)
    {
        
    	return (Q.front==Q.rear);
    }
    //入队操作：先将数据插入至队尾，再将尾指针后移
    bool EnQueue(SeQueue &Q,int x)
    {
        
    	if((Q.rear+1)%MaxSize==Q.front) return false; //判断队列是否满，满则返回false,这里牺牲了一个存储空间用来区分队满和队空
    	Q.data[Q.rear]=x;
    	Q.rear=(Q.rear+1)%MaxSize; //这里要注意！由于这种方式实现的队列在逻辑上似乎是循环的，也称作循环队列
    	return true;
    }
    //出队操作：先将数据取出，再将头指针后移
    bool DeQueue(SeQueue &Q,int &x)
    {
        
    	if(Q.front==Q.rear) return false; //判断是否队空
    	x=Q.data[Q.front];
    	Q.front=(Q.front+1)%MaxSize;
    	return true;
    }
    //查;获取队头元素
    bool GetHead(SeQueue Q,int &data)
    {
        
    	if(Q.front==Q.rear) return false;
    	data=Q.data[Q.front];
    	return true;
    }
    int main(void)
    {
        
    	SeQueue Q;
    	int x;
    	int data;
    	InitQueue(Q);
    	printf("队列是否为空：%d\n",QueueEmpty(Q));
    	EnQueue(Q,1);
    	printf("队列是否为空：%d\n",QueueEmpty(Q));
    	GetHead(Q,data);
    	printf("队头元素为：%d\n",data);
    	DeQueue(Q,x);
    	printf("队列是否为空：%d\n",QueueEmpty(Q));
    	return 0;
    }

队列元素个数：(Q.rear-Q.front+MaxSize)%MaxSize;

如果想要不浪费一个存储空间用来区分队满与队空，我们可以使用一个在队列中定义一个size用来记录元素个数，初始设为0，增加元素size++，减少元素size–，队满条件size= =Maxsize，队空条件为：size= =0；

也可以设置tag，删除tag置为0，插入tag置为1，队满一定是因为插入，tag一定为1；

###### 3）队列的链式存储结构 ######

#include <stdio.h>
    #include <stdlib.h>
    //定义链式队列结点
    typedef struct LinkNode
    {
        
    	int data;
    	LinkNode * next;
    }LinkNode;
    //定义链式队列
    typedef struct 
    {
        
    	LinkNode * front,* rear;
    }LinkQueue;
    //初始化(带头结点)
    void InitQueue(LinkQueue &Q)
    {
        
    	Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); 
    	Q.front->next=NULL;
    }
    //队列判空:如果头、尾指针指向同一个结点或者头结点的next指向为NULL则为空
    bool QueueEmpty(LinkQueue Q)
    {
        
    	return (Q.front->next==NULL);
    	//return (Q.front=Q.rear);
    }
    //入队操作(带头结点)
    void EnQueue(LinkQueue &Q,int x)
    {
        
    	//申请一个新的结点用于存储待插入的数据
    	LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
    	p->data=x;
    	//将新结点入队,即在队尾插入新结点
    	p->next=NULL;
    	Q.rear->next=p;
    	Q.rear=p;
    }
    //出队操作(带头结点)
    void DeQueue(LinkQueue &Q,int &x)
    {
        
    	LinkNode * p;
    	p=Q.front->next;
    	x=p->data;
    	Q.front->next=p->next;
    	//！！如果删除的元素为表尾结点,要将尾指针指向头结点
    	if(Q.rear==p)Q.rear=Q.front;
    	free(p);
    }
    //带头结点版本
    int main(void)
    {
        
    	int x;
    	LinkQueue Q;
    	InitQueue(Q);
    	printf("队列是否为空：%d\n",QueueEmpty(Q));
    	EnQueue(Q,2);
    	printf("队列是否为空：%d\n",QueueEmpty(Q));
    	DeQueue(Q,x);
    	printf("删除的元素为：%d\n",x);
    	printf("队列是否为空：%d\n",QueueEmpty(Q));
    	return 0;
    }

#include <stdio.h>
    #include <stdlib.h>
    //定义链式队列结点
    typedef struct LinkNode
    {
        
    	int data;
    	LinkNode * next;
    }LinkNode;
    //定义链式队列
    typedef struct 
    {
        
    	LinkNode * front,* rear;
    }LinkQueue;
    //初始化队列（不带头结点）:使front、rear都指向NULL
    void InitQueue1(LinkQueue &Q)
    {
        
    	Q.front=NULL;
    	Q.rear=NULL;
    }
    //判断队列是否为空（不带头结点）
    bool QueueEmpty1(LinkQueue Q)
    {
        
    	return (Q.front==NULL);
    }
    //入队操作(不带头结点)
    void EnQueue1(LinkQueue &Q,int x)
    {
        
    	//申请一个结点用来存储入队数据
    	LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
    	p->data=x;
    	//执行入队操作
    	p->next=NULL;
    	if(Q.rear==NULL)
    	{
        
    		Q.front=p;
    		Q.rear=p;
    	}
    	else
    	{
        
    		Q.rear->next=p;
    		Q.rear=p;
    	}
    }
    //出队操作(不带头结点)
    void DeQueue1(LinkQueue &Q,int &x)
    {
        
    	LinkNode * p=Q.front;
    	x=p->data;
    	Q.front=p->next;
    	//如果出队恰好使最后一个结点，那么要把rear恢复为NULL
    	if(Q.rear==p)
    		Q.rear=NULL;
    	free(p);
    }
    
    int main(void)
    {
        
    	int x;
    	LinkQueue Q;
    	InitQueue1(Q);
    	printf("队列是否为空：%d\n",QueueEmpty1(Q));
    	EnQueue1(Q,2);
    	printf("队列是否为空：%d\n",QueueEmpty1(Q));
    	DeQueue1(Q,x);
    	printf("删除的元素为：%d\n",x);
    	printf("队列是否为空：%d\n",QueueEmpty1(Q));
    	return 0;
    }

##### 3.栈和队列的应用 #####

###### 1）栈在括号匹配中的应用 ######

（（（））），最后的左括号要优先匹配——栈

#include <stdio.h>
    #define MaxSize 10		
    typedef struct
    {
        
    	char data[MaxSize];
    	int top;
    }SeqStack; 
    //初始化栈
    void InitStack(SeqStack &S)
    {
        
    	for(int i=0;i<MaxSize;i++)
    	{
        
    		S.data[i]=NULL;
    	}
    	S.top=-1; //指栈顶元素，初始时置为-1；
    }
    //判断栈是否为空
    bool StackEmpty(SeqStack S)
    {
        
    	return S.top==-1;
    }
    //入栈
    bool Push(SeqStack &S,char  x)
    {
        
    	if(S.top==MaxSize-1) return false;
    	S.top++;
    	S.data[S.top]=x;
    	return true;
    }
    //出栈
    bool Pop(SeqStack &S,char &x)
    {
        
    	if(S.top==-1) return false;
    	x=S.data[S.top];
    	S.top--;
    	return true;
    }
    //核心代码，这里为了结果直观，对不同匹配情况进行了打印，考试时可以不用，在调用Push、Pop等时对其简单
    //注 释，可直接调用
    bool BraketCheck(char Str[],SeqStack S)
    {
        
    	//判断是否有括号1
    	for(int i=0;i<6;i++)
    	{
        
    		//判断是否有左括号
    		if(Str[i]=='['||Str[i]=='(')
    		{
        
    			//左括号入栈
    			Push(S,Str[i]);
    		}
    		else
    		{
        
    			//判断是否栈空
    			if(!StackEmpty(S))
    			{
        
    				char b;
    				Pop(S,b); //弹出栈顶元素b
    				//判断括号是否匹配，
    				if(Str[i]==')'&&b=='(') {
         printf("%c %c\n",b,Str[i]);}
    				else if(Str[i]==']'&&b=='['){
         printf("%c %c\n",b,Str[i]);}
    				else 
    				{
        
    					printf("Failed!Different type of baracet!\n");return false;
    				}
    			}
    			else
    			{
        
    				 printf("Failed!Right Sigle.\n"); return false;
    			}
    		}
    	}
    	if(StackEmpty(S)){
        printf("Sucess!\n"); return true;}
    	else{
        printf("Failed!Left Sigle!\n");return true;}
    }
    //栈的应用——括号的匹配
    int main(void)
    {
        
    	SeqStack S;
    	InitStack(S);
    	char Str[6]={
        '[','(',')',']',')',')'};
    	BraketCheck(Str,S);
    	return 0;
    }

###### 2）栈在表达式中的应用 ######

后缀表达式的求值：

将后缀表达式依次压栈，遇到操作符号则弹出栈顶的两个元素，将其进行运算，先出栈的放在操作符右边；将运算的结果压栈。

//算法思想：设置操作数栈OPND，运算符栈OPTR，依次扫描表达式，遇到操作数则进操作数栈，遇到运算符则栈顶元素与运算符栈比较，若栈顶元素优先级低，则进栈，若栈顶元素优先级高则出栈。特别的，界限符'(运算优先级级最高直接入栈，)'则依次弹出运算符栈的元素，直到遇到‘（’，同时弹出操作数栈顶两个元素，第一个元素在运算符后，第二个元素在运算符前进行运算，将运算的结果重新压入操作数栈。
    OprandType EvaluateExpression(){
        
        InitStack(OPND); InitStack(OPTR);
        PUSH(OPTR,'#');
        ch=getchar();
        while(GetTop(OPTR)!='#'||ch!='#'){
        
            if(!In(ch,OP)) Push(OPND,ch);//不是运算符则进栈
            else
                switch(Precede(GetTop(OPTR),ch)){
         //拿栈顶元素与其进行比较
                    case '<' : 
                        Push(OPTR,ch);ch=getchar();
                        break;
                    case '=': //(,)中间没有其他运算符，脱括号
                        Pop(OPTR,x); ch=getchar();
                        break;
                    case '>':
                        Pop(OPTR,theta);
                        pop(OPND,b);pop(OPND,a);
                		Push(OPND,Opread(a,theta,b));
                        break;
                } //switch
        } //while
    } //EvalueateExpression

###### 3）进制转换 ######

将十进制数N转换为8进制

//算法思想：除8、取余倒排
    void convention(int n){
        
        //初始化栈
        InitStack(S);
        //N除以8，取余数，余数入栈，n更新为商，直到商为0
        while(n>0){
        
        	 Push(S,n%8);
      		 n=n/8; 
        }
        for(!StackEmpty(S)){
        
            Pop(S,e);
            printf("%d",e);
        }
    }

##### 4.串 #####

###### 1）串的基本操作 ######

#include <stdio.h>
    #define MaxSize 255
    typedef struct 
    {
        
    	char ch[MaxSize];
    	int len;
    }MyString;
    //从指定位序开始截取串的子串
    bool SubString(MyString &Sub,MyString S,int pos,int len)
    {
        
    	if(pos+len-1>S.len) return false; //子串范围越界
    	for(int i=pos;i<pos+len;i++)
    	{
        
    		Sub.ch[i-pos+1]=S.ch[i];
    	}
    	Sub.len=len;
    	return true;
    }
    //比较两个串的大小
    int CompareString(MyString S1,MyString S2)
    {
        
    	//逐个字符比较
    	for(int i=1;i<=S1.len&&i<=S2.len;i++)
    	{
        
    		if(S1.ch[i]!=S2.ch[i]) return S1.ch[i]-S2.ch[i];	
    	}
    	//扫描过的字符皆相同，比较两字符串长度
    	return S1.len-S2.len;
    }
    //定位子串
    int indexString(MyString S,MyString Sub)
    {
        
    	//暂存截取串
    	int i=1;
    	MyString temp;
    	temp.len=Sub.len;
    	while(i<=S.len-Sub.len+1)
    	{
        
    		SubString(temp,S,i,Sub.len);
    		if(CompareString(Sub,temp)!=0) ++i;
    		else return i;
    	}
    	return 0;
    }
    //串的基本操作
    int main(void)
    {
        
    	MyString S1;
    	S1.ch[0]=NULL;
    	S1.ch[1]='w';
    	S1.ch[2]='z';
    	S1.len=2;
    	MyString S2;
    	S2.ch[0]=NULL;
    	S2.ch[1]='z';
    	S2.len=1;
    	printf("%d\n",indexString(S1,S2));
    	return 0;
    }

###### 2）串的朴素模式匹配算法 ######

//串的朴素模式匹配算法
    int Index(MyString S,MyString Sub)
    {
        
    	int i,j,k;//k用于定位S当前匹配到哪个位置,i,j分别用于S与Sub的活动定位
    	k=1;
    	i=k;
    	j=1;
    	while(S.len-k+1<=Sub.len)
    	{
        
    		if(S.ch[i]==Sub.ch[j])
    		{
        
    			++i;
    			++j;
    		}
    		else
    		{
        
    			j=1;
    			++k;
    			i=k;
    		}
    		if(j>Sub.len) return k;
    		else return 0;
    	}
    }

#### 4、树 ####

##### 1.二叉树 #####

###### 1）树的顺序存储 ######

#include <stdio.h>
    #define MaxSize 100
    struct TreeNode{
        
    	int value;
    	bool isEmpty;
    };
    
    void InitTreeNode(TreeNode t[MaxSize])
    {
        
    	for(int i=0;i<MaxSize;i++){
        
    		t[i].isEmpty=true;
    	}
    }
    void main(){
        
    	TreeNode t[MaxSize];
    	InitTreeNode(t);
    }

###### 2）树的链式存储 ######

typedef struct BiTreeNode{
        
    	int value;
    	BiTreeNode * rchild,* lchild;
    }BiTreeNode,* BiTree;
    
    //插入根节点
    	BiTree root=(BiTree)malloc(sizeof(BiTreeNode));
    	root->value=1;
    	root->lchild=NULL;
    	root->rchild=NULL;
    	return true;
    
    //插入新节点
    	BiTreeNode * p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    	p->value=2;
    	p->lchild=NULL;
    	p->rchild=NULL;
    	root->lchild=p;
    	return true;
    
    //先序遍历
    void PreOrder(BiTree T)
    {
        
    	if(T!=NULL)
    	{
        
    		Visit(T);
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    }
    
    //求树的深度：后序的应用
    int TreeDepth(BiTree T)
    {
        
    	if(T==NULL) return 0;
    	int l=TreeDepth(T->lchild);
    	int r=TreeDepth(T->rchild);
    	return l>r?l+1:r+1;
    }
    
    //中序遍历（非递归实现）
    bool InOrderTraverse(BiTree T)
    {
        
        BiTreeNode * p=T; InitStack(S); //初始化一个栈
        while(p||!ISEmpty(S))
        {
        
            if(p){
        push(S,p);p=p->lchild;}
            else
            {
        
                pop(S,q);
                printf("%d,",q->data);
                p=q->rchild;
            }
        }
        return true;
    }

###### 3）二叉树的层次遍历 ######

//层次遍历
    void LevelOrder(BiTree T)
    {
        
    	LinkQueue Q;
    	InitQueue(Q);
    	BiTree p; //用来存DeQueue后的树结点
    	EnQueue(Q,T);
    	while(!IsEmpty(Q))
    	{
        
    		DeQueue(Q,p);
    		Visit(p);
    		if(T->lchild!=NULL){
        EnQueue(Q,p->lchild);}
    		if(T->rchild!=NULL){
        EnQueue(Q,p->rchild);}
    	}
    	
    }

###### 4）线索二叉树的构造 ######

#include <stdio.h>
    //定义线索二叉树结点
    typedef struct ThreadNode
    {
        
    	int data; //数据域存放二叉树数据
    	ThreadNode * lchild,*rchild; //左右孩子
    	int ltag,rtag; //左右孩子标志位
    }ThreadNode,* ThreadTree;
    
    ThreadNode * pre; //全局变量，当前结点的前驱结点

构造并中序线索化

//访问某一个树结点同时进行线索化
    void Visit(ThreadNode * p)
    {
        
    	if(p->lchild==NULL)
    	{
        
    		p->lchild=pre;
    		p->ltag=1;
    	}
    	if(pre!=NULl&&pre->rchild==NULL)
    	{
        
    		pre->rchild=p; //建立前驱结点的后继线索
    		pre->rtag=1;
    	}
    	pre=p; //把pre置为当前结点，当下一次调用visit时访问的pre就是当前结点（下一次遍历的前驱）
    }
    //二叉树中序遍历（并调用Visit进行线索化）
    void InThread(ThreadTree T)
    {
        
        if（T！=NULL）
        {
        
    	 InThread(T->lchild);
    	 Visit(T);
    	 InThread(T->rchild);
        }
    }
    
    void CreateInThread(ThreadTree T)
    {
        
        pre=NULL;
        if(T!=NULL)
        {
        
            InThread(T);
            if(pre->rchild==NULL) pre->rtag=1; //对最后一个结点进行特殊处理
        }  
    }

构造并先序线索化（构造代码同上）

//二叉树先序遍历（并调用Visit进行线索化）
    void InThread(ThreadTree T)
    {
        
        if（T！=NULL）
        {
        
        Visit(T);
        if（T->LTag==0）InThread(T->lchild); //!!!注意此处的判断条件，因为先序遍历访问顺序是根左右，如果根线索化了，无论根有没有左孩子，lchild都有指向，因此必须加此判断条件，判断其到底有没有左孩子
    	InThread(T->rchild);
        }
    }

###### 5）线索二叉树的遍历 ######

中序遍历

//找到以p为根的子树中第一个被中序遍历的结点，即最左下的那个结点
    ThreadNode * FirstNode(ThreadNode * p)
    {
        
    	while(p->ltag==0) p=p->lchild;
    	return p;
    }
    
    //找到某个结点的后继节点
    ThreadNode * NextNode(ThreadNode * p)
    {
        
    	if(p->rtag==1) return p->rchild;
    	else if(p->rchild==0) return FirstNode(p->rchild); //返回右子树最左下的那个结点
    }
    
    void Inorder(ThreadTree * T)
    {
        
        for(ThreadNode * p=FirstNode(T)；p!=NULL；p=NextNode(p)) //先找到第一个结点，然后不断的找其后继
            visit(p);
    }

逆向中序遍历：从最后一个结点开始不断遍历其前驱即可。

###### 6）平衡二叉树 ######

//平衡二叉树结点
    typedef struct AVLNode
    {
        
    	int ket; //数据域
    	int balance; //平衡因子
    	struct AVLNode * lchild,* rchild;
    }* AV

//LL平衡旋转（右旋）
    f->lchild=p->rchild;
    p->rchild=f;
    gf->lchild/rchild=p;

#### 5、图 ####

##### 1.图的存储结构 #####

###### 1）数组表示法 ######

//-----图的组（邻接矩阵）存储表示-----
    #define INFINITY INT_MAX //最大值∞
    #define MAX_VERTEX_NUM 20 //最大的顶点个数
    typedef enum {
        DG,DN,UDG,UDN}GraphKind; //{有向图（Digraph），有向网（DiNet），无向图(UniDigraph),无向网} 
    typedef struct ArcCell{
        
        VRType adj; //VRType是顶点关系类型。对无权图，用1或者0表示相邻与否；对带权图，则为权值类型。
        InfoType *info; //该弧相关信息的指针
    }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    typedef struct{
        
        VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
        AdjMatrix arcs; //邻接矩阵
        int vexnum,arcnum; //图的当前顶点数与边数
        GraphKind kind; //图的种类标志
    }MGpraph

###### 2）邻接表 ######

//---------图的邻接表存储表示-----------
    #define MAX_VERTEX_NUM 20
    typedef struct ArcNode{
        
        int adjvex; //该弧指向的顶点的位置
        struct ArcNode *nextarc; //指向下一条弧的指针
        InfoType *info; //该弧相关信息的指针
    }ArcNode;
    typedef struct VNode{
        
        VertexType data; //顶点信息
        ArcNode *firstarc;  //指向的一条依附该顶点的弧的指针
    }VNode，AdjList[MAX_VERTEX_NUM]；
    typedef struct{
        
    	AdjList vertices;
    	int vexnum,arcnum; //图的当前顶点数和弧数
    	int kind; //图的种类
    }

###### 3）十字链表法 ######

十字路口有方向，十字链表法是专门针对有向图设计的，旨在解决有向图用邻接表法找不到入度的这个问题。顶点结点包含三个域，数据域，firstin和firstout域分别指向第一个入度边，第一个出度边；边结点有五个域，尾域头域分别表示该弧的弧尾和弧头，链域tlink指向弧尾相同的下一条弧，hlink指向弧头相同的下一条弧，这样弧头相同的弧就在一个链表上，弧尾相同的弧也在一个链表上，info域指向该弧的相关信息。

##### 2.图的遍历 #####

###### 1）广度优先遍历 ######

void BFSTraverse(Graph G,Status(*visit)(int v)){
        
        //按广度优先搜索遍历非递归遍历图G，使用辅助队列和访问标志数组visited
        for(v=0;v<G.vexnum;v++)	 visited[v]=FALSE;
        InitQueue(Q);
        for(v=0;v<G.vexnum;++v)
            if(!visited[v]){
        
            	visited[v]=True;
            	visit(v);
                EnQueue(Q,v);
                while(!QueueEmpty(Q)){
        
                    DeQueue(Q,u);
                    for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
                          if(!visited[w]){
        
                              visited[w]=True;
            				visit(w);
                    		EnQueue(Q,w);
                          } //if
                    } //while
            } //if
    } //BFSTraverse

###### 2）深度优先遍历 ######

void DFSTraverse(Graph G,Statues(* Visit)(int v)){
        
        for(v=0;v<G.vexnum;++v) visited[v]=FALSE;
        for(v=0;v<G.vexnum;++v){
        
            if(!visited[v]) DFS(G,v);
        }
    }
    void DFS(Graph G,int v){
        
        if(!visited[v]) {
        
            visit(G,v);
            visted[v]=TRUE;
        } //if
        while(w=FirstAdjVetex(G,v);w>=0;w=NextAdjVetex(G,v,w)){
        
            if(!visited[w]){
        
            	DFS(G,w);
            } //if 
        } //while
    } //DFSTraverse

##### 3.最小生成树（prim算法） #####

//prim算法的思想：选择一个初始顶点，把它加入辅助数组，计算该顶点到其他顶点的代价，选择其中最小代价对应点加入辅助数组，扫描加入新的顶点有没有使其到各个顶点的代价变化，并更新代价数组；重复进行以上步骤，知道所有顶点都已经加入了辅助数组
    //记录顶点集U到V-U的代价最小的边的辅助数组
    struct{
        
        VertexType adjvex;
        VRType lowcost;
    }closedge[MAX_VERTEX_NUM];
    
    void MiniSpanTree_PRIM(MGraph G,VetexType u){
        
        //用prim算法从第v个顶点出发构造网的最小生成树T，并输出最小生成树的各条边
      	k=LocateVex(G,u);
        for(j=0;j<G.vexnum;j++) //辅助数组初始化
            if(j!=k) closedge[j]={
        u,G.arcs[k][j].adj}; //{adjvex,lowcost}
        closedge[k].lowcost=0; //初始，U={u}
        for(i=1;i<G.vexnum;++i){
         //选择其余G.vexnum-1个顶点
            k=minimum(closedge);  //求出T的下一个顶点:第k顶点
            printf(closedge[k].adjvex,G.vexs[k]);
            closedge[k].lowcost=0;
            for(j=0;j<G.vexnum;++j)
                if(G.arcs[k][j]).adj<closedge[j].lowcost)
                    closedge[j]={
        G.vexs[k],G.arcs[k][j].adj};
        }
    } //MiniSpanTree

##### 4.最短路径 #####

###### 1）单源最短路径 ######

BFS可用于求不带权的图的单源最短路径（课本上没有）

bool viisted[Max_VeTex_num];
    
    void BFS_Min_Distance(Graph G,int v){
        
        //BFS求无向图的单源最短路径
        for(int i=0;i<G.vexNum;i++){
        
            d[i]=Inifinate; //最短路径大小
            path[i]=-1; //最短路径从哪里过来
        }
        d[v]=0; //起点到自己的距离置为0；
        visited[v]=true;
        EnQueue(Q,v);
        while(!IsEmpty(Q)){
        
            DeQueue(Q,v);
            for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
        
                if(!visited[w]){
        
                    visited[w]=true;
                    EnQueue(Q,w);
                    d[w]=d[v]+1;
                    path[w]=u;
                  }
            }
        }
    }

##### 5.拓扑排序 #####

Status TopologicalOrder(ALGraph G,Stack &T){
        
        //有向网G采用邻接表存储结构，求各顶点事件最早发生时间ve（全局变量）
        //T为拓扑序列顶点栈，S为零入度顶点栈
        //若G无回路，则栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR
        FindInDegree(G,indegree); //对各顶点求入度indegree[0...vernum-1]
        InitStack(S)； //建立并初始化零入度顶点栈
        count=0;ve[0...G.vexnum-1]=0; //初始化
        while(!StackEmpty(S)){
        
            Pop(S,j); Push(T,j);++count; //j号顶点入T栈并计数
            for(p=G.vertices[j].firstarc;p;p->nextarc){
        
                k=p->adjvex; //对j号顶点的每个邻接点的入度减1
                if(--indgree[k]==0) Push(S,k); //若入度减为0，则入栈
                if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info) ;
            }
        }
        if(count<G.vexnum) return ERROR; //该有向图有回路
        else retrun OK;
    }

#### 6、排序 ####

##### 1.插入排序 #####

###### 1）直接插入排序 ######

//直接插入排序，进行增序排序
    void InsertSort(SqlList &L){
        
        //从第2个元素开始，进行i-1轮插入
        for(int i=2;i<=L.length;i++){
        
            //如果待插入元素与之前元素比较已经属于有序，无需操作，否则执行操作
            if(L.r[i].key<L.r[i-1].key){
        
                //复制待插入元素为哨兵
                L.r[0]=L.r[i];
                for(int j=i-1;L.r[0].key<L.r[j].key;j--) //比待插入元素大的都往后移
                        L.r[j+1]=L.r[j];
                L.r[j]=L.r[0];
            } //if
        } //for
    } //InsertSort

###### 2）折半插入排序 ######

void BInsertSort(SeqList &L)
    {
        
          //从第二个元素开始把待排序序列插入到有序序列
        for(int i=2;i<=L.length;i++)
        {
        
            L.r[0]=L.r[i]; 
            int low=1,high=i-1; //从第i-1个元素（有序序列的最后一个元素）开始往前找空
            while(low<=high){
         //当low=high,还执行一次，将mid与low，high指向相同位置，并因此会执行else语句，使high+1位置为待插入元素的位置
                 mid=(low+high)/2;
                 if(L.r[mid].key<L.r[0].key) low=mid+1;
           		 else high=mid-1;
            } //循环结束，high+1为插入位置
            for(int j=i-1;j>high+1;--j) L.r[j+1]=L.r[j];
            L.r[high+1]=L.r[0];
        }
    }

###### 3）希尔排序 ######

//一趟增量为dk的希尔排序
    void ShellSort(SeqList &L,int dk){
        
        for(i=dk+1;i<=L.length;i++){
         //从dk+1个元素开始，把无序子序列的元素插入有序序列
            if(L.r[i]<L.r[i-dk]){
         //当第i个元素比他前面子序列的元素要小，则执行，否则已经有序，无需操作
                L.r[0]=L.r[i]; //复制为哨兵
                for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j-=dk) //比L.r[i]大的元素后移空位置
                    L.r[j+dk]=L.r[j];
                 L.r[j]=L.r[0];
            }
        }
    }

##### 2.交换排序 #####

###### 1）冒泡排序 ######

void BubbleSort(SeqList &L){
        
        for(int i=0;i<L.length;i++){
        
            flag=false; //用来记录一趟冒泡排序是否发生了交换
            for(int j=L.length;j>i;j--){
        
                if(L.r[j-1].key>L.r[j].key) //逆序：前面的比后面的大，则交换
                	{
        
                    	swap(L.r[j-1],L.r[j]);
                		flag=true;
                	}
            }
            if(flag==false) return;
        }
    }

###### 2）快速排序 ######

void QuickSort(ElemType A[],int low,int high)
    {
        
        if(low<high) //递归跳出条件
        {
        
            //partition()就是划分操作，将表A[low...high]划分为两个子表
            int pivotopos=partition(A,low,high); //划分
            QuickSort(A,low,privotopos-1); //依次对两个子表进行递归排序
            QuickSort(A,privotopos+1,high);
        }
    }

int Partition（SqlList &L,int low,int high){
        
        L.r[0]=L.r[low];
        privotkey=L.r[low].key;//将当前表中的第一个元素设置为枢轴值，将表进行划分
        while(low<high){
         //循环跳出条件
            while(low<high&&L.r[high].key>=privotkey) --high;
            L.r[low]=L.r[high];
            while(low<high&&L.r[low].key<=prvotkey) ++low;
            L.r[high]=L.r[low];
        }
        L.r[low]=L.r[0]; //枢轴纪录到位
        return low; //返回枢轴位置
    }

##### 3.选择排序 #####

###### 1）简单选择排序 ######

void SeclectSort(SeqList &L){
        
        for(int i=1;i<L.length;i++){
         //让i从1到n-1进行n-1趟选择排序（最后一个位置不用再选择了）
            min=i;
            for(j=i+1;j<L.length;j++){
        
                if(L.r[j].key<L.r[min].key)
                	min=j;
            }
            if(min!=i) swap(L.r[i]=L.r[min]);
        }
    }

###### 2）堆排序 ######

void HeapSort(HeapType &H)
    {
        
        //对顺序表进行堆排序
        for(i=H.length/2;i>0;--i) //从最后一个非叶子结点开始建立堆
            HeapAdjust(H,i,H.length); 
        for(i=H.length;i>1;--i){
        
             //...输出堆顶元素
             H.r[1]<-->H.r[i];  //将堆顶记录和最后一个记录交换
             HeapAdjust(H,1,i-1); //重新建堆
        }
    }
    
    void HeapAdjust(HeapAdjust &H,int s,int m){
         //调整为大顶堆
        rc=H.r[s]; //暂存堆顶元素
        for(j=2*s;j<=m;j*=2){
         //从上到下调整。让j指向堆顶左孩子，对其子树依次执行循环体（j*=2）
            if(j<m&&LT(H.r[j].key,H.r[j+1].key)) ++j; //如果左孩子小于右孩子，那么把j指右孩子，如果j==m，说明j已经是最后一个结点了，没有右孩子
            if(!LT(rc.key,H.r[j].key)) break; //比较堆顶与孩子结点大小，如果堆顶已经比孩子大，break；
            H.r[s]=H.r[j];  //否则，把堆顶置换为孩子结点元素 
            s=j; //对其子树进行判断调整，以调整由于之前置换导致的子树下坠情况
        }
        H.r[s]=rc; //把暂存的元素插入最后空出的位置
    }

##### 4.归并排序 #####

void Merge(RcdType SR[],RcdType TR[],int i,int m,int n){
        
        //两个有序子序列的归并，SR中存待归并数据，TR是数据暂存的临时空间，i是SR第一个序列开始，m是第1个子序列结尾位置，n是第2个子序列结束位置
        for(j=m+1,k=i;i<=m&&j<=n;++k){
        //j指向第二个子序列开始位置,k指向i指针对应位置（即让TR插入元素的起始位置与SR相同）
            if(LQ(SR[i].key,SR[j].key)) TR[k]=SR[i++];
            else TR[k]=SR[j++];
        }
        //判断哪个子序列还有剩余元素，全部复制到TR
        if(i<=m) TR[k...n]=SR[i...m]; //伪代码，可以用while循环实现
        if(j<=n) TR(k...n)=SR[j...n];
    }
    
    void MSort(RcdType SR[],RcdType &TR1[],int s,int 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(SqlList &L){
        
        Msort(L.r,L.r,1,L.length);
    }
    
            if(flag==false) return;
        }
    }

##### 5.快速排序 #####