Yutt's Blog

数据结构

理论
2018/03/22 Share

线性表

线性表插入一个元素，需要移动的元素个数的期望值为 n/2，删除一个元素的期望值为(n-1)/2。

链表节点类型定义：

1
2
3
4
typedef struct node {
    int data;
    struct node *next;
}NODE, *LinkList

单链表中，p节点后插入s

1
2
s->next = p->next;
p->next = s;

单链表中，删除p节点的后续节点

1
2
3
q = p->next;
p->next = q->next->next;
free(q);

单链表的查找运算

1
2
3
4
5
6
7
8
9
10
11
12
// k为元素个数
LinkList Find_List(LinkList L, int k) {
    LinkList p;
    int i;
    i = 1;
    p = L->next;
    while(p && i < k) {
        p = p -> next; i++
    }
    if (p && i== k) return p
    return NULL;
}

单链表的插入运算

1
2
3
4
5
6
7
8
9
10
11
12
int Insert_List(LinkList L, int k, int newElem) {
    LinkList p,s
    if(k == 1) p = L;
    else p = Find_List(L, k-1);
    if(!p) return -1;
    s = (NODE *)malloc(sizeof(NODE));
    if(!s) return -1;
    s->data = newElem;
    s->next = p->next;
    p->next = s
    return 0;
}

双向链表中，在p节点钱插入一个新节点s

1
2
3
4
s->front = p->front;
p->front->next = s;
s->next = p
p->front = s

双向链表中，删除一个节点p

1
2
3
p->front->next = p->next;
p->next->front = p->front;
free(p);

栈

较为简单，着重考虑出栈入栈的顺序。

队列

队列Q的容量为MAXSIZE, 初始时队列为空，且Q.rear和Q.front等于0。
元素入队时，修改队尾指针 Q.rear = ( Q.rear + 1 ) % MAXSIZE
元素出队时，修改队头指针 Q.front = ( Q.front + 1 ) % MAXSIZE

循环队列类型定义

1
2
3
4
5
6
7
#define MAXQSIZE 100

typedef struct {
    int *base;
    int front;
    int rear;
}SqQueue;;

创建一个空的循环队列

1
2
3
4
5
6
7
int InitQueue(SqQueue *Q) {
    Q->base = (int *)malloc(MAXQSIZE*sizeof(int));
    if(!Q->base) return -1;
    Q->front = 0; 
    Q->rear = 0;
    return 0;
}

元素入循环队列

1
2
3
4
5
6
7
int EnQueue(SqQueue *Q, int e) {
    /* 判断是否满队列 */
    if( (Q->rear+1) % MAZQSIZE == Q->front ) return -1;
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXQSIZE;
    return 0;
}

元素出循环队列

1
2
3
4
5
6
7
int DelQueue(SqQueue *Q, int *e) {
    /* 判断队列是否为空 */
    if(Q->rear == Q->front) return -1;
    *e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAXQSIZE
    return 0;
}

串

朴素的模式匹配算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 查找并返回模式串T在主串S中从pos开始的位置（下标），若T不是S的子串，则返回-1 */
int Index(char S[], char T[], int pos) {
    int i, j, slen, tlen;
    i = pos;
    j = 0;
    slen = strlen(S);
    tlen = strlen(T);
    while(i < slen && j < tlen) {
        if (S[i] === T[i]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
        if(j >= tlen) return i - tlen;
        return -1;
    }
}

最好的情况下，匹配成功的平均比较次数 (n + m)/ 2，时间复杂度为 O(n + m);
最差情况，m ✖️ (n - m + 2) / 2，时间复杂度为 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
void Get_next(char *p, int next[]) {
    int i, j, slen;
    slen = strlen(p);
    i = 0;
    next[0] = -1;
    j = -1
    while(i < slen) {
        if(j == -1 || p[i] == p[j]) {
            ++i;
            ++j;
            next[i] = j;
        }else {
            j= next[j]
        }
    }
}

int Index_KMP(char* s, char* p, int pos, int next[]) {
    int i, j, slen, plen;
    i = pos - 1;
    j = -1;
    slen = slen(s);
    plen = slen(p);
    while(i < slen && j < plen) {
        if(j == -1 || s[i] == p[j]) { ++i; ++j }
        else j = next[j]
    }
    if(j >= plen) return i-plen;
    else  return -1;
}

数组

二维数组：行优先存储，列优先存储

矩阵

对称矩阵
若一个矩阵是对称矩阵，可以将n^2个元素压缩存储到n(n+1)/2的存储空间中。
假设以一维数组B[n(n+1)/2]作为n阶堆成矩阵A中元素的存储空间，则 B[k](1=<k<n(n+1)/2)
与下标为ij的举证元素之间存在这一一对应的关系

i >= 1, j <= n， i >= j
k = i(i-1)/2 + j
i <= j
k = j(j-1)/2 + i

对角矩阵
k = 3(i-1) -1 + j -i +1 + 1 = 2i + j -2;

稀疏矩阵

树

二叉树的性质

  • 二叉树第i层上，最多有2^(i-1)个节点。
  • 高度位k的二叉树，最多有2^k-1个节点。
  • 对于任何一颗二叉树，若终端节点个数位a,度为2的节点个数位b，则 a=b+1。
  • 对于具有n个节点的完全二叉树的深度为floor(logn2^n) + 1。

二叉链表的节点类型

1
2
3
4
typedef struct BiTnode {
    int data;
    struct BiTnode *lchild, *rchild;
}BiTnode,*Bitree;

二叉树的先序遍历

1
2
3
4
5
6
7
void PreOrder(Bitree root) {
    if(root != NULL) {
        printf("%d", root->data);
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}

二叉树的中序遍历

1
2
3
4
5
6
7
void InOrder(Bitree root) {
    if(root != NULL) {
        InOrder(root->lchild);
        printf("%d", root->data);
        InOrder(root->rchild);
    }
}

二叉树的后序遍历

1
2
3
4
5
void PostOrcer(Bitree root) {
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    printf("%d", root->data);
}

二叉树的中序非递归遍历算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int InOrderTraverse(BiTree root) {
    BiTree p;
    /* 创建一个空栈 */
    InitStack(St);
    p = root;
    while(p != NULL || !isEmpty(St)){
        if(p != NULL) {
            Push(St, p)
            p = p->lchild;
        } esle {
            /* 栈顶元素出栈 */
            q = Top(St); Pop(St);
            printf("%d", q->data);
            p = q->rchild;
        }
    }
}

创建最优二叉树

图

  • 有向图
  • 无向图
  • 完全图，共有n(n-1)/2条边
  • 度、出度和入度
  • 路径
  • 连通图
  • 强连通图
  • 网
  • 有向树

图的存储结构
邻接链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 图中顶点的最大值 */
# define MaxN 50

typedef struct ArcNonde{
    /* 链接链表的定点序号 */
    int adjevex;
    /* 边上的权值 */
    double weight;
    /* 指向下一个定点的指针 */
    struct ArcNode* nextarc;
}EdgeNode

typedef struct VNode{
    char data;
    struct ArcNode *firstarc
}AdjList[MaxN];

typedef struct {
    int zvnum;
    AdjList Vertices;
}Graph

邻接矩阵

1
2
3
4
5
6
7
8
#define MaxN 30

typedef int AdjMatrix[MaxN][MaxN]
typedef struct {
    /* 图中顶点数目 */
    int Vnum;
    adjMatrix Arcs;
}Graph;

图的遍历

  • DFS，深度优先遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int visited[MaxN] = {0};
    void Dfs(Grap G, int i) {
        EdgeNode *t;int j;
        /* 访问序号为i的定点 */
        prinft("%d", i); 
        visited[i] = 1;
        t = G.Vertices[i].firstarc;
        while(t != NULL) {
            j = t->adjvex;
            if(visited[j] == 0)
                Dfs(G,j);
            t = t->nextarc;
        }
    }

  • BFS，广度优先遍历

生成树及最小生成树

  • 普里姆算法(Prim) 算法, O(n^2)
  • 克鲁斯卡尔算法(Kruskal) 算法, O(eloge)

AOV, AOE

查找

顺序查找，平均查找长度(n+1)/2.

折半查找, 需要有序排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Bsearch_rec(int r[], int low, int high, int key) {
    int mid;
    if(low <= high) {
        mid = (low + high) / 2;
        if(key == r[mid])
            rerturn mid;
        else if (key < r[mid])
            return Bsearch_rec(r,low,mid - 1, key);
        else if (key > r[mid])
            return Bsearch_rec(r,mid + 1, high, key);
    }
    return -1;
    
}

二叉排序树采用二叉链表存储

1
2
3
4
typedef struct Tnode {
    int data;
    struct Tnode *lchild, *rchild
}BSTnode, *BSTree

二叉排序树查找算法

1
2
3
4
5
6
7
8
9
BsTree SearchBST(BSTree root, int key, BSTree *father) {
    BSTree p = root; *father = NULL;
    while(p && p->data!=key) {
        *father = p;
        if(key < p->data) p=p-lchild;
        else p= p->rchild
    }
    return p;
}

  • 平衡二叉树
  • B_树
  • 哈希表（通过增量序列解决冲突）

排序

排序算法 平均情况 最好情况 最坏情况 空间复杂度 稳定性
直接插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n^1.3) O(n) O(n^2) O(1) 不稳定
简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
堆排序 O(nlog2 n) O(nlog2 n) O(nlog2 n) O(1) 不稳定
冒泡排序 O(n^2) O(n) O(n2) O(1) 稳定
快速排序 O(nlog2 n) O(nlog2 n) O(n^2) O(nlog2 n) 不稳定
归并排序 O(nlog2 n) O(nlog2 n) O(nlog2 n) O(1) 稳定
基数排序 O(d(r+n)) O(d(n+rd)) O(d(r+n)) O(rd+n) 稳定

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
void Insertsort (int data[], int n) {
    int i, j;
    int tmp;
    for(i = 1; i < n; i++) {
        if(data[i] < data[i - 1]) {
            tmp = data[i];
            data[i] = data[i -1];
            for(j = i - 1; j >= 0 && data[j] > tmp; j--) data[j+1] = data[j];
            data[j + 1] = tmp;
        }
    }
}

希尔排序

1
2
3
void ShellSort(int data[], int n) {

}

1
2
3
4
5
6
7
8
9
10
11
12
13
**简单选择排序**
void SelectSort(int data[], int n) {
    int i, j, k, tmp;
    for(i = 0;i < n -1; i++) {
        k = i;
        for(j = i + 1;j < n;j++) {
            if(data[j] < data[k]) k = j;
        }
        if(k != i) {
            tmp = data[i]; data[i] = data[k]; data[k] = tmp
        }
    }
}

快速排序

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
int partiton(int data[], int low, int high)
{
  int i, j, pivot;
  pivot = data[low];
  i = low;
  j = high;
  while (i < j)
  {
    while (i < j && data[j] >= pivot)
      j--;
    data[i] = data[j];
    while (i < j && data[i] <= pivot)
      i++;
    data[j] = data[i];
  }
  data[i] = pivot;
  return i;
}

void quickSort(int data[], int low, int high)
{
  if (low < high)
  {
    int loc = partiton(data, low, high);
    quickSort(data, low, loc - 1);
    quickSort(data, loc + 1, high);
  }
}

CATALOG
  1. 1. 线性表
  2. 2. 栈
  3. 3. 队列
  4. 4. 串
  5. 5. 数组
  6. 6. 矩阵
  7. 7. 树
  8. 8. 图
  9. 9. 查找
  10. 10. 排序
Archive Tag
Total : 25
2018
理论 English java android web javascript git js leetCode react-native react redux