用C++實現高效數據結構和演算法

一、數據結構與演算法C++實現

C++作為面向對象的編程語言，能夠非常好地支持數據結構和演算法的實現。具體實現方法包括：

    //定義一個單鏈表節點
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    //定義一個二叉樹節點
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    //定義一個並查集，給予素數的不相交集合實現，以便路徑壓縮和按秩合併。
    class UnionFind {
    public:
        UnionFind(int N): count(N) {
            parent = new int[N];
            rank = new int[N];
            for (int i = 0; i  rank[rootQ]) {
                parent[rootQ] = rootP;
                rank[rootP] += rank[rootQ];
            } else {
                parent[rootP] = rootQ;
                rank[rootQ] += rank[rootP];
            }
            count--;
        }
    
        int getCount() const {
            return count;
        }
    
        ~UnionFind() {
            delete[] parent;
            delete[] rank;
        }
    private:
        int count;
        int* parent;
        int* rank;
    };

上述數據結構的實現，僅是維度其基本結構，更加常用的是在這些基本結構上進行各種演算法操作。例如使用鏈表實現歸併排序:

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    
    ListNode* mergeKLists(vector& lists) {
        int n = lists.size();
        if (n == 0) return nullptr;
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[i + k]);
            }
            n = k;
        }
        return lists[0];
    }

二、數據結構與演算法實現

根據不同的場景需求，選擇不同的數據結構與演算法實現，能夠更好地提升程序的運行效率。舉例來說，選取下面幾種演算法實現:

1. 雙指針演算法

常見於數組和鏈表的問題中，使用兩個指針解決問題。

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* fast = dummy;
    ListNode* slow = dummy;
    while (n--) fast = fast->next;  //fast先走n步
    while (fast && fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* tmp = slow->next;
    slow->next = slow->next->next;
    delete tmp;
    return dummy->next;
}

2. 排序演算法

能避免線性查找的單次O(N)時間複雜度，主要有快速排序、歸併排序等。

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    int pivot = arr[left];
    int l = left + 1;
    int r = right;
    while (l <= r) {
        if (arr[l]  pivot) {
            swap(arr[l], arr[r]);
            l++;
            r--;
        }
        if (arr[l] >= pivot) l++;
        if (arr[r] <= pivot) r--;
    }
    swap(arr[left], arr[r]);
    quickSort(arr, left, r - 1);
    quickSort(arr, r + 1, right);
}

3. 搜索演算法

能夠優化遍歷的演算法，主要有深度優先搜索、廣度優先搜索等。

void dfs(TreeNode* root, vector& res) {
    if (root == nullptr) return;
    res.push_back(root->val);
    dfs(root->left, res);
    dfs(root->right, res);
}

vector preorderTraversal(TreeNode* root) {
    vector res;
    dfs(root, res);
    return res;
}

三、總結

本文從數據結構與演算法C++實現、數據結構與演算法實現兩個方面，講解了用C++實現高效數據結構和演算法的方法。在實現中，使用到了面向對象編程思想、各種常見的搜索、排序、計算等演算法的實現，減少了多重循環，提高了代碼運行效率。希望能夠對讀者的C++程序設計和演算法實現能有所幫助。