用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 < N; ++i) {
                parent[i] = i;
                rank[i] = 1;
            }
        }
    
        int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }
    
        void Union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            if (rank[rootP] > 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 < l2->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 && arr[r] > 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++程序设计和算法实现能有所帮助。