【正文】 q!=NULL） { if （ pexp qexp） { … /*將 p結(jié)點加入到和多項式中 */} else if ( pexp= =qexp） { … /*若指數(shù)相等 ， 則相應的系數(shù)相加 。 算法實現(xiàn) ， 算法演示 若 pexp qexp， 則結(jié)點 p所指的結(jié)點應 是 “ 和多項式 ” 中的一項 ， 令指針 p后移； 若 pexpqexp， 則結(jié)點 q所指的結(jié)點應是 “ 和多項式 ” 中的一項 ， 將結(jié)點 q插入在結(jié)點 p之前 ， 且令指針 q在原來的鏈表上后移； 若 pexp=qexp， 則將兩個結(jié)點中的系數(shù)相加 ， 當和不為零時修改結(jié)點 p的系數(shù)域 ， 釋放 q結(jié)點；若和為零 ， 則和多項式中無此項 ， 從 A中刪去 p結(jié)點 ， 同時釋放 p和 q結(jié)點 。e)。rearnext=s 。e)。 int c,e。 Polynode *next。/*從刪除第 i個元素 */ space[j]cursor=*av。 for(m=1,mi1。} 77 物料管理 LILST 77 DataStructures:LiLst 靜態(tài)鏈表 刪除 算法描述： 首先尋找第 i 1個元素的位置 ， 之后通過修改相應的游標域進行刪除；在將被刪除的結(jié)點空間鏈到可用靜態(tài)單鏈表中 ， 實現(xiàn)回收 。mi1。 /*j為從備用表中取到的可用結(jié)點空間的下標 */ av=space[av]cursor。 } ? 結(jié)點回收 void freenode(int *av,int k) /*將下標為 k的空閑結(jié)點插入到備用鏈表 */ { space[k].cursor=*av。 /*標記鏈尾 */ *av=1。/*設置靜態(tài)單鏈表的頭指針指向位置 0*/ for(k=0。 }Component, StaticList[Maxsize]。 靜態(tài)鏈表的結(jié)構(gòu)定義 ， 靜態(tài)鏈表的插入和刪除操作示例 。當申請結(jié)點時，每個結(jié)點應含有兩個域： data域和 next域。 /*變換指針指向 */ pprior=q。 /* h指向表中的第一個結(jié)點 ， 即 a */ p=hnext。 } 70 物料管理 LILST 70 DataStructures:LiLst 雙向鏈表應用舉例 已知 ： 設一個循環(huán)雙鏈表 L=（ a,b,c,d）編寫一個算法將鏈表轉(zhuǎn)換為 L=（b,a,c,d）。 ppriornext=pnext。 } 算法演示連接 。 snext=p。 ? /*首先檢查待插入的位置 i是否合法 */ ? /*若位置 i合法 ， 則讓指針 p指向它 */ s=(DNode*)malloc(sizeof(DNode))。 } 63 物料管理 LILST 63 DataStructures:LiLst 雙向鏈表 雙向鏈表： 在單鏈表的每個結(jié)點里再增加一個指向其前趨的指針域 prior。 /*找到表 LB的表尾 */ qnext=LA。 p=LA。 帶頭結(jié)點循環(huán)單鏈表示意圖 。 p=pnext。 prenext=pnext。 /*掃描 LB中的結(jié)點 ， 尋找與 LA中 *P結(jié)點相同的結(jié)點 */ while (q!=NULLamp。*p, *r。 57 物料管理 LILST 57 DataStructures:LiLst 求兩個集合的差 ? 已知： 以單鏈表表示集合，假設集合 A用單鏈表 LA表示，集合 B用單鏈表 LB表示，設計算法求兩個集合的差，即 AB。 /*用來存放單鏈表的長度 */ while(p!=NULL) { p=pnext。 /*釋放被刪除的結(jié)點所占的內(nèi)存空間 */ } 56 物料管理 LILST 56 DataStructures:LiLst 求單鏈表的長度 算法描述： 可以采用 “ 數(shù) ” 結(jié)點的方法來求出單鏈表的長度，用指針 p依次指向各個結(jié)點 ,從第一個元素開始 “ 數(shù) ” ，一直 “ 數(shù) ” 到最后一個結(jié)點（ pnext=NULL）。 } r=pnext。ki1) /*尋找被刪除結(jié)點 i的前驅(qū)結(jié)點 */ { p=pnext。 p=L。 /*將待插入結(jié)點的值 e賦給 s的數(shù)據(jù)域 */ snext=prenext。 k=k+1。 int k=0。 } 52 物料管理 LILST 52 DataStructures:LiLst 單鏈表插入操作 ? 算法描述： 要在帶頭結(jié)點的單鏈表 L中第 i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素 e，需要首先在單鏈表中找到第 i1個結(jié)點并由指針 pre指示，然后申請一個新的結(jié)點并由指針 s指示，其數(shù)據(jù)域的值為 e，并修改第 i1個結(jié)點的指針使其指向 s，然后使 s結(jié)點的指針域指向第 i個結(jié)點。 p=Lnext。 (ji)) { p=pnext； j++； / * 掃描下一結(jié)點 * / } / * 已掃描結(jié)點計數(shù)器 * / if（ i= =j） return p； / * 找到了第 i個結(jié)點 * / else return NULL； / * 找不到 ， i≤ 0或 in * / } 50 物料管理 LILST 50 DataStructures:LiLst ?按值查找 算法描述：按值查找是指在單鏈表中查找是否有結(jié)點值等于 e的結(jié)點，若有的話，則返回首次找到的其值為 e的結(jié)點的存儲位置，否則返回 NULL。 算法實現(xiàn) ，算法演示。 rnext=s。 /*r指針始終動態(tài)指向鏈表的當前表尾 */ while(flag) /*標志 ， 初值為 1。 int flag =1。 Lnext=s。 while(flag) { c=getchar()。 c1 ∧ s L ∧ L ci1 ∧ c2 c1 ∧ ci s … c1 ∧ 45 物料管理 LILST 45 DataStructures:LiLst 頭插法建表算法 Linklist CreateFromHead() { LinkList L。 單鏈表包括 兩個域 ： 數(shù)據(jù)域 用來存儲結(jié)點的值； 指針域 用來存儲數(shù)據(jù)元素的直接后繼的地址（或位置）。 37 物料管理 LILST 37 DataStructures:LiLst 線性表的鏈式存儲 ? 鏈表定義： 采用鏈式存儲結(jié)構(gòu)的線性表稱為 鏈表 。 （ 2） .有順序表 A和 B,其元素均按從小到大的升序排列，編寫算法將他們合并成一個順序表 C，要求 C的元素也是從小到大的升序排列。 /*向上移動 */ Llen。 return(0)。 /*插入成功，返回 */ } // initList_Sq。j) Ldata[j+1]=Ldata[j]。} /*表空間已滿，不能插入 */ if (i1 || iLlen+1) {printf(“Infeasible”)。 查找第 i 個結(jié)點，代價 O(1)。 總共 n 種情況 在一般情況下，刪除第 i 個結(jié)點，移動 ni 次。在長度為 n 的線性表中插入一個結(jié)點的平均次數(shù)為： ∑(ni+1)/(n+1) = n/2 時間復雜性為 O(n)。插第 4 個結(jié)點之前，移動 6－（ 4－ 1） 次。插入（在線性表的第 i 個位置上插入 x） ： 25 12 47 89 36 14 1 2 3 4 5 6 7 8 9 25 12 47 99 89 36 14 99插入 25 12 47 89 36 14 25 12 47 89 36 14 25 12 47 89 36 14 } // init_seq。建立一個順序存儲的線性表： seqlist *init_seqlist( ) { seqlist *L。 int len。設每個結(jié)點占用 L 個單元。順序表示：在物理位置上緊靠在一起。 ++j。 ++i。 } else { Listinsert(Lc, ++k, bj ) 。 ( j = ) ) { GetElem(La,i,ai)。 = ListLength(La)。 25 物料管理 LILST 25 DataStructures:LiLst Void Mergelist(List La,list Lb, list amp。 23 物料管理 LILST 23 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9， 11 ， 11， 15） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點為遞增序。 21 物料管理 LILST 21 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9， 11， 11 ） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點為遞增序。 19 物料管理 LILST 19 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9， 11 ） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點為遞增序。 17 物料管理 LILST 17 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9 ） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線