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

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

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

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

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

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

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

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

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

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

10、中任一位置插入一個(gè)結(jié)點(diǎn)刪除：刪除表中任一結(jié)點(diǎn)修改：修改表中給定結(jié)點(diǎn)的值讀值：讀取表中給定結(jié)點(diǎn)的數(shù)據(jù)都只有一個(gè)之間前驅(qū)和一個(gè)直接后驅(qū).表示為:(ai,a2,aian)h單鏈表h循環(huán)鏈表雙向鏈表求長(zhǎng)：計(jì)算表中結(jié)點(diǎn)的個(gè)數(shù)清表：去除表中結(jié)點(diǎn),使其成為空表檢索：找出表中給定特征的結(jié)點(diǎn)排序：按給定要求對(duì)表中元素重新排序（2）常用算法舉例順序表的插入例題：*向線(xiàn)性表中第i個(gè)元素位置插入一個(gè)新元素*算法步驟：1檢查i值是否超出所允許的范圍iwiwn+i,假設(shè)超出,那么進(jìn)行“超出范圍錯(cuò)誤處理；2將線(xiàn)性表的第i個(gè)元素和它后面的所有元素均向后移動(dòng)一個(gè)位置；3將新元素寫(xiě)入到空出的第I個(gè)位置上；4使線(xiàn)性表的長(zhǎng)度增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;順序表的刪除例題：*刪除線(xiàn)性表中第i個(gè)元素*算法步驟：1檢查i值是否超出所允許的范圍1wiwn,假設(shè)超出,那么進(jìn)行“超出范圍錯(cuò)誤處理;2將線(xiàn)性表的第i個(gè)元素后面的所有元素均向前移動(dòng)一個(gè)位置;PROCEDURdeletelist(v,n,i)ABCDEFGBEGIN1但 IF(in+1)THENerror(outofrange)/此處 n=7i國(guó) ELSE

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

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

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

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

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

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

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

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

20、結(jié)點(diǎn)的值賦給函數(shù)名,并將棧頂指針暫存 p,以便回收棧頂結(jié)點(diǎn)；3刪除棧頂結(jié)點(diǎn)；4回收 PT 結(jié)點(diǎn)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è)置一個(gè)空棧只要把棧頂指針置 0 即可.Proceduresetnull(s,top);Begintop:=0end;假設(shè)不考慮回收結(jié)點(diǎn),只要將 HSg 空即可,假設(shè)考慮回收鏈棧中的所有結(jié)點(diǎn),算法如右.Proceduresetnull(HS)；BeginWhileHSnildop:=HS;HS:=HST.next;Dispose(p)End;判斷一個(gè)棧是否為空可用一個(gè)函數(shù)來(lái)描述,?？諘r(shí)返回“真值,非空時(shí)返回“假值.Functionempty(s):boolean；BeginIfs.to

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

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

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

25、和隊(duì)尾指針均賦 0 即可.Proceduresetnull(q,front,rear);Beginfront:=0；rear:=0end;運(yùn)算種類(lèi)鏈隊(duì)算法步驟算法描述插入一個(gè)新的隊(duì)尾元素,即進(jìn)隊(duì)1為待入隊(duì)元素 x 分配一個(gè)結(jié)點(diǎn) PT,并把 x 賦給 PT結(jié)點(diǎn)的值域,nil賦給 PT結(jié)點(diǎn)的指針域；2假設(shè)鏈隊(duì)為空,那么說(shuō)明待插入 PT 的結(jié)點(diǎn)既是隊(duì)首結(jié)點(diǎn)也是隊(duì)尾結(jié)點(diǎn),否那么把 PT結(jié)點(diǎn)插入隊(duì)尾,并使隊(duì)尾指針指向 PT 結(jié)點(diǎn).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;刪 除 隊(duì) 頭 元素,即出隊(duì)1假設(shè)鏈隊(duì)為空,那么進(jìn)行錯(cuò)誤處理；2將隊(duì)首結(jié)點(diǎn)的值賦給變參；3把隊(duì)首指針暫存指針變量 p,以便回收該結(jié)點(diǎn)；4刪除隊(duì)首結(jié)點(diǎn),即假設(shè)鏈隊(duì)中只有一個(gè)結(jié)點(diǎn)即 front=rear,那么應(yīng)同時(shí)把front 和 rear 置空,否那么只修改隊(duì)首指針,使之成為下一個(gè)結(jié)點(diǎn)；5回收原隊(duì)首結(jié)點(diǎn),即 PT 結(jié)點(diǎn).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è)置一個(gè)空隊(duì)只要把隊(duì)首和隊(duì)尾指針置空即可.Proceduresetnull(hq,front,rear)；BeginFront:=nil；rear:=nilEnd;(4)應(yīng)用劃分子集問(wèn)題離散事件仿真iAAF=JC.DAEAAFA2.5 樹(shù)1 .樹(shù)的概念樹(shù)：是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集T,其中有且僅有一個(gè)結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn),其余結(jié)點(diǎn)可以分為m小0個(gè)互不相交的有限集T1,T2,Tm其中每個(gè)集合本身又是一棵樹(shù)叫子樹(shù).是一個(gè)遞歸定義.結(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

37、短表,方法簡(jiǎn)單； 不適合長(zhǎng)表,檢索起來(lái)太慢.對(duì)半檢索法首先選擇表中間的一個(gè)記錄,比擬其關(guān)鍵字的值,假設(shè)要找的記錄的關(guān)鍵字值大,那么再取表的后半部的中間記錄進(jìn)行比擬； 否那么取前半部的中間記錄進(jì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;僅適用丁有序表；只適用向量存儲(chǔ)結(jié)構(gòu)的表,要求表中元素根本不變,在需要插入或刪除運(yùn)算時(shí),影響檢索效率；平均查找長(zhǎng)度最小,ASL=n+1log2n+1-1N分塊檢索法要求將元素均勻地分成塊,塊間