數據結構: C++實現常用演算法及數據結構

一、數組與鏈表

1、數組是一組連續的內存空間，可以進行隨機訪問，其增刪操作較為低效。鏈表是由一系列結點組成，每個結點包含數據和指向下一個結點的指針，其插入刪除操作較為高效，但是訪問元素時需要遍歷整個鏈表，時間複雜度為O(n)。

2、示例代碼：

//定義一個數組
int arr[5] = {1,2,3,4,5};

//定義一個鏈表結點
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//創建鏈表
ListNode* head = new ListNode(1);
ListNode* node1 = new ListNode(2);
ListNode* node2 = new ListNode(3);
ListNode* node3 = new ListNode(4);
ListNode* node4 = new ListNode(5);
head->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;

二、棧和隊列

1、棧是一種後進先出的數據結構，其存儲方式可以使用數組或鏈表實現。可以使用棧來實現一些逆序輸出的問題，如字元串逆置、括弧匹配等。隊列是一種先進先出的數據結構，其存儲方式同樣可以使用數組或鏈表實現。隊列可以用來解決廣度優先遍歷的問題。

2、示例代碼：

//定義一個棧
stack stk;
stk.push(1);
stk.push(2);
stk.push(3);
int x = stk.top(); //獲取棧頂元素
stk.pop(); //彈出棧頂元素

//定義一個隊列
queue q;
q.push(1);
q.push(2);
q.push(3);
int x = q.front(); //獲取隊首元素
q.pop(); //彈出隊首元素

三、哈希表

哈希表是一種根據鍵(key)直接訪問內存地址的數據結構，其查找、插入、刪除操作的平均時間複雜度為O(1)。哈希函數是實現哈希表的關鍵，決定了如何將鍵轉化為內存地址。哈希函數需要滿足以下兩個條件：（1）散列均勻；（2）盡量避免哈希衝突。常用的哈希函數包括取模法、乘法哈希等。

2、示例代碼：

//定義一個哈希表
unordered_map mp;
mp["apple"] = 10;
mp["orange"] = 3;

//查找元素
if (mp.find("apple") != mp.end()) {
    int x = mp["apple"];
}

//遍歷哈希表
for (auto& it : mp) {
    cout << it.first << ":" << it.second << endl;
}

四、堆

堆是一種動態的數據結構，它分為最大堆和最小堆。其中最大堆要求父結點的值大於或等於子結點的值，最小堆要求父結點的值小於或等於子結點的值。堆可以用於解決一些查找最大/小值的問題，如Top K 問題、求中位數等。

2、示例代碼：

//定義一個最小堆
priority_queue<int, vector, greater> pq;
pq.push(3);
pq.push(1);
pq.push(4);
int x = pq.top(); //獲取堆頂元素
pq.pop(); //彈出堆頂元素

五、圖

圖由結點和邊組成，其中結點可以包含任意信息，邊可以包含權值等信息。圖的遍歷方式有深度優先遍歷和廣度優先遍歷。深度優先遍歷可以使用遞歸或棧來實現，廣度優先遍歷可以使用隊列來實現。圖的常見演算法包括最短路徑演算法、最小生成樹演算法、網路流演算法等。

2、示例代碼：

//定義一個圖（使用鄰接表表示）
vector<vector> graph(n);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);
graph[2].push_back(3);

//DFS遍歷
vector visited(n); //標記是否訪問過
void DFS(int node) {
    visited[node] = true;
    //訪問當前結點
    for (int i = 0; i < graph[node].size(); i++) {
        int next_node = graph[node][i];
        if (!visited[next_node]) {
            DFS(next_node);
        }
    }
}

//BFS遍歷
queue q;
vector visited(n); //標記是否訪問過
void BFS(int start) {
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        //訪問當前結點
        for (int i = 0; i < graph[node].size(); i++) {
            int next_node = graph[node][i];
            if (!visited[next_node]) {
                q.push(next_node);
                visited[next_node] = true;
            }
        }
    }
}