数据结构

数据结构笔记

Posted by jiang on July 9, 2018

绪论

  • 基本概念
1
2
3
4
5
6
数据:信息的载体,符号集合。
数据元素:是数据的基本单元,一个数据元素可由若干数据项组成。数据项是构成数据元素不可分割的最小单元。
数据对象:具有相同性质的数据元素的集合,是数据的一个子集。
数据类型:一个值的集合和定义在此集合上的一组操作的总称。原子类型,结构类型,抽象数据类型
抽象数据类型ADT:指一个数学模型以及定义在该模型上的一组操作。(数据对象,数据关系,基本数据操作集)
数据结构:元素之间的相互关系称为结构。是相互之间特定关系的数据元素的集合。(逻辑结构,存储结构,数据的运算)
  • 数据的逻辑结构
1
2
3
4
5
集合
线性结构 一般线性表 栈 队列 串 数组 广义表
树形结构 一般数 二叉树
图状结构 有向图 无向图
网状结构
  • 数据的存储结构
1
2
3
4
顺序存储
链式存储
索引存储
散列存储
  • 数据的运算

算法和算法的评价

  • 概念 对特定问题的求解步骤的一种描述。
1
2
3
4
5
有穷性
确定性
可行性
输入
输出
  • 算法效率度量
1
2
3
4
5
6
7
8
9
10
11
T(n) O(n)
时间复杂度:一个语句的频度是指该语句在算法中被重复执行的次数。
最坏时间复杂度 平均时间复杂度 最好时间复杂度
加法规则 T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
乘法规则 T(n)=T1(n)xT2(n)=O(f(n)xg(n))

常见渐进时间复杂度
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

S(n)
空间复杂度:算法所耗费的存储空间。
  • 小结
1
2
循环主体中的变量参与循环条件的判断
循环主体红的变量与循环条件无关 递归程序 非递归程序

线性表

  • 定义和基本操作
1
2
3
4
5
6
7
8
9
10
11
12
是具有相同数据类型的n个元素的有限序列。
L=(a1,a2,a3...an)

InitList(&L)
Length(L)
LocateElem(L,e)
GetELem(L,i)
ListInsert(&L,i,e)
ListDelete(&L,i,&e)
PrintList(L)
Empty(L)
DestoryList(&L)

线性表的顺序表示

  • 顺序表 线性表的顺序存储=>顺序表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

#define InitSize 100
typedef struct{
    ElemType *data;
    int MaxSize,length;
} SeqList;

//随机访问 通过首地址和元素序号可以在O(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
27
28
29
30
31
32
33
34
35
36
37
38
39
//插入操作
bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.length+1) return false;
    if(L.length>=MaxSize) return false;
    for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
}
//最好:O(1)
//最坏:O(n)
//平均:O(n)

//删除操作
bool ListDelete(SqList &L,int i,Elemtype &e){
    if(i<1||i>L.length)return false;
    e = L.data[i-1];
    for(int j=i;j<L.length;j++){
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}
//最好O(1)
//最坏O(n)
//平均O(n)

//按值查找 顺序查找
int LocateElem(SqList L,ElemType 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)

线性表的链式表示

  • 单链表的定义
1
2
通过一组任意的存储单元来存储线性表中的数据元素
非随机存储
  • 结点定义
1
2
3
4
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}
  • 单链表的基本操作
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
//头插法建议单链表
LinkList CreateList1(LinkList &L){
    LNode *s;int x;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}
//O(n)

//尾插法建立单链表
LinkList CreateList2(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }    
    r->next=NULL;
    return L;
}
//O(n)

//按序号查找结点值
LNode *GetElem(LinkList L,int i){
    int j=1;
    LNode *p=L->next;
    if(i==0) return L;
    if(i<1) return NULL;
    while(p&&j<i){
        p=p->next;
        j++;
    }
    return p;
}
//O(n)

//按值查找表结点
LNode *LocateELem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}
//O(n)

//插入结点操作 给定前驱O(1) 不给定前驱O(n)
p=GetElem(L,i-1);
s->next=p->next;
p->next=s;

//换值后插 给定前驱O(1) 不给定前驱O(n)
s->next=p->next;
p->next=s;
temp=p->data;
p->data=s->data;
s->data=temp;

//删除结点操作 O(n)
p=GetElem(L,i-1);
q=p->next;
p->next=q->next;
free(q);

//求表长操作 O(n)
  • 双链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typeof struct DNode{
    ELemtype data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

//插入操作
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;

//删除操作
p->next=q->next;
q->next->prior=p;
free(q);
  • 循环链表
1
2
循环单链表
循环双链表
  • 静态链表 借助数组来描述线性表的链式存储结构。

栈和队列

  • 栈的基本操作
1
2
3
4
5
6
InitStack(&S)
StackEmpty(S)
Push(&S,x)
Pop(&S,&x)
GetTop(S,&x)
ClearStack(&S)
  • 栈的顺序存储结构
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
#define MaxSize 50
typedef struct {
    Elemtype data[MaxSize];
    int top;
} SqStack;

//初始化
void InitStack(&S){
    s.top=-1;
}

//判栈空
bool StackEmpty(S){
    if(S.top==-1){
        return true;
    }else{
        return false;
    }
}

//进栈
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1){
        return false;
    }
    S.data[++S.top]=x;
    return true;
}

//出栈
bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1){
        return false;
    }
    x=S.data[S.top--];
    return true;
}

//读出栈顶元素
bool GetTop(SqStack S,ELemType &x){
    if(S.top==-1){
        return false;
    }
    x=S.data[S.top];
    return true;
}
  • 共享栈 O(1) 更好的利用存储空间

  • 栈的链式存储结构 不存在上溢情况

1
2
3
4
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}*LiStack

队列

  • 队列的基本操作
1
2
3
4
5
InitQueue(&Q)
QueueEmpty(Q)
EnQueue(&Q,x)
DeQueue(&Q,&x)
GetHead(Q,&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
32
33
34
35
36
37
38
39
40
41
42
43
//存储类型描述
#define MaxSize 20
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

//循环队列
//初始化
void InitQueue(&Q){
    Q.rear=Q.front=0;
}

//判队空
bool isEmpty(Q){
    if(Q.rear==Q.front) {
        return true;
    }else{
        return false;
    }
}

//入队
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){
        return false;
    }else{
        Q.data[Q.rear]=x;
        Q.rear=(Q.rear+1)%MaxSize;
        return true;
    }
}

//出队
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front){
        return false;
    }else{
        x=Q.data[Q.front];
        Q.front=(Q.front+1)%Maxsize;
        return true;
    }
}
  • 队列的链式存储结构
1
2
3
4
5
6
7
typedef struct{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typdef struct{
    LinkNode *front,*rear;
}LinkQueue;
  • 链式队列的基本操作
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 InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

//判队空
bool isEmpty(Q){
    if(Q.front==Q.rear){
        return true;
    }else{
        return false;
    }
}

//入队
void EnQueue(LinkQueue &Q,ElemType x){
    s=(LinkNode *)mallco(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

//出队
bool DeQueue(LinkQueue &QElemType &x){
    if(Q.front==Q.rear) return false;
    p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
    free(p);
    return true;
}
  • 双端队列 允许两端都可以进行入队和出队操作的队列。

栈与队列的应用

  • 栈在括号匹配中的应用

  • 栈在表达式求值中的应用

  • 栈在递归中的应用

  • 队列在层次遍历中的应用 层次遍历二叉树

  • 队列在计算机系统中的应用 主机与外设速度不匹配问题 多用户引起的资源竞争问题

特殊矩阵的压缩存储

  • 数组存储结构

  • 矩阵压缩存储 对多个相同的元素只分配一个存储空间,对零元素不分配存储空间。

  • 特殊矩阵 对称矩阵 上下三角矩阵 对角矩阵 三对角矩阵

  • 稀疏矩阵 矩阵元素个数s相对矩阵中非零元素个数t来说非常多。三元组(行标,列标,值)

树与二叉树

  • 概念
1
2
3
4
5
6
7
8
祖先结点
兄弟结点
结点的度
树的度
结点的层次
结点的深度
结点的高度
路径长度
  • 树的性质
1
2
3
4
1.树的结点数等于所有结点的度数+1
2.度为m的树中第i层上至多有m^(i-1)个结点
3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
4.具有n个结点的m叉树的最小高度为[logm(n(m-1)+1)]

二叉树的概念

  • 二叉树的特性
1
二叉树是每个结点至多有两个子树,且有左右子树之分。
  • 满二叉树
    高度为h,并含有2^h-1个结点的二叉树称为满二叉树

  • 完全二叉树
    高度为h,有n个结点的二叉树,当且仅当每个结点都与高度高为h的满二叉树编号1~n的结点一一对应

  • 二叉排序树
    左子树上的所有结点的关键字均小于根节点的关键字,右子树上的所有结点关键字均大于根结点的关键字。

  • 平衡二叉树
    树上任意结点的左子树和右子树的深度之差不超过1

  • 二叉树性质

1
2
3
4
1.非空二叉树上叶子结点数等于度为2的结点数+1,N0=N2+1
2.非空二叉树上第K层上至多有2^(k-1)个结点
3.高度为H的二叉树至多有2^H-1个结点
4.具有N个结点的完全二叉树的高度为[log2(N+1)]
  • 二叉树的顺序存储结构
1
|1|2|3|0|4|0|5|0|0|6|0|
  • 二叉树的链式存储结构
1
2
3
4
typedef struct BiNode{
    ElemType data;
    struct BiNode *rchild,*lchild;
}BiNode,*BiTree;

二叉树的遍历和线索二叉树

  • 先序遍历 PreOrder
1
2
3
4
5
6
7
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T.lchild);
        PreOrder(T.rchild);
    }
}
  • 中序遍历
1
2
3
4
5
6
7
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T.lchild);
        visit(T);
        InOrder(T.rchild);
    }
}
  • 后序遍历
1
2
3
4
5
6
7
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T.lchild);
        PostOrder(T.rchild);
        visit(T);
    }
}
  • 中序遍历的非递归算法
1
2
3
4
5
6
7
8
9
10
11
12
13
void InOrder2(BiTree T){
    InitStack(S);BiTree p=T;
    while(p||!IsEmpty(S)){
        if(p){
            Push(S,p);
            p=p->lchild;
        }else{
            Pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}
  • 层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void LevelOrder(BiTree T){
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
        DeQueue(Q,p)
        visit(p);
        if(p->lchild!=NULL){
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(Q,p->rchild);
        }
    }
}
  • 由遍历序列构造二叉树
1
2
3
4
确定唯一的二叉树:
先序与中序
后序与中序
层次与中序
  • 线索二叉树

指向结点的前驱和后继的指针叫做线索。加上线索的二叉树为线索二叉树。

1
2
3
4
5
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;
  • 线索二叉树的构造
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
void InThread(ThreadTree &p,ThreadTree &pre){
    if(p!=NULL){
        InThread(p->lchild,pre);
        if(p->lchild==NULL){
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        InThread(p->rchild,pre);
    }
}


void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){
        InThread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag==0){
        p=p->lchild;
    }
    return p;
}

ThreadNode *Nextnode(ThreadNode *p){
    if(p->rtag==0){
        return FirstNode(p->rchild);
    }else{
        return p->rchild;
    }
}

void InOrder(ThreadNode T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=NextNode(p)){
        visit(p);
    }
}

树、森林

  • 树的存储结构
1
2
3
双亲表示法
孩子表示法
孩子兄弟表示法
  • 树、森林与二叉树的转换
1
2
3
树->二叉树:每个结点左指针指向它的第一个孩子结点,右指针指向它在树中的相邻兄弟结点。
森林->二叉树:先将每个树转为二叉树,在将第一个树根作为二叉树的根,第一棵树的左子树作为作为转换后的二叉树的左子树,第二棵树作为转换后二叉树根的右子树,以此类推。
二叉树->森林:唯一的 若二叉树非空,则二叉树根及其左子树为第一棵树的二叉树形式,右子树以此类推。
  • 树的遍历
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
简单的集合表示,
Union
Find
Initial

#define SIZE 100
int UFSets[SIZE]

void Initial(int S[]){
    for(int i=0;i<size;i++){
        S[i]=-1;
    }
}

int Find(int S[],int x){
    while(S[x]>=0){
        x=S[x]
    }
}

void Union(int S[],int Root1,int Root2){
    S[Root2]=Root1;
}

树与二叉树的应用

  • 二叉排序树 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
27
28
29
30
31
32
33
34
35
36
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
    p=NULL;
    while(T!=NULL&&key!=T->data){
        p=T;
        if(key<T->data) T=T->lchild;
        else T=T->rchild;
    }
    return T;
}

int BST_Insert(BiTree &T,KeyType k){
    if(T==NULL){
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;
    }else if(k==T->key) {
        return 0;
    }else if(k>T->key){
        return BST_Insert(T->rchild,k);
    }else{
        return BST_Insert(T->lchild,k);
    }
}

void Create_BST(BiTree &T,KeyType str[],int n){
    T=NULL;
    int i=0;
    while(i<n){
        BST_Insert(T,str[i]);
        i++;
    }
}
//查找最坏 O(n)
//查找平均O(log2(n))
//插入与删除O(n)
  • 平衡二叉树 AVL
    任意左右子树高度相差不超过1
    查找 log2(n)
    1
    2
    3
    4
    
    LL平衡旋转(右单旋转)
    RR平衡旋转(左单旋转)
    LR平衡旋转(先左后右旋转)
    RL平衡旋转(先右后左旋转)
    
  • 哈弗曼树 Huffman 和哈夫曼编码

在含有N个带权叶子结点的二叉树中,其中带权路径长度WPL,最小的二叉树称为哈夫曼树,称为最优二叉树。

哈弗曼树的构造

哈夫曼编码

  • 图的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1.有向图
2.无向图
3.简单图
4.多重图
5.完全图
6.子图
7.连通、连通图、和连通分量
8.强连通图 强连通分量
9.生成树 生成森林
10.顶点的度 出度 入度
11.边的权和网
12.稠密图 稀疏图
13.路径 路径长度 回路
14.简单路径 简单回路
15.距离
16.有向树

图的存储及基本操作

  • 邻接矩阵
1
2
3
4
5
6
7
8
9
10
结点数为n的图G=(V,E)的邻接矩阵Anxn的,将G的顶点编号为v1,v2,v3...vn
(vi,vj)属于E,A[i][j]=1,否则A[i][j]=0
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType Vex[MaxVertexNum];
    EdgeType Edge[MaxVertexNum][MaxVertexNum];
    int vexnum,arcnum;
}MGraph;
  • 邻接表
1
2
3
4
5
6
7
8
9
10
11
12
13
#define MaxVertexNum 100;
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *next;
}ArcNode;
typedef struct VNode{
    VertexType data;
    ArcNode *first;
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;
  • 十字链表 有向图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MaxVertexNum 100
typedef struct ArcNode{
    int tailvex,headvex;
    struct ArcNode *hlink,*tlink;
}ArcNode;

typedef struct VNode{
    VertexType  data;
    ArcNode *firstin,*firstout;
}VNode;

typedef struct {
    VNode xlist[MaxVertexNum];
    int vexnum,arcnum;
}GLGraph;

邻接多重表 无向图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MaxVertexNum 100
typedef struct ArcNode{
    bool mark;
    int ivex,jvex;
    struct ArcNode *ilink,*jlink;
}ArcNode;

typedef struct VNode{
    VertexType data;
    ArcNode *firstedge;
}VNode;

typedef struct{
    VNode adjmulist[MaxVertexNum];
    int vexnum,arcnum;
}AMLGraph;
  • 图的操作
1
2
3
4
5
6
7
8
9
10
Adjacent(G,x,y)
Neighbors(G,x)
InsertVertex(G,x)
DeleteVertex(G,x)
AddEdge(G,x,y)
RemoveEdge(G,x,y)
FirstNeighbor(G,x)
NextNeighbor(G,x,y)
Get_edge_value(G,x,y)
Set_edge_value(G,x,y,v)

图的遍历

  • 广度优先搜索BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS(Graph G,int v){
    visit(v);
    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]){
                visit(w);
                visited[w]=true;
                EnQueue(Q,w);
            }
        }
    }
}

//空间复杂度 O(|V|) 邻接表O(|V|+|E|) 邻接矩阵O(|V|^2)
  • 最短路径问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BFS_MIN_Distance(Graph G,int u){
    for(i=0;i<G.vexnum;++i){
        d[i]=&;
        visited[u]=true;
        d[u]=0;
        EnQueue(Q,u);
        while(!isEmpty(Q)){
            DeQueue(Q,u);
            for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
                if(!visited[w]){
                    visited[w]=true;
                    d[w]=d[u]+1;
                    EnQueue(Q,w);
                }
            }
        }
    }
}
  • 深度优先搜索DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
    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){
    visit(v);
    visited[v]=true;
    for(w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w)){
        if(!visited[w]) DFS(G,w)
    }
}
//空间复杂度O(|V|) 邻接表时间复杂度O(|V|+|E|) 邻接矩阵时间复杂度O(|V|^2)

图的应用

  • 最小生成树
1
2
3
若T为R中边的权值之和最小的那棵生成树,则T称为G的最小生成树。
1.普利姆算法 prim 选择最小权值边 O(|V|^2) 边稠密的图的最小生成树
2.克努斯卡算法 kruskal 森林合并成树 边稀疏而顶点较多的图
  • 最短路径
1
2
1.Dijkstra算法 单源最短路径问题 贪心策略 O(|V|^2)
2.Floyd算法 各个顶点之间最短路径问题 O(|V|^3)
  • 拓扑排序
1
2
3
有向无环图 DAG图
AOV网
拓扑排序:每个顶点出现一次 若顶点A在序列中排在顶点B的前面,则图中不存在B到A的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool TopologicalSort(Grgph G){
    InitStack(S);
    for(int i=0;i<G.vexnum;i++){
        if(indegree[i]==0)Push(S,,i);
    }
    int count=0;
    while(!IsEmpty(S)){
        Pop(S,i);
        print[count++]=i;
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){
            v=p->adjvex;
            if(!(--indegree[v]))Push(S,v);
        }
    }
    if(count<G.vexnum){
        return false;
    }else{
        return true;
    }
}
  • 关键路径
1
带权有向图,以顶点表示事件,有向边表示活动,权值表示完成该活动的开销,AOE网

查找

  • 顺序查找

  • 折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
int Binary_Search(SeqList L,ElemType key){
    int low=0,high=L.TableLen-1;mid;
    while(low<high){
        mid=(low+high)/2;
        if(L.elem[mid]==key){
            return mid;
        }else if(L.elem[mid]<key){
            low=mid + 1
        }else{
            high=mid - 1
        }
    }
}
  • 分块查找 索引顺序查找 块内无序 块外有序 b块 s个元素 O=log2(b+1)+(s+1)/2

B树和B+树

  • B树及其基本操作
1
2
3
4
5
多路平衡查找树 B树中所有结点的孩子结点数的最大值称为B树的阶。通常m表示,一棵m阶B树或空树,或为满足如下特性的m叉树。
B树的高度 磁盘存取次数
B树的查找 
B树的插入
B树的删除
  • B+树基本概念
1
2
3
1.每个分支最多有m棵子树
2.叶子结点包含关键字
3.两个指针 顺序查找 多路查找
  • 散列表
1
2
3
4
5
散列函数:把查找表中的关键字映射成关键字对应的地址函数
Hash(key)=Addr
冲突 同一个地址
散列表:根据关键字而直接进行访问的数据结构 
理想情况下 O(1)
  • 散列函数的构造方法
1
2
3
4
5
直接地址法 H(key)=axkey+b 空位较多 空间浪费
除留余数法 H(key)=key%p
数字分析法 关键字是r进制数 分布不均匀
平方取中法 取关键字的平方值的中间几位作为散列地址。 分布均匀 
折叠法 关键字分割成位数相同的几个部分,取这几个部分的叠加和作为散列地址。
  • 处理冲突方法
1
2
3
4
5
6
7
8
1.开放定址法 可存放新表项的空闲地址既向的同义词开放,又向它的非同义词表项开放。
H=(H(key)+d)%m
线性探测法 元素堆积 降低查询效率
平方探测法 二次探测 探测一半单元 m是一个表示成4k+3的素数
再散列法 双散列法 H=(H1(key)+ixH2(key))%m i散列次数 最多m-1次探测
伪随机序列法
弊端:不能删除元素,逻辑删除。
2.拉链法 同义词链表 数组+链表 可删除
  • 性能分析
1
2
装填因子
a=表中记录数n/散列表长度m

字符串模式匹配

  • 简单的模式匹配算法
    求第一个字符串在第二个字符串中的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S[0] && j<=T[0]){
        if(S[i]==T[j]){
            {++i;++j;}
        }else{
            {i=i-j+2;j=1;}
        }
    }
    if(j>T[0]){
        return i-T[0];
    }
    else{
        return 0;
    }
}
//O(n*m)
  • 改进的模式匹配算法-KMP算法
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
void get_next(char T[],int next[]){
    i=1;
    next[1]=0;
    j=0;
    while(i<=T[0]){
        if(j==0||T[i]==T[j]){
            ++i;++j;next[i]=j;
        }else{
            j=next[j];
        }
    }
}

int KMP(char S[],char T[],int next[],int pos){
    i=pos;
    j=1;
    while(i<=S[0]&&j<=T[0]){
        if(j==0||S[i]==T[j]){
            ++i;
            ++j;
        }else{
            j=next[j]
        }
    }
    if(j>T[0]){
         return i-T[0];
    }else{
         return 0;   
    }
}
//O(m+n)

排序

  • 算法稳定性
1
2
3
4
相同元素,排序后如果顺序不变,算法稳定
内部排序 外部排序 是否需要额外空间
比较和移动 
基数排序不基于比较

插入排序

  • 直接插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(ElemType A[],int n){
    int i,j;
    for(i=2;i<=n;i++){
        if(A[i].key<A[i-1].key){
            A[0]=A[i];
            for(j=i-1;A[0].key<A[j].key;--j){
                A[j+1]=A[j];
            }
            A[j+1]=A[0];
        }
    }
}
//稳定排序算法 O(n^2)
  • 折半插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InsertSort(ElemType A[],int []){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0]=A[i];
        low=1;high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid].key>A[0].key){
                high=mid-1;
            }else{
                low=mid+1;
            }
            for(j=i-1;j>=high+1;--j){
                A[j+1]=A[j];
            }
            A[high+1]=A[0];
        }
    }
}

//稳定排序算法 比较次数O(nlog2(n)) O(n^2)
  • 希尔排序 缩小增量排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(ElemType A[],int n){
    for(dk=n/2;dk>=1;dk=dk/2){
        for(i=dk+1;i<=n;++i){
            if(A[i].key<A[i-dk].key){
                A[0]=A[i];
                for(j=i-dk;j>0 && A[0].key<A[j].key;j-=dk){
                    A[j+dk]=A[j];
                }
                A[j+dk]=A[0];
            }
        }
    }
}
//不稳定排序 平均O(n^(1.3)) 最坏O(n^2)

交换排序

  • 冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbleSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
        flag=false;
        for(j=n-1;j>i;j--){
            if(A[j-1].key>A[j].key){
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
        if(flag==false) return;
    }
}
//稳定排序算法 比较n(n-1)/2 移动3n(n-1)/2 时间复杂度 O(n^2)
  • 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void QuickSort(ElemType A[],int low,int high){
    if(low<high){
        int pivotpos = Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos-1,high);
    }
}

int Partition(ElemType A[],int low,int high){
    ElemType pivot=A[low];
    while(low<high){
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high];
        while(low<high&&A[low]<=pivot) ++low;
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}
//栈深度 空间复杂O(n) 平均O(log2(n)) 时间复杂度最坏 O(n^2) 平均 O(nlog2(n)) 不稳定排序

选择排序

  • 简单选择排序
1
2
3
4
5
6
7
8
9
10
11
12
void SelectSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;j++){
            if(A[j]<A[min]){
                min=j;
            }
        }
        if(min!=i) swap(A[i],A[min]);
    }
}
//不稳定排序算法 O(n^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
//树形选择排序
void BuildMaxHeap(ElemType A[],int len){
    for(int i=len/2;i>0;i--) AdjustDown(A,i,len);
}

void AdjustDown(ElemType A[],int k,int len){
    A[0]=A[k];
    for(i=2*k;i<=len;i*=2){
        if(i<len&&A[i]<A[i+1])
            i++;
        if(A[0]>=A[i]) break;
        else
            A[k]=A[i];
            k=i;
    }//for
    A[k]=A[0];
}

void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A,len);
    for(i=len;i>1;i--){
        Swap(A[i],A[1]);
        AdjustDown(A,1,i-1);
    }//for
}

void AdjustUp(ElemType A[],int k){
    A[0]=A[k];
    int i=k/2;
    while(i>0&&A[i]<A[0]){
        A[k]=A[i];
        k=i;
        i=k/2;
    }//while
    A[k]=A[0];
}
//不稳定排序 时间复杂度O(n*log2(n))

归并排序和基数排序

  • 归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ElemType *B=(ElemType *)malloc((n+1)sizeof(ElemType));
void Merge(ELemType A[],int low,int mid,int high){
    for(int k=low;k<=high;k++)
        B[k]=A[k];
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }//for
    while(i<=mid) A[k++]=B[i++];
    while(j<=mid) A[k++]=B[j++];
}

void MergeSort(ElemType A[],int low,int high){
    if(low<high)
        int mid = (low+high)/2
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
}
//空间复杂度 O(n) 时间复杂度 O(nlog2(n)) 稳定排序算法
  • 基数排序
1
2
3
4
基于关键字排序
最高位优先MSD 
最低位优先LSD
空间复杂度O(r) 时间复杂度 O(r+d) d趟数 r队列数 稳定排序算法

外部排序

  • 多路平衡归并与败者树
1
2
减少树高度 增大归并路数
败者树 完全二叉树
  • 置换选择排序
1
减少初始归并段
  • 最佳归并树

小结

1
对n个整数进行排序,要求时间复杂度O(n),空间复杂度O(1)