使用C++編寫高效的數據結構和算法

一、STL標準庫

STL（Standard Template Library）是C++的標準庫之一，它提供了許多數據結構和算法的實現。STL中的容器（Container）包括向量（vector）、鏈表（list）、隊列（queue）等，容器中的元素可以是任意類型的。STL也提供了一系列的算法（Algorithm），如排序（sort）、查找（find）等，使得我們能夠方便地進行大量操作。

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    int main() {
        std::vector v = {5, 3, 1, 4, 2};
        std::sort(v.begin(), v.end());
        for(int i=0; i<v.size(); i++) {
            std::cout << v[i] << " ";
        }
        return 0;
    }

以上代碼演示了如何使用vector容器和sort算法進行排序。這些容器和算法是經過嚴格測試和優化過的，在許多場景下都具有較高的效率和性能。

二、自定義數據結構

在某些情況下，我們需要自定義數據結構來應對特定問題。C++提供了多種方式來定義數據結構，其中最常用的是結構體（struct）。結構體允許我們將多個不同類型的變量打包成一個整體，方便地進行操作。

    #include <iostream>
    
    struct Student {
        std::string name;
        int age;
        double score;
    };
    
    int main() {
        Student s;
        s.name = "Tom";
        s.age = 18;
        s.score = 95.5;
        std::cout << s.name << " " << s.age << " " << s.score;
        return 0;
    }

以上代碼演示了如何定義一個學生結構體，並存儲學生的姓名、年齡和成績。結構體可以實現自定義數據類型的封裝，方便我們進行操作。

三、遞歸算法

遞歸算法是一種通過重複調用自身來解決問題的算法。在許多情況下，遞歸算法可以簡化問題的複雜度。遞歸算法有兩個重要概念：基本情況和遞歸情況。基本情況是指問題可以直接解決的情況，遞歸情況是指問題需要進一步分解的情況。

    #include <iostream>
    
    int factorial(int n) {
        if(n==0) return 1;
        else return n * factorial(n-1);
    }
    
    int main() {
        std::cout << factorial(5); // 輸出 120
        return 0;
    }

以上代碼演示了如何使用遞歸算法實現階乘。遞歸算法可以簡化問題，但需要注意避免死循環和堆棧溢出等問題。

四、動態規劃

動態規劃是一種解決複雜問題的算法，它利用了重複子問題和最優子結構的性質。動態規劃一般包括三個步驟：定義狀態、設計狀態轉移方程和確定初始狀態。定義狀態是指確定問題的狀態集合，設計狀態轉移方程是指找到問題之間的關係，確定初始狀態是指確定問題的初始狀態。

    #include <iostream>
    
    int fibonacci(int n) {
        int f0 = 0, f1 = 1, f2 = 1;
        if(n==0) return f0;
        if(n==1 || n==2) return f1;
        for(int i=3; i<=n; i++) {
            f0 = f1;
            f1 = f2;
            f2 = f0 + f1;
        }
        return f2;
    }
    
    int main() {
        std::cout << fibonacci(6); // 輸出 8
        return 0;
    }

以上代碼演示了如何使用動態規劃實現斐波那契數列。動態規劃是一種複雜但強大的算法，可以解決許多實際問題。