数据结构实验笔记

Fib(3)
├── Fib(2)
│   ├── Fib(1) → 返回 1
│   └── Fib(0) → 返回 0
│   得 1
└── Fib(1) → 返回 1
得 2

int Fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return Fib(n - 1) + Fib(n - 2);
}

struct Node {          // 一个非零元素
    int i, j;          // 行号、列号
    int data;          // 元素值
};

struct Matrix {
    int m, n;          // 总行数、总列数
    int L;             // 非零元素个数
    Node* Ma[MAX];     // 非零元素数组
};

// 构造 LPS 数组
void computeLPS(const string& pat, vector<int>& lps) {
    int len = 0;          // 当前最长前后缀匹配长度
    lps[0] = 0;
    int i = 1;
    while (i < (int)pat.size()) {
        if (pat[i] == pat[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];   // 回退到次长前后缀，继续比较
        } else {
            lps[i++] = 0;
        }
    }
}

// 在 text 中查找 pat
void KMPSearch(const string& text, const string& pat) {
    int m = pat.size(), n = text.size();
    vector<int> lps(m);
    computeLPS(pat, lps);

    int i = 0, j = 0;          // i 走文本，j 走模式串
    while (i < n) {
        if (pat[j] == text[i]) { i++; j++; }
        if (j == m) {
            cout << "在索引 " << i - j << " 处找到匹配串" << endl;
            j = lps[j - 1];    // 继续找下一次匹配
        } else if (i < n && pat[j] != text[i]) {
            if (j != 0) j = lps[j - 1];
            else        i++;   // j 已为 0，无法再回退，只能让文本指针前进
        }
    }
}

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
};

void preOrder(TreeNode* p) {          // 前序：根 → 左 → 右
    if (!p) return;
    visit(p);
    preOrder(p->left);
    preOrder(p->right);
}

void inOrder(TreeNode* p) {           // 中序：左 → 根 → 右
    if (!p) return;
    inOrder(p->left);
    visit(p);
    inOrder(p->right);
}

void postOrder(TreeNode* p) {         // 后序：左 → 右 → 根
    if (!p) return;
    postOrder(p->left);
    postOrder(p->right);
    visit(p);
}

void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* p = q.front(); q.pop();
        visit(p);
        if (p->left)  q.push(p->left);
        if (p->right) q.push(p->right);
    }
}

        a
      /   \
     b     c
    / \   / \
   @   d e   f
      / \ / \ / \
     @  @ @ @ @  @

while (minHeap.size() > 1) {
    auto left  = minHeap.top(); minHeap.pop();
    auto right = minHeap.top(); minHeap.pop();
    auto parent = new HuffmanNode('$', left->frequency + right->frequency);
    parent->left = left;
    parent->right = right;
    minHeap.push(parent);
}

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val)      root->left  = insert(root->left,  val);
    else if (val > root->val) root->right = insert(root->right, val);
    return root;   // 相等时不插入，避免重复
}

TreeNode* remove(TreeNode* root, int val) {
    if (!root) return nullptr;
    if (val < root->val)      root->left  = remove(root->left,  val);
    else if (val > root->val) root->right = remove(root->right, val);
    else {
        if (!root->left)  { auto t = root->right; delete root; return t; }
        if (!root->right) { auto t = root->left;  delete root; return t; }
        // 两个孩子：找右子树最小节点
        TreeNode* succ = root->right;
        while (succ->left) succ = succ->left;
        root->val  = succ->val;
        root->right = remove(root->right, succ->val);
    }
    return root;
}

struct Node {
    int data;
    Node *left, *right;
    int ltag, rtag;   // 0 表示指向孩子，1 表示是线索（指向前驱/后继）
};

Node* pre = nullptr;

void thread(Node* p) {
    if (!p) return;
    thread(p->left);              // 先处理左子树

    if (!p->left) {               // 左孩子为空，左指针改指向前驱
        p->left = pre;
        p->ltag = 1;
    }
    if (pre && !pre->right) {     // 前驱的右孩子为空，右指针改指向后继
        pre->right = p;
        pre->rtag = 1;
    }

    pre = p;                      // 更新前驱
    thread(p->right);             // 再处理右子树
}

vector<int> adj[MAX];          // 每个元素是一个链表/动态数组
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);       // 无向图要加反向边
}

sort(edges.begin(), edges.end(),
     [](const Edge& a, const Edge& b) { return a.weight < b.weight; });

UnionFind uf(numNodes);
vector<Edge> result;
for (const Edge& e : edges) {
    if (uf.find(e.start) != uf.find(e.end)) {   // 不连通 → 加入不会成环
        result.push_back(e);
        uf.unite(e.start, e.end);
    }
}

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);   // 路径压缩
    return parent[x];
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (rank[a] < rank[b]) swap(a, b);   // 按秩合并
    parent[b] = a;
    if (rank[a] == rank[b]) rank[a]++;
}

vector<int> dijkstra(const vector<vector<int>>& g, int src) {
    int n = g.size();
    vector<int> dist(n, INF);
    // 小顶堆：队首是距离最小的元素
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;        // 过期条目，跳过
        for (int v = 0; v < n; v++) {
            if (g[u][v] == 0) continue;   // 0 表示无直接连接
            if (dist[u] + g[u][v] < dist[v]) {
                dist[v] = dist[u] + g[u][v];
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

void calcEarliest() {
    // 必须先按拓扑序处理，否则前驱的 ES 还没算好
    for (int u : topoOrder) {
        for (int v : activities[u].next) {
            earliest[v] = max(earliest[v], earliest[u] + activities[u].duration);
        }
    }
}

void calcLatest() {
    for (int u : reverseTopoOrder) {
        for (int v : activities[u].next) {
            latest[u] = min(latest[u], latest[v] - activities[u].duration);
        }
    }
}