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

1、名師推薦精心整理學(xué)習(xí)必備第1章緒論內(nèi)容提要： 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。針對非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作。非線性結(jié)構(gòu)（遺輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容：朝結(jié)構(gòu)圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)順存結(jié)構(gòu)整式結(jié)構(gòu)索弓!結(jié)構(gòu)散到端構(gòu)插入運(yùn)算腮除運(yùn)算（數(shù)據(jù)這拜）修改運(yùn)其查找運(yùn)其擇序詼算 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。數(shù)據(jù)一一所有能被計(jì)算機(jī)識別、存儲和處理的符號的集合。數(shù)據(jù)元素一一是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義。數(shù)據(jù)對象一一具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)一一是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：Da

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

3、內(nèi)容提要： 線性表的邏輯結(jié)構(gòu)定義，對線性表定義的操作。線性表的定義：用數(shù)據(jù)元素的有限序列表示丸,叫，%)裁據(jù)元素的直接兩趨.的左接E熱城餐點(diǎn)/D為元素總口印時稱為空猊機(jī)、即1f注.n 線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)：其結(jié)點(diǎn)在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一走相鄰。通過指針來實(shí)現(xiàn)! 線性表的操作在兩種存儲結(jié)構(gòu)中的實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：修改、插入、刪除、查找、排序1)修改一一通過數(shù)組的下標(biāo)便可訪問某個特定元素并修改之。核心語句：Vi=x;順序表修改操作的時間效率是0

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

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

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

7、不斷“順藤摸瓜”字母鏈表的生成。要一個個慢慢鏈入(2)單鏈表的修改(或讀取)思路：要修改第i個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針p,然后才能： pdata=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.單鏈表的插入才結(jié)點(diǎn)的生成方式: S= (node*) ma I loc (m)： 5-data=#;S-next=p-nex tp. . P1S鏈表插入的核心語句：St

8、ep 1: s-next=p-next;Step 2： p-next=s ;6.單鏈表的刪除-L 同刪除動作的核心語句(要借助輔助指針變量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元素，請?jiān)诘趇元素前插入元素x：ai-1的后繼從ai(指針是p)變?yōu)閤(指針是s):s-next=p;p-prior-next=s;ai的前驅(qū)從ai-1(指針是p-prior)變?yōu)閤(指針是s);s-prior=p-prior;p-prior=s;8.雙向鏈表的

9、刪除操作:設(shè)p指向第i個元素，刪除第i個元素后繼方向：ai-1的后繼由ai（指針p）變?yōu)閍i+1（指針p-next）;p-prior-next=p-next;前驅(qū)方向：ai+1的前驅(qū)由ai（指針p）變?yōu)閍i-1（指針p-prior）;p-next-prior=p-prior; 數(shù)組的邏輯結(jié)構(gòu)定義及存儲數(shù)組：由一組名字相同、下標(biāo)不同的變量構(gòu)成N維數(shù)組的特點(diǎn)：n個下標(biāo)，每個元素受到n個關(guān)系約束一個n維數(shù)組可以看成是由若干個n1維數(shù)組組成的線性表。存儲：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存入存儲器中。在二維數(shù)組中，我們既可以規(guī)定按行存儲，也可以規(guī)定按列存儲。設(shè)一般的二維數(shù)組

10、是Ac1.d1,c2.d2,_則行優(yōu)先存儲時的地址公式為：即中A二LOC風(fēng)尸LOC（C2）+（i-c1）*（di-cI+l）+j-c2）*L11m口幽;二維數(shù)組列優(yōu)先存儲的通式為：LOCj）=LOC（叼，J十比工丁知力+l）+icDL 稀疏矩陣（含特殊矩陣）的存儲及運(yùn)算。稀疏矩陣：矩陣中非零元素白個數(shù)較少（一般小于5%）學(xué)習(xí)重點(diǎn)： 線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。在順序存儲結(jié)構(gòu)中，元素存儲的先后位置反映出這種線性關(guān)系,而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，是靠指針來反映這種關(guān)系的。 順序存儲結(jié)構(gòu)用一維數(shù)組表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機(jī)存取的存儲結(jié)構(gòu)。 鏈表操作中應(yīng)注意不要使鏈意

11、外“斷開”。因此，若在某結(jié)點(diǎn)前插入一個元素，或刪除某元素，必須知道該元素的前驅(qū)結(jié)點(diǎn)的指針。 掌握通過畫出結(jié)點(diǎn)圖來進(jìn)行鏈表（單鏈表、循環(huán)鏈表等）的生成、插入、刪除、遍歷等操作。 數(shù)組（主要是二維）在以行序/列序?yàn)橹鞯拇鎯χ械牡刂酚?jì)算方法。 稀疏矩陣的三元組表存儲結(jié)構(gòu)。 稀疏矩陣的十字鏈表存儲方法。補(bǔ)充重點(diǎn):1 .每個存儲結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域(鏈域)其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放 可以對空表、非空表的情況以及對亙2 .在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由3 .在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)，表長度等附

12、加信息,其作用是為了對鏈表進(jìn)行操作時，元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理,編程更方便。4 .如何表不空表？(1)無頭結(jié)點(diǎn)時，當(dāng)頭指針的值為空時表示空表；(2)有頭結(jié)點(diǎn)時，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r表示空表。5 .鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？因每個結(jié)點(diǎn)至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。6 .sizeof(x)計(jì)算變量x的長度(字節(jié)數(shù))；malloc(m)開辟m字節(jié)長度的地址空間，并返回這段空間的首地址；free(p)釋放指針p所指變量的存儲空間，即徹底刪除一個變量。7.鏈表的運(yùn)算效率分析：(1)查找因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的

13、時間復(fù)雜度為O(n)。(2)插入和刪除因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為0(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時間復(fù)雜度將是O(n)。例：在n個結(jié)點(diǎn)的單鏈表中要刪除已知結(jié)點(diǎn)*P,需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時間復(fù)雜度為O(n)8.順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別和優(yōu)缺點(diǎn)？順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲的優(yōu)點(diǎn)是存儲密度大，存儲空間利用率高；缺點(diǎn)是插入或刪除元素時不方便。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。鏈?zhǔn)酱鎯Φ膬?yōu)點(diǎn)是插入或

14、刪除元素時很方便，使用靈活。缺點(diǎn)是存儲密度小，存儲空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作; 鏈表宜于做插入、刪除這樣的動態(tài)操作。 若線性表的長度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9 .判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對嗎？答：對的。因?yàn)橐灰粩?shù)組中各元素具有統(tǒng)一的類型;數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。數(shù)組的基本操作比較簡單,除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。10 .三元素組表中的每個結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個非零元素，它包

15、含有三個數(shù)據(jù)項(xiàng)，分別表示該元素的行下標(biāo)、列下標(biāo)和元素值。11 .寫出右圖所示稀疏矩陣的壓縮存儲形式。解：介紹3種存儲形式。法1:用線性表表示：(1,2,12),(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),法2:用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算法3:用三元組矩陣表示:12 93 0 :14241815-7(6,4,-7)方法：每個非。元素占用5個域稀疏矩陣壓縮存儲的缺點(diǎn)：將失去隨機(jī)存取功能代碼:1.用數(shù)組V來存放26個英文字母組成的線性表(a,b,c,，z),寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。charV30;voi

16、dbuild()字母線性表的生成，即建表操作inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;voiddisplay()/字母線性表的顯示，即讀表操作inti;for(i=0;iM)上溢elsestop+=e;順序棧出棧函數(shù)POP()statusPop()if(top=L)下溢elsee=s-top;return(e);隊(duì)列的定義及操作，隊(duì)列的刪除在一端（隊(duì)尾），而插入則在隊(duì)列的另一端（隊(duì)頭）。因此在兩種存儲結(jié)構(gòu)中，都需要隊(duì)頭和隊(duì)尾兩個指針。隊(duì)列：只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。鏈隊(duì)列結(jié)點(diǎn)類型定義：typedefStructQNodeQEl

17、emTypedata;元素StructQNode空鏈隊(duì)的特征：front=rear 鏈隊(duì)會滿嗎？ 一般不會，因?yàn)閯h除時有 free動作。除非內(nèi)存不足!入隊(duì)（尾部插入）：rear-next=S; rear=S;出隊(duì)（頭部刪除）：front-next=p-next;2.順序隊(duì)順序隊(duì)類型定義：#define QUEUE-MAXSIZE100 最大隊(duì)列長度typedef struct QElemType *base; 隊(duì)列的基址intfront; 隊(duì)首指針intrear;隊(duì)尾指針SqQueue建隊(duì)核心語句：q . base=(QElemType *)malloc(sizeof (QElemType )

18、 QUEUE_MAXSIZE;分配空間隊(duì)列會潴嗎？極易裝瞞1因?yàn)楠?dú)組逋 常有長度限制，而其前 磬空間無法釋放“E樣實(shí)現(xiàn)A隊(duì)和出以 操作？核心語句卸下： 入(尾部斷入L rear*+ .Qrrar|-c；出隊(duì)(頭部刪除)：rtH , f-QftQnil；next;指向下一結(jié)點(diǎn)的指針Qnode,*QueuePtr;鏈隊(duì)列類型定義：typedefstructQueuePtrfront;/隊(duì)首指針QueuePtrrear;隊(duì)尾指針LinkQueue;rca r鏈隊(duì)示意圖：空隊(duì)列的特征?fruiit典定：ftQil rearreur3QQ-循環(huán)隊(duì)列：隊(duì)空條件：front=rear(初始化時：front=

19、rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長度(即數(shù)據(jù)元素個數(shù))：L=(N+rearfront)%N1)初始化一個空隊(duì)列StatusInitQueue(SqQueue&q)11初始化空循環(huán)隊(duì)列qq.base=(QElemType*)malloc(sizeof(QElemType)*QUEUE_MAXSIZE);分配空間if(!q.base)exit(OVERFLOW);/內(nèi)存分配失敗，退出程序q.front=q.rear=0;/置空隊(duì)歹UreturnOK;/InitQueue;2)入隊(duì)操作StatusEnQueue(SqQueue&q,QElemTypee)

20、向循環(huán)隊(duì)列q的隊(duì)尾加入一個元素eif(q.rear+1)%QUEUE_MAXSIZE=q.front)returnERROR;隊(duì)滿則上溢，無法再入隊(duì)q.rear=(q.rear+1)%QUEUE_MAXSIZE;q.baseq.rear=e;新元素e入隊(duì)returnOK;/EnQueue;3)出隊(duì)操作StatusDeQueue(SqQueue&q,QElemType&e)若隊(duì)列不空，刪除循環(huán)隊(duì)列q的隊(duì)頭元素，由e返回其值，并返回OKif(q.front=q.rear)returnERROR;/隊(duì)列空q.front=(q.front+1)%QUEUE_MAXSIZE;e=q.baseq.fron

21、t;returnOK;/DeQueue1等于隊(duì)頭鏈隊(duì)列空的條件是首尾指針相等，而循環(huán)隊(duì)列滿的條件的判定，則有隊(duì)尾加和設(shè)標(biāo)記兩種方法。補(bǔ)充重點(diǎn)：1 .為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算的有力工具；用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；簡化了程序設(shè)計(jì)的問題。2 .為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？離散事件的模擬（模擬事件發(fā)生的先后順序，例如CPU芯片中的指令譯碼隊(duì)列）；操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU執(zhí)行多個作業(yè)）；簡化程序設(shè)計(jì)。3 .什么叫“假溢出”？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”-解決假溢

22、出的途徑采用循環(huán)隊(duì)列。4 .在一個循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的前一個位置。那么，從循環(huán)隊(duì)列中刪除一個元素時，其操作是先移動隊(duì)首位置,后取出元素。5 .線性表、棧、隊(duì)的異同點(diǎn)：相同點(diǎn)：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運(yùn)算加以限制）。不同點(diǎn)：運(yùn)算規(guī)則不同：線性表為隨機(jī)存??；而棧是只允許在一端進(jìn)行插入和刪除運(yùn)算，因而是后進(jìn)先出表LIFO;隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計(jì)等；隊(duì)列用于離散事件模擬、OS作業(yè)調(diào)度和

23、簡化設(shè)計(jì)等。第四章串內(nèi)容提要：串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。串比較：intstrcmp(char*s1,char*s2);求串長：intstrlen(char*s);串連接：charstrcat(char*to,char*from)子串T定位：charstrchr(char*s,char*c);串的存儲結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點(diǎn)大小”的問題。模式匹配算法。串有三種機(jī)內(nèi)表示方法：順序用一組地址連跳的存儲單元存儲串值的字存儲將序列，屬淋態(tài)存儲方式.螂分配存儲表示一用一組:址連續(xù)的存

24、儲單元存儲串值的字符序列,但存儲空間是在程序執(zhí)行過程中動點(diǎn)站能分配而得.魯建串的塊鏈存儲表示仔商桂式方式存儲模式匹配算法：算法目的：確定主串中所含子串第一次出現(xiàn)的位置(定位)定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos)BF算法的實(shí)現(xiàn)一即編寫Index(S,T,pos)函數(shù)BF算法設(shè)計(jì)思想：將主串S的第pos個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的下一字符(pos+1)起，重新與T第一個字符比較。直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0。IntInd

25、ex_BP(SStringS,SStringT,intpos)返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)值為0.其中，T非空，1wposwStrLength(S)i=pos;j=1;while(i=S0&jT0)returni-T0;/T子串指針j正常到尾，說明匹配成功，elsereturn0;/否則屬于iS0情況，i先到尾就不正常/Index_BP補(bǔ)充重點(diǎn)：1 .空串和空白串有無區(qū)別？答：有區(qū)別。空串（NullString）是指長度為零的串；而空白串（BlankString）,是指包含一個或多個空白字符（空格鍵）的字符串2 .“空串是任意串的子串；任意串S都是S本身的子串

26、，除S本身外，S的其他子串稱為S的真子串?！倍ㄩL順序存赭結(jié)構(gòu)串T有儲船構(gòu)-堆存儲結(jié)構(gòu)塊鏈存儲結(jié)構(gòu)若干函數(shù)的實(shí)現(xiàn)模式匹配算法模式匹配即子串定位運(yùn)算即如何實(shí)現(xiàn)InMMS臥$）函數(shù)第六章樹和二叉樹內(nèi)容提要： 樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。樹：由一個或多個（n0）結(jié)點(diǎn)組成的有限集合T,有且僅有一個結(jié)點(diǎn)稱為根（root）,當(dāng)n1時，其余的結(jié)點(diǎn)分為m（m0）個互不相交的有限集合T1,T2,，Tm。每個集合本身又是棵樹，被稱作這個根的子樹。二叉樹：是n（n0）個結(jié)點(diǎn)的有限集合，由一個根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。術(shù)語：P88 二叉樹的性質(zhì)，存

27、儲結(jié)構(gòu)。性質(zhì)1:在二叉機(jī)勺第i層上至多有2i-1個結(jié)點(diǎn)（i0）。性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)（k0）。性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個，則葉子數(shù)（n0）必定為n2+1性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度必為性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點(diǎn)，其左孩子編號必為2i,其右孩子編號為2i+1;其雙親的編號必為i/2（i=1時為根，除外）。二叉樹的存儲結(jié)構(gòu)：一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。若是完全/滿二叉樹則可以做到唯一復(fù)原。不是完全二叉樹：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處

28、統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。缺點(diǎn)：浪費(fèi)空間；插入、刪除不便二、鏈?zhǔn)酱鎯Y(jié)構(gòu)用二叉鏈表即可方便表示。一般從根結(jié)點(diǎn)開始存儲。rlgbt(hldd優(yōu)點(diǎn)：不浪費(fèi)空間；插入、刪除方便 二叉樹的遍歷。指按照某種次序訪問二叉樹的所有結(jié)點(diǎn)，并且每個結(jié)點(diǎn)僅訪問一次，得到一個線性序列。遍歷規(guī)則二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、L、R若限定先左后右，則有三種實(shí)現(xiàn)方案：DLRLDRLRD先序遍歷中序遍歷后序遍歷樹的存儲結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換?；仡櫲?鉗如何轉(zhuǎn)為二叉樹? 方法,加線抹線旋轉(zhuǎn)回顧2:二叉樹怎樣還原為樹？要點(diǎn)：逆操作，把所有右孩子變?yōu)樾值埽∮懻? :森林如何轉(zhuǎn)為二叉樹？法一：

29、各森林先各自轉(zhuǎn)為二叉樹；依次連到前一個二叉樹的右子樹上。法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹討論2:二叉樹如何還原為森林？要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值軜浜蜕值拇鎯Ψ绞剑簶溆腥N常用存儲方式：雙親表示法孩子表示法孩子一兄弟表示法問：樹一二叉樹的“連線一抹線一旋轉(zhuǎn)”如何由計(jì)算機(jī)自動實(shí)現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。存儲的過程就是樹轉(zhuǎn)換為二叉樹的過程！樹、森林的遍歷:螭的遍歷深度優(yōu)先遍田（小根、后根舞烈霆夕囚廣度優(yōu)先遍歷I層次）先根遍歷：訪問根結(jié)點(diǎn)；依次先根遍歷根結(jié)點(diǎn)的每棵子樹。 后根遍歷：依次后根遍歷根結(jié)點(diǎn)的每棵子樹；訪問根結(jié)點(diǎn)。 討論：樹若采用“先轉(zhuǎn)換，后遍歷”方

30、式，結(jié)果是否一樣？1 .樹的先根遍歷與二叉樹的先序遍歷相同；2 .樹的后根遍歷相當(dāng)于二叉樹的中序遍歷；3 .樹沒有中序遍歷，因?yàn)樽訕錈o左右之分。森林的遍歷-深度優(yōu)先遍歷先序、中序）廣度優(yōu)先遍歷（層次）先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點(diǎn)；先根遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問第一棵樹的根結(jié)點(diǎn)；中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。Huffman樹：最優(yōu)二叉樹(帶權(quán)路徑長度最短的樹)Huffman編碼：不等長編碼。n樹的帶權(quán)路

31、徑長度：Ik(樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和)構(gòu)造Huffman樹的基本思想：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長路徑。構(gòu)造Huffman樹的步驟(即Huffman算法)：由給定的n個權(quán)值w1,w2,，wn構(gòu)成n棵二叉樹的集合F=T1,T2,，Tn(即森林)，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空。(2)在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹做為左右子樹構(gòu)造一棵新的二叉樹，且讓新二叉樹根結(jié)點(diǎn)的權(quán)值等于其左右子樹的根結(jié)點(diǎn)權(quán)值之和。(3)在F中刪去這兩棵樹，同時將新得到的二叉樹加入F中。(4)重復(fù)(2)和(3),直到F只含一棵樹為止。這棵樹便是Huffman樹。具體操作步驟

32、：stepl：對權(quán)值進(jìn)行合并、刪除與替換在權(quán)值集合仃,5.2,4中，忠是合并當(dāng)前值最小的兩個權(quán)a.初始仁合并網(wǎng)A合并（7H1Uf； （instep2：按左右1對Htlffman樹的所有分支編號將Huffman樹鳥而加社門編碼掛鉤Huffman編碼結(jié)果：d=,i= tWFL=lbitX7+2bitX5+3bitQ+4）=35 （小于等長碼的ffFL=36）a= I I （：, n=學(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ù)。由二叉樹遍歷的前序和中序序

33、列或后序和中序序列可以唯一構(gòu)造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。 完全二叉樹的性質(zhì)。 樹、森林和二叉樹間的相互轉(zhuǎn)換。 哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。補(bǔ)充：1 .滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前k-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點(diǎn)。滿二叉樹是完全二叉樹的一個特例。2 .Huffman樹有什么用？最小冗余編碼、信息高效傳輸?shù)谄哒聢D內(nèi)容提要：圖的定義，概念、術(shù)語及基本操作。圖：記為G=（V,E）其中：V是G的頂點(diǎn)集合，是有窮非空集;E是G的邊集合，是有窮集。術(shù)語：見課件圖的存儲結(jié)構(gòu)。1 .鄰接矩陣（數(shù)組）表

34、示法建立一個頂點(diǎn)表和一個鄰接矩陣設(shè)圖A=（V,E）有n個頂點(diǎn)，則圖的鄰接矩陣是一個二維數(shù)組A.Edgenn。注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點(diǎn)vi為尾的?。闯龆冗叄坏趇列含義：以結(jié)點(diǎn)vi為頭的?。慈攵冗叄?。鄰接矩陣法優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。┱翼旤c(diǎn)的鄰接點(diǎn)等等。鄰接矩陣法缺點(diǎn)：n個頂點(diǎn)需要n*n個單元存儲邊（?。?空間效率為O（n2）。2 .鄰接表（鏈?zhǔn)剑┍硎痉▽γ總€頂點(diǎn)vi建立一個單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來,表中每個結(jié)點(diǎn)都設(shè)為3個域：美結(jié)點(diǎn)妻結(jié)點(diǎn)每個單鏈表還應(yīng)當(dāng)附設(shè)一個頭結(jié)點(diǎn)（設(shè)為2個域），存vi信息；每

35、個單鏈表的頭結(jié)點(diǎn)另外用順序存儲結(jié)構(gòu)存儲。鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；鄰接表的缺點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。圖的遍歷。沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā),每個頂點(diǎn)僅被訪問一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索深度優(yōu)先搜索（遍歷）步驟：訪問起始點(diǎn)v；若v的第1個鄰接點(diǎn)沒訪問過，深度遍歷此鄰接點(diǎn)；若當(dāng)前鄰接點(diǎn)已訪問過，再找v的第2個鄰接點(diǎn)重新遍歷。基本思想：一一仿樹的先序遍歷過程。I應(yīng)退回到梯;因?yàn)槠谝延袠?biāo)記1vlT vlTvdT例 T v5T_

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

37、ml算法示例：對邊操作，桿井邊 普利姆（Prim）算法示例：歸并頂點(diǎn)在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。兩種常見的最短路徑問題：一、單源最短路徑一用Dijkstra（迪杰斯特拉）算法二、所有頂點(diǎn)間的最短路徑一用Floyd（弗洛伊德）算法一、單源最短路徑（Dijkstra算法）一頂點(diǎn)到其余各頂點(diǎn)（v0-j）目的：設(shè)一有向圖G=（V,E）,已知各邊的權(quán)值，以某指定點(diǎn)v0為源點(diǎn)，求從v0到圖的其余各點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。二、所有頂點(diǎn)之間的最短路徑可以通過調(diào)用n次Dijkstra算法來完成，還有更簡單的一個算法：Fl

38、oyd算法（自學(xué)）。學(xué)習(xí)重點(diǎn)：圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點(diǎn)?；靖拍钪校B通分量，生成樹，鄰接點(diǎn)是重點(diǎn)。 連通圖：在無向圖中，若從頂點(diǎn)v1到頂點(diǎn)v2有路徑，則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的，則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。 生成樹：是一個極小連通子圖，它含有圖中全部n個頂點(diǎn)，但只有n-1條邊。 鄰接點(diǎn)：若（u,v）是E（G）中的一條邊，則稱u與v互為鄰接頂點(diǎn)。 圖是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，也有順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)：數(shù)組表示法（重點(diǎn)是鄰接距陣）和鄰接表。這兩種存儲結(jié)構(gòu)對有向圖和無向圖均適用 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握

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

40、）。3 .用途：鄰接矩陣多用于稠密圖的存儲而鄰接表多用于稀疏圖的存儲3.若對連通圖進(jìn)行遍歷，得到的是生成樹若對非連通圖進(jìn)行遍歷，得到的是生成森林。第八章查找內(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存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。intSearch_Seq（SSTableST,KeyTypekey）ST.ele

41、m0.key=key;for（i=ST.length;ST.elemi.key!=key;-i）;returni;/Search_SeqASL=（1+n）/2,時間效率為O（n）,這是查找成功的情況：順序查找的特點(diǎn)：優(yōu)點(diǎn)：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：ASL太大，時間效率太低。二、折半查找（二分或?qū)Ψ植檎遥┤絷P(guān)鍵字不在表中，怎樣得知并及時停止查找？典型標(biāo)志是：當(dāng)查找范圍的上界w下界時停止查找。ASL的畬m是“甘均n傘數(shù)據(jù)的查找時間”，而前式是n個數(shù)據(jù)查找時間的總和，所以:ASL=j2jlog2（n1）-1：log2nnj4n三、分塊查找（索引順序查找）思路：先讓數(shù)據(jù)分塊有序，即

42、分成若干子表，要求每個子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。特點(diǎn)：塊間有序，塊內(nèi)無序。查找：塊間折半，塊內(nèi)線性查找步驟分兩步進(jìn)行：對索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚淮_定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無序表）查找效率ASL分析：時索引震查找的AS匚1塊內(nèi)交找眄A&L應(yīng)由三此式口0%強(qiáng)紀(jì).）6內(nèi)播的訊錄小-nA印塊的款目二|但祈半法要揪 一I先全排序1仍 需時間.例如當(dāng)n-兀用3時,分班法的鳳，=3.5而折半法的碗光1姐所31原序法的硯氣1+

43、11）0-5動態(tài)查找表：二叉排序樹，平衡二叉樹。特點(diǎn)：表結(jié)構(gòu)在查找過程中動態(tài)生成。要求：對于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key的記錄。二叉排序樹的定義-或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：(1)左子樹的所有結(jié)點(diǎn)均小于根的值；(2)右子樹的所有結(jié)點(diǎn)均大于根的值；(3)它的左右子樹也分別為二叉排序樹。二叉排序樹的插入與刪除思路：查找不成功，生成一個新結(jié)點(diǎn)s,插入到二叉排序樹中；查找成功則返回。SearchBST(K,&t)/K為待查關(guān)鍵字，t為根結(jié)點(diǎn)指針p寸/p為查找過程中進(jìn)行掃描的指針while(p!=NULL)caseK=p-d

44、ata:查找成功，returnKdata:q=p;p=p-L_child繼續(xù)向左搜索Kp-data:q=p;p=p-R_child/繼續(xù)向右搜索查找不成功則插入到二叉排序樹中s=(BiTree)malloc(sizeof(BiTNode);s-data=K;s-L_child=NULL;s-R_child=NULL;查找不成功，生成一個新結(jié)點(diǎn)s,插入到二叉排序樹葉子處caset=NULL:t=s;若t為空，則插入的結(jié)點(diǎn)s作為根結(jié)點(diǎn)Kdata:q-L_child=s;若K比葉子小，掛左邊Kq-data:q-R_child=s;若K比葉子大，掛右邊returnOK二叉排序樹的刪除操作如何實(shí)現(xiàn)？如何

45、刪除一個結(jié)點(diǎn)？假設(shè)：p有兩棵子樹時，如何進(jìn)行刪除操作？設(shè)刪除前的中序遍歷序列為：.PL s p PR f顯然p的直接前驅(qū)是s , s是*p左子樹最右下方的結(jié)點(diǎn)希望刪除p后，其它元素的相對位置不變。有兩種解決方法：法1:令*p的左子樹為 *f的左子樹，*p的右子樹接為*s的右子樹；即fL=PLSR=PR ;法2：直接令*s代替*p / *s為*p左子樹最右下方的結(jié)點(diǎn)p表示被刪結(jié)點(diǎn)的指針；PL和PR分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點(diǎn)指針；并假定*p是*f的左孩子；則可能有三種情況：劇除此結(jié)點(diǎn)酎，直接修改*;指針域即可：T*0只有T子的(或左在右):駟46q為*f的左核子即可：”I

46、印有兩牌子幗二情況提優(yōu)-+二叉排序樹的ASL2(l+i)ln111平衡二叉樹的定義：又稱AVL樹，即它或者是一顆空樹，或者是它的左子樹和右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對值不超過1。平衡因子：一一該結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度。平衡二叉樹的特點(diǎn)：任一結(jié)點(diǎn)的平衡因子只能?。?1、0或1。如果在一棵AVL樹中插入一個新結(jié)點(diǎn)，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：1)LL平衡旋轉(zhuǎn):2) RR平衡旋轉(zhuǎn)*若賽A鮑 電子村的 左手忖上國 人息,蟆平布內(nèi)哥m1構(gòu)加至2, 短，工遺擰升我將。聆再4哂*尋”的

47、忐 手鑄上必 人 第疝.EM平衡國手以加X 2, 香鼻一菱葉鐘崔格a3) LR平衡旋轉(zhuǎn):4) RL平衡旋轉(zhuǎn):若布A的行子材的 左子村上JS入站 A,健A的平衡國子隊(duì)增加工工，學(xué)習(xí)重點(diǎn)： 查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。因元素間關(guān)系非常松散，其操作需借助其它數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。本章列舉了三種方法(靜態(tài)查找表，動態(tài)查找表)實(shí)現(xiàn)查找表的運(yùn)算。 順序表因設(shè)置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長度不超過樹的深度。 查找的ASL 二叉排序樹的形態(tài)取決于元素的輸入順序。按中序遍歷可得到結(jié)點(diǎn)的有序序列，應(yīng)熟練掌握其建立、查找，插入和刪除算法。 平衡二叉樹的概念，應(yīng)熟練掌握手工繪制平衡二叉樹。補(bǔ)充：1 .查找

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

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

50、3)二路插入排序一小改選4)次植入排序J5)希爾排序一大我講每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。1)直接插入排序在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。例1；關(guān)鍵字序列T-6,3,31,9,27,5,11)T而寫出直接插入排序的中間過程序列.【13】，6,3,31,*215,116,13,3,31,孔女，113,6,13，31,*216,1113,樂13.31,9:7,5,113,6,*13,311,27,5,11口,0*13,鞏311*5,11口，工*1右打*31，11口，工乞9,11,13,27,31時間效率：因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為(0+1+n-1)一O(n2)。其他情況下也要考慮移動元素的次數(shù)。故時間復(fù)雜度為O(n2)空間效率：僅占用1個緩沖單元一一O(1)算法的穩(wěn)定性：因?yàn)?5*排序后仍然在25的后面一一穩(wěn)定直接插入排序算法的實(shí)現(xiàn)：voidInsertSort(SqList&L)/對順序表L作直接插入排序for(i=2;i=L.length;i+)假定第一個記錄有序L.r0=L.ri;j=i-1;先將待插入的元素放入“哨兵”位置while(L0.keyLj.key)L.rj+1=L.rj;j-;只