【正文】 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é)點(diǎn)為遞增序。 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é)點(diǎn)為遞增序。 15 物料管理 LILST 15 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8 ） 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é)點(diǎn)為遞增序。 11 物料管理 LILST 11 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6 ） 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é)點(diǎn)為遞增序。 7 物料管理 LILST 7 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ） 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é)點(diǎn)為遞增序。 線性表的邏輯結(jié)構(gòu) 3 物料管理 LILST 3 DataStructures:LiLst 線性表 (Linear_list)是 a1,a2,… ,an,n(≥0) 個(gè)數(shù)據(jù)元素的有限序列。 存在 唯一的 一個(gè)被稱之為 “ 最后一個(gè) ” 的結(jié)點(diǎn)。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。 Lc) { InitiList( Lc )。 GetElem(Lb,j,bj)。 }。如用數(shù)組表示線性表。 } seqlist。 主函數(shù)調(diào)用： Main(){ Seqlist *L。 在一般情況下，插在第 i 個(gè)結(jié)點(diǎn)之前，移動(dòng) n(i1) 次 插在第 1 個(gè)結(jié)點(diǎn)之前，移動(dòng) n 次 插在第 2 個(gè)結(jié)點(diǎn)之前，移動(dòng) n1 次 插在第 i 個(gè)結(jié)點(diǎn)之前，移動(dòng) n(i1) 次 插在第 n 個(gè)結(jié)點(diǎn)之前，移動(dòng) 1 次。 刪除 31 物料管理 LILST 31 DataStructures:LiLst 插入和刪除的時(shí)間復(fù)雜性分析： 32 物料管理 LILST 32 DataStructures:LiLst 插入、刪除、查找的實(shí)現(xiàn)算法： /*結(jié)點(diǎn)移動(dòng) */ Ldata[i1]=x。} for(j=i。 36 物料管理 LILST 36 DataStructures:LiLst 順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn) ? 優(yōu)點(diǎn)： ； 。 頭指針 ：指向鏈表頭結(jié)點(diǎn)的指針。 if(c!=’$’) /*為讀入的字符分配存儲(chǔ)空間 */ { s=(Node*)malloc(sizeof(Node))。 L=(Node * )malloc(sizeof(Node))。 r=s } else { flag=0。查找過(guò)程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值 e作比較。 e s a1 … … an ∧ ai1 ai e s pre L a1 … … an ∧ pre ai1 ai 53 物料管理 LILST 53 DataStructures:LiLst 單鏈表插入操作算法實(shí)現(xiàn) void InsList(LinkList L,int i,ElemType e) { /*在帶頭結(jié)點(diǎn)的單鏈表 L中第 i個(gè)結(jié)點(diǎn)之前插入值為 e的新結(jié)點(diǎn) 。 } if(k!=i1) { printf(“插入位置不合理 ！ ” )； return。 int k =0。 pnext=pnextnext 。 j ++。 pre=LA。 p=pnext。 60 物料管理 LILST 60 DataStructures:LiLst 帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖 L a1 … … ai1 ai an L a1 … … ai1 ai an rear *(rearnext) *rear 空鏈表 帶 頭 結(jié)點(diǎn)的一般形式 帶 尾 結(jié)點(diǎn)的一般形式 61 物料管理 LILST 61 DataStructures:LiLst 循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表 已知 ： 有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表 LA、 LB，編寫一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為 LA。/*修改表 LB 的尾指針 ， 使之指向表 LA 的頭結(jié)點(diǎn) */ pnext=LBnext。 if (s) { sdata=e。 68 物料管理 LILST 68 DataStructures:LiLst 雙向鏈表的刪除操作 ? 算法描述： 欲刪除雙向鏈表中的第 i個(gè)結(jié)點(diǎn)，則指針的變化情況如圖所示。 算法思想： 實(shí)際上是交換表中前兩個(gè)元素的次序。 pnext=h。 ? 基本操作： 初始化 、 分配結(jié)點(diǎn)與結(jié)點(diǎn)回收 、 前插操作 、 刪除 。kMaxsize1。 *av=k。m++) /*尋找第 i 1個(gè)元素的位置 k */ k=space[k]cursor。m++) /*尋找第 i1個(gè)元素的位置 k */ k=space[k]cursor 。 } Polynode , * Polylist。/*鍵入多項(xiàng)式的系數(shù)和指數(shù)項(xiàng) */ while(c!=0) /*若 c=0， 則代表多項(xiàng)式的輸入結(jié)束 */ { s=(Polynode*)malloc(sizeof(Polynode))。 } rearnext=NULL。 若系數(shù)為 0則刪除 p， q節(jié)點(diǎn) */} else{ … /*將 q結(jié)點(diǎn)加入到和多項(xiàng)式中 */} } … ../*將多項(xiàng)式 polya或 polyb中剩余的結(jié)點(diǎn)加入到和多項(xiàng)式中 */ } 。} 81 物料管理 LILST 81 DataStructures:LiLst 多項(xiàng)式的單鏈表表示示意圖 說(shuō)明：圖示分別為多項(xiàng)式 A(x)=7+3x+9x8+5x17 B(x)=8x+22x79x8 1 7 0 3 1 5 17 ∧ 9 8 8 1 1 22 7 9 8 ∧ 82 物料管理 LILST 82 DataStructures:LiLst 兩個(gè) 多項(xiàng)式相加 ? 運(yùn)算規(guī)則 ： 兩個(gè)多項(xiàng)式中所有指數(shù)相同的項(xiàng)的對(duì)應(yīng)系數(shù)相加 ， 若和不為零 ， 則構(gòu)成 “ 和多項(xiàng)式 ” 中的一項(xiàng)；所有指數(shù)不相同的項(xiàng)均復(fù)抄到 “和多項(xiàng)式 ” 中 。 sexp=e 。 Polylist polycreate() { Polynode *head, *rear, *s。 space[k]cursor=space[j]cursor。 /*修改游標(biāo)域 */ space[k]cursor=j。 void insbefore(StaticList space,int i,int *av) { j=*av 。 /*連鏈 */ space[Maxsize1]=0。 int cursor。 } 71 物料管理 LILST 71 DataStructures:LiLst * 靜態(tài)鏈表 ? 基本概念： 游標(biāo)實(shí)現(xiàn)鏈表的方法 ：定義一個(gè)較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點(diǎn)空間（即存儲(chǔ)池）。 h=Lnext。 ? /*首先檢查待插入的位置 i是否合法 */ ? /*若位置 i合法 ， 則讓指針 p指向它 */ *e=pdata。 ppriornext=s。 return(LA)。 62 物料管理 LILST 62 DataStructures:LiLst 循環(huán)單鏈表合并算法實(shí)現(xiàn) LinkList merge_1(LinkList LA,LinkList LB) /*此算法將兩個(gè)鏈表的首尾連接起來(lái) */ { Node *p, *q。 } else { pre=p。 /*p向表中的某一結(jié)點(diǎn) ， pre始終指向 p的前驅(qū) */ while(p!=NULL) { q=LBnext。 } 算法演示鏈接 。 free(r)。amp。 /*為 e申請(qǐng)一個(gè)新的結(jié)點(diǎn) */ sdata=e。 pre=L。 51 物料管理 LILST 51 DataStructures:LiLst 按值查找算法實(shí)現(xiàn) / * 在帶頭結(jié)點(diǎn)的單鏈表 L中查找其結(jié)點(diǎn)值等于 key的結(jié)點(diǎn) ， 若找到則返回該結(jié)點(diǎn)的位置 p， 否則返回 NULL * / Node *Locate( LinkList L,ElemType key) { Node *p。 } } } 48 物料管理