【正文】 Polylist polyb) { …… /* p和 q分別指向 polya和 polyb鏈表中的當(dāng)前計(jì)算結(jié)點(diǎn) */ …… /* pre指向和多項(xiàng)式鏈表中的尾結(jié)點(diǎn) */ while p!=NULL amp。 scanf(“%d,%d”,amp。 /*建立多項(xiàng)式的頭結(jié)點(diǎn) ， rear 始終指向單鏈表的尾 */ scanf(“%d,%d”,amp。 /*置備用表頭指針以新值 */ } 78 物料管理 LILST 78 DataStructures:LiLst 順序表和鏈表的比較 ? 1．基于空間的考慮 ? 2．基于時(shí)間的考慮 ? 3．基于語言的考慮 79 物料管理 LILST 79 DataStructures:LiLst 一元多項(xiàng)式的表示及相加 一個(gè)一元多項(xiàng)式 Pn(x)可按升冪的形式寫成： Pn(x)=p0+p1x+p2x2+p3x3+ … +p nxn 在計(jì)算機(jī)內(nèi) ， 可以用一個(gè)線性表 P來表示： P=（ p0， p1， p2， … ， pn） 用單鏈表存儲多項(xiàng)式的結(jié)點(diǎn)結(jié)構(gòu)如下： typedef struct Polynode { int coef。int i。 k=space[0]cursor。 *av=space[*av].cur。 設(shè) space為靜態(tài)單鏈表的名字 ， av為備用單鏈表的頭指針 ， 其算法如下： void initial(StaticList space,int *av) { int k。數(shù)組的第 0個(gè)分量可以設(shè)計(jì)成表的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的 next域指示了表中第一個(gè)結(jié)點(diǎn)的位置，為 0表示靜態(tài)單鏈表的結(jié)束。 /* 保存 a 結(jié)點(diǎn)的前驅(qū) */ hnext=pnext。 free(p)。 return TRUE。 雙向鏈表的 結(jié)構(gòu)定義： typedef struct Dnode { ElemType data； struct DNode *prior， *next； } DNode, * DoubleList； 64 物料管理 LILST 64 DataStructures:LiLst 雙鏈表的結(jié)構(gòu)定義 ? 雙鏈表的結(jié)點(diǎn)結(jié)構(gòu) 后繼指針域 prior data next 前驅(qū)指針域 數(shù)據(jù)域 65 物料管理 LILST 65 DataStructures:LiLst 雙向循環(huán)鏈表示意圖 a1 a2 a3 L L 空的雙向循環(huán)鏈表 非空的雙向循環(huán)鏈表 66 物料管理 LILST 66 DataStructures:LiLst 雙向鏈表的前插操作 ? 算法描述： 欲在雙向鏈表第 i個(gè)結(jié)點(diǎn)之前插入一個(gè)的新的結(jié)點(diǎn)，則指針的變化情況如圖所示。 while (pnext!=LA) p=pnext。 特點(diǎn) ：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由 NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。qdata!=pdata) q=qnext。具體做法是，對于集合 A中的每個(gè)元素 e，在集合 B的鏈表 LB中進(jìn)行查找，若存在與 e相同的元素，則從 LA中將其刪除。 p=Lnext。 } if(k!=i1) /* 即 while循環(huán)是因?yàn)?pnext=NULL而跳出的 */ { printf(“刪除結(jié)點(diǎn)的位置 i不合理 ！ ” )。 } 54 物料管理 LILST 54 DataStructures:LiLst 單鏈表刪除 ? 算法描述： 欲在帶頭結(jié)點(diǎn)的單鏈表 L中刪除第 i個(gè)結(jié)點(diǎn)，則首先要通過計(jì)數(shù)方式找到第 i1個(gè)結(jié)點(diǎn)并使 p指向第 i1個(gè)結(jié)點(diǎn)，而后刪除第 i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。amp。 else break。 否則返回 NULL * / Lnode *Get(LinkList L, int i) { Lnode *p； p=L； j=0； / * 從頭結(jié)點(diǎn)開始掃描 * / while (pnext!=NULL amp。 if(c!=’$’) { s=(Node*)malloc(sizeof(Node))。 } } 46 物料管理 LILST 46 DataStructures:LiLst 尾插法建表 C1 ∧ s r ∧ L c1 r s c2 ∧ L c1 ∧ r s L 47 物料管理 LILST 47 DataStructures:LiLst 尾插法建表算法 Linklist CreateFromTail() /*將新增的字符追加到鏈表的末尾 */ { LinkList L。 int flag=1。 38 物料管理 LILST 38 DataStructures:LiLst ? 單鏈表 ? 單鏈表上的基本運(yùn)算 ? 循環(huán)鏈表 ? 雙向鏈表 ?* 靜態(tài)鏈表 ? 順序表和鏈表的比較 鏈表 39 物料管理 LILST 39 DataStructures:LiLst 單鏈表 結(jié)點(diǎn)（ Node） 為了正確地表示結(jié)點(diǎn)間的邏輯關(guān)系，必須在存儲線性表的每個(gè)數(shù)據(jù)元素值的同時(shí)，存儲指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這兩部分信息組成的存儲映象叫做 結(jié)點(diǎn)（ Node） 。 /*刪除成功 */ } 34 物料管理 LILST 34 DataStructures:LiLst 插入、刪除 、 查找的實(shí)現(xiàn)算法： 33 物料管理 LILST 33 DataStructures:LiLst 插入、刪除 、 查找的實(shí)現(xiàn)算法： } /*檢查插入位置的正確性 */ if(j=Llen。 i =1 n 刪除（刪除線性表的第 i 個(gè)結(jié)點(diǎn)） ： 25 12 47 89 36 14 1 2 3 4 5 6 7 8 9 25 12 47 36 14 25 12 47 36 14 25 12 47 36 14 在一般情況下，插在第 i 個(gè)結(jié)點(diǎn)之前，移動 n(i1) 次。 Llen=1。隨機(jī)存?。涸L問任何一個(gè)數(shù)據(jù)元素或結(jié)點(diǎn)花費(fèi)同樣多時(shí)間。 } // Mergelist La Lb 時(shí)間復(fù)雜性 : 和 表 LA、 LB 中的結(jié)點(diǎn)個(gè)數(shù)（之和）成正比。 } } while (i = ) { GetElem(La,i,ai)。 while ( ( i = ) amp。 24 物料管理 LILST 24 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， 20） 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)為遞增序。 20 物料管理 LILST 20 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é)點(diǎn)為遞增序。 16 物料管理 LILST 16 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 和線性表 LB 中的結(jié)點(diǎn)為遞增序。 12 物料管理 LILST 12 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 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)為遞增序。 8 物料管理 LILST 8 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ） 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)為遞增序。 特點(diǎn)： ①同一性 ②有限性 ③有序性 n=0 稱空表 n0 常記作（ a1,a2,… ,an） n: 稱線性表的表長 1. 線性表的定義 4 物料管理 LILST 4 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， 20） 合并的方法如下： LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2） i j k 2. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點(diǎn)為遞增序。1 物料管理 LILST 1 DataStructures:LiLst 線性表的邏輯結(jié)構(gòu)