第1章 緒論

內(nèi)容提要：

◆ 數(shù)據(jù)結構研究的內(nèi)容。

針對非數(shù)值計算的程序設計問題，研究計算機的

操作對象

以及它們之間的

關系和操作

。 數(shù)據(jù)結構涵蓋的內(nèi)容：

◆ 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結構、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。

數(shù)據(jù)

——所有能被計算機識別、存儲和處理的符號的集合。

數(shù)據(jù)元素

——是數(shù)據(jù)的基本單位，具有完整確定的實際意義。

數(shù)據(jù)對象

——具有相同性質的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

數(shù)據(jù)結構

——是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合，表示為： Data_Structure=（D, R）

數(shù)據(jù)類型

——是一個值的集合和定義在該值上的一組操作的總稱。

抽象數(shù)據(jù)類型

——由用戶定義的一個數(shù)學模型與定義在該模型上的一組操作， 它由基本的數(shù)據(jù)類型構成。

◆ 算法的定義及五個特征。

算法

——是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉換為輸出的計算步驟。

算法的基本特性

：輸入、輸出、有窮性、確定性、可行性

◆ 算法設計要求。

①正確性、②可讀性、③健壯性、④效率與低存儲量需求

◆ 算法分析。

時間復雜度、空間復雜度、穩(wěn)定性

學習重點：

◆ 數(shù)據(jù)結構的“三要素”：

邏輯結構

、

物理（存儲）結構

及在

這種結構上所定義的操作（運算）

。

◆ 用計算語句頻度來估算算法的時間復雜度。

第二章 線性表

內(nèi)容提要：

◆ 線性表的邏輯結構定義，對線性表定義的操作。

線性表的定義：用數(shù)據(jù)元素的有限序列表示

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

順序存儲定義：把邏輯上

相鄰

的數(shù)據(jù)元素存儲在物理上

相鄰

的存儲單元中的存儲結構。 鏈式存儲結構: 其結點在存儲器中的位置是隨意的，即邏輯上

相鄰

的數(shù)據(jù)元素在物理上

不一定

相鄰。通過

指針

來實現(xiàn)！

◆ 線性表的操作在兩種存儲結構中的實現(xiàn)。

數(shù)據(jù)結構的基本運算：

修改、插入、刪除、查找、排序

1) 修改——通過數(shù)組的下標便可訪問某個特定元素并修改之。

核心語句:

V[i]=x;

順序表修改操作的時間效率是 O(1)

2) 插入——在線性表的第i個位置前插入一個元素 實現(xiàn)步驟： ①將第n至第i 位的元素向后移動一個位置； ②將要插入的元素寫到第i個位置； ③表長加1。 注意：事先應判斷: 插入位置i 是否合法?表是否已滿? 應當符合條件： 1≤i≤n+1 或 i=[1, n+1]

核心語句：

for (j=n; j>=i; j--) a[j+1]=a[ j ]; a[ i ]=x; n++;

插入時的平均移動次數(shù)為：n(n+1)/2÷（n+1）＝n/2≈O(n)

3) 刪除——刪除線性表的第i個位置上的元素 實現(xiàn)步驟： ①將第i+1 至第n 位的元素向前移動一個位置； ②表長減1。 注意：事先需要判斷，刪除位置i 是否合法? 應當符合條件：1≤i≤n 或 i=[1, n]

核心語句：

for ( j=i+1; j<=n; j++ ) a[j-1]=a[j]; n--;

順序表刪除一元素的時間效率為:T（n)=(n-1)/2 ≈O(n)

順序表插入、刪除算法的平均空間復雜度為O(1)

單鏈表：

（1）

用單鏈表結構來存放26個英文字母組成的線性表（a，b，c，…，z）,請寫出C語言程序。 #include #include typedef struct node{ char data; struct node *next; }node; node *p,*q,*head; //一般需要3個指針變量 int n ; // 數(shù)據(jù)元素的個數(shù) int m=sizeof(node); /*結構類型定義好之后，每個node類型的長度就固定了， m求一次即可*/ void build( ) //字母鏈表的生成。要一個個慢慢鏈入 { int i; head=(node*)malloc(m); //m=sizeof(node) 前面已求出 p=head; for( i=1; i<26; i++) //因尾結點要特殊處理，故i≠26 { p->data=i+‘a(chǎn)’-1; // 第一個結點值為字符a p->next=(node*)malloc(m); //為后繼結點“挖坑”！ p=p->next；} //讓指針變量P指向后一個結點 p->data=i+‘a(chǎn)’-1; //最后一個元素要單獨處理 p->next=NULL ; //單鏈表尾結點的指針域要置空！ } } void display() //字母鏈表的輸出 { p=head; while (p) //當指針不空時循環(huán)（僅限于無頭結點的情況） { printf("%c",p->data); p=p->next; //讓指針不斷“順藤摸瓜” } } （2）單鏈表的修改(或讀?。?思路：要修改第i個數(shù)據(jù)元素，必須從頭指針起一直找到該結點的指針p， 然后才能：p>data=new_value 讀取第i個數(shù)據(jù)元素的核心語句是： Linklist *find(Linklist *head ,int i) { int j=1; Linklist *p; P=head->next; While((p!=NULL)&&(jnext; j++; } return p; } 3. 單鏈表的插入 鏈表插入的核心語句： Step 1：s->next=p->next; Step 2：p->next=s ； 6.單鏈表的刪除 刪除動作的核心語句（要借助輔助指針變量q）： q = p->next; //首先保存b的指針，靠它才能找到c； p->next=q->next; //將a、c兩結點相連，淘汰b結點； free(q) ； //徹底釋放b結點空間 7.雙向鏈表的插入操作： 設p已指向第 i 元素，請在第 i 元素前插入元素 x： ① ai-1的后繼從 ai ( 指針是p)變?yōu)?x（指針是s) : s->next = p ; p->prior->next = s ; ② ai 的前驅從 ai-1 ( 指針是p->prior)變?yōu)?x ( 指針是s); s->prior = p ->prior ; p->prior = s ; 8.雙向鏈表的刪除操作： 設p指向第 i 個元素，刪除第 i 個 元素 后繼方向：ai-1的后繼由 ai ( 指針p)變?yōu)?ai+1(指針 p ->next ); p ->prior->next = p->next ; 前驅方向：ai+1的前驅由 ai ( 指針p)變?yōu)閍i-1 (指針 p -> prior ); p->next->prior = p ->prior ;

◆ 數(shù)組的邏輯結構定義及存儲

數(shù)組： 由一組名字相同、下標不同的變量構成 N維數(shù)組的特點：n個下標，每個元素受到n個關系約束 一個n維數(shù)組可以看成是

由若干個n－1維數(shù)組

組成的線性表。 存儲：事先約定按某種次序將數(shù)組元素排成一列序列，然后將這個線性序列存入存儲器中。 在二維數(shù)組中，我們既可以規(guī)定按行存儲，也 可以規(guī)定按列存儲。 設一般的二維數(shù)組是A[c1..d1, c2..d2]， 則行優(yōu)先存儲時的地址公式為： 二維數(shù)組列優(yōu)先存儲的通式為：

◆ 稀疏矩陣（含特殊矩陣）的存儲及運算。

稀疏矩陣：矩陣中非零元素的個數(shù)較少（一般小于5%）

學習重點：

◆ 線性表的邏輯結構，指線性表的數(shù)據(jù)元素間存在著

線性關系

。在順序存儲結構中，元素存儲的

先后位置

反映出這種線性關系，而在鏈式存儲結構中，是靠

指針

來反映這種關系的。

◆ 順序存儲結構用一維數(shù)組表示，給定下標，可以存取相應元素，屬于

隨機存取

的存儲結構。

◆ 鏈表操作中應注意不要使鏈意外“斷開”。因此，若在某結點前插入一個元素，或刪除某元素，必須知道該元素的

前驅結點的指針

。

◆ 掌握通過畫出結點圖來進行鏈表（單鏈表、循環(huán)鏈表等）的

生成、插入、刪除、遍歷

等操作。

◆ 數(shù)組（主要是二維）在以

行序/列序

為主的存儲中的地址計算方法。

◆ 稀疏矩陣的三元組表存儲結構。

◆ 稀疏矩陣的十字鏈表存儲方法。

補充重點：

1.每個存儲結點都包含兩部分：

數(shù)據(jù)域和指針域(鏈域)

2.在單鏈表中，除了首元結點外，任一結點的存儲位置由

其直接前驅結點的鏈域的值

指示。

3.在鏈表中設置頭結點有什么好處？

頭結點即在鏈表的首元結點之前附設的一個結點，該結點的

數(shù)據(jù)域可以為空，也可存放表長度

等附加信息，其作用是為了對鏈表進行操作時，可以對

空表、非空表

的情況以及對

首元結點

進行統(tǒng)一處理，編程更方便。

4.如何表示空表？

（1）無頭結點時，當頭指針的值為空時表示空表； （2）有頭結點時，當頭結點的指針域為空時表示空表。

5.鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？

因每個結點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結構數(shù)據(jù)類型。

6.sizeof(x)——

計算變量x的長度（字節(jié)數(shù)）

；

malloc(m) —

開辟m字節(jié)長度的地址空間，并返回這段空間的首地址；

free(p) ——

釋放指針p所指變量的存儲空間，即徹底刪除一個變量。

7.鏈表的運算效率分析：

（1）查找

因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為 O(n)。

（2） 插入和刪除

因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復雜度為 O(1)。

但是，如果要在單鏈表中進行前插或刪除操作，因為要從頭查找前驅結點，所耗時間復雜度將是 O(n)。

例：在n個結點的單鏈表中要刪除已知結點*P，需找到它的

前驅結點的地址

，其時間復雜度為

O（n）

8. 順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？

順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。

順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。

鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。

鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。

◆ 順序表適宜于做

查找

這樣的靜態(tài)操作； ◆ 鏈表宜于做

插入、刪除

這樣的動態(tài)操作。 ◆ 若線性表的長度變化不大，且其主要操作是查找，則采用順序表； ◆ 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。

9. 判斷：“數(shù)組的處理比其它復雜的結構要簡單”，對嗎？

答：對的。因為—— ① 數(shù)組中各元素具有

統(tǒng)一的類型

； ② 數(shù)組元素的下標一般具有

固定的上界和下界

，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。 ③數(shù)組的

基本操作比較簡

單，除了結構的初始化和銷毀之外，只有存取元素和修改元素值的操作。

10.三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的

行下標

、

列下標

和

元素值

。

11.寫出右圖所示稀疏矩陣的壓縮存儲形式。 解：介紹3種存儲形式。

法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：用十字鏈表表示

用途：方便稀疏矩陣的加減運算 方法：每個非0元素占用5個域

法3：用三元組矩陣表示：

稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能

代碼：

1.用數(shù)組V來存放26個英文字母組成的線性表（a，b，c，…，z），寫出在順序結構上生成和顯示該表的C語言程序。 char V[30]; void build() //字母線性表的生成，即建表操作 { int i; V[0]='a'; for( i=1; i<=n-1; i++ ) V[i]=V[i-1]+1; } void display( ) //字母線性表的顯示，即讀表操作 { int i; for( i=0; i<=n-1; i++ ) printf( "%c", v[i] ); printf( "\n " ); } void main(void) //主函數(shù)，字母線性表的生成和輸出 { n=26; // n是表長，是數(shù)據(jù)元素的個數(shù)，而不是V的實際下標 build( ); display( ); }

第三章 棧和隊列

內(nèi)容提要：

◆ 從數(shù)據(jù)結構角度來講，棧和隊列也是線性表，其操作是線性表操作的子集，屬操作受限的線性表。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。

◆ 棧的定義及操作。棧是只準在一端進行插入和刪除操作的線性表，該端稱為棧的頂端。

插入元素到棧頂?shù)牟僮鳎Q為入棧。 從棧頂刪除最后一個元素的操作，稱為出棧。 對于向上生成的堆棧: 入?？谠E：堆棧指針top “先壓后加” : S[top++]=an+1 出棧口訣：堆棧指針top “先減后彈” : e=S[--top]

◆ 棧的順序和鏈式存儲結構，及在這兩種結構下實現(xiàn)棧的操作。

順序棧入棧函數(shù)PUSH（） status Push(ElemType e) { if(top>M){上溢} else s[top++]=e; } 順序棧出棧函數(shù)POP() status Pop( ) { if(top=L) { 下溢 } else { e=s[--top]; return(e);} }

◆ 隊列的定義及操作，隊列的刪除在一端（隊尾），而插入則在隊列的另一端（隊頭）。因此在兩種存儲結構中，都需要隊頭和隊尾兩個指針。

隊列：只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。 鏈隊列 結點類型定義： typedef Struct QNode{ QElemType data; //元素 Struct QNode *next; //指向下一結點的指針 }Qnode , * QueuePtr ; 鏈隊列類型定義： typedef struct { QueuePtr front ; //隊首指針 QueuePtr rear ; //隊尾指針 } LinkQueue; 鏈隊示意圖： ① 空鏈隊的特征：front=rear ② 鏈隊會滿嗎？一般不會，因為刪除時有free動作。除非內(nèi)存不足！ ③ 入隊（尾部插入）：rear->next=S; rear=S; 出隊（頭部刪除）：front->next=p->next; 2.順序隊 順序隊類型定義： #define QUEUE-MAXSIZE 100 //最大隊列長度 typedef struct { QElemType *base; //隊列的基址 int front; //隊首指針 int rear; //隊尾指針 }SqQueue 建隊核心語句： q . base=(QElemType *)malloc(sizeof (QElemType ） * QUEUE_MAXSIZE; //分配空間 順序隊示意圖： 循環(huán)隊列： 隊空條件 : front = rear (初始化時：front = rear ) 隊滿條件： front = (rear+1) % N (N=maxsize) 隊列長度（即數(shù)據(jù)元素個數(shù)）：L=（N＋rear－front）% N 1）初始化一個空隊列 Status InitQueue ( SqQueue &q ) //初始化空循環(huán)隊列 q { q . base=(QElemType *)malloc(sizeof(QElemType） * QUEUE_MAXSIZE); //分配空間 if (!q.base) exit(OVERFLOW);//內(nèi)存分配失敗，退出程序 q.front =q.rear=0; //置空隊列 return OK; } //InitQueue; 2）入隊操作 Status EnQueue(SqQueue &q, QElemType e) {//向循環(huán)隊列 q 的隊尾加入一個元素 e if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front ) return ERROR ; //隊滿則上溢，無法再入隊 q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; q.base [ q.rear ] = e; //新元素e入隊 return OK; }// EnQueue; 3）出隊操作 Status DeQueue ( SqQueue &q, QElemType &e) {//若隊列不空，刪除循環(huán)隊列q的隊頭元素， //由 e 返回其值，并返回OK if ( q.front = = q.rear ) return ERROR;//隊列空 q.front=(q.front+1) % QUEUE_MAXSIZE ; e = q.base [ q.front ] ; return OK; }// DeQueue

◆ 鏈隊列空的條件是首尾指針相等，而循環(huán)隊列滿的條件的判定，則有隊尾加1等于隊頭和設標記兩種方法。

補充重點：

1.為什么要設計堆棧？它有什么獨特用途？

① 調用函數(shù)或子程序非它莫屬； ② 遞歸運算的有力工具； ③ 用于保護現(xiàn)場和恢復現(xiàn)場； ④ 簡化了程序設計的問題。

2.為什么要設計隊列？它有什么獨特用途？

① 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊列）； ② 操作系統(tǒng)中的作業(yè)調度（一個CPU執(zhí)行多個作業(yè)）； ③ 簡化程序設計。

3.什么叫“假溢出” ？如何解決？

答：在順序隊中，當尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。解決假溢出的途徑———采用循環(huán)隊列。

4.在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是先

移動隊首位置

，后

取出元素

。

5.線性表、棧、隊的異同點：

相同點：邏輯結構相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。 不同點：① 運算規(guī)則不同： 線性表為隨機存??； 而棧是只允許在一端進行插入和刪除運算，因而是后進先出表LIFO； 隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。 ② 用途不同，線性表比較通用；堆棧用于函數(shù)調用、遞歸和簡化設計等；隊列用于離散事件模擬、OS作業(yè)調度和簡化設計等。

第四章 串

內(nèi)容提要 ：

◆ 串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。

串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。 串比較：int strcmp(char *s1,char *s2); 求串長：int strlen(char *s); 串連接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c);

◆ 串的存儲結構，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結點大小”的問題。

模式匹配算法 。

串有三種機內(nèi)表示方法：

模式匹配算法 ：

算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位） 定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos) BF算法的實現(xiàn)—即編寫Index(S, T, pos)函數(shù) BF算法設計思想： 將主串S的第pos個字符和模式T的第1個字符比較， 若相等，繼續(xù)逐個比較后續(xù)字符； 若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。 直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。 否則，匹配失敗，返回值 0。 Int Index_BP(SString S, SString T, int pos) { //返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)值為0. // 其中，T非空，1≤pos≤StrLength(S) i=pos; j=1; while ( i<=S[0] && j<=T[0] ) //如果i,j二指針在正常長度范圍， { if (S[i] = = T[j] ) {++i, ++j; } //則繼續(xù)比較后續(xù)字符 else {i=i-j+2; j=1;} //若不相等，指針后退重新開始匹配 } if(j>T[0]) return i-T[0]; //T子串指針j正常到尾，說明匹配成功， else return 0; //否則屬于i>S[0]情況，i先到尾就不正常 } //Index_BP

補充重點：

1.空串和空白串有無區(qū)別？

答：有區(qū)別。 空串(Null String)是指長度為零的串； 而空白串(Blank String),是指包含一個或多個空白字符‘ ’(空格鍵)的字符串.

2.“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串?！?/p>

第六章 樹和二叉樹

內(nèi)容提要：

◆ 樹是復雜的非線性數(shù)據(jù)結構，樹，二叉樹的遞歸定義，基本概念，術語。

樹：由一個或多個(n≥0)結點組成的有限集合T，有且僅有一個結點稱為根（root），當n>1時，其余的結點分為m(m≥0)個互不相交的有限集合T1,T2，…，Tm。每個集合本身又是棵樹，被稱作這個根的子樹 。 二叉樹：是n（n≥0）個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。 術語：P88

◆ 二叉樹的性質，存儲結構。

性質1: 在二叉樹的第i層上至多有2i-1個結點（i>0）。 性質2: 深度為k的二叉樹至多有2k-1個結點（k>0）。 性質3: 對于任何一棵二叉樹，若2度的結點數(shù)有n2個，則葉子數(shù)（n0）必定為n2＋1 性質4: 具有n個結點的完全二叉樹的深度必為

?

性質5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結點，其左孩子編號必為2i，其右孩子編號為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）。

二叉樹的存儲結構：

一、順序存儲結構 按二叉樹的結點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。 若是完全/滿二叉樹則可以做到唯一復原。 不是完全二叉樹：一律轉為完全二叉樹！ 方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結點”，其內(nèi)容為空。 缺點：①浪費空間；②插入、刪除不便 二、鏈式存儲結構 用二叉鏈表即可方便表示。一般從根結點開始存儲。 優(yōu)點：①不浪費空間；②插入、刪除方便

◆ 二叉樹的遍歷。

指按照某種次序訪問二叉樹的所有結點，并且每個結點僅訪問一次，得到一個線性序列。 遍歷規(guī)則——— 二叉樹由根、左子樹、右子樹構成，定義為D、 L、R 若限定先左后右，則有三種實現(xiàn)方案： DLR LDR LRD 先序遍歷 中序遍歷 后序遍歷

◆ 樹的存儲結構，樹、森林的遍歷及和二叉樹的相互轉換。

回顧2：二叉樹怎樣還原為樹？ 要點：逆操作，把所有右孩子變?yōu)樾值埽?

討論1：森林如何轉為二叉樹？

法一：① 各森林先各自轉為二叉樹；② 依次連到前一個二叉樹的右子樹上。

法二：森林直接變兄弟，再轉為二叉樹 討論2：二叉樹如何還原為森林？ 要點：把最右邊的子樹變?yōu)樯郑溆嘤易訕渥優(yōu)樾值?

樹和森林的存儲方式：

樹有三種常用存儲方式： ①雙親表示法 ②孩子表示法 ③孩子—兄弟表示法 問：樹→二叉樹的“連線—抹線—旋轉” 如何由計算機自動實現(xiàn)？ 答：用“左孩子右兄弟”表示法來存儲即可。 存儲的過程就是樹轉換為二叉樹的過程！

樹、森林的遍歷：

① 先根遍歷：訪問根結點；依次先根遍歷根結點的每棵子樹。 ② 后根遍歷：依次后根遍歷根結點的每棵子樹；訪問根結點。 討論：樹若采用“先轉換，后遍歷”方式，結果是否一樣？ 1. 樹的先根遍歷與二叉樹的先序遍歷相同； 2. 樹的后根遍歷相當于二叉樹的中序遍歷； 3. 樹沒有中序遍歷，因為子樹無左右之分。 ① 先序遍歷 若森林為空，返回； 訪問森林中第一棵樹的根結點； 先根遍歷第一棵樹的根結點的子樹森林； 先根遍歷除去第一棵樹之后剩余的樹構成的森林。 ② 中序遍歷 若森林為空，返回； 中根遍歷森林中第一棵樹的根結點的子樹森林； 訪問第一棵樹的根結點； 中根遍歷除去第一棵樹之后剩余的樹構成的森林。

◆ 二叉樹的應用：哈夫曼樹和哈夫曼編碼。

Huffman樹：最優(yōu)二叉樹（帶權路徑長度最短的樹） Huffman編碼：不等長編碼。 樹的帶權路徑長度：（樹中所有葉子結點的帶權路徑長度之和） 構造Huffman樹的基本思想：權值大的結點用短路徑，權值小的結點用長路徑。 構造Huffman樹的步驟（即Huffman算法）： (1) 由給定的 n 個權值{ w1, w2, …, wn }構成n棵二叉樹的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉樹 Ti 中只有一個帶權為 wi 的根結點，其左右子樹均空。 (2) 在F 中選取兩棵根結點權值最小的樹 做為左右子樹構造一棵新的二叉樹，且讓新二叉樹根結點的權值等于其左右子樹的根結點權值之和。 (3) 在F 中刪去這兩棵樹，同時將新得到的二叉樹加入 F中。 (4) 重復(2) 和(3) , 直到 F 只含一棵樹為止。這棵樹便是Huffman樹。

具體操作步驟：

學習重點：（本章內(nèi)容是本課程的重點）

◆ 二叉樹性質及證明方法，并能把這種方法推廣到K叉樹。

◆ 二叉樹遍歷，遍歷是基礎，由此導出許多實用的算法，如求二叉樹的高度、各結點的層次數(shù)、度為0、1、2的結點數(shù)。

◆ 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。

◆ 完全二叉樹的性質。

◆ 樹、森林和二叉樹間的相互轉換。

◆ 哈夫曼樹的定義、構造及求哈夫曼編碼。

補充：

1.滿二叉樹和完全二叉樹有什么區(qū)別？

答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前k-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結點。滿二叉樹是完全二叉樹的一個特例。

2.Huffman樹有什么用？

最小冗余編碼、信息高效傳輸

第七章 圖

內(nèi)容提要：

◆ 圖的定義，概念、術語及基本操作。

圖：記為 G＝( V, E )

其中：V 是G 的頂點集合，是有窮非空集； E 是G 的邊集合，是有窮集。 術語：見課件

◆ 圖的存儲結構。

1.鄰接矩陣(數(shù)組)表示法 ① 建立一個頂點表和一個鄰接矩陣 ② 設圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 A.Edge[n][n]。 注：在有向圖的鄰接矩陣中， 第i行含義：以結點vi為尾的弧(即出度邊）； 第i列含義：以結點vi為頭的弧(即入度邊）。 鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。 鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。 2.鄰接表(鏈式)表示法 ① 對每個頂點vi 建立一個單鏈表，把與vi有關聯(lián)的邊的信息（即度或出度邊）鏈接起來，表中每個結點都設為3個域: ② 每個單鏈表還應當附設一個頭結點（設為2個域），存vi信息； ③ 每個單鏈表的頭結點另外用順序存儲結構存儲。 鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點； 鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜索兩結點對應的單鏈表，沒有鄰接矩陣方便。

◆ 圖的遍歷。

遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。

圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索

深度優(yōu)先搜索（遍歷）步驟： ① 訪問起始點 v; ② 若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點； ③ 若當前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。 基本思想：——仿樹的先序遍歷過程。 廣度優(yōu)先搜索（遍歷）步驟： ① 在訪問了起始點v之后，依次訪問 v的鄰接點； ② 然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點； ③ 直到所有頂點都被訪問過為止。

◆ 圖的應用（最小生成樹，最短路經(jīng)）

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

求MST最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法 Kruskal算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。 Prime算法特點: 將頂點歸并，與邊數(shù)無關，適于稠密網(wǎng)。 在帶權有向圖中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權值之和最小的路徑，即最短路徑。 兩種常見的最短路徑問題： 一、 單源最短路徑—用Dijkstra（迪杰斯特拉）算法 二、所有頂點間的最短路徑—用Floyd（弗洛伊德）算法 一、單源最短路徑 (Dijkstra算法)一頂點到其余各頂點（v0→j） 目的： 設一有向圖G=（V, E），已知各邊的權值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。限定各邊上的權值大于或等于0。 二、所有頂點之間的最短路徑 可以通過調用n次Dijkstra算法來完成，還有更簡單的一個算法：Floyd算法（自學）。

學習重點： 圖是應用最廣泛的一種數(shù)據(jù)結構，本章也是這門課程的重點。

◆ 基本概念中，連通分量，生成樹，鄰接點是重點。

① 連通圖：

在無向圖中, 若從頂點v1到頂點v2有路徑, 則稱頂點v1與v2是連通的。 如果圖中任意一對頂點都是連通的, 則稱此圖是連通圖。 非連通圖的極大連通子圖叫做

連通分量。

② 生成樹：

是一個極小連通子圖，它含有圖中全部n個頂點，但只有n-1條邊。

③ 鄰接點：

若 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點。

◆ 圖是復雜的數(shù)據(jù)結構，也有順序和鏈式兩種存儲結構：數(shù)組表示法（重點是鄰接距陣）和鄰接表。這兩種存儲結構對有向圖和無向圖均適用

◆ 圖的遍歷是圖的各種算法的基礎，應熟練掌握圖的深度、廣度優(yōu)先遍歷。

◆ 連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權值之和是唯一的。 應熟練掌握prim和kruscal算法，

特別是手工分步模擬生成樹的生成過程。

◆ 從單源點到其他頂點，以及各個頂點間的最短路徑問題，掌握熟練手工模擬。

補充：

1.問：當有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？

答：是樹！而且是一棵有向樹！

2.討論：鄰接表與鄰接矩陣有什么異同之處？

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

3.若對連通圖進行遍歷，得到的是生成樹

若對非連通圖進行遍歷，得到的是生成森林。

第八章 查找

內(nèi)容提要：

◆ 查找表是稱為集合的數(shù)據(jù)結構。是元素間約束力最差的數(shù)據(jù)結構：元素間的關系是元素僅共在同一個集合中。

（同一類型的數(shù)據(jù)元素構成的集合）

◆ 查找表的操作：查找，插入，刪除。

◆ 靜態(tài)查找表：順序表，有序表等。

針對靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找

一、順序查找（線性查找） 技巧：把待查關鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。 int Search_Seq( SSTable ST , KeyType key ){ ST.elem[0].key =key; for( i=ST.length; ST.elem[ i ].key!=key; - - i ); return i; } // Search_Seq //ASL＝（1＋n）/2，時間效率為 O(n)，這是查找成功的情況: 順序查找的特點： 優(yōu)點：算法簡單，且對順序結構或鏈表結構均適用。 缺點： ASL 太大，時間效率太低。 二、折半查找（二分或對分查找） 若關鍵字不在表中，怎樣得知并及時停止查找？ 典型標志是：當查找范圍的上界≤下界時停止查找。 ASL的含義是“平均每個數(shù)據(jù)的查找時間”，而前式是n個數(shù)據(jù)查找時間的總和，所以： 三、分塊查找（索引順序查找） 思路：先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關鍵字構成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。 特點：塊間有序，塊內(nèi)無序。 查找：塊間折半，塊內(nèi)線性 查找步驟分兩步進行： ① 對索引表使用折半查找法（因為索引表是有序表）； ② 確定了待查關鍵字所在的子表后，在子表內(nèi)采用順序查找法（因為各子表內(nèi)部是無序表）； 查找效率ASL分析：

◆ 動態(tài)查找表：二叉排序樹，平衡二叉樹。

特點：表結構在查找過程中動態(tài)生成。 要求：對于給定值key, 若表中存在其關鍵字等于key的記錄，則查找成功返回；否則插入關鍵字等于key 的記錄。 ① 二叉排序樹的定義 ----或是一棵空樹；或者是具有如下性質的非空二叉樹： （1）左子樹的所有結點均小于根的值； （2）右子樹的所有結點均大于根的值； （3）它的左右子樹也分別為二叉排序樹。 ② 二叉排序樹的插入與刪除 思路：查找不成功，生成一個新結點s，插入到二叉排序樹中；查找成功則返回。 SearchBST (K, &t) { //K為待查關鍵字，t為根結點指針 p=t; //p為查找過程中進行掃描的指針 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->data=K; s ->L_child=NULL; s ->R_child=NULL; //查找不成功，生成一個新結點s，插入到二叉排序樹葉子處 case { t=NULL： t=s; //若t為空，則插入的結點s作為根結點 K < q->data: q->L_child=s; //若K比葉子小，掛左邊 K > q->data: q->R_child=s; //若K比葉子大，掛右邊 } return OK } ③ 二叉排序樹的刪除操作如何實現(xiàn)？ 如何刪除一個結點？ 假設：*p表示被刪結點的指針； PL和PR 分別表示*P的左、右孩子指針； *f表示*p的雙親結點指針；并假定*p是*f的左孩子；則可能有三種情況： *p有兩棵子樹時，如何進行刪除操作？ 設刪除前的中序遍歷序列為：…. PL s p PR f //顯然p的直接前驅是s ，s是*p左子樹最右下方的結點 希望刪除p后，其它元素的相對位置不變。有兩種解決方法： 法1：令*p的左子樹為 *f的左子樹，*p的右子樹接為*s的右子樹； //即 fL=PL ; SR=PR ; 法2：直接令*s代替*p // *s為*p左子樹最右下方的結點 二叉排序樹的 ④ 平衡二叉樹的定義：又稱AVL樹，即它或者是一顆空樹，或者是它的左子樹和右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對值不超過1。 平衡因子：——該結點的左子樹的深度減去它的右子樹的深度。 平衡二叉樹的特點：任一結點的平衡因子只能?。?1、0 或 1。 如果在一棵AVL樹中插入一個新結點，就有可能造成失衡，此時必須重新調整樹的結構，使之恢復平衡。我們稱調整平衡過程為

平衡旋轉

。 平衡旋轉可以歸納為四類：

學習重點：

◆ 查找表是稱為集合的數(shù)據(jù)結構。因元素間關系非常松散，其操作需借助其它數(shù)據(jù)結構來實現(xiàn)。本章列舉了三種方法（靜態(tài)查找表，動態(tài)查找表）實現(xiàn)查找表的運算。

◆ 順序表因設置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長度不超過樹的深度。

◆ 查找的ASL

◆ 二叉排序樹的形態(tài)取決于元素的輸入順序。按中序遍歷可得到結點的有序序列，應熟練掌握其建立、查找，插入和刪除算法。

◆ 平衡二叉樹的概念，應熟練掌握手工繪制平衡二叉樹。

補充：

1.查找的過程是怎樣的？

給定一個值K，在含有n個記錄的文件中進行搜索，尋找一個關鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。

2.對查找表常用的操作有哪些？

查詢某個“特定的”數(shù)據(jù)元素是否在表中； 查詢某個“特定的”數(shù)據(jù)元素的各種屬性； 在查找表中插入一元素； 從查找表中刪除一元素。

3.哪些查找方法？

查找方法取決于表中數(shù)據(jù)的排列方式;

4.如何評估查找方法的優(yōu)劣？

用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度ASL。

ASL=∑ Pi. Ci

5.使用折半查找算法時，要求被查文件：采用順序存貯結構、記錄按關鍵字遞增有序

6.將線性表構造成二叉排序樹的優(yōu)點：

① 查找過程與順序結構有序表中的折半查找相似，查找效率高； ② 中序遍歷此二叉樹，將會得到一個關鍵字的有序序列（即實現(xiàn)了排序運算）； ③ 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結點上，而且插入或刪除時只需修改指針而不需移動元素。

第九章 內(nèi)部排序

內(nèi)容提要：

◆ 排序的定義，排序可以看作是線性表的一種操作

排序:將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

◆ 排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。

穩(wěn)定性——若兩個記錄A和B的關鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。

◆ 插入排序（直接插入、折半插入，索引表插入、希爾插入排序）。

插入排序的基本思想是： 每步將一個待排序的對象，按其關鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當位置上，直到對象全部插入為止。 簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。 1) 直接插入排序

在已形成的有序表中線性查找，并在適當位置插入，把原來位置上的元素向后順移。

時間效率： 因為在最壞情況下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。 其他情況下也要考慮移動元素的次數(shù)。 故時間復雜度為O(n2) 空間效率：僅占用1個緩沖單元——O（1） 算法的穩(wěn)定性：因為25*排序后仍然在25的后面——穩(wěn)定 直接插入排序算法的實現(xiàn)： void InsertSort ( SqList &L ) { //對順序表L作直接插入排序 for ( i = 2; i <=L.length; i++) //假定第一個記錄有序 { L.r[0]= L.r[i]; j=i-1 ; //先將待插入的元素放入“哨兵”位置 while（L[0] .key

◆ 交換排序（冒泡排序、快速排序）。

交換排序的基本思想是：兩兩比較待排序記錄的關鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。

1) 冒泡排序 基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。 優(yōu)點：每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結束排序。 前提：順序存儲結構 冒泡排序的算法分析： 時間效率：O（n2) —因為要考慮最壞情況 空間效率：O（1） —只在交換時用到一個緩沖單元 穩(wěn) 定 性： 穩(wěn)定 —25和25*在排序前后的次序未改變 冒泡排序的優(yōu)點：每一趟整理元素時，不僅可以完全確定一個元素的位置（擠出一個泡到表尾），還可以對前面的元素作一些整理，所以比一般的排序要快。 2） 快速排序 基本思想：從待排序列中任取一個元素 (例如取第一個) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調整，直到每個子表的元素只剩一個。此時便為有序序列了。 優(yōu)點：因為每趟可以確定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！ 前提：順序存儲結構 時間效率：O(nlog2n) —因為每趟確定的元素呈指數(shù)增加 空間效率：O（log2n）—因為遞歸要用棧(存每層low，high和pivot) 穩(wěn) 定 性： 不 穩(wěn) 定 —因為有跳躍式交換。

◆ 選擇排序（簡單選擇排序、樹形選擇排序、堆排序）。

選擇排序的基本思想是：每一趟在后面n-i 個待排記錄中選取關鍵字最小的記錄作為有序序列中的第i 個記錄。 1）簡單選擇排序 思路異常簡單：每經(jīng)過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可。 ——首先，在n個記錄中選擇最小者放到r[1]位置；然后，從剩余的n-1個記錄中選擇最小者放到r[2]位置；…如此進行下去，直到全部有序為止。 優(yōu)點：實現(xiàn)簡單 缺點：每趟只能確定一個元素，表長為n時需要n-1趟 前提：順序存儲結構 Void SelectSort(SqList &L ) { for (i=1; i

堆排序算法分析：

時間效率： O(nlog2n)。因為整個排序過程中需要調用n-1次HeapAdjust( )算法，而算法本身耗時為log2n； 空間效率：O(1)。僅在第二個for循環(huán)中交換記錄時用到一個臨時變量temp。 穩(wěn)定性： 不穩(wěn)定。 優(yōu)點：對小文件效果不明顯，但對大文件有效。

學習要點：

◆ 各種排序所基于的基本思想。

◆ 在“最好”和“最差”情況下，排序性能的分析，是否是穩(wěn)定排序的結論，時間效率和空間效率。

◆ 對每種排序方法的學習，應掌握其本質（排序所基于的思想），熟練掌握手工模擬各種排序的過程。

補充：

1.排序算法的好壞如何衡量？

時間效率——排序速度（即排序所花費的全部比較次數(shù)） 空間效率——占內(nèi)存輔助空間的大小 穩(wěn)定性——若兩個記錄A和B的關鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。

2.“快速排序”是否真的比任何排序算法都快？

——基本上是，因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的。