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

一、C++中的STL

C++中的STL（Standard Template Library）是一個高效的數據結構和算法庫。它包含了眾多的數據結構，例如vector、set、map等等；同時也包含了一些常見的算法，例如排序算法、查找算法等等。它的高效性來自於使用模板實現，因此它可以在編譯時期進行類型檢查，並生成優化後的代碼。

下面以vector為例，展示如何使用STL中的數據結構。

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(3);
    vec.push_back(2);

    cout << "vector: ";
    for (auto i:vec)
        cout << i << " ";
    cout << endl;

    return 0;
}

以上代碼中定義了一個vector\，並向其中依次添加了1、3、2三個元素。最後使用迭代器遍歷輸出vector中的元素。使用STL的代碼簡潔、高效。

二、自定義數據結構

除了STL中提供的數據結構，我們也可以自定義數據結構來滿足特定的需求。以下是實現鏈表的代碼示例。

#include <iostream>

using namespace std;

// 鏈表節點的結構體
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 鏈表類
class LinkedList {
public:
    LinkedList() {
        head = NULL;
    }

    // 在鏈表頭部插入節點
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }

    // 在鏈表尾部插入節點
    void addAtTail(int val) {
        ListNode *node = new ListNode(val);
        if (!head) {
            head = node;
            return;
        }

        ListNode *tail = head;
        while (tail->next) {
            tail = tail->next;
        }
        tail->next = node;
    }

    // 在指定位置插入節點
    void addAtIndex(int index, int val) {
        if (index next;
        }
        if (!cur) {
            return;
        }

        node->next = cur->next;
        cur->next = node;
    }

    // 刪除指定位置的節點
    void deleteAtIndex(int index) {
        if (index next;
            return;
        }

        ListNode *cur = head;
        while (--index && cur) {
            cur = cur->next;
        }
        if (!cur->next) {
            return;
        }

        cur->next = cur->next->next;
    }

    // 獲取指定位置的節點的值
    int get(int index) {
        if (index next;
        }
        if (!cur) {
            return -1;
        }

        return cur->val;
    }

private:
    ListNode *head;
};

int main() {
    LinkedList list;
    list.addAtHead(1);
    list.addAtTail(3);
    list.addAtIndex(1, 2);
    list.deleteAtIndex(1);

    cout << list.get(1) << endl; // 輸出3

    return 0;
}

以上代碼中定義了一個LinkedList類，實現了鏈表節點的添加、刪除、查找等操作。鏈表是一種基礎的數據結構，在一些場景下可以提供比STL更高效的實現。

三、算法實現

在實現算法時，我們需要深入理解算法思路，並使用高效的數據結構加以實現。以下是LeetCode問題“兩數相加”的代碼實現。

#include <iostream>

using namespace std;

// 鏈表節點的結構體
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = NULL;
        ListNode *tail = NULL;
        int carry = 0;

        while (l1 || l2 || carry) {
            int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            carry = sum / 10;
            sum %= 10;

            if (!head) {
                head = tail = new ListNode(sum);
            } else {
                tail = tail->next = new ListNode(sum);
            }

            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }

        return head;
    }
};

int main() {
    Solution solution;
    ListNode *l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    ListNode *l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    ListNode *result = solution.addTwoNumbers(l1, l2);

    while (result) {
        cout << result->val << " ";
        result = result->next;
    }
    cout << endl; // 輸出7 0 8

    return 0;
}

以上代碼實現了兩個鏈表的相加操作。算法思路簡單，但需要使用高效的鏈表數據結構實現。

四、總結

C++提供了豐富的數據結構和算法庫，包括STL和自定義數據結構等；同時也提供了高效的模板實現，可以大大縮短開發時間。在實際開發中，要深入理解算法思路，並根據場景選擇恰當的數據結構，以實現最優的代碼。