——算法、線性表——

概念明晰：隨機存取、順序存取、隨機存儲和順序存儲

隨機存取、順序存取、隨機存儲和順序存儲這四個概念是完全不一樣的，切不可將之混淆

很多人包括我可能認為隨機存取就是隨機存儲，順序存取就是順序存取，其實不是這樣。

下面完整的介紹一下這4個概念

1、存取結構

分為隨機存取和非隨機存取（又稱順序存取）

1、隨機存取就是直接存取，可以通過下標直接訪問的那種數據結構，與存儲位置無關。例如數組。

? 非隨機存取就是順序存取，不能通過下標訪問了，只能按照存儲順序存取，與存儲位置有關，例如鏈表。

2、順序存取就是存取第N個數據時，必須先訪問前（N-1）個數據 （list）;

? 隨機存取就是存取第N個數據時，不需要訪問前（N-1）個數據，直接就可以對第N個數據操作 （array）。

2、存儲結構

分為順序存儲和隨機存儲

3、順序存儲結構

• 在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素，稱作線性表的順序存儲結構。

  - 順序存儲結構是存儲結構類型中的一種，該結構是把**邏輯上相鄰的節點**存儲在**物理位置上相鄰的存儲單元**中，結點之間的邏輯關系由存儲單元的鄰接關系來體現。 - 由此得到的儲結構為順序存儲結構，通常順序存儲結構是借助于計算機程序設計語言（例如c/c++）的數組來描述的。

? – 主要優點：節省存儲空間。

? 因為分配給數據的存儲單元全用存放結點的數據（不考慮c/c++語言中數組需指定大小的情況），結點之間的邏輯關系沒有占用額外的存儲空間。采用這種方法時，可實現對結點的隨機存取，即每一個結點對應一個序號，由該序號可以直接計算出來結點的存儲地址。

? – 主要缺點：不便于修改，對結點的插入、刪除運算時可能要移動一系列的結點。

4、隨機存儲結構

在計算機中用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。它不要求邏輯上相鄰的元素在物理位置上也相鄰。因此它沒有順序存儲結構所具有的弱點，但也同時失去了順序表可隨機存取的優點。

? --隨機存儲最典型的代表為鏈式存儲：

鏈式存儲結構特點

1、比順序存儲結構的存儲密度小 （每個節點都由數據域和指針域組成，所以相同空間內假設全存滿的話順序比鏈式存儲更多）。

2、邏輯上相鄰的節點物理上不必相鄰。

3、插入、刪除靈活 （不必移動節點，只要改變節點中的指針）。

4、查找結點時鏈式存儲要比順序存儲慢。

5、每個結點是由數據域和指針域組成

一、數據結構的概念

1、基本概念:

• 數據：描述客觀事實的符號，是計算機中可以操作的對象，能被計算機識別，并輸給計算機處理的符號集合。
• 數據元素：是組成數據的、有一定意義的基本單位，在計算機中通常作為整體處理，也被成為記錄。
• 數據對象：是性質相同數據元素的集合，是數據的一個子集。
• 數據項：一個數據元素可以由若干個數據項組成，數據項是數據不可分割的最小單位。
• 數據結構：相互之間存在一種或者多種特定關系的數據元素的集合。可分為邏輯結構和物理結構。

2、算法

(1)概念

解決特定問題的求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作。

(2)重要特性：

①輸入：有零個輸入或者多個輸

②輸出：只有一個或者多個輸出

③有窮性：算法在執行有限個步驟時，會自動結束而不會陷入無限循環里面

④確定性：算法的每一步都有確定的含義而不會出現二義性

⑤可行性：算法的每一步都可以通過有限次數完成。

3、算法的評價標準(“好”的算法應該考慮達到以下目標)

①正確性。算法能夠正確地求解問題。

②可讀性。算法能具有良好的可讀性，以幫助人們理解。

③健壯性。輸入非法數據時，算法能適當地做出反應或進行處理。而不會產生莫名其妙的輸出結果。

④效率與低存儲量需求。效率指算法執行的時間，存儲量需求是指算法執行過程中所需的最大存儲空間。

4、算法的時空效率

(1)時間復雜度

根據算法寫成的程序在執行時耗費時間的長度，記為T(n) = O(n)

(2)空間復雜度

根據算法寫成的程序在執行時占用存儲單元的長度記為S(n)

(3)語句頻度

一個算法中的語句執行次數稱為語句頻度或時間頻度，記為T(n)

時間復雜度：時間復雜度實際上是一個函數，代表基本操作重復執行的次數，進而分析函數雖變量的變化來確定數量級，數量級用O表示，所以算法的時間復雜度為： T（n）=O（f（n））

在一個算法存在最好、平均、最壞三種情況，我們一般關注的是最壞情況，原因是，最壞情況是任何輸入實例在運行時間的上界，對于某些算法來說，最壞情況出現的比較頻繁，從大體上來看，平均情況和最壞情況一樣差。

(4)一般O（n）的計算方法：

①用 1代替所有運行時間中出現的加法常數；

②在修改后的運行函數中**保留最高階的項；

③如果最高階的項系數不是1，則去除這個項系數。

④ 遞歸算法的時間復雜度為：遞歸總次數每次遞歸中基本操作執行的次數。

(5)常見的時間復雜度有以下七種：

① O（1）常數型；② O（log2N）對數型；③ O（N）線性型；④ O（Nlog2N）二維型；⑤ O（N^2)平方型；⑥ O（N^3)立方型；⑦ O（2^N）指數型。

例如：

i=1;① while (i<=n) {i=i*2; ② } 解：語句1的頻度是1, 設語句2的頻度是f(n),則：2^f(n)<=n;f(n)<=log2n 取最大值f(n)= log2n, T(n)=O(log2n )

二、線性表

1、順序存儲

(1)結構體的定義

typedef int Position; typedef struct LNode * PtrToLNode; struct LNode {ElmenetType Data[ MAXSIZE ];Position Last; }; typedef PtrToLNode List;

(2)順序表的初始化

1、構造一個空表

2、動態分配表結構所需的存儲空間，然后將表中Last指針置為-1 表示表中沒有數據。

List MakeEmpty() {List L; L = (List)malloc(sizeof(struct LNode));L->Last = -1; //Last 置為-1 表示表中沒有數據元素Return L; }

• 通過L我們可以訪問相應線性表的內容。比如：下標為i 的元素：L->Data[i]

• 查詢線性表的長度：L->Last+1;

(3)順序表的查找(時間復雜度為O(n))

在線性表中查找與給定值 X 相等的數據元素。

由于線性表的元素都存儲在數組Data中，所以這個查找的過程實際上就是在數組里順序查找：

• 從第 1 個元素 a1 起依次和 X 比較， 直到找到一個與 X 相等的數據元素，返回它在順序表中的存儲下標；
• 或者查遍整個表都沒有找到與 X 相等的元素，則返回錯誤信息 ERROR。

#define ERROR -1 /* 將錯誤信息 ERROR 的值定義為任一負數都可以 */ Position Find( List L, ElementType X ) {Position i = 0;While( i <= L->Last && L->Data[i] != X)i++;if( i > L->Last)return ERROR; /* 如果沒有找到，則返回錯誤信息 */elsereturn i; /* 找到后返回的是存儲位置 */ }

(4）順序表的插入 (時間復雜度為O(n))

在表的插入是指在表的第 i（1≤ i ≤ n + 1）個位序上插入一個值為 X 的新元素（也可以理解為在第 i 個元素之前插入新的元素）

插入后使得原來長度為 n 的序列，變為長度為 n+1的序列（i = 1時插入序列的最前端，i = n+1 時插入序列的最后）

• 將ai~an順序向后移動（移動次序是從 an 到ai)，為新元素讓出位置；
• 將 X 放入空出的第 i 個位序；
• 修改 Last 指針（相當于修改表長）,使之指向最后一個元素。

bool Insert( List L, ElementType X, int i) { /* 在 L 的指定位序 i 前插入一個新元素 X； 位序 i 元素數組位置下標為 i-1 */Postion j;if(L->Last == MAXSIZE-1){/* 表空間已滿，不能插入 */printf("表滿！\n");return false;}if( i<1 || i > L->Last+2){/* 檢查插入位序的合法性：是否在 1~n+1； n為當前元素個數，即Last+1 */printf（"位序不合法！\n");return false;}for( j = L->Last; j >= i-1; j--) /*Last 指向序列最后元素an */L->Data[j+1] = L->Data[j]; /* 將位序為 i 及以后的元素順序向后移動 */L->Data[i-1] = X; /* Last 仍指向最后一個元素 */L->Last++;return true; }

(5)順序表的刪除（時間復雜度為O(n)）

將表中的位序為 i（1≤ i ≤ n + 1）的元素從線性表中去掉，刪除后使原長度為 n 的數組元素序列,變為長度為 n-1 的序列

• 將a[i+1]~a[n] 順序向前移動 ，a[i] 元素被a[i+1]覆蓋；

• 修改 Last 指針（相當于修改表長）使之仍指向最后一個元素。

bool Delete(List L, int i) { /*從 L 中刪除指定位序 i 的元素，該元素數組下標為 i-1*/Position j;if(i < 1 || i > L->Last + 1)/* 檢查空表及刪除位序的合法性*/ {printf("位序%d不存在元素",i);return false;} for( j = i; i <= L->Last; j++)L->Data[j-1] = L->Data[j];/*將位序 i+1 及以后的元素順序向前移動*/ L->Last--;/*Last 仍指向最后元素*/ return true; }

2、鏈表存儲

(1）結構體的定義（時間復雜度為O(n)）

typedef struct LNode * PtrToLNode; struct LNode {ElementType Data;PtrToLNode Next; }; typedef PtrToLNode Position; /*這里的位置是結點的地址 */ typedef PreToLNode List;

(2)求表長（時間復雜度為O(n)）

在順序存儲中求表長是很容易的，直接返回 Last+1 就可以了。但在鏈式存儲中，需要將鏈表從頭到尾遍歷一遍

• 設一個移動指針p和計數器cnt，初始化后，p從表的第 1 個結點開始逐步往后移，同時計數器 cnt+1.
• 當后面不再有結點時，cnt 的值就是結點個數，即 表長。

int Length(List L) {//默認該鏈表是有頭結點的 Position p;int i=0; /* 初始化計數器 *///單向鏈表的遍歷(三部曲)p = L->next; /* p指向表的第 1 個結點 */while(p){ /* 遍歷單鏈表，統計結點數 */ p=p->next; i++; } return i; }

(3)判空

int ListEmpty(LinkList L) { //若 L 為空，則返回1，否側返回 0if(L->Next) //非空return 0;elsereturn 1; }

(4)查找（時間復雜度為O(n)）

有兩種 按序號查找（FindKth）和 按值查找（Find）

①按序號查找 FindKth（時間復雜度為O(n)）

對于順序存儲，按序號查找是很直接的事情，要得到第 K 個元素的值，直接取L->Data[K-1]即可。

但是對于鏈式存儲則需要采用跟求表長類似的思路：

• 從鏈表的第 1 個元素結點起，判斷當前結點是否是第 K 個；
• 若是，則返回該結點的值，否則繼續對比后一個，直到表結束為止。
• 如果沒有第 K 個結點則返回錯誤信息。

#define ERROR -1 /* 一般定義為表中元素不可能取到的值 */ElementType FindKth(List L, int K) { /* 根據指定的位序 K， 返回 L 中相應的元素 */Position P;int cnt = 1; /* 位序從 1 開始 */p = L; /* p 指向 L的第 1 個結點 */while(p && cnt < K){p = p->next;cnt++} if((cnt == K) && p)return p->Data; /* 返回第 K 個 */elsereturn ERROR; /* 否則返回錯誤信息 */ }

②按值查找，即定位 Find（時間復雜度為O(n)）

基本方法：也是從頭到尾遍歷，直到找到為止：

• 從鏈表的第 1 個元素結點起，判斷當前結點的值是否等于 X；
• 若是，返回該結點的位置，否則繼續對比后一個，直到表結束位置為止；
• 找不到時返回錯誤信息。

#define ERROR NULL /*空地址表示錯誤 */Position Find( List L, ElementType X) {Position p = L;/* p指向 L 的第 1 個元素 */while(p && p->Data != x){p = p->Next;}if(p)return p;elsereturn ERROR; }

(5)鏈表的插入（時間復雜度為O(n)）

int ListInsert_L(LinkList &L, int i,ElementType e) {p = L;j = 0;while(p&& j<i-1){//尋找第 i-1 個結點p = p->next;++=j;}if(!p || j > i-1)return ERROR;//s = (LinkList)malloc(sizeof(LNode));//生成新結點ss->data = e; //將結點s 的數據域的值 更新為 es->next = p->next; //將結點s 插入 L 中p->next = s;return OK; }

(6)創建鏈表（時間復雜度為O(n)）

1、帶頭結點的【頭插法】（時間復雜度為O(n)）

/* 帶頭結點的插入創建 */ void createListHead( Linklist L, int n ) { //建立頭結點L = (LNode*)malloc(sizeof(struct LNode));L->Next = NULL;//建立單鏈表（頭插法）LNode *temp = NULL;//申請空間，寫入數據for(int i = 0; i < n; i++){tmp = (LNode*)malloc(sizeof(struct LNode)); /* 申請、填裝結點 */scanf("%d",&tmp->Data);//輸入元素值//插入到頭結點的后面tmp->Next = L->Next; L->Next = tmp; } }

2、帶尾結點的插入【尾插法】（時間復雜度為O(n)）

/*帶尾結點的插入*/ void CreateList_L( Listlist &L, int n ) { //正位序數輸入 n 個元素的值，建立帶表頭結點的單鏈表L//建立頭結點L = (LNode*)malloc(sizeof(struct LNode));L->Next = NULL;//建立單鏈表（尾插法）LNode r = L; //尾指針指向頭結點//申請空間，寫入數據for(int i = 0;i < n; i++){LNode *tmp = (LNode*)malloc(sizeof(struct LNode)); /* 申請新結點 */scanf("%d",&tmp->Data); //輸入元素tmp->Next = NULL;//插入到尾結點后面r->next = temp; r = tmp; //r指向新的尾結點} }

(7)刪除（時間復雜度為O(n)）

//將線性表L 中第 i 個數據元素刪除 int ListDelete_L(LinkList &L, int i, ElementType &e) {p=L;int j=0;while(p->next && j < i-1){//尋找第 i 個結點，并令p指向其前驅p = p>next;++j;}if(!(p->next)||j < i-1)return ERROR;//刪除位置不合理q = p->next; //臨時保存被刪除結點的地址以備釋放p->next = q->next; //改變被除結點的驅結點的指針域e = q->data; //保存被刪除結點的數據域free(q); //釋放被刪除結點的空間return OK; }

3、二者時間復雜度和優缺點的比較

1、兩者復雜度比較

查找插入刪除

順序表	O(1)	O(1)	O(n)通過下標直接找到待操作元素，主要時間花在移動元素上。
鏈表	O(n)	O(n)主要時間用于找到插入元素的位置	O(n)主要時間用于找到待刪除元素的位置

2、兩者優缺點比較

數組優點缺點

	隨機訪問性強；查找速度快	插入和刪除效率低；可能浪費內存；內存空間要求高，必須有足夠的連續內存空間；數組大小固定，不能動態拓展

鏈表優點缺點

	插入刪除速度快；內存利用率高，不會浪費內存；大小沒有固定，拓展很靈活。	不能隨機查找，必須從第一個開始遍歷，查找效率低

兩者的區別在于順序結構的要求一片連續的存儲空間，而鏈式結構的不要求存儲空間連續。

三、棧

1、棧的順序存儲實現

通常由一個一維數組和一個記錄棧頂元素位置的變量組成。

(1)順序棧結構體的定義

當 Top = -1時，表示棧空；當Top = MaxSize -1 時，棧滿！

typedef int Position; typedef int ElementType; typedef struct SNode *PtrToNode; struct SNode {ElementType * Data; /*存儲元素的數組*/Position Top; /*棧頂指針*/int MaxSize; /*堆棧最大容量*/ }; typedef PtrToNode Stack;

(2)順序棧的創建

Stack CreateStack(int MaxSize) /*順序棧的創建*/ {Stack S = (Stack)malloc(sizeof(struct SNode));S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));S->Top = -1; /*"-1"表示空棧 "MaxSize-1"表示滿棧*/ S->MaxSize = MaxSize; /*指定棧的最大容量*/ return S; }

(3)判滿

bool IsFull(Stack S) /*判斷棧是否滿了*/ {return(S->Top == S->MaxSize-1); }

(4)判空

bool IsEmpty(Stack S) /*判斷堆棧是否為空*/ {return(S->Top == -1); }

(5)入棧

在執行堆棧 Push 操作時，先判斷棧是否滿；

• 若不滿，Top 加1，并將新元素放入 Data數組的Top位置上
• 若滿，則返回錯誤標志

bool Push(Stack S, ElementType X) /*順序棧的 入棧 操作*/ { if(IsFull(S)) {printf("堆棧滿！");return false;}else{S->Data[++(S->Top)] = X; /*若是棧不滿，則Top加 1,并將新元素放入Data數組的Top位置中*/ return true;} }

(6)出棧

執行Pop操作時，首先判別棧是否為空；

• 若不為空，返回Data[Top]，同時將Top-1;
• 否則要返回錯誤標志

ElementType Pop(Stack S) /*順序棧 的 出棧 操作*/ {if(IsEmpty(S)) {printf("堆棧空！");return ERROR; /*ERROR 是 ElementType 類型的特殊值，標志錯誤。必須是正常棧元素數據不可能取到的值 */ }elsereturn(S->Data[(S->Top)--]); /*若不空，返回Data[Top]，同時將Top減 1*/ }

2、棧的順序存儲實現

鏈棧與單鏈表類似，但其操作受限制，插入和刪除操作只能在鏈棧的棧頂進行。

(1)順序棧結構體的定義

typedef struct SNode *PtrToSNode; typedef int ElementType; struct SNode {ElementType Data;PtrToSNode Next; }; typedef PtrToSNode Stack;

(2)順序棧的創建

Stack CreateStack() { /*構建一個堆棧的頭結點，返回該結點指針*/ Stack S;S = (Stack)malloc(sizeof(struct SNode));S->Next = NULL;return S; }

(3)判空

bool IsEmpty(Stack S) { /*判斷堆棧 S 是否為空，若是返回 true，否則返回 false*/ return(S->Next == NULL); }

(4)判滿 注意：鏈棧，不必判斷堆棧是否滿

(5)入棧

鏈棧，不必判斷堆棧是否滿

bool Push(Stack S, ElementType X) { /*將元素 X 壓入堆棧 S */ PtrToSNode TmpCell;TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));TmpCell->Data = X;//頭插法TmpCell->Next = S->Next;S->Next =TmpCell;return true; }

(6)出棧

ElementType Pop(Stack S) ElementType Pop(Stack S) { /*刪除并返回堆棧 S 的棧頂元素*/ PtrToSNode FirstCell;ElementType TopElem;if(IsEmpty(S)){printf("堆棧空！");return ERROR;}else{FirstCell = S->Next;TopElem = FirstCell->Data;S->Next = FirstCell->Next;free(FirstCell);return TopElem; } }/*順序棧 的 出棧 操作*/ {if(IsEmpty(S)) {printf("堆棧空！");return ERROR; /*ERROR 是 ElementType 類型的特殊值，標志錯誤。必須是正常棧元素數據不可能取到的值 */ }elsereturn(S->Data[(S->Top)--]); /*若不空，返回Data[Top]，同時將Top減 1*/ }

3、棧的應用

四、隊列

1、隊列的順序存儲實現

(1) 循環隊列的結構體定義

typedef int Status; typedef int QElemType; /* QElemType類型根據實際情況而定，這里假設為int */ /* 循環隊列的順序存儲結構 */ typedef struct QNode {QElemType data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針，若隊列不空，指向隊列尾元素的下一個位置 */ }SqQueue;

(2)生成空隊列

/* 初始化一個空隊列Q */ Status CreateQueue(SqQueue *Q) {SqQueue *Q = (SqQueue)malloc(sizeof(struct QNode));Q->data = (ElementType*)malloc(MaxSize * sizeof(ElementType));Q->front = Q->rear = 0;return OK; }

(3)判空

隊空的條件是：rear=front

bool IsEmpty(SqQueue *Q) {return(Q->front == Q->rear); }

(4)判滿

隊滿的條件是：(rear+1)%數組的長度等于 front

bool IsFull(SqQueue *Q) {return((Q->rear+1)% MaxSize == Q->front); }

(5)入隊

/* 若隊列未滿，則插入元素e為Q新的隊尾元素 */ Status EnQueue(SqQueue *Q,QElemType e) {if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置， *//* 若到最后則轉到數組頭部 */return OK; }

(6)出隊

/* 若隊列不空，則刪除Q中隊頭元素，用e返回其值 */ Status DeQueue(SqQueue *Q,QElemType *e) {if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置， *//* 若到最后則轉到數組頭部 */return OK; }

2、隊列的鏈式存儲實現

隊列與堆棧一樣，也可以采用鏈式存儲結構，但隊列的頭（front）必須指向鏈表的頭結點，隊列的尾（rear）指向鏈表的尾結點。

(1)隊列的鏈式存儲結構體定義

typedef int Status; typedef int QElemType; /* QElemType類型根據實際情況而定，這里假設為int */ typedef struct QNode /* 結點結構 */ {QElemType data;struct QNode *next; }QNode,*QueuePtr;typedef struct /* 隊列的鏈表結構 */ {QueuePtr front,rear; /* 隊頭、隊尾指針 */ }LinkQueue;

(2)生成空隊列

/* 構造一個空隊列Q */ Status InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));if(!Q->front)exit(OVERFLOW);Q->front->next=NULL;return OK; }

(3)判空

隊空的條件是：rear=front

Status QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear)return TRUE;elsereturn FALSE; }

(4)判滿 鏈式隊列，不必判斷堆棧是否滿

(5)入隊

/* 插入元素e為Q的新的隊尾元素 */ Status EnQueue(LinkQueue *Q,QElemType e) { QueuePtr s=(QueuePtr)malloc(sizeof(QNode));if(!s) /* 存儲分配失敗 */exit(OVERFLOW);s->data=e;s->next=NULL;Q->rear->next=s; /* 把擁有元素e的新結點s賦值給原隊尾結點的后繼，見圖中① */Q->rear=s; /* 把當前的s設置為隊尾結點，rear指向s，見圖中② */return OK; }

(6)出隊

/* 若隊列不空,刪除Q的隊頭元素,用e返回其值,并返回OK,否則返回ERROR */ Status DeQueue(LinkQueue *Q,QElemType *e) {QueuePtr p;if(Q->front==Q->rear)return ERROR;p=Q->front->next; /* 將欲刪除的隊頭結點暫存給p，見圖中① */*e=p->data; /* 將欲刪除的隊頭結點的值賦值給e */Q->front->next=p->next;/* 將原隊頭結點的后繼p->next賦值給頭結點后繼，見圖中② */if(Q->rear==p) /* 若隊頭就是隊尾，則刪除后將rear指向頭結點，見圖中③ */Q->rear=Q->front;free(p);return OK; }

五、棧和隊列操作的特點

相同點不同點

堆棧(FILO)	只允許在端點處插入和刪除元素；	棧是先進后出或者后進先出；棧是只能在表的一端進行插入和刪除操作的線性表
隊列(FIFO)	只允許在端點處插入和刪除元素；	隊列是先進先出；隊列是只能在表的一端進行插入，然后在另外一端進行刪除操作的線性表

六、數組存儲地址的計算

數組類型存儲地址的計算（a是數組首地址，len是每個數組元素所占長度）

一維數組	a[i]的存儲地址：a+i*len
二維數組:a[m] [n]	按行存儲：a+(i * n+j) * len；按列存儲：a+(j * m+i) * len

例子：數組存儲地址的計算示例：
1）已知一維數組a中每個元素占用2個字節，求a[10]的存儲地址？
答：a[10]的存儲地址為：a+10*2=a+20
2）已知二維數組a[4][5]中, 每個元素占用2個字節，求元素a[3][2]按行為主序存儲的存儲地址和按列為主序存儲的存儲地址？
答： 按行存儲：a+(35+2) *2 = a+34
按列存儲：a+(24+3) *2 = a+22

———————樹———————

一、二叉樹

1、定義

二叉樹是每個節點最多有兩個子樹的樹結構。

它有五種基本形態:

• 二叉樹可以是空集;
• 根可以有空的左子樹或右子樹；
• 或者左、右子樹皆為空。

2、結點的度、孩子、雙親、深度、有序樹、無序樹、樹的高度

a.結點、葉子、樹的度

• 結點的度：結點擁有的子樹的數目。
• 葉子：度為零的結點。
• 樹的度：樹中結點的最大的度

b.孩子、雙親、兄弟、子孫、祖先

• 雙親：若一個結點有子樹，該結點稱為子樹根的"雙親"。
• 孩子：子樹的根是該結點的"孩子"。
• 兄弟：有相同雙親的結點互為"兄弟"。
• 子孫：一個結點的所有子樹上的任何結點都是該結點的子孫。
• 祖先：從根結點到某個結點的路徑上的所有結點都是該結點的祖先。

c.無序樹、有序樹、森林

• 無序樹：如果樹中結點的各子樹之間的次序是無次序的，可以交換位置。
• 有序樹：如果樹中結點的各子樹之間的次序是有次序的, 不可以交換位置。
• 森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；刪去根，樹即成為森林。

d.層次、高度

層次：根結點的層次為1，其余結點的層次等于該結點的雙親結點的層次加1。
樹的深度和高度：二叉樹中節點的最大層次稱為二叉樹的深度或高度。

2、性質

性質1：二叉樹第 i 層上最多為 2^(i-1) (i≥1)個結點。

性質2：深度為k的二叉樹至多有2^k - 1個結點(k≥1)。

性質3：具有n個結點的【完全二叉樹】的高度k為(log<2>n) +1）（[log2n]表示不大于與其的整數）

性質4：在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1。

性質5：如果對一棵有 n個結點的完全二叉樹（其深度為(log<2>n) +1）的結點按 【層序】編號（從第1層到第(log<2>n) +1） 層，每層從左到右），對任一結點 i （1≤ i ≤ n）有：

• 如果 i = 1，則結點 i是二叉樹的根，無雙親；如果 i ＞ 1，則其雙親是結點 [i/2];
• 如果2i ＞n，則結點 i 無左孩子（即結點 i 為葉子結點）；否則其左孩子是結點 2i；
• 如果 2i+1 ＞n，則結點 i 無右孩子；否則其右孩子是結點 2i+1。

3、滿二叉樹、完全二叉樹和二叉排序樹

a.滿二叉樹

定義：高度為h，并且由2{h} –1個結點的二叉樹，被稱為滿二叉樹。

b.完全二叉樹

定義：一棵二叉樹中，只有最下面兩層結點的度可以小于2，并且最下一層的葉結點集中在靠左的若干位置上。這樣的二叉樹稱為完全二叉樹。

特點：葉子結點只能出現在最下層和次下層，且最下層的葉子結點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。

c.二叉查找樹

定義：二叉查找樹(Binary Search Tree)，又被稱為二叉搜索樹。左小右大，任意結點的左、右子樹也是二叉查找樹

在二叉查找樹中：
(01) 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
(02) 任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
(03) 任意節點的左、右子樹也分別為二叉查找樹。
(04) 沒有鍵值相等的節點（no duplicate nodes）。

二、靜態查找

1、順序存儲結構

指用一組地址連續的存儲單元依次自上而下、自左至右存儲完全二叉樹的結點元素，即將完全二叉樹上編號為i的結點元素存儲在一維數組下標i－1的分量中。

2、順序查找

從表的一端開始，逐個將記錄的關鍵字和給定值比較，若找到一個記錄的關鍵字與給定值相等，則查找成功；若整個表中記錄均比較過，仍未找到關鍵字等于給定值的記錄，則查找失敗。

缺點：查找表的長度越長，查找效率越低。

優點：簡單、適應面廣，對查找表結構沒有要求，對順序存儲和鏈式存儲都適用。

3、二分查找（也稱“折半查找”，是一棵“二叉排序樹”）

設查找表元素存儲在一維數組r[1,…,n]中，在表中的元素已經按關鍵字遞增方式排序的情況下，

進行[折半查找]的方法是：首先將待查元素的關鍵字（key）值與表r中間位置上（下標為mid）記錄的關鍵字關鍵字進行比較，

• 若相等，則查找成功；
• 若key>r[mid].key,則說明待查記錄只可能在后半個子表r[mid+1,…,n]中；
• 若key<r[mid].key，則說明待查記錄只可能在前半個子表r[1,…,mid-1]中；

這樣逐步縮小范圍，直到查找成功或子表為空時失敗為止。

注意：每次縮小范圍后，改變的下標是哪個

//遞增的方式排序，則折半查找的算法為 //在數組r[low...high],在數組r中找值為key的元素 int Bsearch(int r[],int low,int high,int key) {int mid;while(low <= high){mid = (low + high)/2;if(key == r[mid])return mid;else if(key < r[mid])high = mid-1;elselow = mid+1;}return -1; }//折半查找，遞歸算法 int Bsearch_rec(int r[],int low,int high,int key) {int mid;if(low <= high){mid = (low + high)/2;if(key == r[mid])return mid;else if(key < r[mid])return Bsearch_rec(r,low,mid-1,key);elsereturn Bsearch_rec(r,mid+1,high,key);}return -1; }

折半查找的過程可以用一顆二叉樹來描述，以當前查找區域間的中間位置序號作為根，左半個子表和右半個子表中的記錄序號分別分別作為根的左子樹和右子樹上的結點，這樣構造的二叉樹稱為折半查找判定樹，從樹上可以看出：

? 查找成功時，折半查找的過程恰好走了一條從根結點到被查找結點的路徑，與關鍵字進行比較的次數即為被查找結點在樹中的層數。因此，折半查找判定樹在查找成功時進行比較的關鍵字個數最多不超過樹的深度，而具有n個結點的判定樹的深度為；所以折半查找在查找成功時和給定值進行比較的關鍵字個數最多為。

優點：查找效率更高，但它要求查找表進行順序存儲并按關鍵字進行排序。
缺點：對表進行插入或刪除時，需要移動大量元素。
適用：表不易變動，且又經常進行查找的情況

4、二分查找判定樹ASL計算

折半查找的過程看，可用二叉樹來描述，二叉樹中的每個結點對應有序表中的一個記錄，結點中的值為該記錄在表中的位置。通常稱這個描述折半查找二叉樹的過程稱為折半查找判定樹。

例如：順序存儲的序列{1,2,3,4,5,6,7,8,9,10} 來構建二叉判定樹，計算其ASL

例如：長度為10的折半查找判定樹的具體生成過程：都遵循這個規律，左孩子結點<根結點<右孩子結點 【左小右大】（1）在長度為10的有序表中進行折半查找，不論查找哪個記錄，都必須和中間記錄進行比較，而中間記錄為 （1+10）/2 =5 (注意要取整) 即判定數的的根結點為5，如圖7-2（a）所示。（2）考慮判定樹的左子樹，即將查找區域調整到左半區，此時的查找區間為[1,4],那么中間值為（1+4）/2 =2 (注意要取整) ，所以做孩子根結點為2,如圖7-2（b）所示。（3）考慮判定樹的右子樹，即將查找區域調整到右半區，此時的查找區間為[6,10],那么中間值為（6+10）/2 =8 (注意要取整) ，所以做孩子根結點為8,如圖7-2（c）所示。(4)重復以上步驟，依次去確定左右孩子、

特點：

1.折半查找是一棵二叉排序樹，每個根結點的值都大于左子樹的所有結點的值，小于右子樹所有結點的值。

2.折半查找判定數中的結點都是查找成功的情況，將每個結點的空指針指向一個實際上不存在的結點————外結點，所有外界點都是查找不成功的情況，如圖7-2（e）所示。如果有序表的長度為n,則外結點一定有n+1個。

（1）查找成功的ASL

折半查找判定數中，某結點所在的層數就是即將要比較的次數，整個判定樹代表的有序表的平均查找長度即為查找每個結點的比較次數之和除以有序表的 長度。

ASL成功 = 每層結點所在高度×每層結點數 之和 除以 總結點數

例如：長度為10的有序表的平均查找長度為ASL=(1×1+2×2+3×4+4×3)/10=29/10;

（2）查找不成功的ASL

折半查找判定數中，查找不成功的次數即為查找相應外結點(定義在上方）與內結點的比較次數。整個判定樹代表的有序表的平均查找長度。查找失敗時的有序表的平均查找長度即為查找每個外結點的比較次數之和除以外結點的個數。

ASL失敗 = （每層【補上的】結點所在高度-1）×每層【補上的】結點數 之和 除以 【補上的】總結點數

例如：查找失敗時，長度為10的有序表的平均查找長度為：ASL=(3×5+4×6)/11=39/11;

三、動態查找

1、二叉樹鏈表結構描述如下：

typedef struct TNode *Position; typedef Position BinTree; /* 二叉樹類型 */ struct TNode {/*樹結點定義 */ElementType Data; /* 結點數據*/BinTree Left; /*指向左子樹*/BinTree Right;/*指向右子樹*/ };

二叉鏈表至少包含3個域：數據域 data、左指針域 lchild和右指針域 rchild

指針域： n個結點有2n個指針域。

空指針域：n 個結點的二叉鏈表中含有 n+1 個空指針域。

?

2、二叉搜索（排序、查找）樹的構造過程

(1)構造過程

構造二叉排序樹的過程，就是從空二叉樹開始，逐個向樹中插入節點的過程。

設記錄的關鍵碼序列為：63,90,70,55,67,42,98,83,10,45,58

(2)插入過程算法及其代碼

設待插入節點關鍵碼值為 X ：

（1）先在樹中查找值為 X 的節點，若查找成功，說明節點已存在，無需插入；

（2）若查找失敗，說明節點不存在，則將其插入到樹中

因此，新插入節點一定是作為葉子節點插入的。

BinTree Insert(Bintree BST, ElmentType X) {if(!BST){/*若原來樹為空，生成并返回一個結點的二叉搜索樹*/BST = (BinTree)malloc(sizeof(struct TNode));BST->Data = X;BST->Left = BST->Right = NULL;}else{/*開始查找插入元素的位置*/if(X < BST->Data)BST->Left = Insert(BST->Left, X);/*遞歸插入左子樹*/else if(X > BST->Data)BST->Right = Insert(BST->Right, X);/*遞歸插入右子樹*/}return BST; }

(2)刪除過程算法及其代碼

二叉搜索樹的刪除操作比其它操作更為復雜，要刪除結點在樹中的位置決定了操作所采用的策略。

a.若要刪除的結點是葉子結點

? 可以直接刪除，然后再修改其父結點的指針。

b.若要刪除的結點只有一個孩子結點（該結點不一定是葉結點，可以是子樹的根）

? 刪除之前需要改變父結點的指針，指向要刪除結點的孩子結點。

?

c.若要刪除的結點有左、右兩棵子樹，有兩種選擇：

? 基本原則：保持二叉搜索樹的有序性

? 1、取其右子樹中的最小元素；

? 2、取其左子樹中的最大元素。

(3)查找過程算法及其代碼

BST樹的查找思想:

首先將給定的K值與二叉排序樹的根節點的關鍵字進行比較：

• 若相等，則查找成功；

• 若給定的K值小于BST樹的根節點的關鍵字：繼續在該節點的左子樹上進行查找；

• 若給定的K值大于BST樹的根節點的關鍵字：繼續在該節點的右子樹上進行查找。

a.二叉搜索樹的遞歸查找函數

在二叉排序樹上進行查找，則是從根結點出發走了一條從根到待查結點的路徑；

若查找不成功，則是從根結點出發走了一條從跟到某一葉結點的路徑。

Position Find(BinTree BST,ElementType X) {if(!BST->Data)return NULL;/* 查找失敗 */if(X > BST->Data)return Find(BST->Right, X);/* 在 右子樹 中遞歸查找 */else if(X < BST->Data)return Find(BST->Left, X);/* 在 左子樹 中遞歸查找 */elsereturn BST;/* 在當前結點查找成功，返回當前結點的地址*/ }

b.迭代查找算法

由于非遞歸函數的執行效率高，一般采用非遞歸的迭代來實現查找。很容易將遞歸函數改為迭代函數

while循環 代替 Find遞歸調用即可

Position Find(BinTree BST,ElementType X) {while(BST){if(X > BST->Data)BST = BST->Right;/* 向 右子樹 中移動，繼續查找 */else if(X < BST->Data)BST = BST->Left; /* 向 右子樹 中移動，繼續查找 */else /* X == BST->Data;*/break;/* 在當前結點查找成功，跳出循環 */} return BST;/* 返回找到的結點地址，或是NULL */ }

(4)查找最大值和最小值

根據二叉搜索樹的性質，最小元素一定是在樹的最左分支的端點上。最左分支的端點：最左分支上無左孩子的結點。

最大元素一定在最右分支的端結點上。

• 從根結點開始，當其不為空時，沿左分支或者右分支逐個判斷各結點的指針，直到遇到空指針為止。
• 當左分支逐層推下來查找到的是最小元素。
• 反之，當右分支逐層推下來查找到的是最大元素。

a.最小元素的遞歸函數

Position FindMin(BinTree BST) { /* 最小元素在最左端點 */if(!BST)return NULL;/* 空的二叉搜素樹，返回NULL */else if(!BST->Left)return BST; /* 找到最左端點并返回 */elsereturn FindMin(BST->Left); /*沿左分支遞歸查找 */ }

b.查找最大元素的迭代函數

Position FindMax(BinTree BST) {if(BST)while(BST->Right);BST = BST->Right; /*沿右分支一直向下，直到最右端點 */return BST; }

四、二叉樹的遍歷

指按照某種次序訪問二叉樹的所有結點，并且每個結點僅訪問一次，得到一個線性序列。

1、先序遍歷

（1）訪問根結點
（2）先序遍歷左子樹
（3）先序遍歷右子樹

-中序、后序遍歷相似

先序遍歷：A → B → D → C
中序遍歷：B → D → A → C
后續遍歷：D → B → C → A
層序遍歷：A → B → C → D

void PreOrderTraverse(BiTree T) //鏈式二叉樹先序遍歷遞歸算法 {if (T != NULL){printf_s("%d ", T->data); //訪問根結點PreOrderTraverse(T->lchild); //先序遍歷左子樹PreOrderTraverse(T->rchild); //先序遍歷右子樹} }//鏈式二叉樹中序遍歷遞歸算法 void InOrderTraverse(BiTree T) {if (T != NULL) {InOrderTraverse(T->lchild);printf_s("%d ", T->data);InOrderTraverse(T->rchild);} }//鏈式二叉樹后序遍歷遞歸算法 void PostOrderTraverse(BiTree T) {if (T != NULL) {PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf_s("%d ", T->data);} }

2、層序遍歷(隊列實現）

仔細看看層序遍歷過程，其實就是從上到下，從左到右依次將每個數放入到隊列中，然后按順序依次打印就是想要的結果。

實現過程

• 從隊列中取出一個元素；
• 訪問該元素所指結點；
• 若該元素所指結點的左、右孩子結點非空，則將其左、右孩子的指針順序入隊。

不斷執行這三步操作，直到隊列為空，再無元素可取，二叉樹的程序遍歷就完成了。

void LevelorDerTraversal(BinTree BT) {Queue Q;BinTree T;if(!BT)return;/* 若是空樹則直接返回 */Q = CreatQueue(); /* 創建空隊列 */AddQ(Q, BT);while(!IsEmpty(Q)){T = DeteleQ(Q);printf("%d",T->Data); /* 訪問取出隊列的結點 */if(T->Left)AddQ(Q, T->Left);if(T->Right)AddQ(Q, T->Right);} }

3、由遍歷序列還原二叉樹

已知先序遍歷和中序遍歷，可以還原二叉樹；
已知中序遍歷和后序遍歷，可以還原二叉樹；
已知先序遍歷和后序遍歷，不可以還原二叉樹.

a.已知先序遍歷和中序遍歷還原二叉樹

算法思路：
1、根據先序遍歷結果確定根節點。先序遍歷的第一個節點為根節點。
2、 在中序遍歷結果中找到根節點，根節點左側的部分為左子樹節點，根節點右側的部分為右子樹節點。
3、 將中序遍歷的結果按根節點分為兩部分，迭代的執行第一步和第二步，直到還原整個二叉樹。

例如：已知先序遍歷的結果為：ABDHIEJKCFLMGNO,中序遍歷的結果為：HDIBJEKALFMCNGO

則二叉樹為以下結構：

其后序遍歷結果為：HIDJKEBLMFNOGCA

b.已知后序遍歷和中序遍歷還原二叉樹

算法思路：
1、根據后序遍歷結果確定根節點。
后序遍歷的最后一個節點為根節點。
2、在中序遍歷結果中找到根節點，根節點左側的部分為左子樹節點，根節點右側的部分為右子樹節點。
3、將中序遍歷的結果按根節點分為兩部分，迭代的執行第一步和第二步，直到還原整個二叉樹。

例如：已知后序遍歷的結果為：HIDJKEBLMFNOGCA,中序遍歷的結果為：HDIBJEKALFMCNGO

則二叉樹為以下結構：

其先序遍歷結果為：ABDHIEJKCFLMGNO

五、遞歸遍歷算法的應用

1、求二叉樹的深度

//求樹的深度 int TreeDeep(BiTree T) {int deep = 0;if (T != NULL) {int leftDeep = TreeDeep(T->lchild);int rightDeep = TreeDeep(T->rchild);deep = leftDeep >= rightDeep ? leftDeep + 1 : rightDeep + 1;}return deep; }

2、求二叉樹的葉子樹

//求葉子樹 int LeafCount(BinTree T,int num) {if(T){if(!T->Left && !T->Right){nm++;}TreeDeep(T->lchild, num);TreeDeep(T->rchild, num);}return num; }

3、交互（換）左、右子樹

void Swap(BiTree *&right,BiTree *&left) {BiTree *temp=right;right=left;left=temp; }void SwapSubtrees(BiTree *T) {if(!T)return ;SwapSubtrees(T->rchild);SwapSubtrees(T->lchild);Swap(T->rchild,T->lchild); }

六、靜態查找和動態查找的根本區別

• 上述基于二叉排序樹的動態查找，它的基本原理和基于線性表的靜態二分查找很相似，都是利用有序性不斷縮小查找空間。

• 而之所以有靜態和動態之分，主要是為了適應不同的應用需求。

適合用于

靜態查找	數據一旦建立好，不需要或者很少進行 刪除 和 插入 操作
動態查找	頻繁的數據變化，插入 和 刪除 是基本操作

七、樹/森林與二叉樹的轉換

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

由于二叉樹是有序的，為了避免混淆，對于無序樹，我們約定樹中的每個結點的孩子結點按從左到右的順序進行編號。

將樹轉換成二叉樹的步驟是：
（1）加線。就是在所有兄弟結點之間加一條連線；
（2）抹線。就是對樹中的每個結點，只保留他與第一個孩子結點之間的連線，刪除它與其它孩子結點之間的連線；
（3）旋轉。就是以樹的根結點為軸心，將整棵樹順時針旋轉一定角度，使之結構層次分明。

2、森林轉換為二叉樹

森林是由若干棵樹組成，可以將森林中的每棵樹的根結點看作是兄弟，由于每棵樹都可以轉換為二叉樹，所以森林也可以轉換為二叉樹。

將森林轉換為二叉樹的步驟是：
（1）先把每棵樹轉換為二叉樹；
（2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹的根結點的右孩子結點，用線連接起來。當所有的二叉樹連接起來后得到的二叉樹就是由森林轉換得到的二叉樹。

3、二叉樹轉換為樹

二叉樹轉換為樹是樹轉換為二叉樹的逆過程，其步驟是：
（1）若某結點的左孩子結點存在，將左孩子結點的右孩子結點、右孩子結點的右孩子結點……都作為該結點的孩子結點，將該結點與這些右孩子結點用線連接起來；
（2）刪除原二叉樹中所有結點與其右孩子結點的連線；
（3）整理（1）和（2）兩步得到的樹，使之結構層次分明。

4、二叉樹轉換為森林

二叉樹轉換為森林比較簡單，其步驟如下：
（1）先把每個結點與右孩子結點的連線刪除，得到分離的二叉樹；
（2）把分離后的每棵二叉樹轉換為樹；
（3）整理第（2）步得到的樹，使之規范，這樣得到森林。

5、轉換以后的特點：

? (1、 根據樹與二叉樹的轉換關系以及二叉樹的遍歷定義可以推知：

• 樹的先序遍歷與其轉換的相應的二叉樹的先序遍歷的結果序列相同；

• 樹的后序遍歷與其轉換的二叉樹的中序遍歷的結果序列相同；

• 樹的層序遍歷與其轉換的二叉樹的后序遍歷的結果序列相同。

（2、 由森林與二叉樹的轉換關系以及森林與二叉樹的遍歷定義可知：

? 森林的先序遍歷和中序遍歷與所轉換得到的二叉樹的先序遍歷和中序遍歷的結果序列相同。

八、線索二叉樹

傳統的二叉鏈表僅能體現出一種父子關系，不能直接得到結點在遍歷中的前驅或后繼。引入【線索二叉樹】正是為了加快查找結點前驅和后繼的速度。
（1、定義：

• 前驅與后繼：在二叉樹的先序、中序或后序遍歷序列中的兩個相鄰的結點；
• 線索：指向前驅或后繼的結點的指針；
• 線索二叉樹：加上線索的二叉鏈表的二叉樹；
• 線索化：對二叉樹按某個遍歷次序使其變為線索二叉樹的過程。

（2、規定：【口訣：左前右后，0孩1前后】

• 若無左子樹，令lchild指向其前驅結點；
• 若無右子樹，令rchild執行指向其后繼結點
• 增加兩個標志域標識是指左/右孩子還是指向前驅/后繼。

1、存儲結構

//線索二叉樹存儲結構 typedef struct ThreadNode{char data;struct ThreadNode *lchild, *rchild; // 左右孩子指針int ltag, rtag; // 左右線索標志 }ThreadNode, *ThreadTree;

2、如何判斷是孩子還是線索

其標志位含義如下： 【口訣：左前右后，0孩1前后】

• 這種加上線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹。

• 根據線索性質的不同， 線索二叉樹可分為前序線索二叉樹、 中序線索二叉樹和后序線索二叉樹三種。

3、三種遍歷

因為線索化后， 各個結點指向有變化， 因此原來的遍歷方式不能使用， 需要使用新的方式遍歷線索化二叉樹。

中序線索二叉樹的結點中隱含了線索二叉樹的前驅和后繼信息。

在對其遍歷時，需要找到第一個具有前驅結點的左結點，然后依次找結點的后繼。

在中序線索二叉樹中找結點后繼的規律是:

• 若其右標志為1，則右鏈為線索，指示其后繼;
• 否則遍歷右子樹中第一個訪問的結點（右子樹中最左下的結點）為其后繼。

void InOrderTraverse(BiThrTree T){ // 中序輸出if(T){InOrderTraverse(T->lchild); //中序遍歷左子樹cout<< T->data;InOrderTraverse(T->rchild); //中序遍歷右子樹} }

九、哈夫曼樹

1、帶權路徑長度WPL

2、哈夫曼樹的構造（算法）

構造 Huffman 樹的基本思想：權值大的結點用短路徑，權值小的結點用長路徑。

構造過程

3、哈夫曼樹的性質

4、哈夫曼編碼

———散列查找———

一、散列查找

1、基本概念

• 散列函數

? 在進行查找時，在記錄的存儲位置與它的關鍵字之間建立一個確定的對應關系h,以線性表中每個元素的關鍵字K為自變量，通過函數h(K)計算出該元素的存儲位置，我們將h函數稱為散列函數或哈希函數。h(K)的值稱為散列地址或哈希地址。

• 沖突

? 在實際應用中，通常可能出現一個待插入元素的散列地址單元已被占用情況，使得該元素無法直接存入此單元，這種情況稱為沖突。

• 同義詞

  ? 具有不同關鍵字而具有相同散列地址的元素稱為同義詞，即key1≠key2，但h(key1)=h(key2)。由同義詞引起的沖突稱作同義詞沖突。

• 裝填因子(α)

  指散列表中已存入的元素數n與散列表空間大小m的比值,即：α=n/m。當α越小時，沖突可能性就越小，但同時，存儲空間利用率就越低。

散列表：根據設定的哈希函數及處理沖突的方法將一組關鍵字映象到一個有限的連續的地址集上，即把記錄存放在表中映象的位置上，這種表便稱為散列表(哈希表)。

• 一個散列表的好壞與三個因素有關：1.裝填因子 2、所采用的散列函數 3、解決沖突的方法

假定一個線性表為A=(18,75,60,43,54,90,46)，選取散列函數為：h(K)=K%m 取m=13
則得每個元素散列地址：
h(18)=18 % 13=5
h(75)=75 % 13=10
h(60)=60 % 13=8
h(43)=43 % 13=4
h(54)=54 % 13=2
h(90)=90 % 13=12
h(46)=46 % 13=7
根據散列地址，實現元素的存儲映象H[m]：

0123456789101112

H			54		43	18		46	60		75		90

例：如向下表中再插入元素70時，70%13=5，則出現了沖突

0123456789101112

H			54		43	18		46	60		75		90

2、散列函數

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-OtlYI1uv-1641217649135)(myReviewPicture/散列函數.png)]

構造散列函數的目標是使散列地址盡可能均勻分布在散列空間上，同時使計算盡可能簡單，以節省計算時間。

（1、關鍵詞為數字時：

a.直接定址法

b.除留余數法(常用)

c.數字分析法

分析數字關鍵字在各位上的變化情況，取比較隨機的位作為散列地址，如電話號碼、身份證號碼某幾位會比較隨機；

**例：**有一組關鍵字如下：

? 92326875

? 92739628

? 92343634

? 92706816

? 92774638

? 92381262

? 92394220

通過分析：每個關鍵字從左到右第1、2、3位和第6位取值較集中，不宜作散列地址，其余的第4、5、7、8位取值分散，可以選擇，若取最后兩位作散列地址，得：(2,75,28,34,16,38,62,20)

d.平方取中法

key取平方再取中間幾位

（2、關鍵詞為字符時：

a、ASCII碼加和法

h(key)=(求和key[i])mod TableSize

b、前3個字符移位法

h(key)=(key[0]*27*27+key[1]*27+key[2])mod TableSize

二、處理沖突的方法

1、開放定址法

a.線性探測法

注意：查找某個值時，用散列函數計算完后，如果那個結果位置上的數字與關鍵詞不一樣時，并不能斷定關鍵詞不存在，還應該按照沖突解決策略繼續找，直到找到空位置了還沒找到，才能斷定該關鍵詞不存在。

b、平方探測（二次探測）

舉例：h(key)=key mod 11;

**注意：**取素數是為了減少公因子（減少沖突）

c.在散列法

2、分離鏈接法

———————————————圖————————————————

一、圖的基本概念

集合只有同屬于一個集合；線性結構存在一對一的關系；樹形結構存在一對多的關系；圖狀結構存在多對多的關系。

1、簡單圖

簡單圖滿足以下兩條內容：

1）不存在重復邊

2）不存在頂點到自身的邊

2、完全圖

任意兩頂點之間都存在邊

3、連通分量

在無向圖中，兩頂點有路徑存在，就稱為連通的。若圖中任意兩頂點都連通，同此圖為連通圖。無向圖中的極大連通子圖稱為連通分量。

4、強連通分量

在有向圖中，兩頂點兩個方向都有路徑，兩頂點稱為強連通。

若任一頂點都是強連通的，稱為強連通圖。有向圖中極大強連通子圖為有向圖的強連通分量。

5.頂點的度、入度和出度

頂點的度為以該頂點為一個端點的邊的數目。

對于無向圖，頂點的邊數為度，度數之和是頂點邊數的 2 倍。

對于有向圖，入度是以頂點為終點，出度相反。有向圖的全部頂點入度之和等于出度之和且等于邊數。頂點的度等于入度與出度之和

注意：入度與出度是針對有向圖來說的

二、圖的存儲

1、數組（鄰接矩陣）表示法

• 建立一個頂點表（記錄各個頂點信息）和一個鄰接矩陣（表示各個頂點之間關系）。

• 設圖A=（V，E）有n個頂點，則

• 圖的鄰接矩陣是一個二位數組A.arcs[n] [n]，定義為：

??¨è??é????’?
￥????‰????è?°

a.無向圖的鄰接矩陣表示法

分析1：無向圖的鄰接矩陣是對稱的；
分析2：頂點i的度=第i行（列）中1的個數；
特別：完全圖的鄰接矩陣中，對角元素為0，其余1。

b.有向圖的鄰接矩陣表示法

注：在有向圖的鄰接矩陣中，
第 i 行含義：以結點vi為尾的弧（即出度邊）
第 i 列含義：以結點vi為頭的弧（即入度邊）
分析1：有向圖的鄰接矩陣可能是不對稱的；
分析2：頂點的出度 = 第 i 行元素之和
頂點的入度 = 第 i 列元素之和
頂點的度 = 第 i 行元素之和 + 第 i 列元素之和

c.有權圖（網）的鄰接矩陣表示法

2.鄰接表（順序存儲與鏈式存儲結合）

a.無向圖的鄰接表

b.有向圖的鄰接表與逆鄰接表

c.帶權值的網圖

三、圖的遍歷

1、深度優先遍歷算法

深度優先搜索類似于樹的先序遍歷。

其基本思想是：

• 首先訪問起始頂點v，然后由v出發，訪問與v 鄰接且未被訪問的任一頂點w1，再訪問與w1 鄰接且未被訪問的任一頂點W2……重復上述操作。

• 當不能再繼續向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續上述搜索過程，直至圖中所有頂點均被訪問過為止。

從頂點a 出發，進行深度優先遍歷，可以得到的一種頂點序列為：a e d f c b

2、廣度優先遍歷算法

廣度優先搜索類似于二叉樹的層序遍歷算法。

其基本思想是：

• 首先訪問起始頂點v，接著由ν出發，依次訪問v 的各個未訪問過的鄰接頂點W1，W2，…，Wi，然后依次訪問W1，W2，…，Wi的所有未被訪問過的鄰接頂點；
• 再從這些訪問過的頂點出發，訪問它們所有未被訪問過的鄰接頂點，直至圖中的所有頂點都被訪問過為止。
• 若此時圖中尚有頂點未被訪問，則另選圖中的一個未被訪問的頂點作為始點，重復上述過程，直至圖中所有頂點都被訪問到為止。

從頂點1 出發，按照廣度優先規則遍歷，可以得到的一種頂點序列是： 1234576

二、最小生成樹

1、性質

2、Prim算法

3、Kruskal算法

三、拓撲排序

四、最短路徑

迪杰斯特拉算法

通過迪杰斯特拉算法計算圖G中的最短路徑時，需要指定起點s。

? 此外，需要引進兩個集合S和U。

• S的作用：記錄已求出最短路徑的頂點（以及相應的最短路徑長度），
• U的作用：記錄還未求出最短路徑的頂點（以及該頂點到起點s的距離）。
• 初始時，S中只有起點s；
• U中是除s之外的頂點，并且U中頂點的路徑是“起點s到該頂點的路徑”。
• 然后，從U中找到路徑最短的頂點，并將其加入到S中；
  • 接著，更新U中的頂點和頂點對應的路徑。
  • 然后，再從U中找到路徑最短的頂點，并將其加入到S中；接著，更新U中的頂點和頂點對應的路徑。
  • 重復上述操作，直到遍歷完所有頂點。

具體過程

1、初始化，所有頂點的距離初始化為無窮大（INFINITY)

2、選定點A，更新（A-A距離設為0)

3、S集合為{A,B}，考察B的所有鄰接點

為什么選定B加入集合S？
因為不可能還有其他路徑比2還短，我不管經過C到B還是D到B都不可能是路徑小于2，所以我們得到了A->B的最短路徑

做完這一步，下一步加入集合S的是D
因為目前A->D的路徑長度最短，為3（我已經知道了A直接到D和A經過B到D的路徑長度）
如果A->B->X->D小于min{A->D,A->B->D},那么A->B->X小于min{A->D,A->B->D}，那么加入集合的應該是X，這是矛盾的（接下來的操作都是一樣的道理

4、S集合為{A,B,D}，在U中沒有D的鄰接點，不操作

5、S集合為{A,B,D,C}，在U中沒有C的鄰接點，不操作

6、S集合為{A,B,D,C,F}，更新

7、S集合為{A,B,D,C,F,E}，在U中沒有E的鄰接點，不操作

8、S集合為{A,B,D,C,F,E,G}，在U中沒有G的鄰接點，不操作

9、最終結果如上圖。

———排序———

一、排序的類別

1、插入排序

基本思想：

【1】直接插入排序

（1、基本思想：

1）、將待排序的一組序列（有N個數）分為已排好的和未排好的 2個部分；

2）、初始狀態時，已排序序列僅包含第1 個元素，未排序序列中的元素為除去第1 個元素意外的N-1 個元素；

3）、此后，將未排序序列中的元素逐一插入到已排序的序列中；

4）、如此往復，經過N-1 次插入后，未排序序列中元素個數為0 ，則排序完成。

（2、執行過程

（3、時空效率及穩定性

【2】希爾排序

（1、基本思想：

1）、將帶排序序列的一組元素按一定間隔分為若干序列分別進行插入排序；

2）、開始時設置的“間隔”較大，在每輪排序中，將**”間隔“逐步縮小**

3）、直到“間隔”為 1，也就到了最后一步，做簡單插入排序。

（2、執行過程

（3、時空效率及穩定性

2、交換排序

基本思想：

【1】冒泡排序

（1、基本思想：

（2、執行過程

（3、時空效率及穩定性

【2】快速排序

（1、基本思想：

1)、將未排序元素根據一個作為基準的“主元（pivot）分為兩個子序列；

2）、其中一個子序列的記錄均大于“主元”，另一個序列則均小于“主元；

3）、遞歸地對兩個子序列用類似的方法進行排序。

（2、執行過程

（3、時空效率及穩定性

3、選擇排序

基本思想：

【1】簡單選擇排序

（1、基本思想：

1）、在未排序的序列中選出最小元素和序列的首位元素交換，

2）、再在剩下的排序序列中再選出最小元素與序列的第2 個位置元素交換

3）、以此類推，最后形參從小到大的已排序序列。

（2、執行過程

（3、時空效率及穩定性

【2】堆排序

（1、基本思想：

1）、利用最大堆（或最小堆）輸出堆頂元素，即最大值（或最小值）；

2）、將剩余元素重新生成最大堆（或最小堆），繼續輸出堆頂元素；

3）、重復此過程，知道全部元素都已輸出，得到的輸出元素序列即為有序序列

（2、執行過程要點

<1>初始化堆的過程

下面是構建初始堆的過程

下面是堆排序的過程

（3、時空效率及穩定性

4、歸并排序

二、各種排序的比較

口訣：快選堆希不穩，選堆歸基不變

不穩：說的是 算法不穩定

不變：說的是 關于移動次數和關鍵字順序無關的排序

總結

以上是生活随笔為你收集整理的【数据结构】【期末复习】知识点总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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