【正文】 M*2)。 return 0。 free(palistelement)。 palistMAXNUM *=2?，F(xiàn)在要求一個(gè)新 集合 A=AUB 思路： 從線性表 B中依次取得每個(gè)元素： retrieve_seq(pblist, p) ? x 在線 性表 A中 查找 x： locate_seq(palist, x ) 若不存在則插入到表最后： insertPost_seq( palist, palistn1, x ) 思考：線性表應(yīng)用舉例 2022/1/4 34/114 (2) 求順序表中第一個(gè)值為 x的元素的前驅(qū)和后繼的位置 (3) 合并有序 (非遞減順序 )線 性表 A和 B，合并后的線性表 C也具有同樣的特性 2022/1/4 35/114 優(yōu)點(diǎn)： 邏輯相鄰，物理相鄰 存儲空間使用緊湊 可隨機(jī)存取任一元素 缺點(diǎn)： 插入、刪除操作需要移動(dòng)大量的元素 預(yù)先分配空間需按最大空間分配，利用不充分 表容量難以擴(kuò)充 小結(jié)：線性表示的優(yōu)缺點(diǎn) 2022/1/4 36/114 基本概 念與 ADT 順序表示 鏈接表示 應(yīng)用舉例 矩陣 廣義表與動(dòng)態(tài)存儲管理 2022/1/4 37/114 特點(diǎn)： 邏輯相鄰但物理不相鄰 增加指針來指示其后繼 鏈接表示 2022/1/4 38/114 每個(gè)節(jié)點(diǎn)有兩個(gè)域： 數(shù)據(jù)域 (info)：數(shù)據(jù)元素本身的信息 指針域 (link)：后繼結(jié)點(diǎn)的存儲位置 最后一個(gè)元素沒有后繼，其指針為空 設(shè)一線性表有 n個(gè)元素，則此 n個(gè)結(jié)點(diǎn)就通過指針鏈接成一個(gè)鏈表 ，由于每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，故又稱為 單鏈表 。 單鏈表表示 2022/1/4 39/114 2022/1/4 40/114 結(jié)點(diǎn)類型和單鏈表類型定義： [說明 ] PNode與 LinkList實(shí)為同一類型，既可以是指向某一結(jié)點(diǎn)的指針類型，也可以看成單鏈表的類型 (即頭指針的類型 ) 2022/1/4 41/114 struct Node。 /*結(jié)點(diǎn)指針類型 */ struct Node { /*單鏈表結(jié)點(diǎn)結(jié)構(gòu) */ DataType info。 }。 /*單鏈表類型 */ struct Node { DataType info。 }。 if (llist != NULL) llistlink = NULL。 /*創(chuàng)建失敗 */ return (llist)。 2022/1/4 45/114 int isNullList_link( LinkList llist) { /*判斷帶有頭結(jié)點(diǎn)的單鏈表 llist是否是空鏈表 */ return (llistlink == NULL)。 if (llist==NULL) return(NULL)。 while( p != NULL amp。 pinfo != x) p = plink。 } 4. 在某結(jié)點(diǎn)后插入新節(jié)點(diǎn) int insertPost_link(LinkList llist, PNode p, DataType x) 在結(jié)點(diǎn) p后面插入值為ｘ的新結(jié)點(diǎn) 2022/1/4 47/114 p a b x q (1) qlink=plink。 注意： (1)、 (2)順序不能反！ 2022/1/4 48/114 int insertPost_link(LinkList llist, PNode p, DataType x) { /*在 llist帶頭結(jié)點(diǎn)的單鏈表中 ,p所指結(jié)點(diǎn)后面插入元素 x */ PNode q = (PNode)malloc(sizeof( struct Node))。 return(0)。 qlink = plink。 return(1)。 if (llist==NULL) return(NULL)。 while( p1 != NULL amp。 p1link != p ) p1 = p1link。 } int deleteV_link(LinkList llist, DataType x) 刪除第一個(gè)元素值為 x的結(jié)點(diǎn)，并返回刪除成功與否的標(biāo)志 從第一個(gè)結(jié)點(diǎn)開始查找第一個(gè)元素值為 x的結(jié)點(diǎn) 刪除該結(jié)點(diǎn) (修改指針 ) 需記錄其前驅(qū)結(jié)點(diǎn) 2022/1/4 51/114 p a b c plink=plinklink。 p = llist。 while ( plink != NULL amp。 plinkinfo != x ) p = plink。 return 1。 /*找到值為 x的結(jié)點(diǎn) */ plink = qlink。 return 1。 先調(diào) 用 locatePre_link(llist, p )找到 p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 然后實(shí)現(xiàn)結(jié)點(diǎn)刪除。 缺點(diǎn)： 每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲空間，存儲密度??； 鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種非隨機(jī)存儲結(jié)構(gòu)，查找任一結(jié)點(diǎn)都要從頭指針開始，沿指針域一個(gè)一個(gè)地搜索，這增加了有些算法的時(shí)間代價(jià)。 /*雙鏈表結(jié)點(diǎn) */ typedef struct DoubleNode * PDoubleNode。 PDoubleNode llink, rlink。 struct DoubleList { /*雙鏈表類型 */ PDoubleNode head。 /*指向最后一個(gè)結(jié)點(diǎn) */ }。 prlinkllink = pllink。 2022/1/4 59/114 2. 雙鏈表 – cont. 雙鏈表中，在 p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)： q = (PDoubleNode)malloc(sizeof(struct DoubleNode))。 qrlink = prlink。 prlink = q。 Josephus問題： 對于任意給定的 n, s和 m，求出按出列次序得到的 n個(gè)人員的序列 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) 利用線性表的一些運(yùn)算 構(gòu)造 Josephus表 。 2022/1/4 66/114 主要步驟： (1) 將整數(shù)序列 (1， 2， 3， … ， n)存儲在一 個(gè) palist所指順序表中 用整數(shù) i來代替 ni (2) 最初從第 s個(gè)人開始 (即 palistelement[s1])，則第一個(gè)報(bào)數(shù)出列的元素編號應(yīng)為： (s1+m1) % n(設(shè)該編號為 i) 是否 s ≤ n對程序并不影響 (3) 輸出元 素 palistelement[i]，并將該元素從順序表中刪除 (4) 繼續(xù)在新的順序表中進(jìn)行以上 (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。 for(i = palistn。 i) { /*找出列的元素 */ s1 = (s1 + m 1) % i 。 /*求下標(biāo)為 s1的元素的值 */ printf(Out element %d \n, w)。 /*刪除出列的元素 */ } } 2022/1/4 69/114 void main() { int i, n, s, m。 scanf(%d,amp。 printf( please input the values of s = )。s)。 scanf(%d,amp。 PSeqList jos_alist=createNullList_seq( n )。 i n。 josephus_seq(jos_alist,s,m)。 free(jos_alist)。 (b) 從 p所指結(jié)點(diǎn)開始計(jì)數(shù)尋找第 m個(gè)結(jié)點(diǎn) 。 (d) 刪除該結(jié)點(diǎn)，并將該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)放在指針變量 p中，轉(zhuǎn)去執(zhí)行 (b)，直到所有結(jié)點(diǎn)被刪除為止 . 采用循環(huán)鏈表模擬 2022/1/4 70/114 2022/1/4 71/114 include include include define FALSE 0 define TRUE 1 int init_clist(PLinkList pclist, int n) { /*用 1, …, n為 *pclist所示的循環(huán)表初始化 */ PNode p, q。 q = (PNode)malloc(sizeof(struct Node))。 *pclist=q。 qlink = q。 for(i=2。i++) { p=(PNode)malloc(sizeof(struct Node))。 pinfo=i。 qlink=p。 } return (TRUE)。 int i。 /*找第 s個(gè)元素 */ if (s==1) { pre =p。 while (p!=*pclist) { pre =p。 } } else for(i=1。i++) { pre =p。 } /*當(dāng)鏈表中結(jié)點(diǎn)個(gè)數(shù)大于 1時(shí) */