當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

数据结构教程(c语言)(已完结)

發布時間：2023/12/18 编程问答 36 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构教程(c语言)(已完结) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

一、基本概念和術語

數據： 是客觀事物的符號表示，能夠輸入到計算機中并能被計算機程序處理的符號的總稱
數據元素： 是數據的基本單位，用于完整地描述一個對象
數據對象： 是性質相同的數據元素的集合，是數據的一個子集
數據項： 是組成數據元素的，有獨立含義的，不可分割的最小單位
數據結構： 是相互之間存在的一種或者多種的特定關系的數據元素的集合，換句話說，數據結構是帶結構的數據元素的集合，“結構”，就是指數據元素之間的關系。數據結構包括，邏輯結構和存儲結構兩個層次。

邏輯結構： 兩個要素：數據元素和關系
四種基本邏輯結構：集合結構，線性結構，樹結構，圖結構

非線性結構：樹，二叉樹，有向圖，無向圖線性結構：線性表（線性表，棧與隊列，字符串，數組，廣義表）

具體如下圖：

存儲結構： 數據對象在計算機中的存儲表示成為數據的存儲結構，也稱為物理結構

順序存儲結構：順序存儲是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系通常借助程序設計語言的數組來表示。鏈式存儲結構：順序存儲結構要求所有元素依次存放在一片連續的存儲空間內鏈式存儲結構，則不需要占據一整塊存儲空間只需要給每個節點附加指針，用于存放后繼元素的存儲地址通常借助于程序設計語言的指針來表示。

二、算法和算法分析

算法：是為了解決某類問題而規定的一個有限長的操作序列

算法具有的五個特性：
有窮性： 有限步驟，有限時間
確定性： 不產生二義性
可行性： 基本操作運算執行有限次來實現
輸入： 有零個或者多個輸入
輸出： 有一個或者多個輸出
評價算法優劣的基本準則：
正確性，可讀性（易于理解，相互交流），健壯性（能對非法輸出做出良好的回應），高效性（時間復雜度，空間復雜在度來衡量）

接下來介紹時間復雜度和空間復雜度：先來說明兩個概念：

問題規模： 算法求解問題輸入量的多少，是問題大小的本質表示
語句頻度： 一條語句重復執行的次數

時間復雜度：(重要)

先來看個簡單的例子

//求兩個n階矩陣的乘積算法 for(i=1;i<=n;i++){ //頻度為 n+1for(j=1;j<=n;j++){ //頻度為 n*(n+1)c[i][j]=0; //頻度為 n^2for(k=1;k<=n;k++){ //頻度為 n^2*(n+1)c[i][j] = c[i][j]+a[i][k]*b[k][j]; //頻度為 n^3}} }

該算法中的所有語句頻度之和，是矩陣階數n的函數
用 $f (n)$ 表述： $f(n)=2n^3+3n^2+2n+1$
為了方便，我們這樣來理解，至少我就是這樣來理解的，忽略低階，忽略系數，在數學中，當n無窮大時， $f(n)=n^3$ ，3次方對該方程的影響最大。

所以一般情況下:算法中的基本語句的，重復執行的次數，是問題規模n的某個函數 $f (n)$ ，算法的時間度量記為： $T (n) = O (f (n))$ ，他表示問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，成為算法的漸進時間復雜度，簡稱為時間復雜度。
上述例子的時間復雜度為：O( $n^3$ )

加深理解，我們再來看兩個例子：

{x++;s=0}//時間復雜度為O(1)

實際上如果算大執行時間不隨問題規模n的增加而增長，算法中的語句頻度就是個常數，即使這個常數再大，算法的時間復雜度都是 $O (1)$

再來看一個例子：

for(i=0;i<10000;i++){x++;s=0; } //時間復雜度仍然為O(1)

再來一個例子(對數階)：

for(i=1;i<=n;i=i*2){x++;s=0; }

設循環體內兩條基本語句的頻度為f(n),
那么就有 $2f(n)≤n2^{f(n)}\leq n$ $f(n)≤log2nf(n)\leq log_2 n$ 時間復雜度： $T(n)=O(log_2 n)$

i=1; while(i<=n)i=i*3;

同設： $3f(n)≤n3^{f(n)}\leq n$
時間復雜度： $O(log_3 n)$
常見的時間復雜度按數量級遞增排列依次為：
$常量階 O (1) ，$ $對數階O(log_2n)，$ $線性階 O (n) ，$ $線性對數階O(n log_2 n)，$ $平方階O(n^2)，$ $立方階O(n^3)，$ $k次方階O(n^k)，$ $指數階O(2^n)$

最好時間復雜度：算法計算量可能達到的最小值
最壞時間復雜度：算法計算量可能達到的最大值
平均時間復雜度：算法在所有可能下，按輸入實例以等概率出現，算法計算量的加權平均值

說明：一般情況人們只關心最壞情況下的時間復雜度，一般的時間復雜度，指的就是最壞時間復雜度

接下來舉個例子說明

for(i=0;i<n;i++){if(a[i]==e) return i+1; return 0; }

上述例子語句頻度不止與n有關，還與輸入實例中的數組a[i]的各元素值以及e的取值有關， 假定數組中存在與e相同的值，且要查找的值就在a[0]位置，這樣的情況最好，為 $O (1)$ ，最壞的情況下為 $O (n)$

空間復雜度

關于算法存儲空間需求，類似于算法的時間復雜度，我們采用漸進空間復雜度作為算法所需存儲空間的度量民間稱空間復雜度，它也是問題規模n的函數，記作： $S (n) = O (f (n))$

一般情況下，一個程序在機器上執行時，除了需要本身所用的指令，常數，輸入數據外，還需要一些對數據進行操作的輔助存儲空間，其中對于輸入數據所占的具體存儲量取決于問題本身，與算法無關，這樣，只需要分析該算法在實現時所需要的輔助空間就可以了

下面看兩個例子：
均實現數組逆序
算法一

for(i=0;i<n/2;i++){t=a[i];a[i]=a[n-i-1];a[n-i-1]=t; }

算法二

for(i=0;i<n;i++){b[i]=a[n-i-1]; } for(i=0;i<n;i++){a[i]=b[i]; }

算法一僅需要借助一個變量t，與問題規模n大小無關，空間復雜度為:O(1)
算法二需要借助另外一個大小為n的輔助數組b，空間復雜度為：O(n)

總結：對于一個算法，其時間復雜度和空間復雜度往往是相互影響的，當追求一個較好的時間復雜度時，可能會導致占用較多的存儲空間，即可能會使空間復雜度的性能變差，反之亦然。不過通常情況下鑒于運算空間較為充足，人們都以算法的空間復雜度作為算法的衡量指標

三、線性表

基本特點：除第一個元素無直接前驅，最后一個元素無直接后繼以外，其他每個基本元素都有一個前驅和后繼
線性表是最基本最常用的一種線性結構，也是其他數據結構的基礎，尤其單鏈表
定義：由 $n (n \geq 0)$ 個數據特性相同的元素構成的有限序列稱為線性表
空表： 線性表中元素的個數n定義為線性表的長度，n=0時為空表
順序表： 線性表的順序表示指的時用一組地址連續的存儲單元依次存儲線性表的數據元素，這種表示頁稱作表的順序存儲結構（隨機存取）或順序映像。
順序表特性：邏輯上相鄰的數據元素，其物理地址次序也是相鄰的

線性表的兩種實現(java)
	順序表	鏈表
空間性能	順序表的存儲空間是靜態分布的，需要一個固定的數組，總有部分數組元素要浪費	鏈表的存儲空間是動態分布，因此不會有空間被浪費。但由于鏈表需要額外的空間來為每個節點保存指針，因此也要犧牲一部分空間
時間性能	順序表中的元素的邏輯順序和物理存儲順序保持一致，而且支持隨機存取。因此順序表在查找，讀取時候效率很快	鏈表采用鏈式結構來保存表內的元素，因此在插入、刪除的時候效率比較高
1. 線性表本質上是一個充當容器的工具類，當程序有一組結構相同的數據元素需要保存的時候，就可以考慮使用線性表來保存。 2. Java中經常使用的線性表是list，Java中list接口就是代表線性表，線性表中常見的兩種實現分別是ArrayList和LinkedList，其中LinkedList是一個雙向鏈表，而ArrayList是動態數組來實現。 3. ArrayList實現原理是數組，有點在于遍歷查找速度很快，但是對于插入和刪除效率不高。 4. LinkedList的實現就是鏈表遍歷和查找速度不高，但是插入和刪除的效率很高。

至于具體的線性表操作算法，此處不再贅述！實在想知道，百度一下~

接下來，我們要關注的是線性鏈表（單鏈表）

線性鏈表的存儲結構特點： 用一組任意的存儲單元存儲線性表的數據（存儲單元可連續，也可不連續）

所以，數據元素 $a_i$ ，與其直接后繼元素的 $a_{i+1}$ 的邏輯關系。對于 $a_1$ 來說，處理本身的存儲信息外，還需要一個指示其直接后繼的信息（即直接后繼的存儲位置），這兩部分組成了 $a_i$ 的存儲映像，即結點，它包括兩個域：數據域（存儲數據信息），指針域（存儲直接后繼的位置信息），指針域中存儲的信息稱為：指針或者鏈

以上兩張圖，比較全面的表示出了單鏈表的特點！

一般情況下，為了方便處理，我們還會再單鏈表的第一個節點之前附設一個節點，稱為頭結點，作用有如下兩點：1. 便于首元結點的處理 2 .便于空表和非空表的統一處理

下面對三個容易混淆的概念加以說明：

首元結點： 指鏈表中存儲第一個數據元素 $a_1$ 的結點，例如圖2.8中的結點“ZHAO”
頭結點： 在首元結點之前的一個結點，其指針域只想首元結點，頭節點的數據域可以不存儲任何信息
頭指針： 指向鏈表中的第一個結點的指針。若鏈表設有頭結點，則頭指針所指結點為線性表的頭結點；若鏈表沒有設頭節點，則頭指針所指結點為該線性表的首元結點

同上，單鏈表的操作算法，不在贅述

接下里，介紹循環鏈表和雙向鏈表

循環列表：是一種形式的鏈式存儲結構，其特點是，表中的最后結點的指針域指向頭結點，整個鏈表形成一個環。

雙向鏈表： 顧名思義，在雙向鏈表中有兩個指針域，一個指向直接后繼，另一個指向直接前驅

接下來是總結，為了方便，直接貼圖！

一個公式：

$存儲密度=數據元素本身所占的存儲量結點結構占用的存儲量存儲密度=\frac{數據元素本身所占的存儲量}{結點結構占用的存儲量}$

四、棧和隊列

棧和隊列的定義和特點

棧：是限定僅在表尾進行插入或者刪除的線性表，所以，對于棧來說，表尾端有特殊含義，稱為棧頂，表頭稱為棧底，其最大的特點就是后進先出

個人覺得，火車的例子很好理解~

隊列：是僅允許在表的一端插入，一端刪除，前者那一端稱為隊尾，后者那一端稱為隊頭，實際生活中，排隊時最好的例子，其最大的特點是先進先出
棧的表示和操作實現

棧的類型定義，順序棧和鏈棧，初始化，增刪改查！
棧和遞歸

遞歸： 若是在一個函數、過程或者數據結構定義的內部又直接（或間接）出現定義本身的應用，則稱它們是遞歸

例如：

階乘的定義：
$若 n = 0 ，則$ $F a c t (n) = 1$ $若 n > 0 ，則$ $F a c t (n) = n ? F a c t (n ? 1)$
Hanoi問題：
- 問題描述：假設有3個分別命名為A、B、C的塔座，在塔座A上插有n個直徑大小各不同，一小到大標號為1，2，…，n的圓盤，要求將塔座A上的n個圓盤移動到C盤上，并且仍按原來的順序疊排。
  
  同時遵循下列規則：
  - 每次只能移動一個圓盤
  - 圓盤可以插在A、B、C中的任一塔座上
  - 任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上
  算法如下：
  void Hanoi(int n,char A,char B,char C){//將塔座A上的n個圓盤按規則搬到C上，B做輔助塔if(n==1) move(A,1,C); //將編號為1的圓盤從A移動到Celse{Hanoi(n-1,A,C,B); //將編號為1至n-1的圓盤移動到B,C做輔助塔move(A,n,C); //將編號為n的圓盤從A移動到CHanoi(n-1,B,A,C); //將B上編號為1至n-1的圓盤移動到C，A做輔助塔} }
  個人理解：當有3個圓盤時，怎么移動大家應該都很清楚，那么當有多個圓盤時，把最底層的兩個圓盤除外，上面的所有圓盤當作整體，然后在研究這個 “整體”，如果數量還很多，可以繼續使用整體思想。
而上述算法，則是一直遞歸到n=1為止，然后在把遞歸，一層層“翻”出來！

遞歸算法優缺點：
- 優點：程序結構清晰，形式簡潔但遞歸程序在執行時需要系統提供隱式的工作棧來保存調用過程中的參數、局部變量和返回地址
- 缺點：占用內存空間多，運行效率較低

與此類似的還有八皇后問題，迷宮問題等。。

隊列的表示和操作實現

隊列也有兩種存儲表示：順序存儲，鏈式存儲
其操作實現和順序棧類似，具體算法，具體分析，此處不再贅述

五、串，數組，廣義表

串：

定義：是由零個或者多個字符組成的有限序列，或者稱為字符串。
特點：串是一種特殊的線性表，特殊性體現在，其處理的數據元素是一個字符。串中的字符數目n稱為串的長度，0個字符的串稱為空串
子串：串中任意個連續的字符組成的子序列稱為該串的子串，包含子串的串稱為主串
位置： 通常，稱字符在序列中的序號為該字符在串中的位置，子串在主串中的位置則以子串的第一個子都在主串中的位置來表示

下面舉例說明:

a = "BEI" b = "JING" c = "BEIJING" d = "BEI JING"他們的長度長度分別為：3，4，7，8 a和b都是c和d的子串 a在c和d中的位置都是1 b在c中的位置是4，在d中的位置則是5

相等的串: 當且僅當這兩個串的值相等，也就是說，兩個串的長度，并且對應位置的字符都相等時才相等。
空格串： 由一個或者多個空格組成的串“ ”，注意：此處并不是空串。

串的存儲結構： 順序存儲，鏈式存儲，但考慮到存儲效率和算法的方便性，串多采用順序結構

順序存儲：

//--------串的定長順序存儲結構------------ #define MAXLEN 225 //串的最大長度 typedef struct{char ch[MAXLEN+1]; //存儲串的一維數組int length; //串的當前長度 }//----------串的堆式存儲結構----------- type struct{char *ch; //若是非空串，則按串長分配存儲區，否則ch為空int length； //串的當前長度 }

鏈式存儲：

//順序串的插入和刪除不方便，需要移動大量元素，因此采用單鏈表方式存儲串 #define CHUNKSIZE 80 //由用戶定義塊大小 typedef struct{char ch[CHUNKSIZE];struct Chunk *next; }Chunk; typedef struct{Chunk *head,*tail; //串的頭和尾指針int length； //串的當前長度 }LString；

貼一張圖加深理解：

下面介紹兩個著名的模式匹配算法： 應用于：搜索引擎，拼寫檢查，語言翻譯，數據壓縮等
1.BF算法
此算法是最簡單直觀的模式匹配算法

int Index_BF(SString S,SString T,int pos){//返回模式T在主串S中第pos個字符開始第一次出現的位置，若是不存在，則返回0//其中，T為非空，1<=pos<=S.lengthi=pos;j=1; //初始化while(i<=S.length && j<=T.length){//兩個串均為比較到串尾if(S.ch[i] == T.ch[j]){//繼續比較后繼字符++i;++j;}else{//指針后退重新開始i=i-j+2;j=1;}if(j>T.length) return i-T.length;//匹配成功else return 0;//匹配失敗} }

下圖為子模式： $T = “ a b c a c ”$ 和主串S匹配過程：

2.KMP算法
此算法是BF算法的改進版

int index_KMP(SString S,SString T,int pos){//利用模式串T的next函數求T在主串S中的第pos個字符之后的位置//其中，T非空，1<=pos<=S.lengthi = pos;j=1; //初始化while(i<=S.length && j<=T.length){//兩個串均為比較到串尾if(j==0 || S.ch[i] == T.ch[j]){//繼續比較后繼字符++i;++j;}else{//模式串向右移動j=next[j];}if(j>T.length) return i-T.length;//匹配成功else return 0;//匹配失敗 }

KMP算法是在已知模式串的next函數值的基礎上進行的。
下面兩張圖說明函數 $n e x t ()$ :

以上可以看出， $n e x t ()$ 的函數值，取決于模式串本身。下面介紹求 $n e x t ()$ 函數值的算法

void get_next(SString T,int next[]){//求模式串T的next值，并存放到數組next中i=1;next[1]=0;j=0;while(i<T.length){if(j==0 || T.ch[i]==T.ch[j]){++i;++j;next[i]=j;}else j=next[j];} }

數組：

定義： 數組是由類型相同的元素構成的有序集合，每個元素稱為數組元素
特點： 結構中的元素本身可以是具有某種結構的數據，但屬于統一數據類型
數組的順序存儲：
由于數組一般不做插入或刪除操作，所以一般采用順序存儲。
對于二維數組來說，有兩種存儲方式
- 以行序為主的存儲
  假設每個數據元素占L個存儲單元，則二維數組 $A [0 . . . m ? 1, 0 . . . n ? 1]$ (即下標從0開始，共有m行n列)中任意元素aij的存儲單元位置可由下式確定： $L O C (i, j) = L O C (0, 0) + (n ? i + j) L$
  式中， $L O C (i, j)$ 是 $a_{ij}$ 的存儲位置； $L O C (0, 0)$ 是 $a_{00}$ 的存儲位置，即二維數組A的起始位置，也稱為基地址或者基址

推廣到n維數組： $LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑i=1ncijiLOC(j_1,j_2,...,j_n)=LOC(0,0,...,0)+\sum_{i=1}^nc_ij_i$ $其中，C_n=L，C_{i-1}=b_ic_i,1<i≤n$

以列序為主的存儲：
同理有以下公式可確定位置： $L O C (i, j) = L O C (0, 0) + (m ? i + j) L$

特殊矩陣的壓縮存儲：

對稱矩陣
三角矩陣
對角矩陣

以上，自行了解，不再贅述

廣義表：
定義：顧名思義廣義表就是線性表的推廣，也稱為列表，一般記作： $LS=(a_1,a_2,...,a_n)$ $其中， L S 是廣義表的名字， n 是其長度$ $a i 既可以是單個元素，也可以是廣義表，分別稱為廣義表 L S 的原子和子表$

舉例如下：

A=() ——A是一個空表，其長度為0
B=(e) ——B只有一個原子e，其長度為1
C=(a,(b,c,d)) ——C的長度為2，兩個元素分別為原子a和子表（b,c,d）
D=(A,B,C) ——D的長度為3，3個元素都是廣義表，可以將值帶入
E=(a,E) ——E的長度為2，這是一個遞歸表，E相當于一個無限廣義表E=(a,(a,(a,…)))

由上述例子得出三個結論

廣義表的元素可以是子表，而子表的元素還可以是子表，由此，廣義表是一個多層次結構
廣義表可以為其他廣義表所共享，由D可以看出
廣義表可以是一個遞歸的表

廣義表的運算

取表頭
取表尾

注意：廣義表()和(())不同，前者為空表，長度為0，后者長度為1，可分解得到其表頭，表尾均為空表()

廣義表的存儲結構
通常情況，采用鏈式存儲結構，分為兩種：

頭尾鏈表的存儲結構
擴展線性鏈表的存儲結構

以上兩種結構，自行了解，此處不再贅述

六、樹和二叉樹

樹和二叉樹的定義：
樹：是 $n （ n \geq 0 ）$ 個結點的有限集，它或為空樹（n=0），或為非空樹，對于非空樹T：
- 有且僅有一個稱之為根的結點；
- 出根節點以外的其余結點可分為 $m （ m > 0 ）$ 個互不相交的有限集 $T_1,T_2,...,T_m$ ，其中每一個集合本身又是一棵樹，并且稱為根的子樹

樹的一般表示：

樹的其他表示：

嵌套集合形式：
廣義表形式：
凹入表示法(類似書的編目)：

樹的基本術語：
- 結點： 樹中的一個獨立單元，包含一個數據元素及若干指向子樹的分支，如圖5.1(b)中的A,B,C,D等（下面術語，均以圖5.1（b）為例）
- 結點的度： 結點擁有的子樹數稱為結點的度，例如，A的度為3，C的度為1，F的度為0
- 樹的度： 樹的度是樹內各結點度的最大值，5.1（b）所示的樹的度為3
- 葉子： 度為0的結點稱為葉子或者終端結點。結點K,L,F,G,M,I.J都是樹的葉子
- 非終端結點： 度不為0的結點稱為非終端結點或者分支結點，除根結點，非終端結點也稱為內部結點
- 雙親和孩子： 結點的子樹的根稱為該結點的孩子，相應的該結點稱為孩子的雙親，例如：B的雙親為A，B的孩子由E和F
- 兄弟： 同一個雙清的孩子之間互稱為兄弟，例如H,I,J互為兄弟
- 祖先： 從根到該結點所經分支上的所有結點，例如：M的祖先為A，D，H
- 子孫： 以某結點為根的子樹中的任一結點都稱為該結點的子孫，如B的子孫為E，K，L，F
- 層次： 結點的層次從根結點定義起，根為第一層，根的孩子為第二層，樹中任一結點的層次等于其雙親層次加1
- 堂兄弟： 雙親在同一層的結點互為堂兄弟。例如：結點G與E，F，H，J，I為堂兄弟
- 樹的深度： 樹中的結點的最大層次稱為樹的深度或高度，例子中的深度為4
- 有序樹和無序樹： 如果將樹中結點的各子樹看成從左至右是有次序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個孩子，最右邊的稱為最后一個孩子
- 森林： 是 $m （ m \geq 0 ）$ 棵互不相交的樹的集合，對于樹中每個結點而言，其子樹的集合即為森林
二叉樹：
- 定義： 是 $n （ n \geq 0 ）$ 個結點所構成的集合，它或為空樹或為非空樹，對于非空樹T：
  - 有且僅有一個稱之為根的結點；
- 除根結點以外的其余結點分為兩個互不相交的子集 $T_1，T_2$ ，分別稱為T的左子樹和右子樹，且 $T_1，T_2$ 本身又都是二叉樹
- 二叉樹與樹的區別
  - 二叉樹每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點）
- 二叉樹的子樹有左右之分，其次順序不能任意顛倒
- 二叉樹的性質和存儲結構：
  
  性質：
  - 性質1： 在二叉樹的第i層上至多有 $2^{i-1}$ 個結點（i≥1），至少有1個
  - 性質2： 深度為k的二叉樹至多有 $2^{k-1}$ 個結點（k≥1），至少有k個
  - 性質3： 對任一棵二叉樹T，如果其終端結點數為n，度為2的結點數為m，則n=m+1
接下來，先介紹滿二叉樹和完全二叉樹
滿二叉樹： 深度為k且含有 $2^{k-1}$ 個結點的二叉樹
特點：
- 每一層上的結點數都是最大結點數
- 對滿二叉樹的結點進行連續編號，約定編號從根結點開始，自上而下，自左向右，由此得出完全二叉樹的概念
完全二叉樹： 深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中的編號從1至n的結點一一對應時，稱為完全二叉樹

特點：
- 葉子結點只可能是在層次最大的兩層出現；
- 對于任一結點，若其右分支下的子孫的最大層次為 i，則其左分支下的子孫的最大層次必為 i 或者 i+1
性質：
- 性質4： 假設深度為k，則根據性質2和完全二叉樹的定義有 $2^{k-1}-1<n≤2^{k-1}或者2^{k-1}≤n＜2^k$ 于是 $k?1≤log2n＜k，因為k是整數，所以k=?log2n?+1k-1≤log_2n＜k，因為k是整數，所以k=\lfloor{log_2n}\rfloor +1$
- 性質5： 如果對一棵樹有n個結點的完全二叉樹（其深度為 $?log2n?+1\lfloor{log_2n}\rfloor +1$ ）的結點按層序編號（從第一層到第 $?log2n?+1\lfloor{log_2n}\rfloor +1$ 層，每層從左到右），則對任一結點 $i(1≤i≤n)i(1\leq i\leq n)$ ，則有：
  - (1)如果i=1，則結點i是二叉樹的根，無雙親，如果i>1，則其雙親PARENT(i)是接待你 $?i/2?\lfloor i/2 \rfloor$
  - (2)如果2i>n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子LCHILD(i)是結點2i
  - (3)如果2i+1>n，則幾點i無右孩子；否則其右孩子RCHILD(i)是結點2i+1
符號說明：
- $?x?\lfloor x\rfloor$ 表示不大于 $x$ 的最大整數
- $?x?\lceil x\rceil$ 表示不小于 $x$ 的最小整數
存儲結構：
順序存儲結構
適用于完全二叉樹，按層序存儲，一般的二叉樹會造成空間的浪費
鏈式存儲結構
類似于線性表，設置數據域，左右指針域
遍歷二叉樹：
- 遍歷二叉樹： 是指按某條搜索路徑巡訪樹中的每個結點，使得每個接待你均被訪問一次，而且僅被訪問一次
  - 約定：L,D,R分別代表遍歷左子樹，訪問根結點，遍歷右子樹
  - 訪問方法：一般有三種方式：前序遍歷（DLR），中序遍歷（LDR），后序遍歷（LRD），這是在不分左右的情況下，如果分左右，可得到另外三種訪問方式
  - 結論：得知前序遍歷和中序遍歷或者中序遍歷和后序遍歷，可以畫出該二叉樹，前序遍歷和后續遍歷不能確定唯一的一棵二叉樹
  下面舉個例子：
  先來看看幾個特性：
  - 特性A，對于前序遍歷，第一個肯定是根節點；
  - 特性B，對于后序遍歷，最后一個肯定是根節點；
  - 特性C，利用前序或后序遍歷，確定根節點，在中序遍歷中，根節點的兩邊就可以分出左子樹和右子樹；
  - 特性D，對左子樹和右子樹分別做前面3點的分析和拆分，相當于做遞歸，我們就可以重建出完整的二叉樹；
  題目：前序遍歷的順序是: CABGHEDF，中序遍歷的順序是: GBHACDEF，畫出這棵二叉樹，找到其后序遍歷
  解:
哈夫曼樹：
- 定義：哈夫曼樹又稱最優樹，是一類帶權路徑長度最短的樹
接下來介紹一些基本概念：
- 路徑： 從樹的一各結點到另一個結點之間的分支構成兩個結點之間的路徑
- 路徑長度： 路徑上的分支數目稱作路徑長度
- 樹的路徑長度： 從樹根到每一個接待你的路徑長度之和
- 權：賦予某個實體一個量，是對實體的某個或某些屬性的數值化描述，在數據結構中實體有結點（元素）和邊（關系）兩大類，所以對應有結點權和邊權。結點權或邊權具體代表什么意義，由實際情況決定，如果在一棵樹中的結點上帶有權值，則對應的就帶有權樹等概念
- 結點的帶權路徑長度： 從該結點到樹根之間的路徑長度與結點上權的乘積
- 樹的帶權路徑長度： 樹中所有葉子結點的帶權路徑長度之和，通常記作: $∑k=1nwklk\sum_{k=1}^nw_kl_k$
- 哈夫曼樹：假設有m個權值 ${w_1,w_2,...,w_m\}$ ，可以構造一棵含有n個葉子結點的二叉樹，每個葉子結點的權為 $w_i$ ，其中帶權路徑長度WPL最小的二叉樹稱作最優二叉樹或哈夫曼樹
  
  上圖（c）即為哈夫曼樹

那么如何構造一棵哈夫曼樹呢？
哈夫曼樹構造過程：

根據給定的n個權值 ${w_1,w_2,...,w_n\}$ ，構造n棵只有根結點的二叉樹，這n棵二叉樹構成一個森林F。
在森林F中選取兩棵根結點權值最小的樹最為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和
在森林F中刪除這兩棵樹，同時將新的到的二叉樹加入F中
重復第二步，第三步，直到F中含有一棵樹為止，這棵樹便是哈夫曼樹

七、圖

圖定義和基本術語：
定義：圖G由兩個集合V和E組成，記作 $G = (V, E)$ ，其中V是頂點的有窮非空集合，E是V中的頂點偶對的有窮集合，這些頂點偶對稱為邊。 $V (G)$ 和 $E (G)$ 通常分別表示圖G的頂點集合和邊集合， $E (G)$ 可以為空集。若 $E (G)$ 為空，則圖G只有頂點而沒有邊。

對于圖G，若邊集 $E (G)$ 為有向邊的集合，則該圖為有向圖；反之，則該圖為無向圖。
在有向圖中頂點對用尖括號表示，例如： $< x, y >$ 是有序的
在無向圖中用圓括號表示，例如： $(x, y)$ 是無序的。

用n表示圖中的頂點數目，用e表示邊的數目，來說明一些基本術語：
- 子圖： 假設有兩個圖 $G = (V, E)$ 和 $G^{'} = (V^{'}, E^{'})$ ，如果 $V′∈VV'\in V$ 且 $E′∈EE'\in E$ ，則稱 $G^{'}$ 為 $G$ 的子圖
- 無向完全圖和有向完全圖： 對于無向圖，若具有 $n (n ? 1) / 2$ 條邊，則稱為無向完全圖，對于有向圖，若具有 $n (n ? 1)$ 條弧，則稱為有向完全圖
- 稀疏圖和稠密圖： 有很少條邊或弧（如 $e<nlog_2n$ ），的圖稱為稀疏圖，反之稱為稠密圖
- 權和網： 每條邊可以標上具有某種意義的數字，該數值就稱為該邊的權，這些權可以表示從一個頂點到另一個頂點的距離或耗費。這種帶權的圖通常稱為網
- 鄰接點： 對于無向圖G，如果圖的邊 $(v,v′)∈E(v,v')\in E$ ，則頂點v，v’稱為鄰接點。
- 度，入度，出度： 頂點y的度是指和y相關聯的邊的數目，記為 $T D (v)$ ，入度是指以頂點v為頭的弧的數目記作 $I D (v)$ ，出度是以v為頂點的弧數目，記作 $O D (v)$ ，三者滿足： $T D (v) = I D (v) + O D (v)$ 。一般的滿足： $e=12∑i=1nTD(vi)e=\frac 12 \sum_{i=1}^nTD(v_i)$ 例如：圖6.1中， $G_1$ 中 $V_1$ 的出度為2，入度1，度為3
- 路徑和路徑長度： 在無向圖G中，從頂點v到頂點v’的路徑是一個頂點序列集合，如果是有向圖，那么路徑也是有向的。路徑長度是一條路徑上經過的邊或弧的數目
- 回路或環： 第一個頂點和最后一個頂點相同的路徑
- 簡單路徑，簡單回路，簡單環： 序列中頂點不重復出現的路徑稱為簡單路徑，除了第一個頂點和最后一個頂點之外，其余頂點不重復出現的回路，稱為簡單回路或簡單環
- 連通，連通圖，連通分量： 在無向圖中，兩個頂點之間有路徑，則稱這兩個頂點之間是連通的，如果一個圖中的任意兩個頂點之間連通，則稱該圖為連通圖，連通分量是指無向圖中的極大連通子圖
- 強連通圖，強連通分量： 在有向圖中，如果任意兩個頂點（不相等的兩個頂點），之間都存在路徑。則稱該圖為強連通圖，有向圖中的極大連通子圖稱為有向圖的強連通分量
- 連通圖的生成樹： 一個極小連通子圖，它含有圖中全部頂點，但只有足以構成一棵樹的n-1條邊，這樣的連通子圖稱為連通圖的生成樹
圖的存儲結構：
鄰接矩陣
- 表示頂點之間相鄰關系的矩陣，設G（V,E）是具有n個頂點的圖，則矩陣具有如下性質： $若<vi,vj>或(vi,vj)∈E若<v_i,v_j>或(v_i,v_j)\in E$ $則 A [i] [j] = 1$ $反之$ $A [i] [j] = 0$
  下圖是圖6.1所示 $G_1$ $G_2$ 的鄰接矩陣
  
  若G是網：
  
  鄰接矩陣的優點：
  - 便于判斷兩個點之間是否有邊
  - 便于計算各個頂點的度
  鄰接矩陣的 缺點：
  - 不便于增加和刪除頂點
  - 不便于統計邊的數目
  - 空間復雜度高
鄰接表
鄰接表是圖的一種鏈式存儲結構，在鄰接表中，對圖中每個頂點 $v_i$ 建立一個單鏈表，把與 $v_i$ 相鄰接的頂點放在這個鏈表中，鄰接表中每個單鏈表的第一個結點存放有關頂點的信息，把這以結點看出鏈表的表頭，其余節點存放有關邊的信息，這樣，鄰接表便有兩部分組成，表頭結點表和邊表
- 表頭結點表：由所有表頭結點以順序結構的形式存儲，以便可以隨機訪問任一頂點的邊鏈表。表頭結點包括數據域和鏈域
- 邊表：由表示圖中頂點間關系的2n個邊鏈表組成，邊鏈表中邊結點包括鄰接點域，數據域，鏈域
  
  下圖為表示圖6.1的鄰接表
  
  注意：一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一
鄰接表優點：
- 便于增加和刪除頂點
- 便于統計邊的數目
- 空間效率高
鄰接表缺點：
- 不便于判斷頂點之間是否有邊
- 不便于計算各個頂點的度
十字鏈表
十字鏈表是有向圖的另一種鏈式存儲結構。可以看成將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。
在十字鏈表中，對應有向圖中每一條弧由一個結點，對應每個頂點也有一個結點

在弧結點中有5個域：
- 尾域（tailvex）：弧尾這個頂點在圖中的位置
- 頭域（headvex）：弧頭這個頂點在圖中的位置
- 鏈域（hlink）：指向弧頭相同的下一條弧
- 鏈域（tlink）：指向弧尾相同的下一條弧
- info域（info）：指向弧的相關信息
在頂點結點中有3個域：
- data：存儲和頂點相關的信息
- firstin：指向該頂點為弧頭的第一個弧結點
- firstout：指向該頂點為弧尾的第一個弧結點
圖的遍歷：

圖的遍歷類似于樹的遍歷們也是從圖中某一頂點出發，按照某種方法對圖中所有頂點訪問且僅訪問一次，圖的遍歷算法是求解圖的連通性問題，拓撲排序和關鍵路徑等算法的基礎

根據搜索路徑的方向：有兩條遍歷圖的路徑：

首先說明：這兩種方法對有向圖和無向圖都適用

深度優先搜索（depth first search DFS）
這種遍歷類似于樹的前序（先序）遍歷，是樹的線序遍歷的推廣
- （1）從圖中某個頂點v出發，訪問v
- （2）找出剛訪問過的頂點的第一個未被訪問的鄰接點，訪問該頂點，以該頂點為新頂點，重復此步驟，直到剛訪問過的頂點沒有未被訪問的鄰接點為止
- （3）返回前一個訪問過的且仍有未被訪問的鄰接點的頂點，找出該頂點的下一個未被訪問的鄰接點，訪問該頂點
- （4）重復（2）（3），直到圖中所有頂點都被訪問過，搜索結束
廣度優先搜索（breadth first search BFS）
- （1）從圖中某個頂點v出發，訪問v
- （2）依次訪問v的各個未曾訪問過的鄰接點
- （3）分別從這些鄰接點出發依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，重復步驟（3）直到圖中所有已被未訪問的頂點的鄰接點都被訪問到
接下來看個例子：

可以看出：
DFS的訪問序列為：
- $v_1→v_2→v_4→v_8→v_5→v_3→v_6→v_7$
BFS的訪問序列為：
- $v_1→v_2→v_3→v_4→v_5→v_6→v_7→v_8$
圖中以帶箭頭的粗實線表示遍歷時的訪問路徑，以帶箭頭的虛線表示回溯路徑，小圓圈表示已經被訪問過的鄰接點，大圓圈表示未被訪問的鄰接點

至于兩者的算法實現：只做一點說明：遍歷過程為了區別頂點是否被訪問，需要附設一個標志數組visited[n]，其初值為“false”，一旦頂點被訪問，相應的分量置為“true”，其他情況，具體問題具體分析
圖的應用：
最小生成樹：在一個連通網中，各邊代價之和最小的那棵生成樹為該連通網的最小代價生成樹，簡稱最小生成樹
- 具體算法應用有：
  - 普里姆算法
  - 克魯斯卡爾算法
最短路徑：從源點到終點的所有路徑中，路徑上的邊的權值之和最小的即為最短路徑
- 具體算法應用有：
  - 迪杰斯特拉算法
  - 弗洛伊德算法
拓撲排序算法
關鍵路徑算法

以上四點就是圖的應用，具體算法，自行查找
下來是一個小結：

八、查找

查找的基本概念：
查找表：是同一類型的數據元素（或記錄）構成的集合。
關鍵字：是數據元素（或記錄）中某個數據項的值，用它可以標識一個數據元素（或記錄）。若此關鍵字可以唯一標識一個記錄，則稱此關鍵字為主關鍵字（不同記錄，不同主關鍵字），反之，稱用以識別若干記錄關鍵字為次關鍵字。當數據元素只有一個數據項時，其關鍵字即為該數據元素的值
查找：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的記錄或數據元素，若表中存在這樣一個記錄，則查找成功，此時查找結果可以給出整個記錄信息，或指示該記錄在查找表中的位置，若表中不存在關鍵字等于給定值的記錄，則稱查找不成功，此時查找結果可以給出一個“空”記錄或“空”指針
動態查找表和靜態查找表：若查找的同時對表做修改操作（如：插入和刪除），則相應的表稱為動態查找表，反之，稱為靜態查找表
平均查找長度： 為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數的期望值，稱為在查找成功時的平均查找長度。
對含有n個記錄的表，查找成功時的平均查找長度為： $ASL=∑i=1nPiCiASL=\sum_{i=1}^nP_iC_i$ 其中， $P_i$ 為查找表中第 $i$ 個記錄的概率，且 $∑i=1nPi=1\sum_{i=1}^nP_i=1$ ； $C_i$ 為找到表中其關鍵字與給定值相等的第 $i$ 個記錄時，和給定值已進行比較過的關鍵字個數。顯然， $C_i$ 隨查找過程不同而不同
線性表的查找:
順序查找
- 過程：從表的一端開始，依次將記錄的關鍵字和給定值進行比較，若記錄的關鍵字和給定值相等，則查找成功；反之，若掃描整個表后，仍未找到關鍵字和給定值相等的記錄，則查找失敗。順序查找，前面已經介紹過了，此處不再贅述
二分查找
- 二分查找也稱折半查找，它是一種效率較高的查找方法，但是，折半查找要求線性表必須采用順序存儲結構

例如：已知如下 11個數據元素的有序表(關鍵字即為數據元素的值)
（5，16，20，27，30，36，44，55，60，67，71）
查找27,65的過程：

分塊查找
- 分塊查找又稱索引順序查找，這是一種性能介于順序查找和二分查找之間的一種查找方法。在此方法中，除表本身外，尚需建里一個索引表。
  
  這樣，分塊查找分為兩步，先和索引表做比較，在確定子表。例如：查找38，22<38<48，如果38存在，那么一定在第二子表中，然后在該子表中做順序查找

分塊查找的平均查找度：
將長度為n的表，平均分為b塊，每個塊有s個記錄，即 $b=?n/s?b=\lceil n/s \rceil$ 假定表中每個記錄的查找概率相等，則，每塊查找的概率為 $1 / b$ ，塊中每個記錄的查找概率為 $1 / s$ ，設 $L_b，L_w$ 分別為：查找索引表確定所在的塊的平均查找長度，在塊中查找元素的平均查找長度。則分塊查找的平均查找長度為： $ASLbs=Lb+Lw=1b∑j=1bj+1s∑i=1s=b+12+s+12=12(ns+s)+1ASL_{bs}=L_b+L_w=\frac 1 b \sum_{j=1}^b j +\frac 1 s \sum_{i=1}^s=\frac {b+1} 2 +\frac{s+1} 2=\frac 1 2 ( \frac n s+s)+1$ 可見，此時的平均查找長度不僅與n有關還和s有關，容易證明當 $s=ns=\sqrt n$ 時，平均查找長度取到最小值 $n+1\sqrt n +1$ ，但其遠不及折半查找

分塊查找的優缺點：

優點：在表中插入和刪除數據元素時，只需要找到該元素對應的塊，就可以在該塊內進行插入和刪除運算
缺點：要增加一個索引表的存儲可見并對初始索引進行排序運算

樹表的查找:

二叉排序樹
- 二叉排序樹又稱二叉查找樹，它是一種對排序和查找都很有用的特殊二叉樹
- 二叉排序樹定義：二叉排序樹或者式一棵空樹，或者是具有下列性質的二叉樹
  （1）若**左子樹**不空，則左子樹上所有結點的值**均小于它的根結點的值**（2）若**右子樹**不空，則右子樹上所有結點的值**均大于它的根結點的值**（3）它的左，右子樹分別也為二叉排序樹
由二叉排序樹的定義（遞歸定義）得知一個重要性質：中序遍歷一棵二叉樹時，可以得到接待你值遞增的有序序列

所以在二叉排序樹上進行查找和折半查找類似
平衡二叉樹
- 定義：或者是空樹，或者是具有以下性質的二叉排序樹
  - 左子樹和右子樹的深度之差的絕對值不超過1；
  - 左子樹和右子樹也是平衡二叉樹
    
    若將二叉樹上的所有結點的定義為該結點左子樹和右子樹的深度之差，則平衡二叉樹上所有結點的平衡因子只可能是1 0 -1 。如下圖
散列表的查找:
散列表查找又叫哈希表查找，通過查找關鍵字不需要比較就可以獲得需要記錄的存儲位置，它是通過在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f（key）。即：
—存儲位置=f（關鍵字），其中f為哈希函數。
- 幾個基本術語:
- 散列函數和散列地址：在記錄的存儲位置 $p$ 和其關鍵字 $k e y$ 之間建立一個確定的對應關系 $H$ ，使 $p = H (k e y)$ ,稱這個對應關系 $H$ 為散列函數， $p$ 為散列地址。
- 散列表：一個有限連續的地址空間，所以存儲按散列函數計算得到的相應散列地址的數據記錄，通常散列表的存儲空間是一個一維數組，散列地址是數組的下標
- 沖突和同義詞：對不同的關鍵字可能得到同一散列地址，即 $key_1≠key_2$ ，然而 $H(key_1)=H(key_2)$ ，這種現象稱為沖突，具有相同函數值的關鍵字對該散列函數來說稱作同義詞， $key_1和key_2$ 互稱為同義詞
- 哈希表的構造方法：
  - 直接定址法
  - 數字分析法
  - 平方取中法
  - 折疊法
  - 除留余數法
- 處理沖突的方法：
- 開放地址法
  - 線性探測法
  - 二次探測發
  - 偽隨機探測法
- 鏈地址法
  
  圖中裝填因子α定義為： $α=表中填入的記錄數散列表的長度α=\frac {表中填入的記錄數}{散列表的長度}$ α標志散列表的裝滿程度

下來，是一個小結：

九、排序

基本概念和方法：
排序： 是按關鍵字的非遞減或非遞增順序對一組記錄進行重新排列的操作
排序穩定性：當排序記錄中的關鍵字右兩個或以上的關鍵字記錄相等時。假設 $k_i=k_j(i≠j，i，j都在范圍內)$ ，且排序前的序列中 $R_i$ 領先 $R_j$ 即 $i < j$ 若排序后 $R_i$ 仍然領先 $R_j$ 那么，稱所使用的排序方法是穩定的，反之，稱為不穩定
內部排序和外部排序：內部排序是指排序記錄全部存放在計算機內存中進行排序的過程，外部排序是指排序記錄數量很大，內存不能全部容納，在拍戲過程中尚需對外村進行訪問的排序過程
內部排序的分類：
- 插入類：
  - 插入排序
  - 折半插入排序
  - 希爾排序
- 交換類：
  - 冒泡排序
  - 快速排序
- 歸并類：
  - 2-路歸并排序
- 分配類：
  - 基數排序
- 選擇類：
  - 簡單選擇排序
  - 樹形選擇排序
  - 堆排序
插入排序：
- 直接插入排序
  - 最簡單的排序方法，基礎操作為：將一條記錄插入到已排好序的有序表中
    
    時間復雜度為： $O(n^2)$
    空間復雜度為： $O (1)$
- 折半插入排序
  - 在直接插入排序的基礎上增加“折半查找”這一操作，例如，在圖8.1中，在每一次插入新的數據時，都得從第一個元素開始比較，而折半插入排序，則是，每次“比較”都使用折半查找找到要插入數據的該插入位置，而不是一個個的比較。
  - 時間和空間復雜度和直接插入排序相同
  - 此算法時穩定排序
  - 適用于順序結構，
  - 適用于初始記錄無須，n較大
- 希爾排序
  - 又稱縮小增量排序，希爾排序，從減少記錄個數和序列基本有序，兩個方面對直接插入排序進行改進
  - 本質上時采用分組插入法
    
    d代表所有間隔為d的記錄在一組。對組兩頭的數據進行交換即可
交換排序：
- 冒泡排序：
  - 是一種最簡單的交換排序方法，它通過兩兩比較相鄰記錄的關鍵字，如果發生逆序，則進行交換，從而實現排序
    
    時間復雜度： $O(n^2)$
    空間復雜度： $O (1)$
- 快速排序
  - 由冒泡排序改進而來，在冒泡排序中，支隊相鄰的兩個記錄進行比較，因此每次交換兩個相鄰的記錄只能消除一個逆序，如果能通過兩個（不相鄰）記錄的一次交換，消除多個逆序，則會大大增加排序的速度。快速排序即可一次交換消除多個逆序
    
    說明：
    - 先選擇排序表中的第一個記錄作為樞軸（pivotkey），將其暫時記錄在r[0]的位置，附設兩個指針low和high，分別指向表的下界和上界
    - 從表的右側依次向左搜索，找到第一個關鍵字小于樞軸關鍵字的記錄，將其移動到low處
    - 從表的左側依次向右搜索，找到第一個關鍵字大于樞軸關鍵字的記錄，將其和樞軸關鍵字交換位置。
    - 重復第二步和第三步，直到low和high相等
    時間復雜度： $O(nlog_2n)$
    空間復雜度：
    - 最好情況下： $O(log_2n)$
    - 最壞情況下： $O (n)$
選擇排序：
- 選擇排序的基本思想：每一趟從待排序的記錄中選出關鍵字最小的記錄，放到已排序的序列中，重復直到全部拍完
  - 簡單選擇排序：
    - 也稱為直接選擇排序
      
      時間復雜度： $O(n^2)$
      空間復雜度： $O (1)$
  - 樹形選擇排序：
    - 又稱錦標賽排序，是一種按照錦標賽的思想進行選擇排序的方法，首先對n個記錄的關鍵字進行兩兩比較，然后在其中 $[n2][\frac n2 ]$ 個較小者之間再進行兩兩比較，如此重復，直到選出最小關鍵字的記錄為止。這個記錄可用一棵由n個葉子結點的完全二叉樹表示。
      
      接下來，看一種樹形選擇排序
  - 堆排序：
    - 堆排序是一種樹形選擇排序，是維洛姆斯在1964年提出的，在該排序過程中，將待排序的記錄 r[1…n] 看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序的序列中選擇關鍵字最大（或最小）的記錄
    - 堆分為最大堆和最小堆，其實就是完全二叉樹。最大堆要求節點的元素都要不小于其孩子，最小堆要求節點元素都不大于其左右孩子，兩者對左右孩子的大小關系不做任何要求，其實很好理解。有了上面的定義，我們可以得知，處于最大堆的根節點的元素一定是這個堆中的最大值。
    - 其實我們的堆排序算法就是抓住了堆的這一特點，**每次都取堆頂的元素，將其放在序列最后面，**然后將剩余的元素重新調整為最大堆，依次類推，最終得到排序的序列。
      
      時間復雜度： $O(nlog_2n)$
      空間復雜度： $O (1)$
歸并排序：
- 歸并排序就是將兩個或兩個以上的有序表合并成一個有序表的過程。
- 2-路歸并：
  - 將兩個有序表合并成一個有序表的過程稱為2-路歸并
  - 思想：假設初始序列由含有n個記錄，則可看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到[n/2]個長度為2或1 的有序子序列，在兩兩歸并，…，如此重復，直至得到一個長度為n的有序序列為止。
    
    時間復雜度： $O(nlog_2n)$
    空間復雜度： $O (n)$
基數排序：
- 基數排序與前面的排序方法都不同，它不需要比較關鍵字的大小。它是根據關鍵字中各位的值，通過對排序的N個元素進行若干趟“分配”與“收集”來實現排序的。例如：撲克牌的按花色分配收集和按面值分配收集
  例如：
  - 初始序列： R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}
  我們知道，對于數字來說，個十百位的數字無非0~9，所以先按個位分類得到：

050300100

1	11
2	2
3	123	543
4
5
6
7	187
8
9	49

接下來，按照，0~9的順序，排列得到：
{50, 30, 0, 100, 11, 2, 123, 543, 187, 49}
同理，按十位數排列，百位數排列，…，最后得到的必然是有序序列

外部排序：
- 外部排序指的是大文件的排序，即待排序的記錄存儲在外存儲器上，待排序的文件無法一次裝入內存，需要在內存和外部存儲器之間進行多次數據交換，以達到排序整個文件的目的

總結

以上是生活随笔為你收集整理的数据结构教程(c语言)(已完结)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。