計(jì)算機(jī)軟件技術(shù)基礎(chǔ)：第二講-數(shù)據(jù)結(jié)構(gòu)

1、第二章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2.1程序=算法+數(shù)據(jù)結(jié)構(gòu)也就是說，計(jì)算機(jī)按照程序所描述的算法對(duì)某種結(jié)構(gòu)的數(shù)據(jù)進(jìn)行加工處理。.數(shù)據(jù)結(jié)構(gòu)數(shù) 據(jù)：在計(jì)算機(jī)領(lǐng)域，指能夠被計(jì)算機(jī)輸入、存儲(chǔ)、處理和輸出的一切信息。數(shù)據(jù)項(xiàng)：是數(shù)據(jù)的最小單位，有時(shí)也稱為域（field）。數(shù)據(jù)記錄：是數(shù)據(jù)處理領(lǐng)域組織數(shù)據(jù)的基本單位，它由數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素：是數(shù)據(jù)集合中相對(duì)獨(dú)立的單位，也稱結(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)：或稱物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)

2、存儲(chǔ)器中的存儲(chǔ)形式。r線性結(jié)構(gòu)：每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)（第一和最后一個(gè)結(jié)點(diǎn)除外）（邏輯結(jié)M樹型結(jié)構(gòu)：每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)（樹根結(jié)點(diǎn)除非線性結(jié)時(shí)外），但可以有任意多個(gè)后繼結(jié)點(diǎn)。圖型結(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è)與其相鄰接的元素的地址（指針），通過指針找到下一個(gè)，相關(guān)元素的實(shí)際存儲(chǔ)地址。每個(gè)

3、結(jié)點(diǎn)由數(shù)據(jù)域和指針域組成。,存儲(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ǔ)器中位置。通過索引表來訪問記錄。（散列存儲(chǔ)結(jié)構(gòu)：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)讀取棧 頂元素只要將棧頂元素賦 給指定變參y即可， 棧頂指針保持不變。Procedure readtop (s,y,top );BeginIf top=0Then error (empty)else y:=stop end;只要取出Hs t data

4、 的值即可。Procedure readtop (HS, y);BeginIf HS=nilThen error ( empty) else y:= Hs t data end;設(shè)置一 個(gè)空棧只要把棧頂指針置0 即可。Procedure setnull (s,top);Begintop:=0 end;若不考慮回收結(jié)點(diǎn)， 只要將HS置空即可, 若考慮回收鏈棧中 的所有結(jié)點(diǎn)，算法如 右。Procedure setnull (HS)； BeginWhile HSnil do p:=HS;HS:二HS t . next;Dispose(p)End;判斷一 個(gè)棧是 否為空可用一個(gè)函數(shù)來描 述，?？諘r(shí)返回

5、“真” 值，非空時(shí)返回“假” 值。Function empty (s) ： boolean；BeginIf s. top:=0 then empty： =trueElse empty：=falseend;只要當(dāng)IIS=nil時(shí)返 回“真”值，否則返 回“假”值即可。Function empty ( hs )： boolean；BeginIf HS=nilthen empty：=trueElse empty： =false end;應(yīng)用過程的嵌套和遞歸表達(dá)式求值程序編譯過程中的語法檢查地圖四染色問題2.隊(duì)(1)基本概念隊(duì)：是一種限定在一端進(jìn)行插入而在另一端進(jìn)行刪除的線性表，遵循先進(jìn)先出的原則。進(jìn)

6、隊(duì)：從隊(duì)尾插入一個(gè)新的隊(duì)尾元素。出隊(duì)：將一個(gè)隊(duì)中的隊(duì)頭元素刪除。(2)存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)和鏈接存儲(chǔ)兩種結(jié)構(gòu)，鏈接存儲(chǔ)的隊(duì)叫鏈隊(duì)。隊(duì)可以用一維數(shù)組表示q (1： m) , m表示隊(duì)列的最大容量，front表示頭指針，rear表 示尾指針，入隊(duì)時(shí)，尾指針增1,出隊(duì)時(shí)，頭指針增1,當(dāng)61-10111二111時(shí)，隊(duì)滿。順序存儲(chǔ)的隊(duì)：出隊(duì)進(jìn)隊(duì)鏈隊(duì):front data nextrear（3） 運(yùn)算插入一個(gè)新的隊(duì)尾元素，即進(jìn)隊(duì);刪除隊(duì)頭元素，即出隊(duì)；設(shè)置一個(gè)空隊(duì)列；運(yùn)算種類順序存儲(chǔ)的隊(duì)算法步驟算法描述插入一個(gè) 新的隊(duì)尾 元素，即進(jìn)隊(duì)1）檢查隊(duì)是否已滿，若滿，則進(jìn)行錯(cuò)誤處理；2）將隊(duì)尾指針后移；3）將新元素

7、賦給隊(duì)尾元素；4）若原隊(duì)為空隊(duì)，則進(jìn)行插入后，同時(shí)把隊(duì)首 指針置為1。Procedure insert (q,x,front, rear);BeginIf rear=m Then error (overflow)Rear:=rear+l;qrear:=x;if front=0 then front:=1end;刪除隊(duì)頭 元素，即出 隊(duì)1）檢查隊(duì)是否為空，若空，則進(jìn)行錯(cuò)誤處理；2）將隊(duì)首元素賦給指定變參y;3）若刪除后隊(duì)空，將隊(duì)首和隊(duì)尾指針置0,否則 將隊(duì)首指針后移。Procedure delete (q,y,front, rear);BeginIf front=0 Then error(und

8、erflow) y:=qfront;if front=rear then front:=0;rear:=0 else front=front+1end;設(shè)置一個(gè) 空隊(duì)只要把隊(duì)首和隊(duì)尾指針均賦0即可。Procedure setnull (q, front, rear);Beginfront:=0； rear:=0 end;（4） 應(yīng)用運(yùn)算種類鏈隊(duì)算法步驟算法描述插入一個(gè) 新的隊(duì)尾 元素,即進(jìn)隊(duì)1）為待入隊(duì)兀素x分配 個(gè)結(jié)點(diǎn)P t , 并把x賦給P t結(jié)點(diǎn)的值域，nil賦 給Pt結(jié)點(diǎn)的指針域；2）若鏈隊(duì)為空，則表明待插入Pt的結(jié) 點(diǎn)既是隊(duì)首結(jié)點(diǎn)也是隊(duì)尾結(jié)點(diǎn)，否則 把Pt結(jié)點(diǎn)插入隊(duì)尾，并使隊(duì)尾指針

9、指向Pt結(jié)點(diǎn)。Procedure insert (hq,x, front, rear);BeginNew (p) ; Pt. data:二x; P t . next :=nil;if rear=nilthen front:=p; rear:=pelse rear t . next:=p; rear:=pend;刪除隊(duì)頭 元素，即出隊(duì)1）若鏈隊(duì)為空，則進(jìn)行錯(cuò)誤處理；2）將隊(duì)首結(jié)點(diǎn)的值賦給變參；3）把隊(duì)首指針暫存指針變量p,以便回 收該結(jié)點(diǎn)；4）刪除隊(duì)首結(jié)點(diǎn)，即若鏈隊(duì)中只有一個(gè) 結(jié)點(diǎn)（即fron t=rear）,則應(yīng)同時(shí)把 front和rear置空，否則只修改隊(duì)首 指針，使之成為下一個(gè)結(jié)點(diǎn)；5）回

10、收原隊(duì)首結(jié)點(diǎn)，即Pt結(jié)點(diǎn)。Procedure delete (hq,x, front, rear);Beginif front=nil then error(underflow);x:二front t . data;p:=front;if front=rear then front:=nil;rear:=nil else front:=front t . next;dispose(p)end;設(shè)置一個(gè) 空隊(duì)只要把隊(duì)首和隊(duì)尾指針置空即可。Procedure setnull(hq, front, rear)；BeginFront： =nil； rear： =nilEnd;劃分子集問題離散事件仿真.

11、5樹.樹的概念樹：是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集T,其中有且僅有一個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)，其余結(jié)點(diǎn)可 以分為m （mO）個(gè)互不相交的有限集Tl, T2,，Tm,其中每個(gè)集合本身又是一棵樹 （叫子樹）。是一個(gè)遞歸定義。結(jié) 點(diǎn)：表示樹中的元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹的分支。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。葉 子：度為0的結(jié)點(diǎn)，又稱端結(jié)點(diǎn)。孩 子：結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。雙 親：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)。兄 弟：同一雙親的孩子。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始算起，根為第一層。深度：樹中結(jié)點(diǎn)的最大層次數(shù)。森 林：是口棵互不相交的樹的集合。有序樹：樹中結(jié)點(diǎn)同層間從左至右有次序排列，不能互換的樹。能互換的樹稱為無

12、序樹。二叉樹：是n （n20）個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛洌╪=0）,或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱 為左子樹和右子樹的互不相交的二叉樹構(gòu)成。也是一個(gè)遞歸定義。滿二叉樹：深度為h且含有2h-l個(gè)結(jié)點(diǎn)的二叉樹，即樹中每一層的結(jié)點(diǎn)數(shù)是滿的二叉樹。完全二叉樹：在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿 的，或者是右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)的二叉樹。滿足關(guān)系式：2h-1-ln2h-l.二叉樹的存儲(chǔ)結(jié)構(gòu)可以有順序存儲(chǔ)和鏈接存儲(chǔ)兩種。順序存儲(chǔ)只適合完全二叉樹，能夠充分利用存儲(chǔ)空間，但 對(duì)一般二叉樹不合適，會(huì)造成許多存儲(chǔ)單元空閑。一般的二叉樹通常用具有兩個(gè)指針域的鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)。其

13、中每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域、 左指針域和右指針域組成。1）二叉樹的第i層上至多有2-（iNl）個(gè)結(jié)點(diǎn)；2）深度為h的二叉樹中至多含有211個(gè)結(jié)點(diǎn)。3）若在任意一棵二叉樹中，有n。個(gè)葉子結(jié)點(diǎn)，有山個(gè)度為2的結(jié)點(diǎn)，則必有：n0=n2+l.將樹轉(zhuǎn)換成二叉樹的方法：1）在兄弟間加一連線2）對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與右孩子之間的聯(lián)系3）以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45。3.二叉樹的運(yùn)算二叉樹的運(yùn)算包括：二叉樹的遍歷、求二叉樹的深度、輸出二叉樹、二叉樹的線索化和利用 線索進(jìn)行遍歷等。（1）二叉樹的遍歷這是二叉樹中其它所有運(yùn)算的基礎(chǔ)。它是指按照一定次序訪問樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié) 點(diǎn)僅被訪問一次的過

14、程。遍歷一棵非空二叉樹的問題可分解為三個(gè)子問題：訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹。相應(yīng)的二叉樹的遍歷方案有六種：DLR、LDR、LRD、DRL、RDL、RLD。遍歷方案算法（均為遞歸算法）.運(yùn)算結(jié)果代號(hào)名稱DLR前序遍歷或先根遍歷Procedure preorder (bt)；BeginIf btnil thenwrite (bt t . data) ;訪問根結(jié)點(diǎn)preorder (bt f . left) ;前序遍歷左子樹preorder (bt t . right) ; 前序遍歷右子樹 end;bt為具有billist類型的樹根指針LDR中序遍歷或中根遍歷Procedure inorde

15、r (bt)；BeginIf btnil theninorder(bt t . left) ;中序遍歷左子樹write (bt t . data) ;訪問根結(jié)點(diǎn)inorder (bt t . right) ; 中序遍歷右子樹 end;LRD后序遍歷或后根遍歷Procedure postorder (bt)；BeginIf btnil theninorder (bt t . left) ; 后序遍歷左子樹 inorder (bt t . right) ; 后序遍歷右子樹 write (bt t . data) ;訪問根結(jié)點(diǎn)end;前序：A,B,C,D,E,F,G中序：C,B,D,A,E,G,F后

16、序：C,D,B,G,F9E,A（2）求二叉樹的深度若一棵二叉樹為空，則深度為0；否則求二叉樹深度的遞歸定義為：它等于左子樹和右子樹中的最大深度加1。即： depth=max （depL, depR） +1求二叉樹深度的遞歸算法：function depth (bt) ： integer；beginif bt=nil then depth： =0else depL： = depth (bt t . Left)； depR： = depth (bt f .right)； if depL=depR then depth:=depL+l else depth:=depR+lend;5.二叉樹的應(yīng)用1）

17、判定樹是用一系列判定構(gòu)成的樹，用于判定。2）哈夫曼樹是一類帶權(quán)路徑最短的樹，用于信息檢索。3）二叉排序樹 是一種特殊結(jié)構(gòu)的樹，可作為一種表的組織手段，用于排序和檢索。2.6圖1.圖的概念圖的概念：是一種比線性表和樹結(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)的無序?qū)蛴行驅(qū)?。有向圖G：即在圖G中，E (G)是有向邊，邊是頂點(diǎn)的有序?qū)Γ洖閂,W。無向圖G：即在圖G中，E (G)是無向邊，邊是頂點(diǎn)的無序?qū)Γ?/p>

18、為(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è)(n x e)階矩陣，當(dāng)某邊連到某頂點(diǎn)時(shí)，與該邊和該 頂點(diǎn)對(duì)應(yīng)的矩陣元素為1,否則為0。用關(guān)聯(lián)矩陣表示的圖比較簡(jiǎn)單，用一個(gè)二維數(shù)組即可 存儲(chǔ)。但這種關(guān)聯(lián)矩陣是個(gè)“稀疏”矩陣，因?yàn)槊苛兄挥袃蓚€(gè)非0元素，浪費(fèi)內(nèi)存。(2)鄰接矩陣鄰接矩陣表示各頂點(diǎn)間的鄰接關(guān)系，是一個(gè)(nx n)階方陣，n為圖的頂點(diǎn)數(shù)。每行和每 列都分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)，兩頂點(diǎn)有邊相連就稱兩點(diǎn)相鄰接。1對(duì)無向圖存在(Vi, %)邊，對(duì)有向圖存在Vi, V邊；Hij

19、= YL 0反之對(duì)無向圖，其鄰接矩陣是對(duì)稱的，只輸入和存儲(chǔ)上三角矩陣元素即可得到整個(gè)鄰接矩陣。 當(dāng)圖的頂點(diǎn)較多而邊數(shù)較少時(shí)，鄰接矩陣也是“稀疏”矩陣，浪費(fèi)存儲(chǔ)空間。鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由鄰接矩陣改進(jìn)而來，只考慮非0元素，節(jié)省存儲(chǔ)空 間。在鄰接表中對(duì)每個(gè)頂點(diǎn)建立一個(gè)單鏈表，鏈表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著該行的一個(gè)非0 元素。十字鏈表十字鏈表有向圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3.圖的遍歷遍歷圖：從圖中某一頂點(diǎn)出發(fā)，訪問圖中其余頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次。J深度優(yōu)先搜索：類似于樹的先根遍歷，是一個(gè)遞歸過程。遍歷順序I廣度優(yōu)先搜索：類似于樹的按層次遍歷的過程，不是一個(gè)遞歸過程。2.7檢索.基本概念

20、檢索：也稱查找，是根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元 素。它不是一種數(shù)據(jù)結(jié)構(gòu)，而是一種輔助性運(yùn)算。平均查找長(zhǎng)度ASL：為確定記錄在表中的位置所進(jìn)行的和關(guān)鍵字比較的次數(shù)的期望值，是衡量一個(gè)查找算法好壞的依據(jù)。X n為表中元素總數(shù)，Pi為查表中第i個(gè)元素的概率，Ci為找到第i個(gè)元素所需的比較次數(shù)。.常用檢索方法名稱檢索方式算法區(qū)別性索 線檢法從表的第一個(gè)元素開始，將給定的 值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行 比較，直到兩者符合，查到所要找 的元素為止。否則就是表中沒有要 找的元素，檢索不成功。Procedure seqsrch (r, n, k, i)；BeginRn+l.K

21、ey：=k； i=l；While riL key k do i:=i+l;If inThen write(J succ, i=，i)Else write C unsucc，)End;對(duì)表結(jié)構(gòu)為有序表、無序 表均可適用；對(duì)存儲(chǔ)結(jié)構(gòu)為向量和線性 鏈表均適用；平均查找長(zhǎng)度最大，ASL= (n+1) /2；適合于短表，方法簡(jiǎn)單；不適合長(zhǎng)表，檢索起來太 慢。半索 對(duì)檢法首先選擇表中間的一個(gè)記錄，比較 其關(guān)鍵字的值，若要找的記錄的關(guān) 鍵字值大，則再取表的后半部的中 間記錄進(jìn)行比較；否則取前半部的 中間記錄進(jìn)行比較，如此反復(fù)，直 到找到為止。Procedure bingsrch (r, k, n)；Begi

22、nLow:=l; high=n;While lowhigh do .mid: = (low+high)/2;case :krmid. key; low:=mid+l; k=rmid, key; write(mid);exit;km then return (0);jstart;while (j Bi. start+Bi. length and ( k2 Aj,key) do j：= j +1；if j=BiL start+Bi, lengththen return(0) else return(j) end;要求表中元素是逐段有序 的；對(duì)存儲(chǔ)結(jié)構(gòu)為向量和線性 鏈表的均適用；平均查找長(zhǎng)度比線性檢

23、索 小，nsASL= log2 ( +1) + 一S2散列 檢索 法在記錄的存儲(chǔ)位置和它的關(guān)鍵字 之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，由 關(guān)鍵字作某種運(yùn)算后直接確定元 素的地址。用散列函數(shù)(或稱哈希在散列存儲(chǔ)中會(huì)引起沖突，降低沖突的途徑：1)降低裝填因子a2)選擇合適的散列函數(shù)選擇合適的解決沖突的方法函數(shù)）來表示關(guān)鍵字與元素地址的 關(guān)系。2.8排序.基本概念排序：是將一組記錄按其關(guān)鍵字的遞增或遞減的次序排列起來。它也是一種運(yùn)算。.常用排序方法名稱排序方式算法選擇排序首先找出表中關(guān)鍵字為最小的（或最大 的）元素，將其與表中第一個(gè)關(guān)鍵字大于 它的元素對(duì)換，然后再在其余元素中找出 關(guān)鍵字最小的元素與表中第二

24、個(gè)關(guān)鍵字 大于它的元素對(duì)換，依次類推，直到整個(gè) 表按其關(guān)鍵字由小到大排好。Procedure seisort (r,n);BeginFor i:=1 to n-1 doP：=i；for j:=i+l to n doif rj.key 0) and (switch=l) doswitch:=0;for j:=1 to m doif rj. key rj+1. keythen switch:； temp:=rj; rj :=rj+l; rj+l :=temp;end;線性插入 排序?qū)⒁粋€(gè)表看成由已排好序的和未排好序 的兩個(gè)部分組成，依次將未排好序部分的 元素逐個(gè)通過線性比較插入到已排好序 部分的應(yīng)

25、有位置上去。Procedure insort (r, n)；BeginFor i： =2 to n dox： =ri； r0：=x； j：二i -1； while x.key x.key) and (jI) do.If ijThen ri:=rj; i:=i+l;While (rj.key x.key) and (Ij) do i:=i+l;If ij then rj:=ri;Until i=j;ri:=x; i:=i+l;If lj then call qksort (r, 1, j);If ip then call qksort (r, i, p)End;歸并排序即將兩個(gè)或兩個(gè)以上的有序表

26、組合成一個(gè)新的有序表。先將n數(shù)據(jù)看成n個(gè)長(zhǎng)度為1的表，將相 鄰的表成對(duì)歸并，得到長(zhǎng)度為2的有序表，再將相鄰表成對(duì)歸并成長(zhǎng)度為4的有序表，依次做下 去，直到所有數(shù)據(jù)均合并到一個(gè)長(zhǎng)度為n的有序表中為止。應(yīng)關(guān)系，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。 由關(guān)鍵字作某種運(yùn)算后直接確定元素的地址。在數(shù)據(jù)的邏輯結(jié)構(gòu)中，樹型結(jié)構(gòu)（1：N）是圖型結(jié)構(gòu)（M:N）的特例（M=l）, 線性結(jié)構(gòu)（1:1）是樹型結(jié)構(gòu)（1:N）的特例（N=1）。一種數(shù)據(jù)結(jié)構(gòu)可以表示成一種或多種物理結(jié)構(gòu)。在數(shù)據(jù)處理過程中，一個(gè)恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu) 起著非常重要的作用。2.算法算 法：即解決特定問題的方法。L數(shù)值算法：是解決數(shù)值問題的算法，

27、主要進(jìn)行算術(shù)運(yùn)算，如：求解代數(shù)方程、求 算法種類解數(shù)值積分等。早期的計(jì)算機(jī)主要用于數(shù)值計(jì)算。 I非數(shù)值算法：是解決非數(shù)值問題的算法，主要進(jìn)行比較和邏輯運(yùn)算，如：排序、查 找、插入、刪除等。隨著計(jì)算機(jī)技術(shù)的發(fā)展，非數(shù)值計(jì)算的應(yīng)用越來越 廣。有窮性：在執(zhí)行有限步之后必須終止確定性：所給出的每一計(jì)算步驟必須是精確定義的算法準(zhǔn)則 可行性：要執(zhí)行的每一計(jì)算步驟都可在有限時(shí)間內(nèi)完成輸入： 一般應(yīng)具有0個(gè)或多個(gè)輸入信息，它是算法所需的初始數(shù)據(jù)【輸出： 一般應(yīng)具有0個(gè)或多個(gè)輸出信息，它是算法對(duì)輸入信息的運(yùn)算結(jié)果正確性：指在合理的數(shù)據(jù)輸入下，能在有限的運(yùn)行時(shí)間內(nèi)得到正確的結(jié)果。算法評(píng)價(jià) 運(yùn)行時(shí)間（時(shí)間復(fù)雜性）：

28、指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間占用的存儲(chǔ)空間（空間復(fù)雜性）：指一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器中所占用的存儲(chǔ)空間 I簡(jiǎn)單性：指容易驗(yàn)證其正確性，且便于編寫、修改、閱讀和調(diào)試Pascal語言簡(jiǎn)介整型 integer整型 integer一個(gè)整型數(shù)據(jù)占用2個(gè)字節(jié)的存儲(chǔ)單元實(shí)型real簡(jiǎn)單類型|字符型charI布爾型boolean一個(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)為線性結(jié)構(gòu)。（1）數(shù)據(jù)類型記錄：記錄中的成分在位置上是順序排列的，存儲(chǔ)結(jié)構(gòu)

29、是順序存儲(chǔ)結(jié)構(gòu)，循環(huán)鏈表雙向鏈表線性表的運(yùn)算基本運(yùn)算插入：在表中任一位置插入一個(gè)結(jié)點(diǎn)刪除：刪除表中任一結(jié)點(diǎn)修改：修改表中給定結(jié)點(diǎn)的值讀值：讀取表中給定結(jié)點(diǎn)的數(shù)據(jù)求長(zhǎng)：計(jì)算表中結(jié)點(diǎn)的個(gè)數(shù)清表：清除表中結(jié)點(diǎn)，使其成為空表檢索：找出表中給定特征的結(jié)點(diǎn)排序：按給定要求對(duì)表中元素重新排序常用算法舉例順序表的插入例題：*向線性表中第i個(gè)元素位置插入一個(gè)新元素*算法步驟：1）檢查i值是否超出所允許的范圍（IWiWn+l）,若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理；2）將線性表的第i個(gè)元素和它后面的所有元素均向后移動(dòng)一個(gè)位置；3）將新元素寫入到空出的第I個(gè)位置上；4）使線性表的長(zhǎng)度增loPROCEDURE inse

30、rtlist (v,n, i, x)BEGIN回 IF (in+l) THEN error 團(tuán) ELSE FOR j:=n DOWNTO i DO .vj+l :=vj;慟vi:=x;叵|n:=n+l END;順序表的刪除例題：*刪除線性表中第i個(gè)元素*算法步驟：1）檢查i值是否超出所允許的范圍（IWiWn）,若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理;2）將線性表的第i個(gè)元素后面的所有元素均向前移動(dòng)一個(gè)位置；1# 28 3# 4# 5# 6# 7#3)使線性表的長(zhǎng)度減1。PROCEDURE deletelist(v,n, i)BEGIN1)| IF (in+l) THEN error (out of

31、 range)此處 n =7 i=4國(guó) ELSE FOR j:=i TO n-1 DO刪除vj:=vj+l;胡 n:=n-l 1# 2# 3# 4# 5# 6# 7#END;單鏈表的插入例題：*向單鏈表中第i個(gè)結(jié)點(diǎn)（i20）之后插入一個(gè)元素為b的結(jié)點(diǎn)*算法步驟：1）為待插入元素b分配一個(gè)結(jié)點(diǎn)（假定是由s指針變量所指向的結(jié)點(diǎn)，即st結(jié)點(diǎn)），并把 b賦給s t結(jié)點(diǎn)的值域；2）如果i=0,則將st結(jié)點(diǎn)插入表頭后返回；3）從單鏈表中查找第i個(gè)結(jié)點(diǎn)；4）若查找成功,則在第i個(gè)結(jié)點(diǎn)后插入s t結(jié)點(diǎn)否則表明值超出單鏈表的長(zhǎng)度,應(yīng)進(jìn)行 錯(cuò)誤處理。插入前 head1 2 3 I 4cEDAGBF3726015d

32、atanext5 6.7插入后 headCEDAGBFb87260153CEDAGBFb87260153插入前G0head插入后G 0123 1 4 5678PROCEDURE insert (head,i, b)BEGINNEW (S) ； Sdata:二b；IF i=0 THEN s f . next:= head； head:二s； RETURN；P：=head； j:=l ； 用指針P指向單鏈表中第j個(gè)結(jié)點(diǎn)While (p nil) and (ji). doj：=j+1;p:=p f . next；回IF pnil THEN 若條件成立，則表明查找成功s f . next:二p t.n

33、ext；使s t結(jié)點(diǎn)的指針域指向p t結(jié)點(diǎn)的后繼p t . next:二s；使pt結(jié)點(diǎn)的指針域指向s t結(jié)點(diǎn)ELSE error ( error，) END;單鏈表的刪除例題：*在單鏈表中刪除結(jié)點(diǎn)d *算法步驟：1）如果單鏈表為空，則進(jìn)行出錯(cuò)處理；2）如果表頭結(jié)點(diǎn)是被刪除結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)后返回；3）從單鏈表中查找其值等于d的結(jié)點(diǎn)，直到查找結(jié)束（成功或失?。橹?4）若查找成功，則刪除被查找到的結(jié)點(diǎn)后，否則進(jìn)行錯(cuò)誤處理。刪除前 head12 3 ； 4cEdAGBF3726015datanext5 6.7刪除前刪除后97CPROCEDURE delete (head, d)BEGINflj|

34、IF head=nil THEN error C this is a empty list，)；團(tuán) IF head t . data =d THENP：二head；把表頭指針賦給P,以便刪除表頭結(jié)點(diǎn)后收回該結(jié)點(diǎn)head:二head t . next； 刪除表頭結(jié)點(diǎn)dispose (p) ；系統(tǒng)回收由p所指向的結(jié)點(diǎn)，即原表頭結(jié)點(diǎn)RETURN ；返回叵q:=head； p:=q t.next ； P指向待比較的結(jié)點(diǎn)，q指向p的前驅(qū)結(jié)點(diǎn)While p nil doIF p t . data=d THEN exitELSE q:=p; p:=p t .next；回 IF pnil THENq t-ne

35、xt:=p t . next； 刪除p t結(jié)點(diǎn)，即值為d的結(jié)點(diǎn)dispose(p) ；回收 p 結(jié)點(diǎn)ELSE error error，)END;結(jié)論：在表很長(zhǎng)時(shí)，采用順序方式時(shí)插入和刪除元素的效率很低，只有在很少進(jìn)行插入和刪除 運(yùn)算的情況下，采用順序表才是合適的。而線性鏈表的插入和刪除運(yùn)算效率總是很高， 與表長(zhǎng)無關(guān)。.線性表的應(yīng)用線性表是應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu)。常見的有：高級(jí)語言中的數(shù)組操作系統(tǒng)中的文件系統(tǒng)、目錄系統(tǒng)事務(wù)管理中的表格.3數(shù)組.數(shù)組的概念數(shù)組：按一定格式排列起來的一列同一屬性的項(xiàng)目。有一維數(shù)組、二維數(shù)組、三維數(shù)組等。二維數(shù)組：每一行都是一個(gè)線性表，每一個(gè)數(shù)據(jù)元素既在一個(gè)行表中，又在一個(gè)列表中。.數(shù)組的存儲(chǔ)結(jié)構(gòu)計(jì)算機(jī)中的存儲(chǔ)單元是一維結(jié)構(gòu)，數(shù)組是多維結(jié)構(gòu)，用一維的連續(xù)單元存放數(shù)組時(shí)，按存放次 序的不同有下列不同的存放形式：按行優(yōu)先順序存放元素aij的存儲(chǔ)地址為：Lo