【文章內(nèi)容簡介】 llist, PNode p, DataType x) { /*在 llist帶頭結(jié)點的單鏈表中 ,p所指結(jié)點后面插入元素 x */ PNode q = (PNode)malloc(sizeof( struct Node))。 /*申請新結(jié)點 */ if ( q == NULL ) { printf(Out of space!!!\n)。 return(0)。 } else { qinfo = x。 qlink = plink。 plink = q。 return(1)。 } } 5. 在某結(jié)點前插入新節(jié)點 int insertPre_link(LinkList llist, PNode p, DataType x) 在結(jié)點 p前面插入值為ｘ的新結(jié)點 1) 先找到結(jié)點 p的前驅(qū) (locatePre_link) 2) 在 p的前驅(qū)之后插入新結(jié)點 2022/1/4 49/114 2022/1/4 50/114 PNode locatePre_link(LinkList llist, PNode p) { /*在單鏈表中求 p所指結(jié)點的前驅(qū)結(jié)點 */ PNode p1。 if (llist==NULL) return(NULL)。 p1 = llist。 while( p1 != NULL amp。amp。 p1link != p ) p1 = p1link。 return (p1)。 } int deleteV_link(LinkList llist, DataType x) 刪除第一個元素值為 x的結(jié)點，并返回刪除成功與否的標志 從第一個結(jié)點開始查找第一個元素值為 x的結(jié)點 刪除該結(jié)點 (修改指針 ) 需記錄其前驅(qū)結(jié)點 2022/1/4 51/114 p a b c plink=plinklink。 2022/1/4 52/114 int deleteV_link( LinkList llist, DataType x ) { /*在 llist帶有頭結(jié)點的單鏈表中刪除第一個值為 x的結(jié)點 */ PNode p, q。 p = llist。 if (p==NULL) return(0)。 while ( plink != NULL amp。amp。 plinkinfo != x ) p = plink。 /*找值為 x的結(jié)點的前驅(qū)結(jié)點的存儲位置 */ if ( plink == NULL ) { /*沒找到值為 x的結(jié)點 */ printf(Not exist!\n)。 return 1。 } else { q = plink。 /*找到值為 x的結(jié)點 */ plink = qlink。 /*刪除該結(jié)點 */ free( q )。 return 1。 } } 7. 單鏈表中按位置刪除元素 int deleteP_link(LinkList llist, PNode p) 刪除鏈表中的結(jié)點 p ，并返回刪除成功與否的標志。 先調(diào) 用 locatePre_link(llist, p )找到 p所指結(jié)點的前驅(qū)結(jié)點 然后實現(xiàn)結(jié)點刪除。 2022/1/4 53/114 單鏈表 (n個結(jié)點 )的結(jié)點查找 最壞情況下要查找 n個結(jié)點，平均情況下需要查找 n/2個結(jié)點，因此時間復雜度為 O(n) 其它操作的時間復雜度？ 分析與比較 2022/1/4 54/114 優(yōu)點 : 不要預先按最大的需要分配連續(xù)空間； 線性表的插入和刪除只需修改指針域，而不需移動其他元素。 缺點： 每個結(jié)點中的指針域需額外占用存儲空間，存儲密度?。? 鏈式存儲結(jié)構(gòu)是一種非隨機存儲結(jié)構(gòu)，查找任一結(jié)點都要從頭指針開始，沿指針域一個一個地搜索，這增加了有些算法的時間代價。 小結(jié)：鏈接表示的優(yōu)缺點 2022/1/4 55/114 1. 循環(huán)鏈表 單鏈表：最后一個結(jié)點的指針為 NULL 循環(huán)鏈表：最后一個結(jié)點的指針指向頭一個結(jié)點 優(yōu)點：從循環(huán)鏈表中任一結(jié)點出發(fā)，都能訪問遍所有結(jié)點 單鏈表的改進和擴充 2022/1/4 56/114 2. 雙鏈表 單鏈表：找到某結(jié)點的前驅(qū)比較困難 雙鏈表：每個結(jié)點有兩個指針域：一個指向前驅(qū)，一個指向后繼 2022/1/4 57/114 2. 雙鏈表 – cont. 雙鏈表及其結(jié)點的定義： 2022/1/4 58/114 struct DoubleNode。 /*雙鏈表結(jié)點 */ typedef struct DoubleNode * PDoubleNode。 /*結(jié)點指針類型 */ struct DoubleNode { /*雙鏈表結(jié)點結(jié)構(gòu) */ DataType info。 PDoubleNode llink, rlink。 }。 struct DoubleList { /*雙鏈表類型 */ PDoubleNode head。 /*指向第一個結(jié)點 */ PDoubleNode rear。 /*指向最后一個結(jié)點 */ }。 2. 雙鏈表 – cont. 雙鏈表中，刪除指針變量 p所指的結(jié)點： pllinkrlink = prlink。 prlinkllink = pllink。 free(p)。 2022/1/4 59/114 2. 雙鏈表 – cont. 雙鏈表中，在 p所指結(jié)點后插入一個新結(jié)點： q = (PDoubleNode)malloc(sizeof(struct DoubleNode))。 qllink = p。 qrlink = prlink。 prlinkllink = q。 prlink = q。 2022/1/4 60/114 3. 循環(huán)雙鏈表 雙鏈表 +循環(huán)鏈表 頭結(jié)點由頭指針 cdlist指出，并鏈接在頭結(jié)點和尾結(jié)點之間 2022/1/4 61/114 基本概 念與 ADT 順序表示 鏈接表示 應用舉例 矩陣 廣義表與動態(tài)存儲管理 2022/1/4 62/114 問題描述： 設有 n個人圍坐在一個圓桌周圍，現(xiàn)從第 s個人開始報數(shù)，數(shù)到第m的人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第 m的人又出列， … ，如此反復直到所有的人全部出列為止。 Josephus問題： 對于任意給定的 n, s和 m，求出按出列次序得到的 n個人員的序列 Josephus問題 2022/1/4 63/114 2022/1/4 64/114 以 n=8， s=1， m=4為例 (a) n4 (b) n4n8 (c) n4n8n5 (d) n4n8n5n2 2022/1/4 65/114 (e) n4n8n5n2n1 (f) n4n8n5n2n1n3 (g) n4n8n5n2n1n3n7 (h) n4n8n5n2n1n3n7n6 求解 Josephus問題的一般步驟： (1) 利用線性表的一些運算 構(gòu)造 Josephus表 。 如：創(chuàng)建空線性表、插入元素等 (2) 從 Josephus表中的第 s個結(jié)點開始 尋找、輸出和刪除 表中的第m個結(jié)點，然后再從該結(jié)點后的下一結(jié)點開始尋找、輸出和刪除表中的第 m個結(jié)點，重復此過程，直到 Josephus表中的所有元素都刪除。 2022/1/4 66/114 主要步驟： (1) 將整數(shù)序列 (1， 2， 3， … ， n)存儲在一 個 palist所指順序表中 用整數(shù) i來代替 ni (2) 最初從第 s個人開始 (即 palistelement[s1])，則第一個報數(shù)出列的元素編號應為： (s1+m1) % n(設該編號為 i) 是否 s ≤ n對程序并不影響 (3) 輸出元 素 palistelement[i]，并將該元素從順序表中刪除 (4) 繼續(xù)在新的順序表中進行以上 (2)、 (3)操作，直至順序表為空為止 相關(guān)代碼： 采用順序表模擬 2022/1/4 67/114 2022/1/4 68/114 include include include “ void josephus_seq(PSeqList palist, int s, int m) { int s1, i, w。 s1 = s 1。 for(i = palistn。 i0。 i) { /*找出列的元素 */ s1 = (s1 + m 1) % i 。 w = palistelement[s1]。 /*求下標為 s1的元素的值 */ printf(Out element %d \n, w)。 /*元素出列 */ deleteP_seq(palist,s1)。 /*刪除出列的元素 */ } } 2022/1/4 69/114 void main() { int i, n, s, m。 printf(\n please input the values(100) of n = )。 scanf(%d,amp。n)。 printf( please input the values of s = )。 scanf(%d,amp。s)。 printf( please input the values of m = )。 scanf(%d,amp。m)。 PSeqList jos_alist=createNullList_seq( n )。 /*創(chuàng)建空順序表 */ if (jos_alist!=NULL) { for( i = 0。 i n。 i++ ) /*線性表賦值 */ insertPre_seq( jos_alist, i, i+1