1、第1章緒論內容提要：數據結構研究的內容。針對非數值計算的程序設計問題，研究計算機的操作對象以及它們之間的 關系和操作。數據結構涵蓋的內容：錢進結構（建性表、棧、駄、串、數紐非線性結掏樹結構圖結構數據結構物理（）結杓鞭疼結構 遂式結構 紊引結構 散列結構插入運算駅除運翳 修改運算 查找運算 排序運算基本概念：數據、數據元素、數據對象、數據結構、數據類型、抽象數據類型。 數據一一所有能被計算機識別、存儲和處理的符號的集合。數據元素一一是數據的基本單位，具有完整確定的實際意義。數據對象一一具有相同性質的數據元素的集合，是數據的一個子集。數據結構是相互之間存在一種或多種特定關系的數據元素的集合，表示為

2、：Data_Structure= （ D, R）數據類型一一是一個值的集合和定義在該值上的一組操作的總稱。抽象數據類型一一由用戶定義的一個數學模型與定義在該模型上的一組操作，它由基本的數據類型構成。算法的定義及五個特征。算法 是對特定問題求解步驟的一種描述，它是指令的有限序列， 是一系列輸入轉換為輸出的計算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性算法設計要求。 正確性、可讀性、健壯性、效率與低存儲量需求算法分析。時間復雜度、空間復雜度、穩定性學習重點：數據結構的“三要素”：邏輯結構、物理（存儲）結構 及在這種結構上所定義的操作（運 算）。用計算語句頻度來估算算法的時間復雜度。第

3、二章線性表內容提要：線性表的邏輯結構定義，對線性表定義的操作。線性表的定義：用數據元素的有限序列表示丿'n為元素兌 口時稱為空眈曽:器線性表的存儲結構：順序存儲結構和鏈式存儲結構。不一順序存儲定義：把邏輯上 相鄰的數據元素存儲在物理上 相鄰的存儲單元中的存儲結構。 鏈式存儲結構：其結點在存儲器中的位置是隨意的， 即邏輯上相鄰的數據元素在物理上 定相鄰。通過指針來實現！ 線性表的操作在兩種存儲結構中的實現。數據結構的基本運算：修改、插入、刪除、查找、排序1) 修改一一通過數組的下標便可訪問某個特定元素并修改之。核心語句：Vi=x;順序表修改操作的時間效率是0(1)2) 插入在線性表的第i

4、個位置前插入一個元素 實現步驟： 將第n至第i位的元素向后移動一個位置； 將要插入的元素寫到第i個位置； 表長加1。注意：事先應判斷：插入位置i是否合法？表是否已滿？應當符合條件：K i < n+1 或 i=1, n+1核心語句：for (j=n; j>=i; j-)aj+1=a j ；a i =x;n+;插入時的平均移動次數為：n(n+1)/2 *( n+1) = n/20(n)3) 刪除一一刪除線性表的第i個位置上的元素實現步驟： 將第i+1至第n位的元素向前移動一個位置； 表長減1。注意：事先需要判斷，刪除位置i是否合法？應當符合條件：K i < n 或i=1, n核心

5、語句：for ( j=i+1; j<=n; j+ )aj-1=aj;n-;順序表刪除一元素的時間效率為：T (n)=(n-1)/2疋0(n)順序表插入、刪除算法的平均空間復雜度為0(1)單鏈表:用單鏈表結構來存放26個英文字母組成的線性表(a, b, c，,， z),請寫出C語言程序。#in clude<stdio.h> #in clude<stdlib.h> typedef struct node char data;struct node *n ext;int i;head=(no de*)malloc(m); p=head;for( i=1; i<26

6、; i+) p->data=i+ a' -1;p-> next=( no de*)malloc(m); p=p->next ； p->data=i+ a' -1;p-> next=NULL ;void display()p=head;while (p)/m=sizeof( no de)前面已求出因尾結點要特殊處理，故iz 26/第一個結點值為字符a/為后繼結點“挖坑” ！/讓指針變量P指向后一個結點最后一個元素要單獨處理/單鏈表尾結點的指針域要置空！字母鏈表的輸出/當指針不空時循環(僅限于無頭結點的情況)n ode;node *p,*q,*head

7、;int n ;int m=sizeof( no de);一般需要3個指針變量/數據元素的個數/*結構類型定義好之后，每個node類型的長度就固定了,m求一次即可*/void build()/字母鏈表的生成。要一個個慢慢鏈入讓指針不斷“順藤摸瓜”prin tf("%c",p->data); p=p->n ext;(2)單鏈表的修改(或讀取)思路：要修改第i個數據元素，必須從頭指針起一直找到該結點的指針p,然后才能： p>data=n ew_value讀取第i個數據元素的核心語句是：Linklist *find(Linklist *head ,int i)

8、int j=1;Li nklist *p;P=head->n ext;While(p!=NULL)&&(j<i) p=p->n ext;j+； return p;3單鏈表的插入茲結點的生成方式土 S= (node*) ma I loc (m);S->next=p->nex t鏈表插入的核心語句：Step 1: s->next=p->next;Step 2： p->next=s ；6單鏈表的刪除刪除動作的核心語句(要借助輔助指針變量q)：q = p->next;/首先保存b的指針，靠它才能找到c;p->next=q-&g

9、t;next;將a、c兩結點相連，淘汰 b結點；free(q)；徹底釋放b結點空間7雙向鏈表的插入操作:二 3i-g口IL :二X 1設p已指向第i元素，請在第i元素前插入元素x: ai-1的后繼從ai (指針是p)變為x (指針是s):s_>n ext = p ;p->prior- >next = s ; ai的前驅從ai-1 (指針是p->prior)變為x (指針是s);s->prior = p ->prior ; p->prior = s ;8雙向鏈表的刪除操作:設p指向第i個元素，刪除第i個 元素 后繼方向：ai-1的后繼由ai （指針p）變

10、為ai+1（指針p ->next ）;p _>prior- >next =p_>n ext前驅方向：ai+1的前驅由ai （指針p）變為ai-1 （指針p -> prior ）;p->n ext->prior = p ->prior ;數組的邏輯結構定義及存儲數組：由一組名字相冋、下標不冋的變量構成N維數組的特點：n個下標，每個元素受到 n個關系約束一個n維數組可以看成是 由若干個n- 1維數組 組成的線性表。 存儲：事先約定按某種次序將數組元素排成一列序列，然后將這個線性序列存入存儲器中。在二維數組中，我們既可以規定按行存儲，也可以規定按列存儲

11、。設一般的二維數組是 Ac1.d1, c2.d2,Amu加皿亦我擔日1世則行優先存儲時的地址公式為：LOC（aij）=LOC（afb C2）+（i-c1）*（drc2+l）+j-c2）*L二維數組列優先存儲的通式為:LOC（現戸LOCQi 口田（j弋尸（血7十1）和-門）江稀疏矩陣（含特殊矩陣）的存儲及運算。稀疏矩陣：矩陣中非零元素的個數較少（一般小于 5%）學習重點：線性表的邏輯結構，指線性表的數據元素間存在著 線性關系。在順序存儲結構中，元素 存儲的先后位置反映出這種線性關系，而在鏈式存儲結構中，是靠 指針來反映這種關系的。順序存儲結構用一維數組表示，給定下標，可以存取相應元素，屬于隨機存

12、取的存儲結構。鏈表操作中應注意不要使鏈意外“斷開”。因此，若在某結點前插入一個元素，或刪除某元素，必須知道該元素的 前驅結點的指針。掌握通過畫出結點圖來進行鏈表（單鏈表、循環鏈表等）的生成、插入、刪除、遍歷 等操作。數組（主要是二維）在以 行序/列序為主的存儲中的地址計算方法。稀疏矩陣的三元組表存儲結構。稀疏矩陣的十字鏈表存儲方法。補充重點：1. 每個存儲結點都包含兩部分：數據域和指針域（鏈域）其直接前驅結點的鏈域的值指示。該結點的數據域可以為空，也可存放 可以對空表、非空表的情況以及對首2. 在單鏈表中，除了首元結點外，任一結點的存儲位置由3. 在鏈表中設置頭結點有什么好處？頭結點即在鏈表的

13、首元結點之前附設的一個結點， 表長度等附加信息，其作用是為了對鏈表進行操作時, 元結點進行統一處理，編程更方便。4. 如何表示空表？（1）無頭結點時，當頭指針的值為空時表示空表；（2）有頭結點時，當頭結點的指針域為空時表示空表。5. 鏈表的數據元素有兩個域，不再是簡單數據類型，編程時該如何表示？因每個結點至少有兩個分量，且數據類型通常不一致，所以要采用結構數據類型。6. sizeof（x）計算變量x的長度（字節數）；malloc（m） 開辟m字節長度的地址空間，并返回這段空間的首地址； free（p）釋放指針p所指變量的存儲空間，即徹底刪除一個變量。7. 鏈表的運算效率分析：（1）查找因線性鏈

14、表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為0（ n）。（2）插入和刪除因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復雜度為0（1）。但是，如果要在單鏈表中進行前插或刪除操作，因為要從頭查找前驅結點，所耗時間復雜 度將是0（n）。例：在n個結點的單鏈表中要刪除已知結點*P，需找到它的前驅結點的地址，其時間復雜度為0（ n）8. 順序存儲和鏈式存儲的區別和優缺點？順序存儲時，邏輯上相鄰的數據元素，其物理存放地址也相鄰。順序存儲的優點是存儲 密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈式存儲時，相鄰數據元素可隨意存放，但所占存儲空間分兩部分， 一部分存放結點

15、值，另一部分存放表示結點間關系的指針。鏈式存儲的優點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。 順序表適宜于做查找這樣的靜態操作; 鏈表宜于做插入、刪除這樣的動態操作。 若線性表的長度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9. 判斷：“數組的處理比其它復雜的結構要簡單”，對嗎？答：對的。因為一一 數組中各元素具有統一的類型； 數組元素的下標一般具有 固定的上界和下界，即數組一旦被定義，它的維數和維界就不 再改變。 數組的基本操作比較簡單，除了結構的初始化和銷毀之外，只有存取元素和修改元素值的

16、操作。10. 三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數據項，分別表示該元素的行下標、列下標和元素值。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)rr12 93 0:14241815-7IM法3:用三元組矩陣表示:value12122 1393313*3514彳A324E521BT6115R64-7稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能代碼:1用數組V來存放26個英文字母組成的線性表(

17、a，b，c， ,， z)，寫出在順序結構上生成法2:用十字鏈表表示 用途：方便稀疏矩陣的加減運算 方法：每個非0元素占用5個域和顯示該表的C語言程序。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( "n ");void main(void)/主函數，字母線性表

18、的生成和輸出n=26; / n是表長，是數據元素的個數，而不是V的實際下標build();display();第二章棧和隊列內容提要：從數據結構角度來講，棧和隊列也是線性表，其操作是線性表操作的子集，屬操作受限 的線性表。但從數據類型的角度看，它們是和線性表大不相同的重要抽象數據類型。棧的定義及操作。棧是只準在一端進行插入和刪除操作的線性表，該端稱為棧的頂端。 插入元素到棧頂的操作，稱為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。對于向上生成的堆棧：入棧口訣：堆棧指針top "先壓后加”：Stop+=a n+1出棧口訣：堆棧指針top "先減后彈”： e=S-top棧的順

19、序和鏈式存儲結構，及在這兩種結構下實現棧的操作。順序棧入棧函數PUSH ()status Push(ElemType e) if(top>M)上溢else stop+=e;順序棧出棧函數POP()status Pop() if(top=L) 下溢else e=s-top; return(e);隊列的定義及操作，隊列的刪除在一端（隊尾），而插入則在隊列的另一端（隊頭）。因此在兩種存儲結構中，都需要隊頭和隊尾兩個指針。隊列：只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。 鏈隊列結點類型定義：typedef Struct QNodeQEIemTypedata;/ 元素Struc

20、t QNode*n ext; /指向下一結點的指針Qnode , * QueuePtr ;鏈隊列類型定義：typedef struct QueuePtrfront ; / 隊首指針QueuePtrrear ; / 隊尾指針Lin kQueue;鏈隊示意圖：i*ca IfromJl旦 空鏈隊的特征：fron t=rear 鏈隊會滿嗎？ 一般不會，因為刪除時有free動作。除非內存不足! 入隊（尾部插入）：rear-next=S; rear=S;出隊（頭部刪除）：front->next=p->next;2順序隊順序隊類型定義：#defi neQUEUE-MAXSIZE100 /最大隊列

21、長度typedef struct QEIemType *base;intintSqQueue建隊核心語句：/隊列的基址front;II隊首指針rear;II隊尾指針q . base=(QEIemType *)malloc(sizeof (QEIemType* QUEUE_MAXSIZE;順序隊示意圖：II分配空間rear30ajai型3i.財i再A賦一宙Vtifrt嗎弓fron,空臥列的待征？I約定：frait rrar臥列會満嗎？ 概易裝瞞I因為昨筑| 常有悵度限制，而英前 端空何盂辭放。蟲樣實現人臥和也肌； 提作T權右諧句如下：|入:rear*+ .Qrrar|-c；出甌頭曲刪臨；rt k

22、 . e-Q h'o nl|;循環隊列：隊空條件：front = rear(初始化時：front = rear )隊滿條件：front = (rear+1) % N(N=maxsize)隊列長度(即數據元素個數)：L= ( N + rear- front) % N1) 初始化一個空隊列StatusInitQueue ( SqQueue&q ) / 初始化空循環隊列qq . base=(QEIemType *)malloc(sizeof(QEIemType )* QUEUE_MAXSIZE);/ 分配空間if (!q.base) exit(OVERFLOW);/內存分配失敗，退出

23、程序q.front =q.rear=0; / 置空隊歹Ureturn OK; /Ini tQueue;2) 入隊操作Status En Queue(SqQueue &q, QElemType e)/向循環隊列q的隊尾加入一個元素eif ( (q.rear+1) % QUEUE_MAXSIZE = = q.fro nt )return ERROR ; /隊滿則上溢，無法再入隊q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE;q.base q.rear = e;/新元素 e 入隊return OK;/ En Queue;3) 出隊操作Status DeQu

24、eue ( SqQueue &q, QElemType &e)/若隊列不空，刪除循環隊列q的隊頭元素，由e返回其值，并返回 OKif ( q.front = = q.rear )return ERROR;/ 隊列空q.fron t=(q.fro nt+1) % QUEUE_MAXSIZE ;e = q.base q.front ;return OK;/ DeQueue1等于隊頭鏈隊列空的條件是首尾指針相等，而循環隊列滿的條件的判定，則有隊尾加 和設標記兩種方法。補充重點：1. 為什么要設計堆棧？它有什么獨特用途？ 調用函數或子程序非它莫屬； 遞歸運算的有力工具； 用于保護現場和

25、恢復現場； 簡化了程序設計的問題。2. 為什么要設計隊列？它有什么獨特用途？ 離散事件的模擬（模擬事件發生的先后順序，例如CPU芯片中的指令譯碼隊列）； 操作系統中的作業調度（一個 CPU執行多個作業）； 簡化程序設計。3. 什么叫“假溢出”？如何解決？答：在順序隊中，當尾指針已經到了數組的上界，不能再有入隊操作， 但其實數組中還有空位置，這就叫“假溢出”。解決假溢出的途徑采用循環隊列。4. 在一個循環隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環隊列中刪除一個元素時，其操作是先移動隊首位置，后取出元素。5. 線性表、棧、隊的異同點：相同點：邏輯結構相同， 都是線性的；都可以用順

26、序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。不同點：運算規則不同：線性表為隨機存取；而棧是只允許在一端進行插入和刪除運算，因而是后進先出表LIFO ；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。用途不同，線性表比較通用；堆棧用于函數調用、遞歸和簡化設計等；隊列用于離散事 件模擬、OS作業調度和簡化設計等。第四章串內容提要：串是數據元素為字符的線性表，串的定義及操作。串即字符串，是由零個或多個字符組成的有限序列，是數據元素為單個字符的特殊線性表。串比較：int strcmp(char *s1,char *s2);求串

27、長：int strle n(char *s);串連接： char strcat(char *to,char *from)子串 T 定位：char strchr(char *s,char *c);串的存儲結構，因串是數據元素為字符的線性表，所以存在“結點大小”的問題。 模式匹配算法。串有三種機內表示方法：耐用一組地址連續的存儲單元存儲串垃的字存諸稱序列，屬ifr態存儲方式.堆令少存儲表示-用-組連續的存儲單元存儲串垃的字 符序列，但存瞎空同是在稈序執祎過程中彩 継吉分配而得*鷲誇串的塊雒捽儲表示仔臨鏈式方式存儲模式匹配算法：算法目的：確定主串中所含子串第一次出現的位置(定位)定位問題稱為串的模式

28、匹配，典型函數為In dex(S,T,pos)BF算法的實現一即編寫Index(S, T, pos)函數BF算法設計思想：將主串S的第pos個字符和模式T的第1個字符比較，若相等，繼續逐個比較后續字符；若不等，從主串S的下一字符(pos+1 )起，重新與T第一個字符比較。直到主串S的一個連續子串字符序列與模式T相等。返回值為 S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0。Int In dex_BP(SStri ng S, SStri ng T, i nt pos) /返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數值為0.其中，T 非空，1 <

29、 posw StrLength(S)i=pos; j=1;while ( i<=S0 && j<=T0 ) / 如果i,j二指針在正常長度范圍，if (Si = = Tj ) +i, +j; II則繼續比較后續字符else i=i-j+2; j=1; II若不相等，指針后退重新開始匹配if(j>T0) return i-T0; IIT 子串指針 j 正常到尾，說明匹配成功，else return 0;II否則屬于i>S0情況，i先到尾就不正常 III ndex_BP補充重點:1.空串和空白串有無區別？ 答：有區別。空串(Null String)是指長度為

30、零的串；而空白串(Biank String),是指包含一個或多個空白字符2.“空串是任意串的子串；任意串S都是S本身的子串,(空格鍵)的字符串S本身外，S的其他子串稱為S的真子串。f運建吉槍 s =* uiju.a*'定長順序存儲結構串T有儲齬構-堆存情結構二若干函數的實現1模式匹配算法模式匹配即子串定位運算即如何實現lDd<x(S,T,pflS)S第六章樹和二叉樹內容提要：樹是復雜的非線性數據結構，樹，二叉樹的遞歸定義，基本概念，術語。樹：由一個或多個（n> 0）結點組成的有限集合 T,有且僅有一個結點稱為根（root）,當n>1 時，其余的結點分為 m（m >

31、; 0）個互不相交的有限集合T1,T2 , , , Tm。每個集合本身又是棵樹，被稱作這個根的子樹。二叉樹：是n （n0）個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為左 子樹和右子樹的二叉樹組成。術語：P88二叉樹的性質，存儲結構。性質1:在二叉樹的第i層上至多有2i-1個結點（i>0 ）。性質2:深度為k的二叉樹至多有2k-1個結點（k>0 ）。性質3:對于任何一棵二叉樹，若 2度的結點數有n2個，則葉子數（n0）必定為n2 + 1 性質4:具有n個結點的完全二叉樹的深度必為 性質5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結點，其左孩子編號必為2i，其

32、右孩子編號為 2i + 1;其雙親的編號必為i/2 （i = 1時為根，除外）。二叉樹的存儲結構：一、順序存儲結構按二叉樹的結點“自上而下、從左至右”編號，用一組連續的存儲單元存儲。 若是完全/滿二叉樹則可以做到唯一復原。不是完全二叉樹：一律轉為完全二叉樹！方法很簡單，將各層空缺處統統補上“虛結點”，其內容為空。缺點：浪費空間；插入、刪除不便二、鏈式存儲結構用二叉鏈表即可方便表示。一般從根結點開始存儲。irlt Cbtdngbt (hldd優點：不浪費空間；插入、刪除方便二叉樹的遍歷。指按照某種次序訪問二叉樹的所有結點，并且每個結點僅訪問一次，得到一個線性序列。 遍歷規則二叉樹由根、左子樹、右

33、子樹構成，定義為D、 L、R若限定先左后右，則有三種實現方案：DLR先序遍歷LDR中序遍歷LRD后序遍歷樹的存儲結構，樹、森林的遍歷及和二叉樹的相互轉換。回顧2 :二叉樹怎樣還原為樹？要點：逆操作，把所有右孩子變為兄弟！討論1 :森林如何轉為二叉樹？法一： 各森林先各自轉為二叉樹；依次連到前一個二叉樹的右子樹上。法二：森林直接變兄弟，再轉為二叉樹討論2 :二叉樹如何還原為森林？要點：把最右邊的子樹變為森林，其余右子樹變為兄弟樹和森林的存儲方式：樹有三種常用存儲方式： 雙親表示法孩子表示法孩子一兄弟表示法問：樹t二叉樹的“連線一抹線一旋轉”如何由計算機自動實現？答：用“左孩子右兄弟”表示法來存儲

34、即可。存儲的過程就是樹轉換為二叉樹的過程！樹、森林的遍歷：探度優先第歷（先脈怎和 需驚蹩？皿1廣度憂去遁歷（層執】 先根遍歷：訪問根結點；依次先根遍歷根結點的每棵子樹。 后根遍歷：依次后根遍歷根結點的每棵子樹；訪問根結點。 討論：樹若采用“先轉換，后遍歷”方式，結果是否一樣？1. 樹的先根遍歷與二叉樹的先序遍歷相同；2. 樹的后根遍歷相當于二叉樹的中序遍歷；3. 樹沒有中序遍歷，因為子樹無左右之分。淼林的逼歷-深度優先遍歷£先序、申序）廣度優先遍歷層次1 先序遍歷若森林為空，返回； 訪問森林中第一棵樹的根結點；先根遍歷第一棵樹的根結點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構成的

35、森林。 中序遍歷若森林為空，返回； 中根遍歷森林中第一棵樹的根結點的子樹森林； 訪問第一棵樹的根結點；中根遍歷除去第一棵樹之后剩余的樹構成的森林。二叉樹的應用：哈夫曼樹和哈夫曼編碼。Huffman樹：最優二叉樹（帶權路徑長度最短的樹）Huffman編碼：不等長編碼。n樹的帶權路徑長度：（樹中所有葉子結點的帶權路徑長度之和） 構造Huffman樹的基本思想：權值大的結點用短路徑，權值小的結點用長路徑。構造Huffman樹的步驟（即 Huffman算法）：（1）由給定的n個權值 w1, w2, , , wn 構成n棵二叉樹的集合 F = T1, T2, , , Tn （即 森林），其中每棵二叉樹

36、Ti中只有一個帶權為 wi的根結點，其左右子樹均空。（2）在F中選取兩棵根結點權值最小的樹做為左右子樹構造一棵新的二叉樹，且讓新二叉樹根結點的權值等于其左右子樹的根結點權值之和。 在F中刪去這兩棵樹，同時將新得到的二叉樹加入F中。重復和，直到F只含一棵樹為止。這棵樹便是Huffman樹。具體操作步驟：stepl：對權值進行合并、刪除與替換在權値東合忡,5t2, 4中，總是合井當的最小的兩個權a.初始令并國同FH7K11吐合井（11Ft 11step2：按左“（T右"F對Htlffman樹的所有分支編號將Huffman樹與Huffman碼掛鉤a 21 ri nHuffinan編碼結果：

37、d=： , i= t a- 0, n=WFL=lbitX7+2MtX5+3bitQ+4）=35 （小于尊長碼的ffFL=36）學習重點：（本章內容是本課程的重點）二叉樹性質及證明方法，并能把這種方法推廣到K叉樹。二叉樹遍歷，遍歷是基礎，由此導出許多實用的算法，如求二叉樹的高度、各結點的層 次數、度為0、1、2的結點數。由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構造一棵二叉樹。由前序和 后序序列不能唯一確定一棵二叉樹。完全二叉樹的性質。樹、森林和二叉樹間的相互轉換。哈夫曼樹的定義、構造及求哈夫曼編碼。補充：1. 滿二叉樹和完全二叉樹有什么區別？答：滿二叉樹是葉子一個也不少的樹，而完全二

38、叉樹雖然前k-1層是滿的，但最底層卻允許在右邊缺少連續若干個結點。滿二叉樹是完全二叉樹的一個特例。2. Huffman樹有什么用？最小冗余編碼、信息高效傳輸第七章圖內容提要：圖的定義，概念、術語及基本操作。圖：記為 G= （ V, E ）其中：V是G的頂點集合，是有窮非空集；E是G的邊集合，是有窮集。術語：見課件圖的存儲結構。1鄰接矩陣（數組）表示法 建立一個頂點表和一個鄰接矩陣 設圖A = （V, E）有n個頂點，則圖的鄰接矩陣是一個二維數組A.Edgenn。注：在有向圖的鄰接矩陣中，第i行含義：以結點 vi為尾的弧（即出度邊）；第i列含義：以結點 vi為頭的弧（即入度邊）。鄰接矩陣法優點：

39、容易實現圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（弧）找頂點的鄰接點等等。鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊（弧）;空間效率為0（n2）。2鄰接表（鏈式）表示法 對每個頂點vi建立一個單鏈表，把與 vi有關聯的邊的信息（即度或出度邊）鏈接起來, 表中每個結點都設為 3個域：頭站點表蛤點 每個單鏈表還應當附設一個頭結點（設為 2個域），存vi信息； 每個單鏈表的頭結點另外用順序存儲結構存儲。鄰接表的優點：空間效率高；容易尋找頂點的鄰接點；鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜索兩結點對應的單鏈表，沒有鄰接矩陣方 便。圖的遍歷。遍歷定義：從已給的連通圖中某一頂點出發，沿著

40、一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。圖常用的遍歷：一、深度優先搜索；二、廣度優先搜索 深度優先搜索（遍歷）步驟： 訪問起始點v; 若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點； 若當前鄰接點已訪問過，再找 v的第2個鄰接點重新遍歷。 基本思想：一一仿樹的先序遍歷過程。廣度優先搜索（遍歷）步驟： 在訪問了起始點v之后，依次訪問 v的鄰接點； 然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點; 直到所有頂點都被訪問過為止。圖的應用（最小生成樹，最短路經）最小生成樹（MST ）的性質如下：若 U集是V的一個非空子集，若（uO, vO）是一

41、條最小 權值的邊，其中 uO U , vO V-U ;則：（uO, vO）必在最小生成樹上。求MST最常用的是以下兩種：Kruskal （克魯斯卡爾）算法、 Prim （普里姆）算法Kruskal算法特點：將邊歸并，適于求稀疏網的最小生成樹。Prime算法特點：將頂點歸并，與邊數無關，適于稠密網。Kruskal法示剛：對邊操作*舊井邊普利姆（Prim）算法示例：歸井頂點在帶權有向圖中 A點（源點）到達 B點（終點）的多條路徑中，尋找一條各邊權值之和最 小的路徑，即最短路徑。兩種常見的最短路徑問題：一、單源最短路徑一用 Dijkstra （迪杰斯特拉）算法二、所有頂點間的最短路徑一用Floyd

42、（弗洛伊德）算法一、單源最短路徑（Dijkstra算法）一頂點到其余各頂點（vOj）目的： 設一有向圖G= （V, E）,已知各邊的權值，以某指定點vO為源點，求從vO到圖的其余各點的最短路徑。限定各邊上的權值大于或等于0。二、所有頂點之間的最短路徑可以通過調用n次Dijkstra算法來完成，還有更簡單的一個算法：Floyd算法（自學）。學習重點：圖是應用最廣泛的一種數據結構，本章也是這門課程的重點。基本概念中，連通分量，生成樹，鄰接點是重點。 連通圖：在無向圖中，若從頂點v1到頂點v2有路徑，則稱頂點v1與v2是連通的。 如果圖中任意一對頂點都是連通的，則稱此圖是連通圖。非連通圖的極大連通子

43、圖叫做 連通分量。 生成樹：是一個極小連通子圖，它含有圖中全部n個頂點，但只有n-1條邊。 鄰接點：若（u, v）是E（G）中的一條邊，則稱 u與v互為鄰接頂點。圖是復雜的數據結構，也有順序和鏈式兩種存儲結構：數組表示法（重點是鄰接距陣） 和鄰接表。這兩種存儲結構對有向圖和無向圖均適用圖的遍歷是圖的各種算法的基礎，應熟練掌握圖的深度、廣度優先遍歷。應熟練掌連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權值之和是唯一的。握 prim 和 kruscal 算法，從單源點到其他頂點，以及各個頂點間的最短路徑問題，掌握熟練手工模擬。補充：1. 問：當有向圖中僅 1個頂點的入度為0,其余頂點的入度均為

44、 1,此時是何形狀？ 答：是樹！而且是一棵有向樹！2. 討論：鄰接表與鄰接矩陣有什么異同之處？1. 聯系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數等于一行中非零元素的個數。2. 區別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。3. 用途：鄰接矩陣多用于稠密圖的存儲而鄰接表多用于稀疏圖的存儲3. 若對連通圖進行遍歷，得到的是生成樹若對非連通圖進行遍歷，得到的是生成森林。第八章 查找內容提要：查找表是稱為集合的數據結構。是元素間約束力最差的數據結構：元素間的關系是元素 僅共在同一個集合中。（同一類型的數據元素構成的集合）

45、查找表的操作：查找，插入，刪除。靜態查找表：順序表，有序表等。針對靜態查找表的查找算法主要有：順序查找、折半查找、分塊查找一、順序查找（線性查找）技巧：把待查關鍵字 key存入表頭或表尾（俗稱“哨兵”）,這樣可以加快執行速度。int Search_Seq（ SSTable ST , KeyType key ） ST.elemO.key =key;for（ i=ST.le ngth; ST.elem i .key!=key;- - i ）;return i; / Search_Seq/ASL =（ 1 + n） /2，時間效率為 0（n）,這是查找成功的情況： 順序查找的特點：優點：算法簡單，且

46、對順序結構或鏈表結構均適用。 缺點：ASL太大，時間效率太低。二、折半查找（二分或對分查找）若關鍵字不在表中，怎樣得知并及時停止查找？ 典型標志是：當查找范圍的上界w下界時停止查找。ASL的含義是“平均每個數據的查找時間”，而前式是n個數據查找時間的總和，所以:ASL j 2Jlog2（n 1） 1 ： log2 nn yn三、分塊查找（索引順序查找）思路：先讓數據分塊有序，即分成若干子表，要求每個子表中的數據元素值都比后一塊中的 數值小（但子表內部未必有序）。然后將各子表中的最大關鍵字構成一個索引表，表中還要 包含每個子表的起始地址（即頭指針）。特點：塊間有序，塊內無序。查找：塊間折半，塊內

47、線性查找步驟分兩步進行： 對索引表使用折半查找法（因為索引表是有序表）； 確定了待查關鍵字所在的子表后，在子表內采用順序查找法 （因為各子表內部是無序表）查找效率ASL分析：ASLsU+L-B 對盍引表査推的|_對塊內査找胯氏$1址加=+ - 佃“"豈丿抵M .）-.3希毎塊內課的吐貿晞叩塊的茹目二）殂折半佚要預 一先全排序肝爲時何.創即當n-叫5=33 J r 分快法的楓.=3. 5 而折半迭的開日1 噸瑋法咖L珂L+nW動態查找表：二叉排序樹，平衡二叉樹。特點：表結構在查找過程中動態生成。要求：對于給定值 key,若表中存在其關鍵字等于key的記錄，則查找成功返回；否則插入關鍵字

48、等于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 /繼續向左搜索K&

49、gt; p->data : q=p ； p=p->R_child / 繼續向右搜索查找不成功則插入到二叉排序樹中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; /

50、 若 K 比葉子大，掛右邊return OK 二叉排序樹的刪除操作如何實現？如何刪除一個結點？假設：若在A的屮子甘的 挖亍時 上J*入姑 A,血乂的*斷因子從-塔扣至簽 5E事卻疔顧Mfi驢齊建時 針如/'、j鼻 人的 佶ju 內 撬轉匸二學習重點：查找表是稱為集合的數據結構。因元素間關系非常松散，其操作需借助其它數據結構來 實現。本章列舉了三種方法(靜態查找表，動態查找表)實現查找表的運算。順序表因設置了監視哨使查找效率大大提高。有序表的平均查找長度不超過樹的深度。查找的ASL二叉排序樹的形態取決于元素的輸入順序。按中序遍歷可得到結點的有序序列，應熟練 掌握其建立、查找，插入和刪除算

51、法。平衡二叉樹的概念，應熟練掌握手工繪制平衡二叉樹。p表示被刪結點的指針；PL和PR分別表示*P的左、右孩子指針;*f表示*p的雙親結點指針；并假定 *p是*f的左孩子；則可能有三種情況:|巾為葉了 LJW除此結點時”直接悔改曲域即可：彳打只有Tt了討（虹或右）±鋰卑吃為*f曲左曲子即町:I衍有兩操子樹=悟況矍琳-4二叉排序樹的AS.<2(l + -L)ln it1 平衡二叉樹的定義：又稱AVL樹，即它或者是一顆空樹， 或者是它的左子樹和右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對值不超過1。平衡因子：該結點的左子樹的深度減去它的右子樹的深度。平衡二叉樹的特點：任一結

52、點的平衡因子只能取：-1、0或1。如果在一棵AVL樹中插入一個新結點，就有可能造成失衡，此時必須重新調整樹的結構, 使之恢復平衡。我們稱調整平衡過程為平衡旋轉。平衡旋轉可以歸納為四類:1 LL平衡旋轉：軸魂” niAftS牛布囚子派1堆加垂 2,齢筑忙-心5時針蓋稱*野在也站占干禪陽 生 子樽上妞 人 箱點+ OtA昨平衙兇子啟1期抽3) LR平衡康轉:若 灰A的士子甘的 右子+上J6人 A, TltA的辛街因子從L堆加生 1,需奐st琨好夠葉汁程轉.再4) RL平衡族轉:補充：1. 查找的過程是怎樣的？給定一個值K，在含有n個記錄的文件中進行搜索，尋找一個關鍵字值等于K的記錄,如找到則輸出該

53、記錄，否則輸出查找不成功的信息。2. 對查找表常用的操作有哪些？查詢某個"特定的”數據元素是否在表中；查詢某個"特定的”數據元素的各種屬性； 在查找表中插入一元素；從查找表中刪除一元素。3. 哪些查找方法？查找方法取決于表中數據的排列方式；4. 如何評估查找方法的優劣？用比較次數的平均值來評估算法的優劣。稱為平均查找長度ASL。ASL=刀 Pi. Ci5. 使用折半查找算法時，要求被查文件：采用順序存貯結構、記錄按關鍵字遞增有序6. 將線性表構造成二叉排序樹的優點： 查找過程與順序結構有序表中的折半查找相似，查找效率高； 中序遍歷此二叉樹，將會得到一個關鍵字的有序序列（即實現了排序運算）； 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結點上，而且插入或刪除