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

1、第二章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2.1程序=算法+數(shù)據(jù)結(jié)構(gòu)也就是說，計算機按照程序所描述的算法對某種結(jié)構(gòu)的數(shù)據(jù)進行加工處理。.數(shù)據(jù)結(jié)構(gòu)數(shù) 據(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ù)是相對而言的（如一條記錄相 對于所在文件被認為是數(shù)據(jù)元素，而它相對于所含的數(shù)據(jù)項又被認為是數(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、存儲器中的存儲形式。r線性結(jié)構(gòu)：每個結(jié)點有且只有一個前驅(qū)結(jié)點和一個后繼結(jié)點（第一和最后一個結(jié)點除外）（邏輯結(jié)M樹型結(jié)構(gòu)：每個結(jié)點有且只有一個前驅(qū)結(jié)點（樹根結(jié)點除非線性結(jié)時外），但可以有任意多個后繼結(jié)點。圖型結(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ù)的存儲空間，當數(shù)據(jù)元素的數(shù)目不確定時，會造成存儲空間的閑置。鏈接存儲結(jié)構(gòu)：為數(shù)據(jù)結(jié)構(gòu)的每個結(jié)點元素附加一個數(shù)據(jù)項，其中存放一個與其相鄰接的元素的地址（指針），通過指針找到下一個，相關(guān)元素的實際存儲地址。每個

3、結(jié)點由數(shù)據(jù)域和指針域組成。,存儲結(jié)構(gòu)其存儲空間不必連續(xù)，在進行插入、刪除操作時不必移動結(jié)點，但結(jié)點指針要占用額外的存儲空間。索引存儲結(jié)構(gòu)：將全部記錄分別存放在存儲器的不同位置，系統(tǒng)為整個 記錄建立一張索引表，表中登記了每條記錄的長度、邏輯記錄 號和在存儲器中位置。通過索引表來訪問記錄。（散列存儲結(jié)構(gòu)：在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對讀取棧 頂元素只要將棧頂元素賦 給指定變參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è)置一 個空棧只要把棧頂指針置0 即可。Procedure setnull (s,top);Begintop:=0 end;若不考慮回收結(jié)點， 只要將HS置空即可, 若考慮回收鏈棧中 的所有結(jié)點，算法如 右。Procedure setnull (HS)； BeginWhile HSnil do p:=HS;HS:二HS t . next;Dispose(p)End;判斷一 個棧是 否為空可用一個函數(shù)來描 述，?？諘r返回

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

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

7、賦給隊尾元素；4）若原隊為空隊，則進行插入后，同時把隊首 指針置為1。Procedure insert (q,x,front, rear);BeginIf rear=m Then error (overflow)Rear:=rear+l;qrear:=x;if front=0 then front:=1end;刪除隊頭 元素，即出 隊1）檢查隊是否為空，若空，則進行錯誤處理；2）將隊首元素賦給指定變參y;3）若刪除后隊空，將隊首和隊尾指針置0,否則 將隊首指針后移。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è)置一個 空隊只要把隊首和隊尾指針均賦0即可。Procedure setnull (q, front, rear);Beginfront:=0； rear:=0 end;（4） 應(yīng)用運算種類鏈隊算法步驟算法描述插入一個 新的隊尾 元素,即進隊1）為待入隊兀素x分配 個結(jié)點P t , 并把x賦給P t結(jié)點的值域，nil賦 給Pt結(jié)點的指針域；2）若鏈隊為空，則表明待插入Pt的結(jié) 點既是隊首結(jié)點也是隊尾結(jié)點，否則 把Pt結(jié)點插入隊尾，并使隊尾指針

9、指向Pt結(jié)點。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;刪除隊頭 元素，即出隊1）若鏈隊為空，則進行錯誤處理；2）將隊首結(jié)點的值賦給變參；3）把隊首指針暫存指針變量p,以便回 收該結(jié)點；4）刪除隊首結(jié)點，即若鏈隊中只有一個 結(jié)點（即fron t=rear）,則應(yīng)同時把 front和rear置空，否則只修改隊首 指針，使之成為下一個結(jié)點；5）回

10、收原隊首結(jié)點，即Pt結(jié)點。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è)置一個 空隊只要把隊首和隊尾指針置空即可。Procedure setnull(hq, front, rear)；BeginFront： =nil； rear： =nilEnd;劃分子集問題離散事件仿真.

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

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

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

14、程。遍歷一棵非空二叉樹的問題可分解為三個子問題：訪問根結(jié)點、遍歷左子樹、遍歷右子樹。相應(yīng)的二叉樹的遍歷方案有六種：DLR、LDR、LRD、DRL、RDL、RLD。遍歷方案算法（均為遞歸算法）.運算結(jié)果代號名稱DLR前序遍歷或先根遍歷Procedure preorder (bt)；BeginIf btnil thenwrite (bt t . data) ;訪問根結(jié)點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é)點inorder (bt t . right) ; 中序遍歷右子樹 end;LRD后序遍歷或后根遍歷Procedure postorder (bt)；BeginIf btnil theninorder (bt t . left) ; 后序遍歷左子樹 inorder (bt t . right) ; 后序遍歷右子樹 write (bt t . data) ;訪問根結(jié)點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)系可以是任意的,圖中任意兩個元素之間可以相聯(lián)結(jié)。圖的定義：圖G是由兩個集合V (G)和E (G)組成的，記為：G = (V, E)其中V (G)是頂點的非空有限集合E (G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)?。有向圖G：即在圖G中，E (G)是有向邊，邊是頂點的有序?qū)?，記為V,W。無向圖G：即在圖G中，E (G)是無向邊，邊是頂點的無序?qū)?，?/p>

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

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

20、檢索：也稱查找，是根據(jù)給定的某個值，在表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元 素。它不是一種數(shù)據(jù)結(jié)構(gòu)，而是一種輔助性運算。平均查找長度ASL：為確定記錄在表中的位置所進行的和關(guān)鍵字比較的次數(shù)的期望值，是衡量一個查找算法好壞的依據(jù)。X n為表中元素總數(shù)，Pi為查表中第i個元素的概率，Ci為找到第i個元素所需的比較次數(shù)。.常用檢索方法名稱檢索方式算法區(qū)別性索 線檢法從表的第一個元素開始，將給定的 值與表中逐個元素的關(guā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;對表結(jié)構(gòu)為有序表、無序 表均可適用；對存儲結(jié)構(gòu)為向量和線性 鏈表均適用；平均查找長度最大，ASL= (n+1) /2；適合于短表，方法簡單；不適合長表，檢索起來太 慢。半索 對檢法首先選擇表中間的一個記錄，比較 其關(guān)鍵字的值，若要找的記錄的關(guā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;要求表中元素是逐段有序 的；對存儲結(jié)構(gòu)為向量和線性 鏈表的均適用；平均查找長度比線性檢

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

24、個關(guān)鍵字 大于它的元素對換，依次類推，直到整個 表按其關(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ū)⒁粋€表看成由已排好序的和未排好序 的兩個部分組成，依次將未排好序部分的 元素逐個通過線性比較插入到已排好序 部分的應(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;歸并排序即將兩個或兩個以上的有序表

26、組合成一個新的有序表。先將n數(shù)據(jù)看成n個長度為1的表，將相 鄰的表成對歸并，得到長度為2的有序表，再將相鄰表成對歸并成長度為4的有序表，依次做下 去，直到所有數(shù)據(jù)均合并到一個長度為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=l）, 線性結(jié)構(gòu)（1:1）是樹型結(jié)構(gòu)（1:N）的特例（N=1）。一種數(shù)據(jù)結(jié)構(gòu)可以表示成一種或多種物理結(jié)構(gòu)。在數(shù)據(jù)處理過程中，一個恰當?shù)臄?shù)據(jù)結(jié)構(gòu) 起著非常重要的作用。2.算法算 法：即解決特定問題的方法。L數(shù)值算法：是解決數(shù)值問題的算法，

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

28、指一個算法在計算機上運算所花費的時間占用的存儲空間（空間復(fù)雜性）：指一個算法在計算機存儲器中所占用的存儲空間 I簡單性：指容易驗證其正確性，且便于編寫、修改、閱讀和調(diào)試Pascal語言簡介整型 integer整型 integer一個整型數(shù)據(jù)占用2個字節(jié)的存儲單元實型real簡單類型|字符型charI布爾型boolean一個實型數(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)

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

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

31、 range)此處 n =7 i=4國 ELSE FOR j:=i TO n-1 DO刪除vj:=vj+l;胡 n:=n-l 1# 2# 3# 4# 5# 6# 7#END;單鏈表的插入例題：*向單鏈表中第i個結(jié)點（i20）之后插入一個元素為b的結(jié)點*算法步驟：1）為待插入元素b分配一個結(jié)點（假定是由s指針變量所指向的結(jié)點，即st結(jié)點），并把 b賦給s t結(jié)點的值域；2）如果i=0,則將st結(jié)點插入表頭后返回；3）從單鏈表中查找第i個結(jié)點；4）若查找成功,則在第i個結(jié)點后插入s t結(jié)點否則表明值超出單鏈表的長度,應(yīng)進行 錯誤處理。插入前 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個結(jié)點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é)點的指針域指向p t結(jié)點的后繼p t . next:二s；使pt結(jié)點的指針域指向s t結(jié)點ELSE error ( error，) END;單鏈表的刪除例題：*在單鏈表中刪除結(jié)點d *算法步驟：1）如果單鏈表為空，則進行出錯處理；2）如果表頭結(jié)點是被刪除結(jié)點，則刪除該結(jié)點后返回；3）從單鏈表中查找其值等于d的結(jié)點，直到查找結(jié)束（成功或失?。橹?4）若查找成功，則刪除被查找到的結(jié)點后，否則進行錯誤處理。刪除前 head12 3 ； 4cEdAGBF3726015datanext5 6.7刪除前刪除后97CPROCEDURE delete (head, d)BEGINflj|

34、IF head=nil THEN error C this is a empty list，)；團 IF head t . data =d THENP：二head；把表頭指針賦給P,以便刪除表頭結(jié)點后收回該結(jié)點head:二head t . next； 刪除表頭結(jié)點dispose (p) ；系統(tǒng)回收由p所指向的結(jié)點，即原表頭結(jié)點RETURN ；返回叵q:=head； p:=q t.next ； P指向待比較的結(jié)點，q指向p的前驅(qū)結(jié)點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é)點，即值為d的結(jié)點dispose(p) ；回收 p 結(jié)點ELSE error error，)END;結(jié)論：在表很長時，采用順序方式時插入和刪除元素的效率很低，只有在很少進行插入和刪除 運算的情況下，采用順序表才是合適的。而線性鏈表的插入和刪除運算效率總是很高， 與表長無關(guān)。.線性表的應(yīng)用線性表是應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu)。常見的有：高級語言中的數(shù)組操作系統(tǒng)中的文件系統(tǒng)、目錄系統(tǒng)事務(wù)管理中的表格.3數(shù)組.數(shù)組的概念數(shù)組：按一定格式排列起來的一列同一屬性的項目。有一維數(shù)組、二維數(shù)組、三維數(shù)組等。二維數(shù)組：每一行都是一個線性表，每一個數(shù)據(jù)元素既在一個行表中，又在一個列表中。.數(shù)組的存儲結(jié)構(gòu)計算機中的存儲單元是一維結(jié)構(gòu)，數(shù)組是多維結(jié)構(gòu)，用一維的連續(xù)單元存放數(shù)組時，按存放次 序的不同有下列不同的存放形式：按行優(yōu)先順序存放元素aij的存儲地址為：Lo