数据结构与算法分析简要

算法知识简要大纲

抽象数据类型(Abstract Data Type, ADT)
抽象数据类型的特征是 实现操作 分离,从而实现 封装
抽象数据类型体现了程序设计中 问题分解信息隐藏 的特征。它把问题分解为多个规模较小且容易处理的问题,然后把每个功能模块的实现为一个独立单元,通过一次或多次调用来实现整个问题。

算法分析

递归简论

  1. 基准情况:在某一情况下无须递归就会return。
  2. 不断推进:每一次递归都往基准推进。
  3. 设计法则:所有递归都能调用。
  4. 合成效益法则:在同一个问题中,勿在不同递归调用中做同一个工作

时间复杂度

(大概是看看就好了吧)

  • 定义:如果存在正常数$𝑐$和$𝑛_0$, 使当$𝑁≥𝑛_0$时$𝑇(𝑁)≤𝑐𝑓(𝑁)$, 则记为$𝑇(𝑁)=\mathcal{O}(𝑓(𝑁))$
  • 定义:如果存在正常数$𝑐$和$𝑛_0$, 使当$𝑁≥𝑛_0$时$𝑇(𝑁)≥𝑐𝑔(𝑁)$, 则记为$𝑇(𝑁)=Ω(𝑔(𝑁))$
  • 定义:$𝑇(𝑁)=Θ(ℎ(𝑁)$当且仅当$𝑇(𝑁)=\mathcal{O}(ℎ(𝑁))$且$𝑇(𝑁)=Ω(ℎ(𝑁))$
  • 定义:如果$𝑇(𝑁)=\mathcal{O}(𝑝(𝑁))$且$𝑇(𝑁)≠Ω(𝑝(𝑁))$, $𝑇(𝑁)=\mathcal{O}(𝑝(𝑁))$
名称 运行时间T(N) 算法举例
常数时间 $\mathcal{O}(1)$ 判断一个二进制数的奇偶
对数时间 $\mathcal{O}(log⁡N)$ 二分搜索
(小于1次)幂时间 $\mathcal{O}(N^c)$其中$0<c<1$ K-d树的搜索操作
线性时间 $\mathcal{O}(N)$ 无序数组的搜索
线性对数时间 $\mathcal{O}(N\log{⁡N})$ 最快的比较排序
二次时间 $\mathcal{O}(N^2)$ 冒泡排序、插入排序
三次时间 $\mathcal{O}(N^3)$ 矩阵乘法的基本实现,计算部分相关性
指数时间 $\mathcal{O}(2^N)$ /

时间复杂度

  • 计算时间复杂度
    • 一层循环的时间复杂度为$𝑂(𝑁)$
    • 多层嵌套循环的时间复杂度是每层循环的时间复杂度之积$𝑂(𝑁^n)$
    • if…else… /case…switch…语句中取各个分支中最长的时间作为时间开销

表、栈、队列

表ADT(链表) List

习惯上会留出一个 标志节点 , 有时称之为 表头(header)哑节点(dummy node)

  • 动画
  • Head File

    1
    struct Node;
    2
    typedef struct Node *PtrToNode;
    3
    typedef PtrToNode List;
    4
    typedef PtrToNode Position;
    5
    typedef int ElementType;
    6
    // series of functions
    7
    // ......
  • 结构体定义

    1
    struct Node{
    2
        ElementType Element;
    3
        Position Next;
    4
        // 可以加一个前置节点, 则成为双链表
    5
    };
  • Find 查询
    其实就是从头遍历

    1
    Position Find( ElementType X, List L){
    2
        Position P;
    3
        P = L->Next;
    4
        while( P != NULL && P->Element != X){
    5
            P = P->Next;
    6
        }
    7
        return P;
    8
    }
  • FindPrevious 查询前一个节点
    和Find类似, 区别仅在line2,3

    1
    Position FindPrevious( ElementType X, List L){
    2
        Position P;
    3
        P = L;
    4
        while(P->Next != NULL && P->Next->Element != X){
    5
            P = P->Next;
    6
        }
    7
        return P;
    8
    }
  • Delete 删除

    1
    void Delete( ElementType X, List L){
    2
        Position P, TmpCell;
    3
        P = FindPrevious(X, L);
    4
        if ( !IsLast( P, L) ){
    5
            TmpCell = P->Next;
    6
            P->Next = TmpCell->Next;
    7
            free(TmpCell); // 及时释放内存空间
    8
        }
    9
    }
  • Insert 插入

    1
    void Insert( ElementType X, List L, Position P){
    2
        Position TmpCell;
    3
        TmpCell = malloc( sizeof (struct Node));
    4
        if (TmpCell == NULL){
    5
            // FatalError("Out of space!!!");
    6
            printf("Out of space!!!");
    7
        }
    8
        TmpCell->Element = X;
    9
        TmpCell->Next = P->Next;
    10
        P->Next = TmpCell;
    11
    }
  • 其他类型
    • 双链表
    • 循环链表
    • 多重表
  • 基数排序(radix sort)
    • 低位排序LSD
    • 高位排序MSD
  • 游标(cursor)实现法
    需要链表又不能使用指针(如 BASIC 和 FORTRAN 等)

栈ADT Stack

又名 LIFO(先进后出)表
基本上就Pop(出栈)Push(进栈)操作

  • 实现

    • 链表实现
      主要时间花费在于分配新空间和删除弹出的结点
    • 数组实现
      唯一潜在危害: 需要提前声明一个数组大小
  • 应用

    • 后缀表达式
    • 中缀到后缀的转换
    • 函数调用
      • 尾递归(TODO:未懂)
        执行的任何递归调用是在这种情况下的最后操作,而且通过封闭递归,递归调用的返回值(若有)立即返回.
        必须是 线性递归 (递归内只调用一个新的递归)
    • 平衡符号
      平衡符号

队列 Queue

  • 基本操作
    • Enqueue 入队 : 在表的末端(队尾rear)插入一个元素
    • Dequeue 出队 : 删除 / 返回 表的开头(队头front)
  • 实现
    • 链表实现
    • 数组实现(循环数组circular array实现)
  • 应用
    • 排队论(queueing theory)

树 Tree

预备知识

  • 基本术语
术语 定义
根(root) /
边(edge) 连接节点的有向线
—- —-
子节点(child) 一个节点含有的子树的根节点称为该节点的子节点
父节点(parent) 若一个节点含有子节点,则这个节点称为其子节点父节点
兄弟节点(sibling) 具有相同父节点的节点互称为兄弟节点
堂兄弟节点 双亲在同一层的节点互为堂兄弟
祖先(grandparent) 从根到该节点所经分支上的所有节点
子孙(grandchild) 以某节点为根的子树中任一节点都称为该节点的子孙
—- —-
树叶(leaf) 没有子节点的节点
从节点$n_1$到$n_k$的路径(path) 节点$n_1, n_2, \cdots,n_k$的一个序列
路径的长(length) 路径上边的条数
深度(depth) 从根到$n_i$的位移路径的长
高度(height) 从$n_i$到一片树叶的最长路径的长
树的高度或深度 树中节点的最大层次
—- —-
非终端节点或分支节点 度不为0的节点
节点的层次 从根开始定义起,根为第1层,根的子节点为第2层,以此类推
节点的度 一个节点含有的子树的个数称为该节点的度
树的度 一棵树中,最大的节点的度称为树的度
森林 由m(m>=0)棵互不相交的树的集合称为森林
  • 种类
    • 无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树;
    • 有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;
    • 二叉树:每个节点最多含有两个子树的树称为二叉树;
    • 完全二叉树
    • 满二叉树
    • 霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;

遍历

遍历顺序 应用 顺序 动画
先序遍历 显示文件夹结构 中->左->右 前序遍历
后序遍历 计算文件夹总大小 左->右->中 后序遍历
中序遍历 表达式树 左->中->右 中序遍历
层序遍历 层序遍历

二叉树

动画

  • 种类: 表达式树, 查找树ADT——二叉查找树
  • Head File

    1
    struct TreeNode;
    2
    typedef struct TreeNode *Position;
    3
    typedef struct TreeNode *SearchTree;
    4
    typedef int ElementType;
    5
    // series of functions
    6
    // ......
  • 结构体定义

    1
    struct TreeNode{
    2
        ElementType Element;
    3
        SearchTree Left;
    4
        SearchTree Right;
    5
    };
  • Find 查询

    1
    Position Find( ElementType X, SearchTree T){
    2
        if (T==NULL){
    3
            return NULL;
    4
        }
    5
        if(X<T->Element){// 元素大了
    6
            return Find(X,T->Left);// 去找左边小一点的
    7
        }else if(X>T->Element){
    8
            return Find(X,T->Right);
    9
        }else{
    10
            return T;// 返回后类型变为Position了
    11
        }
    12
    }
  • Insert 插入

    1
    SearchTree Insert( ElementType X, SearchTree T){
    2
        if (T==NULL){
    3
            //创建并返回一个一节点树
    4
            T = malloc(sizeof(struct TreeNode));
    5
            if (T==NULL){
    6
                printf("out of space!!!");
    7
            }else{
    8
                T->Element = X;
    9
                T->Left = T->Right = NULL;
    10
            }
    11
        }else if(X < T->Element){
    12
            T->Left = Insert(X,T->Left);
    13
        }else if(X > T->Element){
    14
            T->Right = Insert(X,T->Right);
    15
        }else{
    16
            printf("%d is already in tree...\n",X);
    17
        }
    18
        return T;
    19
    }
  • Delete 删除节点

    1
    //TODO:
  • PrintTree 打印树

    1
    void PrintTree( SearchTree T,int space,int LR,int *N){
    2
        // LR: 标志左右节点的参数,用以打印`/`或`\`
    3
        // *N: 打印前N个节点
    4
        int len = 10; // 每一层的打印间距(空格)
    5
        if (T!=NULL && (*N)>0){
    6
            (*N)--;
    7
            PrintTree(T->Right,space+len,1,N);
    8
            for (int loop = 0;loop<space; loop++){
    9
                printf(" ");
    10
            }
    11
            if(LR==1){
    12
                printf("/");
    13
            }else if(LR==0){
    14
                printf("\\");
    15
            }
    16
            printf("%-6d\n",T->Element);
    17
            PrintTree(T->Left,space+len,0,N);
    18
        }
    19
    }

AVL树 (Adelson-Velsky 和 Landis)

动画

  • 定义: 每个节点的左子树和有字数的高度最大相差1的二叉查找树
  • 深度: $\mathcal{O}(\log{N})$
  • 旋转
    • 单旋转
      相邻子树高度相差大于等于2
    • 双旋转
      相邻子树高度相差为1

伸展树 splay tree

  • 基本想法: 当一个节点被访问后,它就要经过一系列AVL树的旋转被放到根上
  • 两种情况
    • 之字形(zig-zag): AVL双旋转
    • 一字形(zig-zig): AVL单旋转两次

B-树 (B-tree)

不是二叉树的查找树

  • 称呼
    • 4阶B-树 == 2-3-4树
    • 3阶B-树 == 2-3树

考试好像不考但是先马克这个博客吧

分析树

这个好像也不考

哈希 Hash

又名散列

哈希函数

  • 简单
    1
    Index HashNormal(ElementType Key, int TableSize){
    2
      return Key%TableSize;
    3
    }
  • 优秀
    1
    Index HashBeautifully(ElementType Key, int TableSize){
    2
    ElementType * ptrKey = &Key;
    3
    unsigned int HashVal = 0;
    4
    while (*ptrKey !='\0'){
    5
        HashVal = (HashVal << 5) + *ptrKey++;
    6
    }
    7
    return HashVal % TableSize;
    8
    }

    分离链表法(拉链法)

  • 头文件

    1
    struct ListNode;
    2
    typedef struct ListNode *Position;
    3
    struct HashTbl;
    4
    typedef struct HashTbl *HashTable;
    5
    typedef int ElementType;
    6
    typedef int Index;
  • 初始化

    1
    HashTable 
    2
    InitializeTable(int TableSize){
    3
      HashTable H;
    4
      int i;
    5
      if (TableSize < MinTableSize){
    6
          printf("Table size too small");
    7
          return NULL;
    8
      }
    9
      // allocate table
    10
      H = malloc(sizeof(struct HashTbl));
    11
      if(H == NULL){
    12
          printf("out of sapce !!!");
    13
      }
    14
      // allocate list headers
    15
      for (i=0; i<H->TableSize; i++){
    16
          H->TheLists[i] = malloc(sizeof(struct ListNode));
    17
          if (H->TheLists[i]==NULL){
    18
              printf("out of space !!!");
    19
          }else{
    20
              H->TheLists[i]->Next = NULL;
    21
          }
    22
      }
    23
      return H;
    24
    }
  • 结构体定义

    1
    struct ListNode{
    2
        ElementType Element;
    3
        Position Next;
    4
    };
    5
    6
    typedef Position List;
    7
    8
    struct HashTbl{
    9
        int TableSize;
    10
        List *TheLists;
    11
    };
  • Find

    1
    Position 
    2
    Find( ElementType Key, HashTable H, Index HashNum){
    3
        Position P;
    4
        List L;
    5
    6
        // L = H->TheLists[Hash(Key, H->TableSize)];
    7
        L = H->TheLists[HashNum];
    8
        P = L->Next;
    9
        while(P!=NULL && P->Element!=Key){
    10
            P=P->Next;
    11
        }
    12
        return P;
    13
    }
  • Insert

    1
    void 
    2
    Insert( ElementType Key, HashTable H, Index HashNum){
    3
        Position Pos, NewCell;
    4
        List L;
    5
        Pos = Find(Key,H,HashNum);
    6
        if(Pos == NULL){
    7
            NewCell = malloc(sizeof(struct ListNode));
    8
            if (NewCell == NULL){
    9
                printf("out of space!!!");
    10
            }else{
    11
                // L = H->TheLists[Hash(Key,H->TableSize)];
    12
                L = H->TheLists[HashNum];
    13
                NewCell->Next = L->Next;
    14
                NewCell->Element = Key;
    15
                L->Next = NewCell;
    16
            }
    17
        }else{
    18
            printf("already have it!\n");
    19
        }
    20
    }
  • 装填因子(load factor) $\lambda$

    尽量让表的大小与预料的元素个数差不多,即 $\lambda\approx 1$ .

开放定址法

  • 头文件
    1
    typedef unsigned int Index;
    2
    typedef Index Position;
    3
    4
    struct HashTbl;
    5
    typedef struct HashTbl *HashTable;
    6
    typedef int ElementType;
    7
    // series of functions
    8
    // ......
  • 基础声明

    1
    #define MinTableSize 10
    2
    extern int Collision_Square,Collision_Liner,Collision_Double;
    3
    enum KindOfEntry{Legitimate,Empty,Deleted};
    4
    5
    struct HashEntry{
    6
        ElementType Element;
    7
        enum KindOfEntry Info;
    8
    };
    9
    10
    typedef struct HashEntry Cell;
    11
    12
    // 哈希表
    13
    struct HashTbl{
    14
        int TableSize;
    15
        Cell *TheCells;
    16
    };
  • 初始化

    1
    HashTable 
    2
    InitializeTable(int TableSize){
    3
        HashTable H;
    4
        int i;
    5
    6
        if(TableSize<MinTableSize){
    7
            printf("Table Size too small");
    8
            return NULL;
    9
        }
    10
        
    11
        // allocate table
    12
        H = malloc(sizeof(struct HashTbl));
    13
        if (H == NULL){
    14
            printf("out of space!!!\n");
    15
        }
    16
        H->TableSize = NextPrime(TableSize);
    17
    18
        // allocate array of cells
    19
        H->TheCells = malloc(sizeof(Cell) * H->TableSize);
    20
        if (H->TheCells == NULL){
    21
            printf("out of space!!!\n");
    22
        }
    23
    24
        for (i = 0;i<H->TableSize;i++){
    25
            H->TheCells[i].Info = Empty;
    26
        }
    27
        return H;
    28
    }

线性探测法

  • Find
    1
    Position 
    2
    FindByLiner(ElementType Key, HashTable H){
    3
        Position CurrentPos;
    4
        int CollisionNum;
    5
        CollisionNum = 0;
    6
        CurrentPos = HashNormal(Key,H->TableSize);
    7
        while(H->TheCells[CurrentPos].Info != Empty &&  // 非空
    8
              H->TheCells[CurrentPos].Element != Key){  // 不等于查询值
    9
            CurrentPos++;       
    10
            CollisionNum++;
    11
            if(CurrentPos >= H->TableSize){
    12
                CurrentPos -= H->TableSize;             // 循环查找
    13
            }
    14
        }// 一旦找到就跳出循环
    15
        Collision_Liner += CollisionNum;
    16
        return CurrentPos;
    17
    }
  • Insert

    1
    void InsertByLiner(ElementType Key, HashTable H){
    2
        Position Pos;
    3
        Pos = FindByLiner(Key,H);
    4
        if(H->TheCells[Pos].Info != Legitimate){// 该位置没有数据
    5
            H->TheCells[Pos].Info = Legitimate;
    6
            H->TheCells[Pos].Element = Key;
    7
        }
    8
    }
  • 一次聚集(primary clustering)
    占据的单元形成一些区块

  • 预期探测次数

    • 插入 / 不成功的查找
    • 成功的查找

平方散列法

  • 快速公式
    CurrentPos += 2 * ++CollisionNum - 1
  • Find
    1
    Position 
    2
    FindBySquare(ElementType Key, HashTable H){
    3
        Position CurrentPos;
    4
        int CollisionNum;
    5
        CollisionNum = 0;
    6
        CurrentPos = HashNormal(Key,H->TableSize);
    7
        while(H->TheCells[CurrentPos].Info != Empty &&  // 非空
    8
              H->TheCells[CurrentPos].Element != Key){  // 不等于查询值
    9
            CurrentPos += 2 * ++CollisionNum - 1;       // 平方探测 快速方法
    10
            if(CurrentPos >= H->TableSize){
    11
                CurrentPos -= H->TableSize;             // 循环查找
    12
            }
    13
        }// 一旦找到就跳出循环
    14
        Collision_Square += CollisionNum;
    15
        return CurrentPos;
    16
    }
  • Insert
    1
    void InsertBySquare(ElementType Key, HashTable H){
    2
        Position Pos;
    3
        Pos = FindBySquare(Key,H);
    4
        if(H->TheCells[Pos].Info != Legitimate){        // 该位置没有数据
    5
            H->TheCells[Pos].Info = Legitimate;
    6
            H->TheCells[Pos].Element = Key;
    7
        }
    8
    }

双(倍)散列

  • Find

    1
    Position 
    2
    FindByDouble(ElementType Key, HashTable H){
    3
        Position CurrentPos;
    4
        int CollisionNum = 0;
    5
        int addDouble = HashDoubel(Key,7);
    6
        CurrentPos = HashNormal(Key,H->TableSize);
    7
        while(H->TheCells[CurrentPos].Info != Empty &&  // 非空
    8
              H->TheCells[CurrentPos].Element != Key){  // 不等于查询值
    9
            CurrentPos += addDouble;       
    10
            CollisionNum++;
    11
            if(CurrentPos >= H->TableSize){
    12
                CurrentPos -= H->TableSize;             // 循环查找
    13
            }
    14
        }// 一旦找到就跳出循环
    15
        Collision_Double += CollisionNum;
    16
        return CurrentPos;
    17
    }
  • Insert

    1
    void InsertByDouble(ElementType Key, HashTable H){
    2
        Position Pos;
    3
        Pos = FindByDouble(Key,H);
    4
        if(H->TheCells[Pos].Info != Legitimate){        // 该位置没有数据
    5
            H->TheCells[Pos].Info = Legitimate;
    6
            H->TheCells[Pos].Element = Key;
    7
        }
    8
    }

再散列

当表有超过 70% 的单元是满的, 建立新表
新表大小是原表大小两倍后的第一个素数

  • 实现
    • 表满一半就再散列
    • 当插入失败是才再散列
    • 途中(middle-of-the-road)策略 : 当表达到某个装填因子时进行再散列

可扩散列

优先队列(堆) Heap

二叉堆 binary heap

动画
堆是一刻完全二叉树(complete binary tree)

  • 堆序性 heap order
    • 最小元在根上
    • 任意节点小于其所有后裔

基本堆操作

  • Insert

    • 上滤
      加在队尾然后向上排序
    • 标记 sentinel
      通过添加一条 哑信息(dummy piece of information) , 避免在插入新的最小值时每个循环都执行一次的测试
  • DeleteMin

    • 下滤
      删除根, 队尾换到队头, 向下排序

应用

  • 选择问题
  • 时间模拟

d-堆

略TODO:

左式堆

略TODO:

斜堆

略TODO:

二项队列

略TODO:

排序 Sort

动画

  • 算法复杂度
    算法复杂度

    冒泡排序 Bubble

    相邻比较+换位
    1
    void BubbleSort(int *arr, int len)  
    2
    {  
    3
        int i, j, tmp;  
    4
        for (i = 0; i < len - 1; i++) {  
    5
            for (j = 0; j < len - i - 1; j++) {  
    6
                if (arr[j] > arr[j+1]) {  
    7
                    tmp = arr[j];  
    8
                    arr[j] = arr[j+1];  
    9
                    arr[j+1] = tmp;  
    10
                }  
    11
            }  
    12
        }  
    13
    }  
    14
    ``` 
    15
    ![冒泡](https://images2017.cnblogs.com/blog/849589/201710/849589-20171015223238449-2146169197.gif)
    16
    17
    ## 选择排序 Select
    18
    向后查找最小元, 与每一轮首位换位
    19
    ```c 
    20
    void SelectionSort(int *arr, int len)
    21
    {
    22
        int i, j, min, tmp;
    23
        for (i = 0; i < len - 1; i++) {
    24
            min = i;
    25
            for (j = i + 1; j < len; j++) {
    26
                if (arr[j] < arr[min]) {
    27
                    min = j;// 修改最小元
    28
                }
    29
            }
    30
            tmp = arr[min];
    31
            arr[min] = arr[i];
    32
            arr[i] = tmp;
    33
        }
    34
    }
    选择

插入排序 Insert

从第二个开始抽出来, 和前面的比较并排位

1
void InsertionSort(int *arr, int len)    
2
{    
3
    int i, j, tmp;    
4
    for (i = 1; i < len; i++) { 
5
        //从第二个开始   
6
        if (arr[i] < arr[i-1]) {   // 如果小于前一个 
7
            tmp = arr[i];          // 要移动的元放到temp中
8
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {  
9
                //向前顺位
10
                arr[j+1] = arr[j];    
11
            }  
12
            arr[j+1] = tmp;    
13
        }          
14
    }    
15
}

插入

希尔排序 Shell

按增量分批做插入排序

1
// 希尔排序
2
void ShellSort(int *arr, int size)  
3
{  
4
    int i, j, tmp, increment;  
5
    for (increment = size/ 2; increment > 0; increment /= 2) {    
6
        for (i = increment; i < size; i++) {  
7
            // 做插入排序
8
            tmp = arr[i];  
9
            for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {  
10
                arr[j + increment] = arr[j];  
11
            }  
12
            arr[j + increment] = tmp;
13
        }  
14
    }  
15
}

希尔

归并排序 Merge

分治法

1
void merge(int arr[], int low, int mid, int high){
2
    int i, k;
3
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
4
    //申请空间,使其大小为两个
5
    int left_low = low;
6
    int left_high = mid;
7
    int right_low = mid + 1;
8
    int right_high = high;
9
10
    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
11
        if(arr[left_low]<=arr[right_low]){
12
            tmp[k] = arr[left_low++];
13
        }else{
14
            tmp[k] = arr[right_low++];
15
        }
16
    }
17
18
    if(left_low <= left_high){  //若第一个序列有剩余,直接复制出来粘到合并序列尾
19
        //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
20
        for(i=left_low;i<=left_high;i++)
21
            tmp[k++] = arr[i];
22
    }
23
24
    if(right_low <= right_high){ //若第二个序列有剩余,直接复制出来粘到合并序列尾
25
        //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
26
        for(i=right_low; i<=right_high; i++)
27
            tmp[k++] = arr[i];
28
    }
29
30
    // 从tmp复制回arr内
31
    for(i=0; i<high-low+1; i++)
32
        arr[low+i] = tmp[i];
33
    free(tmp);
34
    return;
35
}
36
37
void MergeSort(int arr[], unsigned int first, unsigned int last){
38
    int mid = 0;
39
    if(first<last){
40
        mid = (first+last)/2; /* 注意防止溢出 */
41
        /*mid = first/2 + last/2;*/
42
        //mid = (first & last) + ((first ^ last) >> 1);
43
        MergeSort(arr, first, mid);
44
        MergeSort(arr, mid+1,last);
45
        merge(arr,first,mid,last);
46
    }
47
    return;
48
}

快速排序 Quick

分块排序, 且左块皆小于右块

1
void swap(int *a, int *b){  
2
    int temp;  
3
    temp = *a;  
4
    *a = *b;  
5
    *b = temp;  
6
}  
7
void QuickSort(int *arr, int maxlen, int begin, int end){  
8
    int i, j;  
9
    if (begin < end) {  
10
        i = begin + 1;  
11
        j = end;        
12
        while (i < j) {  
13
            if(arr[i] > arr[begin]) {  
14
                swap(&arr[i], &arr[j]); 
15
                j--;  
16
            } else {  
17
                i++;        // 否则继续往后看
18
            }  
19
        }                   // 循环跳出后i,j一样
20
        if (arr[i] >= arr[begin]) {  
21
            i--;  
22
        }  
23
        swap(&arr[begin], &arr[i]);      
24
        QuickSort(arr, maxlen, begin, i);  
25
        QuickSort(arr, maxlen, j, end);  
26
    }  
27
}

快速

堆排序 Heap

1
#define LeftChild(i) (2*(i)+1)
2
3
void PercDown(int A[],int i, int N){                  // 下滤
4
    int Child;
5
    int Tmp;
6
    for (Tmp=A[i];LeftChild(i)<N;i=Child){            // Tmp为第一个本体的值 , 每次更新i为指向的子节点(较大者)
7
        Child = LeftChild(i);                         // 指向左子节点
8
        if(Child != N-1 && A[Child + 1] > A[Child]){  // 子节点不在最末(不然会爆) 且 右子节点>左子节点
9
            Child++;                                  // 从左子节点指向右子节点
10
        }
11
        if(Tmp < A[Child]){                           // 如果本体小于子节点最大的那个,
12
            A[i] = A[Child];                          // 把子节点覆盖到本体.
13
        }else{
14
            break;                                    // 一旦本体已经最大则跳出
15
        }
16
    }
17
    A[i] = Tmp;                                       // 把元初本体的值放到最后指向的子节点
18
}
19
20
void HeapSort(int A[],int N){
21
    int i;
22
    for (i=N/2;i>=0;i--){                             // 从倒数第二层向上过滤排序
23
        PercDown(A,i,N);                              // 构造大顶堆
24
    }
25
    for (i = N-1;i>0;i--){
26
        swap(&A[0],&A[i]);                            // 每换一次位(提取最大值到最后),
27
        PercDown(A,0,i);                              // 又要再做一次下滤.
28
    }
29
}

堆

基数排序

1
// TODO:

基数

计数排序

1
// TODO:

计数

桶排序

1
// TODO:

桶

随机快速排序

1
// TODO:

图论 Graph

基本概念

  • 图(Graph)顶点(Vertex)边(Edge) 的集合。边是对任意两个顶点的连接。
  • 基本术语

术语 定义
阶(Order) 图中顶点的个数
尺寸(Size) 图中边的个数
子图(Sub-graph) 一个图的顶点与边的子集。即,当$𝑉(𝐺’)∈𝑉(𝐺)$并且$𝐸(𝐺’ )∈𝐸(𝐺)$时,$𝐺’$是$𝐺$的一个子图
生成子图(Sub-graph) 当$𝐺’$是$𝐺$的子集,并且$𝑉(𝐺’ )=𝑉(𝐺)$时, $𝐺’$是$𝐺$的一个生成子图
度(Degree) 一个顶点𝑣的度是与它相连的边的数量,记作𝑑(𝑣)。$\sum_{\nu \in V}d(\nu)=2 \mid E \mid$
出度(In-degree) 出度为从该顶点出发的边的个数
入度(Out-degree) 入度为终点时该节点的边的个数
路径(Path) 路径经过的边数为𝑘,即路径长度为$𝑘$
简单路径(simple-path) 路径的所有顶点都不相同或只有起点$𝑣_0$和终点$𝑣_𝑘$两个顶点相同
圈(cycle) 在有向图中路径起点$𝑣_0$和终点$𝑣_𝑘$相同。若满足简单路径的条件则是一个简单圈。
距离 两个顶点之间的最短路径长度就是两点之间的距离

图的分类

  • 按边
类型 定义
简单图(simple graph) 既没有平行边,也没有自环
多重图(multi-graph) 有平行边的图
伪图(Pseudograph) 既有平行边的图,也有自环的图
完全图 每对顶点之间都有边的图是完全图

有的作者也允许多重图有自环
类型

  • 按路径
类型 定义
连通图 一个图中的每个顶点到其他顶点都有路径
强连通图 有向图满足该条件
弱连通图 有向图不连通,但是它的基础图连通

基础图: 边去掉方向的图

  • 按方向
    有向图与无向图

  • 按权重
    有权图与无权图

存储显示方式

邻接矩阵 adjacency matrices

邻接矩阵使用$|V|∗|V|$的二维数组来表示图。$g[i][j]$表示的是顶点$i$和顶点$j$的关系。

  • 无向图
    只需要知道顶点$i$和顶点$j$是否是相连的,因此我们只需要将$g[i][j]$和$g[j][j]$设置为1或是0表示相连或不相连即可。
    邻接矩阵
  • 有向图
    只需要知道是否有从顶点$i$到顶点$j$的边,因此如果顶点$i$有一条指向顶点$j$的边,那么$g[i][j]$就设为1,否则设为0。有向图与无向图不同,并不需要满足$g[i][j]=g[j][i]$
    邻接矩阵
  • 有权图
    在带权值的图中,g[i][j]表示的是顶点i到顶点j的边的权值。由于在边不存在的情况下,如果将g[i][j]设为0,就无法和权值为0的情况区分开来,因此选取适当的较大的常数INF(只要能和普通的权值区别开来就可以了),然后令g[i][j]=INF就好了。当然,在无向图中还是要保持g[i][j]=g[j][i]。在一条边上有多种不带权值的情况下,定义多个同样的|V|∗|V|数组,或者是使用结构体或类作为数组的元素,就可以和原来一样对图进行处理了。
    邻接矩阵

  • 优点
    很方便地判断任意两个顶点之间是否有边以及确定顶点的度

  • 缺点
    在这种表示法中扫描所有边至少需要O(n2)时间,因为必须检查矩阵中的n2−n个元素才能确定图中边的条数(邻接矩阵对角线上的n个元素都是0,因此不用检查。又因为无向图的邻接矩阵是对称的,实际只需检查邻接矩阵的一半元素)。
    通常把边很少的图成为稀疏图(sparse graphs)。如果用邻接矩阵表示稀疏图就会浪费大量内存空间

邻接表

  • 优点: 只需$\mathcal{O}(|V|+|E|)$的内存空间
    领接表
    1
    #define MAX_VERTICES 50 
    2
    typedef struct node *node-pointer; 
    3
    typedef struct node { 
    4
        int vertex; 
    5
        struct node *link; 
    6
    }; 
    7
    node_pointer graph[MAX_VERTICES]; 
    8
    int n=0;

链接多重表

在无向图的邻接表存储表示中,每一条边$(v_i,v_j)$
都表示为两项:一项在顶点vi 的邻接表中,而另一项在顶点 $v_j$ 的邻接表中。在多重表中,各链表中的结点可以被几个链表共享,此时图中的每一条边只对应于一个结点,而这个结点出现在该边所关联的两个顶点的每个邻接链表中。

1
typedef struct edge *edge-pointer 
2
typedef struct edge { 
3
    short int marked; 
4
    int vertex1; 
5
    int vertex2; 
6
    edge_pointer path1; 
7
    edge_pointer path2; 
8
};

操作

拓扑排序

最短路径

略……


参考资料: