數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)全面總結(jié)—精華版

1、第1章 緒論 內(nèi)容提要： 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作。數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容： 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。數(shù)據(jù)所有能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的符號(hào)的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義。數(shù)據(jù)對(duì)象具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為： Data_Structure=（D, R）數(shù)據(jù)類型是一個(gè)值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型由用戶定義的一個(gè)數(shù)學(xué)模型與定義在該模型上的一組操作， 它

2、由基本的數(shù)據(jù)類型構(gòu)成。 算法的定義及五個(gè)特征。算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計(jì)算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性 算法設(shè)計(jì)要求。正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求 算法分析。時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性學(xué)習(xí)重點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲(chǔ)）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作（運(yùn)算） 。 用計(jì)算語(yǔ)句頻度來(lái)估算算法的時(shí)間復(fù)雜度。第2章 線性表內(nèi)容提要： 線性表的邏輯結(jié)構(gòu)定義，對(duì)線性表定義的操作。 線性表的定義：用數(shù)據(jù)元素的有限序列表示 線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)定義：把邏輯

3、上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu): 其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。通過(guò)指針來(lái)實(shí)現(xiàn)！ 線性表的操作在兩種存儲(chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：修改、插入、刪除、查找、排序1) 修改通過(guò)數(shù)組的下標(biāo)便可訪問(wèn)某個(gè)特定元素并修改之。 核心語(yǔ)句: Vi=x; 順序表修改操作的時(shí)間效率是 O(1)2) 插入在線性表的第i個(gè)位置前插入一個(gè)元素 實(shí)現(xiàn)步驟： 將第n至第i 位的元素向后移動(dòng)一個(gè)位置； 將要插入的元素寫到第i個(gè)位置； 表長(zhǎng)加1。 注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿? 應(yīng)當(dāng)符合條件： 1in+1 或 i=

4、1, n+1 核心語(yǔ)句：for (j=n; j>=i; j-)aj+1=a j ; a i =x; n+; 插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2÷（n+1）n/2O(n) 3) 刪除刪除線性表的第i個(gè)位置上的元素 實(shí)現(xiàn)步驟： 將第i+1 至第n 位的元素向前移動(dòng)一個(gè)位置； 表長(zhǎng)減1。 注意：事先需要判斷，刪除位置i 是否合法? 應(yīng)當(dāng)符合條件：1in 或 i=1, n 核心語(yǔ)句：for ( j=i+1; j<=n; j+ )aj-1=aj; n-; 順序表刪除一元素的時(shí)間效率為:T（n)=(n-1)/2 O(n) 順序表插入、刪除算法的平均空間復(fù)雜度為O(1)單鏈表：（

5、1）用單鏈表結(jié)構(gòu)來(lái)存放26個(gè)英文字母組成的線性表（a，b，c，z）,請(qǐng)寫出C語(yǔ)言程序。#include<stdio.h>#include<stdlib.h>typedef struct nodechar data; struct node *next;node; node *p,*q,*head; /一般需要3個(gè)指針變量int n ; / 數(shù)據(jù)元素的個(gè)數(shù)int m=sizeof(node); /*結(jié)構(gòu)類型定義好之后，每個(gè)node類型的長(zhǎng)度就固定了， m求一次即可*/void build( ) /字母鏈表的生成。要一個(gè)個(gè)慢慢鏈入 int i;head=(node*)mal

6、loc(m); /m=sizeof(node) 前面已求出p=head;for( i=1; i<26; i+) /因尾結(jié)點(diǎn)要特殊處理，故i26 p->data=i+a-1; / 第一個(gè)結(jié)點(diǎn)值為字符ap->next=(node*)malloc(m); /為后繼結(jié)點(diǎn)“挖坑”！p=p->next； /讓指針變量P指向后一個(gè)結(jié)點(diǎn)p->data=i+a-1; /最后一個(gè)元素要單獨(dú)處理p->next=NULL ; /單鏈表尾結(jié)點(diǎn)的指針域要置空！ void display() /字母鏈表的輸出 p=head; while (p) /當(dāng)指針不空時(shí)循環(huán)（僅限于無(wú)頭結(jié)點(diǎn)的情況）

7、 printf("%c",p->data); p=p->next; /讓指針不斷“順藤摸瓜” （2） 單鏈表的修改(或讀?。┧悸罚阂薷牡趇個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針p， 然后才能：p>data=new_value 讀取第i個(gè)數(shù)據(jù)元素的核心語(yǔ)句是：Linklist *find(Linklist *head ,int i) int j=1; Linklist *p; P=head->next; While(p!=NULL)&&(j<i) p=p->next; j+; return p; 3. 單鏈表的插入

8、鏈表插入的核心語(yǔ)句：Step 1：s->next=p->next;Step 2：p->next=s ；6. 單鏈表的刪除刪除動(dòng)作的核心語(yǔ)句（要借助輔助指針變量q）：q = p->next; /首先保存b的指針，靠它才能找到c；p->next=q->next; /將a、c兩結(jié)點(diǎn)相連，淘汰b結(jié)點(diǎn)；free(q) ； /徹底釋放b結(jié)點(diǎn)空間7. 雙向鏈表的插入操作：設(shè)p已指向第 i 元素，請(qǐng)?jiān)诘?i 元素前插入元素 x： ai-1的后繼從 ai ( 指針是p)變?yōu)?x（指針是s) : s->next = p ; p->prior->next = s

9、 ; ai 的前驅(qū)從 ai-1 ( 指針是p->prior)變?yōu)?x ( 指針是s); s->prior = p ->prior ; p->prior = s ; 8. 雙向鏈表的刪除操作：設(shè)p指向第 i 個(gè)元素，刪除第 i 個(gè) 元素后繼方向：ai-1的后繼由 ai ( 指針p)變?yōu)?ai+1(指針 p ->next ); p ->prior->next = p->next ; 前驅(qū)方向：ai+1的前驅(qū)由 ai ( 指針p)變?yōu)閍i-1 (指針 p -> prior ); p->next->prior = p ->prio

10、r ; 數(shù)組的邏輯結(jié)構(gòu)定義及存儲(chǔ)數(shù)組： 由一組名字相同、下標(biāo)不同的變量構(gòu)成N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n維數(shù)組可以看成是由若干個(gè)n1維數(shù)組組成的線性表。存儲(chǔ)：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存入存儲(chǔ)器中。 在二維數(shù)組中，我們既可以規(guī)定按行存儲(chǔ)，也 可以規(guī)定按列存儲(chǔ)。設(shè)一般的二維數(shù)組是Ac1.d1, c2.d2，則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：二維數(shù)組列優(yōu)先存儲(chǔ)的通式為： 稀疏矩陣（含特殊矩陣）的存儲(chǔ)及運(yùn)算。 稀疏矩陣：矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）學(xué)習(xí)重點(diǎn)：  線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。在順序存儲(chǔ)

11、結(jié)構(gòu)中，元素存儲(chǔ)的先后位置反映出這種線性關(guān)系，而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，是靠指針來(lái)反映這種關(guān)系的。 順序存儲(chǔ)結(jié)構(gòu)用一維數(shù)組表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。 鏈表操作中應(yīng)注意不要使鏈意外“斷開”。因此，若在某結(jié)點(diǎn)前插入一個(gè)元素，或刪除某元素，必須知道該元素的前驅(qū)結(jié)點(diǎn)的指針。 掌握通過(guò)畫出結(jié)點(diǎn)圖來(lái)進(jìn)行鏈表（單鏈表、循環(huán)鏈表等）的生成、插入、刪除、遍歷等操作。 數(shù)組（主要是二維）在以行序/列序?yàn)橹鞯拇鎯?chǔ)中的地址計(jì)算方法。 稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)。 稀疏矩陣的十字鏈表存儲(chǔ)方法。補(bǔ)充重點(diǎn)：1.每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域(鏈域)2.在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)

12、的存儲(chǔ)位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。 3.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？ 頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放表長(zhǎng)度等附加信息，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。4. 如何表示空表？（1）無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；（2）有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。5.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？ 因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。6.sizeof(x) 計(jì)算變量x的長(zhǎng)度（字節(jié)數(shù)）； malloc(m)

13、 開辟m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址； free(p) 釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。7. 鏈表的運(yùn)算效率分析：（1）查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。（2） 插入和刪除 因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是 O(n)。例：在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為 O（n）8. 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別和優(yōu)缺點(diǎn)？ 順序存儲(chǔ)時(shí)，邏輯上相鄰的數(shù)據(jù)元素，其

14、物理存放地址也相鄰。順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作； 鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。 若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9. 判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單”，對(duì)嗎？答：對(duì)的。因?yàn)?數(shù)組中各元素具有統(tǒng)一的類型； 數(shù)

15、組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。10. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、列下標(biāo) 和 元素值 。 11. 寫出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。解：介紹3種存儲(chǔ)形式。法1：用線性表表示： （( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7)）法2：用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算方法：

16、每個(gè)非0元素占用5個(gè)域法3：用三元組矩陣表示：稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能代碼：1.用數(shù)組V來(lái)存放26個(gè)英文字母組成的線性表（a，b，c，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語(yǔ)言程序。char V30;void build() /字母線性表的生成，即建表操作 int i; V0='a' for( i=1; i<=n-1; i+ ) Vi=Vi-1+1; void display( ) /字母線性表的顯示，即讀表操作 int i; for( i=0; i<=n-1; i+ ) printf( "%c", vi ); printf(

17、 "n " );void main(void) /主函數(shù)，字母線性表的生成和輸出 n=26; / n是表長(zhǎng)，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V的實(shí)際下標(biāo) build( ); display( );第3章 棧和隊(duì)列內(nèi)容提要：  從數(shù)據(jù)結(jié)構(gòu)角度來(lái)講，棧和隊(duì)列也是線性表，其操作是線性表操作的子集，屬操作受限的線性表。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。 棧的定義及操作。棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，該端稱為棧的頂端。 插入元素到棧頂?shù)牟僮?，稱為入棧。 從棧頂刪除最后一個(gè)元素的操作，稱為出棧。 對(duì)于向上生成的堆棧: 入?？谠E：堆棧指針top

18、 “先壓后加” : Stop+=an+1 出棧口訣：堆棧指針top “先減后彈” : e=S-top 棧的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實(shí)現(xiàn)棧的操作。 順序棧入棧函數(shù)PUSH（）status Push(ElemType e) if(top>M)上溢 else stop+=e;順序棧出棧函數(shù)POP()status Pop( ) if(top=L) 下溢 else e=s-top; return(e); 隊(duì)列的定義及操作，隊(duì)列的刪除在一端（隊(duì)尾），而插入則在隊(duì)列的另一端（隊(duì)頭）。因此在兩種存儲(chǔ)結(jié)構(gòu)中，都需要隊(duì)頭和隊(duì)尾兩個(gè)指針。隊(duì)列：只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的

19、線性表。鏈隊(duì)列結(jié)點(diǎn)類型定義： typedef Struct QNode QElemType data; /元素 Struct QNode *next; /指向下一結(jié)點(diǎn)的指針 Qnode , * QueuePtr ;鏈隊(duì)列類型定義： typedef struct QueuePtr front ; /隊(duì)首指針 QueuePtr rear ; /隊(duì)尾指針 LinkQueue;鏈隊(duì)示意圖： 空鏈隊(duì)的特征：front=rear 鏈隊(duì)會(huì)滿嗎？一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！ 入隊(duì)（尾部插入）：rear->next=S; rear=S; 出隊(duì)（頭部刪除）：front->next

20、=p->next;2. 順序隊(duì)順序隊(duì)類型定義：#define QUEUE-MAXSIZE 100 /最大隊(duì)列長(zhǎng)度 typedef struct QElemType *base; /隊(duì)列的基址 int front; /隊(duì)首指針 int rear; /隊(duì)尾指針 SqQueue建隊(duì)核心語(yǔ)句：q . base=(QElemType *)malloc(sizeof (QElemType ）* QUEUE_MAXSIZE; /分配空間順序隊(duì)示意圖：循環(huán)隊(duì)列：隊(duì)空條件 : front = rear (初始化時(shí)：front = rear )隊(duì)滿條件： front = (rear+1) % N (N=ma

21、xsize)隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）：L=（Nrearfront）% N 1） 初始化一個(gè)空隊(duì)列Status InitQueue ( SqQueue &q ) /初始化空循環(huán)隊(duì)列 q q . base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE); /分配空間if (!q.base) exit(OVERFLOW);/內(nèi)存分配失敗，退出程序 q.front =q.rear=0; /置空隊(duì)列 return OK; /InitQueue;2） 入隊(duì)操作Status EnQueue(SqQueue &q, QElemTyp

22、e e)/向循環(huán)隊(duì)列 q 的隊(duì)尾加入一個(gè)元素 e if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front ) return ERROR ; /隊(duì)滿則上溢，無(wú)法再入隊(duì) q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; q.base q.rear = e; /新元素e入隊(duì) return OK; / EnQueue;3） 出隊(duì)操作Status DeQueue ( SqQueue &q, QElemType &e) /若隊(duì)列不空，刪除循環(huán)隊(duì)列q的隊(duì)頭元素， /由 e 返回其值，并返回OK if ( q.front =

23、= q.rear ) return ERROR;/隊(duì)列空 q.front=(q.front+1) % QUEUE_MAXSIZE ; e = q.base q.front ; return OK; / DeQueue 鏈隊(duì)列空的條件是首尾指針相等，而循環(huán)隊(duì)列滿的條件的判定，則有隊(duì)尾加1等于隊(duì)頭和設(shè)標(biāo)記兩種方法。補(bǔ)充重點(diǎn)：1. 為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？ 調(diào)用函數(shù)或子程序非它莫屬； 遞歸運(yùn)算的有力工具； 用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)； 簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題。2.為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？ 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊(duì)列）； 操作系統(tǒng)中的作業(yè)

24、調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）； 簡(jiǎn)化程序設(shè)計(jì)。3. 什么叫“假溢出” ？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。解決假溢出的途徑采用循環(huán)隊(duì)列。4.在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先 移動(dòng)隊(duì)首位置 ，后 取出元素。5.線性表、棧、隊(duì)的異同點(diǎn)：相同點(diǎn)：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表（只是對(duì)插入、刪除運(yùn)算加以限制）。不同點(diǎn)： 運(yùn)算規(guī)則不同：線性表為隨機(jī)存??；而棧是只允許在一端進(jìn)行插入和刪除運(yùn)算

25、，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡(jiǎn)化設(shè)計(jì)等；隊(duì)列用于離散事件模擬、OS作業(yè)調(diào)度和簡(jiǎn)化設(shè)計(jì)等。第四章 串內(nèi)容提要 ： 串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。串即字符串，是由零個(gè)或多個(gè)字符組成的有限序列，是數(shù)據(jù)元素為單個(gè)字符的特殊線性表。串比較：int strcmp(char *s1,char *s2); 求串長(zhǎng)：int strlen(char *s); 串連接：char strcat(char *to,char *from) 子串T定位：char strchr

26、(char *s,char *c); 串的存儲(chǔ)結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點(diǎn)大小”的問(wèn)題。模式匹配算法 。串有三種機(jī)內(nèi)表示方法：模式匹配算法 ：算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）定位問(wèn)題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos)BF算法的實(shí)現(xiàn)即編寫Index(S, T, pos)函數(shù)BF算法設(shè)計(jì)思想：將主串S的第pos個(gè)字符和模式T的第1個(gè)字符比較， 若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個(gè)字符比較。 直到主串S的一個(gè)連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列

27、第一個(gè)字符的序號(hào)，即匹配成功。否則，匹配失敗，返回值 0。Int Index_BP(SString S, SString T, int pos) /返回子串T在主串S中第pos個(gè)字符之后的位置。若不存在，則函數(shù)值為0. / 其中，T非空，1posStrLength(S) i=pos; j=1; while ( i<=S0 && j<=T0 ) /如果i,j二指針在正常長(zhǎng)度范圍， if (Si = = Tj ) +i, +j; /則繼續(xù)比較后續(xù)字符 else i=i-j+2; j=1; /若不相等，指針后退重新開始匹配 if(j>T0) return i-T0;

28、 /T子串指針j正常到尾，說(shuō)明匹配成功， else return 0; /否則屬于i>S0情況，i先到尾就不正常 /Index_BP補(bǔ)充重點(diǎn)：1.空串和空白串有無(wú)區(qū)別？答：有區(qū)別?？沾?Null String)是指長(zhǎng)度為零的串；而空白串(Blank String),是指包含一個(gè)或多個(gè)空白字符 (空格鍵)的字符串.2. “空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串?！?第6章 樹和二叉樹內(nèi)容提要：  樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語(yǔ)。樹：由一個(gè)或多個(gè)(n0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱為根（roo

29、t），當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)分為m(m0)個(gè)互不相交的有限集合T1,T2，Tm。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的子樹 。二叉樹：是n（n0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。術(shù)語(yǔ)：P88 二叉樹的性質(zhì)，存儲(chǔ)結(jié)構(gòu)。性質(zhì)1: 在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>0）。性質(zhì)2: 深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k>0）。性質(zhì)3: 對(duì)于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n21 性質(zhì)4: 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為 ë 性質(zhì)5: 對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則

30、編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)為2i1；其雙親的編號(hào)必為i/2（i1 時(shí)為根,除外）。 二叉樹的存儲(chǔ)結(jié)構(gòu)：一、順序存儲(chǔ)結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。若是完全/滿二叉樹則可以做到唯一復(fù)原。不是完全二叉樹：一律轉(zhuǎn)為完全二叉樹！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。缺點(diǎn)：浪費(fèi)空間；插入、刪除不便 二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用二叉鏈表即可方便表示。一般從根結(jié)點(diǎn)開始存儲(chǔ)。優(yōu)點(diǎn)：不浪費(fèi)空間；插入、刪除方便 二叉樹的遍歷。指按照某種次序訪問(wèn)二叉樹的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次，得到一個(gè)線性序列。遍歷規(guī)則二叉樹由根、左子樹、右子樹構(gòu)成

31、，定義為D、 L、R若限定先左后右，則有三種實(shí)現(xiàn)方案： DLR LDR LRD先序遍歷 中序遍歷 后序遍歷 樹的存儲(chǔ)結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換。 回顧2：二叉樹怎樣還原為樹？ 要點(diǎn)：逆操作，把所有右孩子變?yōu)樾值埽?討論1：森林如何轉(zhuǎn)為二叉樹？ 法一： 各森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個(gè)二叉樹的右子樹上。 法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹 討論2：二叉樹如何還原為森林？ 要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值軜浜蜕值拇鎯?chǔ)方式：樹有三種常用存儲(chǔ)方式：雙親表示法 孩子表示法 孩子兄弟表示法問(wèn)：樹二叉樹的“連線抹線旋轉(zhuǎn)” 如何由計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)？答：用“左孩子右兄弟”表

32、示法來(lái)存儲(chǔ)即可。存儲(chǔ)的過(guò)程就是樹轉(zhuǎn)換為二叉樹的過(guò)程！樹、森林的遍歷： 先根遍歷：訪問(wèn)根結(jié)點(diǎn)；依次先根遍歷根結(jié)點(diǎn)的每棵子樹。 后根遍歷：依次后根遍歷根結(jié)點(diǎn)的每棵子樹；訪問(wèn)根結(jié)點(diǎn)。討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？1. 樹的先根遍歷與二叉樹的先序遍歷相同； 2. 樹的后根遍歷相當(dāng)于二叉樹的中序遍歷；3. 樹沒(méi)有中序遍歷，因?yàn)樽訕錈o(wú)左右之分。 先序遍歷若森林為空，返回；訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)；先根遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問(wèn)第一棵樹的根結(jié)點(diǎn)；中根遍歷除去第一

33、棵樹之后剩余的樹構(gòu)成的森林。 二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。Huffman樹：最優(yōu)二叉樹（帶權(quán)路徑長(zhǎng)度最短的樹）Huffman編碼：不等長(zhǎng)編碼。樹的帶權(quán)路徑長(zhǎng)度：（樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和）構(gòu)造Huffman樹的基本思想：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。構(gòu)造Huffman樹的步驟（即Huffman算法）：(1) 由給定的 n 個(gè)權(quán)值 w1, w2, , wn 構(gòu)成n棵二叉樹的集合F = T1, T2, , Tn （即森林） ，其中每棵二叉樹 Ti 中只有一個(gè)帶權(quán)為 wi 的根結(jié)點(diǎn)，其左右子樹均空。(2) 在F 中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹 做為左右子樹構(gòu)造一棵新的二

34、叉樹，且讓新二叉樹根結(jié)點(diǎn)的權(quán)值等于其左右子樹的根結(jié)點(diǎn)權(quán)值之和。(3) 在F 中刪去這兩棵樹，同時(shí)將新得到的二叉樹加入 F中。(4) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹為止。這棵樹便是Huffman樹。具體操作步驟：學(xué)習(xí)重點(diǎn)：（本章內(nèi)容是本課程的重點(diǎn)） 二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K叉樹。 二叉樹遍歷，遍歷是基礎(chǔ)，由此導(dǎo)出許多實(shí)用的算法，如求二叉樹的高度、各結(jié)點(diǎn)的層次數(shù)、度為0、1、2的結(jié)點(diǎn)數(shù)。 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。 完全二叉樹的性質(zhì)。 樹、森林和二叉樹間的相互轉(zhuǎn)換。 哈夫曼樹的定義

35、、構(gòu)造及求哈夫曼編碼。補(bǔ)充：1.滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個(gè)也不少的樹，而完全二叉樹雖然前k-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿二叉樹是完全二叉樹的一個(gè)特例。2. Huffman樹有什么用？最小冗余編碼、信息高效傳輸?shù)?章 圖內(nèi)容提要：  圖的定義，概念、術(shù)語(yǔ)及基本操作。 圖：記為 G( V, E ) 其中：V 是G 的頂點(diǎn)集合，是有窮非空集； E 是G 的邊集合，是有窮集。 術(shù)語(yǔ)：見(jiàn)課件 圖的存儲(chǔ)結(jié)構(gòu)。1.鄰接矩陣(數(shù)組)表示法 建立一個(gè)頂點(diǎn)表和一個(gè)鄰接矩陣 設(shè)圖 A = (V, E) 有 n 個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組 A.

36、Edgenn。注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。鄰接矩陣法優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。鄰接矩陣法缺點(diǎn)：n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。2. 鄰接表(鏈?zhǔn)?表示法 對(duì)每個(gè)頂點(diǎn)vi 建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來(lái)，表中每個(gè)結(jié)點(diǎn)都設(shè)為3個(gè)域: 每個(gè)單鏈表還應(yīng)當(dāng)附設(shè)一個(gè)頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息； 每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；鄰接

37、表的缺點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。 圖的遍歷。 遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索 深度優(yōu)先搜索（遍歷）步驟： 訪問(wèn)起始點(diǎn) v; 若v的第1個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò)，深度遍歷此鄰接點(diǎn)； 若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò)，再找v的第2個(gè)鄰接點(diǎn)重新遍歷?；舅枷耄悍聵涞南刃虮闅v過(guò)程。廣度優(yōu)先搜索（遍歷）步驟： 在訪問(wèn)了起始點(diǎn)v之后，依次訪問(wèn) v的鄰接點(diǎn)； 然后再依次（順序）訪問(wèn)這些點(diǎn)（下一層）中未被訪問(wèn)過(guò)的鄰接點(diǎn)； 直到所有頂點(diǎn)

38、都被訪問(wèn)過(guò)為止。 圖的應(yīng)用（最小生成樹，最短路經(jīng)） 最小生成樹（MST）的性質(zhì)如下：若U集是V的一個(gè)非空子集，若(u0, v0)是一條最小權(quán)值的邊，其中u0ÎU，v0ÎV-U；則：(u0, v0)必在最小生成樹上。 求MST最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法 Kruskal算法特點(diǎn)：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。Prime算法特點(diǎn): 將頂點(diǎn)歸并，與邊數(shù)無(wú)關(guān)，適于稠密網(wǎng)。 在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。兩種常見(jiàn)的最短路徑問(wèn)題：一、 單源最短路徑用Dijkstr

39、a（迪杰斯特拉）算法二、所有頂點(diǎn)間的最短路徑用Floyd（弗洛伊德）算法一、單源最短路徑 (Dijkstra算法)一頂點(diǎn)到其余各頂點(diǎn)（v0j）目的： 設(shè)一有向圖G=（V, E），已知各邊的權(quán)值，以某指定點(diǎn)v0為源點(diǎn)，求從v0到圖的其余各點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。2、 所有頂點(diǎn)之間的最短路徑可以通過(guò)調(diào)用n次Dijkstra算法來(lái)完成，還有更簡(jiǎn)單的一個(gè)算法：Floyd算法（自學(xué)）。學(xué)習(xí)重點(diǎn)： 圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點(diǎn)。 基本概念中，連通分量，生成樹，鄰接點(diǎn)是重點(diǎn)。 連通圖：在無(wú)向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱頂點(diǎn)v1與v2是連通的。 如果

40、圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱此圖是連通圖。 非連通圖的極大連通子圖叫做連通分量。 生成樹：是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有n-1條邊。 鄰接點(diǎn)：若 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點(diǎn)。 圖是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，也有順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（重點(diǎn)是鄰接距陣）和鄰接表。這兩種存儲(chǔ)結(jié)構(gòu)對(duì)有向圖和無(wú)向圖均適用 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握?qǐng)D的深度、廣度優(yōu)先遍歷。 連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權(quán)值之和是唯一的。 應(yīng)熟練掌握prim和kruscal算法，特別是手工分步模擬生成樹的生成過(guò)程。 從單源點(diǎn)到其他頂點(diǎn)

41、，以及各個(gè)頂點(diǎn)間的最短路徑問(wèn)題，掌握熟練手工模擬。 補(bǔ)充：1. 問(wèn)：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？答：是樹！而且是一棵有向樹！2.討論：鄰接表與鄰接矩陣有什么異同之處？1. 聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行， 鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2. 區(qū)別：對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。3. 用途：鄰接矩陣多用于稠密圖的存儲(chǔ)而鄰接表多用于稀疏圖的存儲(chǔ)3. 若對(duì)連通圖進(jìn)行遍歷，得到的是生成樹 若對(duì)非連通圖進(jìn)行遍歷，得到的是生成森林。第8章 查找 內(nèi)容提要： 查找表是稱

42、為集合的數(shù)據(jù)結(jié)構(gòu)。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個(gè)集合中。（同一類型的數(shù)據(jù)元素構(gòu)成的集合） 查找表的操作：查找，插入，刪除。 靜態(tài)查找表：順序表，有序表等。 針對(duì)靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找 一、順序查找（線性查找） 技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。int Search_Seq( SSTable ST , KeyType key )ST.elem0.key =key; for( i=ST.length; ST.elem i .key!=key; - - i ); return i; / Sea

43、rch_Seq/ASL（1n）/2，時(shí)間效率為 O(n)，這是查找成功的情況:順序查找的特點(diǎn)：優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)： ASL 太大，時(shí)間效率太低。 二、折半查找（二分或?qū)Ψ植檎遥?若關(guān)鍵字不在表中，怎樣得知并及時(shí)停止查找？ 典型標(biāo)志是：當(dāng)查找范圍的上界下界時(shí)停止查找。ASL的含義是“平均每個(gè)數(shù)據(jù)的查找時(shí)間”，而前式是n個(gè)數(shù)據(jù)查找時(shí)間的總和，所以： 三、分塊查找（索引順序查找）思路：先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個(gè)子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值小（但子表內(nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，表中還要包含每個(gè)子表的起始地址（即頭指針

44、）。特點(diǎn)：塊間有序，塊內(nèi)無(wú)序。查找：塊間折半，塊內(nèi)線性查找步驟分兩步進(jìn)行： 對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無(wú)序表）；查找效率ASL分析： 動(dòng)態(tài)查找表：二叉排序樹，平衡二叉樹。特點(diǎn)：表結(jié)構(gòu)在查找過(guò)程中動(dòng)態(tài)生成。要求：對(duì)于給定值key, 若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key 的記錄。 二叉排序樹的定義-或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹： （1）左子樹的所有結(jié)點(diǎn)均小于根的值； （2）右子樹的所有結(jié)點(diǎn)均大于根的值； （3）它的左右子樹也分別為二叉排序樹。 二叉排序

45、樹的插入與刪除思路：查找不成功，生成一個(gè)新結(jié)點(diǎn)s，插入到二叉排序樹中；查找成功則返回。SearchBST (K, &t) /K為待查關(guān)鍵字，t為根結(jié)點(diǎn)指針 p=t; /p為查找過(guò)程中進(jìn)行掃描的指針 while（p!=NULL） case K= p->data: 查找成功，return K< p->data : q=p；p=p->L_child /繼續(xù)向左搜索 K> p->data : q=p；p=p->R_child /繼續(xù)向右搜索 /查找不成功則插入到二叉排序樹中s =(BiTree)malloc(sizeof(BiTNode); s->

46、;data=K; s ->L_child=NULL; s ->R_child=NULL; /查找不成功，生成一個(gè)新結(jié)點(diǎn)s，插入到二叉排序樹葉子處case t=NULL： t=s; /若t為空，則插入的結(jié)點(diǎn)s作為根結(jié)點(diǎn)K < q->data: q->L_child=s; /若K比葉子小，掛左邊K > q->data: q->R_child=s; /若K比葉子大，掛右邊 return OK 二叉排序樹的刪除操作如何實(shí)現(xiàn)？如何刪除一個(gè)結(jié)點(diǎn)？假設(shè)：*p表示被刪結(jié)點(diǎn)的指針； PL和PR 分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點(diǎn)指針；并假定*p是

47、*f的左孩子；則可能有三種情況： *p有兩棵子樹時(shí)，如何進(jìn)行刪除操作？設(shè)刪除前的中序遍歷序列為：. PL s p PR f /顯然p的直接前驅(qū)是s ，s是*p左子樹最右下方的結(jié)點(diǎn)希望刪除p后，其它元素的相對(duì)位置不變。有兩種解決方法：法1：令*p的左子樹為 *f的左子樹，*p的右子樹接為*s的右子樹； /即 fL=PL ; SR=PR ;法2：直接令*s代替*p / *s為*p左子樹最右下方的結(jié)點(diǎn)二叉排序樹的 平衡二叉樹的定義：又稱AVL樹，即它或者是一顆空樹，或者是它的左子樹和右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對(duì)值不超過(guò)1。平衡因子：該結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度。

48、平衡二叉樹的特點(diǎn)：任一結(jié)點(diǎn)的平衡因子只能取：-1、0 或 1。如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：學(xué)習(xí)重點(diǎn)：  查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。因元素間關(guān)系非常松散，其操作需借助其它數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。本章列舉了三種方法（靜態(tài)查找表，動(dòng)態(tài)查找表）實(shí)現(xiàn)查找表的運(yùn)算。 順序表因設(shè)置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長(zhǎng)度不超過(guò)樹的深度。 查找的ASL 二叉排序樹的形態(tài)取決于元素的輸入順序。按中序遍歷可得到結(jié)點(diǎn)的有序序列，應(yīng)熟練掌握其建立、查找，插入和刪除算法。 平衡二叉樹的概念

49、，應(yīng)熟練掌握手工繪制平衡二叉樹。補(bǔ)充：1.查找的過(guò)程是怎樣的？ 給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。2.對(duì)查找表常用的操作有哪些？ 查詢某個(gè)“特定的”數(shù)據(jù)元素是否在表中；查詢某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。 3.哪些查找方法？查找方法取決于表中數(shù)據(jù)的排列方式;4.如何評(píng)估查找方法的優(yōu)劣？用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)劣。稱為平均查找長(zhǎng)度ASL。ASL= Pi. Ci5.使用折半查找算法時(shí)，要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序6.將線性表構(gòu)造成二叉

50、排序樹的優(yōu)點(diǎn)： 查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高； 中序遍歷此二叉樹，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）； 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。第9章     內(nèi)部排序內(nèi)容提要： 排序的定義，排序可以看作是線性表的一種操作 排序:將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。 排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。 穩(wěn)定性若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 插入排序（直接插入、折半插入，索引表插入、希爾插入排序）。插入排序的基本思想是：每步將一個(gè)待排