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

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

2、與定義在該模型上的一組操作，它由基本的數(shù)據(jù)類型構(gòu)成。 算法的定義及五個特征。算法 是對特定問題求解步驟的一種描述， 它是指令的有限序列， 是一系列輸入轉(zhuǎn)換為輸出的計算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性 算法設(shè)計要求。正確性、可讀性、健壯性、效率與低存儲量需求 算法分析。時間復雜度、空間復雜度、穩(wěn)定性學習重點： 數(shù)據(jù)結(jié)構(gòu)的“三要素” ：邏輯結(jié)構(gòu) 、物理（存儲）結(jié)構(gòu)及在 這種結(jié)構(gòu)上所定義的操作（運卑微如螻蟻、堅強似大象共享知識分享快樂算）。 用計算語句頻度來估算算法的時間復雜度。第二章 線性表內(nèi)容提要： 線性表的邏輯結(jié)構(gòu)定義，對線性表定義的操作。線性表的定義：用數(shù)據(jù)元素的有限

3、序列表示 線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲定義：把邏輯上相鄰 的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。鏈式存儲結(jié)構(gòu) : 其結(jié)點在存儲器中的位置是隨意的， 即邏輯上 相鄰的數(shù)據(jù)元素在物理上 不一定相鄰。通過 指針 來實現(xiàn)！ 線性表的操作在兩種存儲結(jié)構(gòu)中的實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的基本運算：修改、插入、刪除、查找、排序1) 修改通過數(shù)組的下標便可訪問某個特定元素并修改之。核心語句 :Vi=x;順序表修改操作的時間效率是O(1)2) 插入在線性表的第 i 個位置前插入一個元素實現(xiàn)步驟：將第 n 至第 i 位的元素向后移動一個位置；將要插入的元素寫到第i 個位置；表長加1。注意：

4、事先應(yīng)判斷: 插入位置i 是否合法 ?表是否已滿 ?應(yīng)當符合條件：1 i n+1或i=1, n+1核心語句：for (j=n; j>=i; j-)aj+1=a j ;a i =x;n+;插入時的平均移動次數(shù)為：n(n+1)/2 ÷（ n+1） n/2O(n)3) 刪除刪除線性表的第i 個位置上的元素實現(xiàn)步驟：將第 i+1 至第 n 位的元素向前移動一個位置；表長減1。注意：事先需要判斷，刪除位置i 是否合法 ?應(yīng)當符合條件：1 i n或i=1, n核心語句：for ( j=i+1; j<=n; j+ )卑微如螻蟻、堅強似大象共享知識分享快樂aj-1=aj;n-;順序表刪除

5、一元素的時間效率為:T （ n)=(n-1)/2 O(n)順序表插入、刪除算法的平均空間復雜度為O(1)單鏈表：（ 1）用單鏈表結(jié)構(gòu)來存放26 個英文字母組成的線性表（a， b，c， ， z） ,請寫出 C 語言程序。#include<stdio.h>#include<stdlib.h>typedef struct nodechar data;struct node *next;node;node *p,*q,*head;/ 一般需要 3 個指針變量int n ;/ 數(shù)據(jù)元素的個數(shù)int m=sizeof(node);/* 結(jié)構(gòu)類型定義好之后，每個node 類型的長度就

6、固定了，m 求一次即可 */void build( )/ 字母鏈表的生成。要一個個慢慢鏈入int i;head=(node*)malloc(m);/m=sizeof(node)前面已求出p=head;for( i=1; i<26; i+)/因尾結(jié)點要特殊處理，故i 26p->data=i+ a -1;/ 第一個結(jié)點值為字符ap->next=(node*)malloc(m);/ 為后繼結(jié)點“挖坑” ！p=p->next ；/ 讓指針變量P 指向后一個結(jié)點p->data=i+ a -1;/最后一個元素要單獨處理p->next=NULL ;/單鏈表尾結(jié)點的指針域要

7、置空！void display()/ 字母鏈表的輸出p=head;while (p)/ 當指針不空時循環(huán)（僅限于無頭結(jié)點的情況）printf("%c",p->data);p=p->next;/讓指針不斷“順藤摸瓜”卑微如螻蟻、堅強似大象共享知識分享快樂（2）單鏈表的修改(或讀?。┧悸罚阂薷牡趇 個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點的指針p，然后才能： p>data=new_value讀取第 i 個數(shù)據(jù)元素的核心語句是：Linklist *find(Linklist *head ,int i)int j=1;Linklist *p;P=head->

8、;next;While(p!=NULL)&&(j<i)p=p->next;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 兩結(jié)點相連，淘汰b 結(jié)點；free(q) ；/徹底釋放b 結(jié)點空間7.雙向鏈表的插入操作：設(shè) p 已指向第i 元素，請在第i 元素前插入元素x：

9、 ai-1 的后繼從 ai ( 指針是 p)變?yōu)?x（指針是 s) :s->next = p;p->prior->next = s ;卑微如螻蟻、堅強似大象共享知識分享快樂 ai 的前驅(qū)從 ai-1 ( 指針是 p->prior) 變?yōu)?x ( 指針是 s);s->prior = p ->prior ; p->prior = s ;8.雙向鏈表的刪除操作：設(shè) p 指向第i 個元素，刪除第i 個 元素后繼方向： ai-1 的后繼由ai ( 指針 p)變?yōu)閍i+1(指針p ->next );p ->prior->next =p->n

10、ext;前驅(qū)方向： ai+1 的前驅(qū)由ai ( 指針 p)變?yōu)?ai-1 (指針p -> prior );p->next->prior = p ->prior ; 數(shù)組的邏輯結(jié)構(gòu)定義及存儲數(shù)組：由一組名字相同、下標不同的變量構(gòu)成N 維數(shù)組的特點：n 個下標，每個元素受到n 個關(guān)系約束一個 n 維數(shù)組可以看成是由若干個n 1 維數(shù)組 組成的線性表。存儲：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存入存儲器中。在二維數(shù)組中，我們既可以規(guī)定按行存儲，也可以規(guī)定按列存儲。設(shè)一般的二維數(shù)組是Ac1.d1, c2.d2 ，則行優(yōu)先存儲時的地址公式為：二維數(shù)組列優(yōu)先

11、存儲的通式為： 稀疏矩陣（含特殊矩陣）的存儲及運算。稀疏矩陣：矩陣中非零元素的個數(shù)較少（一般小于5%）學習重點： 線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系 。在順序存儲結(jié)構(gòu)中，元素存儲的 先后位置 反映出這種線性關(guān)系，而在鏈式存儲結(jié)構(gòu)中，是靠指針來反映這種關(guān)系的。 順序存儲結(jié)構(gòu)用一維數(shù)組表示，給定下標，可以存取相應(yīng)元素，屬于隨機存取 的存儲結(jié)構(gòu)。 鏈表操作中應(yīng)注意不要使鏈意外“斷開” 。因此，若在某結(jié)點前插入一個元素，或刪除某元素，必須知道該元素的 前驅(qū)結(jié)點的指針 。 掌握通過畫出結(jié)點圖來進行鏈表（單鏈表、循環(huán)鏈表等）的生成、插入、刪除、遍歷等操作。 數(shù)組（主要是二維）在以行序 /

12、列序 為主的存儲中的地址計算方法。卑微如螻蟻、堅強似大象共享知識分享快樂 稀疏矩陣的三元組表存儲結(jié)構(gòu)。 稀疏矩陣的十字鏈表存儲方法。補充重點：1.每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和指針域(鏈域 )2.在單鏈表中， 除了首元結(jié)點外， 任一結(jié)點的存儲位置由其直接前驅(qū)結(jié)點的鏈域的值指示。3.在鏈表中設(shè)置頭結(jié)點有什么好處？頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的 數(shù)據(jù)域可以為空，也可存放表長度 等附加信息， 其作用是為了對鏈表進行操作時， 可以對 空表、非空表 的情況以及對 首元結(jié)點 進行統(tǒng)一處理，編程更方便。4.如何表示空表？（ 1）無頭結(jié)點時，當頭指針的值為空時表示空表；（ 2）有頭結(jié)

13、點時，當頭結(jié)點的指針域為空時表示空表。5.鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。6.sizeof(x) 計算變量x 的長度（字節(jié)數(shù)） ；malloc(m) 開辟 m 字節(jié)長度的地址空間，并返回這段空間的首地址； free(p) 釋放指針 p 所指變量的存儲空間，即徹底刪除一個變量。7.鏈表的運算效率分析：（ 1）查找因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為O(n) 。（ 2） 插入和刪除因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復雜度為O(1) 。但是，如果要

14、在單鏈表中進行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復雜度將是 O(n) 。例：在n 個結(jié)點的單鏈表中要刪除已知結(jié)點*P ，需找到它的前驅(qū)結(jié)點的地址，其時間復雜度為O（ n ）8.順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？順序存儲時， 邏輯上相鄰的數(shù)據(jù)元素， 其物理存放地址也相鄰。 順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈式存儲時， 相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。 鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作；

15、鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9. 判斷：“數(shù)組的處理比其它復雜的結(jié)構(gòu)要簡單”，對嗎？答：對的。因為 數(shù)組中各元素具有統(tǒng)一的類型； 數(shù)組元素的下標一般具有 固定的上界和下界 ，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。數(shù)組的 基本操作比較簡 單，除了結(jié)構(gòu)的初始化和銷毀之外， 只有存取元素和修改元素值的操作。10.三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別卑微如螻蟻、堅強似大象共享知識分享快樂表示該元素的行下標、列下標和 元素值。1

16、1.寫出右圖所示稀疏矩陣的壓縮存儲形式。解：介紹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），寫出在順序結(jié)構(gòu)上生成和顯示該表的 C 語言程序。char V30;void build()/字母線性表的

17、生成，即建表操作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)/主函數(shù)，字母線性表的生成和輸出n=26; / n 是表長，是數(shù)據(jù)元素的個數(shù)，而不是V 的實際下標build( );卑微如螻蟻、堅強似大象共享知識分享快樂display( );第三章 棧和隊列內(nèi)容提要： 從數(shù)據(jù)結(jié)構(gòu)角度來

18、講，棧和隊列也是線性表，其操作是線性表操作的子集，屬操作受限的線性表。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。 棧的定義及操作。棧是只準在一端進行插入和刪除操作的線性表，該端稱為棧的頂端。插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。對于向上生成的堆棧:入?？谠E：堆棧指針top “先壓后加”:Stop+=an+1出?？谠E：堆棧指針top “先減后彈”:e=S-top 棧的順序和鏈式存儲結(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實現(xiàn)棧的操作。順序棧入棧函數(shù)PUSH （）status Push(ElemType e) if(top>M)上溢 else stop+

19、=e;順序棧出棧函數(shù)POP()status Pop( ) if(top=L) 下溢else e=s-top;return(e);卑微如螻蟻、堅強似大象共享知識分享快樂 隊列的定義及操作，隊列的刪除在一端（隊尾），而插入則在隊列的另一端（隊頭）。因此在兩種存儲結(jié)構(gòu)中，都需要隊頭和隊尾兩個指針。隊列：只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。鏈隊列結(jié)點類型定義：typedef Struct QNodeQElemTypedata;/ 元素StructQNode*next;/指向下一結(jié)點的指針Qnode , * QueuePtr ;鏈隊列類型定義：typedefstruct Que

20、uePtrfront ; / 隊首指針QueuePtrrear ; /隊尾指針LinkQueue;鏈隊示意圖：空鏈隊的特征：front=rear鏈隊會滿嗎？一般不會，因為刪除時有free 動作。除非內(nèi)存不足！入隊（尾部插入） ： rear->next=S; rear=S;出隊（頭部刪除） ： front->next=p->next;2.順序隊順序隊類型定義：#defineQUEUE-MAXSIZE100/ 最大隊列長度typedefstruct QElemType*base;/隊列的基址intfront;/隊首指針intrear;/ 隊尾指針SqQueue建隊核心語句：q .

21、 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）初始化一個空隊列StatusInitQueue ( SqQueue&q ) / 初始化空循環(huán)隊列qq . base=(QElemType *)malloc(sizeo

22、f(QElemType）* QUEUE_MAXSIZE);/ 分配空間if (!q.base)exit(OVERFLOW);/內(nèi)存分配失敗，退出程序q.front =q.rear=0; / 置空隊列return OK; /InitQueue;2）入隊操作StatusEnQueue(SqQueue&q,QElemType e)/ 向循環(huán)隊列q 的隊尾加入一個元素eif (q.rear+1) %QUEUE_MAXSIZE = =q.front)returnERROR ; / 隊滿則上溢，無法再入隊q.rear = ( q . rear + 1 ) %QUEUE_MAXSIZE;q.base

23、 q.rear = e;/ 新元素 e 入隊returnOK;/ EnQueue;3）出隊操作StatusDeQueue ( SqQueue&q,QElemType &e)/ 若隊列不空，刪除循環(huán)隊列q 的隊頭元素，/由 e 返回其值，并返回OKif ( q.front = = q.rear )return ERROR;/ 隊列空q.front=(q.front+1) % QUEUE_MAXSIZE ;e = q.base q.front ;return OK;/ DeQueue 鏈隊列空的條件是首尾指針相等，而循環(huán)隊列滿的條件的判定，則有隊尾加1 等于隊頭卑微如螻蟻、堅強似大

24、象共享知識分享快樂和設(shè)標記兩種方法。補充重點：1.為什么要設(shè)計堆棧？它有什么獨特用途？ 調(diào)用函數(shù)或子程序非它莫屬； 遞歸運算的有力工具； 用于保護現(xiàn)場和恢復現(xiàn)場； 簡化了程序設(shè)計的問題。2.為什么要設(shè)計隊列？它有什么獨特用途？ 離散事件的模擬（模擬事件發(fā)生的先后順序,例如CPU 芯片中的指令譯碼隊列）； 操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU 執(zhí)行多個作業(yè)） ； 簡化程序設(shè)計。3.什么叫“假溢出”？如何解決？答：在順序隊中，當尾指針已經(jīng)到了數(shù)組的上界， 不能再有入隊操作， 但其實數(shù)組中還有空位置，這就叫“假溢出” 。解決假溢出的途徑采用循環(huán)隊列。4.在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一

25、個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是先移動隊首位置，后取出元素 。5.線性表、棧、隊的異同點：相同點：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。不同點：運算規(guī)則不同：線性表為隨機存??；而棧是只允許在一端進行插入和刪除運算，因而是后進先出表LIFO ；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO 。 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計等；隊列用于離散事件模擬、 OS 作業(yè)調(diào)度和簡化設(shè)計等。卑微如螻蟻、堅強似大象共享知識分享快樂第四章串內(nèi)容提要：

26、 串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。串比較： int strcmp(char *s1,char *s2);求串長： int strlen(char *s);串連接： charstrcat(char *to,char *from)子串 T 定位： char strchr(char *s,char *c); 串的存儲結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點大小”的問題。模式匹配算法。串有三種機內(nèi)表示方法：模式匹配算法：算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）定位問題稱為串的模式匹配，典型

27、函數(shù)為Index(S,T,pos)BF 算法的實現(xiàn)即編寫Index(S, T, pos)函數(shù)BF 算法設(shè)計思想：將主串 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./ 其中

28、， T 非空， 1 posStrLength(S)i=pos;j=1;while ( i<=S0 && j<=T0 ) /如果 i,j 二指針在正常長度范圍，卑微如螻蟻、堅強似大象共享知識分享快樂if (Si = = Tj ) +i, +j; / 則繼續(xù)比較后續(xù)字符else i=i-j+2; j=1; /若不相等，指針后退重新開始匹配if(j>T0) return i-T0; /T 子串指針 j 正常到尾，說明匹配成功， else return 0; / 否則屬于 i>S0 情況， i 先到尾就不正常 /Index_BP補充重點：1.空串和空白串有無區(qū)別

29、？答：有區(qū)別?？沾?(Null String) 是指長度為零的串；而空白串 (BlankString), 是指包含一個或多個空白字符 (空格鍵 )的字符串 .2.“空串是任意串的子串；任意串S 都是 S 本身的子串，除S 本身外， S 的其他子串稱為S的真子串?！北拔⑷缦N蟻、堅強似大象共享知識分享快樂第六章 樹和二叉樹內(nèi)容提要： 樹是復雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。樹：由一個或多個 (n 0)結(jié)點組成的有限集合 T ，有且僅有一個結(jié)點稱為根（ root），當 n>1 時，其余的結(jié)點分為 m(m 0)個互不相交的有限集合 T1,T2 ， ， Tm。每個集合本身又

30、是棵樹，被稱作這個根的子樹。二叉樹：是 n（ n0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。術(shù)語： P88 二叉樹的性質(zhì)，存儲結(jié)構(gòu)。性質(zhì) 1: 在二叉樹的第i 層上至多有2i-1 個結(jié)點（ i>0 ）。性質(zhì) 2: 深度為 k 的二叉樹至多有2k-1 個結(jié)點（ k>0 ）。性質(zhì) 3: 對于任何一棵二叉樹，若2 度的結(jié)點數(shù)有n2 個，則葉子數(shù)（n0）必定為n2 1性質(zhì) 4: 具有 n 個結(jié)點的完全二叉樹的深度必為性質(zhì) 5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為 2i ，其右孩子編號為2i1；其雙親的編

31、號必為i/2 （i 1 時為根 ,除外）。二叉樹的存儲結(jié)構(gòu)：一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。若是完全 /滿二叉樹則可以做到唯一復原。不是完全二叉樹：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空。缺點：浪費空間；插入、刪除不便二、鏈式存儲結(jié)構(gòu)用二叉鏈表即可方便表示。一般從根結(jié)點開始存儲。優(yōu)點：不浪費空間；插入、刪除方便 二叉樹的遍歷。指按照某種次序訪問二叉樹的所有結(jié)點，并且每個結(jié)點僅訪問一次，得到一個線性序列。遍歷規(guī)則二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、R若限定先左后右，則有三種實現(xiàn)方案：卑微如螻蟻、堅

32、強似大象共享知識分享快樂DLRLDRLRD先序遍歷中序遍歷后序遍歷 樹的存儲結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換?；仡?2：二叉樹怎樣還原為樹？要點：逆操作，把所有右孩子變?yōu)樾值?！討?1：森林如何轉(zhuǎn)為二叉樹？法一：各森林先各自轉(zhuǎn)為二叉樹；依次連到前一個二叉樹的右子樹上。法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹討論 2：二叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值軜浜蜕值拇鎯Ψ绞剑簶溆腥N常用存儲方式：雙親表示法孩子表示法孩子兄弟表示法問：樹二叉樹的“連線抹線旋轉(zhuǎn)”如何由計算機自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。存儲的過程就是樹轉(zhuǎn)換為二叉樹的過程！樹、森

33、林的遍歷： 先根遍歷：訪問根結(jié)點；依次先根遍歷根結(jié)點的每棵子樹。 后根遍歷：依次后根遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？1. 樹的先根遍歷與二叉樹的先序遍歷相同；2. 樹的后根遍歷相當于二叉樹的中序遍歷；3. 樹沒有中序遍歷，因為子樹無左右之分。 先序遍歷卑微如螻蟻、堅強似大象共享知識分享快樂若森林為空，返回；訪問森林中第一棵樹的根結(jié)點；先根遍歷第一棵樹的根結(jié)點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結(jié)點的子樹森林；訪問第一棵樹的根結(jié)點；中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的

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

35、根結(jié)點的權(quán)值等于其左右子樹的根結(jié)點權(quán)值之和。(3)在 F 中刪去這兩棵樹，同時將新得到的二叉樹加入F 中。(4)重復 (2) 和 (3) , 直到 F 只含一棵樹為止。這棵樹便是Huffman 樹。具體操作步驟：卑微如螻蟻、堅強似大象共享知識分享快樂學習重點：（本章內(nèi)容是本課程的重點） 二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K 叉樹。 二叉樹遍歷，遍歷是基礎(chǔ)，由此導出許多實用的算法，如求二叉樹的高度、各結(jié)點的層次數(shù)、度為 0、 1、 2 的結(jié)點數(shù)。 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。 完全二叉樹的性質(zhì)。 樹、森林和二

36、叉樹間的相互轉(zhuǎn)換。 哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。補充：1.滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前k-1 層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。2.Huffman樹有什么用？最小冗余編碼、信息高效傳輸卑微如螻蟻、堅強似大象共享知識分享快樂第七章 圖內(nèi)容提要： 圖的定義，概念、術(shù)語及基本操作。圖：記為G(V,E)其中： V是 G 的頂點集合，是有窮非空集；E 是 G 的邊集合，是有窮集。術(shù)語：見課件 圖的存儲結(jié)構(gòu)。1.鄰接矩陣 (數(shù)組 )表示法 建立一個頂點表和一個鄰接矩陣 設(shè)圖A = (V, E)

37、有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組A.Edgenn 。注：在有向圖的鄰接矩陣中，第 i 行含義：以結(jié)點 vi 為尾的弧 (即出度邊）；第 i 列含義：以結(jié)點 vi 為頭的弧 (即入度邊）。鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。鄰接矩陣法缺點：n 個頂點需要n*n 個單元存儲邊(弧);空間效率為O(n2)。2.鄰接表 (鏈式 )表示法 對每個頂點 vi 建立一個單鏈表，把與 vi 有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來，表中每個結(jié)點都設(shè)為 3 個域 : 每個單鏈表還應(yīng)當附設(shè)一個頭結(jié)點（設(shè)為2 個域），存 vi 信息； 每個

38、單鏈表的頭結(jié)點另外用順序存儲結(jié)構(gòu)存儲。鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；鄰接表的缺點： 判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。 圖的遍歷。遍歷定義：從已給的連通圖中某一頂點出發(fā)， 沿著一些邊，訪遍圖中所有的頂點， 且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索卑微如螻蟻、堅強似大象共享知識分享快樂深度優(yōu)先搜索（遍歷）步驟： 訪問起始點v; 若 v 的第 1 個鄰接點沒訪問過，深度遍歷此鄰接點； 若當前鄰接點已訪問過，再找v 的第 2 個鄰接點重新遍歷?；舅枷耄悍聵涞南刃虮闅v過程。廣度優(yōu)

39、先搜索（遍歷）步驟： 在訪問了起始點v 之后，依次訪問v 的鄰接點； 然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點； 直到所有頂點都被訪問過為止。 圖的應(yīng)用（最小生成樹，最短路經(jīng)）最小生成樹（ MST ）的性質(zhì)如下：若 U 集是 V 的一個非空子集，若 (u0, v0) 是一條最小權(quán)值的邊，其中 u0 U ，v0 V-U ；則： (u0, v0)必在最小生成樹上。求 MST 最常用的是以下兩種： Kruskal （克魯斯卡爾）算法、 Prim （普里姆）算法 Kruskal 算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。Prime 算法特點 : 將頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)

40、。在帶權(quán)有向圖中A 點（源點）到達B 點（終點）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。兩種常見的最短路徑問題：一、單源最短路徑用Dijkstra （迪杰斯特拉）算法二、所有頂點間的最短路徑用Floyd （弗洛伊德）算法一、單源最短路徑(Dijkstra 算法 )一頂點到其余各頂點（v0j ）目的：設(shè)一有向圖G=（ V, E），已知各邊的權(quán)值，以某指定點v0 為源點，求從v0 到圖的其余各點的最短路徑。限定各邊上的權(quán)值大于或等于0。二、所有頂點之間的最短路徑可以通過調(diào)用n 次 Dijkstra 算法來完成，還有更簡單的一個算法：Floyd 算法（自學） 。卑微如螻蟻、堅強似大

41、象共享知識分享快樂學習重點：圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點。 基本概念中，連通分量，生成樹，鄰接點是重點。 連通圖： 在無向圖中 , 若從頂點v1 到頂點 v2 有路徑 , 則稱頂點v1 與 v2 是連通的。如果圖中任意一對頂點都是連通的, 則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。 生成樹： 是一個極小連通子圖，它含有圖中全部n 個頂點，但只有n-1 條邊。 鄰接點： 若 (u, v) 是 E(G) 中的一條邊，則稱u 與 v 互為鄰接頂點。 圖是復雜的數(shù)據(jù)結(jié)構(gòu)，也有順序和鏈式兩種存儲結(jié)構(gòu)：數(shù)組表示法（重點是鄰接距陣）和鄰接表。這兩種存儲結(jié)構(gòu)對有向圖和無向圖

42、均適用 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握圖的深度、廣度優(yōu)先遍歷。 連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權(quán)值之和是唯一的。應(yīng)熟練掌握 prim 和 kruscal 算法，特別是手工分步模擬生成樹的生成過程。 從單源點到其他頂點，以及各個頂點間的最短路徑問題，掌握熟練手工模擬。補充：1.問：當有向圖中僅1 個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？答：是樹！而且是一棵有向樹！2.討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點

43、編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。3.用途：鄰接矩陣多用于稠密圖的存儲而鄰接表多用于稀疏圖的存儲3.若對連通圖進行遍歷，得到的是生成樹若對非連通圖進行遍歷，得到的是生成森林。卑微如螻蟻、堅強似大象共享知識分享快樂第八章查找內(nèi)容提要： 查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個集合中。 （同一類型的數(shù)據(jù)元素構(gòu)成的集合） 查找表的操作：查找，插入，刪除。 靜態(tài)查找表：順序表，有序表等。針對靜態(tài)查找表的查找算法主要有 :順序查找、折半查找、分塊查找一、順序查找（線性查找）技巧：把待查關(guān)鍵字key 存入表頭或表尾（俗稱“哨兵”），這樣可

44、以加快執(zhí)行速度。int Search_Seq( SSTableST , KeyTypekey )ST.elem0.key =key;for( i=ST.length; ST.elem i .key!=key;- - i);returnm i;1j1ASLj2n j 1n1log 2 (n1)1log 2 nn/ASL （ 1 n）/2，時間效率為O(n) ，這是查找成功的情況:順序查找的特點：優(yōu)點：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點：ASL 太大，時間效率太低。二、折半查找（二分或?qū)Ψ植檎遥┤絷P(guān)鍵字不在表中，怎樣得知并及時停止查找？典型標志是：當查找范圍的上界下界時停止查找。ASL 的含義是 “平均每個數(shù)據(jù)的查找時間”，而前式是n 個數(shù)據(jù)查找時間的總和，所以：三、分塊查找（索引順序查找）思路： 先讓