国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社

2年前作者：Mr_Dwj分類(lèi)：Toy博客閱讀(30)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

前言

博客起源：本博客記錄了個(gè)人學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)期間做的一些筆記，其中含有PPT的截圖或者個(gè)人的一些見(jiàn)解與思考，多有不足還望包含與指出，祝各位學(xué)習(xí)愉快

參考教材：《數(shù)據(jù)結(jié)構(gòu) C++語(yǔ)言描述》高等教育出版社

相關(guān)代碼：DataStructure

筆記范圍：全書(shū)

一、緒論

1.1 數(shù)據(jù)分析+結(jié)構(gòu)存儲(chǔ)+算法計(jì)算

1.1.1 邏輯結(jié)構(gòu)

對(duì)于當(dāng)前的數(shù)據(jù)之間的關(guān)系進(jìn)行分析，進(jìn)而思考應(yīng)該如何存儲(chǔ)

集合
線性結(jié)構(gòu)
樹(shù)形結(jié)構(gòu)
圖結(jié)構(gòu)

1.1.2 存儲(chǔ)結(jié)構(gòu)

設(shè)計(jì)一定的方法存儲(chǔ)到程序中

存儲(chǔ)內(nèi)容
- 數(shù)值存儲(chǔ)
- 數(shù)據(jù)與數(shù)據(jù)之間關(guān)系域的存儲(chǔ)
存儲(chǔ)方式
- 順序存儲(chǔ)
- 鏈?zhǔn)酱鎯?chǔ)
- 樹(shù)形存儲(chǔ)
- 圖存儲(chǔ)

1.1.3 算法實(shí)現(xiàn)

設(shè)計(jì)算法計(jì)算實(shí)現(xiàn)

1.2 數(shù)據(jù)類(lèi)型

約束：值集 + 運(yùn)算集

數(shù)據(jù)類(lèi)型 $Data\ Type$ （DT）：一般編程語(yǔ)言已經(jīng)實(shí)現(xiàn)好了

抽象數(shù)據(jù)類(lèi)型 $Abstract\ Data\ Type$ （ADT）：數(shù)據(jù)結(jié)構(gòu)+算法操作

1.3 算法方法

正確性
健壯性（魯棒性）：對(duì)于不合法、異常的輸入也有處理能力
可讀性
可擴(kuò)展性
高效率
1. 空間復(fù)雜度
2. 時(shí)間復(fù)雜度 $T (n) = O (f (n))$ ，其中有三種表示時(shí)間復(fù)雜度的公式
  - $O ()$ upper bound：最壞的時(shí)間復(fù)雜度
  - $\Omega()$ lower bound：最好的時(shí)間復(fù)雜度
  - $\Theta()$ average bound：平均時(shí)間復(fù)雜度

二、線性表

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

2.1 線性表的邏輯結(jié)構(gòu)

有一個(gè)頭結(jié)點(diǎn)，尾結(jié)點(diǎn)，且每一個(gè)結(jié)點(diǎn)只有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。

2.2 線性表的存儲(chǔ)結(jié)構(gòu)

2.2.1 順序存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)在一維地址連續(xù)的存儲(chǔ)單元里

特點(diǎn)：邏輯位置相鄰，物理位置也相鄰

數(shù)據(jù)結(jié)構(gòu)：一個(gè)一個(gè)一維數(shù)組 + 一個(gè)長(zhǎng)度變量 n

template<class T, int MaxSize>
class SeqList
{
    T data[MazSize];
    int length;
public:
    ...
}

順序表可以直接存儲(chǔ)元素與關(guān)系

鏈表的元素存儲(chǔ)也是可以直接實(shí)現(xiàn)的，但是關(guān)系要通過(guò)指針域來(lái)實(shí)現(xiàn)

2.2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

單鏈表：默認(rèn)有一個(gè)頭結(jié)點(diǎn)，不存儲(chǔ)數(shù)據(jù)
循環(huán)鏈表
雙向鏈表

2.3 線性表的操作算法

2.3.1 順序表的操作算法

順序表初始化構(gòu)造
求順序表長(zhǎng)度
按位查找
按值查找
遍歷順序表
插入
刪除

2.3.2 鏈表的操作算法

單鏈表初始化構(gòu)造

head = new Node<T>;
head->next = nullptr;

頭插法

head = new Node<T>;
head->next = nullptr;

尾插法
```
head = new Node<T>;
rear = head;
```

求單鏈表長(zhǎng)度
按位查找
按值查找
遍歷單鏈表
插入
刪除
單鏈表的析構(gòu)函數(shù)
其他操作

雙向鏈表操作

插入

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

// 插入當(dāng)前結(jié)點(diǎn) s
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

刪除

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

// 刪除當(dāng)前結(jié)點(diǎn) p
p->next->prior = p->prior;
p->prior->next = p->next;

三、棧和隊(duì)列

3.1 棧

3.1.1 棧的基本概念

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

卡特蘭數(shù)：假設(shè) $f (k)$ 表示第 k 個(gè)數(shù)最后一個(gè)出棧的總個(gè)數(shù)，則 $f (k) = f (k ? 1) f (n ? k)$
$\sum_{k=1}^{n} f(k-1) f(n-k)=\frac{1}{n+1} C_{2n}^{n}$

3.1.2 棧的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)
鏈?zhǔn)酱鎯?chǔ)

3.1.3 棧的操作算法

順序棧的操作
鏈棧的操作

3.1.4 棧的應(yīng)用

括號(hào)匹配
算數(shù)表達(dá)式求值
- 中綴表達(dá)式求值
  雙棧思路，算符優(yōu)先法
  - 遇到數(shù)字，直接入數(shù)棧
  - 遇到符號(hào)
    - 如果是括號(hào)，左括號(hào)直接入棧，右括號(hào)進(jìn)行運(yùn)算直到遇到左括號(hào)
    - 如果是算符，在入算符棧之前，需要進(jìn)行運(yùn)算操作直到算符棧頂元素等級(jí)小于當(dāng)前算符等級(jí)
- 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
  算符棧即可
  
  后綴先遇到就直接計(jì)算的運(yùn)算符 $\to$ 中綴表達(dá)式需要先算的運(yùn)算符，于是轉(zhuǎn)化思路就是：
  - 遇到數(shù)字，直接構(gòu)造后綴表達(dá)式
  - 遇到算符
    - 如果是括號(hào)，左括號(hào)直接入棧，右括號(hào)進(jìn)行后綴表達(dá)式構(gòu)造直到遇到左括號(hào)
    - 如果是算符，在入算符棧之前，需要進(jìn)行后綴表達(dá)式構(gòu)造操作直到算符棧頂元素等級(jí)小于當(dāng)前算符等級(jí)
- 后綴表達(dá)式求值
  
  數(shù)棧即可
  
  遇到數(shù)字直接入數(shù)棧，遇到算符直接進(jìn)行運(yùn)算
棧與遞歸

遞歸工作棧

3.2 隊(duì)列

3.2.1 隊(duì)列的基本概念

先進(jìn)先出

3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)
鏈?zhǔn)酱鎯?chǔ)

3.2.3 隊(duì)列的操作算法

循環(huán)隊(duì)列的操作
循環(huán)隊(duì)列的三個(gè)注意點(diǎn)
- 解決假溢出：采用循環(huán)隊(duì)列，即在入隊(duì)的時(shí)候不是單純的指針 +1，而是+1后 % MaxSize
- 解決隊(duì)空隊(duì)滿的沖突（真溢出）：
  1. 浪費(fèi)一個(gè)元素空間：測(cè)試rear+1是否等于head，
  2. 設(shè)置一個(gè)輔助標(biāo)志變量
  3. 設(shè)置一個(gè)計(jì)數(shù)器
1. 初始化：頭尾全部初始化為0
2. 入隊(duì)push
3. 出隊(duì)pop
4. 取隊(duì)頭front
5. 長(zhǎng)度size
6. 隊(duì)空empty
鏈隊(duì)列的操作

3.2.4 隊(duì)列的應(yīng)用

報(bào)數(shù)問(wèn)題：報(bào)到 0 的出隊(duì)，報(bào)到 1 的重新入隊(duì)，求解出隊(duì)順序
迷宮最短路問(wèn)題：開(kāi)一個(gè)記憶數(shù)組 $d [i] [j]$ 表示從起點(diǎn) $(0, 0)$ 到終點(diǎn) $(i, j)$ 點(diǎn)的最短路徑的長(zhǎng)度。可以將求最短路看做一個(gè)波心擴(kuò)散的物理場(chǎng)景，隊(duì)列中的每一個(gè)點(diǎn)都可以作為一個(gè)波心，從而實(shí)現(xiàn)“兩點(diǎn)之間線段最短”的物理場(chǎng)景
- 為什么用隊(duì)列：逐層搜索，每次搜素到的點(diǎn)就是當(dāng)前點(diǎn)可以搜索到的最短的點(diǎn)，先搜到的點(diǎn)先擴(kuò)展，于是就是隊(duì)列的數(shù)據(jù)結(jié)構(gòu)
- 為什么最短：對(duì)于每一個(gè)點(diǎn)探索到的點(diǎn)都是最短的點(diǎn)，最終的搜索出來(lái)的路徑就是最短的路徑

四、串

4.1 串的基本概念

由字符組成的串

子串（連續(xù)）
主串
位置

4.2 串的存儲(chǔ)結(jié)構(gòu)

4.2.1 串的順序存儲(chǔ)

使用固定長(zhǎng)度的數(shù)組來(lái)存儲(chǔ)，3種存儲(chǔ)字符串長(zhǎng)度的方法如下：

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

4.2.2 串的鏈?zhǔn)酱鎯?chǔ)

$\frac {串值所占的內(nèi)存}{一個(gè)結(jié)點(diǎn)的總內(nèi)存}$

非壓縮形式：一個(gè)結(jié)點(diǎn)存一個(gè)字符

// 存儲(chǔ)密度為：1/9 （64位操作系統(tǒng)）
struct String {
    char data;
    String* next;
};

壓縮形式（塊鏈）：一個(gè)結(jié)點(diǎn)存儲(chǔ)指定長(zhǎng)度的字符

// 存儲(chǔ)密度為：4/12 （64位操作系統(tǒng)）
const int MaxSize = 4;
struct String {
    char data[MaxSize];
    String* next;
}

4.3 串的操作算法

4.3.1 串的基本操作算法

串連接
串比較
串拷貝

4.3.2 串的模式匹配

BF算法（Brute - Force）

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

// 返回匹配上的所有位置下標(biāo)（下標(biāo)從0開(kāi)始）
vector<int> BF(string& s, string& t) {
	vector<int> res;
	int i = 0, j = 0, n = s.size(), m = t.size();
    
	while (i < n && j < m) {
		if (s[i] == t[j]) i++, j++;
		else i = i - j + 1, j = 0;
            
		if (j == m) {
			res.emplace_back(i - j);
			j = 0;
		}
	}

    return res;
}

KMP算法

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

優(yōu)化思想：

先看暴力思想，我們需要每次將模式串 t 后移一位重新進(jìn)行比較，其中浪費(fèi)了已匹配的串?dāng)?shù)據(jù)，優(yōu)化就是從這塊已匹配的串?dāng)?shù)據(jù)入手。而已匹配的串?dāng)?shù)據(jù)就是模式串本身的串?dāng)?shù)據(jù)，因?yàn)槲覀兛梢灾苯訌哪Ｊ酱旧砣胧帧?/p>
初步猜想：

根據(jù)模式串的性質(zhì)，構(gòu)造一個(gè)數(shù)表 next，存儲(chǔ)模式串應(yīng)該后移的指針數(shù) k

算法實(shí)現(xiàn)：

遞推求 next 數(shù)組

KMP 中 i 指針不回溯，j 回溯到 next[j]

// 求 next 數(shù)組	下標(biāo)從1開(kāi)始
for (int i = 2, j = 0; i <= m; i++) {
    while (j && t[i] != t[j + 1])
        // 未匹配上則不斷回溯
        j = ne[j];
    
    if (t[i] == t[j + 1])
        // 匹配上了則j指針后移一位
        j++;
    
    ne[i] = j;
}

// KMP 匹配		 下標(biāo)從1開(kāi)始
for (int i = 1, j = 0; i <= n; i++) {
    while (j && news[i] != newt[j + 1])
        // 未匹配上則不斷回溯
        j = ne[j];
    
    if (news[i] == newt[j + 1])
        // 匹配上了則j指針后移一位
        j++;

    if (j == m) {
        // 匹配完全，則統(tǒng)計(jì)并且回溯
        cnt++;
        j = ne[j];
    }
}

五、數(shù)組和特殊矩陣

5.1 數(shù)組

5.1.1 數(shù)組的基本概念

typedef int arr[m][n];
// 等價(jià)于
typedef int arr1[n];
typedef arr1 arr2[m];

5.1.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)

行優(yōu)先：按行存儲(chǔ)
列優(yōu)先：按列存儲(chǔ)

可以按照下標(biāo)的關(guān)系，只需要知道第一個(gè)元素的地址，通過(guò)矩陣的大小關(guān)系即可直接計(jì)算出 $a_{ij\cdots}$ 的地址

5.2 特殊矩陣的壓縮存儲(chǔ)

對(duì)于多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配空間

5.2.1 對(duì)稱矩陣的壓縮存儲(chǔ)

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

假設(shè)現(xiàn)在有一個(gè) n*n 的對(duì)稱矩陣

存：行優(yōu)先存儲(chǔ) data[n * (n + 1) / 2]

?。何覀?nèi)绻?data[i][j]

對(duì)于上三角
- i >= j：data[i * (i + 1) / 2 + j]
- i < j：data[j * (j + 1) / 2 + i]
對(duì)于下三角
- i >= j：data[i * (i + 1) / 2 + j]
- i < j：data[j * (j + 1) / 2 + i]

5.2.2 三角矩陣的壓縮存儲(chǔ)

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

假設(shè)現(xiàn)在有一個(gè) n*n 的三角矩陣（上三角或下三角為常數(shù)c）

存：行優(yōu)先存儲(chǔ)，常數(shù) c 存儲(chǔ)到最后 data[n * (n + 1) / 2 + 1]

5.2.3 對(duì)角矩陣的壓縮存儲(chǔ)

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

假設(shè)現(xiàn)在有一個(gè) n*n 的對(duì)角矩陣（圍繞主對(duì)角線有數(shù)據(jù)，其余數(shù)據(jù)均為0）

5.2.4 稀疏矩陣的壓縮存儲(chǔ)

假設(shè)現(xiàn)在有一個(gè) n*m 的稀疏矩陣（很多零的一個(gè)矩陣）

三元組順序表

按行存儲(chǔ)兩個(gè)信息，一個(gè)是非零元素的數(shù)值，還有一個(gè)是具體的坐標(biāo) (i, j)
十字鏈表

定義兩個(gè)指針數(shù)組，定義兩個(gè)指針數(shù)組，存儲(chǔ)行列的頭指針即可 vector<CrossNode<T>*> cheads, rheads

六、廣義表

6.1 廣義表的概念

與以往的線性表的區(qū)別在于：線性表的元素只能是DT或ADT。而對(duì)于廣義表，元素還可以是一個(gè)廣義表，即可遞歸結(jié)構(gòu)
表頭、表尾：對(duì)于當(dāng)前序列，第一個(gè)元素就是表頭，其余元素的集合就是表尾
特點(diǎn)：層次結(jié)構(gòu)、共享結(jié)構(gòu)、遞歸結(jié)構(gòu)

6.2 廣義表的存儲(chǔ)結(jié)構(gòu)

6.2.1 廣義表中結(jié)點(diǎn)的結(jié)構(gòu)

采用聯(lián)合結(jié)構(gòu)體存儲(chǔ)結(jié)點(diǎn)類(lèi)型

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

6.2.2 廣義表的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

6.3 廣義表的操作算法

直接遞歸法 - 原子直接操作，子表循環(huán)成原子進(jìn)行操作
減治法 - 先處理第一個(gè)元素（原子：直接操作 $or$ 子表：遞歸操作），最后遞歸操作剩余的元素

6.3.3 廣義表的其他操作算法

復(fù)制廣義表
計(jì)算廣義表的長(zhǎng)度
計(jì)算廣義表的深度 - 原子深度為0，空表深度為1
釋放廣義表的存儲(chǔ)空間

七、樹(shù)和二叉樹(shù)

7.1 樹(shù)的概念和性質(zhì)

7.1.1 樹(shù)的定義

7.1.2 樹(shù)的基本術(shù)語(yǔ)

結(jié)點(diǎn)的度和樹(shù)的度
- 結(jié)點(diǎn)的度：每一個(gè)結(jié)點(diǎn)孩子結(jié)點(diǎn)的數(shù)量
- 樹(shù)的度：一棵樹(shù)中結(jié)點(diǎn)度數(shù)的最大值
孩子、雙親、兄弟結(jié)點(diǎn)
路徑和路徑長(zhǎng)度
子孫結(jié)點(diǎn)和祖先結(jié)點(diǎn)
結(jié)點(diǎn)的層次和樹(shù)的高度
有序樹(shù)和無(wú)序樹(shù)
- 有序樹(shù)：子集不可以隨意交換
- 無(wú)序樹(shù)：子集可以隨意交換
森林
- 多棵樹(shù)

7.1.3 樹(shù)的基本性質(zhì)

7.2 二叉樹(shù)的概念和性質(zhì)

7.2.1 二叉樹(shù)的定義

7.2.2 二叉樹(shù)的基本性質(zhì)

根是第一層。第 $i$ 層最多有 $2^{i - 1}$ 個(gè)結(jié)點(diǎn)
樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)為 $n_0$ ，度數(shù)為2的結(jié)點(diǎn)的個(gè)數(shù)為 $n_2$ 。已知樹(shù)的點(diǎn)數(shù)為 $n$ ，邊數(shù)為 $m$ ，則 $n = m + 1$ 。而 $n=n_0+n_1+n_2$ ， $m=n_1+2n_2$ ，則 $n_0+n_1+n_2 = n_1+2n_2 +1$ ，則
$n_0=n_2 + 1$
滿二叉樹(shù)：每一層都是滿結(jié)點(diǎn)
完全二叉樹(shù)：對(duì)于一個(gè) $k$ 層的二叉樹(shù)， $1\to k-1$ 都是滿的，第 $k$ 層從左到右連接葉子結(jié)點(diǎn)

結(jié)點(diǎn)數(shù)固定，則完全二叉樹(shù)的形狀唯一

若 $i$ 為奇數(shù)，且 $i\neq1$ ，則左兄弟就是 $i ? 1$

若 $i$ 為偶數(shù)，則右兄弟就是 $i + 1$

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

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

對(duì)于一般的二叉樹(shù)，將其轉(zhuǎn)化為完全二叉樹(shù)進(jìn)行存儲(chǔ)即可
插入刪除操作都不方便

7.3.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

7.4 二叉樹(shù)的遍歷

7.4.1 二叉樹(shù)遍歷的概念

7.4.2 二叉樹(shù)遍歷算法

先中后遍歷
1. 遞歸遍歷
2. 棧式遍歷
層序遍歷

7.4.3 二叉樹(shù)的構(gòu)造和析構(gòu)??

由含空指針標(biāo)記的單個(gè)遍歷序列構(gòu)造二叉樹(shù)

可以從遍歷的邏輯進(jìn)行逆推。在遍歷到空指針的時(shí)候輸出一個(gè)編制符號(hào)，然后在構(gòu)造的時(shí)候按照遍歷序列進(jìn)行遞歸構(gòu)造即可，如圖

先序序列進(jìn)行構(gòu)造：
按照遍歷的思路來(lái)，對(duì)于先序序列而言，第一個(gè)元素一定是根元素，因此首先根據(jù)“當(dāng)前局面”的第一個(gè)元素創(chuàng)建根結(jié)點(diǎn)，接著遞歸創(chuàng)建左子樹(shù)和右子樹(shù)即可。注意傳遞的序列起始下標(biāo)是引用類(lèi)型的變量

中序序列進(jìn)行構(gòu)造：
不可以，因?yàn)椴荒艽_定根節(jié)點(diǎn)以及左子樹(shù)和右子樹(shù)的部分

后序序列進(jìn)行構(gòu)造：
與上述先序序列進(jìn)行構(gòu)建的邏輯一致，只不過(guò)有一個(gè)小 trick，即我們從后序序列的最后一個(gè)元素開(kāi)始創(chuàng)建，那么得到的第一個(gè)元素就是根結(jié)點(diǎn)的值，然后首先遞歸創(chuàng)建右子樹(shù)，再遞歸創(chuàng)建左子樹(shù)即可。同樣需要注意的是傳遞參數(shù)時(shí)，序列起始下標(biāo)是引用類(lèi)型的變量與先序序列構(gòu)造邏輯相同，只是遞歸的順序需要調(diào)整一下
由兩個(gè)遍歷序列構(gòu)造二叉樹(shù)
- 先+中：構(gòu)造邏輯與上述帶標(biāo)記的序列構(gòu)造邏輯幾乎一致，只不過(guò)區(qū)別在于如何進(jìn)行遞歸中參數(shù)的傳遞。傳遞的參數(shù)除了先序和中序的字符串，還有當(dāng)前局面先序序列的起始下標(biāo)與當(dāng)前局面中序序列的起始下標(biāo)，以及以當(dāng)前序列進(jìn)行構(gòu)造時(shí)子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)。很容易就可以找到當(dāng)前序列的根結(jié)點(diǎn)，接著就是利用很簡(jiǎn)單的下標(biāo)關(guān)系得到上述的三個(gè)參數(shù)的過(guò)程，最后將新得到的三個(gè)參數(shù)傳遞給遞歸函數(shù)進(jìn)行遞歸構(gòu)建左右子樹(shù)即可，當(dāng)前的根結(jié)點(diǎn)是 pre[ipre]
- 后+中：邏輯與上述一致，只不過(guò)當(dāng)前的根結(jié)點(diǎn)是 post[ipost+n-1]
由順序結(jié)構(gòu)構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)
拷貝構(gòu)造
析構(gòu)

7.5 二叉樹(shù)的其他操作算法

計(jì)算二叉樹(shù)的結(jié)點(diǎn)數(shù)
- 有返回值的遞歸
- 無(wú)返回值的遞歸
計(jì)算二叉樹(shù)的高度
- 有返回值的遞歸
- 無(wú)返回值的遞歸
根據(jù)關(guān)鍵值查找結(jié)點(diǎn)
查找結(jié)點(diǎn)的父結(jié)點(diǎn)

7.6 線索二叉樹(shù)??

7.6.1 線索二叉樹(shù)的概念

將空指針域用前驅(qū) or 后繼結(jié)點(diǎn)的地址進(jìn)行覆蓋

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

依舊是鏈?zhǔn)酱鎯?chǔ)，只不過(guò)增加了結(jié)點(diǎn)域中的指針類(lèi)型，分為鏈接類(lèi)型Link與線索類(lèi)型Thread

7.6.3 線索二叉樹(shù)的操作算法

中序線索化的二叉樹(shù)

線索化算法

設(shè)置一個(gè)全局變量 pre，為了簡(jiǎn)化思維，我們可以將一個(gè)中序遍歷的過(guò)程想象成一個(gè)線性結(jié)構(gòu)。前驅(qū)為pre，當(dāng)前為p。
- p的左子樹(shù)為空，則p的前驅(qū)為pre
- pre的右子樹(shù)為空，則pre的后繼為p
求后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的算法
遍歷算法
求父結(jié)點(diǎn)的算法
- 首先，若已知當(dāng)前是左子樹(shù)，則父結(jié)點(diǎn)一定是當(dāng)前右孩子的中序前驅(qū)線索；若已知當(dāng)前是右子樹(shù)，則父結(jié)點(diǎn)一定是當(dāng)前左孩子的中序前驅(qū)線索
- 但是在未知當(dāng)前結(jié)點(diǎn)的位置（未知左右子樹(shù)）時(shí)，同時(shí)搜索兩邊的父結(jié)點(diǎn)，然后根據(jù)試探出來(lái)的父結(jié)點(diǎn)，特判父結(jié)點(diǎn)的子結(jié)點(diǎn)是否是當(dāng)前結(jié)點(diǎn)即可

7.7 樹(shù)的存儲(chǔ)結(jié)構(gòu)與算法

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

多叉鏈表表示法

將每一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)都預(yù)設(shè)置為一個(gè)定值（樹(shù)的最大度數(shù)）：浪費(fèi)空間

孩子鏈表表示法

自頂向下存儲(chǔ)邊的信息

template<class T>
struct CTBox {
    T data;
    CTNode* firstchild;
};
struct CTNode {
    int child;
    CTNode* next;
};

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

雙親表示法

自下向上存儲(chǔ)邊的信息
孩子兄弟表示法

左結(jié)點(diǎn)存儲(chǔ)孩子，右結(jié)點(diǎn)存儲(chǔ)兄弟

7.7.2 樹(shù)的操作算法

構(gòu)造
計(jì)算樹(shù)的高度
計(jì)算樹(shù)中所有結(jié)點(diǎn)的度

7.8 哈夫曼樹(shù)與哈夫曼編碼??

7.8.1 哈夫曼樹(shù)的定義

樹(shù)的路徑長(zhǎng)度：葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑之和

樹(shù)的帶權(quán)路徑長(zhǎng)度 $W P L$ ：葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑之和 $\times$ 葉子結(jié)點(diǎn)的權(quán)重，整體之和
$W P L$ 最小的樹(shù)就叫做哈夫曼樹(shù)：對(duì)于一個(gè)結(jié)點(diǎn)序列 n，每次選擇其中的兩個(gè)權(quán)值最小的兩個(gè)結(jié)點(diǎn)進(jìn)行合并，在進(jìn)行了 n-1 次以后，得到的二叉樹(shù)就是哈夫曼樹(shù)
哈夫曼編碼：
- 編碼：利用二叉樹(shù)進(jìn)行前綴編碼 - 避免解碼時(shí)的二義性
- 解碼：根據(jù)編碼的二叉 trie 樹(shù)，進(jìn)行解碼

7.8.2 操作算法

構(gòu)造 Huffman 樹(shù)
編碼
解碼

八、圖

8.1 圖的基本概念

8.1.1 圖的定義

$G r a p h = (V, E)$

完全無(wú)向圖： $e d g e = n (n ? 1) /2$

完全有向圖： $e d g e = n (n ? 1)$

8.1.2 圖的基本術(shù)語(yǔ)

帶權(quán)圖稱為網(wǎng)
連通圖和連通分量：
- 無(wú)向圖
- 連通圖：每一個(gè)頂點(diǎn)之間都有路徑可達(dá)
- 連通分量：極大連通子圖
強(qiáng)連通圖和強(qiáng)連通分量：
- 有向圖
- 強(qiáng)連通圖：每一個(gè)頂點(diǎn)之間都有路徑可達(dá)
- 強(qiáng)連通分量：極大強(qiáng)連通子圖

8.2 圖的存儲(chǔ)結(jié)構(gòu)

教材中的點(diǎn)編號(hào)統(tǒng)一從 $0$ 開(kāi)始

8.2.1 鄰接矩陣

無(wú)向圖的度：第 $i$ 行（列）的非標(biāo)記數(shù)的個(gè)數(shù)
有向圖的度：
- 入度：第 $i$ 行的非標(biāo)記數(shù)的個(gè)數(shù)
- 出度：第 $i$ 列的非標(biāo)記數(shù)的個(gè)數(shù)
類(lèi)定義：

8.2.2 鄰接表

存儲(chǔ)出邊表（鄰接表）
存儲(chǔ)入編表（逆鄰接表）
類(lèi)定義：

8.3 圖的遍歷

8.3.1 圖遍歷的概念

每個(gè)結(jié)點(diǎn)只能訪問(wèn)一次，故需要開(kāi)啟標(biāo)記數(shù)組用來(lái)記錄是否訪問(wèn)的情況

8.3.2 深度優(yōu)先搜索

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

鄰接矩陣：
- 時(shí)間復(fù)雜度： $O(n^2)$
- 針對(duì)鄰接矩陣的一個(gè)無(wú)向連通圖的搜索代碼示例
鄰接表：
- 時(shí)間復(fù)雜度： $O (n + e)$
- 針對(duì)鄰接表的一個(gè)無(wú)向連通圖的搜索代碼示例
```
template<class T>
void ALGraph::DFS(int v, bool* visited) {
    cout << vexs[v];
    visited[v] = true;
    // 遍歷所有的邊
}
```

8.3.3 廣度優(yōu)先搜索

通過(guò)隊(duì)列實(shí)現(xiàn)
時(shí)間復(fù)雜度與上述 DFS 算法類(lèi)似

8.3.4 圖遍歷算法的應(yīng)用

求 (u,v) 的所有簡(jiǎn)單路徑

dfs+回溯法的簡(jiǎn)單應(yīng)用
染色法求二部圖

bfs的簡(jiǎn)單應(yīng)用

當(dāng)然dfs也是可以的，只需要在染色之后判斷是否有相同顏色的鄰接點(diǎn)即可

8.4 最小生成樹(shù)

8.4.1 最小生成樹(shù)的概念及其性質(zhì)

$Minimum\ Spanning\ Tree(MST)$

證明：

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

對(duì)于上述的一個(gè)割，選擇其中權(quán)值最小的交叉邊。從而對(duì)于所有的狀態(tài)，每次選擇最小交叉邊即可。

8.4.2 Prim算法

算法標(biāo)簽： $g ree d y$

構(gòu)造 $n ? 1$ 個(gè)割的狀態(tài)
起始狀態(tài)為：頂點(diǎn)集合 $U$ 含 $1$ 個(gè)頂點(diǎn)，頂點(diǎn)集合 $V ? U$ 含 $n ? 1$ 個(gè)頂點(diǎn)
狀態(tài)轉(zhuǎn)移為：
- 選完最小交叉邊之后，將這條邊在集合 $V ? U$ 中的頂點(diǎn)加入到最小生成樹(shù)集合 $U$ 中
- 更新最小交叉邊數(shù)組 $miniedges[\ ]$
時(shí)間復(fù)雜度： $O(n^2)$

8.4.3 Kruskal算法

算法流標(biāo)簽： $g ree d y 、 d s u$

初始化 $n$ 個(gè)頂點(diǎn)作為 $n$ 個(gè)連通分量
按照邊的權(quán)值升序進(jìn)行選擇
- 如果選出的邊的兩個(gè)頂點(diǎn)不在同一個(gè)集合，則加入最小生成樹(shù)
- 如果選出的邊的兩個(gè)頂點(diǎn)在同一個(gè)集合，則不選擇（如果選了就會(huì)使得生成樹(shù)形成回路）
時(shí)間復(fù)雜度： $O(e\log e)$

8.5 最短路徑

8.5.1 最短路徑的概念

單源最短路

$D ijk s t r a$ 算法無(wú)法求解含負(fù)邊權(quán)的單源最短路

$B e ll man ? F or d$ 算法支持負(fù)邊權(quán)的單源最短路求解

$Sp f a$ 算法同樣支持負(fù)邊權(quán)的單元最短路，屬于 $B e ll man ? F or d$ 算法的優(yōu)化

多源最短路

$Fl oy d$ 適用于求解含負(fù)邊權(quán)的多源最短路

8.5.2 單源最短路徑 - $D ijk s t r a$ 算法

算法標(biāo)簽： $g ree d y$ $d p$

其實(shí)就是 $P r im$ 的另一種應(yīng)用

$P r im$ 是只存儲(chǔ)交叉邊的最小值

$D ijk s t r a$ 是存儲(chǔ)交叉邊的最小值 $+$ 這條邊在集合 S 中的點(diǎn)已經(jīng)記錄的值

樸素版：
- 鄰接矩陣
- 定義 $d [i]$ 表示從起點(diǎn)到當(dāng)前i號(hào)點(diǎn)的最短路徑的長(zhǎng)度
- 將頂點(diǎn)分為兩個(gè)集合， $S$ 和 $V ? S$ ，其中 $S$ 表示已經(jīng)更新了最短路徑長(zhǎng)度的頂點(diǎn)集合
- 迭代更新過(guò)程：依次更新每一個(gè)結(jié)點(diǎn)，對(duì)于當(dāng)前結(jié)點(diǎn) $v_i$ ，在集合 $S$ 中的所有結(jié)點(diǎn)中，選擇其中到當(dāng)前結(jié)點(diǎn)路徑最短的頂點(diǎn) $v_j$ ，則 d[i]=d[j]+edges[j][i]
- 時(shí)間復(fù)雜度： $O(n^2)$
堆優(yōu)化：
- 鄰接表
- 時(shí)間復(fù)雜度： $\log e)$

8.5.3 多源最短路徑 - $Fl oy d$ 算法

算法標(biāo)簽： $d p$

多階段決策共 $n$ 個(gè)階段，dp[i][j] 表示每一個(gè)階段 $k$ ，從 $i$ 到 $j$ 的選擇前 $k$ 個(gè)頂點(diǎn)后的最短路徑的長(zhǎng)度

對(duì)于當(dāng)前階段 $k$ ，我們利用階段 $k ? 1$ 的狀態(tài)進(jìn)行轉(zhuǎn)移更新，其實(shí)就是對(duì)于新增加的頂點(diǎn) $v_k$ 是否選擇的過(guò)程

選擇 $v_k$ ，則 dp[i][j] = dp[i][k] + dp[k][j]
不選 $v_k$ ，則 dp[i][j] 就是 $k ? 1$ 狀態(tài)下的 dp[i][j]

8.6 AOV網(wǎng)與拓?fù)渑判?/h4>

8.6.1 有向無(wú)環(huán)圖與AOV網(wǎng)的概念

有向無(wú)環(huán)圖： $D A G$
AOV網(wǎng)： $(activity\ on\ vertex\ network)$
應(yīng)用場(chǎng)景：在時(shí)間先后上有約束關(guān)系的工程管理問(wèn)題

8.6.2 拓?fù)渑判?/h5>

定義：頂點(diǎn)線性化

應(yīng)用：判環(huán)、判斷一個(gè)圖是否可以進(jìn)行動(dòng)態(tài)規(guī)劃

算法設(shè)計(jì)：對(duì)于有向圖，從所有的入度為 0 的點(diǎn)開(kāi)始刪點(diǎn)刪邊，到最后判斷有多少點(diǎn)被刪除即可

算法實(shí)現(xiàn)：可以采用 dfs 進(jìn)行縮點(diǎn)刪邊，也可以采用 bfs 進(jìn)行縮點(diǎn)刪邊

時(shí)間復(fù)雜度： $O (n + e)$

九、查找

9.1 靜態(tài)查找表

定義：只支持查詢和修改，不支持刪除與插入

9.1.1 順序查找

9.1.2 折半查找

9.1.3 分塊查找

結(jié)合順序查找與分塊查找的一種方法

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

索引表可以折半或者順序查找
塊內(nèi)部只能順序查找

9.2 動(dòng)態(tài)查找表

9.2.1 二叉排序樹(shù)

定義：根結(jié)點(diǎn)比左子樹(shù)所有結(jié)點(diǎn)的值都大，比右子樹(shù)所有結(jié)點(diǎn)的值都小。關(guān)鍵字唯一

操作：查找、插入、刪除

判定：想要判定一棵二叉樹(shù)是否為二叉排序樹(shù)，只需要判斷中序遍歷的結(jié)果是不是遞增的即可，可以采取中序遍歷序列比對(duì)的方法，也可以在遞歸遍歷二叉樹(shù)的過(guò)程中通過(guò)記錄前驅(qū)結(jié)點(diǎn)的值直接進(jìn)行比較判斷。時(shí)間復(fù)雜度： $O (n)$

9.2.2 平衡二叉樹(shù)

定義：平衡因子為左子樹(shù)的高度 - 右子樹(shù)的高度，平衡二叉樹(shù)的平衡因子絕對(duì)值 <= 1

構(gòu)建：當(dāng)插入結(jié)點(diǎn)進(jìn)行構(gòu)建時(shí)出現(xiàn)了有結(jié)點(diǎn)平衡因子的絕對(duì)值超過(guò)了1，則進(jìn)行“旋轉(zhuǎn)”調(diào)整，旋轉(zhuǎn)共分為4種

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

嘗試模擬一遍下列序列的構(gòu)造過(guò)程就可以理解了數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社,GPA,數(shù)據(jù)結(jié)構(gòu),c++

9.3 Hash 查找

定義：裝填因子 $\alpha=\frac{n}{m}$ ，其中 $n$ 表示待填入表中的結(jié)點(diǎn)數(shù)， $m$ 表示哈希表的空間大小

哈希函數(shù)應(yīng)該滿足以下兩點(diǎn)：第一、映射出來(lái)的地址不會(huì)越界；第二、映射出來(lái)的地址是唯一的

9.3.1 構(gòu)造表

常用的哈希函數(shù)

直接地址法 - 線性函數(shù)一對(duì)一映射

優(yōu)點(diǎn)。計(jì)算簡(jiǎn)單且不可能產(chǎn)生沖突

缺點(diǎn)。對(duì)于空間的要求極高，如果數(shù)據(jù)過(guò)于離散，則會(huì)造成很大的空間浪費(fèi)
數(shù)字分析法 - 按照數(shù)位中的數(shù)值分布情況進(jìn)行哈希

缺點(diǎn)。需要預(yù)先知道數(shù)據(jù)的數(shù)字分布情況
平方取中法 - 對(duì)于 $10^m$ 的哈?？臻g，可以將數(shù)字平方后取中間 $m$ 位進(jìn)行哈希存儲(chǔ)
折疊法
- 移位法：將一個(gè)數(shù)字按照數(shù)位拆分為幾個(gè)部分，然后將幾個(gè)部分的數(shù)值累加出一個(gè)數(shù)即可，高位抹去不用
- 間隔法：與移位法幾乎一致，只不過(guò)將其中的部分意義間隔的進(jìn)行數(shù)值反轉(zhuǎn)，最后累計(jì)即可，高位抹去不用
除留余數(shù)法 - 按照數(shù)值 $\text{mod}\ p$ 后的數(shù)值進(jìn)行哈希，假設(shè)哈希表空間大小為 $m$ ，則 $p$ 一般取 $\le m$ 的質(zhì)數(shù)

處理沖突

開(kāi)放定址法 - 探測(cè)開(kāi)放地址，一般有三種
- 連續(xù)序列進(jìn)行線性探測(cè)
- 左右倍增序列進(jìn)行探測(cè)
- 偽隨機(jī)序列進(jìn)行探測(cè)
- 雙 hash 探測(cè)法
拉鏈法
- 定義：將產(chǎn)生 hash 沖突的元素放入同一個(gè)子集，通過(guò)單鏈表進(jìn)行存儲(chǔ)
- 優(yōu)點(diǎn)：沒(méi)有堆積現(xiàn)象，從而減少了很多不必要的比價(jià)，提升比較效率；適合一開(kāi)始不知道表長(zhǎng)的情況；除結(jié)點(diǎn)更加容易。

9.3.2 查找表

按照構(gòu)造相同的邏輯進(jìn)行查找即可

十、排序

10.1 排序的基本概念

關(guān)鍵字：

主關(guān)鍵字：每一個(gè)待排序的該關(guān)鍵字是獨(dú)一無(wú)二的
次關(guān)鍵字：每一個(gè)待排序的該關(guān)鍵字可能是重復(fù)的

穩(wěn)定性：

場(chǎng)景：只針對(duì)次關(guān)鍵字的情況
穩(wěn)定：按照次關(guān)鍵字排序后，原來(lái)相同關(guān)鍵字的順序不變
不穩(wěn)定：按照次關(guān)鍵字排序后，原來(lái)相同關(guān)鍵字的順序可能會(huì)改變

內(nèi)外排序：

內(nèi)排序：數(shù)據(jù)全部存放在內(nèi)存
外排序：數(shù)據(jù)量過(guò)大時(shí)，待排序的數(shù)據(jù)在內(nèi)存與外存之間不斷轉(zhuǎn)換

10.2 冒泡排序

基于交換的思路進(jìn)行

穩(wěn)定的文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-803486.html

10.3 選擇排序

選擇第 1 小的數(shù)放在第一個(gè)位置，…，選擇第 i 小的數(shù)放在第 i 個(gè)位置
共選擇 n-1 次

10.4 插入排序

直接插入排序：依次向前綴已經(jīng)排好序的序列中進(jìn)行插入 - $O(n^2)$
折半插入排序：同上，只是選擇插入位置的使用二分 - $O(n\log n)$
遞歸插入排序：排序 [1,i] 等價(jià)于先排好 [1,i-1]，然后插入當(dāng)前 num[i] 即可

穩(wěn)定的

10.5 希爾排序

基于插入直接排序的優(yōu)點(diǎn)：

當(dāng)序列基本有序時(shí)，效率很高
當(dāng)待排序數(shù)很少時(shí)，效率很高

于是希爾（Shell）就得出來(lái)以下的希爾排序算法：

將序列劃分一定次數(shù)，從 d<n 到 1
每次劃分都對(duì)組內(nèi)的元素進(jìn)行直接插入排序
最后分為 1 組時(shí)，直接排序一趟以后就可以得到 sortrd sequence

不穩(wěn)定

10.6 快速排序

分治法三步驟：divide、conquer and combine

每次選擇一個(gè) pivot 進(jìn)行 partition，遞歸兩個(gè) partition

void Sort(int l, int r) {
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);            
    }
    
    Sort(l, j), Sort(j + 1, r);
}

不穩(wěn)定

10.7 堆排序

堆與堆排序的定義

首先我們得知道什么是堆結(jié)構(gòu)。堆是具有下面性質(zhì)（對(duì)于任意的 $1\le i \le n/2$ ）的完全二叉樹(shù)

$k_i \le k_{2i}、k_i \le k_{2i+1}$ 叫做小頂堆

$k_i \ge k_{2i}、k_i \ge k_{2i+1}$ 叫做大頂堆

因此一個(gè)堆結(jié)構(gòu)可以采用線性的單元進(jìn)行存儲(chǔ)與維護(hù)

而堆排序利用堆頂是最值這一性質(zhì)，通過(guò)不斷的取堆頂，調(diào)整堆的方式獲得最終的排好序的序列

建立初始堆

由于完全二叉樹(shù)中，每一個(gè)葉子結(jié)點(diǎn)都已經(jīng)是堆結(jié)構(gòu)，因此直接從第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始建堆即可。對(duì)每一個(gè)元素與左孩子、右孩子進(jìn)行比較

如果當(dāng)前結(jié)點(diǎn)的值比左右孩子都大，那么無(wú)需修改，當(dāng)前位置就是堆頂

如果當(dāng)前結(jié)點(diǎn)的值比左孩子或者右孩子中的最大值小，則將最大的孩子作為堆頂，并將當(dāng)前值不斷的“下沉”即可

交換堆頂與記錄位置后重新建堆

交換記錄值獲取當(dāng)前堆中最值以后，需要將除了已記錄的值的結(jié)點(diǎn)以外的所有結(jié)點(diǎn)重新調(diào)整為堆結(jié)構(gòu)

調(diào)整為堆結(jié)構(gòu)的過(guò)程與上述初始建堆的過(guò)程完全一致，只是結(jié)點(diǎn)數(shù)每次 -1

時(shí)間復(fù)雜度 $\log n)$

不穩(wěn)定

10.8 歸并排序

遞歸

同樣采用分治法，我們按照分治法的三個(gè)步驟進(jìn)行討論

divide: 將當(dāng)前序列劃分為左右兩部分

conquer: 遞歸處理上述劃分出來(lái)的兩部分

combine: 歸并上述遞歸完的兩部分

時(shí)間復(fù)雜度 $\log n)\leftarrow T(n)=2T(\frac{n}{2}) + O(n)$

非遞歸

就是模擬上述遞歸的過(guò)程，可以拆分為三步

歸并

按照指定的長(zhǎng)度處理整個(gè)序列

劃分局部排序的長(zhǎng)度

穩(wěn)定的

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)_C++語(yǔ)言描述_高教出版社的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C++語(yǔ)言描述》-列車(chē)車(chē)廂重排問(wèn)題
完整可編譯運(yùn)行代碼見(jiàn)：Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列貨運(yùn)列車(chē)有 n 節(jié)車(chē)廂，每節(jié)車(chē)廂要?？吭诓煌能?chē)站。假設(shè) n個(gè)車(chē)站從 1 到n 編號(hào)，而且貨運(yùn)列車(chē)按照從n到1的順序經(jīng)過(guò)車(chē)站。車(chē)廂的編號(hào)與它們要停靠的車(chē)站編號(hào)相同。為了便于從
2024年04月10日
瀏覽(30)
數(shù)據(jù)結(jié)構(gòu)——用C語(yǔ)言描述（第2版）耿國(guó)華課后習(xí)題答案
? 如有錯(cuò)誤，敬請(qǐng)諒解！此文章僅為本人學(xué)習(xí)筆記，僅供參考，如有冒犯，請(qǐng)聯(lián)系作者刪除！！目錄第一章習(xí)題答案第二章習(xí)題答案第三章習(xí)題答案第五章習(xí)題答案第六章習(xí)題答案第七章習(xí)題答案第八章查找第九章排序 2 、 ××√ 3 、（ 1 ）包含改變量定義的最小范圍
2024年02月08日
瀏覽(22)
數(shù)據(jù)結(jié)構(gòu)：定長(zhǎng)順序串（SString）基本操作的算法描述（C語(yǔ)言）
作者在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，發(fā)現(xiàn)鮮有完全按照 C 語(yǔ)言描述的算法操作，這讓習(xí)慣于寫(xiě) .c 而不是 .cpp 的初學(xué)者很是頭疼。本文將基于 C 語(yǔ)言描述算法操作，如有錯(cuò)漏還望大佬們指正。本文將按照嚴(yán)惠敏所著《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》所做的函數(shù)原型聲明進(jìn)行算法描述，由于C語(yǔ)言不支
2024年02月07日
瀏覽(34)
數(shù)據(jù)結(jié)構(gòu)（期末復(fù)習(xí)篇）清華大學(xué)出版社
1.1.1 數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)：描述客觀事物的數(shù)和字符的集合數(shù)據(jù)元素：數(shù)據(jù)的基本單位數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系，可以看作互相之間有著特定關(guān)系的集合 1.1.2 邏輯結(jié)構(gòu) 1.邏輯結(jié)構(gòu)的表示一?
2024年01月20日
瀏覽(20)
Java面試、進(jìn)階、實(shí)踐一網(wǎng)打盡（由電子工業(yè)出版社出版）
準(zhǔn)備好應(yīng)對(duì)Java開(kāi)發(fā)的新挑戰(zhàn)嗎？我們?yōu)槟x了五本核心書(shū)籍，一站式滿足您在Java面試準(zhǔn)備、技能進(jìn)階和實(shí)戰(zhàn)應(yīng)用的需求。這套書(shū)籍包括《Offer來(lái)了：Java面試核心知識(shí)點(diǎn)精講（第2版）》、《Java面試八股文：高頻面試題與求職攻略一本通》、《Spring Boot編程思想（核心卷）》
2024年02月04日
瀏覽(90)
數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——圖應(yīng)用實(shí)例-拯救007（問(wèn)題描述、解題思路、偽代碼解讀、C語(yǔ)言算法實(shí)現(xiàn)）
目錄問(wèn)題描述? 解題思路偽代碼? 總體算法 DFS算法偽代碼解讀總體算法 DFS算法具體實(shí)現(xiàn)（C語(yǔ)言）在老電影“007之生死關(guān)頭”（Live and Let Die）中有一個(gè)情節(jié)，007被毒販抓到一個(gè)鱷魚(yú)池中心的小島上，他用了一種極為大膽的方法逃脫 —— 直接踩著池子里一系列鱷魚(yú)的大腦
2024年02月05日
瀏覽(82)
數(shù)據(jù)結(jié)構(gòu)與算法細(xì)節(jié)篇之最短路徑問(wèn)題：Dijkstra和Floyd算法詳細(xì)描述，java語(yǔ)言實(shí)現(xiàn)。
最短路徑的算法有兩個(gè)， Dijkstra算法和 Floyd算法。 Dijkstra算法解決的是單源最短路徑問(wèn)題。 Floyd算法解決的是多源最短路徑問(wèn)題，并且可以處理負(fù)權(quán)圖。今天要講的就是Dijkstra算法。加： feng--Insist (大寫(xiě)的i)，進(jìn)java交流群討論互聯(lián)網(wǎng)+技術(shù)?？伤饕狿PT等資料。其他資料
2024年02月11日
瀏覽(94)
數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)記錄——樹(shù)習(xí)題—Tree Traversals Again（題目描述、輸入輸出示例、解題思路、解題方法C語(yǔ)言、解析）
目錄題目描述輸入示例輸出示例解題思路? 解題方法（C語(yǔ)言）解析有序的二叉樹(shù)遍歷可以用堆棧以非遞歸的方式實(shí)現(xiàn)。例如：假設(shè)遍歷一個(gè)節(jié)點(diǎn)數(shù)為6的二叉樹(shù)（節(jié)點(diǎn)數(shù)據(jù)分別為1到6）時(shí)，堆棧操作為：push（1）；push（2）；push（3）；pop（）；pop（）；push（4）；pop（）
2024年02月07日
瀏覽(33)
鯨落送書(shū)第一期清華出版社系列叢書(shū)
1.《Rust項(xiàng)目開(kāi)發(fā)實(shí)戰(zhàn)》《Rust項(xiàng)目開(kāi)發(fā)實(shí)戰(zhàn)》詳細(xì)闡述了與Rust語(yǔ)言開(kāi)發(fā)相關(guān)的基本解決方案，主要包括Rust語(yǔ)言簡(jiǎn)介、存儲(chǔ)和檢索數(shù)據(jù)、創(chuàng)建REST Web服務(wù)、創(chuàng)建完整的服務(wù)器端Web應(yīng)用程序、利用Yew創(chuàng)建客戶端WebAssembly應(yīng)用程序、利用quicksilver創(chuàng)建WebAssembly游戲、利用ggez創(chuàng)建2D桌面
2024年02月09日
瀏覽(25)
SciencePub學(xué)術(shù) | Elsevier出版社SCIE&EI征稿中
SciencePub學(xué)術(shù)刊源推薦:Elsevier出版社SCIEEI征稿中！信息如下，錄滿為止：一、期刊概況：計(jì)算機(jī)科學(xué)類(lèi)SCI-01 【期刊簡(jiǎn)介】 6.5-7.0，JCR1區(qū)，中科院2區(qū)；【檢索情況】正刊，SCIE在檢；【征稿領(lǐng)域】有關(guān)數(shù)據(jù)處理、人工智能的相關(guān)文章，包括但不限于數(shù)據(jù)表示、存儲(chǔ)和處理、
2024年02月10日
瀏覽(26)

<b id="npnam"><menuitem id="npnam"></menuitem></b>

<code id="npnam"><menuitem id="npnam"></menuitem></code>