第一章：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

1、鏈表

• 動(dòng)態(tài)鏈表

  • 動(dòng)態(tài)鏈表需要臨時(shí)分配鏈表節(jié)點(diǎn)，使用完畢后釋放。

  • 優(yōu)點(diǎn)：能及時(shí)釋放空間，不使用多余內(nèi)存

  • 缺點(diǎn)：需要管理空間，容易出錯(cuò)（競(jìng)賽一般不用動(dòng)態(tài)鏈表）

  • #include<iostream>
    using namespace std;
    
    // n 個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù),數(shù)到m 的人出列，再由下一個(gè)人重新從1 開(kāi)始報(bào)數(shù)，
    // 數(shù)到m 的人再出圈，依次類(lèi)推，直到所有的人都出圈，請(qǐng)輸出依次出圈人的編號(hào)。
    
    // 用動(dòng)態(tài)鏈表實(shí)現(xiàn)
    
    // 結(jié)構(gòu)
    struct Node {
        int data;       // 存儲(chǔ)編號(hào)
        Node* next;     // 指向下一個(gè)節(jié)點(diǎn)的指針
    };
    typedef Node* pN;   // 定義指向Node的指針類(lèi)型為pN
    
    int main() {
        int n, m;
        cin >> n >> m;
    
        // 建立循環(huán)鏈表
        pN head = new Node; // 創(chuàng)建頭節(jié)點(diǎn)
        head->data = 1;
        head->next = nullptr;
        pN pCurrent = head; // 當(dāng)前節(jié)點(diǎn)指針
    
        // 依次創(chuàng)建節(jié)點(diǎn)，構(gòu)建循環(huán)鏈表
        for (int i = 2; i <= n; i++) {
            pN p = new Node;
            p->data = i;
            p->next = nullptr;
            pCurrent->next = p;
            pCurrent = p;
        }
    
        pCurrent->next = head; // 將鏈表閉合成循環(huán)
    
        // 循環(huán)計(jì)數(shù)、出列
        int k = 1;
        while (pCurrent != pCurrent->next) {
            if (k == m) {
                pN p = pCurrent->next;
                cout << p->data << " "; // 輸出出列人的編號(hào)
                pCurrent->next = p->next;
                delete p; // 釋放出列人的節(jié)點(diǎn)
                k = 1;
            } else {
                k++;
                pCurrent = pCurrent->next;
            }
        }
        cout << pCurrent->data; // 輸出最后一個(gè)出列人的編號(hào)
        delete pCurrent; // 釋放最后一個(gè)節(jié)點(diǎn)
    
        return 0;
    }
    

• 靜態(tài)鏈表

  • 靜態(tài)鏈表使用預(yù)先分配的一段連續(xù)空間存儲(chǔ)鏈表，這種鏈表在邏輯上是成立的。

  • 有兩種做法：

    • 定義鏈表結(jié)構(gòu)體數(shù)組，和動(dòng)態(tài)鏈表差不多。
    • 使用一維數(shù)組，直接在靜態(tài)數(shù)組上實(shí)現(xiàn)。

  • 用結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)單向靜態(tài)鏈表

    #include<iostream>
    using namespace std;
    
    // n 個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù),數(shù)到m 的人出列，再由下一個(gè)人重新從1 開(kāi)始報(bào)數(shù)，
    // 數(shù)到m 的人再出圈，依次類(lèi)推，直到所有的人都出圈，請(qǐng)輸出依次出圈人的編號(hào)。
    
    const int N = 105;
    
    // 結(jié)構(gòu)體定義
    struct Node {
        int id;        // 編號(hào)
        int nextid;    // 下一個(gè)節(jié)點(diǎn)的編號(hào)
    } nodes[N];
    
    int main() {
        int n, m;
        cin >> n >> m;
    
        // 初始化單向靜態(tài)鏈表
        for (int i = 0; i < n - 1; i++) {
            nodes[i].id = i + 1;
            nodes[i].nextid = i + 1;
        }
        nodes[n - 1].id = n;
        nodes[n - 1].nextid = 0;
    
        int i = n - 1;
        int k = 1;
    
        // 循環(huán)計(jì)數(shù)、出列
        while (nodes[i].nextid != i) {
            if (k == m) {
                int j = nodes[i].nextid;
                nodes[i].nextid = nodes[j].nextid;
                cout << nodes[j].id << " "; // 輸出出列人的編號(hào)
                k = 1;
            } else {
                k++;
                i = nodes[i].nextid;
            }
        }
    
        cout << nodes[i].id; // 輸出最后一個(gè)出列人的編號(hào)
        return 0;
    }
    
    

  • 用一維數(shù)組實(shí)現(xiàn)單向靜態(tài)鏈表

    #include<iostream>
    using namespace std;
    
    // n 個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù),數(shù)到m 的人出列，再由下一個(gè)人重新從1 開(kāi)始報(bào)數(shù)，
    // 數(shù)到m 的人再出圈，依次類(lèi)推，直到所有的人都出圈，請(qǐng)輸出依次出圈人的編號(hào)。
    
    // 用一維數(shù)組實(shí)現(xiàn)單向靜態(tài)鏈表
    // 定義一個(gè) nodes[] 數(shù)組，nodes[i] 中的 i 就是結(jié)點(diǎn)的值，nodes[i] 里的數(shù)就是下一個(gè)節(jié)點(diǎn)
    int nodes[150];
    
    int main() {
        int n, m;
        cin >> n >> m;
    
        // 初始化單向靜態(tài)鏈表
        for (int i = 1; i < n; i++) {
            nodes[i] = i + 1;
        }
        nodes[n] = 1;
    
        int now = n, prev = 1;
    
        // 循環(huán)計(jì)數(shù)、出列
        while (nodes[now] != now) {
            if (prev == m) {
                cout << nodes[now] << " "; // 輸出出列人的編號(hào)
                nodes[now] = nodes[nodes[now]]; // 跳過(guò)當(dāng)前出列的節(jié)點(diǎn)
            } else {
                prev++;
                now = nodes[now];
            }
        }
    
        return 0;
    }
    

• STL list

  • 在算法競(jìng)賽或工程項(xiàng)目中經(jīng)常使用C++STL list。它是雙向鏈表，由標(biāo)準(zhǔn)模板庫(kù)管理。通過(guò)迭代器訪問(wèn)節(jié)點(diǎn)數(shù)據(jù)，高效的刪除和插入。

  • list的一些重要函數(shù)：

    • list容器的創(chuàng)建：假設(shè)是int型
      • 創(chuàng)建空容器：std::list<int> values;
      • 創(chuàng)建包含n個(gè)元素的容器：std::list<int> values(10);
      • 創(chuàng)建包含n個(gè)元素，并都賦初值的容器：std::list<int> values(10, 5);
      • 拷貝已有l(wèi)ist容器：std::list<int> values2(values1);
    • 返回指向容器中第一個(gè)元素的雙向迭代器：values.begin();
    • 返回指向容器中最后一個(gè)元素所在位置的下一個(gè)位置的雙向迭代器：values.end();
    • 判斷容器中是否有元素，若無(wú)元素，則返回 true；反之，返回 false：values.empty();
    • 返回當(dāng)前容器實(shí)際包含的元素個(gè)數(shù)：values.size();
    • 返回第一個(gè)元素的引用：values.front();
    • 返回最后一個(gè)元素的引用：values.back();
    • 在容器頭部或尾部插入一個(gè)元素：values.push_front(); values.push_back();
    • 刪除容器頭部或尾部的一個(gè)元素：vlaues.pop_front(); values.pop_back();
    • 在容器中的指定位置插入元素：vlaues.insert();
    • 刪除容器中一個(gè)或某區(qū)域內(nèi)的元素：vlaues.erase();

  • #include<iostream>
    #include<list>
    using namespace std;
    
    // n 個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù),數(shù)到m 的人出列，再由下一個(gè)人重新從1 開(kāi)始報(bào)數(shù)，
    // 數(shù)到m 的人再出圈，依次類(lèi)推，直到所有的人都出圈，請(qǐng)輸出依次出圈人的編號(hào)。
    
    // STL模板庫(kù)list實(shí)現(xiàn)功能
    
    int main() {
        int n, m;
        cin >> n >> m;
    
        // 使用STL模板庫(kù)中的list作為鏈表
        list<int> node;
    
        // 初始化鏈表
        for (int i = 1; i <= n; i++) {
            node.push_back(i);
        }
    
        // 迭代器指向鏈表頭部
        list<int>::iterator it = node.begin();
    
        // 循環(huán)直到鏈表中只剩一個(gè)元素
        while (node.size() > 1) {
            // 循環(huán)報(bào)數(shù)，找到第m個(gè)元素
            for (int i = 1; i < m; i++) {
                it++;
                // 如果迭代器達(dá)到鏈表末尾，將其置為鏈表頭部
                if (it == node.end())
                    it = node.begin();
            }
    
            // 輸出出列的人的編號(hào)
            cout << *it << " ";
    
            // 獲取下一個(gè)元素的迭代器
            list<int>::iterator next = ++it;
    
            // 如果下一個(gè)迭代器達(dá)到鏈表末尾，將其置為鏈表頭部
            if (next == node.end())
                next = node.begin();
    
            // 刪除出列的人
            node.erase(--it);
    
            // 更新迭代器為下一個(gè)元素
            it = next;
        }
    
        // 輸出最后剩下的人的編號(hào)
        cout << *it;
    
        return 0;
    }
    

2、隊(duì)列

? 競(jìng)賽一般用STL queue或手寫(xiě)靜態(tài)數(shù)組實(shí)現(xiàn)隊(duì)列

• STL queue

  • STL queue的主要操作：

    • 創(chuàng)建隊(duì)列：queue<int> q;
    • 將item插入隊(duì)列：q.push(item);
    • 返回隊(duì)首元素：q.front();
    • 刪除隊(duì)首元素：q.pop();
    • 返回隊(duì)尾元素：q.back();
    • 返回元素個(gè)數(shù)：q.size();
    • 檢查隊(duì)列是否為空：q.empty();

  • #include<iostream>
    #include<queue>
    using namespace std;
    
    // 假設(shè)內(nèi)存中有 M 個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過(guò) M?1，
    // 軟件會(huì)將新單詞存入一個(gè)未使用的內(nèi)存單元；若內(nèi)存中已存入 M 個(gè)單詞，軟件會(huì)清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來(lái)，存放新單詞。
    // 假設(shè)一篇英語(yǔ)文章的長(zhǎng)度為 N 個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開(kāi)始前，內(nèi)存中沒(méi)有任何單詞。
    
    // 使用哈希表和隊(duì)列存單詞，查單詞用哈希表查，用隊(duì)列騰出單元
    
    int Hash[1000] = { 0 };
    
    int main() {
        int m, n;
        cin >> m >> n;
        int cnt = 0;
    
        // 使用隊(duì)列保存內(nèi)存中的單詞順序
        queue<int> q;
    
        for (int i = 1; i <= n; i++) {
            int t;
            cin >> t;
    
            // 如果單詞未在內(nèi)存中，將其存入內(nèi)存
            if (Hash[t] == 0) {
                cnt++;
                Hash[t] = 1;
                q.push(t);
    
                // 如果內(nèi)存中單詞數(shù)超過(guò) M，騰出最早進(jìn)入內(nèi)存的單元
                if (q.size() > m) {
                    Hash[q.front()] = 0;
                    q.pop();
                }
            }
        }
    
        // 輸出外存查找次數(shù)
        cout << cnt;
    
        return 0;
    }
    
    

• 手寫(xiě)循環(huán)隊(duì)列

  • 下面是循環(huán)隊(duì)列的手寫(xiě)模板，競(jìng)賽一般用靜態(tài)分配空間

  • #include<iostream>
    using namespace std;
    
    // 假設(shè)內(nèi)存中有 M 個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過(guò) M?1，
    // 軟件會(huì)將新單詞存入一個(gè)未使用的內(nèi)存單元；若內(nèi)存中已存入 M 個(gè)單詞，軟件會(huì)清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來(lái)，存放新單詞。
    // 假設(shè)一篇英語(yǔ)文章的長(zhǎng)度為 N 個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開(kāi)始前，內(nèi)存中沒(méi)有任何單詞。
    
    // 使用哈希表和手寫(xiě)循環(huán)隊(duì)列存單詞，查單詞用哈希表查，用隊(duì)列騰出單元
    
    const int N = 1000;
    int Hash[N] = { 0 };
    
    // 手寫(xiě)循環(huán)隊(duì)列結(jié)構(gòu)體
    struct my_queue {
        int data[N];
        int head, rear;
    
        // 構(gòu)造隊(duì)列
        my_queue() : head(0), rear(0) {};
    
        // 返回隊(duì)列長(zhǎng)度
        int size() { return (rear - head + N) % N; }
    
        // 判空操作
        bool empty() {
            return size() == 0;
        }
    
        // 入隊(duì)
        bool push(int e) {
            if ((rear + 1) % N == head)
                return false;
            data[rear] = e;
            rear = (rear + 1) % N;
            return true;
        }
    
        // 出隊(duì)
        bool pop() {
            if (head == rear) {
                return false;
            }
            head = (head + 1) % N;
            return true;
        }
    
        // 返回隊(duì)頭元素
        int front() {
            return data[head];
        }
    } q;
    
    int main() {
        int m, n;
        cin >> m >> n;
        int cnt = 0;
    
        for (int i = 1; i <= n; i++) {
            int t;
            cin >> t;
            if (Hash[t] == 0) {
                cnt++;
                Hash[t] = 1;
                q.push(t);
    
                // 如果隊(duì)列長(zhǎng)度超過(guò) M，騰出最早進(jìn)入隊(duì)列的元素
                if (q.size() > m) {
                    Hash[q.front()] = 0;
                    q.pop();
                }
            }
        }
    
        // 輸出外存查找次數(shù)
        cout << cnt;
    
        return 0;
    }
    

• 雙端隊(duì)列和單調(diào)隊(duì)列

  • 雙端隊(duì)列和單調(diào)隊(duì)列的概念

    • 雙端隊(duì)列是具有隊(duì)列和棧性質(zhì)的數(shù)據(jù)結(jié)構(gòu)，它能且只能在兩端插入或刪除
    • STL的雙端隊(duì)列deque的用法如下：
      • 創(chuàng)建雙端隊(duì)列：deque<int> dq;
      • 返回隊(duì)頭：dq.front();
      • 返回隊(duì)尾：dq.back();
      • 刪除隊(duì)頭：dq.pop_front();
      • 刪除隊(duì)尾：dq.pop_back();
      • 在隊(duì)頭添加一個(gè)元素e：dq.push_front(e);
      • 在隊(duì)尾添加一個(gè)元素e：dq.push_back(e);
    • 單調(diào)隊(duì)列是雙端隊(duì)列的經(jīng)典應(yīng)用，單調(diào)隊(duì)列里的元素是單調(diào)有序的
    • 單調(diào)隊(duì)列里的元素的順序和原來(lái)在序列中的順序是一致的；

  • 單調(diào)隊(duì)列的應(yīng)用：滑動(dòng)窗口：

    #include<iostream>
    #include<deque>
    using namespace std;
    
    // 有一個(gè)長(zhǎng)為 n 的序列 a，以及一個(gè)大小為 k 的窗口。窗口從左邊開(kāi)始向右滑動(dòng)，
    // 每次滑動(dòng)一個(gè)單位，求每次滑動(dòng)后窗口中的最大值和最小值。
    
    // 如果每次移動(dòng)窗口，都要檢查 k 個(gè)數(shù)來(lái)計(jì)算最大值和最小值，那么它就要檢查 O(nk) 次。
    // 可以使用單調(diào)隊(duì)列來(lái)優(yōu)化移動(dòng)窗口，每次移動(dòng)窗口時(shí)，對(duì)應(yīng)的單調(diào)隊(duì)列就要丟棄和增加相應(yīng)元素，并輸出最大值和最小值（需要兩個(gè)單調(diào)隊(duì)列）。
    // 優(yōu)化后只需要檢查 3n 次。
    
    // 單調(diào)遞增隊(duì)列，保存元素下標(biāo)
    deque<int> maxDeque;
    // 單調(diào)遞減隊(duì)列，保存元素下標(biāo)
    deque<int> minDeque;
    
    // 主函數(shù)
    int main() {
        // 輸入序列長(zhǎng)度和窗口大小
        int n, k;
        cin >> n >> k;
        
        // 輸入序列
        int list[1000000];
        for (int i = 0; i < n; i++) {
            cin >> list[i];
        }
    
        int head = 0, rear = 0;
    
        // 處理單調(diào)遞增隊(duì)列
        for (; rear <= k - 1; rear++) {
            int t = list[rear];
            // 保持隊(duì)列單調(diào)遞增，丟棄比當(dāng)前元素小的元素
            while (!maxDeque.empty() && list[maxDeque.back()] < t) {
                maxDeque.pop_back();
            }
            maxDeque.push_back(rear);  // 將當(dāng)前元素下標(biāo)加入隊(duì)列
        }
        cout << list[maxDeque.front()] << " ";  // 輸出當(dāng)前窗口的最大值
        rear--;
    
        // 繼續(xù)處理后續(xù)窗口
        while (rear != n - 1) {
            rear++;
            int t = list[rear];
            // 保持隊(duì)列單調(diào)遞增，丟棄比當(dāng)前元素小的元素
            while (!maxDeque.empty() && list[maxDeque.back()] < t) {
                maxDeque.pop_back();
            }
            maxDeque.push_back(rear);  // 將當(dāng)前元素下標(biāo)加入隊(duì)列
            // 檢查隊(duì)首元素是否仍在當(dāng)前窗口內(nèi)，不在則出隊(duì)
            if (maxDeque.front() == head) {
                maxDeque.pop_front();
            }
            cout << list[maxDeque.front()] << " ";  // 輸出當(dāng)前窗口的最大值
            head++;
        }
        cout << endl;
    
        head = rear = 0;
    
        // 處理單調(diào)遞減隊(duì)列
        for (; rear <= k - 1; rear++) {
            int t = list[rear];
            // 保持隊(duì)列單調(diào)遞減，丟棄比當(dāng)前元素大的元素
            while (!minDeque.empty() && list[minDeque.back()] > t) {
                minDeque.pop_back();
            }
            minDeque.push_back(rear);  // 將當(dāng)前元素下標(biāo)加入隊(duì)列
        }
        cout << list[minDeque.front()] << " ";  // 輸出當(dāng)前窗口的最小值
        rear--;
    
        // 繼續(xù)處理后續(xù)窗口
        while (rear != n - 1) {
            rear++;
            int t = list[rear];
            // 保持隊(duì)列單調(diào)遞減，丟棄比當(dāng)前元素大的元素
            while (!minDeque.empty() && list[minDeque.back()] > t) {
                minDeque.pop_back();
            }
            minDeque.push_back(rear);  // 將當(dāng)前元素下標(biāo)加入隊(duì)列
            // 檢查隊(duì)首元素是否仍在當(dāng)前窗口內(nèi)，不在則出隊(duì)
            if (minDeque.front() == head) {
                minDeque.pop_front();
            }
            cout << list[minDeque.front()] << " ";  // 輸出當(dāng)前窗口的最小值
            head++;
        }
    
        return 0;
    }
    

• 優(yōu)先隊(duì)列

  • 優(yōu)先隊(duì)列由堆組成，有最小優(yōu)先隊(duì)列和最大優(yōu)先隊(duì)列，每個(gè)出隊(duì)元素都是隊(duì)內(nèi)最小或最大值。
  • STL優(yōu)先隊(duì)列的操作：
    • 大頂堆的創(chuàng)建：priority_queue<int> max_pq;
    • 小頂堆的創(chuàng)建：priority_queue<int, vector<int>, greater<int>> min_pq;
    • 將元素插入到優(yōu)先隊(duì)列中：max_pq.push(item);
    • 彈出優(yōu)先隊(duì)列堆頂：max_pq.pop();
    • 返回優(yōu)先隊(duì)列堆頂元素：max_pq.top();
    • 返回優(yōu)先隊(duì)列中的元素個(gè)數(shù)：max_pq.size();
    • 檢查優(yōu)先隊(duì)列是否為空：max_pq.empty();

3、棧

• STL stack

  • 競(jìng)賽一般直接用STLstack，或這自己手寫(xiě)靜態(tài)棧。

  • STL stack的有關(guān)操作：

    • 棧的創(chuàng)建：stack<int> s;
    • 將元素存入棧頂：s.push(item);
    • 返回棧頂元素：s.top(item);
    • 刪除棧頂元素：s.pop(item);
    • 返回棧中元素個(gè)數(shù)：s.size();
    • 檢查棧是否為空：s.empty();

  • #include<iostream>
    #include<stack>
    using namespace std;
    
    // 反轉(zhuǎn)字符串
    // 使用 STL stack 來(lái)完成操作
    
    int main() {
        stack<char> s;
        char c;
    
        // 從標(biāo)準(zhǔn)輸入逐字符讀取，直到遇到換行符
        c = getchar();
        while (c != '\n') {
            if (c == ' ' && !s.empty()) {
                // 如果遇到空格且棧非空，輸出棧內(nèi)字符，并加上空格
                while (!s.empty()) {
                    char t;
                    t = s.top();
                    s.pop();
                    cout << t;
                }
                cout << " ";
            }
            else {
                // 非空格字符入棧
                s.push(c);
            }
            // 繼續(xù)讀取下一個(gè)字符
            c = getchar();
        }
    
        // 處理最后一個(gè)單詞
        if (!s.empty()) {
            while (!s.empty()) {
                char t;
                t = s.top();
                s.pop();
                cout << t;
            }
            cout << " ";
        }
    
        return 0;
    }
    
    

• 手寫(xiě)棧

  • 手寫(xiě)靜態(tài)棧代碼簡(jiǎn)單且節(jié)省空間

  • #include<iostream>
    using namespace std;
    
    //反轉(zhuǎn)字符串
    
    //使用STLstack來(lái)完成操作
    const int N = 100100;
    struct my_stack {
    	char a[N];
    	int t = 0;
    	void push(char x) { a[++t] = x; }
    	void pop() { t--; }
    	char top() { return a[t]; }
    	int empty() { return t == 0 ? 1 : 0; }
    }s;
    int main() {
    	char c;
    	c = getchar();
    	while (c != '\n') {
    		if (c == ' ' && !s.empty()) {
    			while (!s.empty()) {
    				char t;
    				t = s.top();
    				s.pop();
    				cout << t;
    			}
    			cout << " ";
    		}
    		else {
    			s.push(c);
    		}
    		c = getchar();
    	}
    	if (!s.empty()) {
    		while (!s.empty()) {
    			char t;
    			t = s.top();
    			s.pop();
    			cout << t;
    		}
    		cout << " ";
    	}
    	return 0;
    }
    

• 單調(diào)棧

  • 單調(diào)棧中的元素是單調(diào)遞增或單調(diào)遞減的，比如遞減棧從棧頂?shù)綏５资菑拇蟮叫∨判虻摹?/p>

  • 單調(diào)棧的操作：比如遞減棧，當(dāng)一個(gè)元素入棧時(shí)，與棧頂比較，若比棧頂小，則入棧，若比棧頂大，這彈出棧頂，直到比棧頂元素小，則入棧。注意，每個(gè)數(shù)都會(huì)入棧。

  • #include<iostream>
    #include<stack>
    using namespace std;
    
    // N(1 << N << 10^5)頭奶牛站成一排，奶牛i的身高為Hi(1 <= Hi <= 1000000)。
    // 現(xiàn)在，每頭奶牛都在向右看齊。對(duì)于奶牛i，如果奶牛j滿(mǎn)足i < j 且Hi < Hj，我們就說(shuō)奶牛i仰望奶牛j。
    // 求出每頭奶牛離他最近的仰望對(duì)象
    
    // 暴力解法：遍歷序列，在每個(gè)奶牛的序列右邊找到它的仰望對(duì)象，復(fù)雜度在所有奶牛都沒(méi)有仰望對(duì)象的情況下是O(nlog2N)
    
    // 單調(diào)棧優(yōu)化：由于單調(diào)棧的特性是每個(gè)元素都入棧，且棧內(nèi)元素都是單調(diào)性的，所有可以用它來(lái)優(yōu)化暴力
    // 從后往前遍歷序列，每次將元素壓入單調(diào)棧時(shí)，棧頂元素就是該元素的仰望對(duì)象，?？辗祷?，復(fù)雜度是O(n)
    
    int a[100001]; // 存儲(chǔ)奶牛的身高
    int b[100001]; // 存儲(chǔ)每頭奶牛的仰望對(duì)象
    
    int main() {
        int n;
        cin >> n;
    
        // 輸入每頭奶牛的身高
        for (int i = 1; i <= n; i++) {
            int t;
            cin >> t;
            a[i] = t;
        }
    
        stack<int> s; // 單調(diào)棧，用于存儲(chǔ)奶牛的序號(hào)
    
        // 從后往前遍歷奶牛序列，求解每頭奶牛的仰望對(duì)象
        for (int i = n; i >= 1; i--) {
            // 單調(diào)棧維護(hù)單調(diào)遞減的序號(hào)
            while (!s.empty() && a[s.top()] <= a[i]) {
                s.pop();
            }
    
            // 如果棧為空，表示沒(méi)有比當(dāng)前奶牛更高的奶牛，仰望對(duì)象為0
            if (s.empty()) {
                b[i] = 0;
                s.push(i);
            } else {
                // 棧頂元素即為當(dāng)前奶牛的仰望對(duì)象
                b[i] = s.top();
                s.push(i);
            }
        }
    
        // 輸出每頭奶牛的仰望對(duì)象
        for (int i = 1; i <= n; i++) {
            cout << b[i] << " ";
        }
    
        return 0;
    }
    
    

4、二叉樹(shù)和哈夫曼樹(shù)

• 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

  • 動(dòng)態(tài)二叉樹(shù)

    • struct Node{
          int value;	//節(jié)點(diǎn)的值
          node* lson, *rson;	//指向左右孩子的指針
      };
      

    • 動(dòng)態(tài)新建一個(gè)Node時(shí)，需要手動(dòng)分配內(nèi)存，使用完畢后，還要釋放它，以防內(nèi)存泄漏。

    • 動(dòng)態(tài)二叉樹(shù)的優(yōu)點(diǎn)是不浪費(fèi)空間，缺點(diǎn)是需要管理，容易出錯(cuò)。

  • 靜態(tài)二叉樹(shù)

    • struct Node{
          char value;		//節(jié)點(diǎn)的值
          int lson, rson;	//左右孩子的坐標(biāo)
      }tree[N];
      

    • 由于靜態(tài)二叉樹(shù)編碼簡(jiǎn)單，在算法競(jìng)賽中一般使用靜態(tài)二叉樹(shù)。

    • 編碼時(shí)一般不用tree[0]，因?yàn)?被用來(lái)表示空節(jié)點(diǎn)，當(dāng)一個(gè)節(jié)點(diǎn)的左右子樹(shù)為空時(shí)就可以表示為lson = rson = 0;

    • 特別的，當(dāng)用數(shù)組實(shí)現(xiàn)完全二叉樹(shù)時(shí)，可以不用定義lson,rson。一顆節(jié)點(diǎn)總數(shù)為k的完全二叉樹(shù)，設(shè)一號(hào)節(jié)點(diǎn)為根節(jié)點(diǎn)，有以下性質(zhì)：

      • 編號(hào)i > 1的節(jié)點(diǎn)，其父結(jié)點(diǎn)編號(hào)是i / 2。
      • 如果2i > k，說(shuō)明節(jié)點(diǎn) i 沒(méi)有孩子；如果2i + 1 > k, 那么節(jié)點(diǎn) i 沒(méi)有右孩子。
      • 如果節(jié)點(diǎn) i 有孩子，那么它的左孩子是2i，它的右孩子是2i + 1。

  • 多叉樹(shù)轉(zhuǎn)化為二叉樹(shù)

    • 將多叉樹(shù)的第一個(gè)孩子作為右孩子，將其兄弟孩子作為右孩子。

• 哈夫曼編碼以及哈夫曼樹(shù)

  • 哈夫曼編碼是一種用于數(shù)據(jù)壓縮的算法，該編碼算法基于一種稱(chēng)為哈夫曼樹(shù)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)根據(jù)輸入文本中字符的出現(xiàn)頻率構(gòu)建一棵二叉樹(shù)，并將頻率較高的字符用較短的二進(jìn)制碼表示，頻率較低的字符用較長(zhǎng)的二進(jìn)制碼表示，以實(shí)現(xiàn)對(duì)數(shù)據(jù)的高效壓縮。

  • 哈夫曼編碼的主要步驟如下：

    • 統(tǒng)計(jì)輸入文本中每個(gè)字符的出現(xiàn)頻率。

    • 將每個(gè)字符及其頻率構(gòu)建為一個(gè)包含單節(jié)點(diǎn)的二叉樹(shù)。

    • 將這些二叉樹(shù)合并為一棵哈夫曼樹(shù)，合并過(guò)程中頻率較低的樹(shù)作為新樹(shù)的左子樹(shù)，頻率較高的樹(shù)作為右子樹(shù)。

    • 在哈夫曼樹(shù)的葉子節(jié)點(diǎn)上的每個(gè)字符都被賦予一個(gè)唯一的二進(jìn)制編碼，路徑的左分支表示0，右分支表示1。

    • 使用得到的編碼對(duì)輸入文本中的每個(gè)字符進(jìn)行替換，生成壓縮后的二進(jìn)制數(shù)據(jù)。

  • 由于哈夫曼編碼的構(gòu)建過(guò)程保證了沒(méi)有編碼是另一個(gè)編碼的前綴，所以在解碼時(shí)不會(huì)出現(xiàn)歧義。哈夫曼編碼在信息論和數(shù)據(jù)壓縮領(lǐng)域有廣泛應(yīng)用，例如在無(wú)損壓縮算法中，以及在通信領(lǐng)域中的數(shù)據(jù)傳輸和存儲(chǔ)中。

  • 哈夫曼樹(shù)的性質(zhì)：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-802987.html

    • 哈夫曼樹(shù)的所有葉子節(jié)點(diǎn)相加就是字符串長(zhǎng)度
    • 哈夫曼樹(shù)的所有非葉子節(jié)點(diǎn)相加就是字符串的哈夫曼編碼長(zhǎng)度

  • #include<iostream>
    #include<queue>
    #include<string>
    using namespace std;
    
    // 輸入一個(gè)字符串，分別用普通ASCII編碼（每個(gè)字符8bit）和哈夫曼編碼
    // 輸出編碼前后的長(zhǎng)度，并輸出壓縮比
    
    // 本題的核心問(wèn)題是求字符串的哈夫曼編碼長(zhǎng)度
    // 在哈弗曼樹(shù)中，所有非葉子節(jié)點(diǎn)相加即為字符串的哈夫曼編碼長(zhǎng)度
    // 題目沒(méi)有要求輸出哈夫曼編碼，因此不必真的構(gòu)造哈夫曼樹(shù)
    // 只需要一個(gè)變量，初始值為0，每次將兩個(gè)最小頻率的字符的頻率之和加到變量中
    // 直到所有字符都加完，最后的變量值就是字符串的哈夫曼編碼長(zhǎng)度
    
    // 計(jì)算字符串中每個(gè)字符的頻率
    // 將字符串存入字符數(shù)組中，對(duì)數(shù)組進(jìn)行排序
    // 從前往后讀字符，讀到相同的字符頻率加一，直到讀到不同的字符結(jié)束
    // 此時(shí)的頻率就是字符的頻率
    
    // 哈夫曼編碼長(zhǎng)度的計(jì)算
    // 構(gòu)造一個(gè)小頂堆優(yōu)先隊(duì)列（可以直接使用STL優(yōu)先隊(duì)列）
    // 每次計(jì)算完一個(gè)頻率就放入優(yōu)先隊(duì)列，直到處理完所有字符
    // 設(shè)定一個(gè)變量，初始值為0
    // 每次出隊(duì)兩個(gè)頻率，將這兩個(gè)頻率相加再放入隊(duì)列
    // 令變量等于頻率之和加上這個(gè)變量，直到優(yōu)先隊(duì)列為空
    // 此變量就是哈夫曼長(zhǎng)度
    
    int main() {
        priority_queue<int, vector<int>, greater<int>> q; // 小頂堆優(yōu)先隊(duì)列，用于構(gòu)建哈夫曼編碼
        string s;
        cin >> s;
        
        while (s != "END") {
            sort(s.begin(), s.end()); // 將字符串排序以便統(tǒng)計(jì)字符頻率
    
            int num = 1;
            // 統(tǒng)計(jì)字符頻率
            for (int i = 1; i <= s.size(); i++) {
                if (s[i] != s[i - 1]) {
                    q.push(num);
                    num = 1;
                } else {
                    num++;
                }
            }
    
            int ans = 0;
            // 計(jì)算哈夫曼編碼長(zhǎng)度
            while (q.size() != 1) {
                int a = q.top();
                q.pop();
                a = a + q.top();
                q.pop();
                q.push(a);
                ans += a;
            }
            q.pop();
    
            // 輸出編碼前后的長(zhǎng)度和壓縮比
            cout << "Original Length: " << s.size() * 8 << " bits, Huffman Length: " << ans
                 << " bits, Compression Ratio: " << (double)s.size() * 8 / (double)ans << endl;
    
            cin >> s; // 讀取下一個(gè)字符串
        }
    
        return 0;
    }
    
    

到了這里，關(guān)于算法競(jìng)賽：初級(jí)算法（第一章：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！