數(shù)據(jù)結(jié)構(gòu)與算法
    算法
        排序
            插入排序
                直接插入排序/簡單插入排序
                希爾排序
            交換排序
                冒泡排序/簡單交換排序
                快速排序
            選擇排序
                簡單選擇排序
            歸并排序
            基數(shù)排序
            桶排序
            堆排序(STL)
        其他
            遞歸
            分治策略
            動(dòng)態(tài)規(guī)劃
            回溯法
            貪心算法
        概念
            解決特定問題的步驟
                菜譜
                    數(shù)據(jù)結(jié)構(gòu)是菜，算法就是菜譜宵蛀。
        特征
            輸入
            輸出
            有窮性
                在可接受時(shí)間內(nèi)執(zhí)行完成
            確定性
            可行性
        設(shè)計(jì)要求
            正確性
            可讀性
            健壯性
            高效率
            低存儲(chǔ)
        度量方法
            事后統(tǒng)計(jì)方法
                這種方法主要是通過設(shè)計(jì)好的測試程序和數(shù)據(jù)逆巍，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低死相。
            事前統(tǒng)計(jì)方法
                在計(jì)算機(jī)程序編寫前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算咬像。
        算法復(fù)雜度分析
            時(shí)間復(fù)雜度
                本質(zhì)
                    把基本操作的數(shù)量和輸入規(guī)模關(guān)聯(lián)
                    隨著輸入規(guī)模擴(kuò)大的增長量
                計(jì)算步驟
                    找出基本語句(執(zhí)行次數(shù)最多的語句)
                        最內(nèi)層循環(huán)的循環(huán)體
                    計(jì)算基本語句的執(zhí)行次數(shù)的數(shù)量級(jí)
                        只保留最高次冪算撮，忽略低次冪和最高次冪的系數(shù)
                    用大O記號(hào)表示算法的時(shí)間性能
                        P(多項(xiàng)式)
                            O(1)
                                常數(shù)
                            O(logn)
                                對(duì)數(shù)
                            O(n)
                                線性
                            O(nlogn)
                                線性對(duì)數(shù)
                            O(n^2)
                                平方
                            O(n^3)
                                立方
                        NP(非確定多項(xiàng)式)
                            O(2^n)
                                指數(shù)
                            O(n!)
                                階乘
                            O(n^n)
                語句分類
                    順序語句
                        簡單輸入輸出
                            O(1)
                        賦值語句/計(jì)算
                            O(1)
                    分支語句
                    循環(huán)語句
                        for
                            O(n^2)
                            O(n^3)
                            ...
                        while
                            O(logn)
                    遞歸
                            O(2^n)
                            O(n!)
                            O(n^n)
                定義
                    在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)县昂，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)肮柜。
                表示
                    T(n)= O(f(n))
            空間復(fù)雜度
    數(shù)據(jù)結(jié)構(gòu)
        邏輯結(jié)構(gòu)
            集合
                無關(guān)系
                    班級(jí)座次
            線性結(jié)構(gòu)
                一對(duì)一
                    糖葫蘆
            樹形結(jié)構(gòu)
                一對(duì)多
                    族譜
            圖狀結(jié)構(gòu)
                多對(duì)多
                    鐵路路線圖
        物理/存儲(chǔ)結(jié)構(gòu)
            構(gòu)成
                數(shù)據(jù)元素
                    數(shù)據(jù)/數(shù)據(jù)對(duì)象/節(jié)點(diǎn)node
                        數(shù)據(jù)項(xiàng)
                關(guān)系
                    順序存儲(chǔ)結(jié)構(gòu)(相對(duì)位置)
                        特點(diǎn)：結(jié)點(diǎn)之間的邏輯關(guān)系通過相鄰表達(dá)(通常使用數(shù)組實(shí)現(xiàn))
                        優(yōu)點(diǎn):
                            1. 不需要額外的內(nèi)存存儲(chǔ)節(jié)點(diǎn)之間的邏輯關(guān)系。
                            2. 隨機(jī)訪問倒彰。
                        缺點(diǎn)：
                            1. 連續(xù)的存儲(chǔ)空間,內(nèi)存空間的利用率低审洞。
                            2. 插入/刪除需要移動(dòng)大量的元素，效率低待讳。
                        舉例：高鐵
                    鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(指示元素存儲(chǔ)位置的指針)
                        特點(diǎn)：結(jié)點(diǎn)之間的邏輯關(guān)系通過指針表達(dá)(通常使用指針實(shí)現(xiàn))
                        優(yōu)點(diǎn):
                            1. 不采用連續(xù)的存儲(chǔ)空間,內(nèi)存空間利用率高芒澜。
                            2. 插入/刪除效率高
                        缺點(diǎn)：
                            1. 需要額外的內(nèi)存存儲(chǔ)節(jié)點(diǎn)之間的邏輯關(guān)系。
                            2. 不能隨機(jī)訪問
                        舉例：火車
                    索引存儲(chǔ)結(jié)構(gòu)(索引表標(biāo)識(shí)節(jié)點(diǎn)的地址)
                        特點(diǎn)：不僅要存儲(chǔ)數(shù)據(jù)信息還要存儲(chǔ)索引表(通常使用數(shù)組+指針實(shí)現(xiàn))
                        舉例：書籍目錄
                    哈希/散列存儲(chǔ)結(jié)構(gòu)(根據(jù)節(jié)點(diǎn)關(guān)鍵字直接計(jì)算節(jié)點(diǎn)的存儲(chǔ)地址)
                        特點(diǎn)：通過映射計(jì)算確定存儲(chǔ)位置创淡，無需存儲(chǔ)邏輯關(guān)系(通常使用數(shù)組+指針實(shí)現(xiàn))
                        哈希函數(shù)：返回輸入數(shù)值與哈希表元素?cái)?shù)取余的值
        分類
            線性表/列表(List)
                概念
                    零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列
                例子
                    火車
                    月份
                    生肖
                    天干地支
                    通信錄
                分類
                    順序表(`std::vector`)
                    單鏈表(`slist`)
                    靜態(tài)單鏈表
                    單循環(huán)鏈表
                    雙鏈表(`std::list`)
                    雙循環(huán)列表
                實(shí)例
                    多項(xiàng)式運(yùn)算
                    大數(shù)運(yùn)算
            棧
                概念
                    只能在表尾進(jìn)行插入和刪除操作的線性表
                分類
                    順序棧
                    鏈棧("std::stack")
                實(shí)例
                    數(shù)制轉(zhuǎn)換
                    括弧匹配檢測
                    行編輯程序
                    迷宮求解
                    表達(dá)式求解
                    漢諾塔求解
            隊(duì)列
                概念
                    只能在一端進(jìn)行插入操作痴晦，在另一端進(jìn)行刪除操作的線性表
                分類
                    順序隊(duì)列
                    鏈隊(duì)列(`std::queue`)
                    循環(huán)隊(duì)列
                案例
                    離散事件模擬
            串/字符串
                概念
                    零個(gè)或多個(gè)字符組成的有限序列
                分類
                    順序串
                    堆串
                相關(guān)算法
                    串的模式匹配算法
                案例
                    單詞索引表
            數(shù)組/廣義表
            樹
                概念
                    有窮n個(gè)節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。
                分類
                    二叉樹
                    線索二叉樹
                    森林
                    孩子兄弟樹
                案例
                    哈夫曼編解碼
            圖
                概念
                    由有窮非空集合的頂點(diǎn)和頂點(diǎn)之間的邊組成琳彩。
                分類
                    鄰接矩陣
                    鄰接表
                    最小樹
                相關(guān)算法
                    關(guān)鍵路徑
                    最小路徑
            高級(jí)數(shù)據(jù)結(jié)構(gòu)
                紅黑樹RB(std::set,std::map)
                平衡樹B/B+/B-
                鍵樹T
                2-3-4樹
                倒排表
                跳表
        ADT
            抽象數(shù)據(jù)類型(相對(duì)與基本數(shù)據(jù)類型)
                指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作
                    數(shù)學(xué)模型(成員變量)+操作(成員函數(shù))