考研数据结构重要知识点

喜欢ヅ旅行 2023-06-25 10:18 61阅读 0赞

### 文章目录 ###

*  数据结构
 *   *  逻辑结构与物理结构
     *   *  逻辑结构
         *  物理结构
     *  线性表
     *   *  链表操作
         *   *  code
     *  排序
     *   *  性质
         *  选择排序
         *   *  算法思想
             *  code
         *  希尔排序
         *   *  算法思想
             *  操作步骤
             *  code
         *  直接插入排序
         *   *  算法思想
             *  操作步骤
             *  code
         *  堆排序
         *  归并
         *  快速排序
     *  二叉树
     *   *  性质
         *  存储结构
         *   *  双亲表示法
             *   *  思想
                 *  结构
                 *  优缺点分析
             *  孩子表示法
             *   *  结构
                 *  优缺点分析
             *  孩子兄弟表示法
             *   *  结构
         *  二叉树的操作
         *  平衡二叉树
         *  树与森林
         *   *  树转化为二叉树
             *  森林转化为二叉树
             *  二叉树转化为树
             *  二叉树转化为森林
         *  B-树
         *   *  Def
     *  图算法
     *   *  概念
         *   *  连通图和非连通图
         *  性质
         *  邻接表
         *  三元组
         *  最短路径
         *  最小生成树
         *   *  Prim算法（适合稠密图）
             *   *  算法思想
                 *  code
             *  Kruskal算法（适合稀疏图）
             *   *  算法思想
                 *  操作步骤
                 *  code
         *  拓扑排序
         *  关键路径
         *   *  步骤
     *  查找
     *   *  kmp
         *   *  code

# 数据结构 #

## 逻辑结构与物理结构 ##

### 逻辑结构 ###

> 数据对象中数据元素之间的相互关系

1.  集合
2.  线性
3.  树形
4.  图形

### 物理结构 ###

> 数据的逻辑结构在计算机中的存储形式

1.  顺序
2.  链式

## 线性表 ##

### 链表操作 ###

#### code ####

typedef struct Node {
        
        int data;
        struct Node *next;
    } Node;
    
    int getElem(Node *L, int i) {
        
        Node *p;
        p = L->next;
        int j = 1;
        while (p && j < i) {
        
            p = p->next;
            j++;
        }
        if (p == nullptr || j > i)
            return -1;
        return p->data;
    }
    
    int insert(Node *L, int i, int target) {
        
        int j = 1;
        Node *p;
        p = L;
        while (p && j < i) {
        
            p = p->next;
            j++;
        }
        if (!p || j > i) {
        
            return -1;
        }
        Node *tmp = (Node *) malloc(sizeof(Node));
        tmp->data = target;
        tmp->next = p->next;
        p->next = tmp;
        return 0;
    }
    
    int listDelete(Node *L, int i) {
        
        int j = 1;
        Node *p;
        p = L;
        while (p && j < i) {
        
            p = p->next;
            j++;
        }
        if (p->next == nullptr || j > i)
            return -1;
        Node *tmp = p->next;
        p->next = tmp->next;
        free(tmp);
        return 0;
    }
    
    int createListHead(Node *L, int n) {
        //头插法
        Node *p;
        int i = 0;
        L = (Node *) malloc(sizeof(Node));
        L->next = nullptr;
        srand(time(0));
        for (int i = 0; i < n; i++) {
        
            p = (Node *) malloc(sizeof(Node));
            p->data = rand() % 100;
            p->next = L->next;
            L->next = p;
        }
        return 0;
    }
    
    int createListTail(Node *L, int n) {
        //尾插法
        Node *p, *tmp;
        srand(time(0));
        L = (Node *) malloc(sizeof(Node));
        L->next = nullptr;
        p = L;
        for (int i = 0; i < n; i++) {
        
            tmp = (Node *) malloc(sizeof(Node));
            tmp->data = rand() % 100;
            p->next = tmp;
            p = tmp;
        }
        p->next = nullptr;
        return 0;
    }
    
    int reverseList(Node *L) {
        
        Node *p, *q, *r;
        if (L->next != nullptr)
            p = L->next;
        else
            return -1;
        L->next = nullptr;
        q = nullptr;
        while (p) {
        
            r = p->next;
            p->next = q;
            q = p;
            p = r;
        }
        L->next = p;
        return -1;
    }

## 排序 ##

### 性质 ###

*  元素的**移动次数**与关键字的初始排列次序无关的是：**基数排序**
 *  元素的**比较次数**与初始序列无关是：**选择排序**
 *  算法的**时间复杂度**与初始序列无关的是：**直接选择排序**
 *  **选择排序、快速排序、希尔排序、堆排序**不是稳定的排序算法，而**冒泡排序、插入排序、归并排序和基数排序**是稳定的排序算法
 *  总排序趟数与初始状态无关的有：（除了快速排序和优化的冒泡，其他都是）
 *  算法复杂度与初始状态无关的有：堆排序、归并排序、选择排序、基数排序
 *  元素总比较次数与初始状态无关的有：选择排序、基数排序
 *  元素总移动次数与初始状态无关的有：归并排序、基数排序。

### 选择排序 ###

#### 算法思想 ####

选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。  
![在这里插入图片描述][20191228110541524.gif]

#### code ####

public class Selection {
        
        public static void sort(int[] arr){
        
            for(int i=0; i<arr.length-1; i++) {
        
                int minPos = i;
                for (int j = i; j < arr.length; j++) {
        
                    if (arr[j] < arr[minPos]) {
        
                        minPos = j;//找出当前最小元素的位置
                    }
                }
                if(arr[minPos]!=arr[i]) {
        
                    swap(arr,minPos,i);
                }
            }
        }
        public static void swap(int[] arr,int a,int b){
        
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

### 希尔排序 ###

#### 算法思想 ####

希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

#### 操作步骤 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTI2NjMz_size_16_color_FFFFFF_t_70]

初始时，有一个大小为 10 的无序序列。

1.  在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
2.  接下来，按照直接插入排序的方法对每个组进行排序。  
    在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
3.  按照直接插入排序的方法对每个组进行排序。
4.  在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
5.  按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

#### code ####

public static void shellSort(int a[]) {
        
        int d= a.length;//gap的值
        while (true){
        
            d = d/ 2;//每次都将gap的值减半
            for (int x = 0; x< d; x++) {
        //对于gap所分的每一个组
                for (int i = x+ d; i < a.length; i= i + d) {
        //行插入排序
                    int temp= a[i];
                    int j;
                    for (j= i - d; j>= 0 && a[j] > temp;j = j - d){
        
                        a[j+ d] = a[j];
                    }
                    a[j+ d] = temp;
                }
            }
            if (d==1) {
        //gap==1，跳出循环
                    break;
            }
        }
    }

### 直接插入排序 ###

#### 算法思想 ####

将数组的第一个数认为是有序数组，从后往前（从前往后）扫描该有序数组，把数组中其余n-1个数，根据数值的大小，插入到有序数组中，直至数组中的所有数有序排列为止。这样的话，n个元素需要进行n-1趟排序！！！  
![在这里插入图片描述][20191228110653829.gif]

#### 操作步骤 ####

4个数字4,6,7,5进行从大到小的排序  
把第一个数4插入到空的有序数组中的第一个位置上，得到新数字序列4；

1.  从后往前扫描有序数组，将第二个数字6和有序数组中的4进行比较，6大于4，此时将4后移一个位置。此时已经扫描完有序数组中的数，将6插入到4的前面（有序数组的第一个位置），得到新数字序列6,4；
2.  从后往前扫描有序数组，先将第三个数字7和有序数组中的4进行比较，7大于4，此时将4后移一个位置；再将7和有序数组中的6进行比较，7大于6，此时将6后移一个位置。此时已经扫描完有序数组中的数，将7插入到6的前面（有序数组的第一个位置），得到新数字序列7,6,4；
3.  从后往前扫描有序数组，先将第四个数字5和有序数组中的4进行比较，5大于4，此时将4后移一个位置；再将5和有序数组中的6进行比较，5小于6，由于有序数组就按照从大到小排列的，此时直接把5插入到4的前面即可！不需要再和7进行比较！最后，得到新数字序列7,6

#### code ####

#include<iostream>
    #include<cstdio>
    using namespace std;
    #define N 5
    int a[N];//有序数组
    
    int main ( ) {
        
        int i, k, x;
        for (i=0; i<N; i++) {
        
            scanf ("%d", &x);
            for ( k=i; k>0; k-- ) {
                 /* 从后向前比较 */
                if ( a[k-1] > x )    //x前面的数比它大
                    a[k]=a[k-1];         /* 将大数向后移动*/
                else
                    break; /* 找到插入的位置，退出 */
            }
            a[k] = x;  /* 完成插入操作 */
        }
        for (i=0; i<N; i++)
            printf("%d ", a[i]);
        return 0;
    }

### 堆排序 ###

int h[1000];
    int n = 1000;
    
    void siftDown(int i) {
        
        int t, flag = 0;
        while (i * 2 < n && flag == 0) {
        
            if (h[i] < h[i * 2]) {
        
                t = i * 2;
            } else
                t = i;
            if (i * 2 + 1 <= n) {
        
                if (h[t] < h[i * 2 + 1]) {
        
                    t = i * 2 + 1;
                }
            }
            if (t != i) {
        
                int tmp = h[t];
                h[t] = h[i];
                h[i] = tmp;
                i = t;
            } else
                flag = 1;
        }
    }
    
    void siftUp(int i) {
        
        int flag = 0;
        if (i == 1)
            return;
        while (i != 1 && flag == 0) {
        
            if (h[i] > h[i / 2]) {
        
                int tmp = h[i];
                h[i] = h[i / 2];
                h[i / 2] = tmp;
            } else
                flag = 1;
            i = i / 2;
        }
    }
    
    void create() {
        
        for (int i = n / 2; i >= 1; i--) {
        
            siftDown(i);
        }
    }
    
    int deleteMax() {
        
        int t = h[1];
        h[1] = h[n];
        n--;
        siftDown(1);
        return t;
    }
    
    void heapSort() {
        
        while (n > 1) {
        
            int tmp = h[1];
            h[1] = h[n];
            h[n] = tmp;
            n--;
            siftDown(1);
        }
    }

### 归并 ###

void merge(int in[], int out[], int start, int medium, int end) {
        
        int i = start, j = medium, k = 0;
        while (i <= medium && j <= end) {
        
            if (in[i] < in[j]) {
        
                out[k] = in[i];
                i++;
            } else {
        
                out[k] = in[j];
                j++;
            }
            k++;
        }
        while (i <= medium) {
        
            out[k] = in[i];
            i++;
            k++;
        }
        while (j <= end) {
        
            out[k] = in[j];
            k++;
            j++;
        }
    
    }
    
    void mSort(int in[], int out[], int start, int end) {
        
        int tmp[MAXSIZE];
        if (start == end) {
        
            out[start] = in[start];
        } else {
        
            int medium = (start + end) / 2;
            mSort(in, tmp, start, medium);
            mSort(in, tmp, medium + 1, end);
            merge(tmp, out, start, medium, end);
        }
    }
    
    void mergeSort(int L[]) {
        
        mSort(L, L, 1, n);
    }
    void mergePass(int in[], int out[], int width, int end) {
        
        int i = 1;
        int j;
        while (i < n - 2 * width + 1) {
        
            merge(in, out, i, i + width - 1, i + 2 * width - 1);
            i = i + 2 * width;
        }
        if (i < n - width + 1) {
        
            merge(in, out, i, i + width - 1, n);
        } else {
        
            for (j = i; j <= n; j++) {
        
                out[j] = in[j];
            }
        }
    }
    
    //非递归
    void mergeSort2(int in[]) {
        
        int tmp[MAXSIZE];
        int k = 1;
        while (k < n) {
        
            mergePass(in, tmp, k, n);
            k = 2 * k;
            mergePass(tmp, in, k, n);
            k = 2 * k;
        }
    }

### 快速排序 ###

int partition(int L[], int low, int high) {
        
        int key = L[low];
        while (low < high) {
        
            while (low < high && L[high] >= key) {
        
                high--;
            }
            while (low < high && L[low] <= key) {
        
                low++;
            }
            int tmp = L[low];
            L[low] = L[high];
            L[high] = tmp;
        }
        return low;
    }
    
    void qsort(int L[], int low, int high) {
        
        int pivot;
        if (low < high) {
        
            pivot = partition(L, low, high);
            qsort(L, low, pivot - 1);
            qsort(L, pivot + 1, high);
        }
    }
    
    void quickSort(int L[]) {
        
        qsort(L, 1, n);
    }

## 二叉树 ##

### 性质 ###

1.   **n 0 = n 2 + 1 n\_0=n\_2+1 n0=n2\+1**
2.  二叉树的第i层上最多有 2 i − 1 2^\{i-1\} 2i−1结点
3.  高度（或深度）为i的二叉树最多有 2 i − 1 2^\{i-1\} 2i−1结点
4.  给定n个结点，能够成 h ( n ) = C 2 n n n + 1 h(n)=\\frac\{C\_\{2n\}^n\}\{n+1\} h(n)=n\+1C2nn种不同

### 存储结构 ###

[资料来源][Link 1]

#### 双亲表示法 ####

##### 思想 #####

每个结点只有一个双亲，所以选择顺序存储占主要  
以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点位置的指针域  
![在这里插入图片描述][2019122811072847.png]

##### 结构 #####

/*树的双亲表示法结点结构定义*/
    #define MAX_TREE_SIZE 100
    
    typedef int TElemType;
    
    typedef struct PTNode    //结点结构
    {
        
        TElemType data;    //结点数据
        int parent;        //双亲位置
    }PTNode;
    
    typedef struct //树结构
    {
        
        PTNode nodes[MAX_TREE_SIZE];    //结点数组
        int r, n;    //r是根位置，n是结点数
    }PTree;

##### 优缺点分析 #####

**优点**：parent指针域指向数组下标，所以找双亲结点的时间复杂度为O(1),向上一直找到根节点也快  
**缺点**：由上向下找就十分慢，若要找结点的孩子或者兄弟，要遍历整个树

#### 孩子表示法 ####

![在这里插入图片描述][20191228110744954.png]

##### 结构 #####

/*树的孩子表示法结点结构定义*/
    #define MAX_TREE_SIZE 100
    
    typedef int TElemType;
    
    typedef struct PTNode    //结点结构
    {
        
        TElemType data;    //结点数据
        int child1;    //孩子1结点
        int child2;    //孩子2结点
        int child3;    //孩子3结点
    }PTNode;
    
    typedef struct //树结构
    {
        
        PTNode nodes[MAX_TREE_SIZE];    //结点数组
        int r, n;    //r是根位置，n是结点数
    }PTree;

##### 优缺点分析 #####

**缺点**：占用了大量不必要的孩子域空指针

#### 孩子兄弟表示法 ####

任意一棵树，他的结点的第一个孩子如果存在就是唯一结点，他的右兄弟如果存在，也是唯一的，因此，我们设置两个指针，分别指向该结点的第一个孩子和该结点的右兄弟  
![在这里插入图片描述][20191228110807460.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTI2NjMz_size_16_color_FFFFFF_t_70 1]

##### 结构 #####

typedef int TElemType;
    
    typedef struct CSNode
    {
        
        TElemType data;
        struct CSNode* firstchild, *rightsib;
    }CSNode,*CSTree;

### 二叉树的操作 ###

typedef struct BiNode {
        
        char data;
        struct BiNode *lChild, *rChild;
    } BiNode, *BiTree;
    
    void createBiTree(BiTree *T) {
        
        char ch;
        scanf("%c", &ch);
        if (ch == '#') {
        
            *T = nullptr;
        } else {
        
            *T = (BiTree) malloc(sizeof(BiNode));
            if (!*T)
                exit(0);
            (*T)->data = ch;
            createBiTree(&(*T)->lChild);
            createBiTree(&(*T)->rChild);
        }
    }
    
    void preOrderTraverse(BiTree T) {
        
        if (T == nullptr)
            return;
        printf("%c", T->data);
        preOrderTraverse(T->lChild);
        preOrderTraverse(T->rChild);
    }
    
    void inOrderTraverse(BiTree T) {
        
        if (T == nullptr)
            return;
        preOrderTraverse(T->lChild);
        printf("%c", T->data);
        preOrderTraverse(T->rChild);
    }
    
    void postOrderTraverse(BiTree T) {
        
        if (T == nullptr)
            return;
        preOrderTraverse(T->lChild);
        preOrderTraverse(T->rChild);
        printf("%c", T->data);
    }
    
    int depth(BiTree T) {
        
        if (T == nullptr)
            return 0;
        return 1 + std::max(depth(T->lChild), depth(T->rChild));
    }
    
    void exchange(BiTree &T) {
        
        if (T == nullptr)
            return;
        BiTree tmp;
        tmp = T->rChild;
        T->rChild = T->lChild;
        T->lChild = tmp;
        exchange(T->lChild);
        exchange(T->rChild);
    }

### 平衡二叉树 ###

[blog][]

### 树与森林 ###

#### 树转化为二叉树 ####

1.  加线。在所有兄弟结点之间加连线
2.  去线。对树中每个节点，只保留与第一个孩子的连线
3.  层次调整

#### 森林转化为二叉树 ####

1.  把每棵树转化为二叉树
2.  第一课二叉树不动，从第二棵树开始，依次把根节点作为前一棵树的右孩子

#### 二叉树转化为树 ####

1.  加线。每个结点左孩子的n个右孩子作为此节点结点作为此节点的孩子。
2.  删除原二叉树所有结点与其右孩子的连线
3.  调整层次

#### 二叉树转化为森林 ####

1.  从根节点开始，若右孩子存在，则把右孩子结点的连线删除，再看分离后的二叉树。。。
2.  将每棵二叉树转化为树

### B-树 ###

#### Def ####

1.  树中每个结点至多有m 棵子树
2.  若根结点不是叶子结点，则至少有两棵子树
3.  除了根结点和叶子结点，其他结点至少有\[l(m / 2)（代表是取上限的函数）\]个孩子；
4.  若根结点不是叶子结点时，则至少有两个孩子（除了没有孩子的根结点
5.  所有的叶子结点都出现在同一层中，叶子结点不包含任何关键字信息；
6.  有j个孩子的非叶结点恰好有j-1个关键码，关键码按递增次序排列

## 图算法 ##

### 概念 ###

#### 连通图和非连通图 ####

*  如果无向图 G 中任意一对顶点都是连通的，则称此图是**连通图**（connected graph）；
 *  若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为**强连通图**。
 *  相反，如果一个无向图不是连通图，则称为**非连通图**（disconnected graph）
 *  若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为**强连通分量**

### 性质 ###

*  n个顶点的有向图，强连通需要ｎ条边，构成环　单向连通、弱连通需要ｎ-1条边，构成一条链
 *  判断是否有环方法：  
    1.拓扑排序  
    2.深度优先遍历  
    一般来说，最短路径是不行的

### 邻接表 ###

typedef struct EdgeNode {
        
        int nodeId;
        int weight;
        struct EdgeNode *next;
    } EdgeNode;
    typedef struct VertNode {
        
        char data;
        EdgeNode *firstEdge;
    } VertNode, AdjList[999];
    typedef struct {
        
        AdjList adjList;
        int numNode, numEdge;
    } GraphAdjList;
    
    void createALGraph(GraphAdjList *G) {
        
        int i, j, k;
        EdgeNode *e;
        scanf("%d %d", &G->numNode, &G->numEdge);
        for (i = 0; i < G->numNode; i++) {
        //顶点信息表
            scanf("%c", &G->adjList[i].data);
            G->adjList[i].firstEdge = nullptr;
        }
        for (k = 0; k < G->numEdge; k++) {
        
            scanf("%d %d", &i, &j);//顶点信息表
            e = (EdgeNode *) malloc(sizeof(EdgeNode));
            e->nodeId = j;
            e->next = G->adjList[i].firstEdge;
            G->adjList[i].firstEdge = e;
            e = (EdgeNode *) malloc(sizeof(EdgeNode));
            e->nodeId = i;
            e->next = G->adjList[j].firstEdge;
            G->adjList[j].firstEdge = e;
        }
    }

### 三元组 ###

#define MAXSIZE 12500
    typedef struct {
        
        int colId, rowId;
        int data;
    } Triple;
    typedef union {
        
        Triple arrow[MAXSIZE + 1];
        int sumCol, sumRow, length;
    } TSMatrix;
    
    int transposeSMatrix(TSMatrix input, TSMatrix &res) {
        
        res.sumRow = input.sumCol;
        res.sumCol = input.sumRow;
        res.length = input.length;
        if (input.length == 0)
            return 0;
        int index = 1;
        for (int col = 1; col <= input.sumCol; col++) {
        
            for (int p = 1; p <= input.length; p++) {
        
                if (input.arrow[p].colId == col) {
        
                    res.arrow[index].colId = input.arrow[p].rowId;
                    res.arrow[index].rowId = input.arrow[p].colId;
                    res.arrow[index].data = input.arrow[p].data;
                }
            }
        }
        return 0;
    }
    
    int quickTransposeSMatrix(TSMatrix input, TSMatrix &res) {
        
        res.sumRow = input.sumCol;
        res.sumCol = input.sumRow;
        res.length = input.length;
        if (input.length == 0)
            return 0;
        int num[MAXSIZE], colPos[MAXSIZE];
        for (int col = 1; col <= input.sumCol; col++)
            num[col] = 0;
        for (int i = 1; i <= input.length; i++)
            num[input.arrow[i].colId]++;
        colPos[1] = 1;
        for (int i = 2; i <= input.length; i++)
            colPos[i] = colPos[i - 1] + num[i - 1];
        for (int i = 1; i < input.length; i++) {
        
            int col_id = input.arrow[i].colId;
            int q = colPos[col_id];
            res.arrow[q].rowId = input.arrow[i].colId;
            res.arrow[q].colId = input.arrow[i].rowId;
            res.arrow[q].data = input.arrow[i].data;
            colPos[col_id]++;
        }
        return 0;
    }

### 最短路径 ###

int e[999][999];
    int n = 100, m = 99;//顶点、边的数量
    int inf = 99999999;
    
    int floyd() {
        //适用于稠密图，可以解决负权边
        for (int k = 0; k < n; k++) {
        
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (e[i][j] > e[i][k] + e[k][j])
                        e[i][j] = e[i][k] + e[k][j];
                }
            }
        }
    }
    
    int dijkstra() {
        //适用于稠密图，不能解决负权边
        int dis[999];
        int book[999];
        int u = 1;
        for (int i = 1; i <= n; i++) {
        
            dis[i] = e[1][i];
            book[i] = 0;
        }
        for (int i = 0; i < n - 1; i++) {
        
            int min = inf;
            for (int j = 1; j <= n; j++) {
        
                if (book[j] == 0 && dis[j] < min) {
        
                    min = dis[j];
                    u = j;
                }
            }
            book[u] = 1;
            for (int v = 1; v <= n; v++) {
        
                if (e[u][v] < inf) {
        
                    if (dis[v] > dis[u] + e[u][v]) {
        
                        dis[v] = dis[u] + e[u][v];
                    }
                }
            }
        }
        return 0;
    }
    
    int bellman() {
        //适用于稀疏图，可以解决负权边
        int dis[999];
        int u[99], v[99], w[99];
        for (int i = 1; i <= n; i++) {
        
            dis[i] = inf;
        }
        dis[1] = 0;
        for (int k = 1; k <= n - 1; k++) {
        
            for (int i = 1; i <= m; i++) {
        
                if (dis[v[i]] > dis[u[i]] + w[i]) {
        
                    dis[v[i]] = dis[u[i]] + w[i];
                }
            }
        }
    }

### 最小生成树 ###

#### Prim算法（适合稠密图） ####

##### 算法思想 #####

将无向连通图 G G G中所有顶点 V V V分成两个顶点集合 V A V\_A VA和 V B V\_B VB。  
在计算过程中 V A V\_A VA中的点为已经选好连接入生成树的点，否则属于 V B V\_B VB。  
最开始的时候 V A V\_A VA只包含任意选取的图 G G G中的一个点 u u u，其余的点属于 V B V\_B VB，每次添加一个 V B V\_B VB中的点到 V A V\_A VA，该点是集合 V B V\_B VB到集合 V A V\_A VA中距离最小的一个点。直到 V V V个顶点全部属于 V A V\_A VA

##### code #####

const int maxn=105;
    const int INF=0x7fffffff/2;
    int vis[maxn];//判断是否标记
    int p[maxn][maxn];//存图
    int n,m,ans=0;
    struct edge{
        //保存边的情况，to为通往的边
        int to;
        int v;//权值
        friend bool operator <(const edge& x,const edge& y){
        
            return x.v>y.v;//优先队列即最小堆
        }
    }now;
    priority_queue<edge>q;
    void prim(int key){
        
        vis[key]=1;//标记起始点
        while(!q.empty())q.pop();
        for(int i=0;i<n-1;i++){
        
            for(int j=0;j<n;j++){
        //记入新加入点的情况
                if(!vis[j]){
        //没标记过的点就加入
                    now.to=j;
                    now.v=p[key][j];
                    q.push(now);
                }
            }
            while(!q.empty() && vis[q.top().to])
                q.pop();
            if(q.empty())
                break;
            now=q.top();
            key=now.to;
            ans+=now.v;//累加最小边的权值
            vis[key]=1;
            q.pop();
        }
    }
    int main(){
        
        memset(vis,0,sizeof(vis));
        for(int i=0;i<maxn;i++)
            for(int j=0;j<maxn;j++)
                p[i][j]=INF;
        scanf("%d%d",&n,&m);//输入n个顶点,m条边
        while(m--){
        
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            p[u][v]=w;
            p[v][u]=w;
        }
        prim(0);
        printf("%d\n",ans);
        return 0;
    }

#### Kruskal算法（适合稀疏图） ####

##### 算法思想 #####

它是将边按权值排序，每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中，反复操作，直到加入了n-1条边。

##### 操作步骤 #####

1.  将G中的边按权值从小到大快排。
2.  按照权值从小到大依次选边。若当前选取的边加入后使生成树T形成环，则舍弃当前边，否则标记当前边并计数
3.  重复2的操作，直到生成树T中包含n-1条边，否则当遍历完所有边后，选取不到n-1条边，表示最小生成树不存在。

##### code #####

const int maxn=1e5+5;
    int n,m,pre[maxn],ans=0,flag=1;
    struct edge{
        
        int x,y;//边的两个顶点
        int z;//边的权值
    }a[maxn];
    bool cmp(edge a,edge b){
        
        return a.z<b.z;
    }
    int find1(int x){
        
        int r=x;
        while(r!=pre[r])
            r=pre[r];
        int i=x,j;
        while(i!=r){
        
            j=pre[i];
            pre[i]=r;
            i=j;
        }
        return r;
    }
    void Kruskal(){
        
        int f1,f2,k=0;
        for(int i=1;i<=m;i++){
        
            f1=find1(a[i].x);
            f2=find1(a[i].y);
            if(f1!=f2){
        
                ans+=a[i].z;
                pre[f2]=f1;//合并不相同的两个集合
                k++;
                if(k==n-1)break;
            }
        }
        if(k<n-1){
        
            flag=0;
            return;
        }
    }
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            pre[i]=i;
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        sort(a+1,a+m+1,cmp);
        Kruskal();
        if(flag)printf("%d\n",ans);
        return 0;
    }

### 拓扑排序 ###

#define MAXVEX 1000
    typedef struct EdgeNode {
        
        int node;
        int weight;
        struct EdgeNode *next;
    } EdgeNode;
    typedef struct VertexNode {
        
        int in;
        int data;
        EdgeNode *firstEdge;
    } VertexNode, AdjList[MAXVEX];
    typedef struct {
        
        AdjList adjList;
        int numNode, numEdge;
    } graphAdjList, *GraphAdjList;
    
    int topologicalSort(GraphAdjList GL) {
        
        EdgeNode *e;
        int getTop;
        int top = 0;
        int count = 0;
        int stack[MAXVEX];
        for (int i = 0; i < GL->numNode; i++) {
        
            if (GL->adjList[i].in == 0) {
        
                top++;
                stack[top] = i;
            }
        }
        while (top != 0) {
        
            getTop = stack[top];
            top--;
            printf("%d ->", GL->adjList[getTop].data);
            count++;
            for (e = GL->adjList[getTop].firstEdge; e != nullptr; e = e->next) {
        
                int id = e->node;
                GL->adjList[id].in--;
                if (GL->adjList[id].in == 0) {
        
                    top++;
                    stack[top] = id;
                }
            }
        }
        if (count < GL->numNode)//存在环
            return -1;
        return 0;
    }

### 关键路径 ###

[blog][blog 1]

**关键路径**：AOE-网中，从起点到终点最长的路径的长度  
**关键活动**：关键路径上的边  
![在这里插入图片描述][20191228110916276.png]

#define MAXVEX 1000
    #define inf 99999
    int etv[MAXVEX], ltv[MAXVEX];
    int stack2[MAXVEX];
    int top2;
    typedef struct EdgeNode {
        
        int node;
        int weight;
        struct EdgeNode *next;
    } EdgeNode;
    typedef struct VertexNode {
        
        int in;
        int data;
        EdgeNode *firstEdge;
    } VertexNode, AdjList[MAXVEX];
    typedef struct {
        
        AdjList adjList;
        int numNode, numEdge;
    } graphAdjList, *GraphAdjList;
    
    int TopologicalSort(GraphAdjList GL) {
        
        EdgeNode *e;
        int getTop;
        int top = 0;
        int count = 0;
        int stack[MAXVEX];
        for (int i = 0; i < GL->numNode; i++) {
        
            if (GL->adjList[i].in == 0) {
        
                top++;
                stack[top] = i;
            }
            etv[i] = 0;
        }
        while (top != 0) {
        
            getTop = stack[top];
            top--;
            count++;
            top2++;
            stack2[top2] = getTop;
            for (e = GL->adjList[getTop].firstEdge; e != nullptr; e = e->next) {
        
                int id = e->node;
                GL->adjList[id].in--;
                if (GL->adjList[id].in == 0) {
        
                    top++;
                    stack[top] = id;
                }
                if ((etv[getTop] + e->weight) > etv[id])
                    etv[id] = etv[getTop] + e->weight;
            }
        }
        if (count < GL->numNode)
            return -1;
        return 0;
    }
    
    void CriticalPath(GraphAdjList GL) {
        
        EdgeNode *e;
        int getTop;
        int ete, lte;
        TopologicalSort(GL);
        for (int i = 0; i < GL->numNode; i++) {
        
            ltv[i] = inf;
        }
        while (top2 != 0) {
        
            getTop = stack2[top2];
            top2--;
            for (e = GL->adjList[getTop].firstEdge; e != nullptr; e = e->next) {
        
                int id = e->node;
                if (ltv[getTop] > ltv[id] - e->weight)
                    ltv[getTop] = ltv[id] - e->weight;
            }
        }
        for (int i = 0; i < GL->numNode; i++) {
        
            for (e = GL->adjList[i].firstEdge; e != nullptr; e = e->next) {
        
                int id = e->node;
                ete = etv[i];
                lte = ltv[id] - e->weight;
                if (ete == lte) {
        
                    printf("<%d,%d> length: %d", GL->adjList[i].data, GL->adjList[id].data, e->weight);
                }
            }
        }
    }

#### 步骤 ####

1.  输入顶点数和边数，已经各个弧的信息建立图
2.  从源点v1出发，令ve\[0\]=0;按照拓扑序列往前求各个顶点的ve。如果得到的拓扑序列个数小于网的顶点数n，说明我们建立的图有环，无关键路径，直接结束程序
3.  从终点vn出发，令vl\[n-1\]=ve\[n-1\]，按逆拓扑序列，往后求其他顶点vl值
4.  根据各个顶点的ve和vl求每个弧的e（i）和l（i），如果满足e（i）=l（i），说明是关键活动。

## 查找 ##

### kmp ###

#### code ####

void getNext(char *T, int *next) {
        
        int i, j;
        i = 1;
        j = 0;
        next[1] = 0;
        while (i < T[0]) {
        
            if (j == 0 || T[i] == T[j]) {
        
                i++;
                j++;
                next[i] = j;
            } else {
        
                j = next[j];
            }
        }
    }
    
    void getNextVal(char T[], int *nextVal) {
        //改进算法
        int i, j;
        i = 1;
        j = 0;
        nextVal[1] = 0;
        while (i < T[0]) {
        
            if (j == 0 || T[i] == T[j]) {
        
                i++;
                j++;
                if (T[i] != T[j])
                    nextVal[i] = j;
                else
                    nextVal[i] = nextVal[j];
            } else
                j = nextVal[j];
        }
    }
    
    int indexKMP(char s[], char T[], int pos) {
        
        int i = pos;
        int j = 1;
        int next[255];
        getNext(T, next);
        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;
    }

[20191228110541524.gif]: https://img-blog.csdnimg.cn/20191228110541524.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTI2NjMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191228110628355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTI2NjMz,size_16,color_FFFFFF,t_70
[20191228110653829.gif]: https://img-blog.csdnimg.cn/20191228110653829.gif
[Link 1]: https://www.cnblogs.com/ssyfj/p/9459887.html
[2019122811072847.png]: https://img-blog.csdnimg.cn/2019122811072847.png
[20191228110744954.png]: https://img-blog.csdnimg.cn/20191228110744954.png
[20191228110807460.png]: https://img-blog.csdnimg.cn/20191228110807460.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTI2NjMz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191228110827171.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTI2NjMz,size_16,color_FFFFFF,t_70
[blog]: https://blog.csdn.net/isunbin/article/details/81707606
[blog 1]: https://www.jianshu.com/p/1857ed4d8128
[20191228110916276.png]: https://img-blog.csdnimg.cn/20191228110916276.png