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)容：線性結(jié)構(gòu)（靖性友.行劇范.畫泡題序結(jié)構(gòu)建式蓊構(gòu)，素案結(jié)構(gòu)散到結(jié)構(gòu)插入運(yùn)交刪除運(yùn)算數(shù)藕達(dá)簟1修改詼算杳找運(yùn)算排住運(yùn)算基本概念：數(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ù)

2、類型一一是一個(gè)值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型一一由用戶定義的一個(gè)數(shù)學(xué)模型與定義在該模型上的一組操作，它由基本的數(shù)據(jù)類型構(gòu)成。算法的定義及五個(gè)特征。算法一一是對(duì)特定問(wè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ù)雜度。非線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)國(guó)結(jié)構(gòu)教寨結(jié)梅是一系列輸入轉(zhuǎn)換為輸?shù)诙戮€性表內(nèi)容提要：線性表的

3、邏輯結(jié)構(gòu)定義，對(duì)線性表定義的操作。線性表的定義：用數(shù)據(jù)元素的有限序列表示線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)定義：把邏輯上相鄰的數(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í)間效率是0(1)2)插入一一在線性表的第i個(gè)位置前插入一個(gè)元素實(shí)現(xiàn)步驟：將第n至第i位的元素向后移動(dòng)一個(gè)位置；將要插入的元素

4、寫到第i個(gè)位置；表長(zhǎng)加1。注意：事先應(yīng)判斷：插入位置i是否合法？表是否已滿？應(yīng)當(dāng)符合條件：1wiWn+1或i=1,n+1核心語(yǔ)句：for(j=n;j=i;j-)aj+1=aj;ai=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-;序號(hào).或小青n=0時(shí)稱為0.任祝申我也順序表刪除一元素的時(shí)間效率為：T(n)=(n-1)/2-O(

5、n)順序表插入、刪除算法的平均空間復(fù)雜度為0(1)單鏈表:26個(gè)英文字母組成的線性表(a,b,c,，z),請(qǐng)寫出C語(yǔ)言程序。一般需要3個(gè)指針變量/數(shù)據(jù)元素的個(gè)數(shù)/*結(jié)構(gòu)類型定義好之后，每個(gè)node類型的長(zhǎng)度就固定了,m求一次即可*/字母鏈表的生成。要一個(gè)個(gè)慢慢鏈入(1)用單鏈表結(jié)構(gòu)來(lái)存放#include#includetypedefstructnodechardata;structnode*next;node;node*p,*q,*head;intn;intm=sizeof(node);voidbuild()inti;head=(node*)malloc(m);p=head;for(i=1;i

6、data=i+，a，-1;p-next=(node*)malloc(m);p=p-next;p-data=i+，a，-1;p-next=NULL;voiddisplay()p=head;while(p)/m=sizeof(node)前面已求出因尾結(jié)點(diǎn)要特殊處理，故iw26/第一個(gè)結(jié)點(diǎn)值為字符a/為后繼結(jié)點(diǎn)“挖坑”！讓指針變量P指向后一個(gè)結(jié)點(diǎn)/最后一個(gè)元素要單獨(dú)處理單鏈表尾結(jié)點(diǎn)的指針域要置空！字母鏈表的輸出當(dāng)指針不空時(shí)循環(huán)(僅限于無(wú)頭結(jié)點(diǎn)的情況)printf(%c,p-data);p=p-next;讓指針不斷“順藤摸瓜”設(shè)p已指向第i元素，請(qǐng)?jiān)诘趇元素前插入元素x：ai-1的后繼從ai（指針是p

7、）變?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;（2）單鏈表的修改（或讀?。┧悸罚阂薷牡趇個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針P,然后才能：pdata=new_value讀取第i個(gè)數(shù)據(jù)元素的核心語(yǔ)句是：Linklist*find(Linklist*head,inti)(intj=1;Linklist*p;P=head-next;While(p!=NULL)&(jnext;j+;returnp;鏈表插入的核心語(yǔ)句：Step1:s-next=

8、p-next;Step2：p-next=s;常結(jié)點(diǎn)的生成方式：常結(jié)點(diǎn)的生成方式：3二(node*)rnaIIQG(m)：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.雙向鏈表的插入操作:8.雙向鏈表的刪除操作：v、jI：-1M：皆卑|1Mj_：設(shè)p指向第i個(gè)元素，刪除第i個(gè)元素后繼方向：ai-1的后繼由ai（指針p）變?yōu)閍i+1（指針p-next）;p-prior-next=p-next;前驅(qū)方向：ai+1的前驅(qū)由ai（指針p）變?yōu)?/p>

9、ai-1（指針p-prior）;p-next-prior=p-prior;數(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í)的地址公式為：即1.UMi內(nèi)LOCj）-LDC（%好好二維數(shù)組列優(yōu)先存儲(chǔ)的通式為：10c（劭尸LOC（%，/山七十稀疏矩陣（含特殊矩陣）的存儲(chǔ)及運(yùn)算。稀疏矩陣：

10、矩陣中非零元素白個(gè)數(shù)較少（一般小于5%）學(xué)習(xí)重點(diǎn)：線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。在順序存儲(chǔ)結(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)注意不要使鏈意外“斷開(kāi)”。因此，若在某結(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ǔ)方法。

11、補(bǔ)充重點(diǎn):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)開(kāi)辟m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；free(p)釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。7.鏈表的運(yùn)算效率分析：(1)查找因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為O(n)。(2)插入和刪除因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為。(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗

12、時(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ù)元素，其物理存放地址也相鄰。順序存儲(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)度變化不大，且其主要操作是查找，

13、則采用順序表；若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9.判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單”，對(duì)嗎？答：對(duì)的。因?yàn)橐灰粩?shù)組中各元素具有統(tǒng)一的類型;數(shù)組元素的下標(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)和元素值。1.每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域(鏈域)2.在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由3.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好

14、處？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，表長(zhǎng)度等附加信息,其作用是為了對(duì)鏈表進(jìn)行操作時(shí)， 元結(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í)表示空表。其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放可以對(duì)空表、非空表的情況以及對(duì)首(1,2,12),(1,3,9),(3,1,-3),(4,3,24),(5,2,18),(6,1,15),法2:用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算方法：每個(gè)非0元素占用5個(gè)域(3,5,14),(6,4,-7)-31815稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)

15、存取功能代碼:1用數(shù)組V來(lái)存放26個(gè)英文字母組成的線性表(和顯示該表的C語(yǔ)言程序。a,b,c,，z),寫出在順序結(jié)構(gòu)上生成charV30;voidbuild()字母線性表的生成，即建表操作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ì)頭）。因此在兩種存儲(chǔ)結(jié)構(gòu)中，都需要隊(duì)頭和

16、隊(duì)尾兩個(gè)指針。隊(duì)列：只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。鏈隊(duì)列結(jié)點(diǎn)類型定義：typedefStructQNodeQElemTypedata;元素StructQNode*next;/指向下一結(jié)點(diǎn)的指針Qnode,*QueuePtr;鏈隊(duì)列類型定義：typedefstructQueuePtrfront;/隊(duì)首指針QueuePtrrear;/隊(duì)尾指針LinkQueue;鏈隊(duì)示意圖：rur旺no.0 0LZD-KDS3-w空鏈隊(duì)的特征：front=rear鏈隊(duì)會(huì)滿嗎？一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足!入隊(duì)（尾部插入）：rear-next=S;rear=S;出隊(duì)

17、（頭部刪除）：front-next=p-next;2.順序隊(duì)順序隊(duì)類型定義：q.base=(QElemType*)malloc(sizeof(QElemType出火失即刪除hfrtnL+4e#defineQUEUE-MAXSIZE100最大隊(duì)列長(zhǎng)度typedefstructQElemTypeint*base;/隊(duì)列的基址front;intSqQueue建隊(duì)核心語(yǔ)句：rear;隊(duì)首指針隊(duì)尾指針MSMTZE;分配空間空隊(duì)列的轉(zhuǎn)征？的定1frontrrur便雙列春潴嗎?強(qiáng)疆裝摘 T 因?yàn)楠?dú)姐JS靠有長(zhǎng)度限制,而其前端空間北法擇曲*怎祥宏現(xiàn)入隊(duì)利陽(yáng)隊(duì)檸句匐下循環(huán)隊(duì)列：隊(duì)空條件：front=rear(初

18、始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度(即數(shù)據(jù)元素個(gè)數(shù))：L=(N+rearfront)%N1)初始化一個(gè)空隊(duì)列StatusInitQueue(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ì)歹UreturnOK;/InitQueue;2)入隊(duì)操作StatusEnQueue(SqQueue

19、&q,QElemTypee)向循環(huán)隊(duì)列q的隊(duì)尾加入一個(gè)元素eif(q.rear+1)%QUEUE_MAXSIZE=q.front)returnERROR;隊(duì)滿則上溢，無(wú)法再入隊(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)%QU

20、EUE_MAXSIZE;e=q.baseq.front;returnOK;/DeQueue鏈隊(duì)列空的條件是首尾指針相等，而循環(huán)隊(duì)列滿的條件的判定，則有隊(duì)尾加和設(shè)標(biāo)記兩種方法。1等于隊(duì)頭補(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è)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；簡(jiǎn)化程序設(shè)計(jì)。3.什么叫“假溢出”？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其

21、實(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)算，因而是后進(jìn)先出表LIFO;隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡(jiǎn)化設(shè)

22、計(jì)等；隊(duì)列用于離散事件模擬、OS作業(yè)調(diào)度和簡(jiǎn)化設(shè)計(jì)等。第四章串內(nèi)容提要：串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。串即字符串，是由零個(gè)或多個(gè)字符組成的有限序列，是數(shù)據(jù)元素為單個(gè)字符的特殊線性表。串比較：intstrcmp(char*s1,char*s2);求串長(zhǎng)：intstrlen(char*s);串連接：charstrcat(char*to,char*from)子串T定位：charstrchr(char*s,char*c);串的存儲(chǔ)結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點(diǎn)大小”的問(wèn)題。模式匹配算法。串有三種機(jī)內(nèi)表示方法：定長(zhǎng)防i序存儲(chǔ)表示一用一切地址連魅的存的孽元存陡等值的字將序

23、列.屬翻盍存儲(chǔ)方式.堆分配存精表示用一殂地址浮建的存晶拿元存貸用值的字符序列,但存儲(chǔ)空間是在程序執(zhí)行過(guò)用中動(dòng)需分配而部.一的塊鏈存儲(chǔ)表示鏈?zhǔn)椒绞酱鎯?chǔ)模式匹配算法：算法目的：確定主串中所含子串第一次出現(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匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功

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

25、儲(chǔ)存儲(chǔ)2.“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為的真子串?！辩牭诰笜?gòu)鼻=通工加“若干函啦的實(shí)規(guī)一模式匹配算法模式匹配即子串定位運(yùn)算即如何凄現(xiàn)【IHk就SJ，PO+)的數(shù)第六章樹(shù)和二叉樹(shù)內(nèi)容提要：樹(shù)是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹(shù)，二叉樹(shù)的遞歸定義，基本概念，術(shù)語(yǔ)。樹(shù)：由一個(gè)或多個(gè)（n0）結(jié)點(diǎn)組成的有限集合T,有且僅有一個(gè)結(jié)點(diǎn)稱為根（root）,當(dāng)n1時(shí)，其余的結(jié)點(diǎn)分為m（m0）個(gè)互不相交的有限集合T1,T2,，Tm。每個(gè)集合本身又是棵樹(shù)，被稱作這個(gè)根的子樹(shù)。二叉樹(shù)：是n（n0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

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

27、樹(shù)！方法很簡(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)開(kāi)始存儲(chǔ)。心i*cklld優(yōu)點(diǎn)：不浪費(fèi)空間；插入、刪除方便二叉樹(shù)的遍歷。指按照某種次序訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次，得到一個(gè)線性序列。遍歷規(guī)則二叉樹(shù)由根、左子樹(shù)、右子樹(shù)構(gòu)成，定義為D、L、R若限定先左后右，則有三種實(shí)現(xiàn)方案：DLRLDRLRD先序遍歷中序遍歷后序遍歷樹(shù)的存儲(chǔ)結(jié)構(gòu)，樹(shù)、森林的遍歷及和二叉樹(shù)的相互轉(zhuǎn)換。回顧回顧 h 樹(shù)如何轉(zhuǎn)為二叉樹(shù)？樹(shù)如何轉(zhuǎn)為二叉樹(shù)？方法方法: :加瑞抹境一旋轉(zhuǎn)加瑞抹境一旋轉(zhuǎn)回顧2:二叉樹(shù)怎樣還原為樹(shù)？要點(diǎn)：

28、逆操作，把所有右孩子變?yōu)樾值?！討?:森林如何轉(zhuǎn)為二叉樹(shù)？法一：各森林先各自轉(zhuǎn)為二叉樹(shù)；依次連到前一個(gè)二叉樹(shù)的右子樹(shù)上。法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹(shù)討論2:二叉樹(shù)如何還原為森林？要點(diǎn)：把最右邊的子樹(shù)變?yōu)樯郑溆嘤易訕?shù)變?yōu)樾值軜?shù)和森林的存儲(chǔ)方式：樹(shù)有三種常用存儲(chǔ)方式：雙親表示法孩子表示法孩子一兄弟表示法問(wèn)：樹(shù)一二叉樹(shù)的“連線一抹線一旋轉(zhuǎn)”如何由計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)？答：用“左孩子右兄弟”表示法來(lái)存儲(chǔ)即可。存儲(chǔ)的過(guò)程就是樹(shù)轉(zhuǎn)換為二叉樹(shù)的過(guò)程！firstehiidatanext&mirn指向出入而啟兄弟樹(shù)、森林的遍歷：I深度優(yōu)轉(zhuǎn)歷先姓后根）黑黑鬻5，因J-I廣度優(yōu)先遍歷層次）先根遍歷：訪問(wèn)

29、根結(jié)點(diǎn)；依次先根遍歷根結(jié)點(diǎn)的每棵子樹(shù)。后根遍歷： 依次后根遍歷根結(jié)點(diǎn)的每棵子樹(shù)； 訪問(wèn)根結(jié)點(diǎn)。 討論： 樹(shù)若采用“先轉(zhuǎn)換， 后遍歷”方式， 結(jié)果是否一樣？1 .樹(shù)的先根遍歷與二叉樹(shù)的先序遍歷相同；2 .樹(shù)的后根遍歷相當(dāng)于二叉樹(shù)的中序遍歷；3 .樹(shù)沒(méi)有中序遍歷，因?yàn)樽訕?shù)無(wú)左右之分。深度優(yōu)先避歷深度優(yōu)先避歷（先序、中序）（先序、中序）俞林的遍析俞林的遍析. .廣度優(yōu)先染歷廣度優(yōu)先染歷（層次）（層次）先序遍歷若森林為空，返回；訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；先根遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；先根遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；

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

31、的二叉樹(shù)，且讓新二叉樹(shù)根結(jié)點(diǎn)的權(quán)值等于其左右子樹(shù)的根結(jié)點(diǎn)權(quán)值之和。(3)在F中刪去這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。(4)重復(fù)(2)和(3),直到F只含一棵樹(shù)為止。這棵樹(shù)便是Huffman樹(shù)。具體操作步驟：爪呼匕對(duì)權(quán)情進(jìn)行含笄爪呼匕對(duì)權(quán)情進(jìn)行含笄, ,隱隱 普接普接/ /權(quán)值集合出權(quán)值集合出,5.24 中中，總是含總是含并當(dāng)前并當(dāng)前值最小值最小的兩個(gè)梗的兩個(gè)梗* *初婚初婚卜卜 NTH5H2Hg學(xué)習(xí)重點(diǎn)：(本章內(nèi)容是本課程的重點(diǎn))二叉樹(shù)性質(zhì)及證明方法，并能把這種方法推廣到K叉樹(shù)。二叉樹(shù)遍歷，遍歷是基礎(chǔ)，由此導(dǎo)出許多實(shí)用的算法，如求二叉樹(shù)的高度、各結(jié)點(diǎn)的層次數(shù)、度為0、1、2的結(jié)點(diǎn)數(shù)。由二

32、叉樹(shù)遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹(shù)。由前序和后序序列不能唯一確定一棵二叉樹(shù)。70EUh.合并同合并同F(xiàn)E 卜卜 5Hbic.介井睛】何FHiHlH祖魯并祖魯并(111Fj式叩式叩 2：按左右按左右 1”對(duì)對(duì) HUTAIH呵的所有分支編號(hào)呵的所有分支編號(hào)將將 Huffnan 樹(shù)樹(shù)與與 Huffman 編碼編碼掛鉤掛鉤HuiYnui 編碼結(jié)果：編碼結(jié)果：d*i,&,nWPLlUtX7+2MXX5+3bH(2M)35( (小于等長(zhǎng)碼構(gòu)圖凡小于等長(zhǎng)碼構(gòu)圖凡: :那那) )完全二叉樹(shù)的性質(zhì)。樹(shù)、森林和二叉樹(shù)間的相互轉(zhuǎn)換。哈夫曼樹(shù)的定義、構(gòu)造及求哈夫曼編碼。補(bǔ)充：1.滿

33、二叉樹(shù)和完全二叉樹(shù)有什么區(qū)別？答：滿二叉樹(shù)是葉子一個(gè)也不少的樹(shù)，而完全二叉樹(shù)雖然前k-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。2 .Huffman樹(shù)有什么用？最小冗余編碼、信息高效傳輸?shù)谄哒聢D內(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.Edgenn。注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點(diǎn)vi為尾的弧（即出度邊）；第i列含義

34、：以結(jié)點(diǎn)vi為頭的?。慈攵冗叄｀徑泳仃嚪▋?yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。┱翼旤c(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)；鄰接表的缺點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。圖的遍歷。遍歷定義

35、：從已給的連通圖中某一頂點(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)重新遍歷?；舅枷耄阂灰环聵?shù)的先序遍歷過(guò)程。datafirstarcxnestarvl-*v2-*v4TvXTvSTY3TV6T皈同肺8.因?yàn)?已府版記I廣度優(yōu)先搜索（遍歷）步驟：在訪問(wèn)了起始點(diǎn)v之后，依次訪問(wèn)v的鄰接點(diǎn)；然后再依次（順序）訪問(wèn)這些點(diǎn)（下一層）中未被訪問(wèn)過(guò)的鄰接點(diǎn);直到所有頂點(diǎn)都被訪

36、問(wèn)過(guò)為止。圖的應(yīng)用（最小生成樹(shù)，最短路經(jīng)）最小生成樹(shù) （MST）的性質(zhì)如下： 若U集是V的一個(gè)非空子集， 若（u0,v0）是一條最小權(quán)值的邊， 其中u0U,v0V-U;則：（u0,v0）必在最小生成樹(shù)上。求MST最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法Kruskal算法特點(diǎn)：將邊歸并，適于求稀疏網(wǎng)的最小生成樹(shù)。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)題：一、單源最短路徑一用Dijkstra（迪杰斯特拉）算法二、所有頂點(diǎn)間的最

37、短路徑一用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)之間的最短路徑可以通過(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)?；靖拍钪校B通分量，生成樹(shù)，鄰接點(diǎn)是重點(diǎn)。1連通圖：在無(wú)向圖中，若從頂點(diǎn)v1到頂點(diǎn)v2有路徑，則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的，則稱此圖是連通圖。非連通

38、圖的極大連通子圖叫做連通分量。2生成樹(shù)：是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有n-1條邊。3鄰接點(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)先遍歷。連通圖的最小生成樹(shù)不是唯一的，但最小生成樹(shù)邊上的權(quán)值之和是唯一的。應(yīng)熟練掌握prim和kruscal算法，特別是手工分步模擬生成樹(shù)的生成過(guò)程。普利姆普利姆（Prim）算法算法示例：示例：歸并頂點(diǎn)歸并頂點(diǎn)從單源點(diǎn)到其他頂點(diǎn)，以及各個(gè)頂點(diǎn)間的最短路

39、徑問(wèn)題，掌握熟練手工模擬。補(bǔ)充：1.問(wèn)：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1,此時(shí)是何形狀？答：是樹(shù)！而且是一棵有向樹(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)行遍歷，得到的是生成樹(shù)若對(duì)非連通圖進(jìn)行遍歷，得到的是生成森林。第八章查找內(nèi)容提要：查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。是元素間約束力最差的數(shù)

40、據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個(gè)集合中。（同一類型的數(shù)據(jù)元素構(gòu)成的集合）查找表的操作：查找，插入，刪除。靜態(tài)查找表：順序表，有序表等。針對(duì)靜態(tài)查找表的查找算法主要有：順序查找、折半查找、分塊查找一、順序查找（線性查找）技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。intSearch_Seq（SSTableST,KeyTypekey）ST.elem0.key=key;for（i=ST.length;ST.elemi.key!=key;-i）;returni;/Search_SeqASL=（1+n）/2,時(shí)間效率為O（n）,這是查找成功的情況：順序查找的特點(diǎn)：

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

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

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

44、ild=NULL;查找不成功，生成一個(gè)新結(jié)點(diǎn)s,插入到二叉排序樹(shù)葉子處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ù)的刪除操作如何實(shí)現(xiàn)？如何刪除一個(gè)結(jié)點(diǎn)？假設(shè)：一p表示被刪結(jié)點(diǎn)的指針；PL和PR分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點(diǎn)指針；并假定*p是*f的左孩子；則可能有三種情況：用除此堵點(diǎn)時(shí).a 隹也政產(chǎn)蝴域即可TRfi-裸了就加*右)t依型怖，源子即可1,%力西惴樹(shù)：惘況一p有兩棵子樹(shù)時(shí)，如何進(jìn)行刪除操作？設(shè)刪除前的

45、中序遍歷序列為：.PLspPRf/顯然p的直接前驅(qū)是s,s是*p左子樹(shù)最右下方的結(jié)點(diǎn)希望刪除p后，其它元素的相對(duì)位置不變。有兩種解決方法：法1:令*p的左子樹(shù)為*f的左子樹(shù)，*p的右子樹(shù)接為*s的右子樹(shù)；即fL=PLSR=PR;法2：直接令*s代替*p/*s為*p左子樹(shù)最右下方的結(jié)點(diǎn)第 T二叉排序樹(shù)的ASL2d+-)lnnn平衡二叉樹(shù)的定義：又稱AVL樹(shù)，即它或者是一顆空樹(shù)，是平衡二叉樹(shù)，且左子樹(shù)與右子樹(shù)的深度之差的絕對(duì)值不超過(guò)平衡因子：一一該結(jié)點(diǎn)的左子樹(shù)的深度減去它的右子樹(shù)的深度。平衡二叉樹(shù)的特點(diǎn)：任一結(jié)點(diǎn)的平衡因子只能?。?1、0或如果在一棵AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)

46、必須重新調(diào)整樹(shù)的結(jié)構(gòu),使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類:1)LL平窗旋轉(zhuǎn):赤航A的燈號(hào)5岬左手忖上修人味 X.直人的平畤因子以二三三一一C磯B對(duì)決轉(zhuǎn)1 二2)RR平荀旋轉(zhuǎn)：南吊*附*子*的才子可上斷人ttASflJMW困于4-1新tw-2.*曜力一次也與-Q_aH聞此驗(yàn)?zāi)X口-二一一一.L-L3)LRF新旋轉(zhuǎn):若在A，女子+?的用全樹(shù)上匯入AJAL.慎A的+&bd子從1地扣把，*,注應(yīng)燈：*廿1十H植*昇*廿#穗姓*/人物加他RL平衡旋轉(zhuǎn)；補(bǔ)充：1.查找的過(guò)程是怎樣的？給定一個(gè)值K,在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄,如找到則輸

47、出該記錄，否則輸出查找不成功的信息。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)造成二叉排序樹(shù)的優(yōu)點(diǎn)：希咨A的考手加時(shí)任手忖上*人瞞一.津的平餐因子承1增加里士三三*t*w,r3*r或者是它的左子樹(shù)和右子樹(shù)都1。1。1查找過(guò)程與順序結(jié)構(gòu)有序表中

48、的折半查找相似，查找效率高；2中序遍歷此二叉樹(shù)，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）；如果查找不成功，能夠方便地將被查元素插入到二叉樹(shù)的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。第九章內(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è)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排

49、好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。1)直接插入排序在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后順移。例h卻字序(13,品3,3h9f工311),請(qǐng)寫出直接描入棒序的中間過(guò)程序界“【13】+6,3,31,9,27,區(qū)11【6,13】.3,31,9,27,，11口.11313,6,13.311.9,27,5,1130九13,31，27,5t11Li,6,9,13,27,311，丸11【3,工生*13.27,3111心1.17,311時(shí)間效率：因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為(0+1+n-1)一O(

50、n2)。其他情況下也要考慮移動(dòng)元素的次數(shù)。故時(shí)間復(fù)雜度為O(n2)空間效率：僅占用1個(gè)緩沖單元一一O(1)算法的穩(wěn)定性：因?yàn)?5*排序后仍然在25的后面一一穩(wěn)定直接插入排序算法的實(shí)現(xiàn)：voidInsertSort(SqList&L)/對(duì)順序表L作直接插入排序for(i=2;i=L.length;i+)/假定第一個(gè)記錄有序L.r0=L.ri;j=i-1;先將待插入的元素放入“哨兵”位置while(L0.key直接插入H序21折半插入桂序351路插入11序L小淺舞哥重播入排序J總希;Eft/f大卻#3）表插入排序基本思想：在順序存儲(chǔ)結(jié)構(gòu)中，給每個(gè)記錄增開(kāi)一個(gè)指針?lè)至?，在排序過(guò)程中將指針內(nèi)容

51、逐個(gè)修改為已經(jīng)整理（排序）過(guò)的后繼記錄地址。優(yōu)點(diǎn)：在排序過(guò)程中不移動(dòng)元素，只修改指針。此方法具有鏈表排序和地址排序的特點(diǎn)表插入排序算法分析：1無(wú)需移動(dòng)記錄，只需修改指針值。但由于比較次數(shù)沒(méi)有減少，故時(shí)間效率仍為0（n2）2空間效率肯定低，因?yàn)樵鲩_(kāi)了指針?lè)至浚ǖ谶\(yùn)算過(guò)程中沒(méi)有用到更多的輔助單元）c3穩(wěn)定性：25和25*排序前后次序未變，穩(wěn)定。注：此算法得到的只是一個(gè)有序鏈表，查找記錄時(shí)只能滿足順序查找方式。5）希爾（shell）排序基本思想：先將整個(gè)待排記錄序列分割成若干子序列，分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。例：美解1r序列%3航65.97,7瓦13,27,49,55,04）,酒號(hào)出希爾排序的具體丈現(xiàn)過(guò)程.”10123456709104938