1、1,作業(yè)： 1、簡述邏輯結構和存儲結構的聯系？ 2、數據結構和數據類型有什么區(qū)別？ 3、分析以下算法的時間復雜度 void func(int n) int i=0,s=0; while (sn) i+; s=s+i; ,2,2020/8/1,順序表算法設計練習：,已知一個順序表L，其中的元素遞增有序排列，設計一個算法插入一個元素x后保持該順序表仍遞增有序排列。,3,2020/8/1,參考算法：,Void insert (Sqlist ,4,2020/8/1,順序表算法設計練習：,試寫一個算法，實現順序表的就地逆置，即利用原表的存儲空間將線性表。（a1,a2,an）逆置為（an,an-1,a1）

2、。,5,2020/8/1,參考算法：,Void reverse (Sqlist ,6,2020/8/1,順序表算法設計練習：,試設計一個高效的算法，刪除線性表L中所有值為x的元素。,7,2020/8/1,參考算法：,Void deletelist (Sqlist ,8,2020/8/1,鏈表算法設計練習：,設計一個算法刪除帶頭結點的單鏈表L中值為x的結點的直接前驅結點。,9,2020/8/1,參考算法：,Int delx(Linklist ,10,2020/8/1,鏈表算法設計練習：,設計一個算法，在帶頭結點的單鏈表head中刪除一個data域值最小的結點，假設該結點唯一。,11,2020/8

3、/1,參考算法：,Void DelMinNode (Linklist head) Linklist p=head-next, pre=head; Linklist minp, minpre; Elemtype min=p-data; minp=p;minpre=pre; While (p!=NULL) I f (p-datadata) min=p-data; minp=p; minpre=pre; pre=p; p=p-next; minpre-next=minp-next; Free(minp); ,12,2020/8/1,1、假設表達式中允許包含3種括號：圓括號、方括號和大括號。設計一個算

4、法采用順序棧判斷表達式中的括號是否正確配對。 Int match (char exp, int n) char stMaxsize; int top=-1; int i=0,tag=1; while (in ,13,2020/8/1,2、假設用一個循環(huán)單鏈表表示隊列，并且只設一個指針rear指向隊尾結點，但不設頭指針，設計出相應的隊初始化、入隊算法。 Void initQu(Qnode * rear=s ,14,2020/8/1,作業(yè)： 1、設一系列正整數存放在一個數組中，試設計算法，將所有奇數存放在數組的前半部分，將所有的偶數放在數組的后半部分。要求盡可能少用臨時存儲單元并使時間最少。 2、

5、設計一個算法，計算一個三元組表表示的稀疏矩陣的對角線元素之和。,15,例：設樹T的度為4，其中度為1，2，3和4的結點個數分別為4，2，1，1 則T中的葉子數為（ ） A5 B6 C7 D8 提示：因為每個結點都有一條枝指向它，分支數為1*4+2*2+3*1+4*1所有結點數為分支數+1，所以1*4+2*2+3*1+4*1=4+2+1+1+x x=8 例：若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（ ） A9 B11 C15 D不確定 提示： n0=n2+1,16,例3：已知某二叉樹先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 畫出該二叉樹。

6、,17,例1：統(tǒng)計二叉樹中葉子結點的個數,Status CountLeaf (BiTree T, int ,18,例2：求二叉樹的深度,int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + max(depthLeft,depthRight); return depthval; ,19,例3：按先序序列建立二叉樹的二叉鏈表,已知先序序列：A B C 0 0 D E 0 G 0 0 F 0 0 0

7、（其中0表示空格字符, 空指針）建立相應的二叉鏈表,A,B,C,D,E,F,G,20,例：對于前序遍歷與中序遍歷結果相同的二叉樹（ ）; 對于前序遍歷和后序遍歷結果相同的二叉樹為（ ）。 A一般二叉樹 B只有根結點的二叉樹 C根結點無左孩子的二叉樹 D根結點無右孩子的二叉樹 E所有結點只有左子數的二叉樹 F所有結點只有右子樹的二叉樹 例：某二叉樹的前序序列和后序序列正好相反，則該二叉樹 一定是（）的二叉樹。 A空或只有一個結點 B任一結點無左子樹 C高度等于其結點數 D任一結點無右子樹,F,B,21,例： 一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈 域的個數是：( ) A不確定 B. 0

8、 C. 1 D. 2 例： 一棵左右子樹均不空的二叉樹在先序線索化后，其中空 的鏈域的個數是：( )。 A. 0 B. 1 C. 2 D. 不確定,左子樹為空的二叉樹的根結點的左線索為空（無前驅），先序序列的最后結點的右線索為空（無后繼），共2個空鏈域,只有最后一個葉結點沒有后繼,22,例： 線索二叉樹是一種（ ）結構。 A 邏輯 B 邏輯和存儲 C 物理 D線性 例：n個結點的線索二叉樹上含有的線索數為（ ） A2n Bn1 Cn1 Dn,N個結點共有2n個指針域，二叉鏈表用了n-1個，剩下n+1個,23,練習：寫出下圖所示樹的先序和后序遍歷序列并將之轉換成一棵二叉樹,先根遍歷：ABDEGH

9、ICF,后根遍歷：DGHIEBFCA,24,6.4.2 森林和二叉樹的轉換規(guī)則,設森林F=T1,T2,Tm，二叉樹B=（root，LB，RB） (1) 森林轉化成二叉樹的規(guī)則 若F為空(m = 0)，B為空; 若F不空(m0)，B的根root(B)是F中第一棵樹T1的根root (T1)； 左子樹LB從T1根結點的子樹森林 (T11, T12, , T1m)轉換來； 右子樹RB是從森林F=T2, T3, , Tm 轉換而來。 (2) 二叉樹轉換為森林的規(guī)則 若B為空， F為空； 若B非空，則F中第一棵樹T1的根為二叉樹的根root(B)； T1根的子樹森林F1由B的左子樹LB轉換而來； F 中

10、除 T1 外其余樹組成的森林F= T2, T3, , Tn 由B 的右子樹 RB 轉換而來。,25,森林轉換成二叉樹,步驟1：轉換將各棵樹分別轉換成二叉樹 步驟2：加線將每棵樹的根結點用線相連 步驟3：旋轉以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹,森林F,26,森林轉換成二叉樹,步驟1：轉換將各棵樹分別轉換成二叉樹 步驟2：加線將每棵樹的根結點用線相連 步驟3：旋轉以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹,E,F,G,H,I,J,森林F,27,森林轉換成二叉樹,步驟1：轉換將各棵樹分別轉換成二叉樹 步驟2：加線將每棵樹的根結點用線相連

11、 步驟3：旋轉以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹,E,F,G,H,I,J,森林F,F轉換的二叉樹B,28,二叉樹轉換成森林,步驟1：抹線將二叉樹根結點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成多棵二叉樹 步驟2：還原將孤立的二叉樹還原成樹,二叉樹B,29,二叉樹轉換成森林,步驟1：抹線將二叉樹根結點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成多棵二叉樹 步驟2：還原將孤立的二叉樹還原成樹,二叉樹B,30,二叉樹轉換成森林,步驟1：抹線將二叉樹根結點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成

12、多棵二叉樹 步驟2：還原將孤立的二叉樹還原成樹,A,B,C,D,E,F,G,H,I,J,二叉樹B,31,二叉樹轉換成森林,步驟1：抹線將二叉樹根結點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成多棵二叉樹 步驟2：還原將孤立的二叉樹還原成樹,B轉換成的森林F,二叉樹B,A,B,C,D,E,F,G,H,I,J,32,練習：寫出下圖所示森林的先序和中序遍歷序列并將之轉換成一棵二叉樹,先序遍歷：,中序遍歷：,ABCDEFIKJGH,BEFDCIAJGHK,33,例：設F是一個森林，B是由F變換得的二叉樹。若 中有n個非終端結點，則B中右指針域為空的結點有 （ ）個。 A n-1

13、Bn C n+1 D n+2,每一個非終端結點的孩子中都會貢獻出一個空的右指針,例：設F是由T1,T2,T3三棵樹組成的森林,與F對應的二叉樹為B,已知T1,T2,T3的結點數分別為n1,n2和n3則二叉樹B的左子樹中有 個結點，右子樹中有 個結點。,n1-1,n2+n3,34,構造最優(yōu)二叉樹的說明,1 在選取兩棵根結點權值為最小和次小的二叉樹時，如果出現權值相同的情況，可以在相同權值的二叉樹中任選一棵。 2 當兩棵根結點權值為最小和次小的二叉樹組成新的二叉樹的左右子樹時，誰是左子樹誰是右子樹沒有特殊規(guī)定。 3 在最優(yōu)二叉樹中沒有度為1的結點，根據二叉樹的性質3可知有n個葉子結點的二叉樹 有n

14、-1個非終端結點共有2*n-1個結點。,35,如何得到最短的二進制前綴碼（赫夫曼編碼）？ 為了設計電文總長最短的二進制前綴編碼，以n種字符出現的頻率作權，設計一棵赫夫曼樹，從根節(jié)點至即所有葉子節(jié)點，按左分支為0，右分支為1的原則即可得到最短二進制前綴編碼即赫夫曼編碼。 例：已知某系統(tǒng)在通信聯絡中只可能出現8種字符，其概率為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,設計赫夫曼編碼。 解：設權w=(5，29，7，8，14，23，3，11),36,編碼：3（0111） 5（0110） 7（1110） 8（1111） 11（010） 14（110） 23（00）

15、29（10）,37,練習： 用于通信的電文由 8 個字母 c1, c2, c3, c4, c5, c6, c7, c8 組成, 各字母在電文中出現的頻率分別為 5, 25, 3, 6, 10, 11, 36, 4。試 設計不等長 Huffman 編碼, 并給出該電文的總碼數。,0000 0001 001 0100 0101,011 10 11,電文總碼數=4*5+2*25+4*3+4*6+ 3*10+3*11+2*36+4*4= 257,38,2020/8/1,練習 （1）設無向圖的頂點個數為n，則該圖最多有（ ）條邊。 （2）一個有n個結點的圖，最少有（ ）個連通分量，最多有（ ）個連通分量

16、。 （3）在一個無向圖中，所有頂點的度數之和等于所有邊數的_倍。 （4）要連通具有n個頂點的有向圖，至少需要（ ）條邊。 （5）若無向圖G=（V，E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數最少是（ ）。,39,2020/8/1,無向圖,頂點的度：該頂點所在單鏈表中表結點個數,與頂點V1相鄰接的頂點在數組中的下標,40,2020/8/1,權值,無向網,41,2020/8/1,以頂點V1為始點的弧的終點頂點在數組中的下標,頂點的出度 該頂點所在單鏈表中表結點個數 頂點的入度 查詢整個鄰接表中的表結點，與該頂點的序號（數組 下標）一致的表結點個數,有向圖,42,2020/8/1

17、,圖的鄰接表表示,問題：具有n個頂點e條邊的無向圖的鄰接表中有多少個表頭結點？有多個表結點（邊結點）？,有向圖呢？,43,2020/8/1,練習: 請畫出下圖的鄰接矩陣和鄰接表,44,2020/8/1,7.3.1 深度優(yōu)先搜索-舉例,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,給定存儲結構，圖的遍歷序列唯一,45,2020/8/1,7.3.2 廣度優(yōu)先搜索-舉例,廣度遍歷：V1 V3 V2 V7 V6 V5 V4 V8,給定存儲結構，圖的遍歷序列唯一,46,2020/8/1,下列有關圖遍歷的說法中不正確的是（） A連通圖的深度優(yōu)先搜索是一個遞歸過程 B圖的廣度優(yōu)先搜索

18、中鄰接點的尋找具有“先進先出”的特征 C. 圖的遍歷要求每一頂點僅被訪問一次 D對圖進行一次深度優(yōu)先遍歷可以訪問圖中所有頂點,47,2020/8/1,給定有向圖如下：,給出其鄰接表存儲結構 基于鄰接表，給出DFS序列和BFS序列,48,2020/8/1,練習：,已知一個圖的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。,【答】用克

19、魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20,49,2020/8/1,練習：,設有無向圖G，要求給出用普里姆算法構造最小生成樹所走過的邊的集合。,【答】E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4),50,2020/8/1,7.5.1 拓撲排序-實現步驟,C1,C3,C2,C7,C5,C6,C4,拓撲有序序列：,邏輯結構上：拓撲序列不唯一,51,2020/8/1,7.5.2 關鍵路徑,AOE-網(Active On Edge)：在帶權的有向無環(huán)圖中，頂點表示事件，弧表示工程的一個活動，弧上權值

20、表示活動持續(xù)的時間。用來估算工程完成時間。 源點：入度為0的頂點。匯點：出度為0的頂點。 路徑長度：AOE網中路徑上各活動持續(xù)時間之和。 關鍵路徑：路徑長度最長的路徑。,說明： （1）完成工程的最短時間是從開始點到完成點的最長路徑的長度。 （2）關鍵路徑的改變會影響整個工期。,52,2020/8/1,設活動ai在有向無環(huán)圖G的有向邊上： 事件vj的最早發(fā)生時間ve(j):從源點v0到vj的最長路徑長度。 ve(0)=0; ve(j)=從源點到頂點j的最長的路徑長度。 ve(k)=Maxve(j)+dut() 事件vj的最遲開始時間vl(j)：保證匯點vn-1在ve(n-1)時刻完成的前提下，事

21、件vj最遲允許開始的時間。 vl(n-1) = ve(n-1)從源點到匯點的最長路徑長度; vl(k)=從匯點到頂點k的最短的路徑長度。 vl(j)=Minvl(k)-dut(),7.5.2 關鍵路徑定義和術語,53,2020/8/1,7.5.2 關鍵路徑定義和術語,設活動ai在有向邊上,有： 活動ai的最早開始時間e(i)：從源點v0到vj的最長路徑長度。 e(i)= ve(j); 活動ai的最遲開始時間l(i)：是不推遲工程完成的前提下，該活動允許的最遲開始時間。 l(i)=vl(k)-dut() 活動ai時間余量：l(i)-e(i) 關鍵活動：滿足l(i)=e(i)的活動。關鍵路徑上的活

22、動都是關鍵活動。,54,2020/8/1,7.5.2 關鍵路徑求關鍵活動,求頂點（事件）vk的最早開始時間：從ve(0)=0向匯點方向遞推 求頂點（事件）vj的最遲開始時間：從vl(n-1)=ve(n-1)向源點遞推,ve(k)=Maxve(j)+dut(),vl(j)=Minvl(k)-dut(),在拓撲有序的前提下進行,在逆拓撲有序前提下進行,55,2020/8/1,18,14,16,10,7,8,6,6,0,vl(i),18,14,16,7,7,5,4,6,0,ve(i),V9,V8,V7,V6,V5,V4,V3,V2,V1,i,關鍵路徑是V1 ,V2, V5, V7, V9和V1 ,V

23、2 ,V5 ,V8 ,V9,ve(k) = Maxve(j)+dut() vl(j)=Minvl(k)-dut(),e(i) = ve(j); l(i) = vl(k) dut(),14,16,10,7,7,8,6,6,3,2,0,l(i),0,0,0,0,0,0,差,14,16,7,7,7,5,4,6,0,0,0,e(i),a11,a10,a9,a8,a7,a6,a5,a4,a3,a2,a1,注意：關鍵路徑可有多條。 縮短工期必須縮短關鍵活動所需的時間,56,2020/8/1,如何求關鍵路徑？(算法思想) （1）輸入e條弧，建立AOE網的存儲結構； （2）從源點v0出發(fā)，令ve0=0，按拓撲

24、有序求其余各頂點的最早發(fā)生時間vei(1in-1)。如果得到的拓撲有序序列中頂點個數小于網中頂點數n，則說明網中存在環(huán)，不能求關鍵路徑，算法終止，否則執(zhí)行步驟（3）； （3）從匯點vn出發(fā)，令vln-1=ven-1，按逆拓撲有序求余各頂點的最遲發(fā)生時間vli (n-2i2) （4）根據各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s).若某條弧滿足條件e(s)=l(s),則為關鍵活動。,57,2020/8/1,下列關于AOE網的敘述中，不正確的是（ ） A.關鍵活動不按期完成就會影響整個工程的完 成時間 B.某些關鍵活動提前完成，那么整個工程將會 提前完成 C.所有的

25、關鍵活動提前完成，那么整個工程將 會提前完成 D.任何一個關鍵活動提前完成，那么整個工程 將會提前完成,58,2020/8/1,9.2.1 二叉排序樹,二叉排序樹(二叉查找樹）(Binary Sort Tree, BST)：空樹或具 有下列性質的二叉樹: 根的左子樹若非空，則左子樹上的所有結點的關鍵字值均小于根結點的值。 根的右子樹若非空，則右子樹上的所有結點的關鍵字值均大于根結點的值。 它的左右子樹同樣是二叉排序樹。 中序遍歷二叉排序樹可得到一個關鍵字的有序序列,59,2020/8/1,9.2.1 二叉排序樹的插入,例：序列45、24、53、12、90構成一棵二叉排序樹 建BST樹過程： 一

26、個無序序列可以構造二叉排序樹 前提：查找失敗 插入的結點是一個葉子結點， 且是查找失敗時查找路徑上訪問的 最后一個結點的左孩子或右孩子。 插入算法： 二叉排序樹的存儲結構使用鏈表 首先執(zhí)行查找算法，找出被插入結點的父親結點。 若二叉樹為空。則首先單獨生成根結點。 判斷被插結點是其父親結點的左、右孩子。將結點插入,45,53,90,24,12,60,2020/8/1,9.2.1 二叉排序樹-刪除,設二叉排序樹上被刪除結點是p ，PL是p的左子樹，PR是p的右子樹，p的雙親結點是f，不失一般性，設p是f的左孩子。有三種情況： 被刪除的結點p是葉子結點； 被刪除的結點p只有左子樹或者只有右子樹； 被

27、刪除的結點既有左子樹，也有右子樹。 對二叉排序樹，刪去一個結點相當于刪去有序序列中的一個記錄。,61,2020/8/1,9.2.1 二叉排序樹-刪除,1） 被刪除的結點p是葉子結點：修改雙親結點的指針，令 f-lchild=NULL,例：刪除葉子結點12,62,2020/8/1,9.2.1 二叉排序樹-刪除,2） 被刪除的結點p只有左子樹或者只有右子樹：令PL或PR直接為其雙親結點f的左子樹即可，f-lchild=p-lchild|p-rchild。,例：刪除結點24,63,2020/8/1,9.2.1 二叉排序樹-刪除,3）被刪除的結點既有左子樹，也有右子樹。在刪去p結點前，中序遍歷該二叉樹

28、得到的序列為CLCQLQSLSPPRF，即S是中序遍歷序列中被刪結點p的直接前驅結點。 方法一：令P的左子樹為F的左子樹，P的右子樹為S的右子樹,64,2020/8/1,9.2.1 二叉排序樹-刪除,3）被刪除的結點既有左子樹，也有右子樹。在刪去p結點前，中序遍歷該二叉樹得到的序列為CLCQLQSLSPPRF，即S是中序遍歷序列中被刪結點p的直接前驅結點。 方法二：令p的直接前驅S替代p，再從二叉排序樹中刪去S。,65,2020/8/1,9.2.1 二叉排序樹-刪除舉例,刪除45,45,12,37,3,24,66,2020/8/1,9.2.1 二叉排序樹-刪除舉例,刪除45,45,12,3,2

29、4,53,100,61,90,78,37,67,2020/8/1,練習： 假定一棵二叉排序樹采用二叉鏈表存儲結構，其根結點指針為T,設計一個算法輸出該二叉排序樹中最大的鍵值和最小的鍵值。,68,2020/8/1,status maxmindata() if (!T ) return error; p=q=T; while (p-lchild!=NULL) p=p-lchild; printf(“The minimum data is:%d”, p-data); while (q-rchild!=NULL) q=q-rchild; printf(“The minimum data is:%d”,

30、 q-data); ,69,2020/8/1,9.3 哈希表,查找表的特點： 記錄的關鍵字和在結構中的位置之間無確定關系 查找過程是給定值依次和關鍵字集合中各個關鍵字的比較 查找效率取決于和給定值進行比較的關鍵字個數。 希望不經比較，直接可以找到所查記錄 哈希函數：在記錄的關鍵字和其在表中位置之間建立一種 函數關系，即以f(key)作為關鍵字為key的記錄在表中的位 置。,70,2020/8/1,9.3 哈希表定義和術語,沖突：不同關鍵字得到同一哈希地址，key1key2， f(key1)=f(key2) 同義詞：在一個哈希函數中具有相同函數值的不同關鍵字。 哈希表：根據設定的哈希函數H(ke

31、y)和所選中的處理沖突的方 法，將一組關鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū) 間)上，并以關鍵字在地址集中的“象”作為相應記錄在表中的存 儲位置，這種表被稱為哈希表。 哈希造表或散列：映象過程。 哈希地址或散列地址：所得的存儲位置。 構造哈希表要注意的問題： 考慮選擇一個“好”的哈希函數; 選擇一種處理沖突的方法。,71,2020/8/1,9.3.3 處理沖突的方法,1 開放定址法：Hi=(H(key)+di) MOD m i=1,2,k (km-1)，H(key)為哈希函數；m：哈希表長，di是增量序列， 有三種取法 di=1,2,m-1，稱為線性探測再散列 di=12,-12,22,

32、-22,k2 (km/2)稱為二次探測再散列 di=偽隨機數列，稱為隨機探測再散列,72,2020/8/1,處理沖突方法舉例,例：一組關鍵字19,14,23,01,68,20,84,27,55,11,10,79；按 H(key)=key mod 13和線性探測再散列方法處理沖突構造表長 為16的哈希表。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,3,1,1,9,3,1,1,3,4,1,2,1,比較次數,2,0,0,8,2,0,0,2,3,0,1,0,沖突次數,ASLss=1/12（1*6+2+3*3+4+9）=2.5,14,01,68,27,55,19,20,

33、84,79,23,11,10,73,2020/8/1,9.3.3 處理沖突的方法,例：用哈希函數H(key)=key MOD 13和鏈地址法處理沖突求一組關鍵字19,14,23,01,68,20,84,27,55,11,10,79的哈希表：,ASLss=1/12(1*6+2*4+3+4)=1.75,74,2020/8/1,練習：,已知關鍵字序列為：（75,33,52,41,12,88,66,27），哈希表長為10，哈希函數為：H(k)k%9，解決沖突用線性探測法，請： （1）構造出哈希表； （2）計算等概率下查找成功的平均查找長度。,75,2020/8/1,Typedef struct LNo

34、de ElemType data; / 數據域 struct Lnode *next; / 指針域 LNode, *LinkList;,二、結點和單鏈表的 C 語言描述,LinkList L； / L 為單鏈表的頭指針,76,2020/8/1,Typedef struct LNode ElemType data; / 數據域 struct Lnode *next; / 指針域 LNode, *LinkList;,二、結點和單鏈表的 C 語言描述,LinkList L； / L 為單鏈表的頭指針,77,2020/8/1,三、單鏈表操作的實現,GetElem(L, i, j = 1; / p指向第

35、一個結點，j為計數器,while (p / 順指針向后查找，直到 p 指向第 i 個元素 / 或 p 為空,if ( !p | ji ) return ERROR; / 第 i 個元素不存在 e = p-data; / 取得第 i 個元素 return OK;,81,2020/8/1,線性表的操作 ListInsert( j = 0; while (p / i 大于表長或者小于1,84,2020/8/1,s = (LinkList) malloc ( sizeof (LNode); / 生成新結點 s-data = e; s-next = p-next; p-next = s; / 插入 re

36、turn OK;,s,p,85,2020/8/1,線性表的操作ListDelete ( p-next = q-next; e = q-data; free(q);,p,q,87,2020/8/1,Status ListDelete_L(LinkList L, int i, ElemType j = 0; while (p-next / 刪除位置不合理,q = p-next; p-next = q-next; / 刪除并釋放結點 e = q-data; free(q); return OK;,88,2020/8/1,操作 ClearList(,算法時間復雜度：,O(ListLength(L),8

37、9,2020/8/1,逆位序輸入 n 個數據元素的值，建立帶頭結點的單鏈表。,操作步驟：,一、建立一個“空表”；,二、輸入數據元素an， 建立結點并插入；,三、輸入數據元素an-1， 建立結點并插入；,an,an,an-1,四、依次類推，直至輸入a1為止。,90,2020/8/1,void CreateList_L(LinkList L-next = NULL; / 先建立一個帶頭結點的單鏈表,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf( / 插入 ,91,2020/8/1,時間復雜度為O（La.lengt

38、h+Lb.length）。,兩個有序線性表合并為一個有序線性表的算法：,void MergeList_L(LinkList ,92,2020/8/1,5.3.2 稀疏矩陣,稀疏矩陣：設m行n列的矩陣含t個非零元素，則=t/(m*n)稱為稀疏因子，通常認為 0.05 的矩陣為稀疏矩陣。 抽象數據類型稀疏矩陣的定義：書96頁 稀疏矩陣的壓縮存儲 稀疏矩陣中非零元素位置無規(guī)律 記住非零元素的行i，列j，值aij 稀疏矩陣中存在多個非零元素,三元組的C語言描述 typedef struct int i,j; ElemType e; Triple,三元組順序表的C語言描述 #define MAXSIZE

39、 125000 typedef struct Triple dataMAXSIZE+1; int mu,nu,tu;TSMatrix,93,2020/8/1,三元組表表示的稀疏矩陣的轉置,設M和T分別是MM和TT的三元組表，如何由M得到T？ 將矩陣行列值(即m和n)相互交換 將每個三元組中的i和j對換 重排三元組的次序,94,2020/8/1,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,三元組表表示的稀疏矩陣轉置算法1,評價：O(nu*tu)， 優(yōu)點:節(jié)省空間， tumu*nu適用,95,2020/8/1,三元組表

40、表示的稀疏矩陣轉置方法2,思想：按M.data的三元組次序轉置，再將三元組置入T中適當的位置。 問題：轉置前需知MM的每列中非零元素個數及第一個非零元素在T.data中的位置。 解決方案：設num和cpot兩個向量， numcol：矩陣MM的第col列中非零元素的個數， cpotcol: 矩陣MM第col列第一個非零元在T.data中的位置,cpot1=1;,cpotcol=cpotcol-1+numcol-1 (2=col=M.nu),Status FastTransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix時間復雜度為O(nu+tu),若tumu*nu 則為O(mu*nu)，與經典算法相同，多用了兩個輔助向量。,三元組表表示的稀疏矩陣轉置方法2,97,2020/8/1,稀疏矩陣的壓縮存儲行邏輯鏈接順序表,需求：隨機存取任一行的非0元 方法：記住矩陣每一行第一個非0元在三元組表中的位置 設數組rpos1.n:矩陣中的每行第一個非零元素的起始位置。 rpos1=1; rposrow=rposrow-1+第row-1行的非零元素個數 行邏輯鏈接順序表:在稀疏矩陣存儲結構中固定指示行信息的輔助數