数据结构知识点记录

数据结构

线性表：

顺序表

链表:

双向链表

循环链表

栈：

顺序栈

链栈

队列：

顺序队列

链队列

循环队列

二叉树:

堆

AVL树

图：

adj_matrix

邻接表

算法：

串：

KMP

void getnext(int* &next, string s){
    int prefix_len = 0;
    next[0] = 0;
    int i = 1;
    while(i < s.size()){
        if(s[prefix_len] == s[i]) {
            prefix_len++;
            next[i] = prefix_len;
            i++;
        } else{
            if(prefix_len == 0) {
                next[i] = 0;
                i++;
            } else {
                prefix_len = next[prefix_len - 1];
            }
        }
    }   
    return ;
}
int KMP(string str, string substr){
    int sublen = substr.size();
    int* next = new int[sublen];
    getnext(next, substr);
    
    int i = 0; int j = 0;
    while(i < str.size()) {

        if(str[i] == substr[j]) {
            i++; j++;
        }else if(j == 0) {
            i++; 
        }else{ 
            j = next[j-1];
        }

        if(j == sublen) {
            return i-j;
        }
    }
    return -1;
}

树：

霍夫曼树

AVL树构建

红黑树

图：

广度优先搜索（bfs）：

使用递归直接访问所有邻居节点，标记visit。

深度优先搜索（dfs）：

使用队列访问所有邻居节点，邻居节点都加入队列直到队空。

Prim：

初始化：

1.任选一个起点（如 0 号点）加入蓝点集。

2.设置 dist[i] 为各个点到蓝点集的距离（起点为 0，其余为inf）。

找点：

1.从白点集中找一个 dist 最小的点 u。

更新（松弛）：

1.以u为新起点，看它周围的白点 v 到 u的距离是否小于原本的 dist[v]。

2.如果是，则更新 dist[v]。

3.循环：重复上述步骤 n-1 次，直到所有点变蓝。

#include<iostream>
#include<string>
#include<vector>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
int main(){
    int n, m;cin>>n>>m;
    vector<vector<int>> edge_matrix(n, vector<int>(n, inf));
    // input;
    int start = 0;
    vector<int> dist(n, inf);
    vector<int> visited(n, 0);
    dist[0] = 0;

    for(int i = 0; i < n; i++) {
        int u = -1;
        for(int j = 0; j < n; j++) {// find min vertex
            if(!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }

        visited[u] = 1;

        for(int j = 0; j < n; j++) {
            if(!visited[j] && edge_matrix[u][j] < dist[j]){
                dist[j] = edge_matrix[u][j];
            }
        }
    }
}

Kruskal:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct UnionFind{
    vector<int> parent;

    UnionFind(int n) : parent(n) {
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x){
        if(parent[x] == x) {
            return x;
        } else {
            return find(parent[x]);
        }
    }

    int unify(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) {
            return -1;
        }else{
            parent[y] = x;
            return 1;
        }
    }
};

struct Edge{
    int u, v, w;
    Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}

    bool operator<(const Edge &other)const{
        return w < other.w;
    }
};

int main(){
    int n; cin>>n;
    vector<Edge> K_edges(n);
    // edge input
    sort(K_edges.begin(), K_edges.end());

    UnionFind uf(n);
    for(const Edge &e: K_edges) {
        if(uf.unify(e.u, e.v)) {
            //output
        }
    }
}

Dijkstra:

void dijkstra(vector<vector<int>>& adj, int start, int n) {
    vector<int> dist(n, inf);
    vector<int> prev(n, -1);
    vector<int> visited(n, -1);

    dist[start] = 0;

    for(int i = 0; i < n; i++) {
        int u = -1;
        for(int j = 0; j < n; j++) {// 寻找最近的下一个点
            if(!visited[j] && (u == -1 || dist[j] < dist[u])){
                u = j;
            }
        }
        if(u == -1) break;
        visited[u] = 1;

        for(int v = 0; v < n; v++) {
            if(!visited[v] && adj[u][v] != inf) {
                if(dist[u] + adj[u][v] < dist[v]){
                    dist[v] = dist[u] + adj[u][v];
                    prev[v] = u;
                }

            }
        }
    }
}

floyd-warshall:

排序：

插入排序

void insertion_sort(int n, int* &a) {
    for(int i = 1; i < n; i++) {
        int num = a[i]; 
        int j = i-1;
        printlis(n, a);
        while( j >= 0 && a[j] > num) {
            a[j + 1] =  a[j];
            j--;
        }
        a[j+1] = num;
    }      
}

希尔排序

void shell_sort(int n, int* &a){
    for(int gap = n/2; gap > 0; gap/=2) { // 此处按照每次都为长度除以二来设定gap
        for(int i = gap; i < n; i++) {
            int temp = a[i];
            int j = i - gap;
            while(j >= 0 && a[j] > a[j + gap]) { // 此处属于插入排序而非直接交换
                a[j + gap] = a[j];
                j = j - gap;
            }
            a[j+gap] = temp;
        }
    }
}

选择排序

void select_sort(int n, int* &a) {
    for(int i = 0; i < n; i++) {
        int min_idx = i;
        int min = a[i];
        for(int j = i; j < n; j++) {
            if(a[j] < min){
                min = a[j];
                min_idx = j;
            }
        }
        swap(a[min_idx], a[i]);
    }
}

堆排序

void heapify(int i, int*& a, int n) {
    int left = i*2+1;
    int right = i*2+2;
    int max = a[i];
    int max_idx = i;

    if(left < n && max < a[left]) {
        max = a[left];
        max_idx = left;
    }
    if(right < n && max < a[right]) {
        max = a[right];
        max_idx = right;
    }
    if(max_idx == i) return ;
    swap(a[i], a[max_idx]);
    heapify(max_idx, a, n);
}

void heap_sort(int n, int*& a) {
    for(int i = n/2-1; i >= 0; i--) {
        heapify(i, a, n);
    }

    for(int i = n-1; i >= 0; i--) {
        swap(a[0], a[i]);
        heapify(0, a, i);
    }
}

冒泡排序


void bubble_sort(int n, int*& a) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n-i-1; j++) {
            if(a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
            }
        }
    }
}

快速排序

int partition(int l,int r, int*&a) {
    int pivot = a[l];
    int left = l;
    int right = r;
    int index = left;

    while(left < right){
        while(left < right) {
            if(a[right] <= pivot) {
                a[index] = a[right];
                index = right;
                break;
            }
            right--;
        }

        while(left < right) {
            if(a[left] >= pivot) {
                a[index] = a[left];
                index = left;
                break;
            }
            left++;
        }
    }

    a[index] = pivot;
    return index;
}

void quick_sort(int*& a, int l, int r) {
    if(l >= r) {
        return;
    }

    int pivot_idx = partition(l, r, a);
    quick_sort(a, l, pivot_idx-1);
    quick_sort(a, pivot_idx+1, r);
}

归并排序

基数排序

查找：

二分查找顺序查找哈希查找

数据结构

线性表：

链表:

栈：

队列：

二叉树:

图：

算法：

串：

树：

图：

排序：

查找：

评论