第二章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1、第二章數(shù)據(jù)結(jié)構(gòu)根底2.1 根本概念程序=算法+數(shù)據(jù)結(jié)構(gòu)也就是說,計算機根據(jù)程序所描述的算法對某種結(jié)構(gòu)的數(shù)據(jù)進行加工處理.1.數(shù)據(jù)結(jié)構(gòu)據(jù)：在計算機領(lǐng)域,指能夠被計算機輸入、存儲、處理和輸出的一切信息.數(shù)據(jù)項：是數(shù)據(jù)的最小單位,有時也稱為域field.數(shù)據(jù)記錄：是數(shù)據(jù)處理領(lǐng)域組織數(shù)據(jù)的根本單位,它由數(shù)據(jù)項組成.數(shù)據(jù)元素：是數(shù)據(jù)集合中相對獨立的單位,也稱結(jié)點.它和數(shù)據(jù)是相對而言的如一條記錄相對于所在文件被認(rèn)為是數(shù)據(jù)元素,而它相對于所含的數(shù)據(jù)項又被認(rèn)為是數(shù)據(jù).數(shù)據(jù)結(jié)構(gòu)：是描述一組數(shù)據(jù)元素及元素間的相互關(guān)系的.邏輯結(jié)構(gòu)：是指數(shù)據(jù)元素之間抽象化的相互關(guān)系.存儲結(jié)構(gòu)：或稱物理結(jié)構(gòu),是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存

2、儲器中的存儲形式.線性結(jié)構(gòu)：每個結(jié)點有且只有一個前驅(qū)結(jié)點和一個后繼結(jié)點第一和最后一個結(jié)點除外邏輯結(jié)構(gòu)丁樹型結(jié)構(gòu)：每個結(jié)點有且只有一個前驅(qū)結(jié)點樹根結(jié)點除非線性結(jié)構(gòu)Q外,但可以有任意多個后繼結(jié)點.I圖型結(jié)構(gòu)：每個結(jié)點可以有任意多個前驅(qū)結(jié)點和任意多個后繼結(jié)點數(shù)據(jù)結(jié)構(gòu)順序存儲結(jié)構(gòu)：將數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素按某中順序存放在計算機存儲器的連?續(xù)存儲單元中.其結(jié)構(gòu)簡單,可節(jié)省存放指針的空間,但需要連續(xù)的存儲空間,當(dāng)數(shù)據(jù)元素的數(shù)目不確定時,會造成存儲空間的閑置.鏈接存儲結(jié)構(gòu)：為數(shù)據(jù)結(jié)構(gòu)的每個結(jié)點元素附加一個數(shù)據(jù)項,其中存放一個與其相鄰接的元素的地址指針,通過指針找到下一個,相關(guān)元素的實際存儲地址.每個結(jié)點由數(shù)據(jù)域

3、和指針域組成.,存儲結(jié)構(gòu)其存儲空間不必連續(xù),在進行插入、刪除操作時不必移動結(jié)點,但結(jié)點指針要占用額外的存儲空間.索引存儲結(jié)構(gòu)： 將全部記錄分別存放在存儲器的不同位置,系統(tǒng)為整個記錄建立一張索引表,表中登記了每條記錄的長度、邏輯記錄號和在存儲器中位置.通過索引表來訪問記錄.I散列存儲結(jié)構(gòu)：在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系,使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng).由關(guān)鍵字作某種運算后直接確定元素的地址.在數(shù)據(jù)的邏輯結(jié)構(gòu)中,樹型結(jié)構(gòu)1:N是圖型結(jié)構(gòu)M:N的特例M二.,線性結(jié)構(gòu)1:1是樹型結(jié)構(gòu)1:N的特例N=1.一種數(shù)據(jù)結(jié)構(gòu)可以表示成一種或多種物理結(jié)構(gòu).在數(shù)據(jù)處理過程中,一

4、個恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)起著非常重要的作用.2 .算法算法：即解決特定問題的方法.數(shù)值算法：是解決數(shù)值問題的算法,主要進行算術(shù)運算,如：求解代數(shù)方程、求算法種類/解數(shù)值積分等.早期的計算機主要用于數(shù)值計算.I非數(shù)值算法：是解決非數(shù)值問題的算法,主要進行比擬和邏輯運算,如：排序、查找、插入、刪除等.隨著計算機技術(shù)的開展,非數(shù)值計算的應(yīng)用越來越廣.r有窮性：在執(zhí)行有限步之后必須終止確定性：所給出的每一計算步驟必須是精確定義的算法準(zhǔn)那么?可行性：要執(zhí)行的每一計算步驟都可在有限時間內(nèi)完成輸入：一般應(yīng)具有.個或多個輸入信息,它是算法所需的初始數(shù)據(jù)L輸出：一般應(yīng)具有0個或多個輸出信息,它是算法對輸入信息的運算結(jié)果

5、正確性：指在合理的數(shù)據(jù)輸入下,能在有限的運行時間內(nèi)得到正確的結(jié)果.算法評價運行時間時間復(fù)雜性：指一個算法在計算機上運算所花費的時間占用的存儲空間空間復(fù)雜性：指一個算法在計算機存儲器中所占用的存儲空間I簡單性：指容易驗證其正確性,且便于編寫、修改、閱讀和調(diào)試3 .Pascal語言簡介一個實型數(shù)據(jù)占用4個字節(jié)的存儲單元一個字符型數(shù)據(jù)占用1個字節(jié)的存儲單元一個布爾型數(shù)據(jù)false或true占用1個字節(jié)的存儲單元數(shù)組： 數(shù)組中的元素在位置上是順序排列的,存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu),邏輯結(jié)構(gòu)為線性結(jié)構(gòu).1數(shù)據(jù)類型記錄：記錄中的成分在位置上是順序排列的,存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu),邏輯結(jié)構(gòu)為線性結(jié)構(gòu).結(jié)構(gòu)類型集合

6、：集合與元素的位置無關(guān),存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu),邏輯結(jié)構(gòu)是關(guān)系為空即不存在次序關(guān)系的結(jié)構(gòu)文件：文件中的成分在位置上是順序排列的,但邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)可以有多種不同結(jié)構(gòu).整型integer一個整型數(shù)據(jù)占用2個字節(jié)的存儲單元實型real簡單類型字符型char布爾型boolean指針類型是以存儲單元的地址作為其值的一種數(shù)據(jù)類型,它也是一種整體變量,系統(tǒng)為指針變量分配一個固定的存儲單元,一般為2個字節(jié).指針類型的定義為：T類型標(biāo)識符數(shù)組、記錄、集合之間的區(qū)別區(qū)別數(shù)組記錄集合定義ArrayTIofT2;Record域名1:類型1域名2:類型2域名n:類型nEND;Setof基類型成分舊TI：下標(biāo)類型,可

7、以是除整型和實型外的其它任何類型簡單類型；T2：成分元素類型,可以是任何類型類型 1n:可以是任何類型基類型：可以是除整型和實型外的其它任何類型簡單類型；特征 成分是同一類型的 每個成分占有的存儲單元具有相同的字節(jié)數(shù) 每個成分是通過下標(biāo)來指明和訪問的 元素個數(shù)是固定的、位置上是有序的成分允許具有不同類型,每個成分占有的存儲單元可能具有不同的字節(jié)數(shù)每個成分是通過域名來指明和訪問的元素個數(shù)是固定、有序的元素個數(shù)是不固定的元素在位置上是無序的其中的元素不能單獨地訪問和運算,只能作為整體進行訪問2語句賦值語句：變量名：=表達式；轉(zhuǎn)向語句：goto語句標(biāo)號；調(diào)用過程語句：過程名參數(shù)表；退出循環(huán)語句：ex

8、it；返回語句：return;出錯處理語句：error字符串；復(fù)合語句：begin語句1;語句2;；語句nend;條件語句：if條件then語句1else語句2;情況語句：case變量名of常量1:語句1;常量2：語句2;end;for變量名：=初值todownto終值do語句；while條件do語句；repeat一組語句until條件；for循環(huán)語句：While循環(huán)語句：repeat循環(huán)語句:2.2 線性表1 .線性表的邏輯結(jié)構(gòu)線性表：是具有相同特征的數(shù)據(jù)元素的一個有限序列,除第一個和最后一個元素外,每個元素邏輯結(jié)構(gòu)：是線性結(jié)構(gòu).2 .線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)和鏈

9、接存儲結(jié)構(gòu)順序表：具有順序存儲結(jié)構(gòu)的線性表線性鏈表：具有鏈接存儲結(jié)構(gòu)的線性表單鏈表： 每個結(jié)點有一個指針域,有一個頭指針h而無尾指針,表中最后一個結(jié)點的指針域是空的.其結(jié)構(gòu)簡單,但查找效率不高查某結(jié)點總要從頭開始線性鏈表循環(huán)鏈表：每個結(jié)點有一個指針域,有一個頭指針h和一個尾指針r,表中最后一；個結(jié)點的指針域不是空的,尾指針指向表的第一個結(jié)點.它形成環(huán)行結(jié)構(gòu),可顯著提升查找效率從任何結(jié)點出發(fā)都能查到所需結(jié)點.【雙向鏈表：每個結(jié)點有兩個指針域,一個指向直接前驅(qū),一個指向直接后驅(qū).它形成雙環(huán)行結(jié)構(gòu),可進一步提升查找效率從某結(jié)點出發(fā),既可以向前查又可以向后查.3 .線性表的運算（1）根本運算插入：在表

10、中任一位置插入一個結(jié)點刪除：刪除表中任一結(jié)點修改：修改表中給定結(jié)點的值讀值：讀取表中給定結(jié)點的數(shù)據(jù)都只有一個之間前驅(qū)和一個直接后驅(qū).表示為:(ai,a2,aian)h單鏈表h循環(huán)鏈表雙向鏈表求長：計算表中結(jié)點的個數(shù)清表：去除表中結(jié)點,使其成為空表檢索：找出表中給定特征的結(jié)點排序：按給定要求對表中元素重新排序（2）常用算法舉例順序表的插入例題：*向線性表中第i個元素位置插入一個新元素*算法步驟：1檢查i值是否超出所允許的范圍iwiwn+i,假設(shè)超出,那么進行“超出范圍錯誤處理；2將線性表的第i個元素和它后面的所有元素均向后移動一個位置；3將新元素寫入到空出的第I個位置上；4使線性表的長度增1.1

11、#2#3#4#5#6#7#PROCEDUREsertlist(vn,i,x)BEGIN1)IF(in+1)THENerror(outofrange)2)ELSEFOR:=nDOWNTODOvj+1：=vj；vi:=x;4)|n:=n+1END;順序表的刪除例題：*刪除線性表中第i個元素*算法步驟：1檢查i值是否超出所允許的范圍1wiwn,假設(shè)超出,那么進行“超出范圍錯誤處理;2將線性表的第i個元素后面的所有元素均向前移動一個位置;PROCEDURdeletelist(v,n,i)ABCDEFGBEGIN1但 IF(in+1)THENerror(outofrange)/此處 n=7i國 ELSE

12、FOR:=iTOn-1DO 刪除vj：=vj+1；-rq與|團 n:=n-1移B#C木耳#F5#G6#7#END;單鏈表的插入3使線性表的長度減1.1#2#3#4#5#6#7#ABC41#2#3#4#5#6#7#8#例題：*向單鏈表中第i個結(jié)點i0之后插入一個元素為b的結(jié)點*算法步驟：1為待插入元素b分配一個結(jié)點假定是由s指針變量所指向的結(jié)點,即sT結(jié)點,并把b賦名sT結(jié)點的值域；2如果i=0,那么將sT結(jié)點插入表頭后返回；3從單鏈表中查找第i個結(jié)點；4假設(shè)查找成功,那么在第i個結(jié)點后插入sT結(jié)點,.否那么說明值超出單鏈表的長度,應(yīng)進行錯誤處理.PROCEDURnsert(head,i,b)B

13、EGIN回NEW(S);ST.data:=b;團IFi=0THENsT.next:=head;head:=s;RETURN;3)P:=head;j:=1;用指針P指向單鏈表中第j個結(jié)點While(pnil)and(ji)doj:=j+1；p:=pT.next；4)國pnilTHEN假設(shè)條件成立,那么說明查找成功sT.next:=pT.next；使sT結(jié)點的指針域指向pT結(jié)點的后繼pT.next:=s；使pT結(jié)點的指針域指向sT結(jié)點ELSEerror(error)END;單鏈表的刪除例題：*在單鏈表中刪除結(jié)點d*算法步驟：1)如果單鏈表為空,那么進行出錯處理；CEDAGBF3726015CEDA

14、GBFb87260153datanext插入前head123412345678插入后 head插入后2如果表頭結(jié)點是被刪除結(jié)點,那么刪除該結(jié)點后返回；3從單鏈表中查找其值等于d的結(jié)點,直到查找結(jié)束成功或失敗為止;4假設(shè)查找成功,那么刪除被查找到的結(jié)點后,否那么進行錯誤處理.PROCEDURelete(head,d)BEGIN回IFhead=nilTHENerror(thisisaemptylist2)四headT.data=dTHEN刪除pT結(jié)點,即值為d的結(jié)點回收p結(jié)點END;結(jié)論：在表很長時,采用順序方式時插入和刪除元素的效率很低,只有在很少進行插入和刪除運算的情況下,采用順序表才是適宜的

15、.而線性鏈表的插入和刪除運算效率總是很高,與表長無關(guān).4.線性表的應(yīng)用線性表是應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu).常見的有：CEdAGBF3726015CEAGBF276015p:=headhead:=headT.next；dispose(p)RETURN團q:=head;p:二qWhilepnilIFpT.data=dELSEq:=p;p:=p4)時pnilTHEN把表頭指針賦給巳以便刪除表頭結(jié)點后收回該結(jié)點刪除表頭結(jié)點系統(tǒng)回收由p所指向的結(jié)點,即原表頭結(jié)點返回.next;P指向待比擬的結(jié)點,q指向p的前驅(qū)結(jié)點doTHENexitT.nextqT.next:=pT.next；dispose(p);ELSEe

16、rror(error)datanext刪除前 head123456712刪除后 had3L567刪除前(1)高級語言中的數(shù)組(2)操作系統(tǒng)中的文件系統(tǒng)、目錄系統(tǒng)(3)事務(wù)治理中的表格2.3 數(shù)組1 .數(shù)組的概念數(shù)組：按一定格式排列起來的一列同一屬性的工程.有一維數(shù)組、二維數(shù)組、三維數(shù)組等.二維數(shù)組：每一行都是一個線性表,每一個數(shù)據(jù)元素既在一個行表中,又在一個列表中.2 .數(shù)組的存儲結(jié)構(gòu)計算機中的存儲單元是一維結(jié)構(gòu),數(shù)組是多維結(jié)構(gòu),用一維的連續(xù)單元存放數(shù)組時,按存放次序的不同有以下不同的存放形式：按行優(yōu)先順序存放元素au的存儲地址為：Loc(a.)=Loc(aii)+(i-1)xn+(j-1)(

17、1imrj1jn)(式中：m為二維數(shù)組的總行數(shù),n為總列數(shù),aj代表其中第i行、第j列的那個元素),按列優(yōu)先順序存放元素aij的存儲地址為：Loc(a.)=Loc(aii)+(j-1)xm+(i-1)(1imrj1jn)壓縮存儲結(jié)構(gòu)適用于數(shù)組中含有大量零元素的特殊數(shù)組,如下三角陣、三對角陣、稀疏矩陣,它只存儲非零元素,這樣可以節(jié)省大量存儲空間.2.4 棧與隊（1）(1)根本概念棧(或稱堆棧)：是一種僅允許在一端進行插入和刪除運算的線性表,遵循后進先出的原那么.棧頂：棧中可以進行插入和刪除的那一端.棧底：棧中不可以進行插入和刪除的那一端.進棧(或稱入棧、壓棧)：向一個棧插入新元素,即把新元素放到

18、棧頂元素的上面,使其成為新的棧頂元素.出棧(或稱退棧)：一個棧刪除元素,即把棧頂元素刪除掉,使其下面相鄰的元素成為新的棧頂元素.（2）存儲結(jié)構(gòu)有順序存儲和鏈接存儲兩種結(jié)構(gòu),鏈接存儲的棧叫鏈棧.順序存儲的棧：進棧ala2a3an棧點1一棧頂,出棧鏈棧：HSdatanext（3）運算運算種類順序存儲的棧鏈棧算法步驟算法描述算法步驟算法描述插入一個新的 棧 頂 元素,即進棧1檢查棧是否已滿,假設(shè)滿,那么進行錯誤處理；2將棧頂指針上移即加 1;3將新元素賦給棧頂元素.Procedurepush(s,x,top);BeginIftop=mThenerror(overflow)elsetop:=top+1

19、;stop:=xend;1 為待進棧元素 x 分配一個結(jié)點 PT,并把x賦給PT結(jié)點的值域；2 把 PT 結(jié)點推入棧頂.Procedurepush(HSx);Begin1) New(p)；PT.data:=x;2) Pnext:=HSHS=pend;刪除棧頂元素,即出棧1檢查棧是否為空,假設(shè)空,那么進行錯誤處理；2將棧頂元素賦給指定變參 y;3將棧頂指針下移即減 1.Procedurepopstack(s,y,top);BeginIftop=0Thenerror(underflow)elsey:=stop;top:=top-1end;1檢查 HS 是否為空,假設(shè)空,那么進行錯誤處理；2 將棧頂

20、結(jié)點的值賦給函數(shù)名,并將棧頂指針暫存 p,以便回收棧頂結(jié)點；3刪除棧頂結(jié)點；4回收 PT 結(jié)點Functionpop(HS):elemtype;Begin1) ifHS=nilthenerror(underflow)2) pop:=HST.data;p:=HS;3) HS:=HST.next;4) Dispose(p)End;讀取棧頂元素只要將棧頂元素賦給指定變參 y 即可,棧頂指針保持不變.Procedurereadtop(s,y,top);BeginIftop=0Thenerror(empty)elsey:=stopend;只要取出 HsTdata 的值即可.Procedurereadto

21、p(HS,y);BeginIfHS=nilThenerror(empty)elsey:=HsTdataend;設(shè)置一個空棧只要把棧頂指針置 0 即可.Proceduresetnull(s,top);Begintop:=0end;假設(shè)不考慮回收結(jié)點,只要將 HSg 空即可,假設(shè)考慮回收鏈棧中的所有結(jié)點,算法如右.Proceduresetnull(HS)；BeginWhileHSnildop:=HS;HS:=HST.next;Dispose(p)End;判斷一個棧是否為空可用一個函數(shù)來描述,棧空時返回“真值,非空時返回“假值.Functionempty(s):boolean；BeginIfs.to

22、p:=0thenempty：=trueElseempty:=falseend;只要當(dāng) HS=nil 時返回“真值,否那么返回“假值即可.Functionempty(hs)boolean；BeginIfHS=nilthenempty:=trueElseempty:=falseend;（4）應(yīng)用A,過程的嵌套和遞歸,表達式求值程序編譯過程中的語法檢查地圖四染色問題2.隊(1)根本概念隊：是一種限定在一端進行插入而在另一端進行刪除的線性表,遵循先進先出的原那么.進隊：從隊尾插入一個新的隊尾元素.出隊：將一個隊中的隊頭元素刪除.(2)存儲結(jié)構(gòu)有順序存儲和鏈接存儲兩種結(jié)構(gòu),鏈接存儲的隊叫鏈隊.隊可以用一

23、維數(shù)組表示q(1:nj),m表示隊列的最大容量,front表示頭指針,rear表示尾指針,入隊時,尾指針增1,出隊時,頭指針增1,當(dāng)rear-front=m時,隊滿.順序存儲的隊：出隊進隊a1a2a3an鏈隊：frontdatanextrear(3)運算插入一個新的隊尾元素,即進隊;刪除隊頭元素,即出隊；設(shè)置一個空隊列；運算種類順序存儲的隊算法描述算法步驟插入一個新的隊尾元素,即進隊1檢查隊是否已滿,假設(shè)滿,那么進行錯誤處理；2將隊尾指針后移；3將新元素賦給隊尾元素；4假設(shè)原隊為空隊,那么進行插入后,同時把隊首指針置為 1.Procedureinsert(q,x,front,rear);Beg

24、inIfrear=mThenerror(overflow)Rear:=rear+1;qrear:=x;iffront=0thenfront:=1end;刪 除 隊 頭 元素,即出隊1檢查隊是否為空,假設(shè)空,那么進行錯誤處理；2將隊首元素賦給指定變參 y;3 假設(shè)刪除后隊空,將隊首和隊尾指針置 0,否那么將隊首指針后移.Proceduredelete(q,y,front,rear);BeginIffront=0Thenerror(underflow)y:=qfront;iffront=rearthenfront:=0;rear:=0elsefront=front+1end;設(shè)置一個空隊只要把隊首

25、和隊尾指針均賦 0 即可.Proceduresetnull(q,front,rear);Beginfront:=0；rear:=0end;運算種類鏈隊算法步驟算法描述插入一個新的隊尾元素,即進隊1為待入隊元素 x 分配一個結(jié)點 PT,并把 x 賦給 PT結(jié)點的值域,nil賦給 PT結(jié)點的指針域；2假設(shè)鏈隊為空,那么說明待插入 PT 的結(jié)點既是隊首結(jié)點也是隊尾結(jié)點,否那么把 PT結(jié)點插入隊尾,并使隊尾指針指向 PT 結(jié)點.Procedureinsert(hq,x,front,rear);Begin1)New(p);PT.data:=x;PT.next:=nil;2)ifrear=nilthenf

26、ront:=p;rear:=pelserearT.next:=p;rear:=pend;刪 除 隊 頭 元素,即出隊1假設(shè)鏈隊為空,那么進行錯誤處理；2將隊首結(jié)點的值賦給變參；3把隊首指針暫存指針變量 p,以便回收該結(jié)點；4刪除隊首結(jié)點,即假設(shè)鏈隊中只有一個結(jié)點即 front=rear,那么應(yīng)同時把front 和 rear 置空,否那么只修改隊首指針,使之成為下一個結(jié)點；5回收原隊首結(jié)點,即 PT 結(jié)點.Proceduredelete(hq,x,front,rear);Begin1)iffront=nilthenerror(underflow);2) x:=frontT.data;3) p:=

27、front;4) iffront=rearthenfront:=nil;rear:=nilelsefront:=frontT.next;5)dispose(p)end;設(shè)置一個空隊只要把隊首和隊尾指針置空即可.Proceduresetnull(hq,front,rear)；BeginFront:=nil；rear:=nilEnd;(4)應(yīng)用劃分子集問題離散事件仿真iAAF=JC.DAEAAFA2.5 樹1 .樹的概念樹：是由一個或多個結(jié)點組成的有限集T,其中有且僅有一個結(jié)點稱為根結(jié)點,其余結(jié)點可以分為m小0個互不相交的有限集T1,T2,Tm其中每個集合本身又是一棵樹叫子樹.是一個遞歸定義.結(jié)點

28、：表示樹中的元素,包含數(shù)據(jù)項及假設(shè)干指向其子樹的分支.結(jié)點的度：結(jié)點擁有的子樹數(shù).葉子：度為0的結(jié)點,又稱端結(jié)點.孩子：結(jié)點子樹的根稱為該結(jié)點的孩子結(jié)點.雙親：孩子結(jié)點的上層結(jié)點.兄弟：同一雙親的孩子.結(jié)點的層次：從根結(jié)點開始算起,根為第一層.深度：樹中結(jié)點的最大層次數(shù).森林：是m棵互不相交的樹的集合.有序樹：樹中結(jié)點同層間從左至右有次序排列,不能互換的樹.能互換的樹稱為無序樹.二叉樹：是nn0個結(jié)點的有限集,它或為空樹n=0,或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成.也是一個遞歸定義.滿二叉樹：深度為h且含有2h-1個結(jié)點的二叉樹,即樹中每一層的結(jié)點數(shù)是滿的二叉樹.完

29、全二叉樹：在一棵二叉樹中,除最后一層外,假設(shè)其余層都是滿的,并且最后一層或者是滿的,或者是右邊缺少連續(xù)假設(shè)干個結(jié)點的二叉樹.滿足關(guān)系式：2h-1-11個結(jié)點;2深度為h的二叉樹中至多含有2h-1個結(jié)點.3假設(shè)在任意一棵二叉樹中,有no個葉子結(jié)點,有n2個度為2的結(jié)點,那么必有：山=止+13 .將樹轉(zhuǎn)換成二叉樹的方法：1在兄弟間加一連線2對每個結(jié)點,除了其左孩子外,去除其與右孩子之間的聯(lián)系3以樹的根結(jié)點為軸心,將整樹順時針轉(zhuǎn)45.3.二叉樹的運算二叉樹的運算包括：二叉樹的遍歷、求二叉樹的深度、輸出二叉樹、二叉樹的線索化和利用線索進行遍歷等.1二叉樹的遍歷這是二叉樹中其它所有運算的根底.它是指根據(jù)

30、一定次序訪問樹中所有結(jié)點,并且每個結(jié)點僅被訪問一次的過程.遍歷一棵非空二叉樹的問題可分解為三個子問題：訪問根結(jié)點、遍歷左子樹、遍歷右子樹相應(yīng)的二叉樹的遍歷方案有六種：DLRLDRLRDDRLRDLRLD遍歷方家算法均為遞歸算法運算結(jié)果代號名稱DLR前序遍歷或先根遍歷Procedurepreorder(bt)；BeginIfbtnilthenwrite(btdata);訪問根結(jié)點preorder(btleft);前序遍歷左子樹preorder(btright);前序遍歷右子樹end;bt 為具有 billist 類型的樹根指針戰(zhàn)LDR中序遍歷或中根遍歷Procedureinorder(bt)；B

31、eginIfbtniltheninorder(btleft);中序遍歷左子樹write(btdata);訪問根結(jié)點inorder(btright);中序遍歷右子樹end;LRD后序遍歷或后根遍歷Procedurepostorder(bt)；BeginIfbtniltheninorder(btleft);后序遍歷左子樹inorder(btright);后序遍歷右子樹write(btdata);訪問根結(jié)點end;前序：A,B,C,D,E,F,G中序：C,B,D,A,E,GF后序：C,D,B,GF,E,A(2)求二叉樹的深度假設(shè)一棵二叉樹為空,那么深度為0;否那么求二叉樹深度的遞歸定義為：它等于左子

32、樹和右子樹中的最大深度加1.即：depth=max(depL,depR)+1求二叉樹深度的遞歸算法：functiondepth(bt):integer;beginifbt=nilthendepth:=0elsedepL:=depth(btT.Left)；depR:=depth(btright);ifdepL=depRthendepth:=depL+1elsedepth:=depR+1end;5.二叉樹的應(yīng)用1)判定樹是用一系列判定構(gòu)成的樹,用于判定.2)哈夫曼樹是一類帶權(quán)路徑最短的樹,用于信息檢索.3)二叉排序樹是一種特殊結(jié)構(gòu)的樹,可作為一種表的組織手段,用于排序和檢索.2.6 圖1 .圖的概

33、念圖的概念：是一種比線性表和樹結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)元素之間的關(guān)系可以是任意的,圖中任意兩個元素之間可以相聯(lián)結(jié).圖的定義：圖G是由兩個集合V(G)和E(G)組成的,記為：G=(V,E)其中V(G)是頂點的非空有限集合E(G)是邊的有限集合,邊是頂點的無序?qū)蛴行驅(qū)?有向圖G:即在圖G中,E(G)是有向邊,邊是頂點的有序?qū)?記為.無向圖G:即在圖G中,E(G)是無向邊,邊是頂點的無序?qū)?記為(V,W)或(W,V).2 .圖的存儲結(jié)構(gòu)(1)關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣表示邊與頂點的關(guān)聯(lián)關(guān)系,它的每行對應(yīng)圖的一個頂點,每列對應(yīng)圖的一條邊.具有n個頂點和e條邊的圖就是一個(nxe)階矩陣,當(dāng)某邊連到某頂點時,與

34、該邊和該頂點對應(yīng)的矩陣元素為1,否那么為0.用關(guān)聯(lián)矩陣表示的圖比擬簡單,用一個二維數(shù)組即可存儲.但這種關(guān)聯(lián)矩陣是個“稀疏矩陣,由于每列只有兩個非0元素,浪費內(nèi)存.(2)鄰接矩陣鄰接矩陣表示各頂點間的鄰接關(guān)系,是一個(nxn)階方陣,n為圖的頂點數(shù).每行和每列都分別對應(yīng)圖的各個頂點,兩頂點有邊相連就稱兩點相鄰接.1對無向圖存在(V,Vj)邊,對有向圖存在邊；a=.00反之對無向圖,其鄰接矩陣是對稱的,只輸入和存儲上三角矩陣元素即可得到整個鄰接矩陣.當(dāng)圖的頂點較多而邊數(shù)較少時,鄰接矩陣也是“稀疏矩陣,浪費存儲空間.(3)鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu),由鄰接矩陣改良而來,只考慮非0元素,節(jié)省存

35、儲空間.在鄰接表中對每個頂點建立一個單鏈表,鏈表中的每個結(jié)點對應(yīng)著該行的一個非0元素.(4)十字鏈表十字鏈表有向圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu).3.圖的遍歷遍歷圖：從圖中某一頂點出發(fā),訪問圖中其余頂點,且使每一頂點僅被訪問一次.f深度優(yōu)先搜索：類似于樹的先根遍歷,是一個遞歸過程.遍歷順序I廣度優(yōu)先搜索：類似于樹的按層次遍歷的過程,不是一個遞歸過程.2.7 檢索1 .根本概念檢索： 也稱查找,是根據(jù)給定的某個值,在表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素.它不是一種數(shù)據(jù)結(jié)構(gòu),而是一種輔助性運算.平均查找長度ASL:為確定記錄在表中的位置所進行的和關(guān)鍵字比擬的次數(shù)的期望值,是衡量一個查找算法好壞的依據(jù).

36、I查表中第i個元素的概率,Ci為找到第i個元素所需的比擬次數(shù).2 .常用檢索方法名稱檢索方式算法區(qū)別線性檢索法從表的第一個元素開始,將給定的值與表中逐個元素的關(guān)鍵字進行比擬,直到兩者符合,查到所要找的元素為止.否那么就是表中沒有要找的元素,檢索不成功.Procedureseqsrch(r,n,k,i)；BeginRn+1.Key:=k；i=1；Whileri.keykdoi:=i+1;IfinThenwrite(succ,i=,i)Elsewrite(unsucc)End;,對表結(jié)構(gòu)為有序表、無序表均可適用； 對存儲結(jié)構(gòu)為向量和線性鏈表均適用； 平均查找長度最大,ASL=(n+1)/2;適合于

37、短表,方法簡單； 不適合長表,檢索起來太慢.對半檢索法首先選擇表中間的一個記錄,比擬其關(guān)鍵字的值,假設(shè)要找的記錄的關(guān)鍵字值大,那么再取表的后半部的中間記錄進行比擬； 否那么取前半部的中間記錄進行比擬,如此反復(fù),直到找到為止.Procedurebingsrch(r,k,n)；BeginLow:=1;high=n;Whilelowrmid.key;low:=mid+1;k=rmid.key;write(mid);exit;k=rmid.key;high:=mid-1end;write(nosucc)end;僅適用丁有序表；只適用向量存儲結(jié)構(gòu)的表,要求表中元素根本不變,在需要插入或刪除運算時,影響檢索效率；平均查找長度最小,ASL=n+1log2n+1-1N分塊檢索法要求將元素均勻地分成塊,塊間