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

..緒論內(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)容：◆基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型。數(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ù)類(lèi)型——是一個(gè)值的集合和定義在該值上的一組操作的總稱(chēng)。抽象數(shù)據(jù)類(lèi)型——由用戶定義的一個(gè)數(shù)學(xué)模型與定義在該模型上的一組操作,它由基本的數(shù)據(jù)類(lèi)型構(gòu)成?！羲惴ǖ亩x及五個(gè)特征。算法——是對(duì)特定問(wèn)題求解步驟的一種描述,它是指令的有限序列,是一系列輸入轉(zhuǎ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ù)雜度。線性表內(nèi)容提要：◆線性表的邏輯結(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)算：修改、插入、刪除、查找、排序修改——通過(guò)數(shù)組的下標(biāo)便可訪問(wèn)某個(gè)特定元素并修改之。核心語(yǔ)句:V[i]=x;順序表修改操作的時(shí)間效率是O<1>2>插入——在線性表的第i個(gè)位置前插入一個(gè)元素實(shí)現(xiàn)步驟：①將第n至第i位的元素向后移動(dòng)一個(gè)位置；②將要插入的元素寫(xiě)到第i個(gè)位置；③表長(zhǎng)加1。注意：事先應(yīng)判斷:插入位置i是否合法?表是否已滿?應(yīng)當(dāng)符合條件：1≤i≤n+1或i=[1,n+1]核心語(yǔ)句：for<j=n;j>=i;j-->a[j+1]=a[j];a[i]=x;n++;插入時(shí)的平均移動(dòng)次數(shù)為：n<n+1>/2÷〔n+1＝n/2≈O<n>3>刪除——?jiǎng)h除線性表的第i個(gè)位置上的元素實(shí)現(xiàn)步驟：①將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；②表長(zhǎng)減1。注意：事先需要判斷,刪除位置i是否合法?應(yīng)當(dāng)符合條件：1≤i≤n或i=[1,n]核心語(yǔ)句：for<j=i+1;j<=n;j++>a[j-1]=a[j];n--;順序表刪除一元素的時(shí)間效率為:T〔n>=<n-1>/2≈O<n>順序表插入、刪除算法的平均空間復(fù)雜度為O<1>單鏈表：〔1用單鏈表結(jié)構(gòu)來(lái)存放26個(gè)英文字母組成的線性表〔a,b,c,…,z,請(qǐng)寫(xiě)出C語(yǔ)言程序。#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}node;node*p,*q,*head;//一般需要3個(gè)指針變量intn;//數(shù)據(jù)元素的個(gè)數(shù)intm=sizeof<node>;/*結(jié)構(gòu)類(lèi)型定義好之后,每個(gè)node類(lèi)型的長(zhǎng)度就固定了,m求一次即可*/voidbuild<>//字母鏈表的生成。要一個(gè)個(gè)慢慢鏈入{inti;head=<node*>malloc<m>;//m=sizeof<node>前面已求出p=head;for<i=1;i<26;i++>//因尾結(jié)點(diǎn)要特殊處理,故i≠26{p->data=i+‘a(chǎn)’-1;//第一個(gè)結(jié)點(diǎn)值為字符ap->next=<node*>malloc<m>;//為后繼結(jié)點(diǎn)"挖坑"！p=p->next；}//讓指針變量P指向后一個(gè)結(jié)點(diǎn)p->data=i+‘a(chǎn)’-1;//最后一個(gè)元素要單獨(dú)處理p->next=NULL;//單鏈表尾結(jié)點(diǎn)的指針域要置空！}}voiddisplay<>//字母鏈表的輸出{p=head;while<p>//當(dāng)指針不空時(shí)循環(huán)〔僅限于無(wú)頭結(jié)點(diǎn)的情況{ printf<"%c",p->data>; p=p->next;//讓指針不斷"順藤摸瓜"}}單鏈表的修改<或讀取

思路：要修改第i個(gè)數(shù)據(jù)元素,必須從頭指針起一直找到該結(jié)點(diǎn)的指針p,然后才能：p>data=new_value讀取第i個(gè)數(shù)據(jù)元素的核心語(yǔ)句是：Linklist*find<Linklist*head,inti>{intj=1;Linklist*p;P=head->next;While<<p!=NULL>&&<j<i>>{p=p->next;j++;}returnp;}單鏈表的插入鏈表插入的核心語(yǔ)句：Step1：s->next=p->next;Step2：p->next=s；單鏈表的刪除刪除動(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)空間雙向鏈表的插入操作：設(shè)p已指向第i元素,請(qǐng)?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;雙向鏈表的刪除操作：設(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)閍i-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è)n－1維數(shù)組組成的線性表。存儲(chǔ)：事先約定按某種次序?qū)?shù)組元素排成一列序列,然后將這個(gè)線性序列存入存儲(chǔ)器中。在二維數(shù)組中,我們既可以規(guī)定按行存儲(chǔ),也可以規(guī)定按列存儲(chǔ)。設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2],則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：

二維數(shù)組列優(yōu)先存儲(chǔ)的通式為：◆稀疏矩陣〔含特殊矩陣的存儲(chǔ)及運(yùn)算。稀疏矩陣：矩陣中非零元素的個(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ò)畫(huà)出結(jié)點(diǎn)圖來(lái)進(jìn)行鏈表〔單鏈表、循環(huán)鏈表等的生成、插入、刪除、遍歷等操作?！魯?shù)組〔主要是二維在以行序/列序?yàn)橹鞯拇鎯?chǔ)中的地址計(jì)算方法。◆稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)?！粝∈杈仃嚨氖宙湵泶鎯?chǔ)方法。補(bǔ)充重點(diǎn)：1.每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域<鏈域>2.在單鏈表中,除了首元結(jié)點(diǎn)外,任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。3.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn),該結(jié)點(diǎn)的數(shù)據(jù)域可以為空,也可存放表長(zhǎng)度等附加信息,其作用是為了對(duì)鏈表進(jìn)行操作時(shí),可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理,編程更方便。如何表示空表？〔1無(wú)頭結(jié)點(diǎn)時(shí),當(dāng)頭指針的值為空時(shí)表示空表；〔2有頭結(jié)點(diǎn)時(shí),當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。5.鏈表的數(shù)據(jù)元素有兩個(gè)域,不再是簡(jiǎn)單數(shù)據(jù)類(lèi)型,編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量,且數(shù)據(jù)類(lèi)型通常不一致,所以要采用結(jié)構(gòu)數(shù)據(jù)類(lèi)型。6.sizeof<x>——計(jì)算變量x的長(zhǎng)度〔字節(jié)數(shù)；malloc<m>—開(kāi)辟m字節(jié)長(zhǎng)度的地址空間,并返回這段空間的首地址；free<p>——釋放指針p所指變量的存儲(chǔ)空間,即徹底刪除一個(gè)變量。鏈表的運(yùn)算效率分析：〔1查找因線性鏈表只能順序存取,即在查找時(shí)要從頭指針找起,查找的時(shí)間復(fù)雜度為O<n>。〔2插入和刪除因線性鏈表不需要移動(dòng)元素,只要修改指針,一般情況下時(shí)間復(fù)雜度為O<1>。但是,如果要在單鏈表中進(jìn)行前插或刪除操作,因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn),所耗時(shí)間復(fù)雜度將是O<n>。例：在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P,需找到它的前驅(qū)結(jié)點(diǎn)的地址,其時(shí)間復(fù)雜度為O〔n8.順序存儲(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)度變化不大,且其主要操作是查找,則采用順序表；◆若線性表的長(zhǎng)度變化較大,且其主要操作是插入、刪除操作,則采用鏈表。9.判斷："數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單",對(duì)嗎？答：對(duì)的。因?yàn)椤贁?shù)組中各元素具有統(tǒng)一的類(lèi)型；②數(shù)組元素的下標(biāo)一般具有固定的上界和下界,即數(shù)組一旦被定義,它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡(jiǎn)單,除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外,只有存取元素和修改元素值的操作。三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素,它包含有三個(gè)數(shù)據(jù)項(xiàng),分別表示該元素的行下標(biāo)、列下標(biāo)和元素值。寫(xiě)出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。解：介紹3種存儲(chǔ)形式。法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：用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算方法：每個(gè)非0元素占用5個(gè)域法3：用三元組矩陣表示：稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能代碼：1.用數(shù)組V來(lái)存放26個(gè)英文字母組成的線性表〔a,b,c,…,z,寫(xiě)出在順序結(jié)構(gòu)上生成和顯示該表的C語(yǔ)言程序。charV[30];voidbuild<>//字母線性表的生成,即建表操作{inti;V[0]='a';for<i=1;i<=n-1;i++>V[i]=V[i-1]+1;}voiddisplay<>//字母線性表的顯示,即讀表操作{inti;for<i=0;i<=n-1;i++>printf<"%c",v[i]>;printf<"\n">;}voidmain<void>//主函數(shù),字母線性表的生成和輸出{n=26;//n是表長(zhǎng),是數(shù)據(jù)元素的個(gè)數(shù),而不是V的實(shí)際下標(biāo)build<>;display<>;}棧和隊(duì)列內(nèi)容提要：◆從數(shù)據(jù)結(jié)構(gòu)角度來(lái)講,棧和隊(duì)列也是線性表,其操作是線性表操作的子集,屬操作受限的線性表。但從數(shù)據(jù)類(lèi)型的角度看,它們是和線性表大不相同的重要抽象數(shù)據(jù)類(lèi)型?！魲５亩x及操作。棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表,該端稱(chēng)為棧的頂端。插入元素到棧頂?shù)牟僮?稱(chēng)為入棧。從棧頂刪除最后一個(gè)元素的操作,稱(chēng)為出棧。對(duì)于向上生成的堆棧:入?？谠E：堆棧指針top"先壓后加":S[top++]=an+1出棧口訣：堆棧指針top"先減后彈":e=S[--top]◆棧的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),及在這兩種結(jié)構(gòu)下實(shí)現(xiàn)棧的操作。順序棧入棧函數(shù)PUSH〔statusPush<ElemTypee>{if<top>M>{上溢}elses[top++]=e;}順序棧出棧函數(shù)POP<>statusPop<>{if<top=L>{下溢}else{e=s[--top];return<e>;}}◆隊(duì)列的定義及操作,隊(duì)列的刪除在一端〔隊(duì)尾,而插入則在隊(duì)列的另一端〔隊(duì)頭。因此在兩種存儲(chǔ)結(jié)構(gòu)中,都需要隊(duì)頭和隊(duì)尾兩個(gè)指針。隊(duì)列：只能在表的一端進(jìn)行插入運(yùn)算,在表的另一端進(jìn)行刪除運(yùn)算的線性表。鏈隊(duì)列結(jié)點(diǎn)類(lèi)型定義：typedefStructQNode{QElemTypedata;//元素StructQNode*next;//指向下一結(jié)點(diǎn)的指針}Qnode,*QueuePtr;鏈隊(duì)列類(lèi)型定義：typedefstruct{QueuePtrfront;//隊(duì)首指針QueuePtrrear;//隊(duì)尾指針}LinkQueue;鏈隊(duì)示意圖：①空鏈隊(duì)的特征：front=rear②鏈隊(duì)會(huì)滿嗎？一般不會(huì),因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！③入隊(duì)〔尾部插入：rear->next=S;rear=S;出隊(duì)〔頭部刪除：front->next=p->next;順序隊(duì)順序隊(duì)類(lèi)型定義：#defineQUEUE-MAXSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{QElemType*base;//隊(duì)列的基址intfront;//隊(duì)首指針intrear;//隊(duì)尾指針}SqQueue建隊(duì)核心語(yǔ)句：q.base=<QElemType*>malloc<sizeof<QElemType*QUEUE_MAXSIZE;//分配空間順序隊(duì)示意圖：循環(huán)隊(duì)列：隊(duì)空條件:front=rear<初始化時(shí)：front=rear>隊(duì)滿條件：front=<rear+1>%N<N=maxsize>隊(duì)列長(zhǎng)度〔即數(shù)據(jù)元素個(gè)數(shù)：L=〔N＋rear－front%N初始化一個(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ì)列returnOK;}//InitQueue;入隊(duì)操作StatusEnQueue<SqQueue&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.base[q.rear]=e;//新元素e入隊(duì)returnOK;}//EnQueue;出隊(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.base[q.front];returnOK;}//DeQueue◆鏈隊(duì)列空的條件是首尾指針相等,而循環(huán)隊(duì)列滿的條件的判定,則有隊(duì)尾加1等于隊(duì)頭和設(shè)標(biāo)記兩種方法。補(bǔ)充重點(diǎn)：為什么要設(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ì)。什么叫"假溢出"？如何解決？答：在順序隊(duì)中,當(dāng)尾指針已經(jīng)到了數(shù)組的上界,不能再有入隊(duì)操作,但其實(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è)計(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)表示方法：模式匹配算法：算法目的：確定主串中所含子串第一次出現(xiàn)的位置〔定位定位問(wèn)題稱(chēng)為串的模式匹配,典型函數(shù)為Index<S,T,pos>BF算法的實(shí)現(xiàn)—即編寫(xiě)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),即匹配成功。否則,匹配失敗,返回值0。IntIndex_BP<SStringS,SStringT,intpos>{//返回子串T在主串S中第pos個(gè)字符之后的位置。若不存在,則函數(shù)值為0.//其中,T非空,1≤pos≤StrLength<S>i=pos;j=1;while<i<=S[0]&&j<=T[0]>//如果i,j二指針在正常長(zhǎng)度范圍,{if<S[i]==T[j]>{++i,++j;}//則繼續(xù)比較后續(xù)字符else{i=i-j+2;j=1;}//若不相等,指針后退重新開(kāi)始匹配}if<j>T[0]>returni-T[0];//T子串指針j正常到尾,說(shuō)明匹配成功,elsereturn0;//否則屬于i>S[0]情況,i先到尾就不正常}//Index_BP補(bǔ)充重點(diǎn)：1.空串和空白串有無(wú)區(qū)別？答：有區(qū)別。空串<NullString>是指長(zhǎng)度為零的串；而空白串<BlankString>,是指包含一個(gè)或多個(gè)空白字符‘’<空格鍵>的字符串."空串是任意串的子串；任意串S都是S本身的子串,除S本身外,S的其他子串稱(chēng)為S的真子串。"樹(shù)和二叉樹(shù)內(nèi)容提要：◆樹(shù)是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu),樹(shù),二叉樹(shù)的遞歸定義,基本概念,術(shù)語(yǔ)。樹(shù)：由一個(gè)或多個(gè)<n≥0>結(jié)點(diǎn)組成的有限集合T,有且僅有一個(gè)結(jié)點(diǎn)稱(chēng)為根〔root,當(dāng)n>1時(shí),其余的結(jié)點(diǎn)分為m<m≥0>個(gè)互不相交的有限集合T1,T2,…,Tm。每個(gè)集合本身又是棵樹(shù),被稱(chēng)作這個(gè)根的子樹(shù)。二叉樹(shù)：是n〔n≥0個(gè)結(jié)點(diǎn)的有限集合,由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。術(shù)語(yǔ)：P88◆二叉樹(shù)的性質(zhì),存儲(chǔ)結(jié)構(gòu)。性質(zhì)1:在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)〔i>0。性質(zhì)2:深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)〔k>0。性質(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)為完全二叉樹(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ǔ)。

優(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)換。回顧2：二叉樹(shù)怎樣還原為樹(shù)？要點(diǎn)：逆操作,把所有右孩子變?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ò)程！樹(shù)、森林的遍歷：①先根遍歷：訪問(wèn)根結(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ú)左右之分。①先序遍歷若森林為空,返回；訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；先根遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；先根遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。②中序遍歷若森林為空,返回；中根遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；訪問(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)編碼。樹(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)造一棵新的二叉樹(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ù)。具體操作步驟：學(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ù)?！粲啥鏄?shù)遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹(shù)。由前序和后序序列不能唯一確定一棵二叉樹(shù)。◆完全二叉樹(shù)的性質(zhì)。◆樹(shù)、森林和二叉樹(shù)間的相互轉(zhuǎn)換?！艄蚵鼧?shù)的定義、構(gòu)造及求哈夫曼編碼。補(bǔ)充：1.滿二叉樹(shù)和完全二叉樹(shù)有什么區(qū)別？答：滿二叉樹(shù)是葉子一個(gè)也不少的樹(shù),而完全二叉樹(shù)雖然前k-1層是滿的,但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。Huffman樹(shù)有什么用？最小冗余編碼、信息高效傳輸圖內(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.Edge[n][n]。注：在有向圖的鄰接矩陣中,第i行含義：以結(jié)點(diǎn)vi為尾的弧<即出度邊；第i列含義：以結(jié)點(diǎn)vi為頭的弧<即入度邊。鄰接矩陣法優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作,如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊〔弧、找頂點(diǎn)的鄰接點(diǎn)等等。鄰接矩陣法缺點(diǎn)：n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊<弧>;空間效率為O<n2>。鄰接表<鏈?zhǔn)?gt;表示法①對(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)有鄰接矩陣方便?！魣D的遍歷。遍歷定義：從已給的連通圖中某一頂點(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ò)程。廣度優(yōu)先搜索〔遍歷步驟：①在訪問(wèn)了起始點(diǎn)v之后,依次訪問(wèn)v的鄰接點(diǎn)；②然后再依次〔順序訪問(wèn)這些點(diǎn)〔下一層中未被訪問(wèn)過(guò)的鄰接點(diǎn)；③直到所有頂點(diǎn)都被訪問(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)間的最短路徑—用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),本章也是這門(mén)課程的重點(diǎn)?！艋靖拍钪?連通分量,生成樹(shù),鄰接點(diǎn)是重點(diǎn)。①連通圖：在無(wú)向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱(chēng)頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱(chēng)此圖是連通圖。非連通圖的極XX通子圖叫做連通分量。②生成樹(shù)：是一個(gè)極小連通子圖,它含有圖中全部n個(gè)頂點(diǎn),但只有n-1條邊。③鄰接點(diǎn)：若<u,v>是E<G>中的一條邊,則稱(chēng)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)先遍歷?！暨B通圖的最小生成樹(shù)不是唯一的,但最小生成樹(shù)邊上的權(quán)值之和是唯一的。應(yīng)熟練掌握prim和kruscal算法,特別是手工分步模擬生成樹(shù)的生成過(guò)程。◆從單源點(diǎn)到其他頂點(diǎn),以及各個(gè)頂點(diǎn)間的最短路徑問(wèn)題,掌握熟練手工模擬。補(bǔ)充：?jiǎ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ǔ)若對(duì)連通圖進(jìn)行遍歷,得到的是生成樹(shù)若對(duì)非連通圖進(jìn)行遍歷,得到的是生成森林。查找內(nèi)容提要：◆查找表是稱(chēng)為集合的數(shù)據(jù)結(jié)構(gòu)。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個(gè)集合中?！餐活?lèi)型的數(shù)據(jù)元素構(gòu)成的集合◆查找表的操作：查找,插入,刪除?！綮o態(tài)查找表：順序表,有序表等。針對(duì)靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找一、順序查找〔線性查找技巧：把待查關(guān)鍵字key存入表頭或表尾〔俗稱(chēng)"哨兵",這樣可以加快執(zhí)行速度。intSearch_Seq<SSTableST,KeyTypekey>{ST.elem[0].key=key;for<i=ST.length;ST.elem[i].key!=key;--i>;returni;}//Search_Seq//ASL＝〔1＋n/2,時(shí)間效率為O<n>,這是查找成功的情況:順序查找的特點(diǎn)：優(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)查找范圍的上界≤下界時(shí)停止查找。ASL的含義是"平均每個(gè)數(shù)據(jù)的查找時(shí)間",而前式是n個(gè)數(shù)據(jù)查找時(shí)間的總和,所以：三、分塊查找〔索引順序查找思路：先讓數(shù)據(jù)分塊有序,即分成若干子表,要求每個(gè)子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值小〔但子表內(nèi)部未必有序。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表,表中還要包含每個(gè)子表的起始地址〔即頭指針。特點(diǎn)：塊間有序,塊內(nèi)無(wú)序。查找：塊間折半,塊內(nèi)線性查找步驟分兩步進(jìn)行：①對(duì)索引表使用折半查找法〔因?yàn)樗饕硎怯行虮?；②確定了待查關(guān)鍵字所在的子表后,在子表內(nèi)采用順序查找法〔因?yàn)楦髯颖韮?nèi)部是無(wú)序表；查找效率ASL分析：◆動(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ù)也分別為二叉排序樹(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{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ù)向右搜索}

}//查找不成功則插入到二叉排序樹(shù)中s=<BiTree>malloc<sizeof<BiTNode>>;s->data=K;s->L_child=NULL;s->R_child=NULL;

//查找不成功,生成一個(gè)新結(jié)點(diǎn)s,插入到二叉排序樹(shù)葉子處case{

t=NULL：t=s;//若t為空,則插入的結(jié)點(diǎn)s作為根結(jié)點(diǎn)K<q->data:q->L_child=s;//若K比葉子小,掛左邊K>q->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的左孩子；則可能有三種情況：*p有兩棵子樹(shù)時(shí),如何進(jìn)行刪除操作？設(shè)刪除前的中序遍歷序列為：….PLspPRf//顯然p的直接前驅(qū)是s,s是*p左子樹(shù)最右下方的結(jié)點(diǎn)希望刪除p后,其它元素的相對(duì)位置不變。有兩種解決方法：法1：令*p的左子樹(shù)為*f的左子樹(shù),*p的右子樹(shù)接為*s的右子樹(shù)；//即fL=PL;SR=PR;法2：直接令*s代替*p//*s為*p左子樹(shù)最右下方的結(jié)點(diǎn)二叉排序樹(shù)的④平衡二叉樹(shù)的定義：又稱(chēng)AVL樹(shù),即它或者是一顆空樹(shù),或者是它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù),且左子樹(shù)與右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1。平衡因子：——該結(jié)點(diǎn)的左子樹(shù)的深度減去它的右子樹(shù)的深度。平衡二叉樹(shù)的特點(diǎn)：任一結(jié)點(diǎn)的平衡因子只能?。?1、0或1。如果在一棵AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn),就有可能造成失衡,此時(shí)必須重新調(diào)整樹(shù)的結(jié)構(gòu),使之恢復(fù)平衡。我們稱(chēng)調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類(lèi)：學(xué)習(xí)重點(diǎn)：◆查找表是稱(chēng)為集合的數(shù)據(jù)結(jié)構(gòu)。因元素間關(guān)系非常松散,其操作需借助其它數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。本章列舉了三種方法〔靜態(tài)查找表,動(dòng)態(tài)查找表實(shí)現(xiàn)查找表的運(yùn)算?！繇樞虮硪蛟O(shè)置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長(zhǎng)度不超過(guò)樹(shù)的深度?！舨檎业腁SL◆二叉排序樹(shù)的形態(tài)取決于元素的輸入順序。按中序遍歷可得到結(jié)點(diǎn)的有序序列,應(yīng)熟練掌握其建立、查找,插入和刪除算法?！羝胶舛鏄?shù)的概念,應(yīng)熟練掌握手工繪制平衡二叉樹(shù)。補(bǔ)充：1.查找的過(guò)程是怎樣的？給定一個(gè)值K,在含有n個(gè)記錄的文件中進(jìn)行搜索,尋找一個(gè)關(guān)鍵字值等于K的記錄,如找到則輸出該記錄,否則輸出查找不成功的信息。2.對(duì)查找表常用的操作有哪些？查詢(xún)某個(gè)"特定的"數(shù)據(jù)元素是否在表中；查詢(xún)某個(gè)"特定的"數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。3.哪些查找方法？查找方法取決于表中數(shù)據(jù)的排列方式;4.如何評(píng)估查找方法的優(yōu)劣？用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)劣。稱(chēng)為平均查找長(zhǎng)度ASL。ASL=∑Pi.Ci5.使用折半查找算法時(shí),要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序6.將線性表構(gòu)造成二叉排序樹(shù)的優(yōu)點(diǎn)：①查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找相似,查找效率高；②中序遍歷此二叉樹(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)。◆排序的分類(lèi),穩(wěn)定排序與不穩(wěn)定排序的定義。穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字值相等,但排序后A、B的先后次序保持不變,則稱(chēng)這種排序算法是穩(wěn)定的?！舨迦肱判颉仓苯硬迦搿⒄郯氩迦?索引表插入、希爾插入排序。插入排序的基本思想是：每步將一個(gè)待排序的對(duì)象,按其關(guān)鍵碼大小,插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上,直到對(duì)象全部插入為止。簡(jiǎn)言之,邊插入邊排序,保證子序列中隨時(shí)都是排好序的。1>直接插入排序在已形成的有序表中線性查找,并在適當(dāng)位置插入,把原來(lái)位置上的元素向后順移。時(shí)間效率：因?yàn)樵谧顗那闆r下,所有元素的比較次數(shù)總和為〔0＋1＋…＋n-1>→O<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.r[0]=L.r[i];j=i-1;//先將待插入的元素放入"哨兵"位置while〔L[0].key<L[j].key>{L.r[j+1]=L.r[j];j--;}//只要子表元素比哨兵大就不斷后移L.r[j+1]=L.r[0];//直到子表元素小于哨兵,將哨兵值送入//當(dāng)前要插入的位置〔包括插入到表首}}折半插入排序既然子表有序且為順序存儲(chǔ)結(jié)構(gòu),則插入時(shí)采用折半查找定可加速。優(yōu)點(diǎn)：比較次數(shù)大大減少,全部元素比較次數(shù)僅為O<nlog2n>。時(shí)間效率：雖然比較次數(shù)大大減少,可惜移動(dòng)次數(shù)并未減少,所以排序效率仍為O<n2>?？臻g效率：仍為O〔1穩(wěn)定性：穩(wěn)定若記錄是鏈表結(jié)構(gòu),用直接插入排序行否？答：行,而且無(wú)需移動(dòng)元素,時(shí)間效率更高！但請(qǐng)注意：?jiǎn)捂湵斫Y(jié)構(gòu)無(wú)法實(shí)現(xiàn)"折半查找"表插入排序基本思想：在順序存儲(chǔ)結(jié)構(gòu)中,給每個(gè)記錄增開(kāi)一個(gè)指針?lè)至?在排序過(guò)程中將指針內(nèi)容逐個(gè)修改為已經(jīng)整理〔排序過(guò)的后繼記錄地址。優(yōu)點(diǎn)：在排序過(guò)程中不移動(dòng)元素,只修改指針。此方法具有鏈表排序和地址排序的特點(diǎn)表插入排序算法分析：①無(wú)需移動(dòng)記錄,只需修改指針值。但由于比較次數(shù)沒(méi)有減少,故時(shí)間效率仍為O<n2>。②空間效率肯定低,因?yàn)樵鲩_(kāi)了指針?lè)至俊驳谶\(yùn)算過(guò)程中沒(méi)有用到更多的輔助單元。③穩(wěn)定性：25和25*排序前后次序未變,穩(wěn)定。注：此算法得到的只是一個(gè)