《王道》資料結構筆記整理2022

第一章：緒論

1.1資料結構的基本概念

1.資料：資料是資訊的載體，是描述客觀事物屬性的數、字符以及所有能輸入到計算機中并被程式識別和處理的符號的集合，

2.資料元素：資料元素是資料的基本單位，通常作為一個整體進行考慮和處理，一個資料元素可由若干資料項組成，資料項是構成資料元素的不可分割的最小單位，例如，學生記錄就是一個資料元素，它由學號、姓名、性別等資料項組成，

3.資料物件:資料物件是具有相同性值的資料元素的集合，是資料的一個子集，

4.資料型別:資料型別是一個值的集合和定義再此集合上的一組操作的總稱，

1）原子型別，其值不可再分的資料型別，如bool 和int 型別，
2）結構型別，其值可以再分解為若干成分（分量）的資料型別，
3）抽象資料型別，抽象資料組織及與之相關的操作，

5.資料結構:資料結構是相互之間存在一種或多種特定關系的資料元素的集合，

1.2資料結構的三要素

1.資料的邏輯結構：
邏輯結構是指資料元素之間的邏輯關系，即從邏輯關系上描述資料，
邏輯結構包括：

1. 集合結構：結構中的資料元素之間除“同屬一個集合”外，別無其它關系，
2. 線性結構：結構中的資料元素之間只存在一對一的關系，除了第一個元素，所有元素都有唯一前驅；除了最后一個元素，所有元素都有唯一后繼，
3. 樹形結構：結構中資料元素之間存在一對多的關系，
4. 圖狀結構：資料元素之間是多對多的關系，

2.資料的存盤結構（物理結構）：
存盤結構是指資料結構在計算機中的表示（又稱映像），也稱物理結構，
存盤結構包括：

1. 順序存盤：把邏輯上相鄰的元素存盤在物理位置也相鄰的存盤單元中，元素之間的關系由存盤單元的鄰接關系來體現，
2. 鏈式存盤：邏輯上相鄰的元素在物理位置上可以不相鄰，借助指示元素存盤地址的指標來表示元素之間的邏輯關系，
3. 索引存盤：在存盤元素資訊的同時，還建立附加的索引表，索引表中的每項稱為索引項，索引項的一般形式是（關鍵字，地址）
4. 散列存盤：根據元素的關鍵字直接計算出該元素的存盤地址，又稱哈希（Hash）存盤，

3.資料的運算：施加在資料上的運算包括運算的定義何實作，運算的定義是針對邏輯結構的，指出運算的功能；運算的實作是針對存盤結構的，指出運算的具體操作步驟，

1.3演算法的基本概念

程式=資料結構+演算法
演算法（algorithm)是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作，
演算法的特性：
1.有窮性：一個演算法必須總在執行有窮步之后結束，且每一步都可在有窮時間內完成，
2.確定性：演算法中每條指令必須有確定的含義，對于相同的輸入只能得到相同的輸出，
3.可行性：演算法中描述的操作都可以通過已經實作的基本運算執行有限次來實作，
4.輸入：一個演算法有零個或多個輸入，這些輸入取自于某個特定的物件的集合，
5.輸出：一個演算法有一個多個輸出，這些輸出是與輸入有著某種特定關系的量，
好的演算法達到的目標：

1. 正確性：演算法應能夠正確的求接問題，
2. 可讀性：演算法應具有良好的可讀性，以幫助人們理解，
3. 健壯性：輸入非法資料時，演算法能適當地做出反應或進行處理，而不會產生莫名奇妙地輸出結果，
4. 效率與低存盤量需求：效率是指演算法執行的時間，存盤量需求是指演算法執行程序中所需要的最大存盤空間，這兩者都與問題的規模有關，

1.4演算法的時間復雜度

一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函式f(n)，演算法的時間量度記作T（n)=O(n)，它表示隨問題規模n的增大而增大，演算法執行時間的增長率和f(n)的增長率相同，稱作演算法的漸近時間復雜度，簡稱時間復雜度，

1.5演算法的空間復雜度

演算法的空間復雜度S(n)定義為該演算法所耗費的存盤空間，它是問題規模n的函式，記為S(n)=O(g(n))，

第二章：線性表

2.1線性表的定義

線性表是具有相同資料型別的n(n>0)個資料元素的有限序列，其中n為表長，當n=0時線性表是一個空表，

2.2順序表的定義

2.2.1靜態分配:

//順序表的實作--靜態分配

#include<stdio.h>
#define MaxSize 10   //定義表的最大長度 
typedef struct{
	int data[MaxSize];//用靜態的"陣列"存放資料元素
	int length; //順序表的當前長度  
}SqList;        //順序表的型別定義（靜態分配方式） 
void InitList(SqList &L){
	 for(int i=0;i<MaxSize;i++){
	 	L.data[i]=0;  //將所有資料元素設定為默認初始值
		  
	 }
	 L.length=0;
}
int main(){
	SqList L;//宣告一個順序表
	InitList(L);//初始化一個順序表
	for(int i=0;i<MaxSize;i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	}
	return 0; 
}

2.2.2動態分配

//順序表的實作——動態分配
#include<stdio.h>
#include<stdlib.h>//malloc、free函式的頭檔案 
#define InitSize 10 //默認的最大長度
typedef struct{
	int  *data;//指示動態分配陣列的指標
	int MaxSize; //順序表的最大容量
	int length;  //順序表的當前長度 
}SeqList; 
//初始化
void InitList(SeqList &L){
	//用malloc 函式申請一片連續的存盤空間
	L.data =(int*)malloc(InitSize*sizeof(int)) ;
	L.length=0;
	L.MaxSize=InitSize;
} 
//增加動態陣列的長度
void IncreaseSize(SeqList &L,int len){
	int *p=L.data;
	L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];   //將資料復制到新區域 
	}
	L.MaxSize=L.MaxSize+len; //順序表最大長度增加len
	free(p);  //釋放原來的記憶體空間 
	
} 
int main(void){
	SeqList L; //宣告一個順序表
	InitList(L);//初始化順序表
	IncreaseSize(L,5);
	return 0; 
}

順序表的特點：

1. 隨機訪問 ，可以在O(1)時間內找到第i個元素，
2. 存盤密度高，每個節點只存盤資料元素
3. 拓展容量不方便
4. 插入、洗掉操作不方便，需要移動大量元素

2.2順序表的基本操作

1.插入操作 ：平均時間復雜度O(n)

bool ListInsert(SqList &L, int i, int e){ 
    //判斷i的范圍是否有效
    if(i<1||i>L.length+1) 
        return false;
    if(L.length>MaxSize) //當前存盤空間已滿，不能插入  
        return false;

    for(int j=L.length; j>i; j--){    //將第i個元素及其之后的元素后移
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;  //在位置i處放入e
    L.length++;      //長度加1
    return true;
}

2.洗掉操作：平均時間復雜度O(n)

bool LisDelete(SqList &L, int i, int &e){ // e用參考型引數 
    //判斷i的范圍是否有效
    if(i<1||i>L.length) 
        return false;

    e = L.data[i-1]    //將被洗掉的元素賦值給e

    for(int j=L.length; j>i; j--){    //將第i個后的元素前移
        L.data[j-1]=L.data[j];
    }
    L.length--;      //長度減1
    return true;
}

3.按位查找(獲取L表中第i個位置的值)：平均時間復雜度O(1)

#define MaxSize 10            //定義最大長度 
typedef struct{
    ElemType data[MaxSize];  //用靜態的“陣列”存放資料元素 
    int Length;              //順序表的當前長度
}SqList;                     //順序表的型別定義

ElemType GetElem(SqList L, int i){
    // ...判斷i的值是否合法
    return L.data[i-1];      //注意是i-1
}

4.按值查找：平均時間復雜度O（n）

#define InitSize 10            //定義最大長度 
typedef struct{
    ElemTyp *data;  //用靜態的“陣列”存放資料元素 
    int Length;              //順序表的當前長度
}SqList;   

//在順序表L中查找第一個元素值等于e的元素，并回傳其位序
int LocateElem(SqList L, ElemType e){
    for(int i=0; i<L.lengthl i++)
        if(L.data[i] == e)  
            return i+1;     //陣列下標為i的元素值等于e，回傳其位序i+1
    return 0;               //推出回圈，說明查找失敗
}

2.3線性表的鏈式表示

2.3.1 單鏈表的定義

定義： 線性表的鏈式存盤又稱單鏈表，它是指通過一組任意的存盤單元來存盤線性表中的資料元素，

typedef struct LNode{//定義單鏈表結點型別
    ElemType data; //資料域
    struct LNode *next;//指標域
}LNode, *LinkList;

可以利用typedef關鍵字——資料型別重命名：type<資料型別><別名>

單鏈表的兩種實作方式：

1. 不帶頭結點的單鏈表

```bash
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化一個空的單鏈表
bool InitList(LinkList &L){  //注意用參考 &
    L = NULL; //空表，暫時還沒有任何結點；
    return true;
}

void test(){
    LinkList L;  //宣告一個指向單鏈表的指標: 頭指標
    //初始化一個空表
    InitList(L);
    //...
}

//判斷單鏈表是否為空
bool Empty(LinkList L){
    if (L == NULL)
        return true;
    else
        return false;
}

頭結點：代表鏈表上頭指標指向的第一個結點，不帶有任何資料，

2. 帶頭結點的單鏈表

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化一個單鏈表（帶頭結點）
bool InitList(LinkList &L){  
    L = (LNode*) malloc(sizeof(LNode));  //頭指標指向的結點——分配一個頭結點（不存盤資料）
    if (L == NULL)          //記憶體不足，分配失敗
        return false;
    L -> next = NULL;       //頭結點之后暫時還沒有結點
    return true;
}

void test(){
    LinkList L;  //宣告一個指向單鏈表的指標: 頭指標
    //初始化一個空表
    InitList(L);
    //...
}

//判斷單鏈表是否為空（帶頭結點）
bool Empty(LinkList L){
    if (L->next == NULL)
        return true;
    else
        return false;
}

帶頭結點和不帶頭結點的比較：
不帶頭結點：寫代碼麻煩！對第一個資料節點和后續資料節點的處理需要用不同的代碼邏輯，對空表和非空表的處理也需要用不同的代碼邏輯; 頭指標指向的結點用于存放實際資料;
帶頭結點：頭指標指向的頭結點不存放實際資料,頭結點指向的下一個結點才存放實際資料;

2.3.2單鏈表上基本操作的實作

1.按位序插入（帶頭結點）：
==ListInsert(&L, i, e): ==在表L中的第i個位置上插入指定元素e = 找到第i-1個結點(前驅結點)，將新結點插入其后；其中頭結點可以看作第0個結點，故i=1時也適用，

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//在第i個位置插入元素e（帶頭結點）
bool ListInsert(LinkList &L, int i, ElemType e){  
    //判斷i的合法性, i是位序號(從1開始)
    if(i<1)
        return False;
    
    LNode *p;       //指標p指向當前掃描到的結點 
    int j=0;        //當前p指向的是第幾個結點
    p = L;          //L指向頭結點，頭結點是第0個結點（不存資料）

    //回圈找到第i-1個結點
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后會等于NULL
        p = p->next;             //p指向下一個結點
        j++;
    }

    if (p==NULL)                 //i值不合法
        return false;
    
    //在第i-1個結點后插入新結點
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申請一個結點
    s->data = e;
    s->next = p->next;
    p->next = s;                 //將結點s連到p后,后兩步千萬不能顛倒qwq

    return true;
}

平均時間復雜度：O(n)

2.按位序插入（不帶頭結點）
==ListInsert(&L, i, e): ==在表L中的第i個位置上插入指定元素e = 找到第i-1個結點(前驅結點)，將新結點插入其后; 因為不帶頭結點，所以不存在“第0個”結點，因此！i=1 時，需要特殊處理——插入(洗掉)第1個元素時，需要更改頭指標L;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    
    //插入到第1個位置時的操作有所不同！
    if(i==1){
        LNode *s = (LNode *)malloc(size of(LNode));
        s->data =e;
        s->next =L;
        L=s;          //頭指標指向新結點
        return true;
    }

    //i>1的情況與帶頭結點一樣！唯一區別是j的初始值為1
    LNode *p;       //指標p指向當前掃描到的結點 
    int j=1;        //當前p指向的是第幾個結點
    p = L;          //L指向頭結點，頭結點是第0個結點（不存資料）

    //回圈找到第i-1個結點
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后會等于NULL
        p = p->next;             //p指向下一個結點
        j++;
    }

    if (p==NULL)                 //i值不合法
        return false;
    
    //在第i-1個結點后插入新結點
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申請一個結點
    s->data = e;
    s->next = p->next;
    p->next = s;          
    return true;

}

3.指定結點的后插操作：

InsertNextNode(LNode *p, ElemType e): 給定一個結點p，在其之后插入元素e; 根據單鏈表的鏈接指標只能往后查找，故給定一個結點p，那么p之后的結點我們都可知，但是p結點之前的結點無法得知;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool InsertNextNode(LNode *p, ElemType e){
    if(p==NULL){
        return false;
    }

    LNode *s = (LNode *)malloc(sizeof(LNode));
    //某些情況下分配失敗，比如記憶體不足
    if(s==NULL)
        return false;
    s->data = e;          //用結點s保存資料元素e 
    s->next = p->next;
    p->next = s;          //將結點s連到p之后

    return true;
}                         //平均時間復雜度 = O(1)


//有了后插操作，那么在第i個位置上插入指定元素e的代碼可以改成：
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(i<1)
        return False;
    
    LNode *p;       //指標p指向當前掃描到的結點 
    int j=0;        //當前p指向的是第幾個結點
    p = L;          //L指向頭結點，頭結點是第0個結點（不存資料）

    //回圈找到第i-1個結點
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后4鳥會等于NULL
        p = p->next;             //p指向下一個結點
        j++;
    }

    return InsertNextNode(p, e)
}

4.指定結點的前插操作
思想：設待插入結點是s，將s插入到p的前面，我們仍然可以將s插入到*p的后面，然后將p->data與s->data交換，這樣既能滿足了邏輯關系，又能是的時間復雜度為O(1).（真是妙的不達鳥）

//前插操作：在p結點之前插入元素e
bool InsertPriorNode(LNode *p, ElenType e){
    if(p==NULL)
        return false;
    
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL) //記憶體分配失敗
        return false;

    //重點來了！
    s->next = p->next;
    p->next = s;       //新結點s連到p之后
    s->data = p->data; //將p中元素復制到s
    p->data = e;       //p中元素覆寫為e

    return true；
}  //時間復雜度為O(1)

王道書代碼：

bool InsertPriorNode(LNode *p, LNode *s){
    if(p==NULL || S==NULL)
        return false;
    
    s->next = p->next;
    p->next = s;  ///s連接到p
    ELemType temp = p->data;  //交換資料域部分
    p->data = s->data;
    s->data = temp;

    return true;
}
 

5.按位序洗掉節點（帶頭結點）
ListDelete(&L, i, &e): 洗掉操作，洗掉表L中第i個位置的元素，并用e回傳洗掉元素的值;頭結點視為“第0個”結點；

思路：找到第i-1個結點，將其指標指向第i+1個結點，并釋放第i個結點；

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool ListDelete(LinkList &L, int i, ElenType &e){
    if(i<1) return false;

    LNode *p;       //指標p指向當前掃描到的結點 
    int j=0;        //當前p指向的是第幾個結點
    p = L;          //L指向頭結點，頭結點是第0個結點（不存資料）

    //回圈找到第i-1個結點
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后會等于NULL
        p = p->next;             //p指向下一個結點
        j++;
    }

    if(p==NULL) 
        return false;
    if(p->next == NULL) //第i-1個結點之后已無其他結點
        return false;

    LNode *q = p->next;         //令q指向被洗掉的結點
    e = q->data;                //用e回傳被洗掉元素的值
    p->next = q->next;          //將*q結點從鏈中“斷開”
    free(q)                     //釋放結點的存盤空間

    return true;
}

時間復雜度分析：
最壞，平均時間復雜度：O(n)

最好時間復雜度：洗掉第一個結點 O(1)

6.指定結點的洗掉

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    
    LNode *q = p->next;      //令q指向*p的后繼結點
    p->data = p->next->data; //讓p和后繼結點交換資料域
    p->next = q->next;       //將*q結點從鏈中“斷開”
    free(q);
    return true;
} //時間復雜度 = O(1)

2.3.3單鏈表的查找

按位查找
==GetElem(L, i): ==按位查找操作，獲取表L中第i個位置的元素的值;

LNode * GetElem(LinkList L, int i){
    if(i<0) return NULL;
    
    LNode *p;               //指標p指向當前掃描到的結點
    int j=0;                //當前p指向的是第幾個結點
    p = L;                  //L指向頭結點,頭結點是第0個結點(不存資料)
    while(p!=NULL && j<i){  //回圈找到第i個結點
        p = p->next;
        j++;
    }

    return p;               //回傳p指標指向的值
}

平均時間復雜度O（n）

按值查找
LocateElem(L, e):按值查找操作，在表L中查找具有給定關鍵字值的元素;

LNode * LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;    //p指向第一個結點
    //從第一個結點開始查找資料域為e的結點
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;           //找到后回傳該結點指標，否則回傳NULL
}

2.3.4求單鏈表的長度

== Length(LinkList L)==：計算單鏈表中資料結點（不含頭結點）的個數，需要從第一個結點看是順序依次訪問表中的每個結點，演算法的時間復雜度為O（n），

int Length(LinkList L){
    int len=0;       //統計表長
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

2.3.5單鏈表的創建操作

1.頭插法建立單鏈表（平均時間復雜度O(n)）
思路：每次都將生成的結點插入到鏈表的表頭，

LinkList List_HeadInsert(LinkList &L){       //逆向建立單鏈表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));     //建立頭結點
    L->next = NULL;                          //初始為空鏈表,這步不能少！

    scanf("%d", &x);                         //輸入要插入的結點的值
    while(x!=9999){                          //輸入9999表結束
        s = (LNode *)malloc(sizeof(LNode));  //創建新結點
        s->data = x;
        r->next = L->next;
        L->next = s;                         //將新結點插入表中，L為頭指標
        scanf("%d", &x);   
    }
    return L;
   
}

2.尾插法建立單鏈表（時間復雜度O（n））
思路：每次將新節點插入到當前鏈表的表尾，所以必須增加一個尾指標r,使其始終指向當前鏈表的尾結點，好處：生成的鏈表中結點的次序和輸入資料的順序會一致，

LinkList List_TailInsert(LinkList &L){       //正向建立單鏈表
    int x;                                   //設ElemType為整型int
    L = (LinkList)malloc(sizeof(LNode));     //建立頭結點(初始化空表)
    LNode *s, *r = L;                        //r為表尾指標
    scanf("%d", &x);                         //輸入要插入的結點的值
    while(x!=9999){                          //輸入9999表結束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s                                //r指標指向新的表尾結點
        scanf("%d", &x);   
    }
    r->next = NULL;                          //尾結點指標置空
    return L;
}

鏈表的逆置：
演算法思想：逆置鏈表初始為空，原表中結點從原鏈表中依次“洗掉”，再逐個插入逆置鏈表的表頭（即“頭插”到逆置鏈表中），使它成為逆置鏈表的“新”的第一個結點，如此回圈，直至原鏈表為空；

LNode *Inverse(LNode *L)
{
	LNode *p, *q;
	p = L->next;     //p指標指向第一個結點
	L->next = NULL;  //頭結點指向NULL

	while (p != NULL){
		q = p;
		p = p->next;
		q->next = L->next;  
		L->next = q;
	}
	return L;

2.3.6雙鏈表

雙鏈表中節點型別的描述：`

typedef struct DNode{            //定義雙鏈表結點型別
    ElemType data;               //資料域
    struct DNode *prior, *next;  //前驅和后繼指標
}DNode, *DLinklist;

雙鏈表的初始化（帶頭結點）

typedef struct DNode{            //定義雙鏈表結點型別
    ElemType data;               //資料域
    struct DNode *prior, *next;  //前驅和后繼指標
}DNode, *DLinklist;

//初始化雙鏈表
bool InitDLinkList(Dlinklist &L){
    L = (DNode *)malloc(sizeof(DNode));      //分配一個頭結點
    if(L==NULL)                              //記憶體不足，分配失敗
        return false;
    
    L->prior = NULL;   //頭結點的prior指標永遠指向NULL
    L->next = NULL;    //頭結點之后暫時還沒有結點
    return true;
}

void testDLinkList(){
    //初始化雙鏈表
    DLinklist L;         // 定義指向頭結點的指標L
    InitDLinkList(L);    //申請一片空間用于存放頭結點，指標L指向這個頭結點
    //...
}

//判斷雙鏈表是否為空
bool Empty(DLinklist L){
    if(L->next == NULL)    //判斷頭結點的next指標是否為空
        return true;
    else
        return false;
}

雙鏈表的插入操作
后插操作
InsertNextDNode(p, s): 在p結點后插入s結點

bool InsertNextDNode(DNode *p, DNode *s){ //將結點 *s 插入到結點 *p之后
    if(p==NULL || s==NULL) //非法引數
        return false;
    
    s->next = p->next;
    if (p->next != NULL)   //p不是最后一個結點=p有后繼結點  
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    
    return true;
}

按位序插入操作：
思路：從頭結點開始，找到某個位序的前驅結點，對該前驅結點執行后插操作；
前插操作：
思路：找到給定結點的前驅結點，再對該前驅結點執行后插操作；
雙鏈表的洗掉操作
洗掉p節點的后繼節點

//洗掉p結點的后繼結點
bool DeletNextDNode(DNode *p){
    if(p==NULL) return false;
    DNode *q =p->next;            //找到p的后繼結點q
    if(q==NULL) return false;     //p沒有后繼結點;
    p->next = q->next;
    if(q->next != NULL)           //q結點不是最后一個結點
        q->next->prior=p;
    free(q);

    return true;
}

//銷毀一個雙鏈表
bool DestoryList(DLinklist &L){
    //回圈釋放各個資料結點
    while(L->next != NULL){
        DeletNextDNode(L);  //洗掉頭結點的后繼結點
    free(L); //釋放頭結點
    L=NULL;  //頭指標指向NULL

    }
}

雙鏈表的遍歷操作
前向遍歷

while(p!=NULL){
    //對結點p做相應處理，eg列印
    p = p->prior;
}

后向遍歷

while(p!=NULL){
    //對結點p做相應處理，eg列印
    p = p->next;
}

注意：雙鏈表不可隨機存取，按位查找和按值查找操作都只能用遍歷的方式實作，時間復雜度為O(n)

2.3.7回圈鏈表

1.回圈單鏈表
最后一個結點的指標不是NULL,而是指向頭結點

typedef struct LNode{            
    ElemType data;               
    struct LNode *next;  
}DNode, *Linklist;

/初始化一個回圈單鏈表
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); //分配一個頭結點
    if(L==NULL)             //記憶體不足，分配失敗
        return false;
    L->next = L;            //頭結點next指標指向頭結點
    return true;
}

//判斷回圈單鏈表是否為空
bool Empty(LinkList L){
    if(L->next == L)
        return true;    //為空
    else
        return false;
}

//判斷結點p是否為回圈單鏈表的表尾結點
bool isTail(LinkList L, LNode *p){
    if(p->next == L)
        return true;
    else
        return false;
}

單鏈表和回圈單鏈表的比較：
**單鏈表：**從一個結點出發只能找到該結點后續的各個結點；對鏈表的操作大多都在頭部或者尾部；設立頭指標，從頭結點找到尾部的時間復雜度=O(n)，即對表尾進行操作需要O(n)的時間復雜度;
**回圈單鏈表：**從一個結點出發，可以找到其他任何一個結點；設立尾指標，從尾部找到頭部的時間復雜度為O(1)，即對表頭和表尾進行操作都只需要O(1)的時間復雜度;

2.回圈雙鏈表
表頭結點的prior指向表尾結點，表尾結點的next指向頭結點

typedef struct DNode{          
    ElemType data;               
    struct DNode *prior, *next;  
}DNode, *DLinklist;

//初始化空的回圈雙鏈表
bool InitDLinkList(DLinklist &L){
    L = (DNode *) malloc(sizeof(DNode));    //分配一個頭結點
    if(L==NULL)            //記憶體不足，分配失敗
        return false;  
    L->prior = L;          //頭結點的prior指向頭結點
    L->next = L;           //頭結點的next指向頭結點
}

void testDLinkList(){
    //初始化回圈單鏈表
    DLinklist L;
    InitDLinkList(L);
    //...
}

//判斷回圈雙鏈表是否為空
bool Empty(DLinklist L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判斷結點p是否為回圈雙鏈表的表尾結點
bool isTail(DLinklist L, DNode *p){
    if(p->next == L)
        return true;
    else
        return false;
}

雙鏈表的插入（回圈雙鏈表）：

bool InsertNextDNode(DNode *p, DNode *s){ 
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;

雙鏈表的洗掉

//洗掉p的后繼結點q
p->next = q->next;
q->next->prior = p;
free(q);

2.3.8靜態鏈表

1. 定義：

• 單鏈表：各個結點散落在記憶體中的各個角落，每個結點有指向下一個節點的指標(下一個結點在記憶體中的地址);

• 靜態鏈表：用陣列的方式來描述線性表的鏈式存盤結構: 分配一整片連續的記憶體空間，各個結點集中安置，包括了——資料元素and下一個結點的陣列下標(游標)

  • 其中陣列下標為0的結點充當"頭結點"
  • 游標為-1表示已經到達表尾
  • 若每個資料元素為4B，每個游標為4B，則每個結點共8B；假設起始地址為addr，則資料下標為2的存放地址為：addr+8*2
  • 注意： 陣列下標——物理順序，位序——邏輯順序；
  • 優點：增、刪操作不需要大量移動元素；
  • 缺點：不能隨機存取，只能從頭結點開始依次往后查找，容量固定不變！

2.靜態鏈表用代碼表示：

#define MaxSize 10        //靜態鏈表的最大長度

struct Node{              //靜態鏈表結構型別的定義
    ElemType data;        //存盤資料元素
    int next;             //下一個元素的陣列下標(游標)
};

//用陣列定義多個連續存放的結點
void testSLinkList(){
    struct Node a[MaxSize];  //陣列a作為靜態鏈表, 每一個陣列元素的型別都是struct Node
    //...
}

也可以這樣：

#define MaxSize 10        //靜態鏈表的最大長度

typedef struct{           //靜態鏈表結構型別的定義
    ELemType data;        //存盤資料元素
    int next;             //下一個元素的陣列下標
}SLinkList[MaxSize];

void testSLinkList(){
    SLinkList a;
}

也等同于：

#define MaxSize 10        //靜態鏈表的最大長度

struct Node{              //靜態鏈表結構型別的定義
    ElemType data;        //存盤資料元素
    int next;             //下一個元素的陣列下標(游標)
};

typedef struct Node SLinkList[MaxSize]; //重命名struct Node，用SLinkList定義“一個長度為MaxSize的Node型陣列;

注意：SLinkList a 強調a是靜態鏈表；struct Node a 強調a是一個Node型陣列；

3.靜態鏈表基本操作的實作

• 初始化靜態鏈表：把a[0]的next設為-1

• 查找某個位序（不是陣列下標，位序是各個結點在邏輯上的順序）的結點：從頭結點出發挨個往后遍歷結點，時間復雜度O=(n)

• 在位序為i上插入結點：① 找到一個空的結點，存入資料元素；② 從頭結點出發找到位序為i-1的結點；③修改新結點的next；④ 修改i-1號結點的next；

• 洗掉某個結點：① 從頭結點出發找到前驅結點；② 修改前驅節點的游標；③ 被洗掉節點next設為-2；

2.3.9 順序表和鏈表的比較

1.邏輯結構

• 順序表和鏈表都屬于線性表，都是線性結構

2.存盤結構

• 順序表：順序存盤

  • 優點：支持隨機存取，存盤密度高
  • 缺點：大片連續空間分配不方便，改變容量不方便

• 鏈表：鏈式存盤

  • 優點：離散的小空間分配方便，改變容量方便
  • 缺點：不可隨機存取，存盤密度低

3. 基本操作 - 創建

• 順序表：需要預分配大片連續空間，若分配空間過小，則之后不方便拓展容量；若分配空間過大，則浪費記憶體資源；

• 靜態分配：靜態陣列，容量不可改變

• 動態分配：動態陣列，容量可以改變，但是需要移動大量元素，時間代價高（malloc(),free()）

• 鏈表：只需要分配一個頭結點或者只宣告一個頭指標

4. 基本操作 - 銷毀

• 順序表：修改 Length = 0

  • 靜態陣列——系統自動回收空間

typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
}SeqList; 

• 動態分配：動態陣列——需要手動free()

//創
L.data = (ELemType *)malloc(sizeof(ElemType) *InitSize)
//銷
free(L.data);

//！malloc() 和 free() 必須成對出現

5.基本操作-增/刪

• 順序表：插入/洗掉元素要將后續元素后移/前移；時間復雜度=O(n)，時間開銷主要來自于移動元素；

• 鏈表：插入/洗掉元素只需要修改指標；時間復雜度=O(n)，時間開銷主要來自查找目標元素

6.基本操作-查

• 順序表

  • 按位查找：O(1)

• 按值查找：O(n)，若表內元素有序，可在O(log2n)時間內找到

• 鏈表

  • 按位查找：O(n)
  • 按值查找：O(n)

第三章：堆疊和佇列

3.1堆疊（stack）

3.1.1堆疊的基本概念

1.堆疊的定義

• 堆疊是特殊的線性表：只允許在一端進行插入或刪- 除操作， 其邏輯結構與普通線性表相同；
• 堆疊頂（Top）：允許進行插入和洗掉的一端 （最上面的為堆疊頂元素）；
• 堆疊底（Bottom）：固定的，不允許進行插入和洗掉的一端 （最下面的為堆疊底元素）；
• 空堆疊：不含任何元素的空表；
• 特點：后進先出（后進堆疊的元素先出堆疊）；
• 缺點：堆疊的大小不可變，解決方法——共享堆疊；

2.堆疊的基本操作

"創建&銷毀"

• InitStack(&S) 初始化堆疊：構造一個空堆疊S，分配記憶體空間；
• DestroyStack(&S) 銷毀堆疊：銷毀并釋放堆疊S所占用的記憶體空間；

"增&刪"

• Push(&S, x) 進堆疊：若堆疊S未滿，則將x加入使其成為新堆疊頂；
• Pop(&S, &x) 出堆疊：若堆疊S非空，則彈出（洗掉）堆疊頂元素，并用x回傳；
  "查&其他"
• GetTop(S, &x) 讀取堆疊頂元素：若堆疊S非空，則用x-回傳堆疊頂元素；（堆疊的使用場景大多只訪問堆疊頂元素）；
• StackEmpty(S) 判空： 斷一個堆疊S是否為空，若S為空，則回傳true,否則回傳false；

3.1.2 堆疊的順序存盤

1.順序堆疊的定義

#define MaxSize 10         //定義堆疊中元素的最大個數

typedef struct{
    ElemType data[MaxSize];       //靜態陣列存放堆疊中元素
    int top;                      //堆疊頂元素
}SqStack;

void testStack(){
    SqStack S;       //宣告一個順序堆疊(分配空間)
                     //連續的存盤空間大小為 MaxSize*sizeof(ElemType)
}

2.順序堆疊的基本操作

#define MaxSize 10         //定義堆疊中元素的最大個數

typedef struct{
    ElemType data[MaxSize];       //靜態陣列存放堆疊中元素
    int top;                      //堆疊頂元素
}SqStack;

//初始化堆疊
void InitStack(SqStack &S){
    S.top = -1;                   //初始化堆疊頂指標
}

//判堆疊空
bool StackEmpty(SqStack S){
    if(S.top == -1)      //堆疊空
        return true;
    else                 //堆疊不空
        return false;
}

//新元素進堆疊
bool Push(SqStack &S, ElemType x){
    if(S.top == MaxSize - 1)        //堆疊滿
        return false;
    
    S.top = S.top + 1;    //指標先加1
    S.data[S.top] = x;    //新元素入堆疊

    /*
    S.data[++S.top] = x;
    */
    return true;
}

//出堆疊
bool Pop(SqStack &x, ElemType &x){
    if(S.top == -1)          //堆疊空
        return false;
    
    x = S.data[S.top];       //先出堆疊
    S.top = S.top - 1;       //堆疊頂指標減1
    return true;

    /*
    x = S.data[S.top--];
    */

    //只是邏輯上的洗掉，資料依然殘留在記憶體里

}

//讀堆疊頂元素
bool GetTop(SqStack S, ElemType &x){
    if(S.top == -1)
        return false;
    
    x = S.data[S.top];      //x記錄堆疊頂元素
    return true; 
}


void testStack(){
    SqStack S;       //宣告一個順序堆疊(分配空間)
    InitStack(S);
    //...
}

**注意：**也可以初始化時定義 S.top = 0 ：top指標指向下一個可以插入元素的位置(堆疊頂元素的后一個位置)；

• 進堆疊操作 ：堆疊不滿時，堆疊頂指標先加1，再送值到堆疊頂元素，S.data[S.top++] = x;
• 出堆疊操作：堆疊非空時，先取堆疊頂元素值，再將堆疊頂指標減1，`x = S.data[–S.top];
• 堆疊空條件：S.top==-1
• 堆疊滿條件：S.top==MaxSize-1
• 堆疊長：S.top+1

3.共享堆疊
**定義：**利用堆疊底位置相對不變的特性，可以讓兩個順序堆疊共享一個一維陣列空間，將兩個堆疊的堆疊底 分別設定在共享空間的兩端，兩個堆疊頂向共享空間的中間延伸，

• 存取資料的時間復雜度均為O（1）

#define MaxSize 10         //定義堆疊中元素的最大個數

typedef struct{
    ElemType data[MaxSize];       //靜態陣列存放堆疊中元素
    int top0;                     //0號堆疊堆疊頂指標
    int top1;                     //1號堆疊堆疊頂指標
}ShStack;

//初始化堆疊
void InitSqStack(ShStack &S){
    S.top0 = -1;        //初始化堆疊頂指標
    S.top1 = MaxSize;   
}

堆疊滿條件：top1-top0=1

3.1.3堆疊的鏈式存盤

1.定義：采用鏈式存盤的堆疊稱為鏈堆疊，
2.優點：鏈堆疊的優點是便于多個堆疊共享存盤空間和提高其效率，且不存在堆疊滿上溢的情況，
3.特點：

• 進堆疊和出堆疊都只能在堆疊頂一端進行(鏈頭作為堆疊頂)
• 鏈表的頭部作為堆疊頂，意味著：
  1. 在實作資料"入堆疊"操作時，需要將資料從鏈表的頭部插入；
  2. 在實作資料"出堆疊"操作時，需要洗掉鏈表頭部的首元節點；
  因此，鏈堆疊實際上就是一個只能采用頭插法插入或洗掉資料的鏈表;
  堆疊的鏈式存盤結構可描述為：

typedef struct Linknode{
    ElemType data;              //資料域
    struct Linknode *next;      //指標域
}*LiStack;                      //堆疊型別的定義

4. 堆疊的基本操作：

• 初始化
• 進堆疊
• 出堆疊
• 獲取堆疊頂元素
• 判空、判滿
  帶頭結點的鏈堆疊基本操作：

#include<stdio.h>

struct Linknode{
    int data;             //資料域
    Linknode *next;       //指標域
}Linknode,*LiStack;   

typedef Linknode *Node;   //結點結構體指標變數
typedef Node List;        //結點結構體頭指標變數

//1. 初始化
void InitStack(LiStack &L){   //L為頭指標
    L = new Linknode; 
    L->next = NULL;
}

//2.判堆疊空
bool isEmpty(LiStack &L){
    if(L->next == NULL){
        return true;
    }
    else
        return false;
}

//3. 進堆疊(：鏈堆疊基本上不會出現堆疊滿的情況)
void pushStack(LiStack &L, int x){
    Linknode s;          //創建存盤新元素的結點
    s = new Linknode;
    s->data = x;

    //頭插法
    s->next = L->next;
    L->next = s;
}

//4.出堆疊
bool popStack(LiStack &L, int &x){
    Linknode s;
    if(L->next == NULL) //堆疊空不能出堆疊
        return false;
    
    s = L->next;
    x = s->data;
    L->next = L->next->next;
    delete(s);

    return true;
}

不帶頭結點的鏈堆疊基本操作：

#include<stdio.h>

struct Linknode{
    int data;             //資料域
    Linknode *next;       //指標域
}Linknode,*LiStack;   

typedef Linknode *Node;   //結點結構體指標變數
typedef Node List;        //結點結構體頭指標變數

//1.初始化 
void initStack(LiStack &L){
    L=NULL;
}

//2.判堆疊空
bool isEmpty(LiStack &L){
    if(L == NULL)
        return true;
    else
        teturn false;
}

//3.進堆疊
void pushStack(LiStack &L, int x){
    Linknode s;          //創建存盤新元素的結點
    s = new Linknode;

    s->next = L;
    L = s;
}

//4.出堆疊
bool popStack(LiStack &L, int &x){
    Linknode s; 
    if(L = NULL)     //堆疊空不出堆疊
        return false;

    s = L;
    x = s->data;
    L = L->next;
    delete(s);
    
    return true;
}

3.2佇列（Queue）

3.2.1佇列的基本概念

1.定義：佇列（Queue）簡稱隊，是一種操作受限的線性表，只允許在表的一端進行插入，而在表的另一端進行洗掉，
2.特點

• 佇列是操作受限的線性表，只允許在一端進行插入 (入隊)，另一端進行洗掉 (出隊)
• 操作特性：先進先出 FIFO
• 隊頭：允許洗掉的一端
• 隊尾：允許插入的一端
• 空佇列：不含任何元素的空表
  3.佇列的基本操作
  "創建&銷毀"
• InitQueue(&Q): 初始化佇列，構造一個空串列Q
• DestroyQueue(&Q): 銷毀佇列，并釋放佇列Q所占用的記憶體空間
  "增&刪"
• EnQueue(&Q, x): 入隊，若佇列Q未滿，將x加入，使之成為新的隊尾
• DeQueue(&Q, &x): 出隊，若佇列Q非空，洗掉隊頭元素，并用x回傳
  "查&其他"
• GetHead(Q,&x): 讀隊頭元素，若佇列Q非空，則將隊頭元素賦值給x
• QueueEmpty(Q): 判佇列空，若佇列Q為空，則回傳

3.2.2佇列的順序存盤結構

• 隊頭指標：指向隊頭元素
• 隊尾指標：指向隊尾元素的下一個位置

1. 佇列存盤的基本操作

//佇列的順序存盤型別
# define MaxSize 10;     //定義佇列中元素的最大個數
typedef struct{
    ElemType data[MaxSize];   //用靜態陣列存放佇列元素
                              //連續的存盤空間，大小為——MaxSize*sizeof(ElemType)
    int front, rear;          //隊頭指標和隊尾指標
}SqQueue;

//初始化佇列
void InitQueue(SqQueue &Q){
    //初始化時，隊頭、隊尾指標指向0
    Q.rear = Q.front = 0;
}

void test{
    SqQueue Q;                //宣告一個佇列
    InitQueue(Q);
    //...
}

// 判空
bool QueueEmpty(SqQueue 0){
    if(Q.rear == Q.front)    //判空條件后
        return true;
    else 
        return false;
}

2. 回圈佇列
   定義：將回圈佇列臆造為一個環狀的空間，即把存盤佇列元素的表從邏輯上視為一個環，稱為回圈佇列，
   基本操作：

a%b == a除以b的余數

初始：Q.front = Q.rear = 0;

隊首指標進1：Q.front = (Q.front + 1) % MaxSize

隊尾指標進1：Q.rear = (Q.rear + 1) % MaxSize —— 隊尾指標后移，當移到最后一個后，下次移動會到第一個位置

佇列長度：(Q.rear + MaxSize - Q.front) % MaxSize

區分隊慷訓是隊滿的情況：
方案一: 犧牲一個單元來區分隊空和隊滿
隊尾指標的再下一個位置就是隊頭，即 (Q.rear+1)%MaxSize == Q.front

• 回圈佇列——入隊：只能從隊尾插入（判滿使用方案一）

bool EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize == Q.front)        //隊滿
        return false;
    Q.data[Q.rear] = x;                      //將x插入隊尾
    Q.rear = (Q.rear + 1) % MaxSize;         //隊尾指標加1取模

    return true;
}

• 回圈佇列——出隊：只能讓隊頭元素出隊

//出隊，洗掉一個隊頭元素，用x回傳
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //隊空報錯
        return false;  

    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize; //隊頭指標后移動

    return true;
}

• 回圈佇列——獲得隊頭元素

bool GetHead(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //隊空報錯
        return false;  

    x = Q.data[Q.front];
    return true;
}

方案二: 不犧牲存盤空間，設定size
定義一個變數 size用于記錄佇列此時記錄了幾個資料元素，初始化 size = 0，進隊成功 size++，出隊成功size--，根據size的值判斷隊滿與隊空

隊滿條件：size == MaxSize

隊空條件：size == 0

# define MaxSize 10;     
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int size;               //佇列當前長度
}SqQueue;

//初始化佇列
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
    size = 0;
}

方案三: 不犧牲存盤空間，設定tag
定義一個變數 tag，tag = 0 --最近進行的是洗掉操作；tag = 1 --最近進行的是插入操作；

每次洗掉操作成功時，都令tag = 0；只有洗掉操作，才可能導致隊空；
每次插入操作成功時，都令tag = 1；只有插入操作，才可能導致隊滿；
隊滿條件：Q.front == Q.rear && tag == 1

隊空條件：Q.front == Q.rear && tag == 0

# define MaxSize 10;     
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int tag;               //最近進行的是洗掉or插入
}SqQueue;

3.2.3佇列的鏈式存盤結構

1.定義：佇列的鏈式表示稱為鏈佇列，它實際上是一個同時帶有隊頭指標和隊尾指標的單鏈表，
佇列的鏈式存盤型別可描述為:

typedef struct LinkNode{      //鏈式佇列結點
    ElemType data;
    struct LinkNode *next;
}

typedef struct{               //鏈式佇列
    LinkNode *front, *rear;   //佇列的隊頭和隊尾指標
}LinkQueue;

2.鏈式佇列的基本操作——帶頭結點

• 初始化 & 判空

void InitQueue(LinkQueue &Q){
    //初始化時，front、rear都指向頭結點
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front -> next = NULL;
}

//判斷佇列是否為空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)     //也可用 Q.front -> next == NULL
        return true;
    else
        return false;
}

• 入隊操作

//新元素入隊 (表尾進行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申請一個新結點
    s->data = x;
    s->next = NULL;     //s作為最后一個結點，指標域指向NULL
    Q.rear->next = s;   //新結點插入到當前的rear之后
    Q.rear = s;         //表尾指標指向新的表尾
}

• 出隊操作

//隊頭元素出隊
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear)
        return false;                    //空隊
    
    LinkNode *p = Q.front->next;         //p指標指向即將洗掉的結點 (頭結點所指向的結點)
    x = p->data;
    Q.front->next = p->next;             //修改頭結點的next指標
    if(Q.rear == p)                      //此次是最后一個結點出隊
        Q.rear = Q.front;                //修改rear指標
    free(p);                             //釋放結點空間

    return true;
}

• 佇列滿的條件
  順序存盤：預分配存盤空間

鏈式存盤：一般不會隊滿，除非記憶體不足

• 計算鏈隊長度 (遍歷鏈隊)
  設定一個int length 記錄鏈式佇列長度

• 初始化 & 判空

• 入隊操作

//新元素入隊 (表尾進行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申請一個新結點
    s->data = x;
    s->next = NULL;

    //第一個元素入隊時需要特別處理
    if(Q.front = NULL){            //在空佇列中插入第一個元素
        Q.front = s;               //修改隊頭隊尾指標
        Q.rear = s;
    }else{
        Q.rear->next = s;           //新結點插入到rear結點之后
        Q.rear = s;                 //修改rear指標指向新的表尾結點
    }
}

3.2.4雙端佇列

1.定義：雙端佇列是指允許兩端都可以進行入隊和出隊操作的佇列

• 雙端佇列允許從兩端插入、兩端洗掉的線性表；
• 如果只使用其中一端的插入、洗掉操作，則等同于堆疊；
• 輸入受限的雙端佇列：允許一端插入，兩端洗掉的線性表；
• 輸出受限的雙端佇列：允許兩端插入，一端洗掉的線性表；

3.3堆疊的應用

3.3.1堆疊在括號匹配中的應用

用堆疊實作括號匹配

• ((())) 最后出現的左括號最先被匹配 (堆疊的特性—LIFO);

• 遇到左括號就入堆疊;

• 遇到右括號，就“消耗”一個左括號 (出堆疊);
  匹配失敗情況：

• 掃描到右括號且堆疊空，則該右括號單身;

• 掃描完所有括號后，堆疊非空，則該左括號單身;

• 左右括號不匹配;

代碼：

#define MaxSize 10   

typedef struct{
    char data[MaxSize];
    int top;
} SqStack;

//初始化堆疊
InitStack(SqStack &S)

//判斷堆疊是否為空
bool StackEmpty(SqStack &S)

//新元素入堆疊
bool Push(SqStack &S, char x)

//堆疊頂元素出堆疊，用x回傳
bool Pop(SqStack &S, char &x)



bool bracketCheck(char str[], int length){
    SqStack S;      //宣告
    InitStack(S);   //初始化堆疊

    for(int i=0; i<length; i++){
        if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
            Push(S, str[i]);       //掃描到左括號，入堆疊
        }else{
            if(StackEmpty(S))      //掃描到右括號，且當前堆疊空
                return false;      //匹配失敗
            
            char topElem;          //存盤堆疊頂元素
            Pop(S, topElem);       //堆疊頂元素出堆疊

            if(str[i] == ')' && topElem != '(' )
                return false;

            if(str[i] == ']' && topElem != '[' )
                return false;

            if(str[i] == '}' && topElem != '{' )
                return false;       
        }
    }

    StackEmpty(S);                //堆疊空說明匹配成功
}

3.3.2堆疊在運算式求值中的應用

1. 中綴運算式 (需要界限符)
運算子在兩個運算元中間:

① a + b
② a + b - c
③ a + b - c*d
④ ((15 ÷ (7-(1+1)))×3)-(2+(1+1))
⑤ A + B × (C - D) - E ÷ F

2. 后綴運算式 (逆波蘭運算式)
運算子在兩個運算元后面:

① a b +
② ab+ c - / a bc- +
③ ab+ cd* -
④ 15 7 1 1 + - ÷ 3 × 2 1 1 + + -
⑤ A B C D - × + E F ÷ - (機算結果)
  A B C D - × E F ÷ - + (不選擇)

中綴運算式轉后綴運算式-手算
步驟1： 確定中綴運算式中各個運算子的運算順序

步驟2： 選擇下一個運算子，按照[左運算元 右運算元 運算子]的方式組合成一個新的運算元

步驟3： 如果還有運算子沒被處理，繼續步驟2

“左優先”原則: 只要左邊的運算子能先計算，就優先算左邊的 (保證運算順序唯一)；

中綴：A + B - C * D / E + F
       ①   ④   ②   ③   ⑤     
后綴：A B + C D * E / - F +

重點：中綴運算式轉后綴運算式-機算
初始化一個堆疊，用于保存暫時還不能確定運算順序的運算子，從左到右處理各個元素，直到末尾，可能遇到三種情況:

遇到運算元: 直接加入后綴運算式，
遇到界限符: 遇到 ‘(’ 直接入堆疊; 遇到 ‘)’ 則依次彈出堆疊內運算子并加入后綴運算式，直到彈出 ‘(’ 為止，注意: '(' 不加入后綴運算式，
遇到運算子: 依次彈出堆疊中優先級高于或等于當前運算子的所有運算子，并加入后綴運算式，若碰到 ‘(’ 或堆疊空則停止，之后再把當前運算子入堆疊，
按上述方法處理完所有字符后，將堆疊中剩余運算子依次彈出，并加入后綴運算式，

后綴運算式的計算—手算:
從左往右掃描，每遇到一個運算子，就讓運算子前面最近的兩個運算元執行對應的運算，合體為一個運算元；

注意： 兩個運算元的左右順序

重點：后綴運算式的計算—機算
用堆疊實作后綴運算式的計算（堆疊用來存放當前暫時不能確定運算次序的運算元）

步驟1: 從左往后掃描下一個元素，直到處理完所有元素;

步驟2: 若掃描到運算元，則壓入堆疊，并回到步驟1;否則執行步驟3;

步驟3: 若掃描到運算子，則彈出兩個堆疊頂元素，執行相應的運算，運算結果壓回堆疊頂，回到步驟1;

注意: 先出堆疊的是“右運算元”

3.前綴運算式 (波蘭運算式)
運算子在兩個運算元前面:

① + a b
② - +ab  c
③ - +ab *cd

中綴運算式轉前綴運算式—手算
步驟1： 確定中綴運算式中各個運算子的運算順序

步驟2： 選擇下一個運算子，按照[運算子 左運算元 右運算元]的方式組合成一個新的運算元

步驟3： 如果還有運算子沒被處理，就繼續執行步驟2

“右優先”原則: 只要右邊的運算子能先計算，就優先算右邊的;

中綴：A + B * (C - D) - E / F
       ⑤   ③    ②    ④   ①
前綴：+ A - * B - C D / E F

前綴運算式的計算—機算
用堆疊實作前綴運算式的計算

步驟1: 從右往左掃描下一個元素，直到處理完所有元素；

步驟2: 若掃描到運算元則壓入堆疊，并回到步驟1，否則執行步驟3

步驟3: 若掃描到運算子，則彈出兩個堆疊頂元素，執行相應運算，運算結果壓回堆疊頂，回到步驟1；

注意: 先出堆疊的是“左運算元”

4.中綴運算式的計算(用堆疊實作)
兩個演算法的結合： 中綴轉后綴 + 后綴運算式的求值

初始化兩個堆疊，運算元堆疊 和運算子堆疊

若掃描到運算元，壓人運算元堆疊

若掃描到運算子或界限符，則按照“中綴轉后綴”相同的邏輯壓入運算子堆疊 (期間也會彈出運算子，每當彈出一個運算子時，就需要再彈出兩個運算元堆疊的堆疊項元素并執行相應運算，運算結果再壓回運算元堆疊)

3.3.3堆疊在遞回中的應用

函式呼叫的特點：最后被呼叫的函式最先執行結束(LIFO)

函式呼叫時，需要用一個堆疊存盤：

• 呼叫回傳地址
• 實參
• 區域變數

遞回呼叫時，函式呼叫堆疊稱為 “遞回作業堆疊”:

• 每進入一層遞回，就將遞回呼叫所需資訊壓入堆疊頂；
• 每退出一層遞回，就從堆疊頂彈出相應資訊；

**缺點：**太多層遞回可能回導致堆疊溢位；

適合用“遞回”演算法解決：可以把原始問題轉換為屬性相同，但規模較小的問題；

3.4特殊矩陣的壓縮存盤

3.4.1陣列的存盤結構

1.一維陣列

Elemtype a[10];

各陣列元素大小相同，物理上連續存放；

起始地址：LOC

陣列下標：默認從0開始！

陣列元素 a[i] 的存放地址 = LOC + i × sizeof(ElemType)

2.二維陣列

Elemtype b[2][4]; //2行4列的二維陣列

行優先/列優先存盤優點：實作隨機存盤

起始地址：LOC

M行N列的二維陣列 b[M][N] 中，b[i][j]的存盤地址：

行優先存盤: LOC + (i×N + j) × sizeof(ElemType)
列優先存盤：LOC + (j×M + i) × sizeof(ElemType)

3.4.2普通矩陣的存盤

二維陣列存盤：

• 描述矩陣元素時，行、列號通常從1開始；
• 描述陣列時，通常下標從 0 開始；

3.4.3特殊矩陣的存盤

特殊矩陣——壓縮存盤空間（只存有用的資料）

1. 對稱矩陣(方陣)

2. 三角矩陣(方陣)

3. 三對角矩陣(方陣)

4. 稀疏矩陣

• 順序存盤——三元組

• 鏈式存盤——十字鏈表法

第四章：串

4.1串的定義和實作

4.1.1串的定義

1. 串: 零個或多個字符組成的有限序列，如 S = 'iPhone 11 Pro Max?'；
2. 串名：S是串名；
3. 串的長度：串中字符的個數n；
4. 空串：n=0時的串；
5. 子串：串中任意多個連續的字符組成的子序列稱為該串的子串；
6. 主串：包含子串的串；
7. 字符在主串中的位置：某個字符在串中的序號（從1開始）；
8. 子串在主串中的位置：子串的第一個字符在主串中的位置；
9. 空串 V.S 空格串：
   M = ‘’ 是空串；
   N = ’ ’ 是空格串；
10. 串 V.S 線性表：
    串是特殊的線性表，資料元素之間呈線性關系（邏輯結構相似）；
    串的資料物件限定為字符集：中文字符、英文字符、數字字符、標點字符…
    串的基本操作，如增刪改除通常以子串為操作物件

4.1.2串的基本操作

假設有串 T = '', S = 'iPhone 11 Pro Max?', W = 'Pro'

• StrAssign(&T, chars): 賦值操作，把串T賦值為chars；
• StrCopy(&T, S): 復制操作，把串S復制得到串T
• StrEmpty(S): 判空操作，若S為空串，則回傳TRUE，否則回傳False；
• StrLength(S): 求串長，回傳串S的元素個數；
• ClearString(&S): 清空操作，將S清為空串；
• DestroyString(&S): 銷毀串，將串S銷毀——回收存盤空間；
• Concat(&T, S1, S2): 串聯聯接，用T回傳由S1和S2聯接而成的新串———可能會導致存盤空間的擴展；
  例：

Concat(&T, S, W)

T = ‘iPhone 11 Pro Max?Pro’

• SubString(&Sub, S, pos, len): 求子串，用Sub回傳串S的第pos個字符起長度為len的子串；

SubString(&T, S, 4, 6)

T = ‘one 11’

• Index(S, T): 定位操作，若主串S中存在與串T值相同的子串，則回傳它再主串S中第一次出現的位置，否則函式值為0；
• StrCompare(S, T): 串的比較操作，參照英文詞典排序方式；若S > T,回傳值>0; S = T,回傳值=0 (需要兩個串完全相同) ; S < T,回傳值<0;

4.1.3串的存盤結構

1定長順序存盤表示

#define MAXLEN 255   //預定義最大串長為255

typedef struct{
    char ch[MAXLEN];   //靜態陣列實作（定長順序存盤）
                       //每個分量存盤一個字符
                       //每個char字符占1B
    int length;        //串的實際長度
}SString;

• 串長的兩種表示法：

• 方案一：用一個額外的變數length來存放串的長度（保留ch[0]）；

• 方案二：用ch[0]充當length；
  優點：字符的位序和陣列下標相同；

• 方案三：沒有length變數，以字符’\0’表示結尾（對應ASCII碼的0）；
  缺點：需要從頭到尾遍歷；

• **方案四——最終使用方案：**ch[0]廢棄不用，宣告int型變數length來存放串的長度（方案一與方案二的結合）

• 基本操作實作（基于方案四）

#define MAXLEN 255

typedef struct{
    char ch[MAXLEN];   
    int length;       
}SString;

// 1. 求子串
bool SubString(SString &Sub, SString S, int pos, int len){
    //子串范圍越界
    if (pos+len-1 > S.length)
        return false;
    
    for (int i=pos; i<pos+len; i++)
        Sub.cn[i-pos+1] = S.ch[i];
    
    Sub.length = len;

    return true;
}

// 2. 比較兩個串的大小
int StrCompare(SString S, SString T){
    for (int i; i<S.length && i<T.length; i++){
        if(S.ch[i] != T.ch[i])
            return S.ch[i] - T.ch[i];
    }
    //掃描過的所有字符都相同，則長度長的串更大
    return S.length - T.length;
}

// 3. 定位操作
int Index(SString S, SString T){
    int i=1;
    n = StrLength(S);
    m = StrLength(T);
    SString sub;        //用于暫存子串

    while(i<=n-m+1){
        SubString(Sub,S,i,m);
        if(StrCompare(Sub,T)!=0)
            ++i;
        else 
            return i;    // 回傳子串在主串中的位置
    }
    return 0;            //S中不存在與T相等的子串
}

2.堆分配存盤表示

//動態陣列實作
typedef struct{
    char *ch;           //按串長分配存盤區，ch指向串的基地址
    int length;         //串的長度
}HString;

HString S；
S.ch = (char *) malloc(MAXLINE * sizeof(char)); //基地址指標指向連續空間的起始位置
                                                //malloc()需要手動free()
S.length;

3.串的鏈式存盤

typedef struct StringNode{
    char ch;           //每個結點存1個字符
    struct StringNode *next;
}StringNode, * String;

問題：存盤密度低，每個字符1B，每個指標4B；
解決方案：每一個鏈表的結點存盤多個字符——每個結點稱為塊——塊鏈結構

typedef struct StringNode{
    char ch[4];           //每個結點存多個個字符
    struct StringNode *next;
}StringNode, * String;

結合鏈表思考優缺點

• 存盤分配角度：鏈式存盤的字串無需占用連續空間，存盤空間分配更靈活；
• 操作角度：若要在字串中插入或洗掉某些字符，則順序存盤方式需要移動大量字符，而鏈式存盤不用；
• 若要按位序查找字符，則順序存盤支持隨機訪問，而鏈式存盤只支持順序訪問；

4.2串的模式匹配

模式匹配：子串的定位操作稱為串的模式，它求的是子串（常稱模式串）在主串中的位置，

4.2.1樸素模式匹配演算法

int Index(SString S, SString T){
    int i=1;                //掃描主串S
    int j=1;                //掃描模式串T
    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;
}

時間復雜度分析：

• 主串長度為n，模式串長度為m
  最多比較n-m+1個子串
  最壞時間復雜度 = O(nm)
  每個子串都要對比m個字符(對比到最后一個字符才匹配不上)，共要對比n-m+1個子串，復雜度 = O((n-m+1)m) = O(nm - m^2 + m) = O(nm)
  PS:大多數時候，n>>m
  最好時間復雜度 = O(n)
  每個子串的第一個字符就匹配失敗，共要對比n-m+1個子串，復雜度 = O(n-m+1) = O(n)

4.2.2改進的模式匹配演算法——KMP演算法

• 不匹配的字符之前，一定是和模式串一致的；
• 根據模式串T，求出next陣列（只與模式串有關，與主串無關），利用next陣列進行匹配，當匹配失敗時，主串的指標 i 不再回溯！
  next陣列是根據子串求出來的，當前面的字串已知時如果有重復的，從當前的字符匹配即可，

1. 求next陣列

• 作用：當模式串的第j個字符失配時，從模式串的第next[j]繼續往后匹配;
• 對于任何模式串，當第1個字符不匹配時，只能匹配下一個子串，因此，next[1] = 0——表示模式串應右移一位，主串當前指標后移一位，再和模式串的第一字符進行比較；
• 對于任何模式串，當第2個字符不匹配時，應嘗試匹配模式串的第一個字符，因此，next[2] = 0;
  例：對于串 T = 'abaabc'
  

2. 利用next陣列進行模式匹配

int Index_KMP(SString S, SString T, int next[]){
    int i=1;     //主串
    int j=1;     //模式串
    while（i<S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){      //第一個元素匹配失敗時
            ++j;
            ++i;         //繼續比較后繼字符
        }
        else
            j=next[j]   //模式串向右移動
    }
    if(j>T.length)
        return i-T.length; //匹配成功
}

3. 時間復雜度分析

• 求next陣列時間復雜度 = O(m)
• 模式匹配程序最壞時間復雜度 = O(n)
• KMP演算法的最壞時間復雜度 = O(m+n)

第五章：樹

5.1樹的基本概念

5.1.1樹的定義

樹是n個結點的有限集，

• 空樹
• 根結點、分支結點、葉子結點
• 非空樹的特性
• 子樹

5.1.2基本術語

1. 結點之間的關系描述
   1. 祖先、子孫、雙親、兄弟…結點
   2. 路徑、路徑長度
2. 結點、樹的屬性描述
   1. 結點的層次（深度）——從上往下
   2. 結點的高度——從下往上
   3. 樹的高度——總共多少層
   4. 結點的度——有幾個孩子
   5. 樹的度——各結點的度的最大值
3. 有序樹、無序樹
4. 森林

5.1.3樹的性質

1. 樹中的結點數等于所有結點的度數之和加1，
2. 度為m的樹第i層上至多有m^i-1個結點
3. 度為m的數、m叉數的區別
   

5.2二叉樹的概念

5.2.1 二叉樹的定義與特性

1. 二叉樹有左右之分，次序不能顛倒

5.2.2幾種特殊的二叉樹

1. 滿二叉樹
2. 完全二叉樹
3. 二叉排序樹
4. 平衡二叉樹

5.2.3二叉樹的存盤結構

1. 順序存盤
   二叉樹的順序存盤中，一定要把二叉樹的結點編號與完全二叉樹對應起來；

#define MaxSize 100

struct TreeNode{
   ElemType value; //結點中的資料元素
   bool isEmpty;   //結點是否為空
}

main(){
   TreeNode t[MaxSize];
   for (int i=0; i<MaxSize; i++){
      t[i].isEmpty = true;
   }
}

2. 鏈式存盤

//二叉樹的結點

struct ElemType{
   int value;
};

typedef struct BiTnode{
   ElemType data;          //資料域
   struct BiTNode *lchild, *rchild; //左、右孩子指標
}BiTNode, *BiTree;

//定義一棵空樹
BiTree root = NULL;

//插入根節點
root = (BiTree) malloc (sizeof(BiTNode));
root -> data = {1};
root -> lchild = NULL;
root -> rchild = NULL;

//插入新結點
BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
p -> data = {2};
p -> lchild = NULL;
p -> rchild = NULL;
root -> lchild = p; //作為根節點的左孩子

• 找到指定結點p的左/右孩子；
• 找到指定結點p的父節點；只能從根結點開始遍歷，也可以使用三叉鏈表

typedef struct BiTnode{
   ElemType data;          //資料域
   struct BiTNode *lchild, *rchild; //左、右孩子指標
   struct BiTNode *parent;          //父節點指標
}BiTNode, *BiTree;

• n個結點的二叉鏈表共有n+1個空鏈域

5.3二叉樹的遍歷和線索二叉樹

5.3.1二叉樹的遍歷

1. 先序遍歷（根左右）

• 若二叉樹為空，不用操作
• 若二叉樹非空：
  • 訪問根節點
  • 先序遍歷左子樹
  • 先序遍歷右子樹

typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

void PreOrder(BiTree T){
   if(T!=NULL){
      visit(T);                 //訪問根結點
      PreOrder(T->lchild);      //遞回遍歷左子樹
      PreOrder(T->rchild);      //遞回遍歷右子樹
   }
}

2. 中序遍歷（左根右）

• 若二叉樹為空，不用操作
• 若二叉樹非空：
  • 先序遍歷左子樹
  • 訪問根節點
  • 先序遍歷右子樹

typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

void InOrder(BiTree T){
   if(T!=NULL){
      InOrder(T->lchild);       //遞回遍歷左子樹
      visit(T);                 //訪問根結點
      InOrder(T->rchild);       //遞回遍歷右子樹
   }
}

3. 后續遍歷（左右根）

• 若二叉樹為空，不用操作
• 若二叉樹非空：
  - 先序遍歷左子樹
  - 先序遍歷右子樹
  - 訪問根節點

typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

void PostOrder(BiTree T){
   if(T!=NULL){
      PostOrder(T->lchild);       //遞回遍歷左子樹    
      PostOrder(T->rchild);       //遞回遍歷右子樹
      visit(T);                 //訪問根結點
   }
}

4. 二叉樹的層次遍歷
   演算法思想：

• 初始化一個輔助佇列
• 根節點入隊
• 若佇列非空，則隊頭結點出隊，訪問該結點，依次將其左、右孩子插入隊尾（如果有的話）
• 重復以上操作直至佇列為空

//二叉樹的結點(鏈式存盤)
typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

//鏈式佇列結點
typedef struct LinkNode{
   BiTNode * data;
   typedef LinkNode *next;
}LinkNode;

typedef struct{
   LinkNode *front, *rear;  
}LinkQueue;

//層序遍歷
void LevelOrder(BiTree T){
   LinkQueue Q;
   InitQueue (Q);          //初始化輔助佇列
   BiTree p;
   EnQueue(Q,T);           //將根節點入隊
   while(!isEmpty(Q)){     //佇列不空則回圈
      DeQueue(Q,p);        //隊頭結點出隊
      visit(p);            //訪問出隊結點
      if(p->lchild != NULL)
         EnQueue(Q,p->lchild);   //左孩子入隊
      if(p->rchild != NULL)
         EnQueue(Q,p->rchild);   //右孩子入隊
   }
}

5. 由遍歷序列構造二叉樹

• 先序序列 + 中序序列
• 后序序列 + 中序序列
• 層序序列 + 中序序列
  key: 找到樹的根節點，并根據中序序列劃分左右子樹，再找到左右子樹根節點、

5.3.2線索二叉樹

1. 線索二叉樹的概念與作用

2. 線索二叉樹的存盤結構

• 中序線索二叉樹——線索指向中序前驅、中序后繼

//線索二叉樹結點
typedef struct ThreadNode{
   ElemType data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右線索標志
}ThreadNode, *ThreadTree;

tag == 0: 指標指向孩子

tag == 1: 指標是“線索”

• 先序線索二叉樹——線索指向先序前驅、先序后繼

• 后序線索二叉樹——線索指向后序前驅、后序后繼

3. 二叉樹的線索話

• 中序線索化

typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右線索標志
}ThreadNode, *ThreadTree;

//全域變數pre, 指向當前訪問的結點的前驅
TreadNode *pre=NULL;

void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);    //中序遍歷左子樹
        visit(T);               //訪問根節點
        InThread(T->rchild);    //中序遍歷右子樹
    }
}

void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子樹為空，建立前驅線索   
      q->lchild = pre;
      q->ltag = 1;
   }

   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驅結點的后繼線索
      pre->rtag = 1;
   }
   pre = q;
}

//中序線索化二叉樹T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始為NULL
   if(T!=NULL);{              //非空二叉樹才能進行線索化
      InThread(T);            //中序線索化二叉樹
      if(pre->rchild == NULL)
         pre->rtag=1;         //處理遍歷的最后一個結點
   }
}

• 先序線索化
  注意【轉圈】問題，當ltag==0時，才能對左子樹先序線索化

typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右線索標志
}ThreadNode, *ThreadTree;

//全域變數pre, 指向當前訪問的結點的前驅
TreadNode *pre=NULL;

//先序遍歷二叉樹，一邊遍歷一邊線索化
void PreThread(ThreadTree T){
   if(T!=NULL){
      visit(T);
      if(T->ltag == 0)         //lchild不是前驅線索
         PreThread(T->lchild);
      PreThread(T->rchild);
   }
}

void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子樹為空，建立前驅線索   
      q->lchild = pre;
      q->ltag = 1;
   }

   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驅結點的后繼線索
      pre->rtag = 1;
   }
   pre = q;
}

//先序線索化二叉樹T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始為NULL
   if(T!=NULL);{              //非空二叉樹才能進行線索化
      PreThread(T);            //先序線索化二叉樹
      if(pre->rchild == NULL)
         pre->rtag=1;         //處理遍歷的最后一個結點
   }
}

• 后序線索化

typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右線索標志
}ThreadNode, *ThreadTree;

//全域變數pre, 指向當前訪問的結點的前驅
TreadNode *pre=NULL;

//先序遍歷二叉樹，一邊遍歷一邊線索化
void PostThread(ThreadTree T){
   if(T!=NULL){
      PostThread(T->lchild);
      PostThread(T->rchild);
      visit(T);                  //訪問根節點
   }
}

void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子樹為空，建立前驅線索   
      q->lchild = pre;
      q->ltag = 1;
   }

   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驅結點的后繼線索
      pre->rtag = 1;
   }
   pre = q;
}

//先序線索化二叉樹T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始為NULL
   if(T!=NULL);{              //非空二叉樹才能進行線索化
      PostThread(T);            //后序線索化二叉樹
      if(pre->rchild == NULL)
         pre->rtag=1;         //處理遍歷的最后一個結點
   }
}

4. 線索二叉樹中找前驅、后繼

• 中序線索二叉樹找中序后繼：在中序線索二叉樹中找到指定節點 *p 的中序后繼 next

若 p->rtag == 1, 則 next = p->rchild;

若 p->rtag == 0, 則 p 必有右孩子, 則 next = p的右子樹中最左下結點;

//1. 找到以P為根的子樹中，第一個被中序遍歷的結點
ThreadNode *Firstnode(ThreadNode *p){
   //回圈找到最左下的結點（不一定是葉結點）
   while(p->ltag == 0)
      p=p->lchild;
   return p;
}

//2. 在中序線索二叉樹中找到結點p的后繼結點
ThreadNode *Nextnode(ThreadNode *p){
   //右子樹最左下結點
   if(p->rtag==0)
      return Firstnode(p->rchild);
   else 
      return p->rchild; //rtag==1，直接回傳后繼線索
}

//3. 對中序線索二叉樹進行中序遍歷
void Inorder(ThreadNode *T){            //T為根節點指標
   for(ThreadNode *p = Firstnode(T); p!=NULL; p = Nextnode(p))
      visit(p);
}

• 先序線索二叉樹找先序后繼：在先序線索二叉樹中找到指定節點 *p 的先序后繼 next

若 p->rtag == 1, 則 next = p->rchild; 若 p->rtag == 0, 則 p 必有右孩子（左孩子不知道）

case1: 若p有左孩子 ——— 根 左 右 / 根 (根 左 右) 右

case2: 若p沒有左孩子 ——— 根 右 / 根 (*根 *左 右)

• 先序線索二叉樹找先序前驅：在先序線索二叉樹中找到指定節點 *p 的先序前驅pre

若 p->ltag == 1, 則 next = p->lchild;

若 p->ltag == 0, 則 p
必有左孩子，但是先序遍歷中，左右子樹的結點只可能是根的后繼，不可能是前驅，所以不能從左右孩子里尋找p的先序前驅，（除非從頭開始遍歷/三叉鏈表

case1: 如果能夠找到p的父節點，且p是左孩子 —— p的父節點就是p的前驅；

case2: 如果能夠找到p的父節點，且p是右孩子，且其左兄弟為空 —— p的父節點就是p的前驅；

case3: 如果能夠找到p的父節點，且p是右孩子，且其左兄弟非空 ——
p的前驅為左兄弟子樹中最后一個被先序遍歷到的結點（根節點出發，先往右，右沒有往左，找到最下一層的結點）；

case4: p沒有父節點，即p為根節點，則p沒有先序前驅

• 后序線索二叉樹找后序前驅：在后序線索二叉樹中找到指定節點 *p 的后序前驅pre

若 p->ltag == 1, 則 next = p->lchild;

若 p->ltag == 0, 則 p 必有左孩子（不知道有沒有右孩子）

case1: 若p有右孩子 ——— 左 右 根 / 左 (左 右 根) 根

case2: 若p沒有右孩子 ——— 左 根 （左子樹按后序遍歷，最后一個結點，p的左孩子）

• 后序線索二叉樹找后序后繼：在后序線索二叉樹中找到指定節點 *p 的后序后繼next

若 p->rtag == 1, 則 next = p->rchild;

若 p->rtag == 0, 則 p 必有右孩子, 左孩子不知道, 但是在后序遍歷中，左右子樹中的結點只有可能是根的前驅，而不可能是根的后繼，所以找不到后繼，（除非從頭開始遍歷/三叉鏈表

case1: 如果能找到p的父節點，且p是右孩子 —— p的父節點即為其后繼

case2: 如果能找到p的父節點，且p是左孩子，其右兄弟為空 —— p的父節點即為其后繼

case3: 如果能找到p的父節點，且p是左孩子，其右兄弟非空 —— p的后繼為其右兄弟子樹中第一個被后序遍歷的結點；

case4: p沒有父節點，即p為根節點，則p沒有后序后繼；

5.4樹、森林

5.4.1樹的存盤結構

1. 雙親表示法(順序存盤)：每個結點中保存指向雙親的指標

#define MAX_TREE_SIZE 100  //樹中最多結點數

typedef struct{      //樹的結點定義
   ElemType data; 
   int parent;      //雙親位置域
}PTNode;

typedef struct{                   //樹的型別定義
   PTNode nodes[MAX_TREE_SIZE];   //雙親表示
   int n;                         //結點數
}PTree;

增：新增資料元素，無需按邏輯上的次序存盤；（需要更改結點數n）
刪（葉子結點）：① 將偽指標域設定為-1；②用后面的資料填補；（需要更改結點數n）
查詢：①優點-查指定結點的雙親很方便；②缺點-查指定結點的孩子只能從頭遍歷，空資料導致遍歷更慢；

2. 孩子表示法(順序+鏈式)

struct CTNode{
   int child;    //孩子結點在陣列中的位置
   struct CTNode *next;    // 下一個孩子
};

typedef struct{
   ElemType data;
   struct CTNode *firstChild;    // 第一個孩子
}CTBox;

typedef struct{
   CTBox nodes[MAX_TREE_SIZE];
   int n, r;   // 結點數和根的位置
}CTree;

3. 孩子兄弟表示法（鏈式）

typedef struct CSNode{
   ElemType data;                               //資料域
   struct CSNode *firstchild, *nextsibling;     //第一個孩子和右兄弟指標, *firstchild 看作左指標，*nextsibling看作右指標
}CSNode. *CSTree;

5.4.2樹、森林與二叉樹的轉換

本質：森林中各個樹的根結點之間視為兄弟關系

5.4.3樹、森林的遍歷

1. 樹的遍歷

• 先根遍歷：若樹非空，先訪問根結點，再依次對每棵子樹進行先根遍歷；（與對應二叉樹的先序遍歷序列相同）

void PreOrder(TreeNode *R){
   if(R!=NULL){
      visit(R);    //訪問根節點
      while(R還有下一個子樹T)
         PreOrder(T);      //先跟遍歷下一個子樹
   }
}

• 后根遍歷：若樹非空，先依次對每棵子樹進行后根遍歷，最后再回傳根節點；（與對應二叉樹的中序遍歷序列相同）

void PostOrder(TreeNode *R){
   if(R!=NULL){
      while(R還有下一個子樹T)
         PostOrder(T);      //后跟遍歷下一個子樹
      visit(R);    //訪問根節點
   }
}

• 層序遍歷（佇列實作）：

若樹非空，則根結點入隊；
若佇列非空，隊頭元素出隊并訪問，同時將該元素的孩子依次入隊；
重復以上操作直至隊尾為空；

2. 森林的遍歷

• 先序遍歷：等同于依次對各個樹進行先根遍歷；也可以先轉換成與之對應的二叉樹，對二叉樹進行先序遍歷；
• 中序遍歷：等同于依次對各個樹進行后根遍歷；也可以先轉換成與之對應的二叉樹，對二叉樹進行中序遍歷；

5.5樹與二叉樹的應用

5.5.1二叉排序樹（BST）

1. 二叉排序樹的定義
   左子樹結點值<跟結點值<右子樹結點值
2. 查找操作

typedef struct BSTNode{
   int key;
   struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//在二叉排序樹中查找值為key的結點（非遞回）
//最壞空間復雜度：O(1)
BSTNode *BST_Search(BSTree T, int key){
   while(T!=NULL && key!=T->key){        //若樹慷訓等于跟結點值，則結束回圈
      if(key<T->key)       //值小于根結點值，在左子樹上查找
         T = T->lchild;
      else                  //值大于根結點值，在右子樹上查找
         T = T->rchild;
   }
   return T;
}

//在二叉排序樹中查找值為key的結點（遞回）
//最壞空間復雜度：O(h)
BSTNode *BSTSearch(BSTree T, int key){
   if(T == NULL)
      return NULL;
   if(Kry == T->key)
      return T;
   else if(key < T->key)
      return BSTSearch(T->lchild, key);
   else 
      return BSTSearch(T->rchild, key);
}

3. 插入操作

//在二叉排序樹中插入關鍵字為k的新結點（遞回）
//最壞空間復雜度：O(h)
int BST_Insert(BSTree &T, int k){
   if(T==NULL){           //原樹為空，新插入的結點為根結點
      T = (BSTree)malloc(sizeof(BSTNode));
      T->key = k;
      T->lchild = T->rchild = NULL;
      return 1;                       //插入成功
   }
   else if(K == T->key)               //樹中存在相同關鍵字的結點，插入失敗
      return 0;
   else if(k < T->key)                 
      return BST_Insert(T->lchild,k);
   else 
      return BST_Insert(T->rchild,k);
}

4. 二叉排序樹的構造

//按照str[]中的關鍵字序列建立二叉排序樹
void Crear_BST(BSTree &T, int str[], int n){
   T = NULL;                     //初始時T為空樹
   int i=0;
   while(i<n){
      BST_Insert(T,str[i]);     //依次將每個關鍵字插入到二叉排序樹中
      i++;
   }
}

5. 洗掉操作
6. 查找效率分析

查找長度：查找運算中，需要對比關鍵字的次數，反映了查找操作時間復雜度；
查找成功的平均查找長度ASL
查找失敗的平均查找長度ASL

5.5.2平衡二叉樹（AVL）

1. 平衡二叉樹的定義
   在插入和洗掉二叉樹的結點時，要保證任意結點的左右子樹的高度差的絕對值不超過1，將這樣的樹稱為平衡二叉樹，

//平衡二叉樹結點
typedef struct AVLNode{
   int key;         //資料域
   int balance;     //平衡因子
   struct AVLNode *lchild; *rchild; 
}AVLNode, *AVLTree;

2. 平衡二叉樹的插入
3. 插入新節點后如何調整“不平衡”問題
   調整最小不平衡子樹

LL: 在A結點的左孩子的左子樹中插入導致不平衡
調整： A的左孩子結點右上旋
RR: 在A結點的右孩子的右子樹中插入導致不平衡
調整： A的右孩子結點左上旋
LR: 在A結點的左孩子的右子樹中插入導致不平衡
調整： A的左孩子的右孩子，先左上旋再右上旋
RL: 在A結點的右孩子的左子樹中插入導致不平衡
調整： A的右孩子的左孩子，先右上旋再左上旋

4. 平衡二叉樹的查找與效率分析
   若樹高為h，則最壞情況下，查找一個關鍵字最多需要對比h次，即查找操作的時間復雜度不可能超過O(h);

5.5.3哈夫曼樹

1. 帶權路徑長度
2. 哈夫曼樹的定義
3. 哈夫曼樹的構造（重點）
4. 哈杜曼編碼（重點）

第六章 圖

第七章 查找

第八章 排序

8.1排序的基本概念

1. 排序：重新排串列中的元素，使表中元素滿足按關鍵字有序的程序（關鍵字可以相同）
2. 排序演算法的評價指標：時間復雜度、空間復雜度；
3. 排序演算法的穩定性：關鍵字相同的元素在排序之后相對位置不變，稱為穩定的；（選擇題考查）
   Q： 穩定的排序演算法一定比不穩定的好？
   A： 不一定，要看實際需求；
4. 排序演算法的分類：
   內部排序： 資料都在記憶體——關注如何使時間、空間復雜度更低；
   外部排序： 資料太多，無法全部放入記憶體——關注如何使時間、空間復雜度更低，如何使讀/寫磁盤次數更少；

8.2 插入排序

8.2.1直接插入排序

1. 演算法思想： 每次將一個待排序的記錄按其關鍵字大小，插入（依次對比、移動）到前面已經排好序的子序列中，直到全部記錄插入完成
2. 代碼實作：

• 不帶“哨兵”

void InsertSort(int A[], int n){    //A中共n個資料元素
    int i,j,temp;
    for(i=1; i<n; i++)
        if(A[i]<A[i-1]){    //A[i]關鍵字小于前驅
            temp = A[i];  
            for(j=i-1; j>=0 && A[j]>temp; --j)
                A[j-1] = A[j];     //所有大于temp的元素都向后挪
            A[j+1] = temp;         //復制到插入位置
        }
}

• 帶“哨兵” ，優點：不用每輪回圈都判斷j>=0

void InsertSort(int A[], int n){    //A中從1開始存盤，0放哨兵
    int i,j;
    for(i=1; i<n; i++)
        if(A[i]<A[i-1]){    
            A[0] = A[i];     //復制為哨兵
            for(j=i-1; A[0] < A[j]; --j)  //從后往前查找待插入位置
                A[j+1] = A[j];     //向后挪動
            A[j+1] = A[0];          //復制到插入位置
        }
}

3. 演算法效率分析

空間復雜度：O(1)
時間復雜度：主要來自于對比關鍵字、移動關鍵字，若有n個元素，則需要n-1躺處理
最好情況： 原本為有序，共n-1趟處理，每一趟都只需要對比1次關鍵字，不需要移動元素，共對比n-1次 —— O(n)
最差情況： 原本為逆序 —— O(n2)
平均情況： O(n2)
演算法穩定性：穩定

4. 對鏈表進行插入排序
   移動元素的次數變少了，因為只需要修改指標，不需要依次右移；
   但是關鍵字對比的次數依然是O(n2)數量級，因此整體看來時間復雜度仍然是O(n2)

8.2.2折半插入排序

1. 思路： 先用折半查找找到應該插入的位置，再移動元素；

2. 為了保證穩定性，當查找到和插入元素關鍵字一樣的元素時，應該繼續在這個元素的右半部分繼續查找以確認位置; 即當 A[mid] == A[0] 時，應繼續在mid所指位置右邊尋找插入位置

3. 當low>high時，折半查找停止，應將[low,i-1]or[high+1,i-1]內的元素全部右移，并將A[0]復制到low所指的位置；

4. 代碼實作

void InsertSort(int A[], int n){ 
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0] = A[i];                    //將A[i]暫存到A[0]
        low = 1; high = i-1;            //折半查找的范圍

        while(low<=high){               //折半查找
            mid = (low + high)/2;       //取中間點
            if(A[mid]>A[0])             //查找左半子表
                high = mid - 1;
            else                        //查找右半子表
                low = mid + 1;
        }
        
        for(j=i-1; j>high+1;--j)       //統一后移元素，空出插入位置
            A[j+1] = A[j];
        A[high+1] = A[0]
    }
}

5. 與直接插入排序相比，比較關鍵字的次數減少了，但是移動元素的次數沒有變，時間復雜度仍然是O(n2)

8.2.3希爾排序

1. 思路： 先追求表中元素的部分有序，再逐漸逼近全域有序；

2. 更適用于基本有序的排序表和資料量不大的排序表，僅適用于線性表為順序存盤的情況

3. 代碼實作：

void ShellSort(ElemType A[], int n){
    //A[0]為暫存單元
    for(dk=n/2; dk>=1; dk=dk/2)   //步長遞減（看題目要求，一般是1/2
        for(i=dk+1; i<=n; ++i)
            if(A[i]<A[i-dk]){
                A[0]=A[i];
                for(j=i-dk; j>0&&A[0]<A[j];j-=dk)
                    A[j+dk]=A[j];         //記錄后移，查找插入的位置
                A[j+dk]=A[0;]             //插入
            }
}

4. 演算法效率分析

• 空間效率：空間復雜度=O(1)
• 時間效率: 最壞情況下時間復雜度=O(n2)
• 穩定性：希爾排序是一種不穩定的排序方法

8.3 交換排序

**基于“交換”的排序：**根據序列中兩個元素關鍵字的比較結果來對換這兩個記錄再序列中的位置；

8.3.1冒泡排序

1. 第一趟排序使關鍵字值最小的一個元素“冒”到最前面（其最終位置）—— 每趟冒泡的結果是把序列中最小元素放到序列的最終位置，這樣最多做n-1趟冒泡就能把所有元素排好序；

2. 為保證穩定性，關鍵字相同的元素不交換；

3. 代碼實作

//交換
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//冒泡排序
void BubbleSort(int A[], int n){   //從0開始存放
    for(int i=0; i<n-1; i++){
        bool flag = false; // 表示本趟冒泡是否發生交換的標志
        for(int j=n-1; j>i; j--) //一趟冒泡程序
            if(A[j-1]>A[j]){      //若為逆序
                swap(A[j-1],A[j]);  //交換
                flag=true;
            }
        if(flag==false)
            return;       //本趟遍歷后沒有發生交換，說明表已經有序，可以結束演算法
    }
}

4. 演算法效率分析

空間復雜度：O(1)
時間復雜度
最好情況 (有序) ：只需要一趟排序，比較次數=n-1，交換次數=0，最好時間復雜度=O(n)
最壞情況 (逆序) ：比較次數 = (n-1)+(n-2)+…+1 = n(n-1)/2 = 交換次數，最壞時間復雜度 = O(n2)，平均時間復雜度 = O(n2)
冒泡排序可以用于鏈表、順序表

8.3.2快速排序

1. 每一趟排序都可使一個中間元素確定其最終位置
2. 用一個元素（不一定是第一個）把待排序序列“劃分”為兩個部分，左邊更小，右邊更大，該元素的最終位置已確認
3. 演算法實作（重點）

//用第一個元素將待排序序列劃分為左右兩個部分
int Partition(int A[], int low, int high){
    int pivot = A[low];          //用第一個元素作為樞軸
    while(low<high){
        while(low<high && A[high]>=pivot) --high; //high所指元素大于樞軸，high左移
        A[low] = A[high];   //high所指元素小于樞軸，移動到左側

        while(low<high && A[low]<=pivot)  ++low; //low所指元素小于樞軸，low右移
        A[high] = A[low];   //low所指元素大于樞軸，移動到右側
    }
    A[low] = pivot   //樞軸元素存放到最終位置
    return low；     //回傳存放樞軸的最終位置
} 

//快速排序
void QuickSort(int A[], int low, int high){
    if(low<high)   //遞回跳出條件
        int pivotpos = Partition(A, low, high);   //劃分
        QuickSort（A, low, pivotpos - 1);    //劃分左子表
        QuickSort（A, pivotpos + 1, high);   //劃分右子表
}

3. 演算法效率分析

每一層的QuickSort只需要處理剩余的待排序元素，時間復雜度不超過O(n);

把n個元素組織成二叉樹，二叉樹的層數就是遞回呼叫的層數，n個結點的二叉樹最小高度 = ?log?n? + 1, 最大高度 = n

時間復雜度 = O(n×遞回層數) （遞回層數最大為n）

最好 = O(nlog?n) : 每次選的樞軸元素都能將序列劃分成均勻的兩部分；
最壞 = O(n2) ：序列本就有序或逆序，此時時間、空間復雜度最高；
平均時間復雜度 = O(nlog?n) （接近最好而不是最壞）
空間復雜度 = O(遞回層數)（遞回層數最小為log?n）

最好 = O(log?n)
最壞 = O(n)
若每一次選中的“樞軸”可以將待排序序列劃分為均勻的兩個部分，則遞回深度最小，演算法效率最高；

若初始序列本就有序或者逆序,則快速排序的性能最差；

快速排序演算法優化思路： 盡量選擇可以把資料中分的樞軸元素

選頭、中、尾三個位置的元素，取中間值作為樞軸元素；
隨機選一個元素作為樞軸元素；
快速排序使所有內部排序演算法中平均性能最優的排序演算法；

穩定性： 不穩定；

8.4選擇排序

思想：每一趟在待排序元素中選取關鍵字最小（或最大）的元素加入有序子序列；

8.4.1簡單選擇排序

n個元素的簡單選擇排序需要n-1趟處理；

//交換
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void SelectSort(int A[], int n){       //A從0開始
    for(int i=0; i<n-1; i++){          //一共進行n-1趟，i指向待排序序列中第一個元素
        int min = i;                   //記錄最小元素位置
        for(int j=i+1; j<n; j++)       //在A[i...n-1]中選擇最小的元素
            if(A[j]<A[min]) min = j;   //更新最小元素位置
        if(min!=i)                     
            swao(A[i],A[min]);         //交換
    }
}

3. 演算法效率分析

空間復雜度 = O(1)
無論有序、逆序、亂序，都需要n-1的處理，總共需要對比關鍵字 (n-1)+(n-2)+…+1 = n(n-2)/2 次，元素交換次數 < n-1; 時間復雜度 = O(n2)
穩定性： 不穩定
適用性： 既可以用于順序表，也可以用于鏈表；

8.4.2堆排序

1. 什么是“堆（Heap）”？
   可理解為順序存盤的二叉樹，注意

可以將堆視為一棵 完全二叉樹 (?)

可以將堆視為一棵 二叉排序樹 (?)

大根堆：完全二叉樹中，根 ≥ 左、右
小根堆：完全二叉樹中，根 ≤ 左、右

2. 如何基于“堆”進行排序

基本思路：每一趟在待排序元素中選取關鍵字最小（或最大）的元素加入有序子序列，堆頂元素的關鍵字最大或最小 （以下以大根堆為例）

① 將給定初始序列(n個元素)，建立初始大根堆：把所有非終端結點 從后往前都檢查一遍，是否滿足大根堆的要求——根 ≥ 左、右，若不滿足，則將當前結點與更大的孩子互換

在順序存盤的完全二叉樹中:

非終端結點的編號 i≤?n/2?
i 的左孩子 2i
i 的右孩子 2i+1
i 的父節點?i/2?
更小的元素“下墜”后，可能導致下一層的子樹不符合大根堆的要求，則采用相同的方法繼續往下調整 —— 小元素不斷“下墜”

② 基于大根堆進行排序：每一趟將堆頂元素加入有序子序列中，堆頂元素與待排序序列中最后一個元素交換后，即最大元素換到末尾，之后該位置就不用改變，即移出完全二叉樹(len=len-1)，把剩下的待排序元素序列再調整為大根堆；————“一趟處理”

③ 剩下最后一個元素則不需要再調整；

//對初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)   //從后往前調整所有非終端結點
        HeadAdjust(A, i, len);
}

/*將以k為根的子樹調整為大根堆
從最底層的分支結點開始調整*/
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];                      //A[0]暫存子樹的根結點
    for(int i=2*k; i<=len; i*=2){     //沿key較大的子結點向下篩選
                                      // i為當前所選根結點的左孩子
                                      //i*=2是為了判斷調整后再下一層是否滿足大根堆
        if(i<len && A[i]<A[i+1])      //判斷：當前所選根結點的左、右結點哪個更大
            i++;                      //取key較大的子結點的下標
        if(A[0] >= A[i]) 
            break;                    //篩選結束：i指向更大的子結點
        else{
            A[k] = A[i];              //將A[i]調整至雙親結點上
            k=i;                      //修改k值，以便繼續向下篩選
        }
    }
    A[k] = A[0]                       //被篩選的結點的值放入最終位置
}

//交換
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//基于大根堆進行排序
void HeapSort(int A[], int len){
    BuildMaxHeap(A, len);          //初始建堆
    for(int i=len; i>1; i--){      //n-1趟的交換和建堆程序
        swap(A[i], A[1]);          //堆頂元素和堆底元素交換
        HeadAdjust(A,1,i-1);       //把剩余的待排序元素整理成堆
    }
}

8.5歸并排序和基數排序

8.5.1 歸并排序

歸并（Merge）：把兩個或多個已經有序的序列合并成一個；

k路歸并：每選出一個元素，需對比關鍵字k-1次；

外部排序通常采用歸并排序，內部排序一般采用2路歸并；

//創建輔助陣列B
int *B=(int *)malloc(n*sizeof(int));

//A[low,...,mid],A[mid+1,...,high] 各自有序，將這兩個部分歸并
void Merge(int A[], int low, int mid, int high){
    int i,j,k;
    for(k=low; k<=high; k++)
        B[k] = A[k];           //將A中所有元素復制到B中
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B[i]<=B[j])          //為保證穩定性兩個元素相等時，優先使用靠前的那個
            A[k]=B[i++];        //將較小值復制到A中
        else
            A[k]=B[j++];
    }//for
     
    //沒有歸并完的部分復制到尾部，while只會執行一個 
    while(i<=mid)  A[k++]=B[i++];     //若第一個表未檢測完，復制
    while(j<=high) A[k++]=B[j++];     //若第二個表未檢測完，復制
}

//遞回操作
void MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;    //從中間劃分
        MergeSort(A, low, mid);    //對左半部分歸并排序
        MergeSort(A, mid+1, high); //對右半部分歸并排序
        Merge(A,low,mid,high);     //歸并
    }if
}

演算法效率分析：

歸并排序的比較次數與序列的初始狀態無關；

2路歸并的“歸并樹”——倒立的二叉樹，樹高h，歸并排序趟數m = h-1，第h層最多2^(h-1)個結點，則滿足n ≤ 2^(h-1)，即h-1 = ?log?n?; 結論: n個元素進行2路歸并排序，歸并趟數 m = ?log?n?

每趟歸并時間復雜度為O(n), 演算法總時間復雜度為O(nlog?n);

空間復雜度為O(n); (歸并排序演算法可視為本章占用輔助空間最多的排序演算法)

穩定性：歸并排序是穩定的

對于N個元素進行k路歸并排序，排序的趟數m滿足 k^m = N, m = ?logkN?

8.5.2 基數排序

演算法效率分析：

空間效率：O?, 其中r為基數，需要的輔助空間(佇列)為r；
時間效率：一共進行d趟分配收集，一趟分配需要O(n), 一趟收集需要O?, 時間復雜度為 O[d(n+r)]，且與序列的初始狀態無關
穩定性：穩定！
基數排序擅長解決的問題
①資料元素的關鍵字可以方便地拆分為d組，且d較小；
②每組關鍵字的取值范圍不大，即r較小；
③資料元素個數n較大；