第一章

数据结构

算法

  • 算法的好坏

  • 复杂度分析小窍门

第二章

线性表

一、 多项式的表示

  • 顺序储存结构直接表示

  • 顺序储存结构表示非零项

    每个多项式可以看成系数和指数二元组的集合,按指数大小有序储存

  • 链式结构储存非零项

    链表中每个节点储存一个非零项，每个节点包括两个数据域和一个指针域

二、 什么是线性表

由同类型数据元素构成有序序列的线性结构

  • 线性表的顺序存储实现

    利用数组的连续存储空间顺序存放线性表的各元素

    class List {
public:
    int data[MAXSIZE];
    int last; //数组的最后一位数的index

    List() : last(-1) {}
};

    • 查找

      int indexOf(int val) {
    int i = 0;
    while (i <= last && val != data[i]) {
        i++;
    }
    if (i > last) {
        return -1; // 如果没找到，返回-1
    } else {
      return i; // 如果找到，则返回i
    }
}

    • 添加

      /**
 * 第 i (1≤i≤n+1)个位置上插入一个值为val的新元素)
 */
void add(int i, int val) {
    if (last == MAXSIZE - 1) {
        printf("表满");
        return;
    }
    if (i < 1 || i > last + 2) {
        printf("位置不合法");
        return;
    }

    for (int j = last; j >= i - 1; j--) {
        data[j + 1] = data[j];  //后移腾出位置
    }

    data[i - 1] = val;
    last++;
}

    • 删除

      /**
 * 删除表的第 i (1≤i≤n)个位置上的元素)
 */
void remove(int i) {
    if (i < 1 || i > last + 1) {
        printf("位置不合法");
        return;
    }
    for (int j = i; j <= last; j++) {
        data[j - 1] = data[j];
    }
    last--;
}

  • 线性表的链式存储实现

    不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系

    class Node {
public:
    int data;
    Node *next;

    Node(int data) : data(data), next(nullptr) {}
};

class List {
public:
    Node *head;
    int size;

    List() : head(nullptr), size(0) {}
};

    • 长度

      int length(List &list) {
    int size = 0;
    Node *cur = list.head;
    while (cur != nullptr) {
        cur = cur->next;
        size++;
    }
    return size;
}

    • 添加节点

      /**
 * 插入到index(0<=index<=size)位置处
 * @param list
 * @param index
 * @param data
 */
void add(int index, int data) {
    Node *cur = head;
    Node *node = new Node(data);
    if (index < 0 || index > size) {
        return;
    }

    size++;
    if (index == 0) {
        node->next = head;
        head = node;
        return;
    }

    while (--index) {
        cur = cur->next;
    }
    node->next = cur->next;
    cur->next = node;
}

    • 删除节点

      /**
 * 删除index位置处的节点
 */
void remove(int index) {
    if (index < 0 || index > size - 1) {
        return;
    }

    if (index == 0) {
        head = head->next;
        size--;
        return;
    }

    Node *cur = head;
    while (--index) {
        cur = cur->next;
    }
    cur->next = cur->next->next;
    size--;
}

    • 根据index获取值

      int get(int index) {
    if (index < 0 || index >= size) {
        throw "越界";
    }
    Node *cur = head;

    while (index--) {
        cur = cur->next;
    }
    return cur->data;
}

    • 根据值获取它的位置

      int indexOf(int val) {
    int index = -1;
    Node *cur = head;
    while (cur != nullptr) {
        index++;
        if (cur->data == val) {
            return index;
        }
        cur = cur->next;
    }
    return -1;
}

三、 广义表

四、多重链表

堆栈

堆栈是具有一定操作约束的线性表，只在一端做插入，删除
Last In First Out（LIFO）后入先出

  • 栈的顺序存储实现

    栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

    	class Stack{
	public:
	    int data[MAXSIZE];
	    int top;

	    Stack() : top(-1) {}
	};

    • 入栈

      void push(int val) {
    if (top == MAXSIZE - 1) {
        return;
    }
    data[++top] = val;
}

    • 出栈

      int pop() {
    if (top == -1) {
        throw "栈为空";
    } else {
        return data[top--];
    }
}

    用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功

    一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。

    	class Stack {
	public:
	    int data[MAXSIZE];
	    int left, right;

	    Stack() : left(-1), right(MAXSIZE) {}

	    /**
	     * @param val 要插入的数据
	     * @param tag 要插入的栈的类型，1为左边的，2为右边的
	     */
	    void push(int val, int tag) {
	        if (right - left == 1) {
	            printf("栈满");
	            return;
	        }
	        if (tag == 1) {
	            data[++left] = val;
	        } else if (tag == 2) {
	            data[--right] = val;
	        }
	    }

	    int pop(int tag) {
	        if (tag == 1) {
	            if (left == -1) {
	                return -1;
	            } else {
	                return data[left--];
	            }
	        } else {
	            if (right == MAXSIZE) {
	                return -1;
	            } else {
	                return data[right++];
	            }
	        }
	    }
	};

  • 堆栈的链式存储实现

    栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行

    class Node {
public:
    int data;
    Node *next;

    Node(int data) : data(data), next(nullptr) {}
};

class Stack {
public:
    Node *head;
    int size;

    Stack() : head(nullptr), size(0) {}

    void push(int val) {
        Node *node = new Node(val);
        node->next = head;
        head = node;
        size++;
    }

    int pop() {
        if (size == 0) {
            printf("栈空");
            return -1;
        }
        int res = head->data;
        head = head->next;
        size--;
        return res;
    }
};

队列

具有一定操作约束的线性表

插入和删除操作：只能在一端插入，而在另一端删除

先进先出：FIFO

  • 队列的顺序存储实现(顺环队列)

    队列的顺序存储结构通常由一个一维数组和一个记录队列头元 素位置的变量front以及一个记录队列尾元素位置的变量rear组成

class Queue {
public:
      int data[MAXSIZE];
      int front;
      int rear;

      Queue() : front(0), rear(0) {}
  
      void push(int val) {
          //rear+1等于front则表示还余一个空位，这里我们不使用
          if ((rear + 1) % MAXSIZE == front) {
              printf("队列满");
            	return;
          }
  
          rear = (rear + 1) % MAXSIZE;
          data[rear] = val;
      }
  
      int pop() {
          //若rear等于front，表示队列为空
          if (rear == front) {
            throw "队列为空";
          }
  
          front = (front + 1) % MAXSIZE;
          return data[front];
	    }
	};

  • 队列的链式存储实现

    class Node {
public:
    int data;
    Node *next;

    Node(int data) : data(data), next(nullptr) {}
};

class Queue {
public:
    Node *front;
    Node *rear;

    Queue() : front(nullptr), rear(nullptr) {}

    void push(int val) {
        Node *node = new Node(val);
        if (rear == nullptr) { /*队列为空*/
            front = rear = node;
            return;
        }
        rear->next = node;
        rear = rear->next;
    }

    int pop() {
        if (front == nullptr) {
            throw "队列为空";
        }

        Node *tmp = front;
        int ans = front->data;
        if (front == rear) { /*只有一个元素*/
            front = rear = nullptr;
        } else {
            front = front->next;
        }
        delete tmp;
        return ans;
    }
};

第三章

二叉树

二叉搜索树 BST

AVL树（平衡二叉搜索树BBST）

B树

堆（最大堆、最小堆）

优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序

  • 堆即是优先队列的完全二叉树表示
    • 用数组表示的完全二叉树
    • 任一结点的元素是其子树所有结点的最大值(或最小值)
    • 可以插入数据，可以删除最大值
struct Heap {
    int data[MAXSIZE]; //data从1开始存数据
    int size;  //堆当前元素的个数

    Heap() {
        size = 0;
    }
};

  • 插入

    从底部向上依次遍历，直到父节点大于要插入的值

    void insert(int item) {
    if (size == MAXSIZE) {
        cout << "堆已满" << endl;
        return;
    }

    int i = ++size;
    for (; data[i / 2] < item; i /= 2)
        data[i] = data[i / 2];
    data[i] = item;
}

  • 删除最大节点

    //从第i个节点向下调整
void siftdown(int i) {
    int bigIndex = i;
    while (2 * i <= size) {
        if (data[2 * i] > data[i])
            bigIndex = 2 * i;
        if (2 * i + 1 <= size && data[2 * i] < data[2 * i + 1])
            bigIndex = 2 * i + 1;

        if (i != bigIndex) {
            int tmp = data[bigIndex];
            data[bigIndex] = data[i];
            data[i] = tmp;
            i = bigIndex;
        } else {
            break;
        }
    }
}

int deleteMax() {
    if (size == 0) {
        cout << "堆为空";
        return -1;
    }

    int maxItem = data[1];
    data[1] = data[size--];
    siftdown(1);
    return maxItem;
}

  • 创建堆

    把n个元素建立一个堆,首先我可以将这n个结点以自顶向下、从左到右的方式从1到n编码。

    这样就可以把这n个结点转换成为一棵完全二叉树。

    紧接着从最后一个非叶结点(结点编号为n/2)开始到根结点(结点编号为1),逐个扫描所有的结点,根据需要将当前结点向下调整,直到以当前结点为根结点的子树符合堆的特性。

    void create(int n) {
    for (int i = n / 2; i >= 1; i--) {
        siftdown(i);
    }
}

哈夫曼树

哈夫曼树构造：先用所有的数据构造出最小堆，然后每次把权值最小的两棵二叉树合并

struct HuffmanTreeNode {
    int weight;
    HuffmanTreeNode *left, *right;
};

HuffmanTreeNode* huffman(minHeap h) {
    HuffmanTreeNode *t;
    for (int i = 1; i < h->size; i++) {  /*做H->Size-1次合并*/
        t = new HuffmanTreeNode();
        t->left = h->deleteMin();
        t->right = h->deleteMin();
        t->weight = t->left->weight + t->right->weight;

        insert(h, t);
    }
    t = h->deleteMin();
    return t;
}

哈夫曼树的特点

  • 没有度为1的结点

  • n个叶子结点的哈夫曼树共有2n-1个结点（n = n0+n2 = 2n0 - 1）

  • 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树

  • 对同一组权值{w1 ,w2 , …… , wn}，存在不同构的两棵哈夫曼树

哈夫曼编码

给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？

[例] 假设有一段文本，包含58个字符，并由以下7个字符构：a，e，i， s，t，空格（sp），换行（nl）；这7个字符出现的次数不同。如何对这7个字符进行编码，使得总编码空间最少？

  • 用等长ASCII编码：58 ×8 = 464位
  • 用等长3位编码：58 ×3 = 174位
  • 不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则可以编码长些

解码时会出现二义性，分辨不出是一位编码还是二位编码

若任何字符的编码都不是另一字符编码的前缀 ，则可以无二义地解码

第四章

图

图基本概念

  • 包含
    • 一组顶点：通常用V (Vertex) 表示顶点集合
    • 一组边：通常用E (Edge) 表示边的集合
    • 边是顶点对：(v, w) ∈E ，其中v, w ∈ V有向边<v, w> 表示从v指向w的边（单行线）不考虑重边和自回路
  • 无向图：边是无向边(v, w)
  • 有向图：边是有向边<v, w>
  • 连通：如果从V到W存在一条（无向）路径，则称V和W是连通的
  • 连通图(Connected Graph)：如果对于图的任一两个顶点v、w∈V，v和w都是连通的，则称该图为连通图。图中任意两顶点均连通。
  • 连通分量(Connected Component):无向图中的极大连通子图。
    • 极大顶点数：再加1个顶点就不连通了
    • 极大边数：包含子图中所有顶点相连的所有边
  • 强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的。
  • 强连通图：有向图中任意两顶点均强连通。
  • 强连通分量：有向图的极大强连通子图。
  • 路径：V到W的路径是一系列顶点{V, v1, v2, …,vn, W}的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。
  • 如果V到W之间的所有顶点都不同，则称简单路径
  • 回路：起点等于终点的路径

1. 图的表示

邻接矩阵

图的邻接矩阵存储方式就是用一个二维数组来表示。

邻接矩阵G [N] [N]个顶点从0到N-1编号

顶点i、j有边，则G [i] [j] = 1 或 边的权重

  • 邻接矩阵的优点

  • 邻接矩阵的缺点

邻接表

邻接表：G[N]为指针数组，对应矩阵每行一个链表， 只存非0元素

struct Edge {
    int endIndex; //边的终点编号
    int weight;   //边的权重

    Edge(int endIndex, int weight) : endIndex(endIndex), weight(weight) {}
};

vector<Edge> adj[100];
adj[1].push_back(Edge(3, 5));
adj[1].push_back(Edge(4, 6));
adj[2].push_back(Edge(5, 6));

cout << "请输入顶点数:" << endl;
cin >> n;
cout << "请输入边数:" << endl;
int edgeNum;
cin >> edgeNum;

while (edgeNum--) {
    int s, e;
    scanf("%d->%d", &s, &e);
    Adj[s].push_back(e);
}

2.图的遍历

深度优先搜索

  • 邻接矩阵

    const int MAXN = 1e2 + 6;
const int INF = 2147413647;

int n, G[MAXN][MAXN]; //n为顶点数，MAXN为最大顶点数
bool book[MAXN] = {false}; //标记顶点是否被访问过

void dfs(int pos) {
    book[pos] = true;
    printf("%d", pos);

    for (int i = 0; i < n; i++) {
        if (!book[i] && G[pos][i] != INF) {
            dfs(i);
        }
    }
}

void dfsGo() {
    for (int i = 0; i < n; i++) {
        if (!book[i]) {
            dfs(i);
        }
    }
}

  • 邻接表

    const int MAXN = 1e2 + 6;

vector<int> Adj[MAXN]; //Adj为图的邻接表
int n; //n为顶点数，MAXN为最大顶点数
bool book[MAXN] = {false}; //标记顶点是否被访问过

void dfs(int pos) {
    book[pos] = true;
    printf("%d", pos);

    for (int i = 0; i < Adj[pos].size(); i++) {
        if (!book[Adj[pos][i]]) {
            dfs(Adj[pos][i]);
        }
    }
}

void dfsGo() {
    for (int i = 0; i < n; i++) {
        if (!book[i]) {
            dfs(i);
        }
    }
}

广度优先搜索

  • 邻接矩阵

    const int INF = 2147413647;
const int MAXN = 1e2 + 6;

int n, G[MAXN][MAXN]; //n为顶点数，MAXN为最大顶点数
bool book[MAXN] = {false}; //标记顶点是否被访问过

void bfs(int pos) {
    queue<int> q;
    q.push(pos);
    book[pos] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        printf("%d", cur);

        for (int i = 0; i < n; i++) {
            if (!book[i] && G[cur][i] != INF) {
                q.push(i);
                book[i] = true;
            }
        }
    }
}

void bfsGo() {
    for (int i = 0; i < n; i++) {
        if (!book[i]) {
            bfs(i);
        }
    }
}

  • 邻接表

    vector<int> Adj[MAXN]; //Adj为图的邻接表
int n; //n为顶点数，MAXN为最大顶点数
bool book[MAXN] = {false}; //标记顶点是否入过队

void bfs(int pos) {
    queue<int> q;
    q.push(pos);
    book[pos] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        printf("%d", cur);

        for (int i = 0; i < Adj[cur].size(); i++) {
            int next = Adj[cur][i];
            if (!book[next]) {
                q.push(next);
                book[next] = true;
            }
        }
    }

}

void bfsGo() {
    for (int i = 0; i < n; i++) {
        if (!book[i]) {
            bfs(i);
        }
    }
}

广度优先搜索如何记录层数？

void bfs(int pos) {
    queue<int> q;
    q.push(pos);
    book[pos] = true;
    int count = 0, level = 0, last = pos, tail; //count表示个数，level表示层数，last表示该层最后一个元素

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        printf("%d", cur);

        for (int i = 0; i < n; i++) {
            if (!book[i] && G[cur][i] != INF) {
                q.push(i);
                book[i] = true;
                count++;
                tail = i;
            }
        }

        if (cur == last) {
            level++;
            last = tail;
        }
    }
}

3.最短路径

  • 单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径

  • （有向）无权图

    • （有向）有权图

  • 多源最短路径问题：求任意两顶点间的最短路径

单源最短路（无权图）

const int INF = 2147413647;
const int MAXN = 1e5 + 6;

vector<int> Adj[MAXN]; //Adj为图的邻接表
int n; //n为顶点数，MAXN为最大顶点数
int dist[MAXN], path[MAXN];

void unweightedBFS(int start) {
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int i = 0; i < Adj[cur].size(); i++) {
            int next = Adj[cur][i];
            if (dist[next] == INF) {
                q.push(next);
                dist[next] = dist[cur] + 1;
                path[next] = cur;
            }
        }
    }
}

void init() {
    cin >> n;
    int edgeNum;
    cin >> edgeNum;

    while (edgeNum--) {
        int s, e;
        scanf("%d->%d", &s, &e);
        Adj[s].push_back(e);
    }

    fill(path, path + n + 1, -1);
    fill(dist, dist + n + 1, INF);
}

void printPath(int end) {
    int length = 0;
    while (end != -1) {
        printf("%d < ", end);
        end = path[end];
        length++;
    }
    printf("\nlength: %d", length);
}

int main() {
    init();
    unweightedBFS(1);
    printPath(7);
}

单源最短图（有权图）（Dijkstra算法）O(V2+E)

const int INF = 2147413647;
const int MAXN = 1e5 + 6;

struct Node {
    int endIndex, weight;

    Node(int endIndex, int weight) : endIndex(endIndex), weight(weight) {}
};

vector<Node *> Adj[MAXN]; //Adj为图的邻接表
int n; //n为顶点数，MAXN为最大顶点数
int dist[MAXN], path[MAXN], vis[MAXN];

int getLeastPos() {
    int min = INF, ans = -1;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && dist[i] < min) {
            min = dist[i];
            ans = i;
        }
    }
    return ans;
}

void Dijkstra(int start) {
    dist[start] = 0;
    while (true) {
        int leastPos = getLeastPos();
        if (leastPos == -1) break;

        vis[leastPos] = 1;
        for (int i = 0; i < Adj[leastPos].size(); i++) {
            int endIndex = Adj[leastPos][i]->endIndex;
            int weight = dist[leastPos] + Adj[leastPos][i]->weight;
            if (!vis[endIndex] && dist[endIndex] > weight) {
                dist[endIndex] = weight;
                path[endIndex] = leastPos;
            }
        }
    }
}

void init() {
    cin >> n;
    int edgeNum;
    cin >> edgeNum;

    while (edgeNum--) {
        int s, e, w;
        scanf("%d->%d %d", &s, &e, &w);
        Adj[s].push_back(new Node(e, w));
    }

    fill(path, path + n + 1, -1);
    fill(dist, dist + n + 1, INF);
}

void printPath(int end) {
    printf("length: %d\n", dist[end]);
    while (end != -1) {
        printf("%d < ", end);
        end = path[end];
    }
}

int main() {
    init();
    Dijkstra(1);
    printPath(7);
}

利用最小堆优化 O(E*logV)

const int INF = 2147413647;
const int MAXN = 1e5 + 6;

struct Node {
    int endIndex, weight;

    Node(int endIndex, int weight) : endIndex(endIndex), weight(weight) {}
};

vector<Node *> Adj[MAXN]; //Adj为图的邻接表
int n; //n为顶点数，MAXN为最大顶点数
int dist[MAXN], path[MAXN], vis[MAXN];

struct cmp {
    bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
        return p1.second > p2.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> minStack;

int getLeastPos() {
    int ans = -1;
    while (!minStack.empty()) {
        pair<int, int> min = minStack.top();
        minStack.pop();
        if (!vis[min.first]) {
            ans = min.first;
            break;
        }
    }
    return ans;
}

void Dijkstra(int start) {
    dist[start] = 0;
    minStack.push({start, dist[start]});
    while (true) {
        int leastPos = getLeastPos();
        if (leastPos == -1) break;

        vis[leastPos] = 1;
        for (int i = 0; i < Adj[leastPos].size(); i++) {
            int endIndex = Adj[leastPos][i]->endIndex;
            int weight = dist[leastPos] + Adj[leastPos][i]->weight;
            if (!vis[endIndex] && dist[endIndex] > weight) {
                dist[endIndex] = weight;
                path[endIndex] = leastPos;
                minStack.push({endIndex, weight});
            }
        }
    }
}

void init() {
    cin >> n;
    int edgeNum;
    cin >> edgeNum;

    while (edgeNum--) {
        int s, e, w;
        scanf("%d->%d %d", &s, &e, &w);
        Adj[s].push_back(new Node(e, w));
    }

    fill(path, path + n + 1, -1);
    fill(dist, dist + n + 1, INF);
    for (int i = 1; i <= n; i++) {
        minStack.push({i, dist[i]});
    }
}

void printPath(int end) {
    printf("length: %d\n", dist[end]);
    while (end != -1) {
        printf("%d < ", end);
        end = path[end];
    }
}

int main() {
    init();
    Dijkstra(1);
    printPath(7);
}

多源最短路(Floyd算法)

const int INF = 2147413647;
const int MAXN = 1e3 + 6;

int n, m; //n为顶点数，m为边数
int dis[MAXN][MAXN], path[MAXN][MAXN];

void Floyd() {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    path[i][j] = k; //i和j的路径上一定有k
                }
            }
}

int main() {
    int u, v, w;
    fill(dis[0], dis[0] + MAXN * MAXN, INF);
    fill(path[0], path[0] + MAXN * MAXN, -1);
    scc(n, m);
    for (int i = 0; i < n; i++)
        dis[i][i] = 0;
    for (int i = 0; i < m; i++) {
        sccc(u, v, w);
        dis[u][v] = w;
    }
    Floyd();
}

4.最小生成树

prim算法

适合稠密图O(V2)

const int INF = 2147413647;
const int MAXN = 100;

int n, m, sum = 0;
int dis[MAXN], book[MAXN], parent[MAXN], G[MAXN][MAXN];

int getLeastPos() {
    int min = INF, ans = -1;
    for (int i = 1; i <= n; i++) {
        if (!book[i] && dis[i] < min) {
            min = dis[i];
            ans = i;
        }
    }
    return ans;
}

void prim(int start) {
    dis[start] = 0;

    while (true) {
        int leastPos = getLeastPos();
        if (leastPos == -1) break;

        book[leastPos] = 1;
        sum += dis[leastPos];

        for (int i = 1; i <= n; i++) {
            if (!book[i] && G[leastPos][i] < dis[i]) {
                dis[i] = G[leastPos][i];
                parent[i] = leastPos;
            }
        }
    }

    //判断是否能够生成
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (book[i]) cnt++;
    }
    if (cnt < n) {
        printf("不能生成最小生成树");
    } else {
        printf("sum:%d", sum);
    }
}

void init() {
    int u, v, w;
    fill(dis, dis + MAXN, INF);
    fill(G[0], G[0] + MAXN * MAXN, INF);
    scc(n, m);
    for (int i = 1; i <= n; i++)
        G[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        sccc(u, v, w);
        G[u][v] = G[v][u] = w;
    }
}

int main() {
    init();
    prim(1);
}

Kruskal算法

将森林合并成树，O(E*logE)

const int INF = 2147413647;
const int MAXN = 1e3 + 6;

int n, fa[MAXN];

struct Edge {
    int from, to, cost;

    bool operator<(const Edge &p) const {
        return cost < p.cost;
    }
} edge[MAXN];


//找到x的掌门人
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);//路径压缩
}

//合并x和y所在的门派
void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
}

//查看x和y的门派是否相同
bool check(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    return fx == fy;
}

int main() {
    int m, ans, cnt;
    while (~sc(n) && n) {
        sc(m);
        //初始化
        for (int i = 1; i <= n; i++) fa[i] = i;
        ans = 0, cnt = 0;//ans为路程总和，cnt为连接的边的数量
        //读入边
        for (int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
        //对边的权值排序
        sort(edge + 1, edge + m + 1);

        for (int i = 1; i <= m; i++) {
            //若两点不在同一条线
            if (!check(edge[i].from, edge[i].to)) {
                ans += edge[i].cost;
                cnt++;
                unite(edge[i].from, edge[i].to);//合并
            }
        }
        //检验，打印cost之和
        if (cnt == n - 1) p(ans);
        else printf("不能生成");
    }
}

5.拓扑排序

如果图中从V到W有一条有向路径， 则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序

获得一个拓扑序的过程就是拓扑排序

AOV: 如果有合理的拓扑序，则必定是有向无环图

  • 关键路径问题

第五章

散列

“散列（Hashing）” 的基本思想是：

（1）以关键字key为自变量，通过一个确定的函数h(散列函数)， 计算出对应的函数值h(key)，作为数据对象的存储地址。

（2）可能不同的关键字会映射到同一个散列地址上，即h(keyi) = h(keyj)（当keyi ≠ keyj），称为“冲突(Collision)”。

散列函数的构造方法

一个“好”的散列函数一般应考虑下列两个因素：

  1. 计算简单，以便提高转换速度；
    1. 关键词对应的地址空间分布均匀，以尽量减少冲突。

  • 数字关键词的散列函数构造

  • 字符关键词的散列函数构造

    • 一个简单的散列函数——ASCII码加和法
    • 简单的改进——前3个字符移位法
    • 好的散列函数——移位法，涉及关键词所有n个字符

冲突处理方法

开放地址法

一旦产生了冲突（该地址已有其它元素），就按某 种规则去寻找另一空地址

  • 1、线性探测法

    以增量序列 1，2，……，（TableSize -1） 循环试探下一个存储地址

  • 平方探测法

    平方探测法：以增量序列q2，-q2 且q ≤ TableSize/2 循环试探下一个存储地址

    如果散列表长度TableSize是某个4k+3（k是正整 数）形式的素数时，平方探测法就可以探查到整个散列表空间

  • 双散列探测法

链地址法

将相应位置上冲突的所有关键词存储在同一个单链表中

再散列

  • 当散列表元素太多（即装填因子α太大）时，查找效率会下降(实用最大装填因子一般取 0.5 <= α<= 0.85 )

  • 当装填因子过大时，解决的方法是加倍扩大散列表，这个过程叫 做“再散列（Rehashing）”

hhhhh