itsbrqs

數據結構複習期末速成#

作者:itsbrqs  

前言#

​ 本筆記僅針對 2023 年數據結構期末考試內容進行複習總結，考點時效性與準確性不保證，由 itsbrqs 編撰整理。本筆記為 itsbrqs 為應付期末考試所作。

知識點與考點#

考點總結#

• 第一章 緒論：
  • 抽象數據類型
  • 時間複雜度
• 第二章 線性表：
  • 順序表
  • 後向單鏈表
• 第三章 堆疊和佇列
  • 堆疊和佇列的結構特徵
  • 堆疊和佇列的基本操作
• 第五章 陣列和廣義表
  • 地址計算公式
  • 三元組的存儲結構
• 第六章 樹和二叉樹
  • 二叉樹的性質
  • 二叉樹的遍歷算法及其應用
  • 遍歷二叉樹和線索二叉樹
  • 樹和森林的轉換
  • 樹和森林的遍歷算法（序列如何寫）
• 第七章 圖
  • 圖的性質
  • 圖的存儲結構
    • 鄰接矩陣
    • 鄰接表
  • 圖的遍歷
    • 書寫遍歷序列
    • 深度優先遍歷和廣度優先遍歷
  • 最小生成樹
  • 圖的應用
    • 拓撲排序
    • 關鍵路徑
    • 最短路徑

題型#

​ 選擇題五道 + 填空題五道 + 應用大題四道 + 算法書寫兩道

第一章緒論#

知識點 1 數據結構的定義#

1. 學科定義：數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關係和操作等等的學科。
2. 數據結構的定義：數據元素及其相互之間的聯繫。
3. 數據結構的簡單分類：邏輯結構和存儲結構。

知識點 2 四種基本邏輯結構#

1. 集合：數據元素之間除了 “同屬於一個集合” 的關係外，別無其它關係。

2. 線性結構：數據元素之間存在一對一的聯繫。

3. 樹形結構：數據元素之間存在一對多的聯繫。

4. 圖狀結構：數據元素之間存在多對多的聯繫。

​ 其中集合結構、樹結構、圖結構皆屬於非線性結構。

​ 非線性結構：樹、二叉樹、有向圖、無向圖、集合。

​ 線性結構：線性表、堆疊和佇列、陣列、廣義表。

知識點 3 數據#

1. 定義：在計算機領域中是指所有能輸入到計算機中並能被計算機處理的符號的總稱，是計算機程序加工的 “原料”。它包括數值、字符、圖像、聲音等。
2. 操作：輸入、輸出、排序、查找、插入、刪除。

知識點 4 數據結構的分類#

1. 邏輯結構：數據元素之間的邏輯關係、相互聯繫。

2. 物理結構（存儲結構）：數據結構在計算機中的表示。存儲結構又分成順序存儲結構和鏈式存儲結構。

知識點 5 數據存儲結構#

1. 定義：數據對象在計算機中的存儲表示稱為數據的存儲結構，也稱為物理結構。
2. 數據元素在計算機中有兩種基本的存儲結構，分別是順序存儲結構和鏈式存儲結構。

順序存儲結構

1. 定義：順序存儲結構是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係，通常借助程序設計語言的陣列類型來描述。
2. 鄰接存放，借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係。
3. 優點：佔用較少的存儲空間，存儲密度高。缺點：產生碎片現象，做插入或刪除時需要移動元素。

鏈式存儲結構#

1. 順序存儲結構要求所有的元素依次存放在一片連續的存儲空間當中，而鏈式存儲結構勿需佔用一整塊存儲空間。但為了表示節點之間的關係需要給每個節點附加指針字段，用於存放後繼元素的存儲地址，所以鏈式存儲結構通常借助於程序設計語言的指針類型來描述。
2. 非鄰接存放，借助存放元素地址的指針來表示數據元素之間的邏輯關係。
3. 優點：空間利用率高，操作簡單。缺點：佔用較多的存儲空間，數據密度低。

​ 兩種結構的關係：數據的邏輯結構和物理結構是密不可分的兩個方面，一個算法的設計取決於所選定的邏輯結構，而算法的實現依賴於所採用的存儲結構。

知識點 6 抽象數據類型#

​ 抽象數據類型一般指由用戶定義的、表示應用問題的數學模型，以及定義在這個模型上的一組操作的總稱，具體包括三部分：數據對象、數據對象上關係的集合、以及對數據對象基本操作的集合。

知識點 7 算法#

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

算法必須滿足的五個特性：

1. 有窮性

2. 確定性：對於每種情況下所應執行的操作，在算法之中都有確切的規定，不會產生二義性，使算法的執行者或閱讀者都能明確其含義及如何執行。

3. 可行性

4. 輸入

5. 輸出

知識點 8 算法的評價#

1. 正確性
2. 可讀性
3. 健壯性
4. 高效性：高效性包括時間和空間兩個方面，時間高效是指算法設計合理，執行效率高，可以用時間複雜度來衡量；空間高效是指算法佔用存儲容量合理，可以用空間複雜度來衡量。時間和空間複雜度是衡量算法的兩個主要指標。

知識點 9 時間複雜度#

​ 衡量算法效率的方法主要有兩類：事後統計法和事前估計法。事後統計法需要先將算法實現，然後測算其時間和空間開銷。這種方法的缺陷很明顯，一是必須要把算法轉換為可執行的程序，而是時空開銷的測算結果依賴於計算機的軟硬件等環境因素，這容易掩蓋算法本身的優劣。所以普遍採用的方法是事前分析估算法，通過計算算法的漸進複雜度來衡量算法的效率。

算法時間複雜度求法#

​ 尋找最深層循環次數，只需要求出最高階即可。

算法的時間複雜度分析舉例#

1. 常數階 O (1)

   Copy

   {x ++ ;}
   

2. 線性階 O (n)

   Copy

   for( int i = 0 ; i < n ; i ++ ) 
       s ++ ;
   

3. 平方階 O (n^2)

   Copy

   #冒泡排序也是平方階
   for (i = 0; i < size-1;i ++)//size-1是因為不用與自己比較，所以比的數就少一個
   	{
   		int count = 0;
   		for (j = 0; j < size-1 - i; j++)	//size-1-i是因為每一趟就會少一個數比較
   		{
   			if (arr[j] > arr[j+1])//這是升序排法，前一個數和後一個數比較，如果前數大則與後一個數換位置
   			{
   				tem = arr[j];
   				arr[j] = arr[j+1];
   				arr[j+1] = tem;
   				count = 1;
   			}
   		}
   		if (count == 0)			//如果某一趟沒有交換位置，則說明已經排好序，直接退出循環
   				break;	
   	}
   

第二章 線性表#

** 線性表：** 由 n (n≥0) 個數據特性相同的元素構成的有限序列。

線性表的存儲結構：順序存儲結構和鏈式存儲結構。

數據結構的基本運算：修改、插入、刪除、查找、排序。

知識點 10 順序存儲空間動態分配線性表#

順序表存儲結構的優缺點：

​ 優點： 邏輯相鄰，物理相鄰；可隨機存取任一元素；存儲空間使用緊湊；

​ 缺點： 插入、刪除操作需要移動大量的元素；

存儲結構#

typedef struct{
	ElemType *elem;//首地址
     int length;//當前長度
     int listsize;//當前所佔存儲容量
}

初始化#

/*算法思路
*1.空間分配
*2.判斷分配是否成功
*3.初始化其他參數
*/
status Initlist_sq(Sqlist &L){
    //分配空間
    L.elem=(ElemType)* malloc(L * sizeof(ElemType));
   //判斷分配是否成功 
    if(!L.elem) retrun -2;
   //初始化其他參數
    L.length=0;
    L.listszie=0;
    return 0;
}

插入#

/*算法思路
*1.檢查i值合法性
*2.檢查是否空間溢出及溢出空間再分配
*3.檢查再分配是否成功
*4.取插入位置元素，整體向後移位
*5.表長加1
*/
status ListInsert_sq(Sqlist* L,int i,int e){
    int* newbase,q,p;
    //檢查 i 值是否合法，是否會越界
    if(i<1||i>(L->length+1))
    	return ERROR;
	//長度超限時分配內存新空間用於存儲
	if(L->length>=L->listsize){
		newbase=(int*)realloc(L->elem,(L->listsize+LISTINCREMENT)*
		sizeof(int));
     //檢查存儲是否分配失敗
     if(!newbase)
		return (OVERFLOW);
	L->elem=newbase;
	L->listsize+=LISTINCREMENT;
	}
     q=&(L->elem[i-1]);//q 為插入位置
    if(L->length>0){
		for(p=&(L->elem[(L->length)-1]); p>=q; --p){
		*(p+1)=*p;
        }
    }
	*q=e;
	++(L->length);
	return OK;
};     

插值

q=&(L->elem[i-1]);//q 為插入位置元素
    if(L->length>0){//檢查是否為空
		for(p=&(L->elem[(L->length)-1]); p>=q; --p){
		*(p+1)=*p;//元素整體後移
        }
    }
*q=e;//插入元素

刪除#

/*算法思路
*1.檢查i值合法性
*2.取被刪除元素位置
*3.被刪除元素賦值給e
*4.取被刪除元素的元素，整體向前移位
*5.表長減1
*/
//核心代碼： 刪除移位
q=&(L->elem[i-1]);//取被刪除元素位置
*e=*p;//被刪除元素賦值給e
q=L->elem+L->length-1;//表尾
for(++p;p<=q;++p)
	*(p-1)=*p;//向前移位

知識點 11 鏈式存儲後項單鏈線性表#

單鏈表特點：

它是一種動態結構，整個存儲空間為多個鏈表共用； 不需預先分配空間； 指針佔用額外存儲空間； 不能隨機存取，查找速度慢。

存儲結構#

typedef struct LNode{
	Elemtype data;//數據域
	struct LNode *next;//指針域
}

初始化#

Status InitList_L(LNode *L){
    L->next=NULL;//頭結點next域置空非常重要
    return OK;
};

由於並未使用 c++ 引用參數而是將結構體指針傳入所以不需要申請空間。

插值#

/*算法思路
*1.取插值前結點
*2.檢查i值
*3.生成插值結點
*4.斷開老結點插入插值結點
*/
Status ListInsert_L(LNode *L,int i,Elemtype e){
    int j=0;
    LNode *p;
    p=L;
    while(p&&j<i-1){
    p=p->next;
    j++;
    }
    if(!p||j>i-1){
    return ERROR;//i值檢驗，負值或大於表長加1值
    }
    
    LNode *s;
    s=(LinkLIst) malloc(sizeof(LNode));//空間分配！！！生成插值結點
    s->data=e;
    //開始插值
    s->next=p->next;//中部插值時必須
    p->next=s;
    return OK;
};

示意圖如下：

刪除#

/*算法思路
*1.取刪除值前結點
*2.檢查i值
*3.生成刪除結點
*4.斷開老結點鏈接刪除值後結點
*5.返回刪除值，釋放刪除結點
*/
Status ListDelete_L(LNode *L,int i,Elemtype *e){
    int j=0;
    LNode *p;
    p=L;
    
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i-1){
        return ERROR;//i值檢驗，負值或大於表長加1值
    }
    
    LNode *q;
    q=(LinkLIst) malloc(sizeof(LNode));//空間分配！！！
    
    q=p->next;//獲得被刪除結點
    p->next=q->next;//越過被刪除結點實現刪除
    
    *e=q->data;
    free(q);
    return OK;
};

示意圖如下：

第三章 堆疊和佇列#

從數據結構角度來講，堆疊和佇列也是線性表，其操作是線性表操作的子集，屬操作受限 的線性表。但從數據類型的角度看，它們是和線性表大不相同的重要抽象數據類型。

知識點 12 堆疊的結構，定義與操作#

** 定義：** 限定僅在表尾進行插入或刪除操作的線性表。

結構：

typedef struct stack{ 
    int stacksize; //堆疊的容量 
    struct stack *head; //堆疊頂指針 
    struct stack *base; //堆疊底指針
}

操作：

入堆疊push口訣：堆疊指針 top “先壓後加” : S[top++]=an+1

出堆疊pop口訣：堆疊指針 top “先減後彈” : e=S[--top]

//插值 Push
Status Push(SqStack *S,SElemType e){
    if(S->top-S->base>S->stacksize){
        S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));//堆疊滿追加分配空間
        if(!S->base)return -2;//分配失敗
        S->top=S->base+S->stacksize;//堆疊頂指針移動
        S->stacksize+=STACKINCREMENT;
    }
    *(S->top)++=e;//插值之後堆疊頂指針上移，這裡實際為兩步操作
}
//刪除 Pop
Status Pop(SqStack *S,SElemType *e){
    if(S->base==S->top){
        printf("error: SqStack NULL");
        return 0;//堆疊空
    }
    *e=*(S->top-1);
    S->top--;
    return 1;
}

** 特點：** 後入先出，當表中沒有元素時稱為空堆疊。

知識點 13：佇列的結構定義和操作#

** 定義：** 只允許在表的一端（隊頭）進行插入，而在另一端（隊尾）刪除元素。先入先出。

結構：

typedef struct QNode{
    QElemType data;
    struct QNode *next;   
}QNode,*QueuePtr;

typedef struct 
{
    QueuePtr front;//隊頭指針
    QueuePtr rear;//隊尾指針
    int len;
}LinkQueue;

操作：

入佇列EnQueue（尾部插入）：rear->next=S; rear=S;

出佇列DEQueue（頭部刪除）：front->next=p->next;

//插值EnQueue 刪除DEQueue
Status EnQueue(LinkQueue *Q,QElemType e){
    QNode *p=(QueuePtr)malloc (sizeof(QNode));
    p->data=e;
    p->next=NULL;
    if(Q->front==NULL){
        Q->front=Q->rear=p;
    }else{
        Q->rear->next=p;
        Q->rear=p;
    }
    Q->len++;
    return 1;
    }
Status DeQueue(LinkQueue *Q,QElemType *e){
    int isEmpty=QueueEmpty(Q);
    if(!isEmpty){
    QNode *p=Q->front;
    Q->front=p->next;
    printf("info: Queue delete head elem %d success\n",p->data);
    free(p);
    return 1;
    }{
    printf("error:Queue Empty \n");
    return 0;
    }
    Q->len--;
}

** 特點：** 先入先出，空鏈隊的特徵：front=rear。鏈佇列空的條件是首尾指針相等，而循環佇列滿的條件的判定，則有隊尾加 1 等於隊頭 和設標記兩種方法。

知識點 14：線性表、堆疊、隊的異同點：#

相同點：

• 邏輯結構相同，都是線性的；
• 都可以用順序存儲或鏈表存儲；
• 堆疊和佇列是兩種特殊 的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。

不同點：

• 運算規則不同：

  • 線性表為隨機存取； 而堆疊是只允許在一端進行插入和刪除運算，因而是後進先出表 LIFO；
  • 佇列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表 FIFO。

• 用途不同，線性表比較通用；堆疊用於函數調用、遞歸和簡化設計等；佇列用於離散事 件模擬、OS 作業調度和簡化設計等。

第五章 陣列和廣義表#

知識點 15 陣列地址計算公式#

ji 表示 n 維陣列中該元素在第 i 維中的坐標
ai 表示 n 維陣列中第 i 維的起始坐標
bi 表示第 i 維度的長度
L 表示一個元素所佔的字節數

例：一個順序表第一個元素存儲地址是 100，每個元素長度為 2，則第五個元素地址是108。

一維下上述公式為loc(j1)=loc(a1)+L*(j1-a1)。

loc=100+2*(0+(5-1))=108。

例：設二維陣列中，每個元素的長度為 4 個字節，行下標 i 從 1 到 8，列下標從 1 到 10，從首地址 SA 開始以行序列連續存放再存儲器內，那麼元素A[8][6]的起始地址為SA+300。

公式？狗都不用，直接畫出來數第幾個，A[8][6]是第 76 個元素。

loc=SA+4*(76-1)=SA+300。

從首地址 SA 開始以列序列連續存放再存儲器內，那麼元素A[8][6]的起始地址為SA+168。

按列數A[8][6]是 48 個元素。

總結：對於二維陣列A[X][Y], 設行元素個數為 a，列元素個數為 b，首元素地址為 A，元素長度為 s，按行序則地址為A+s*((X-1)*b+Y-1)，按列序則地址為A+s*((Y-1)*a+X-1)。

知識點 16 三元組的存儲結構#

typedef struct
{
    int i,j;
    ElemType e;
}Triple
#三元組順序表的C語言描述,稀疏矩陣
#define MAXSIZE 125000
typedef struct
{
Triple data[MAXSIZE+1;//矩陣包含的三元組表，data[0]未用
int mu,nu,t；//mu行數nu列數tu非0元素數
}TSMatrix

第六章 樹和二叉樹#

知識點 17 樹#

• 樹的概念及術語

  • 樹：n（n≥0）個結點的有限集合。當 n＝0 時，稱為空樹；任意一棵非空樹滿足以下條件：

    • 有且僅有一個特定的稱為根的結點；
    • 當 n＞1 時，除根結點之外的其餘結點被分成 m（m>0）個互不相交的有限集合 T1,T2,… ,Tm，其中每個集合又是一棵樹，並稱為這個根結點的子樹。

  • 結點的度：結點所擁有的子樹的個數。

    樹的度：樹中所有結點的度的最大值。

  • 葉子結點：度為 0 的結點，也稱為終端結點。

    分支結點：度不為 0 的結點，也稱為非終端結點。

  • 孩子、雙親：樹中某結點的子樹的根結點稱為這個結點的孩子結點，這個結點稱為它孩子結點的雙親結點；

    兄弟：具有同一個雙親的孩子結點互稱為兄弟。

  • 路徑：如果樹的結點序列 n1, n2, …, nk 有如下關係：結點 ni 是 ni+1 的雙親（1<=i<k），則把 n1, n2, …, nk 稱為一條由 n1 至 nk 的路徑；路徑上經過的邊的個數稱為路徑長度。

  • 祖先、子孫在樹中，如果有一條路徑從結點 x 到結點 y，那麼 x 就稱為 y 的祖先，而 y 稱為 x 的子孫。

  • 結點所在層數根結點的層數為 1；對其餘任何結點，若某結點在第 k 層，則其孩子結點在第 k+1 層。樹的深度：樹中所有結點的最大層數，也稱高度。

  • 層序編號：將樹中結點按照從上層到下層、同層從左到右的次序依次給他們編以從 1 開始的連續自然數。

  • 有序樹、無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數據結構中討論的一般都是有序樹。

  • 樹通常有前序（根）遍歷、後序（根）遍歷和層序（次）遍歷三種方式（樹，不是二叉樹，沒中序遍歷。)

關於樹的高度與深度

樹的深度是根結點到這個結點所經歷的邊的個數，所以高度等於深度加 1。

知識點 18 二叉樹的定義與性質#

二叉樹的定義#

二叉樹是 n（n≥0）個結點的有限集合，該集合或者為空集（稱為空 二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。

滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，並且所有葉子都在 同一層上。

（滿二叉樹的特點：葉子只能出現在最下一層；只有度為 0 和度為 2 的結點。）

完全二叉樹：對一棵具有 n 個結點的二叉樹按層序編號，如果編號為 i（1≤i≤n）的結點與同樣深度的滿二叉樹中編號為 i 的結點在二叉樹中的位置完全相同。

完全二叉樹的特點：

1. 在滿二叉樹中，從最後一個結點開始，連續去掉任意個結點，即是一棵完全二叉樹。
2. 葉子結點只能出現在最下兩層，且最下層的葉子結點都集中在二叉樹的左部；
3. 完全二叉樹中如果有度為 1 的結點，只可能有一個，且該結點只有左孩子。
4. 深度為 k 的完全二叉樹在 k-1 層上一定是滿二叉樹。
5. 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹，換言之滿二叉樹更加嚴格。

二叉樹的性質#

• 性質 1：二叉樹的第 i 層上最多有 2i-1 個結點（i≥1）。
• 性質 2：一棵深度為 k 的二叉樹中，最多有 2^k-1 個結點，最少有 k 個結點。深度為 k 且具有 2^k-1 個結點的二叉樹一定是滿二叉樹。
• 性質 3：在一棵二叉樹中，如果葉子結點數為 n0，度為 2 的結點數為 n2，則有: n0＝n2 ＋1。（一個結點的度就是指它放出的射線）。
• 性質 4：具有 n 個結點的完全二叉樹的深度為 log2n +1。
• 性質 5：對一棵具有 n 個結點的完全二叉樹中從 1 開始按層序編號，則對於任意的序號為 i（1≤i≤n）的結點（簡稱為結點 i），有：
  • （1）如果 i＞1，則結點 i 的雙親結點的序號為 i/2；如果 i＝1，則結點 i 是根結點，無雙親結點。
  • （2）如果 2i≤n，則結點 i 的左孩子的序號為 2i；如果 2i＞n，則結點 i 無左孩子。
  • （3）如果 2i＋1≤n，則結點 i 的右孩子的序號為 2i＋1；如果 2i＋1＞n，則結點 i 無右孩子。

知識點 19 二叉樹的遍歷#

前序遍歷是指，對於樹中的任意節點來說，先打印這個節點，然後再打印它的左子樹，最後打印它的右子樹。
中序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它本身，最後打印它的右子樹。
後序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它的右子樹，最後打印這個節點本身。

層次遍歷就是按照每一層從左向右的方式進行遍歷。

知識點 20 二叉樹的存儲#

/*------二叉樹的二叉鏈表存儲結構------*/
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode* left;
    struct BiTNode* right;
}BTNode,*BiTree;

知識點 21 線索二叉樹與存儲#

創建二叉樹時我們會發現其中一共有兩個指針域，有的指針域指向的結構為空，這也就浪費了很多空間。所以為了不去浪費這些空間我們採取了一個措施。就是利用那些空地址，存放指向結點在某種遍歷次序之下的前驅和後繼結點的地址。我們把這種指向前驅和後繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應的二叉樹就成為線索二叉樹。

如下圖就是一棵中序遍歷線索二叉樹，其中序遍歷為 1，3，6，8，10。

線索是一種對二叉樹的操作，意思是對二叉樹進行線索化，其目的是使線索化後的二叉樹具有方便被遍歷的特點，即不使用遞歸和堆疊也可以對線索化之後的樹進行中序遍歷。

將對二叉樹以某種次序遍歷使其變為線索二叉樹的過程稱為線索化 。

線索二叉樹的存儲

struct Tree
{
    char  data;        //需要存儲的數據 
    int num;
    int LisThread;//左右的標志,值為0或1
    int RisThread; 
    struct Tree *lchild,*rchild;    //左右孩子的指針
};

知識點 22 二叉樹的應用 - 哈夫曼樹與哈夫曼編碼#

哈夫曼樹的基本概念：#

哈夫曼樹：給定一組具有確定權值的葉子結點，帶權路徑長度最小的二叉樹。

哈夫曼樹的特點：#

1. 權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。

2. 只有度為 0（葉子結點）和度為 2（分支結點）的結點，不存在度為 1 的結點。

哈夫曼樹遍歷：#

構造 Huffman 樹的步驟（即 Huffman 算法）：#

(1) 由給定的 n 個權值 { w1, w2, …, wn } 構成 n 棵二叉樹的集合 F = { T1, T2, …, Tn }（即森林），其中每棵二叉樹 Ti 中只有一個帶權為 wi 的根結點，其左右子樹均空。

(2) 在 F 中選取兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且讓新二叉樹根結點的權值等於其左右子樹的根結點權值之和。 (3) 在 F 中刪去這兩棵樹，同時將新得到的二叉樹加入 F 中。

(4) 重複 (2) 和 (3) , 直到 F 只含一棵樹為止。這棵樹便是 Huffman 樹。

計算帶權路徑長度（WPL）#

帶權路徑長度 = 葉結點的權值 * 路徑長度，以上圖哈夫曼樹為例葉子結點有 7 8 5 3 11 23，WPL=7*4+8*4+3*4+5*4+11*3+23*2=167。

哈夫曼編碼計算#

哈夫曼編碼的定義

哈夫曼編碼就是規定哈夫曼樹中的左分支為 0，右分支為 1，從根節點到每個葉節點所經過的分支對應的 0 和 1 組成的序列便為該節點對應字符的編碼。這樣的編碼稱為哈夫曼編碼。哈夫曼編碼是一種無前綴編碼。解碼時不會混淆。其主要應用在數據壓縮，加密解密等場合。

知識點 23 樹與森林的轉換#

樹到二叉樹#

1. 加線：樹中所有相鄰兄弟加一條線。
2. 去線：對於樹中的每個結點，只保留與其第一個孩子結點之間的連線，刪去與其他孩子結點的連線。
3. 旋轉：以樹的根結點為軸心，將整棵樹順時針旋轉一定角度，使之結構層次分明，即可得到二叉樹。

森林和二叉樹的相互轉換#

二叉樹轉換成森林

1. 加線：將二叉樹中每個結點和其左孩子結點的右孩子加線相連。
2. 去線：去掉樹中的每個結點和右孩子的連線。
3. 旋轉：以樹的根結點為軸心，將整棵樹逆時針旋轉一定角度，使之結構層次分明，即可得到森林。

森林轉換成二叉樹

1. 加線：森林中所有相鄰兄弟加一條線。
2. 去線：對於森林中的每個結點，只保留與其第一個孩子結點之間的連線，刪去與其他孩子結點的連線。
3. 旋轉：以樹的根結點為軸心，將整棵樹順時針旋轉一定角度，使之結構層次分明，即可得到二叉樹。

知識點 24 樹和森林的遍歷#

樹的遍歷#

樹只有前序，後序，層次遍歷沒有中序遍歷。

前序遍歷

和二叉樹一樣先根後左再右，優先級依次降低。樹非空，則先訪問根節點，然後按從左向右的順序，前序遍歷根節點的每一棵子樹。（像是對樹進行類似二叉樹的先序遍歷）如上圖的樹前序遍歷為 A B E F C D G I H。

後序遍歷

樹非空，則按從左向右的順序，後根遍歷根節點的每一棵子樹，然後訪問根節點。（像是對樹進行類似二叉樹的後序遍歷步驟）如上圖的樹後序遍歷為 E F B C I G H D A。

森林的遍歷#

可以直接按照先序遍歷二叉樹，也可以先轉換為二叉樹再遍歷。

例如上圖森林的前序遍歷為 A B C D E F G H J I。

第七章 圖#

知識點 25 圖的定義與性質#

圖的定義：圖 (Graph)：圖 G 是由兩個集合 V (G) 和 E (G) 組成的，記為：G=(V,E)

其中：V (G) 是頂點的非空有限集；E (G) 是邊的有限集合，邊是頂點的無序對或有序對。

有向圖，無向圖

頂點的度：

​ 無向圖中，頂點的度為與每個頂點相連的邊數；

​ 有向圖中，頂點的度分成入度與出度。

​ ** 入度：** 以該頂點為頭的弧的數目。

​ ** 出度：** 以該頂點為尾的弧的數目。

路徑：路徑是頂點的序列。

路徑長度：沿路徑邊的數目或沿路徑各邊權值之和。

回路：第一個頂點和最後一個頂點相同的路徑。

簡單路徑：序列中頂點不重複出現的路徑。

簡單回路：除了第一個頂點和最後一個頂點外，其餘頂點不重複出現的回路。

連通：從頂點 V 到頂點 W 有一條路徑，則說 V 和 W 是連通的。

連通圖：圖中任意兩個頂點都是連通的。

連通分量：非連通圖的每一個連通部分。

強連通圖：有向圖中，如果對每一對 Vi,Vj!=V, Vi!=Vj, 從 Vi 到 Vj 和從 Vj 到 Vi 都存在路徑，則稱 G 是強連通圖。

知識點 26 圖的存儲結構#

鄰接矩陣#

圖的鄰接矩陣表示法，又稱數組表示法。它採用兩個數組來表示圖：

1、用於存儲頂點信息的一維數組；

2、用於存儲圖中頂點之間關聯關係的二維數組，稱為鄰接矩陣。

無權圖的鄰接矩陣

有權圖的鄰接矩陣

#圖結構鄰接矩陣存儲結構代碼實現
#define MAXVEX 20					//頂點最大數
#define INFINITY 65535 				//代指無限大 
typedef struct
{
	datatype data[MAXVEX];			//頂點表 
	edgetype arc[MAXVEX][MAXVEX];	//存儲邊的權的鄰接矩陣 
	int numVertexes,numEdges;		//頂點數,邊或弧的個數 
}MGraph;//圖結構鄰接矩陣
int visited[MAXVEX]; //訪問數組

鄰接表#

鄰接表表示法是圖的一種鏈式存儲結構，基本思想是只存儲圖中存在的邊的信息。

#define MAX_VERTEX_NUM 20 /* 最多頂點個數 */
typedef enum{DG, DN, UDG, UDN} GraphKind; /* 圖的種類 */
 
/* 定義表頭結點的類型 */
typedef struct VertexNode {
    VertexData data;    //數據域，存放頂點信息
    ArcNode * firstarc; //指針域，指向邊表中第一個結點
} VertexNode;
 
/* 定義邊結點的類型 */
typedef struct ArcNode {
    AdjType adjvex;           //鄰接點域，邊的終點在頂點表中的下標
    OtherInfo info;           //數據域，存放其它相關信息
    struct ArcNode * nextarc; //指針域，指向邊表中的下一個結點
} ArcNode;

鄰接表與鄰接矩陣有什麼異同之處？#

1. 聯繫：鄰接表中每個鏈表對應於鄰接矩陣中的一行， 鏈表中結點個數等於一行中非零元素的個數。
2. 區別： 對於任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致）， 但鄰接表不唯一（鏈接次序與頂點編號無關）。
3. 用途： 鄰接矩陣多用於稠密圖的存儲 而鄰接表多用於稀疏圖的存儲。

知識點 27 圖的遍歷#

圖的深度優先遍歷（DFS）#

方法：從圖的某一頂點 V0 出發，訪問此頂點；然後依次從 V0 的未被訪問的鄰接點出發，深度優先遍歷圖，直至圖中所有和 V0 相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重複上述過程，直至圖中所有頂點都被訪問為止。

所謂 DFS，就是從起點開始，找準一個方向直到走不了為止，然後再原路返回，再找到一個能走的地方繼續走的思路。

深度優先遍歷結果是： A B E F C D G H I。

必須說明，若不給定存儲結構，深度優先遍歷的結果不唯一。因為哪個頂點是第一鄰接點未確定。給定存儲結構後，深度優先遍歷的結果是唯一的。

圖的廣度優先遍歷（BFS）#

廣度優先遍歷可定義如下：首先訪問出發點 v，接著依次訪問 v 的所有鄰接點 w1、w2......wt，然後依次訪問 w1、w2......wt 鄰接的所有未曾訪問過的頂點。以此類推，直至圖中所有和源點 v 有路徑相通的頂點都已訪問到為止。此時從 v 開始的搜索過程結束。

廣度優先遍歷結果是： A B C D E F G H I。

廣度優先遍歷按層次優先搜索最近的結點，一層一層往外搜索。

知識點 28 圖的應用 - 最小生成樹#

最小生成樹（MST）的性質如下：若 U 集是 V 的一個非空子集，若 (u0, v0) 是一條最小權值的邊，其中 u0 U，v0 V-U；則：(u0, v0) 必在最小生成樹上。

求 MST 最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法。

Kruskal 算法特點：將邊歸並，適於求稀疏網的最小生成樹。

Prime 算法特點：將頂點歸並，與邊數無關，適於稠密網。

Prim 算法（逐點加入）#

Prim 算法更適用於稠密圖（點少邊多）。

過程圖解：

Kruskal 算法（逐邊加入）#

連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權值之和是唯一的。應熟練掌握 prim 和 kruscal 算法，特別是手工分步模擬生成樹的生成過程。

知識點 29 圖的應用 - 拓撲排序#

拓撲排序是一個 ** 有向無環圖（有向圖、弧不形成閉環）** 的所有頂點的線性序列。該線性序列中，圖的每個頂點只出現一次，若頂點 A 到頂點 B 之間存在有向弧 <v1,v2>, 則頂點 A 一定在頂點 B 前面。

訪問圖的頂點時，保證每次訪問的頂點前面沒有別的頂點 (入度為 0)，即訪問的頂點只作為弧的弧頭。滿足拓撲排序的前提：圖中沒有環。

1. 选入度为 0 的节点 A， 输出 A。 删除 AB AC 的边（B 入度为 1-1=0，C 入度 - 1）。

   2. 选入度为 0 的节点 B， 输出 B。删除 BC，BE 的边（C 入度为 1-1=0，E 入度 - 1）。

   3. 选入度为 0 的节点 C， 输出 C。删以 C 开始的边（对应节点入度 - 1）。

繼續重複即得拓撲排序 ABCDEF（也可以是 ABCEDF）。

注： 拓撲排序結果不唯一（同時有多個入度為 0），所以題目可以要求你寫出全部的拓撲排序。

知識點 30 圖的應用 - 關鍵路徑#

關鍵路徑：若有向圖中，各頂點表示事件，各有向邊表示活動持續事件，則該圖為活動邊網絡，簡稱 AOE 網。AOE 網中的關鍵路徑，就是完成整個網絡所需的最短時間，亦最長路徑，AOE 網中，往往有若干項活動可以平行的進行，因此，從開始頂點到最後一個頂點的最長路徑稱為關鍵路徑。

不多解釋，直接列表，事件最早發生時間 ve（和最大）, 事件最晚發生時間 vl（差最小）。

先寫拓撲排序。

正拓撲排序 v1 v2 v3 v5 v4 v6。

逆拓撲排序 V6 V5 V4 V2 V3 V1。

再算頂點 ve，vl。

ve 使用正拓撲排序算路線和最大。

vl 使用逆拓撲排序算路線差最小。

最後算邊 (事件) 的弧尾頂點最早開始時間即活動最早開始時間 e ，邊 (事件) 的弧頭頂點活動最晚開始時間 - 權值即活動最晚開始時間（只要時最晚就是倒著求）， l 時間余量 l-e。

關鍵路徑即為 v1 v3 v4 v6。

時間余量為 0 代表關鍵活動 a2 a5 a7。

知識點 31 圖的應用 - 最短路徑#

Dijkstra (迪杰斯特拉) 算法是典型的單源最短路徑算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra 算法是很有代表性的最短路徑算法。

算法思想：#

設 G=(V,E) 是一個帶權有向圖，把圖中頂點集合 V 分成兩組，第一組為已求出最短路徑的頂點集合（用 S 表示，初始時 S 中只有一個源點，以後每求得一條最短路徑，就將加入到集合 S 中，直到全部頂點都加入到 S 中，算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用 U 表示），按最短路徑長度的遞增次序依次把第二組的頂點加入 S 中。在加入的過程中，總保持從源點 v 到 S 中各頂點的最短路徑長度不大於從源點 v 到 U 中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S 中的頂點的距離就是從 v 到此頂點的最短路徑長度，U 中的頂點的距離，是從 v 到此頂點只包括 S 中的頂點為中間頂點的當前最短路徑長度。

算法步驟：#

a. 初始時，S 只包含源點，即 S＝{v}，v 的距離為 0。U 包含除 v 外的其他頂點，即={其餘頂點}，若 v 與 U 中頂點 u 有邊，則 < u,v > 正常有權值，若 u 不是 v 的出邊鄰接點，則 < u,v > 權值為∞。

b. 從 U 中選取一個距離 v 最小的頂點 k，把 k，加入 S 中（該選定的距離就是 v 到 k 的最短路徑長度）。
c. 以 k 為新考慮的中間點，修改 U 中各頂點的距離；若從源點 v 到頂點 u 的距離（經過頂點 k）比原來距離（不經過頂點 k）短，則修改頂點 u 的距離值，修改後的距離值的頂點 k 的距離加上邊上的權。
d. 重複步驟 b 和 c 直到所有頂點都包含在 S 中。

解題過程：#

單源點帶非負權值的最短路徑求解算法 Dijkstra 迪杰斯特拉算法，看視頻過程鏈接。

根據上表 u-v 最短路徑 u-a-d-v 最短距離為 5。

超星習題選摘#

堆疊和佇列部分#

1. 當堆疊的最大長度難以估計時，堆疊最好採用 ( 鏈式) 存儲結構。

2. 堆疊結構通常採用的兩種存儲結構是順序存儲結構和鏈式存儲結構。

3.堆疊可作為實現遞歸函數調用的一種數據結構。

4. 表達式 a*(b+c)-d 的後綴表達式是 (abc+*d-)

注：解決表達式轉換為前後綴表達式的思路：

a+b-a*((c+d)/e-f)+g 為例

後綴：

括號法（推薦）：

①按照運算符的優先級，對所有的運算單位加括號。

於是變成：(((a+b)-(a*(((c+d)/e)-f)))+g)

②從最裡面的括號開始，依次把運算符號移動到對應的括號的後面。

於是變成：(((ab)+(a (((cd)+e)/f)-)*)-g)+

③最後，把括號都去掉

於是變成：ab+acd+e/f-*-g+

基於堆疊的算法：

從左到右進行遍歷。

1. 遇到的是運算數，直接輸出。

2. 遇到的是左括號 '('，直接壓入堆疊 (括號是最高優先級，無需比較；入堆後優先級降到最低，確保其他符號正常入堆)。

3. 遇到的是右括號 ')'，意味著括號已結束。不斷彈出堆疊頂運算符並輸出，直到遇到左括號，這個左括號彈出但是不輸出。

4. 遇到的是運算符 ('+'、'-'、'*'、'/')，有三種情況

①如果堆疊為空，直接入堆。

②如果堆疊頂元素是左括號 '('，直接入堆。

③如果堆疊頂元素是運算符，則需要進行比較，

1 - 如果優先級大於堆疊頂運算符，則壓入堆疊；

2 - 如果優先級小於等於堆疊頂運算符，則將堆疊頂運算符彈出並輸出，然後比較新的堆疊頂運算符，直到優先級大於堆疊頂運算符或者堆疊空，再將該運算符入堆。

5. 如果對象處理完畢，則按順序彈出並輸出堆疊中所有運算符。

前綴：

括號法：（推薦）

①按照運算符的優先級，對所有的運算單位加括號。

於是變成：(((a+b)-(a*(((c+d)/e)-f)))+g)

②從最裡面的括號開始，依次把運算符號移動到對應的括號的前面。

於是變成：+(-(+(ab)*(a-(/(+(cd) e) f))) g)

③最後，把括號都去掉

於是變成：+-+ab*a-/+cdefg

基於堆疊的算法

從右到左進行遍歷。

1. 遇到的是運算數，直接輸出。

2. 遇到的是右括號 ')'，直接壓入堆疊 (括號是最高優先級，無需比較；入堆後優先級降到最低，確保其他符號正常入堆)。

3. 遇到的是左括號 '('，意味著括號已結束。不斷彈出堆疊頂運算符並輸出，直到遇到右括號，這個右括號彈出但是不輸出。

4. 遇到的是運算符 ('+'、'-'、'*'、'/')，有三種情況

①如果堆疊為空，直接入堆。

②如果堆疊頂元素是右括號 ')'，直接入堆。

③如果堆疊頂元素是運算符，則需要進行比較，

1 - 如果優先級大於等於堆疊頂運算符，則壓入堆疊；

2 - 如果優先級小於堆疊頂運算符，則將堆疊頂運算符彈出並輸出，然後比較新的堆疊頂運算符，直到優先級大於等於堆疊頂運算符或者堆疊空，再將該運算符入堆。

5. 如果對象處理完畢，則按順序彈出並輸出堆疊中所有運算符。

5. 順序存儲的循環佇列 sq 中，假定 front 和 rear 分別為隊頭指針和隊尾指針，則入隊操作為（ ）

• A、sq.rear=sq.rear+1;sq.data[sq.rear]=x;
• B、sq.data[sq.rear]=x;sq.rear=sq.rear+1;
• C、sq.rear=(sq.rear+1)%maxsize; sq.data[sq.rear]=x;
• D、sq.data[sq.rear]=x;sq.rear=(sq.rear+1)%maxsize;

6. 在具有 m 個單元的順序存儲的循環佇列中，假定 front 和 rear 分別為隊頭指針和隊尾指針，則判斷隊滿的條件為（ ）

• A、rear % m==front
• B、(front+1) % m==rear
• C、（rear－1）%m==front
• D、(rear+1) % m==front

循環佇列判斷條件是 rear 和 front 相差一個元素 rear+1=front，這是為了避免因為循環佇列的結構的導致判空判滿條件相同 rear = front 導致歧義故意少用一個元素的空間使判滿條件變更。

7. 在具有 m 個單元的順序存儲的循環佇列中，假定 front 和 rear 分別為隊頭指針和隊尾指針，則判斷隊空的條件為（ ）

• A、rear ==front
• B、(front+2) % m==rear
• C、（rear－2）%m==front
• D、(rear+2) % m==front

8. 鏈堆疊與順序堆疊相比，有一個比較明顯的優點，即（ ）

• A、插入操作更方便
• B、通常不會出現堆疊滿的現象
• C、 不會出現堆疊空的情況
• D、刪除操作更加方便

9. 用鏈接方式存儲的佇列，在進行刪除運算時（）

• A、僅修改頭指針

• B、僅修改尾指針

• C、頭、尾指針都要修改

• D、頭、尾指針可能都要修改

當僅有一個元素時刪除都要修改。

10. 用單鏈表表示的鏈佇列的隊頭在鏈表的（ ）位置。

• A、鏈頭
• B、鏈尾
• C、鏈中
• D、任意位置

其他習題選摘#

1. 堆疊 S最多可以容納 4 個元素，現有六個元素 ABCDEF 按照順序進堆疊，下列哪一序列可能時出堆疊序列（C）

A)EDCBAF B)BCEFAD C)CBEDAF D)ADFEBC

2. 高度為 h 的二叉樹最多最少有多少個結點（2^h-1）（h）。

3. 若一顆非空二叉樹的先序和後序遍歷相反，則（C）

A）二叉樹任意結點無左孩子。

B）二叉