【正文】 s=(Node*)malloc(sizeof(Node))。 Lnext=p。 2022/8/26 78 【 算法描述 】 AdjustSqlist(SeqList *L) /* {int i=0,j=Llast。 算法實現(xiàn) ， 算法演示 – 若 pexp qexp， 則結(jié)點 p所指的結(jié)點應(yīng) 是 “ 和多項式 ” 中的一項 ， 令指針 p后移； – 若 pexpqexp， 則結(jié)點 q所指的結(jié)點應(yīng)是 “ 和多項式 ” 中的一項 ， 將結(jié)點 q插入在結(jié)點 p之前 ， 且令指針 q在原來的鏈表上后移； – 若 pexp=qexp， 則將兩個結(jié)點中的系數(shù)相加 ， 當(dāng)和不為零時修改結(jié)點 p的系數(shù)域 ， 釋放 q結(jié)點；若和為零 ， 則和多項式中無此項 ， 從 A中刪去 p結(jié)點 ， 同時釋放 p和 q結(jié)點 。 int c,e。 *av=k。 ? 基本操作： 初始化 、 分配結(jié)點與結(jié)點回收 、 前插操作 、 刪除 。 return TRUE。 while (pnext!=LA) p=pnext。} else {rnext=pb。 2022/8/26 43 兩個有序單鏈表的合并 ? 有兩個單鏈表 LA和 LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個單鏈表 LC，要求 LC也是非遞減有序排列。 while(pnext!=NULLamp。 */ Node *pre,*s。 rnext=NULL。 sdata=c。 缺點： ，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結(jié)點，其效率較低； ，存儲分配只能預(yù)先進行靜態(tài)分配。 while(i=LAlastamp。 return(OK)。 /*i為掃描計數(shù)器 ， 初值為 0， 即從第一個元素開始比較 */ while ((i=)amp。 數(shù)據(jù)元素之間是一對一的關(guān)系 ， 即每個數(shù)據(jù)元素最多有一個直接前驅(qū)和一個直接后繼 。 操作結(jié)果：將表 L置為空表。 if( (i1) || (iLlast+2) ) /*首先判斷插入位置是否合法 */ { printf(“插入位置 i值不合法 ” )； return(ERROR)。 /*將后面的元素依次前移 */ Llast。 i++。 ? 帶頭結(jié)點的空單鏈表 ? 帶頭結(jié)點的單鏈表 ∧ H a1 a2 … H an ∧ 2022/8/26 28 單鏈表的存儲結(jié)構(gòu)描述 typedef struct Node / * 結(jié)點類型定義 * / { ElemType data； struct Node * next； }Node, *LinkList； /* LinkList為結(jié)構(gòu) 指針類型 */ 2022/8/26 29 單鏈表上的基本運算 ? 線性表的基本運算 ： 1. 建立單鏈表 2. 單鏈表查找 3. 單鏈表插入操作 4. 單鏈表刪除 ? 算法應(yīng)用示例： 1. 求單鏈表的長度 2. 求兩個集合的差 2022/8/26 30 建立單鏈表 ? 頭插法建表 算法描述： 從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭結(jié)點之后，直至讀入結(jié)束標(biāo)志為止。 r=L。 單鏈表查找 2022/8/26 37 按值查找算法實現(xiàn) / * 在帶頭結(jié)點的單鏈表 L中查找其結(jié)點值等于 key的結(jié)點 ， 若找到則返回該結(jié)點的位置 p， 否則返回 NULL * / Node *Locate( LinkList L,ElemType key) { Node *p。 /*為 e申請一個新的結(jié)點 */ sdata=e。 int ListLength(LinkList L) /*L為帶頭結(jié)點的 單鏈表 */ { Node *p。 LCnext=NULL； r=LC。在循環(huán)單鏈表中，表中所有結(jié)點被鏈在一個環(huán)上。 e s ① ② ③ ④ … b p a … 2022/8/26 55 雙向鏈表的前插操作算法實現(xiàn) void DlinkIns(DoubleList L,int i,ElemType e) { DNode *s,*p。 return TRUE。k++) space[k]cursor=k+1。 pi ei ┋ ┋ 圖 一元多項式只存非零項存儲示意圖 2022/8/26 67 一元多項式的鏈?zhǔn)酱鎯Ρ硎? ? 在鏈?zhǔn)酱鎯χ校瑢σ辉囗検街淮娣橇沩?，則該多項式中每一非零項由兩部分構(gòu)成（指數(shù)項和系數(shù)項），用單鏈表存儲表示的結(jié)點結(jié)構(gòu)為： 用單鏈表存儲多項式的結(jié)點結(jié)構(gòu)如下： struct Polynode { int coef。 /*在當(dāng)前表尾做插入 */ rear=s。 ? 單鏈表的操作特點 ： – ⑴順鏈操作技術(shù) – ⑵指針保留技術(shù) ? 鏈表處理中的相關(guān)技術(shù) 2022/8/26 76 典型題例 ? 例 1： 已知順序表 L中的數(shù)據(jù)元素類型為 int。 2022/8/26 80 ? 算法思路： 逆置后的單鏈表初始為空，表中的結(jié)點不是新生成的，而是從原鏈表中依次 “ 刪除 ” ，再逐個頭插入到逆置表中（類同算法 ）。 2022/8/26 84 【 算法描述 】 void BinAdd(LinkList l) /*用帶頭結(jié)點的單鏈表 L存儲二進制數(shù)，實現(xiàn)加 1運算 */ { Node *q,*r,*temp,*s。 r = rnext。③鏈表實現(xiàn)二進制加 1時，從高位往低位與運算方向正好相反，從第一個結(jié)點開始找，找出最后一個值域為 0的結(jié)點，把該結(jié)點值域賦為 1，其后所有結(jié)點的值域賦為 0。就地逆置就是不需要額外申請結(jié)點空間，只需要利用原有的表中的節(jié)點空間。 2022/8/26 75 總結(jié)與提高 – 線性表鏈?zhǔn)酱鎯Γㄦ湵恚翰捎脛討B(tài)分配方式，借助于 C語言的指針類型，動態(tài)申請與動態(tài)釋放地址空間，故鏈表中的各結(jié)點的物理存儲可以是不連續(xù)的。 sexp=e 。 2022/8/26 66 一元多項式的順序存儲表示 2 – 法 采用只存儲非零項的方法，此時每個非零項需要存儲：非零項系數(shù)和非零項指數(shù)。/*設(shè)置靜態(tài)單鏈表的頭指針指向位置 0*/ for(k=0。 pnextprior=pprior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為 雙 ( 向 ) 鏈表 (Double Linked List)。 } /* MergeLinkList */ 2022/8/26 47 循環(huán)鏈表 循環(huán)鏈表 (Circular Linked List) 是一個首尾相接的鏈表。 pb=LBnext。 pnext=pnextnext /*刪除結(jié)點 r*/ free(r)。 } if(k!=i1) { printf(“插入位置不合理 ！ ” )； return。查找過程從單鏈表的頭指針指向的頭結(jié)點出發(fā)，順著鏈逐個將結(jié)點的值和給定值 e作比較。 L=(Node * )malloc(sizeof(Node))。 頭指針 ：指向鏈表頭結(jié)點的指針。 k++。i=Llast。 2022/8/26 15 插入 算法示意圖 已知： 線性表 (4,9,15,28,30,30,42,51,62)，需在第 4個元素之前插入一個元素 “ 21”。 操作結(jié)果：將 L銷毀。 ?有窮性：線性表由有限個數(shù)據(jù)元素組成，表長度就是表中數(shù)據(jù)元素的個數(shù)。([i]!=e) ) i++。 2022/8/26 17 刪除操作 線性表的刪除運算是指將表的第 i(1≤ i≤ n)個元素刪去，使長度為 n的線性表 (e1， … ,ei1， ei，ei+1， … ， en)，變成長度為 n1的線性表(e1， … ,ei1， ei+1， … ， en)。j=LBlast) if(LAelem[i]=LBelem[j]) { LCelem[k]= LAelem[i]。 2022/8/26 23 線性表的鏈?zhǔn)酱鎯? ? 鏈表定義： 采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為 鏈表 。 Lnext=s。算法實現(xiàn) ，算法演示。 int k=0。ki1) /*尋找被刪除結(jié)點 i的前驅(qū)結(jié)點 */ { p=pnext。例如 LA=(2, 2, 3), LB=(1, 3, 3, 4), 則 LC=(1, 2, 2, 3, 3, 3, 4)。pb=pbnext。 /*找到表 LB的表尾 */ qnext=LA。 } 算法演示連接 。 int cursor。即： ? Q= (q0， q1， q2， … ， qm ) ? 若假設(shè) mn，則兩個多項式相加的結(jié)果 Rn(x)= Pn(x) + Qm(x)，也可以用線性表 R來表示： ? R=(p0+q0， p1+ q1,， p2+ q2， … ， pm+ qm ， pm+1， … ， pn) 2022/8/26 64 一元多項式的存儲 ? 一元多項式的順序存儲表示 ? 一元多項式的鏈?zhǔn)酱鎯Ρ硎? 2022/8/26 65 一元多項式的順序存儲表示 1 ? 一元多項式 Pn(x)的順序表示有兩種。 /*建立多項式的頭結(jié)點 ， rear 始終指向單鏈表的尾 */ scanf(“%d,%d”,amp。Polylist polyb) { …… /* p和 q分別指向