常用算法总结（纯代码版）

置顶 | 发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 37k | 阅读时长 ≈ 34 分钟

线性表

顺序表

定义

1
2
3
4
5
6
7
8
#include 
using namespace std;
typedef int Elemtype_S;
//顺序表
struct SeqList{
    Elemtype_S *data;
    int len;
}

逆置

1
2
3
4
5
6
7
8
9
//逆置
void Reverse(SeqList &L){
    Elemtype_S temp;
    for(int i=0;i2;i++){
        temp = L.data[i];
        L.data[i] = L.data[L.len-i-1];
        L.data[L.len-i-1] = temp;
    }
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//删除所有介于s和t之间的结点
bool Delete_s_t(SeqList &L,Elemtype_S s,Elemtype_S t){
    if(L.len==0||s>=t)
        return false;
    int count = 0;
    for(int i=0;i
        if(L.data[i]>s&&L.data[i]
            count++;
        else
            L.data[i-count] = L.data[i];
    }
    L.len -= count;
    return true;
}

逆置的应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//将a1,a2...am,b1,b2...bn交换为序列b1,b2..bn,a1,a2...am
void Reverse(SeqList &L,int left,int right){
    if(left>=right||right>L.len) return;
    int mid = (left+right)/2;
    for(int i=0;i
        Elemtype_S temp = L.data[i+left];
        L.data[left+i] = L.data[right-i];
        L.data[right-i] = temp;
    }
}
void Exchange(Seqlist &L,int m,int n){
    Reverse(L,0,m+n-1);
    Reverse(L,0,n-1);
    Reverse(L,n,m+n-1);
}

链表

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include 
using namespace std;
typedef int Elemtype_L;
//链表
struct LinkNode{
    Elemtype_L data;	//数据域 
    LinkNode *next;
};
struct LinkList{
    //带头节点以及头尾指针的单链表
    LinkNode *head;
    LinkNode *tail;
    int len;
};
//静态链表
typedef struct Node{
    Elemtype_L data;
    int next;
}LinkNode[size];

初始化

1
2
3
4
5
6
//创造一个空的线性表
void InitList(LinkList &L){
    L.len = 0;
    L.head = L.tail = new LinkNode;		//(LinkNode*)malloc(sizeof(LinkNode))
    L.head->next = NULL;
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
//从第一个位置起查找与e匹配的数据元素，若存在则返回该数据元素的位置
int LocateElem(LinkList &L,Elemtype_L &e,
    bool(*compare)(Elemtype_L &a,Elemtype_L &b)){		//函数指针
    int i = 1;
    LinkNode *p = L.head->next;
    while(p&&!compare(p->data,e)){
        i++;
        p = p->next;
    }
    if(i)
        return i;
    return 0;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//在单链表的第i个数据元素之前插入新的数据元素
bool ListInsert(LinkList &L,int i,Elemtype_L &e){
    if(i<1||i>L.len)
        return false;
    int k = 1;
    LinkNode *p=L.head,*q;
    q = new LinkNode;
    q->data = e;
    while(k
        p = p->next;
        k++;
    }	//p从头节点开始，因此指向第i-1个结点
    q->next = p->next;
    p->next = q;
    L.len++;
    return true;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//在单链表中删除第i个数据元素并用数据变量e返回其值
bool ListDelete(LinkList &L,int i,Elemtype_L &e){	//删除节点数据也可以通过函数返回值返回
    if(i<1||i>L.len)
        return false;
    LinkNode *p=L.head,*q;
    int k = 1;
    while(k
        p = p->next;
        k++;
    }
    q = p->next;
    p->next = q->next;
    if(q==L.tail)	//如果删除是尾结点需要更改尾指针
        L.tail = p;
    e = q->data;
    delete q;	//delete释放指针指向的内存而不是指针本身占有的内存
    q = NULL;	//在delete后要习惯加上此操作防止出现野指针
    L.len--;	//注意头节点带长度信息，需要更新
    return true;
}

栈和队列

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include 
using namespace std;
typedef int Elemtype_s;
//顺序栈
struct SqStack{
    Elemtype_s *base;
    int top;
    int size;
};
//初始化
void InitStack(SqStack &s,int m){
    s.top = 0;	//有些教材设置成-1，注意区分
    s.base = new Elemtype_s[m];
    s.size = 0;
}
//销毁栈
void DestroyStack(SqStack &s){
    delete[] s.base;
    s.top = 0;
    s.size = 0;
}
//判空
bool StackEmpty(SqStack &s){
    return s.top==0;
}
//返回栈中元素个数
int StackLength(SqStack &s){
    return s.top;
}
//获取栈顶元素
bool GetTop(SqStack &s,Elemtype_s &e){
    if(StackEmpty(s))
        return false;
    e = s.base[s.top-1];
    return true;
}
//入栈
void PushStack(SqStack &s,Elemtype_s e){
    if(s.top>=s.size){	//栈满的情况，需要额外的申请空间
        Elemtype_s *newbase;
        newbase = new Elemtype_s[s.size+10];
        for(int j=0;j
            newbase[j] = s.base[j];
        delete[] s.base;
        s.base = newbase;
        s.size = s.size+10;
    }
    s.base[s.top++] = e;
}
//出栈
bool PopStack(SqStack &s,Elemtype_s &e){
    if(StackEmpty(s))
        return false;
    e = s.base[--s.top];
    return true;
}

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include 
using namespace std;
typedef int Elemtype_q;
//队列的链式表示
struct LinkNode{
    Elemtype_q data;
    LinkNode *next;
};
struct LinkQueue{
    LinkNode *front;
    LinkNode *rear;		//就是一个带头尾指针的单链表
};
//初始化
void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = new LinkNode;
    Q.front = NULL;
}
//清空队列
void ClrarQueue(LinkQueue &Q){
    LinkNode *p;
    while(Q.front->next!=NULL){
        p = Q.front->next;
        Q.front->next = p->next;
        delete p;	//这里保留了队列的头节点，和后面的销毁队列不同
    }
    Q.rear = Q.front;
}
//销毁队列
void DestroyQueue(LinkQueue &Q){
    ClrarQueue(Q);
    delete Q.front;
    Q.front = Q.rear = NULL;	//防止野指针
}
//队列判空
bool EmptyQueue(LinkQueue &Q){
    return Q.front==Q.rear;
}
//队列中元素个数
int LengthQueue(LinkQueue &Q){
    LinkNode *p=Q.front->next;
    int i=1;
    while(p!=NULL){
        i++;
        p=p->next;
    }
    if(i)
        return i;
    return 0;
}
//取队头元素的值
Elemtype_q GetHead(LinkQueue &Q){
    return Q.front->next->data;
}
//取队尾元素的值
Elemtype_q GetLast(LinkQueue &Q){
    return Q.rear->data;
}
//入队
void EnQueue(LinkQueue &Q,Elemtype_q e){
    LinkNode *p;
    p = new LinkNode;
    p->data = e;
    Q.rear->next = p;
    p->next = NULL;
    Q.rear = p;
}
//出队
bool DeQueue(LinkQueue &Q,Elemtype_q &e){
    if(EmptyQueue(Q))
        return false;
    LinkNode *p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(p == Q.rear)
        Q.rear = Q.front;
    delete p;
    return true;
}

stack&queue 头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include 
#include 
#include 
using namespace std;
//stack  name
//queue  name
int main(){
    stack <int> s;
    queue <int> q;
    for(int i=0;i<5;i++){
        s.push(i);	//入栈
        q.push(i);	//入队
    }
    s.pop();q.pop();	//注意pop操作没有返回值,s弹出4，q弹出0
    cout<<"top s:"<endl;	//输出3
    cout<<"front q:"<endl;	//输出1
    cout<<"back q:"<endl;	//输出4
    //此外两者都有empty()和size()操作
    //比较难受的是不能取第i个位置的值
}

树

二叉链表

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include 
using namespace std;

#define Maxsize 100
typedef char Elemtype_t;

struct BTNode{
    Elemtype_t data;
    BTNode *lchild;
    BTNode *rchild;
    //int height;	//height主要是为了后面的AVL树服务
};
//二叉链表初始化
void InitBinaryTree(BTNode* &T){
    T = NULL;
}
//销毁二叉树
void DestroyBinaryTree(BTNode* &T){
    if(T){
        DestroyBinaryTree(T->lchild);
        DestroyBinaryTree(T->rchild);
        delete T;
    }
    T = NULL;
}

遍历

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//先序遍历二叉树(递归)
void PreorderTraverse(BTNode* T,void(*visit)(Elemtype_t &e)){
    if(T){
        visit(T->data);
        PreorderTraverse(T->lchild,visit);
        PreorderTraverse(T->rchild,visit);
    }
}
//先序遍历二叉树(非递归)
#include 
void PreorderTraverse2(BTNode* T,void(*visit)(Elemtype_t &e)){
    stack  s;
    BTNode *p=T;
    while(p||!s.empty()){
        while(p){
            visit(p->data);
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty()){
            p = s.top();
            s.pop();
            p=p->rchild		//此处无需判断p是否有右孩子，若无则有置空p指针继续出栈的效果
        }
    } 
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//中序遍历二叉树(递归)
void MidorderTraverse(BTNode* T,void(*visit)(Elemtype_t &e)){
    if(T){
        PreorderTraverse(T->lchild,visit);
        visit(T->data);
        PreorderTraverse(T->rchild,visit);
    }
}
//中序遍历二叉树(非递归)
void MidorderTraverse2(BTNode* T,void(*visit)(Elemtype_t &e)){
    stack s;
    BTNode *p = T;
    while(p||!s.empty()){
        while(p){
            s.push(p);
            p = p->lchild;
        }
        if(!s.empty()){
            p = s.top();
            s.pop();
            visit(p->data);
            p = p->rchild;
        }
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//后序遍历二叉树(递归)
void PostorderTraverse(BTNode* T,void(*visit)(Elemtype_t &e)){
    if(T){
        PreorderTraverse(T->lchild,visit);
        PreorderTraverse(T->rchild,visit);
        visit(T->data);
    }
}
//后序遍历二叉树(非递归)
//不同于先序和中序，后续的非递归要设置一个pre指针来指示是否已经访问过右子树
void PostorderTraverse2(BTNode* T,void(*visit)(Elemtype_t &e)){
    stack  s;
    BTNode *p=T,*pre=NULL;
    while(p||s.empty()){
        while(p){
            s.push(p);
            p = p->lchild;
        }
        if(!s.empty()){
            p = s.top();
            if(p->rchild!=pre){
                p = p->rchild;
                // s.push(p);		//这两步加不加都一样，但有助于理解
                // p = p->lchild;
            }
            else{
                visit(p->data);
                pre = p;
                s.pop();
                p = NULL;	//将p置空，不能漏！
            }
        }
    }
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//层序遍历
void LevelOrder(BTNode* T,void(*visit)(Elemtype_t &e)){
    queue  q;
    BTNode *p;
    q.push(T);
    while(!q.empty()){
        p = q.front();
        q.pop();
        visit(p->data);
        if(p->lchild!=NULL)
            q.push(p->lchild);
        if(p->rchild!=NULL)
            q.push(p->rchild);
    }
}

深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//求二叉树的深度（递归）
int BinaryTreeDepth(BTNode* &T){
    if(T==NULL)
        return 0;
    int h1,h2;
    h1=BinaryTreeDepth(T->lchild);
    h2=BinaryTreeDepth(T->rchild);
    return h1>h2?h1+1:h2+1;
}
//求二叉树的深度(非递归)
//rear始终指向队列中的最后一个结点
//front指向当前访问结点，last指向当前访问结点所在层的最后一个结点
int BinaryTreeDepth2(BTNode* T){
    int front,rear;
    front=rear=-1;
    int last,level;
    last=level=0;
    BTNode *Q[Maxsize],*p;
    Q[++rear]=T;
    while(front
        p = Q[++front];
        if(p->lchild!=NULL)
            Q[++rear]=p->lchild;
        if(p->rchild!=NULL)
            Q[++rear]=p->rchild;
        if(front==last){	//front和last相等，即当前层所有结点已全部入队，last指向下一层最后一个结点
            last = rear;
            level++;
        }
    }
    return level;
}
//同理，此方法也可用于解决二叉树的宽度问题

构建二叉树

先序 + 中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//按先序和中序次序建立二叉树
//前提是二叉树中节点的数据不重复
void CreateBinaryTree2(BTNode* &T,Elemtype_t ch1[],Elemtype_t ch2[],
                        int low,int high,int &k){
    int i;
    if(low>high)
        T = NULL;
    else{
        T = new BTNode;
        T ->data = ch1[k];
        for(i=low;i<=high&&ch2[i]!=ch1[k];i++);< span>
        if(ch2[i] == ch1[k])
        {
            k++;	//这个k没有为题，注意下面两行的递归k值实际是不一样的
            CreateBinaryTree2(T->lchild,ch1,ch2,low,i-1,k);
            CreateBinaryTree2(T->rchild,ch1,ch2,i+1,high,k);
        }
    }
}
//另解
//一般都会给出两个序列，下标搞不清楚的时候画一画
//推荐这种写法，容易记
BTNode* CreateBinaryTree3(Elemtype_t ch1[],Elemtype_t ch2[],int preL,int preR,
                          int inL,int inR){
	if(preL>preR)	return NULL;
    BTNode* T = new BTNode;
    T->data = ch1[preL];
    for(int i=inL;i
    int num_left = i-inL;
    T->lchild = CreateBinaryTree3(ch1,ch2,preL+1,preL+num_left,inR,i-1);
    T->rchild = CreateBinaryTree3(ch1,ch2,preL+num+left+1,preL,i+1,inR);
    return T;
}

中序 + 后序

1
2
3
4
5
6
7
8
9
10
11
BTNode* CreateBinaryTree4(Elemtype_t ch1[],Elemtype_t ch2[],int postL,int postR,
                          int inL,int inR){
    if(postL>postR) return NULL;
    BTNode* T = new BTNode;
    T->data = ch1[postR];
    for(int i=inL;i
    int num_left = i-inL;
    T->lchild = CreateBinaryTree4(ch1,ch2,postL,postL+num_left-1,inL,i-1);
    T->rchild = CreateBinaryTree4(ch1,ch2,postL+num_left,postR-1,i+1,inR);
    return T;
}

中序 + 层序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//中序+层序
Node* Create(int Layer[],int num,int inL,int inR){
if(num==0){
	return NULL;//子树数量为0时直接返回
}
Node* root=(Node*)malloc(sizeof(Node));
//新建一个新的结点，用来存放当前二叉树的根节点
int Left[1000]={0};
int Right[1000]={0};//存放左右子树的层序遍历序列
int Lnum=0,Rnum=0,k;//存放左右子树的层序遍历元素数量
int i,j,isLeft;
root->data=Layer[0];//新结点的数据域为根结点的值
for(k=inL;k0];k++)
for(i=1;i
	isLeft=0;
	for(j=inL;j
		if(Layer[i]==in[j]){
			isLeft=1;
			break;
		}
	}
	if(isLeft){
		Left[Lnum++]=Layer[i];
	}else{
		Right[Rnum++]=Layer[i];
	}
}//区分层序遍历中的左右子树
//返回左子树的根节点地址，赋值给root的左指针
root->lchild=Create(Left,Lnum,inL,k-1);
//返回右子树的根节点地址，赋值给root的右指针
root->rchild=Create(Right,Rnum,k+1,inR);
return root;
}

打印 x 的祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//打印结点值为x的所有祖先节点
//采用后序遍历的方法，当访问到x时栈中元素即为x的祖先节点
//此方法可以拓展到找p和q最近的公共祖先节点
void Search_ancestor(BTNode* T,Elemtype_t &x,void(*visit)(Elemtype_t &e)){
    BTNode *p=T,*pre=NULL;
    stack  S;
    while(p||!S.empty()){
        if(p){
            if(p->data!=x){
            S.push(p);
            p = p->lchild;}

            else {
                while(!S.empty()){
                p = S.top();
                visit(p->data);
                S.pop();}
                return;}
        }
        else{
            p=S.top();
            if(p->rchild&&p->rchild!=pre)
                p = p->rchild;
            else{
                S.pop();
                pre = p;
                p=NULL;}
        }
    }
    return;
}

查找指定结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//返回二叉树中元素值为e的结点指针
BTNode* Locate(BTNode* &T,Elemtype_t &e){
    if(T==NULL||T->data==e)
        return T;
    BTNode *q;
    q = Locate(T->lchild,e);
    if(q)  
        return q;	//点睛之笔，减少了不必要的递归操作
    q = Locate(T->rchild,e);
    return q;
}
//返回节点p的双亲结点
BTNode* Parent(BTNode* &T,BTNode* &p)
{
    if(T==NULL||T==p)
        return NULL;
    if(T->lchild==p||T->rchild==p)
        return T;
    BTNode *q;
    q = Parent(T->lchild,p);
    if(q)
        return q;
    q = Parent(T->rchild,p);
    return q;
}

其他操作

交换二叉树的左右节点

1
2
3
4
5
6
7
8
9
10
11
//交换二叉树的左右节点
BTNode* BinaryTreeSwap(BTNode* &T){
    if(T){
        BinaryTreeSwap(T->lchild);
        BinaryTreeSwap(T->rchild);
        BTNode *temp;
        temp = T->lchild;
        T->lchild = T->rchild;
        T->rchild = temp;
    }
}

判断完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//判断二叉树是否是完全二叉树
//利用层次遍历，如果在非空结点之前有空结点，则二叉树不满
bool Iscomplete(BTNode* T){
    if(T==NULL) return 1;
    queue q;
    BTNode *p;
    q.push(T);
    while(!q.empty()){
        p = q.front();
        q.pop();
        if(p){
            q.push(p->lchild);
            q.push(p->rchild);
        }
        else{
            while(!q.empty()){
                p = q.front();
                if(!p) return 0;
                q.pop();
            }
        }
    }
    return 1;
}

复制一颗二叉树

1
2
3
4
5
6
7
8
9
10
11
//复制一颗二叉树
BTNode* CopyBinaryTree(BTNode* &T){
    if(T==NULL)
        return NULL;
    BTNode *p;
    p = new BTNode;
    p->data = T->data;
    p->lchild = CopyBinaryTree(T->lchild);
    p->rchild = CopyBinaryTree(T->rchild);
    return p;
}

统计叶结点个数

1
2
3
4
5
6
7
8
9
//统计树的叶结点个数
int CountLeaf(BTNode* &T,int &n){
    if(T){
        CountLeaf(T->lchild,n);
        CountLeaf(T->rchild,n);
        if(!T->lchild&&!T->rchild)
            n++;
    }
}

二叉搜索树 (BST)

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//二叉搜索树动态查找
BSTNode* BST_Find2(BSTNode *T,Elemtype_t x){
    while(T){
        if(x>T->data)
            T = T->rchild;
        if(xdata)
            T = T->lchild;
        else
            break;
    }
    return T;
}
//查找最小元素
BSTNode* BST_FindMin(BSTNode *T){
    if(T)
        while(T->lchild)
            T=T->lchild;
    return T;
}
//查找最大元素
BSTNode* BST_FindMax(BSTNode *T){
    if(T)
        while(T->rchild)
            T=T->rchild;
    return T;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//删除
//如果左子树和右子树均存在，取右子树中最小的结点替换，否则取左（右）子树第一个节点替换
BSTNode* Delete_BSTNode_x(BSTNode* &T,Elemtype_t x){
    BSTNode *tmp;
    if(!T)
        cout<<"要删除的元素未找到！"<<endl;
    else{
        if(xdata)
            T->lchild=Delete_BSTNode_x(T->lchild,x);
        else if(x>T->data)
            T->rchild=Delete_BSTNode_x(T->rchild,x);
        else{
            if(T->lchild&&T->rchild){
                tmp = BST_FindMin(T->rchild);
                T->data=tmp->data;
                T->rchild=Delete_BSTNode_x(T->rchild,T->data);
            }
            else{
                tmp = T;
                if(!T->lchild)			//只有右孩子或孩子结点
                    T = T->rchild;
                else T = T->lchild;		//只有左孩子
                delete tmp;
            }
        }
    }
    return T;
}

平衡二叉树 (AVL)

平衡二叉树的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include 
#include "BTree.h"
using namespace std;
typedef BTNode AVLNode;
#define max(a,b) a>b?a:b

AVLNode* SingleLeftRotation(AVLNode* &T);
AVLNode* DoubleLeftRightRotation(AVLNode* &T);
AVLNode* SingleRightRotation(AVLNode* &T);
AVLNode* DoubleRightLeftRotation(AVLNode* &T);
int GetHeight(AVLNode *T){
    if(T==NULL)	return 0;
    else return T->height;
}
//平衡二叉树的插入
AVLNode* AVL_Insert(AVLNode* &T,Elemtype_t e){
    if(!T){
        T = new AVLNode;
        T->data = e;
        T->height = 1;
        T->lchild = T->rchild =NULL;
    }	
    else if(edata){
        T->lchild = AVL_Insert(T->lchild,e);
        //如果需要左旋
        if(GetHeight(T->lchild)-GetHeight(T->rchild) == 2){
            if(elchild->data)
                T=SingleLeftRotation(T);	//左单旋
            else
                T=DoubleLeftRightRotation(T);	//左右双旋
        }
    }
    else if(e>T->data){
        T->rchild = AVL_Insert(T->rchild,e);
        //如果需要右旋
        if(GetHeight(T->lchild)-GetHeight(T->rchild) == -2){
            if(e>T->rchild->data)
                T=SingleRightRotation(T);	//右单旋
            else
                T=DoubleRightLeftRotation(T);	//右左双旋
        }
    }
    //更新树高
    T->height = max(GetHeight(T->lchild),GetHeight(T->rchild))+1;
    return T;
}
AVLNode* SingleLeftRotation(AVLNode* &T){
    BTNode* tmp;
    tmp = T->lchild;
    T->lchild = tmp->rchild;
    tmp->rchild = T;
    T->height = max(GetHeight(T->lchild),GetHeight(T->rchild))+1;
    tmp->height = max(GetHeight(tmp->lchild),GetHeight(tmp->rchild))+1;
    return tmp;
}
AVLNode* SingleRightRotation(AVLNode* &T){
    BTNode* tmp;
    tmp = T->rchild;
    T->rchild = tmp->lchild;
    tmp->lchild = T;
    T->height = max(GetHeight(T->lchild),GetHeight(T->rchild))+1;
    tmp->height = max(GetHeight(tmp->lchild),GetHeight(tmp->rchild))+1;
    return tmp;
}
AVLNode* DoubleLeftRightRotation(AVLNode* &T){
    T->lchild = SingleRightRotation(T->lchild);
    T = SingleLeftRotation(T);
    return T;
}
AVLNode* DoubleRightLeftRotation(AVLNode* &T){
    T->rchild = SingleLeftRotation(T->rchild);
    T = SingleRightRotation(T);
    return T;
}

其他操作

判断是否为平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//暴力解法是对每个结点计算左右子树高度求平衡因子
//在后续遍历时保存在左右子树的信息，可以边遍历边判断
bool IsBalanced(BTNode* T,int* depth){
    if(T==NULL){
        *depth = 0;
        return true;
    }
    int nLeftDepth, nRightDepth;
    bool bleft = IsBalanced(T->lchild,&nLeftDepth);
    bool bright = IsBalanced(T->rchild,&nRightDepth);
    if(bleft&&bright){
        int diff = nLeftDepth - nRightDepth;
        if(diff<1&&diff>-1){
            *depth = 1 + (nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);
            return true;
        }
    }
    return false;
}

堆 (优先队列)

大根堆的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct HNode{
    Elemtype_h *data;
    int size;
    int capacity;
};
typedef Heap MaxHeap;
typedef Heap MinHeap;

MaxHeap InitHeap(int maxsize){
    MaxHeap H = new HNode;
    H->size = 0;
    H->capacity = maxsize;
    H->data[0] = MAXDATA;
    return H;
}

大根堆的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//大根堆的插入
//从下往上寻找合适的位置，对路径上的结点做下移
bool IsFull(MaxHeap H){
    return H->size==H->capacity;
}
bool Insert(MaxHeap &H,Elemtype_h e){
    if(IsFull(H)) return 0;
    int i=++H->size;
    for(;H->data[i/2]2){
        H->data[i]=H->data[i/2];
    }
    H->data[i]=e;
    return 1;
}

大根堆删除最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//大根堆删除最大值
//将最后一个元素从上往下寻找合适的位置，对路径上的结点做上移
bool IsEmpty(MaxHeap &H){
    return H->size==0;
}
Elemtype_h Delete_Max(MaxHeap &H){
    if(IsEmpty(H)) return ERROR;
    int parent,child;
    H->data[0]=H->data[1];
    Elemtype_h x=H->data[H->size--];
    for(parent=1;parent*2<=h->size;parent=child){
        child=parent*2;
        if(child+1size&&H->data[child]data[child+1])
            child++;
        if(x>H->data[child]) break;
        else H->data[parent]=H->data[child];
    }
    H->data[parent] = x;
    return H->data[0];
}

二叉树调整为最大堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//二叉树调整为最大堆
void PreDown(MaxHeap &H,int p){
    Elemtype_h x=H->data[p];
    int parent,child;
    for(parent=p;parent*2 <= h->size;parent=child){
        child=parent*2;
        if(child+1size&&H->data[child]data[child+1])
            child++;
        if(x>H->data[child]) break;
        else H->data[parent]=H->data[child];
    }
    H->data[parent]=x;
}
MaxHeap BuildMaxHeap(MaxHeap &H){
    for(int i=H->size/2;i>0;i--)
        PreDown(H,i);
}

哈夫曼树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct HTNode *HuffmanTree;
struct HTNode{
    int weight;
    HuffmanTree lchild;
    HuffmanTree rchild;
}
HuffmanTree Huffman(MinHeap H){
    HuffmanTree T;
    BuildHeap(H);
    for(int i=1;isize;i++){
        T=new HTNode;
        T->lchild=Delete_Min(H);
        T->rchild=Delete_Min(H);
        T->weight = T->left->weight+T->right->weight;
        Insert(H,T->weight);
    }
    return Delete_MIN(H);
}

图

图的存储

邻接矩阵

1
2
3
4
5
6
7
#define MAXV 1000	//邻接矩阵占用内存过大，一般要求顶点数不超过1000
typedef int EdgeType;
typedef struct{
    VetrexType Vex[MAXV];
    EdgeType Edge[MAXV][MAXV];
    int v,a //当前边数和顶点数
}

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//通用版基础定义方法
//顶点表（顶点域、边表头指针）、边表（邻接点域、指针域）
#define MAXV 1000
struct ArcNode{
    int adjvex;	//邻接点下标
    WeightType weight;	//顶点和这个点之间边的权重
    ArcNode *next;
}
struct VNode{
    VertexType data;
    ArcNode *first;
}
struct ALGraph{
    VNode *vertices;
    int v,a;
}
1
2
3
4
5
6
7
//利用vector快速构建
struct Node{
    int v,w;
    Node(int _v,int _w):v(_v),w(_w){}
}
vector Adj[N]
Adj[1].push_back(Node(3,4)) //构造一条从节点1指向节点3的有向边,权重为4

十字链表

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAXV 100
struct ArcNode{
    int tailvex,headvex;
    ArcNode *hlink,*tlink;
} 
struct VNode{
    VertexType data;
    ArcNode *firstin,*firstout;
}
struct GLGraph{
    VNode xlist[MAXV];
    int v,a;
}

* 邻接多重表

图的遍历

1
2
const int MAXV=1000;
const int INF=1000000000;

DFS

  1. 伪代码描述 
1
2
3
4
5
6
void DFS(int u){	//u为起点
    标记u已被访问；
        for(u所能达到的所有未被访问的节点v){
            DFS(v);
        }
}
  1. 邻接矩阵 
1
2
3
4
5
6
7
8
int n,G[MAXV][MAXV]{INF};	//n为当前图的顶点总数
bool vis[MAXV]{false};
void DFS(int u,int depth){
    vis[u]=true;
    for(int v=0;v
        if(vis[v]==false&&G[u][v]!=INF)
            DFS(v,depth+1);
}
  1. 邻接表 
1
2
3
4
5
6
7
8
9
10
11
vector <int> Adj[MAXV];	//和定义中不一样的是，这里压入的数表示其相邻的结点
int n;	
bool vis[MAXV]{false};
void DFS(int u,int depth){
    vis[u]=true;
    for(int i=0;i//两者的区别就在于找邻接点不一样
        int v=Adh[u][i];
        if(vis[v]==false)
            DFS(u,depth+1);
    }
}
  1. 遍历函数 
1
2
3
4
5
void BFSTrave(){	//这个函数是必要的，因为图不一定是连通的，所以一定要判断所有的顶点
    for(int u=0;u
        if(vis[u]==false)
            DFS(u,1);
}

BFS

  1. 伪代码描述 
1
2
3
4
5
6
7
8
9
void BFS(int u){	//u为起点
    将u入队并标记；
        while(队列不为空){
            取出队首元素p(当前节点)；
                for(当前节点p所能到达的所有未被标记的顶点v){
                    将v入队并标记；
                }
        }
}
  1. 邻接矩阵 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n,G[MAXV][MAXV];
bool inque[MAXV];

void BFS(int u){
    queue <int> q;
    q.push(u);
    inque[u]=true;
    while(!q.empty()){
        int p = q.front();
        q.pop();
        for(int v=0;v
            if(inque[v]==false&&G[p][v]!=INF){
                q.push(v);
                inque[v]=true;
            }
        }
    }
}
  1. 邻接表 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector <int> G[MAXV];
bool inque[MAXV];

void BFS(int u){
    queue <int> q;
    q.push(u);
    inque[u]=true;
    while(!q.empty()){
        int p = q.front();
        q.pop();
        for(int i=0;i
            if(inque[i]==false){
                q.push(i);
                inque[i]=true;
            }
    }
}
  1. 遍历函数 
1
2
3
4
5
void BFSTrave(){
    for(int u=0;u
        if(inque[u]==false)
            BFS(q);
}

最短路径

1
2
const int MAXV 1000;	//最大顶点数
const int INF 100000000;	//设置一个很大的值用于表示邻接矩阵中两个节点不连通

Dijkstra

  1. 伪代码描述 
1
2
3
4
5
6
7
8
9
10
11
Dijkstra(G,d[],s){	//G为图，d为源点，s为起点
	初始化
    for(循环n次){
        u = d[u]中最小且未被访问过的点；
        将u标记为已经被访问；
            for(从u出发能到达的所有顶点v){
                if(v未被访问并且以u为中介使d[v]更优)
                    更新d[v]
            }
    }
}
  1. 邻接矩阵 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n,G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV]={false};

void dijkstra(int s){
    fill(d,d+MAXV,INF);
    d[s]=0;
    for(int i=0;i
        int u=-1,MIN=INF;
        for(int j=0;j
            if(vis[j]==false&&d[j]
                u=j;
                MIN=d[j];
            }
        if(u==-1) return;	//这里是不连通的情况
        vis[u]=true;
        for(int v=0;v
            if(vis[v]==flase&&G[u][v]!=INF&&d[u]+G[u][v]
                d[v]=d[u]+G[u][v]
    }
}
  1. 邻接表 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Node {
    int v,dis;
}
vector  G[MAXV];
int d[MAXV];
int vis[MAXV]{false};

void dijkstra(int s){
    fill[d,d+MAXV,INF];
    d[s]=0;
    for(int i=0;i
        int u=-1,MIN=INF;
        if(vis[i]d==false&&[i]
            u=i;
            MIN=d[u];
        }
    if(u==-1) return;
    vis[u]=true;
    for(int j=0;j
        int v=G[u][j].v;
        if(vis[v]d==false&&[u]+G[u][j].dis
            d[v]=d[u]+G[u][j].dis;
    	}
    }
}

  1. 一些改进

    • 保存每个节点最短路径的前驱节点并用递归的方法输出最短路径 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //在更新每个节点的最短距离（d[i]）时记录前驱
    //临界矩阵的部分调整
    pre[MAXV] //保存每个节点的前驱节点
    for(int v=0;v
        if(vis[v]==flase&&G[u][v]!=INF&&d[u]+G[u][v]
            d[v]=d[u]+G[u][v];
            pre[v]=u;
        }
    }
    //此时可以递归的输出最短路径
    void DFS(int s,int v){	//s为起点，v为当前节点
        if(s==v){
            printf("%d\n",s);
            return;
        }
        DFS(s,pre[v]);
        printf("%d\n",v);
    }

    • 多条最短路径问题

      同上只需在更新节点最短路径的时候略作调整进行相应的判断

      可以新增一个数组来表示边权、点权和最短路径条数

      • 给每条边在增加一条边权（二维数组 cost 记录边权，c [] 记录最小花费）
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      for(int v=0;v
          if(vis[v]==false&&G[u][v]!=INF){
              if(d[u]+G[u][v]
                  d[v]=d[u]+G[u][v];
                  c[v]=c[u]+cost[u][v];
                  pre[v]=u;
              }else if(d[u]+G[u][v]==d[v]&&c[u]+cost[u][v]
                  c[v]=c[u]+cost[u][v];
                  pre[v]=u;
              }
          }
      }
      • 给每个顶点增加一个点权（weight [] 记录点权，w [] 为路径上的最大点权和）
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      for(int v=0;v
          if(vis[v]==false&&G[u][v]!=INF){
              if(d[u]+G[u][v]
                  d[v]=d[u]+G[u][v];
                  w[v]=w[u]+weight[v];
                  pre[u]=v;
              }else if(d[u]+G[u][v]==d[v]&&w[u]+weight[v]>w[v]){
                  w[v]=w[u]+weight[v];
                  pre[v]=u;
              }
          }
      }
      • 到达每个顶点的最短路径条数（用 num [] 保存)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      for(int v=0;v
          if(vis[v]==false&&G[u][v]!=INF){
              if(d[u]+G[u][v]
                  d[v]=d[u]+G[u][v];
                  num[v]=num[u];
              }else if(d[u]+G[u][v]==d[v]){
      			num[v]+=num[u];
              }
          }
      }

Bellman-Ford

  1. 伪代码描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    for(i=0;i-1;i++){	//进n-1轮操作，其中n为顶点数
        for(u的所有邻接边u->v){
            if(d[u]+length[u->v]
                d[v]=d[u]+length[u->v]
        }
    }
    //如果图中有负环，则d还能进行更新，返回false
    for(u的所有邻接边u->v){
        if(d[u]+length[u->v]
            return false;
        return true;
    }

  2. 邻接表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    struct Node{
        int v,dis;
    }
    vector  G[MAXV]
    int n;
    int d[MAXV];

    bool Bellman(int s){
        fill(d,d+MAXV,INF);
        d[s]=0;
        for(int i=0;i-1;i++){
            for(int u=0;u
                for(int j=0;j
                    int v=G[u][j].v;
                    int dis=G[u][j].dis;
                    if(d[u]+dis
                        d[v]=d[u]+dis;
                    }
                }
        }
        for(int u=0;u
            for(int j=0;j
                int v=G[u][j].v;
                int dis=G[u][j].dis;
                if(d[u]+dis
                    return false;
            }
    }

SPFA

  1. 伪代码描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    bool SPFA(G,d[],s){
        int Queue[maxn];
        int front=rear=0;
        int inq[maxn];
        初始化inq、num、d;
        源点s入队;
        while(队列非空){
            取出队首元素u;
            for(u的所有邻接边u->v){
                if(d[u]+dis
                    d[v]=d[u]+dis;
                    if(v当前不在队列){
                        v入队；
                        if(v入队次数大于n-1){
                            return;//有可达负环
                        }
                    }
                }
            }
        }
        return;//达到最优
    }

  2. 邻接表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    vector  Adj[MAXN];
    int n,num[MAXN],d[MAXN];
    bool inq[MAXN];

    bool SPFA(int s){
        fill(d,d+MAXN,INF);
        fill(inq,inq+MAXN,false);
        fill(num,num+MAXN,0);
        queue <int> Q;
        Q.push(s);
        inq[s] = true;
        num[s]++;
        d[s] = 0;
        while(!Q.empty()){
            int u = Q.front();
            Q.pop();
            inq[u] = false;
            for(int i=0;i
                int v = Adj[u][i].v;
                int dis = Adj[u][i].dis;
                if(d[u]+dis
                    d[v] = d[u]+dis;
                    if(!inq[v]){
                        Q.push(v);
                        inq[v] = true;
                        num[v]++;
                        if(num[v]>n-1)
                            return false;       //进入队列n次，说明有负环
                    }
                }
            }
        }
        return true;
    }

Floyd

  1. 外代码描述

    1
    2
    3
    4
    枚举所有顶点k
        枚举所有以k为中介点的顶底对i和j
        	if(dis[i][k]+dis[k][j]
                更新dis[i][j]

  2. 邻接矩阵

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //Floyd解决全源最短路径问题
    int n,m;
    int dis[MAXV][MAXV]

    void Floyd(){
    	for(int k=0;k
    		for(int i=0;i
            	for(int j=0;j
            		if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]
            			dis[i][j]=dis[i][k]+dis[k][j];
    }

最小生成树

Prim

  1. 伪代码描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Dijkstra(G,d[],s){	//G为图，d为源点，s为起点
    	初始化
        for(循环n次){
            u = d[u]中最小且未被访问过的点;
            将u标记为已经被访问;
            将d[u]加入最小边权和;
                for(从u出发能到达的所有顶点v){
                    if(v未被访问并且以u为中介使d[v]更优)
                        更新d[v]	//这里的更新与最优与Dijkstra中是不一样的，但整个算法是一致的
                }
        }
    }

  2. 邻接矩阵

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int n,G[MAXV][MAXV];
    int d[MAXV];
    bool vis[MAXV]={false};

    int dijkstra(int s){
        int ans;
        fill(d,d+MAXV,INF);
        d[s]=0;
        for(int i=0;i
            int u=-1,MIN=INF;
            for(int j=0;j
                if(vis[j]==false&&d[j]
                    u=j;
                    MIN=d[j];
                }
            if(u==-1) return;	//这里是不连通的情况
            vis[u]=true;
            ans += d[u];
            for(int v=0;v
                if(vis[v]==flase&&G[u][v]!=INF&&G[u][v]
                    d[v]=G[u][v]	//这就是前面说的不一样的地方
        }
    }

Kruskal

  1. 伪代码描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int Kruskal(){
        for(从小到大枚举所有的边){
            if(当前测试边的顶点在不同的两个连接块中){
                将该测试边加入最小生成树;
                ans+=此边权值;
                最小生成树的边数加1;
                当边数为n-1是结束循环；
            }
        }
    }

  2. 并查集实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    struct Edge{
        int u,v;//边的两个端点编号
        int cost;//边权
    }E[maxn];
    int father[maxn];//并查集数组
    int FindFather(int x){
        int z,a=x;
        while(x!=father[x]){
            x=father[x];
        }
        //路径压缩
        while(a!=father[a]){
            z=a;
            a=father[a];
            father[z]=x;
        }
        return x;
    }
    int Kruskal(int n,int m){//参数n为顶点个数，m为图的边数，函数返回边权之和
        int ans=0,NumEdge=0;//ans为所求边权之和，NumEdge为当前生成树的边数
        int i;
        int faU,faV;
        //查并集初始化
        for(i=1;i<=n;i++){< span>
            father[i]=i;
        }
        //按边权大小排序
        for(i=0;i
            faU=findFather(E[i].u);
            faV=findFather(E[i].v);//查询测试边的两个端点所在集合的根节点
            if(faU!=faV){//如果不在一个集合内
                father[faU]=faV;//合并集合，把测试边加入最小生成树中
                ans+=E[i].cost;//边权之和计算
                NumEdge++;//当前生成树的边数加一
                if(NumEdge==n-1){
                    break;//边数等于顶点数减一时结束算法
                }
            }
        }
        if(NumEdge!=n-1){
            return -1;//无法连通时返回-1
        }else{
            return ans;//返回最小生成树的边权之和
        }
    }

拓扑排序

  1. 邻接表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    vector<int> G[MAXN];
    int n,m,inDegree[MAXN];
    bool topologicalSort(){
        int num = 0;
        queue<int> q;
        for(int i=0;i
            if(inDegree[i] == 0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i=0;i
                int v = G[u][i];
                inDereee[v]--;
                if(inDegree[v] == 0){
                    q.push(v);
                }
            }
            G[u].clear();
            num++;
        }
        if(num == n) return true;
        else return false;
    }

* 关键路径

查找

顺序查找

1
2
3
4
5
6
int SeqSearch(SeqList L,Elemtype key){
    int i = L.length;
    L.data[0] = key;	//哨兵
    for(;L.data[i]!=key;i--)
    return i;
}

折半查找

1
2
3
4
5
6
7
8
9
10
int BinarySearch(SeqList L,Elemtype key){
    int low=1,high=L.length;
    while(low//注意和快排找位置的区别
        int mid=(low+high)/2;
        if(key==L.data[mid]) return mid;
        else if(key>L.data[mid]) low=mid+1;
        else high=mid-1;
    }
    return 0;
}

排序

插入排序

直接插入排序

1
2
3
4
5
6
7
8
9
void InsertSort(Elemtype A[],int n){
    for(int i=2;i<=n;i++)< span>
        if(A[i]-1]){
            A[0]=A[i];
            for(int j=i-1;A[j]>A[0];j--)
                A[j+1]=A[j];
            A[j+1]=A[0];
        }
}

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//折半插入排序
void Binary_InsertSort(Elemtype A[],int n){
    for(int i=2;i
        if(A[i]-1]){
            A[0]=A[i];
            int low=1,high=i-1;
            //注意此处为寻找有序表中第一个大于A[0]元素的位置，当low=high找到
            while(low
                int mid=(low+high)/2;
                if(A[mid]>x) high=mid;
                else low=mid+1
            }
            for(j=i-1;j>=high;--j)
                A[j+1]=A[j];
            A[high]=A[0];
        }
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
//希尔插入排序
void ShellSort(Elemtype A[],int n){
    for(int dk=n/2;dk>=1;dk/=2)
        for(int i=dk+1;i<=n;++i)< span>
            if(A[i]
                A[0]=A[i];
                for(int j=i-dk;A[j]>A[0];j-=dk)
                    A[j+dk] = A[j];
                A[j+dk] = A[0];
            }
}

交换排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
//冒泡排序
//注意此处tow point的思想
void BubbleSort(Elemtype A[],int n){
    for(int i=0;i-1;i++){
        bool flag=false;
        for(int j=n-1;j>i;j--)
            if(A[j-1]>A[j]){
                swap(A[j-1],A[j]);
                flag = true;
            }
        if(!flag) break;
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//快速排序
int Partition(Elemtype A[],int low,int high){
    Elemtype pivot=A[low];
    while(low
        while(low=pivot) --high;
        A[low] = A[high];
        while(low
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}
void QucikSort(Elemtype A[],int low,int high){
    if(low
        int pos=Partition(A,low,high);
        QuickSort(A,low,pos-1);
        QuickSort(A,pos+1,high);
    }
}

选择排序

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
//简单选择排序
void SelectSort(Elemtype A[],int n){
    for(int i=0;i-1;i++){
        int min=i;
        for(j=i+1;j
            if(A[j]
                min=j;
        if(min!=i) 
            swap(A[i],A[min]);
    }
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//堆排序
void AdjustDown(Elemtype A[],int k,int len){
    A[0]=a[k];
    for(int i=2*k;i<=len;i*=2){
        if(i1]>A[i])
            i++;
        if(A[0]>A[i])   break;
        else{
            A[k]=a[i];
            k=i;
        }
    }
    A[k]=A[0];
}
void BuildMaxHeap(Elemtype A[],int len){
    for(int i=len/2,i>0;i--)
        AdjustDown(A,i,len);
}
void HeapSort(Elemtype A[],int len){
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--){
        Swap(A[i],A[1]);
        AdjustDown(A,1,i-1);
    }
}

归并排序

二路归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//归并排序
int *C = new Elemtype;
void Merge(Elemtype A[],int low,int mid,int high){
    for(int k=low;k<=high;k++)< span>
        B[k]=A[k];
    for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){< span>
        if(B[i]<=b[j])< span>
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid) a[k++]="B[i++];
    while(j<=high) a[k++]="B[j++];
}
void MergeSort(Elemtype A[],int low.int high){
    if(low
        int mid=(low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,high);
    }
}

* 基数排序

丨fengche丨 wechat
来找我聊天吧~
-------------本文结束感谢您的阅读-------------