【文章內(nèi)容簡介】 p=pnext。 else break。 / * 找到結(jié)點 key， 退出循環(huán) * / return p。 } 2022/8/26 38 單鏈表插入操作 ? 算法描述： 要在帶頭結(jié)點的單鏈表 L中第 i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素 e，需要首先在單鏈表中找到第 i1個結(jié)點并由指針 pre指示，然后申請一個新的結(jié)點并由指針 s指示，其數(shù)據(jù)域的值為 e，并修改第 i1個結(jié)點的指針使其指向 s，然后使 s結(jié)點的指針域指向第 i個結(jié)點。 e s a1 … … an ∧ ai1 ai e s pre L a1 … … an ∧ pre ai1 ai 2022/8/26 39 單鏈表插入操作算法實現(xiàn) void InsList(LinkList L,int i,ElemType e) { /*在帶頭結(jié)點的單鏈表 L中第 i個結(jié)點之前插入值為 e的新結(jié)點 。 */ Node *pre,*s。 pre=L。 int k=0。 while(pre!=NULLamp。amp。ki1) /*先找到第 i1個數(shù)據(jù)元素的存儲位置 ,使指針 Pre指向它 */ { pre=prenext。 k=k+1。 } if(k!=i1) { printf(“插入位置不合理 ！ ” )； return。 } s=(Node*)malloc(sizeof(Node))。 /*為 e申請一個新的結(jié)點 */ sdata=e。 /*將待插入結(jié)點的值 e賦給 s的數(shù)據(jù)域 */ snext=prenext。 prenext=s。 } 2022/8/26 40 單鏈表刪除 ? 算法描述： 欲在帶頭結(jié)點的單鏈表 L中刪除第 i個結(jié)點，則首先要通過計數(shù)方式找到第 i1個結(jié)點并使 p指向第 i1個結(jié)點，而后刪除第 i個結(jié)點并釋放結(jié)點空間。 p a1 … ai1 ai … an ∧ p a1 … L … an ∧ ai1 ai ai+1 r L 2022/8/26 41 單鏈表刪除算法實現(xiàn) void DelList(LinkList L,int i,ElemType *e) /*在帶頭結(jié)點的單鏈表 L中刪除第 i個元素 ， 并保存其值到變量 *e中 */ { Node *p,*r。 p=L。 int k =0。 while(pnext!=NULLamp。amp。ki1) /*尋找被刪除結(jié)點 i的前驅(qū)結(jié)點 */ { p=pnext。 k=k+1。 } if(k!=i1) /* 即 while循環(huán)是因為 pnext=NULL而跳出的 */ { printf(“刪除結(jié)點的位置 i不合理 ！ ” )。 return ERROR。 } r=pnext。 pnext=pnextnext /*刪除結(jié)點 r*/ free(r)。 /*釋放被刪除的結(jié)點所占的內(nèi)存空間 */ } 2022/8/26 42 求單鏈表的長度 算法描述： 可以采用 “ 數(shù) ” 結(jié)點的方法來求出單鏈表的長度，用指針 p依次指向各個結(jié)點 ,從第一個元素開始 “ 數(shù) ” ，一直 “ 數(shù) ” 到最后一個結(jié)點（ pnext=NULL）。 int ListLength(LinkList L) /*L為帶頭結(jié)點的 單鏈表 */ { Node *p。 p=Lnext。 j=0。 /*用來存放單鏈表的長度 */ while(p!=NULL) { p=pnext。 j ++。 } return j。 } 算法演示鏈接 。 2022/8/26 43 兩個有序單鏈表的合并 ? 有兩個單鏈表 LA和 LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個單鏈表 LC，要求 LC也是非遞減有序排列。要求：利用新表 LC利用現(xiàn)有的表 LA和 LB中的元素結(jié)點空間，而不需要額外申請結(jié)點空間。例如 LA=(2, 2, 3), LB=(1, 3, 3, 4), 則 LC=(1, 2, 2, 3, 3, 3, 4)。 【 算法描述 】 要求利用現(xiàn)有的表 LA和 LB中的結(jié)點空間來建立新表 LC,可通過更改結(jié)點的 next域來重建新的元素之間的線性關(guān)系，為保證新表仍然遞增有序，可以利用尾插入法建立單鏈表的方法，只是新建表中的結(jié)點不用malloc，而只需要從表 LA和 LB中選擇合適的點插入到新表 LC中即可。 2022/8/26 44 2022/8/26 45 兩個有序單鏈表的合并的算法實現(xiàn) LinkList MergeLinkList(LinkList LA, LinkList LB) /*將遞增有序的單鏈表 LA和 LB合并成一個遞增有序的單鏈表 LC*/ { Node *pa,*pb。 LinkList LC； /*將 LC初始置空表。 pa和 pb分別指向兩個單鏈表 LA和 LB中的第一個結(jié)點 ,r初值為 LC*/ pa=LAnext。 pb=LBnext。 LC=LA。 LCnext=NULL； r=LC。 /*初始化操作 */ 2022/8/26 46 兩個有序單鏈表的合并的算法實現(xiàn)（續(xù)） /*當(dāng)兩個表中均未處理完時，比較選擇將較小值結(jié)點插入到新表 LC中。 */ while(pa!=NULLamp。amp。pb!=NULL) {if(padata=pbdata) {rnext=pa。r=pa。pa=panext。} else {rnext=pb。r=pb。pb=pbnext。} } if(pa) /*若表 LA未完，將表 LA中后續(xù)元素鏈到新表 LC表尾 */ rnext=pa。 else /*否則將表 LB中后續(xù)元素鏈到新表 LC表尾 */ rnext=pb。 free(LB)。 return(LC)。 } /* MergeLinkList */ 2022/8/26 47 循環(huán)鏈表 循環(huán)鏈表 (Circular Linked List) 是一個首尾相接的鏈表。 特點 ：將單鏈表最后一個結(jié)點的指針域由 NULL改為指向頭結(jié)點或線性表中的第一個結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點被鏈在一個環(huán)上。 帶頭結(jié)點循環(huán)單鏈表示意圖 。 2022/8/26 48 帶頭結(jié)點的循環(huán)單鏈表示意圖 L a1 … … ai1 ai an L a1 … … ai1 ai an rear *(rearnext) *rear 空鏈表 帶 頭 結(jié)點的一般形式 帶 尾 結(jié)點的一般形式 2022/8/26 49 循環(huán)單鏈表合并為一個循環(huán)單鏈表 已知 ： 有兩個帶頭結(jié)點的循環(huán)單鏈表 LA、 LB，編寫一個算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為 LA。 算法思想 ：先找到兩個鏈表的尾，并分別由指針p、 q指向它們，然后將第一個鏈表的尾與第二個表的第一個結(jié)點鏈接起來，并修改第二個表的尾Q，使它的鏈域指向第一個表的頭結(jié)點。 2022/8/26 50 循環(huán)單鏈表合并算法實現(xiàn) LinkList merge_1(LinkList LA,LinkList LB) /*此算法將兩個鏈表的首尾連接起來 */ { Node *p, *q。 p=LA。 q=LB。 while (pnext!=LA) p=pnext。 /*找到表 LA的表尾 */ while (qnext!=LB) q=qnext。 /*找到表 LB的表尾 */ qnext=LA。/*修改表 LB 的尾指針 ， 使之指向表 LA 的頭結(jié)點 */ pnext=LBnext。/*修改表 LA的尾指針 ， 使之指向表 LB 中的第一個結(jié)點 */ free(LB)。 return(LA)。 } 2022/8/26 51 雙向鏈表 雙向鏈表： 在單鏈表的每個結(jié)點里再增加一個指向其前趨的指針域 prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為 雙 ( 向 ) 鏈表 (Double Linked List)。 雙向鏈表的 結(jié)構(gòu)定義： typedef struct Dnode { ElemType data； struct DNode *prior， *next； } DNode, * DoubleList； 2022/8/26 52 雙鏈表的結(jié)構(gòu)定義 ? 雙鏈表的結(jié)點結(jié)構(gòu) 后繼指針域 prior data next 前驅(qū)指針域 數(shù)據(jù)域 2022/8/26 53 雙向循環(huán)鏈表示意圖 a1 a2 a3 L L 空的雙向循環(huán)鏈表 非空的雙向循環(huán)鏈表 2022/8/26 54 雙向鏈表的前插操作 ? 算法描述： 欲在雙向鏈表第 i個結(jié)點之前插入一個的新的結(jié)點，則指針的變化情況如圖所示。 e s ① ② ③ ④ … b p a … 2022/8/26 55 雙向鏈表的前插操作算法實現(xiàn) void DlinkIns(DoubleList L,int i,ElemType e) { DNode *s,*p。 ? /*首先檢查待插入的位置 i是否合法 */ ? /*若位置 i合法 ， 則讓指針 p指向它 */ s=(DNode*)malloc(sizeof(DNode))。 if (s) { sdata=e。 sprior=pprior。 ppriornext=s。 snext=p。 pprior=s。 return TRUE。