WHUSESC数据结构考纲算法模版

0x00

数据结构实验期末考试复习，搓了考纲内的简单算法模版，仅作参考

0x01 图

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <climits>
#include <utility>
#include <string>

using namespace std;

class Graph {
public:
    vector<vector<pair<int, int>>> adj; // 邻接表
    vector<vector<int>> matrix;              // 邻接矩阵
    struct Edge
    {
        int u, v, w;
        bool operator<(const Edge &e) const { return w < e.w; }
    };
    vector<Edge> edges;                 // 边集
private:
    const int INF = 0x3f3f3f3f;
    int n;

    vector<int> fa;                     // 并查集

    int find(int x)
    { // 查找所属连通分量
        if (fa[x] != x)
            fa[x] = find(fa[x]);
        return fa[x];
    }

    void Union(int x, int y)
    { // 合并两个连通分量
        fa[find(x)] = find(y);
    }

    void init(int n_)
    {
        n = n_;
        adj.assign(n, {});
        matrix.assign(n, vector<int>(n, INF));
        edges.clear();
        fa.resize(n);
        for (int i = 0; i < n; i++)
            fa[i] = i;
        for (int i = 0; i < n; i++)
            matrix[i][i] = 0;
    }

public:
    Graph(int n_ = 0)
    { 
        init(n_); 
    }

    void reset(int n_)
    { 
        init(n_); 
    }

    void add(int u, int v, int w, bool undirected = true)
    { // 加边，统合三种存储结构
        // 邻接表
        adj[u].push_back({v, w});
        if(undirected)
            adj[v].push_back({u, w});

        // 邻接矩阵
        matrix[u][v] = min(matrix[u][v], w);
        if(undirected)
            matrix[v][u] = min(matrix[v][u], w);

        // 边集（避免无向重复）
        if(!undirected || u < v)
            edges.push_back({u, v, w});
        else if(undirected)
            edges.push_back({v, u, w});
    }

    pair<vector<int>, vector<int>> dijkstra(int s)
    { // 单源最短路径
        vector<int> dist(n, INF);
        vector<int> pre(n, -1); // 用于恢复路径
        priority_queue<pair<int, int>,
                       vector<pair<int, int>>,
                       greater<pair<int, int>>> pq;

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

        while (!pq.empty())
        {
            auto e = pq.top(); 
            pq.pop();
            int d = e.first; // 距离
            int u = e.second; // 目的点
            if (d > dist[u]) continue; // 跳过队列中存在的已优化的目的点

            for (auto &e : adj[u])
            {
                int v = e.first; // 目的点
                int w = e.second; // 距离
                if (dist[v] > dist[u] + w)
                {
                    dist[v] = dist[u] + w;
                    pre[v] = u; 
                    pq.push({dist[v], v}); // 优化一个目的点后压入队列以优化所有相关目的点
                }
            }
        }
        return {dist, pre};
    }

    vector<int> pre2path(int start, int dest, vector<int>& pre)
    { // 根据dijkstra返回的pre数组恢复路径
        vector<int> path;
        for (int cur = dest; cur != -1; cur = pre[cur])
            path.push_back(cur);
        reverse(path.begin(), path.end());
        if (path[0] != start)   // 不可达
            path.clear();
        return path;
    }

    pair<vector<vector<int>>, vector<vector<int>>> floyd()
    {
        vector<vector<int>> dist;   // 最短距离
        vector<vector<int>> next;    // 路径恢复矩阵
        dist = matrix;   // 拷贝邻接矩阵
        next.assign(n, vector<int>(n, -1));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][j] < INF && i != j)
                    next[i][j] = j;  // 初始：i 直达 j
        for (int k = 0; k < n; k++)
        {
            for (int i = 0; i < n; i++)
            {    
                for (int j = 0; j < n; j++)
                {
                    if (dist[i][k] < INF && dist[k][j] < INF &&
                        dist[i][j] > dist[i][k] + dist[k][j])
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k];  // 路径关键点
                    }
                }
            }
        }
        return {dist, next};
    }

    vector<int> next2path(int start, int dest, vector<vector<int>>& next)
    { // 根据floyd返回的next矩阵恢复路径
        vector<int> path;
        if (next[start][dest] == -1)
            return path; // 不可达
        path.push_back(start);
        while(start != dest)
        {
            start = next[start][dest];
            path.push_back(start);
        }
    }

    int kruskal()
    { // 最小生成树, 返回权值和
        for(int i = 0; i < n; i++)
            fa[i] = i;
        sort(edges.begin(), edges.end());

        int res = 0;
        int cnt = 0;
        for (auto &e : edges)
        {
            if (find(e.u) != find(e.v))
            {
                Union(e.u, e.v);
                res += e.w;
                cnt++;
                if (cnt == n - 1) break;
            }
        }
        return (cnt < n - 1) ? -1 : res;
    }

    int prim()
    { // 最小生成树, 返回权值和
        vector<int> dist(n, INF);
        vector<bool> vis(n, false);
        priority_queue<pair<int, int>,
                       vector<pair<int, int>>,
                       greater<pair<int, int>>> pq;

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

        int res = 0, cnt = 0;

        while (!pq.empty())
        {
            auto [d, u] = pq.top(); pq.pop();
            if (vis[u]) continue;

            vis[u] = true;
            res += d;
            cnt++;

            for (auto &e : adj[u])
            {
                int v = e.first, w = e.second;
                if (!vis[v] && dist[v] > w)
                {
                    dist[v] = w;
                    pq.push({w, v});
                }
            }
        }

        return (cnt < n) ? -1 : res;
    }

    vector<int> topological_sort_bfs() 
    { // 广搜拓扑排序
        vector<int> indegree(n, 0); // 记录每个节点的入度
        for (int u = 0; u < n; u++)
        {
            for (auto &e : adj[u])
            {
                indegree[e.first]++;
            }
        }

        queue<int> q;
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0) q.push(i);

        vector<int> order;
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            order.push_back(u);

            for (auto &e : adj[u])
            {
                int v = e.first;
                indegree[v]--; // 减少入度
                if (indegree[v] == 0) q.push(v); // 入度为0入队
            }
        }

        if ((int)order.size() != n) 
        {
            cout << "Graph has a cycle, topological sort not possible." << endl;
            return {};
        }

        return order;
    }

    vector<int> topological_sort_dfs()
    { // 深搜拓扑排序
        vector<int> state(n, 0); // 0=未访问, 1=访问中, 2=已完成
        stack<pair<int, bool>> st;
        vector<int> order;

        for (int i = 0; i < n; i++)
        {
            if (state[i] != 0) continue;
            st.push({i, false});
            while (!st.empty())
            {
                auto [u, finished] = st.top();
                st.pop();
                if (finished)
                { // 所有子节点处理完
                    state[u] = 2;
                    order.push_back(u);
                    continue;
                }
                if (state[u] == 1)
                { // 再次遇到访问中的节点 -> 有环
                    cout << "Graph has a cycle, topological sort not possible." << endl;
                    return {};
                }
                if (state[u] == 2) continue;
                // 第一次访问该节点
                state[u] = 1;
                st.push({u, true}); // 标记：等子节点处理完再回来
                // 子节点逆序入栈
                for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it)
                {
                    int v = it->first;
                    if (state[v] == 0)
                    {
                        st.push({v, false});
                    }
                    else if (state[v] == 1)
                    {
                        // 发现回边
                        cout << "Graph has a cycle, topological sort not possible." << endl;
                        return {};
                    }
                }
            }
        }
        reverse(order.begin(), order.end());
        return order;
    }


    void dfs(int start)
    { // 非递归深搜
        if (start < 0 || start >= n) return;
        vector<bool> visited(n, false);
        stack<int> stk;
        stk.push(start);

        while (!stk.empty())
        {
            int u = stk.top(); stk.pop();
            if (visited[u]) continue;
            visited[u] = true;
            cout << u << " "; // 输出节点

            // 遍历邻接点，逆序入栈保证与递归顺序一致
            for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it)
            {
                int v = it->first;
                if (!visited[v]) stk.push(v);
            }
        }
        cout << endl;
    }

    void bfs(int start)
    { // 广搜
        if (start < 0 || start >= n) return;
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(start);
        visited[start] = true;
        // 利用队列进行
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            cout << u << " "; 

            for (auto &e : adj[u])
            {
                int v = e.first;
                if (!visited[v])
                {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        cout << endl;
    }

    void dfs_recursive(int start)
    { // 递归深搜
        if (start < 0 || start >= n) return;
        vector<bool> visited(n, false);
        dfs_rec_helper(start, visited);
        cout << endl;
    }
private:
    void dfs_rec_helper(int u, vector<bool> &visited)
    {
        visited[u] = true;
        cout << u << " "; // 输出节点
        for (auto &e : adj[u])
        {
            int v = e.first;
            if (!visited[v])
            {
                dfs_rec_helper(v, visited);
            }
        }
    }
};

int main()
{
    Graph graph(10);
    graph.add(1, 2, 50, false);
    graph.add(3, 1, 80, false);
    graph.add(4, 2, 60, false);
    graph.add(9, 7, 50, false);
    graph.add(8, 4, 10, false);
    graph.add(6, 3, 70, false);
    graph.add(3, 2, 10, false);
    graph.add(9, 2, 30, false);
    graph.add(8, 3, 10, false);
    vector<vector<int>>& tmpG = graph.matrix;
    cout << tmpG[1][2] << endl;
    cout << "dijkstra" << endl;
    vector<int> d = graph.dijkstra(3).first;
    for(auto& x : d)
        cout << x << endl;
    cout << "dfs" << endl;
    graph.dfs(3);
    cout << "bfs" << endl;
    graph.bfs(1);
    cout << "dfs_recursive" << endl;
    graph.dfs_recursive(3);
    cout << "topological_sort" << endl;
    vector<int> o = graph.topological_sort_bfs();
    for(auto& x : o)
        cout << x << endl;
    return 0;
}

0x02 孩子兄弟树 (一般树)

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <climits>
#include <utility>
#include <string>

using namespace std;

class CSTree
{
private:
    struct Node
    {
        int data;
        Node* firstChild;
        Node* nextSibling;

        Node(int val)
            : data(val), firstChild(nullptr), nextSibling(nullptr) {}
    };

    Node* root;

    void clearTree(Node* target)
    { // 删除子树
        if(target == nullptr) return;
        if(target->firstChild == nullptr)
        {
            delete target;
            return;
        }
        stack<Node*> st;
        st.push(target->firstChild);
        while (!st.empty())
        {
            Node* cur = st.top();
            st.pop();
            if (cur->firstChild != nullptr)
                st.push(cur->firstChild);
            if (cur->nextSibling != nullptr)
                st.push(cur->nextSibling);
            delete cur;
        }
        delete target;
    }

    Node* findParent(Node* target)
    { // 寻找父节点
        if (root == nullptr || target == nullptr) return nullptr;
        stack<Node*> st;
        st.push(root);
        while (!st.empty())
        {
            Node* node = st.top();
            st.pop();
            for (Node* child = node->firstChild;
                child != nullptr;
                child = child->nextSibling)
            {
                if (child == target)
                    return node;
                st.push(child);
            }
        }
        return nullptr;
    }

public:
    CSTree() : root(nullptr) {}

    ~CSTree()
    {
        clear();
    }

    /********************
     * 设置根结点
     ********************/
    void setRoot(int val)
    {
        clear();
        root = new Node(val);
    }

    Node* insert(Node* parent, int val)
    { // 插入结点
        if (parent == nullptr) return nullptr;
        Node* node = new Node(val);
        if (parent->firstChild == nullptr)
        {
            parent->firstChild = node;
        }else{
            Node* cur = parent->firstChild;
            while (cur->nextSibling != nullptr)
            {
                cur = cur->nextSibling;
            }
            cur->nextSibling = node;
        }
        return node;
    }

    bool remove(Node* target)
    { // 删除节点及以其为根的子树
        if (target == nullptr) return false;
        // 情况 1：删除根结点
        if (target == root)
        {
            clear();
            return true;
        }
        // 1. 找父结点
        Node* parent = findParent(target);
        if (parent == nullptr) return false;
        // 2. 从父结点的孩子链表中断开
        if (parent->firstChild == target)
        {
            parent->firstChild = target->nextSibling;
        }else{
            Node* cur = parent->firstChild;
            while (cur != nullptr && cur->nextSibling != target)
            {
                cur = cur->nextSibling;
            }
            if (cur == nullptr) return false;
            cur->nextSibling = target->nextSibling;
        }
        // 3. 删除子树
        clearTree(target);
        return true;
    }

    Node* getRoot() const
    {
        return root;
    }

    /********************
     * 非递归 DFS（先序）
     ********************/
    void dfs() const
    {
        if (root == nullptr) return;
        stack<Node*> st;
        st.push(root);
        while (!st.empty())
        {
            Node* cur = st.top();
            st.pop();
            cout << cur->data << " ";
            // 兄弟先入栈，保证孩子先访问
            if (cur->nextSibling != nullptr)
                st.push(cur->nextSibling);
            if (cur->firstChild != nullptr)
                st.push(cur->firstChild);
        }
        cout << endl;
    }

    /********************
     * BFS（层序遍历）
     ********************/
    void bfs() const
    {
        if (root == nullptr) return;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            Node* cur = q.front();
            q.pop();
            cout << cur->data << " ";

            for (Node* child = cur->firstChild;
                 child != nullptr;
                 child = child->nextSibling)
            {
                q.push(child);
            }
        }
        cout << endl;
    }

    /********************
     * 释放整棵树
     ********************/
    void clear()
    {
        if (root == nullptr) return;
        Node* cur = root;
        while (cur != nullptr)
        {
            Node* next = cur->nextSibling;  // 先保存
            clearTree(cur);                 // 删除以 cur 为根的树
            cur = next;                     // 继续下一个兄弟
        }
        root = nullptr;
    }
};

0x03 手写堆

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <climits>
#include <utility>
#include <string>

using namespace std;

class MinHeap{
    private:

    vector<int> heap;

    public:

    bool empty()
    {
        return heap.empty();
    }

    int top()
    {
        return heap[0];
    }

    void up(int idx)
    {
        while(idx > 0)
        {
            int p = (idx - 1) / 2; // 父节点
            if(heap[idx] < heap[p]) // 若要改写成最大堆，此处比较翻转
            {
                swap(heap[p], heap[idx]);
                idx = p;
            }else{
                break;
            }
        }
    }

    void down(int idx)
    {
        int n = heap.size();
        while(1)
        {
            int l = 2 * idx + 1; // 左孩子
            int r = 2 * idx + 2; // 右孩子
            int m = idx;
            if(l < n && heap[l] < heap[m]) // 若要改写成最大堆，此处比较翻转
            {
                m = l;
            }
            if(r < n && heap[r] < heap[m]) // 若要改写成最大堆，此处比较翻转
            {
                m = r;
            } // 找到最小的孩子
            if(m == idx)
            {
                break;
            }
            swap(heap[m], heap[idx]);
            idx = m;
        }
    }

    void push(int val)
    {
        heap.push_back(val);
        up(heap.size()-1);
    }

    void pop()
    {
        swap(heap[0], heap.back());
        heap.pop_back();
        down(0);
    }
    
    void make_heap()
    {
        int n = heap.size();
        for(int i = n / 2 - 1; i >= 0; i--)
            down(i);
    }
};

int main()
{
    MinHeap heap;
    heap.push(-1);
    heap.push(100);
    heap.push(-5);
    heap.push(100);
    heap.pop();
    cout << heap.top() << endl;
    return 0;
}

0x04 手写排序

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <climits>
#include <utility>
#include <string>

using namespace std;

struct sortType
{
    char info;
    char data;
    int key;
};

class mySort{
public:

    /*************************************************/
    // 插入排序
    /*************************************************/
    static void insert_sort(vector<sortType>& r)
    {
        sortType temp;
        int i;
        int n = r.size();
        for (int j = 1; j < n; j++)
        {
            if (r[j].key < r[j - 1].key)
            {
                temp = r[j];
                i = j - 1;
                while (i >= 0 && r[i].key > temp.key)
                {
                    r[i + 1] = r[i];
                    i--;
                }
                r[i + 1] = temp;
            }
        }
    }

    /*************************************************/
    // 二分插入排序
    /*************************************************/
    static void midInsert_sort(vector<sortType>& r)
    {
        int n = r.size();
        sortType temp;
        int low, high, mid;

        for (int i = 1; i < n; i++)
        {
            if (r[i - 1].key > r[i].key)
            {
                temp = r[i];
                low = 0;
                high = i - 1;
                while (low <= high)
                {
                    mid = (low + high) / 2;
                    if (r[mid].key > r[i].key)
                    {
                        high = mid - 1;
                    }
                    else
                    {
                        low = mid + 1;
                    }
                }
                for (int j = i - 1; j >= high + 1; j--)
                {
                    r[j + 1] = r[j];
                }
                r[high + 1] = temp;
            }
        }
    }

    /*************************************************/
    // 希尔排序
    /*************************************************/
    static void shell_sort(vector<sortType>& r)
    {
        int n = r.size();
        int d = n / 2;
        sortType temp;
        int j;

        while (d > 0)
        {
            for (int i = d; i < n; i++)
            {
                temp = r[i];
                j = i - d;
                while (j >= 0 && temp.key < r[j].key)
                {
                    r[j + d] = r[j];
                    j -= d;
                }
                r[j + d] = temp;
            }
            d /= 2;
        }
    }

    /*************************************************/
    // 冒泡排序
    /*************************************************/
    static void bubble_sort(vector<sortType>& r)
    {
        int n = r.size();
        bool exchange;
        sortType temp;

        for (int i = 0; i < n - 1; i++)
        {
            exchange = false;
            for (int j = n - 1; j > i; j--)
            {
                if (r[j].key < r[j - 1].key)
                {
                    temp = r[j];
                    r[j] = r[j - 1];
                    r[j - 1] = temp;
                    exchange = true;
                }
            }
            if (!exchange)
                return;
        }
    }

    /*************************************************/
    // 快速排序
    /*************************************************/
    static int quick_sort_partition(vector<sortType>& r, int s, int t)
    {
        int i = s;
        int j = t;
        sortType temp = r[i];

        while (i < j)
        {
            while (j > i && r[j].key >= temp.key)
            {
                j--;
            }
            r[i] = r[j];

            while (i < j && r[i].key <= temp.key)
            {
                i++;
            }
            r[j] = r[i];
        }
        r[i] = temp;
        return i;
    }

    static void quick_sort(vector<sortType>& r, int s, int t)
    {
        if (s < t)
        {
            int i = quick_sort_partition(r, s, t);
            quick_sort(r, s, i - 1);
            quick_sort(r, i + 1, t);
        }
    }

    /*************************************************/
    // 选择排序
    /*************************************************/
    static void select_sort(vector<sortType>& r)
    {
        int n = r.size();
        int minIndex;
        sortType temp;

        for (int i = 0; i < n - 1; i++)
        {
            minIndex = i;
            for (int j = i + 1; j < n; j++)
            {
                if (r[j].key < r[minIndex].key)
                    minIndex = j;
            }
            if (minIndex != i)
            {
                temp = r[minIndex];
                r[minIndex] = r[i];
                r[i] = temp;
            }
        }
    }

    /*************************************************/
    // 堆排序
    /*************************************************/
    static void heap_sort_sift(vector<sortType>& r, int low, int high)
    {
        int i = low;
        int j = 2 * i + 1; // 0-based index
        sortType temp = r[i];

        while (j <= high)
        {
            if (j < high && r[j].key < r[j + 1].key)
                j = j + 1;

            if (temp.key < r[j].key)
            {
                r[i] = r[j];
                i = j;
                j = 2 * i + 1;
            }
            else
            {
                break;
            }
        }
        r[i] = temp;
    }

    static void heap_sort(vector<sortType>& r)
    {
        int n = r.size();
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            heap_sort_sift(r, i, n - 1);
        }
        sortType temp;
        for (int i = n - 1; i > 0; i--)
        {
            temp = r[0];
            r[0] = r[i];
            r[i] = temp;
            heap_sort_sift(r, 0, i - 1);
        }
    }

    /*************************************************/
    // 归并排序
    /*************************************************/
    static void merge(vector<sortType>& r, int low, int mid, int high)
    {
        vector<sortType> s(high - low + 1);
        int i = low;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= high)
        {
            if (r[i].key <= r[j].key)
                s[k++] = r[i++];
            else
                s[k++] = r[j++];
        }
        while (i <= mid) s[k++] = r[i++];
        while (j <= high) s[k++] = r[j++];

        for (i = low, k = 0; i <= high; i++, k++)
        {
            r[i] = s[k];
        }
    }

    static void mergePass(vector<sortType>& r, int length)
    {
        int n = r.size();
        int i;
        for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
        {
            merge(r, i, i + length - 1, i + 2 * length - 1);
        }
        if (i + length - 1 < n - 1)
        {
            merge(r, i, i + length - 1, n - 1);
        }
    }

    static void merge_sort(vector<sortType>& r)
    {
        int n = r.size();
        for (int length = 1; length < n; length *= 2)
        {
            mergePass(r, length);
        }
    }

    /*************************************************/
    // 基数排序
    /*************************************************/
    static void radix_sort(vector<sortType>& r)
    {
        int n = r.size();
        if (n == 0) return;

        sortType maxElem = r[0];
        for (int i = 1; i < n; i++)
        {
            if (r[i].key > maxElem.key)
                maxElem = r[i];
        }

        int base = 1;
        vector<sortType> temp(n);

        while (maxElem.key / base > 0)
        {
            int bucket[10] = {0};

            for (int i = 0; i < n; i++)
            {
                bucket[(r[i].key / base) % 10]++;
            }
            for (int i = 1; i < 10; i++)
            {
                bucket[i] += bucket[i - 1];
            }
            for (int i = n - 1; i >= 0; i--)
            {
                int idx = (r[i].key / base) % 10;
                temp[bucket[idx] - 1] = r[i];
                bucket[idx]--;
            }
            r = temp;
            base *= 10;
        }
    }
};

int main()
{
    vector<sortType> data = { {'a','x',5}, {'b','y',3}, {'c','z',8} };
    mySort::insert_sort(data);
    mySort::bubble_sort(data);
    mySort::quick_sort(data, 0, data.size()-1);
    mySort::radix_sort(data);
    for (auto &e : data)
    {
        cout << e.info << " " << e.data << " " << e.key << endl;
    }
    return 0;
}

0x05 搜索

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <climits>
#include <utility>
#include <string>

using namespace std;

class SearchAll
{
private:
    vector<int> data;

public:
    // 构造函数，可初始化数据
    SearchAll() {}
    SearchAll(const vector<int>& vec) : data(vec) {}

    void setData(const vector<int>& vec)
    {
        data = vec;
    }

    vector<int> getData()
    {
        return data;
    }

    /********************
     * 线性搜索 (Linear Search)
     ********************/
    int linearSearch(int target)
    {
        for (size_t i = 0; i < data.size(); i++)
        {
            if (data[i] == target)
                return static_cast<int>(i); // 返回索引
        }
        return -1; // 未找到
    }

    /********************
     * 二分搜索 (Binary Search)
     * 数据需已排序
     ********************/
    int binarySearch(int target)
    {
        int left = 0;
        int right = static_cast<int>(data.size()) - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (data[mid] == target)
                return mid;
            else if (data[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }

    /********************
     * 哈希搜索 (unordered_set)
     ********************/
    bool hashSearch(int target)
    {
        unordered_set<int> s;
        for (size_t i = 0; i < data.size(); i++)
        {
            s.insert(data[i]);
        }
        return s.count(target) > 0;
    }
};

int main()
{
    vector<int> nums = {5, 3, 7, 1, 9, 4};
    SearchAll searcher(nums);
    cout << "Linear Search 7: " << searcher.linearSearch(7) << endl;
    cout << "Binary Search 3 (unsorted): " << searcher.binarySearch(3)
              << " (may fail if unsorted)" << endl;
    sort(nums.begin(), nums.end());
    searcher.setData(nums);
    cout << "Binary Search 3 (sorted): " << searcher.binarySearch(3) << endl;
    cout << "Hash Search 10: " << (searcher.hashSearch(10) ? "Found" : "Not found") << endl;
    return 0;
}

0x06 二叉搜索树

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <climits>
#include <utility>
#include <string>

using namespace std;

struct BSTNode
{
    int data;
    BSTNode* left;
    BSTNode* right;
    BSTNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class BSTree
{
private:
    BSTNode* root;

public:
    BSTree() : root(nullptr) {}
    ~BSTree() { clear(root); }

    BSTNode* getRoot() 
    { 
        return root; 
    }

    void insert(int val) 
    { // 插入节点
        root = insertRec(root, val); 
    }

    void remove(int val) 
    { // 删除节点
        root = removeRec(root, val); 
    }

    /********************
     * 非递归遍历
     ********************/
    void dfs_pre() 
    { // 前序
        if (!root) return;
        stack<BSTNode*> stk; stk.push(root);
        while (!stk.empty())
        {
            BSTNode* cur = stk.top(); stk.pop();
            cout << "->" << cur->data;
            if (cur->right) stk.push(cur->right);
            if (cur->left) stk.push(cur->left);
        }
        cout << endl;
    }

    void dfs_in() 
    { // 中序
        stack<BSTNode*> stk;
        BSTNode* cur = root;
        while (cur || !stk.empty())
        {
            while (cur) 
            { 
                stk.push(cur); 
                cur = cur->left; 
            }
            cur = stk.top(); 
            stk.pop();
            cout << "->" << cur->data;
            cur = cur->right;
        }
        cout << endl;
    }

    void dfs_post() 
    { // 后序
        if (!root) return;
        stack<BSTNode*> stk;
        BSTNode* cur = root, *prev = nullptr;
        while (cur || !stk.empty())
        {
            while (cur) 
            { 
                stk.push(cur); 
                cur = cur->left; 
            }
            BSTNode* temp = stk.top();
            if (!temp->right || temp->right == prev) 
            { 
                cout << "->" << temp->data; 
                stk.pop(); 
                prev = temp; 
            }
            else cur = temp->right;
        }
        cout << endl;
    }

    void bfs() 
    { // 层序遍历
        if (!root) return;
        queue<BSTNode*> q; q.push(root);
        while (!q.empty())
        {
            BSTNode* cur = q.front(); q.pop();
            cout << "->" << cur->data;
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        cout << endl;
    }

    /********************
     * 递归遍历
     ********************/
    void dfs_pre_rec()
    { //前序
        dfs_pre_rec_helper(root); 
        cout << endl; 
    }
    void dfs_in_rec() 
    { // 中序
        dfs_in_rec_helper(root); 
        cout << endl; 
    }
    void dfs_post_rec()
    { // 后序
        dfs_post_rec_helper(root); 
        cout << endl; 
    }

private:
    /********************
     * 内存释放
     ********************/
    void clear(BSTNode* node)
    {
        if (!node) return;
        clear(node->left);
        clear(node->right);
        delete node;
    }

    /********************
     * 递归插入
     ********************/
    BSTNode* insertRec(BSTNode* node, int val)
    {
        if (!node) return new BSTNode(val);
        if (val < node->data) node->left = insertRec(node->left, val);
        else if (val > node->data) node->right = insertRec(node->right, val);
        return node;
    }

    /********************
     * 递归删除
     ********************/
    BSTNode* removeRec(BSTNode* node, int val)
    {
        if (!node) return nullptr;
        if (val < node->data) node->left = removeRec(node->left, val);
        else if (val > node->data) node->right = removeRec(node->right, val);
        else
        {
            if (!node->left) 
            { 
                BSTNode* temp = node->right; 
                delete node; 
                return temp; 
            }
            if (!node->right) 
            { 
                BSTNode* temp = node->left; 
                delete node; 
                return temp; 
            }
            BSTNode* succ = node->right; 
            while(succ->left) succ = succ->left;
            node->data = succ->data;
            node->right = removeRec(node->right, succ->data);
        }
        return node;
    }

    /********************
     * 递归遍历辅助函数
     ********************/
    void dfs_pre_rec_helper(BSTNode* node) const
    {
        if (!node) return;
        cout << "->" << node->data;
        dfs_pre_rec_helper(node->left);
        dfs_pre_rec_helper(node->right);
    }

    void dfs_in_rec_helper(BSTNode* node) const
    {
        if (!node) return;
        dfs_in_rec_helper(node->left);
        cout << "->" << node->data;
        dfs_in_rec_helper(node->right);
    }

    void dfs_post_rec_helper(BSTNode* node) const
    {
        if (!node) return;
        dfs_post_rec_helper(node->left);
        dfs_post_rec_helper(node->right);
        cout << "->" << node->data;
    }
};

int main()
{
    BSTree tree;
    tree.insert(10); tree.insert(5); tree.insert(15);
    tree.insert(3); tree.insert(7); tree.insert(12);

    cout << "DFS Preorder (non-recursive): "; tree.dfs_pre();
    cout << "DFS Inorder (non-recursive): "; tree.dfs_in();
    cout << "DFS Postorder (non-recursive): "; tree.dfs_post();
    cout << "BFS Level order: "; tree.bfs();

    cout << "DFS Preorder (recursive): "; tree.dfs_pre_rec();
    cout << "DFS Inorder (recursive): "; tree.dfs_in_rec();
    cout << "DFS Postorder (recursive): "; tree.dfs_post_rec();

    tree.remove(5);
    cout << "After removing 5, DFS Inorder: "; tree.dfs_in();

    return 0;
}