【正文】 free(pb)。 prenext=qa。 pre=qb。qa=qanext。free(q)。 q=qb。free(qa)。pre=qa。qb) { if(qaexp==qbexp) { sum=qacoef+qbcoef。 while(qaamp。 qa=panext。int sum。所得 pa指向的鏈表即為兩個多項式之和。 一直進行到 qa或 qb有一個為空為止，然后將有剩余結(jié)點的鏈表連接到 “ 和多項式 ” 鏈表尾部。然后 qa、 qb繼續(xù)向后掃描。 (2) qaexp等于 qbexp， 系數(shù)相加。多項式中的每一項為單鏈表中的一個結(jié)點，每個結(jié)點包含三個域：系數(shù)域、指數(shù)域和指針域。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 46頁 線性表的典型應(yīng)用 在數(shù)學(xué)上，一個多項式可寫成下列形式： P(x)=anxn+an1xn1+…..+a 1x1+a0 ， 其中 ai為 xi的非零系數(shù) 。 存儲密度 是指一個結(jié)點中數(shù)據(jù)元素所占的存儲單元數(shù)和整個結(jié)點所占的存儲單元之比。 (1) 基于存儲的考慮 順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定“ MAXSIZE”大小，估計過大，造成浪費，過小造成溢出。對于頻繁進行插入和刪除操作的線性表，適宜采用鏈表結(jié)構(gòu)。 (2) 需要預(yù)先分配足夠大的存儲空間。 (3) 順序表具有按元素序號隨機訪問的特點。 /* 頭指針變量 */ a1 a2 a3 a4 a5 4 5 3 1 2 4 0 1 2 3 4 5 6 data next SL=0 順序表和鏈表的比較 順序存儲有三個 優(yōu)點 ： (1) 方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。 /* 結(jié)點類型 */ SNode sd[MAXSIZE]。 int next 。 ① p ② 靜態(tài)鏈表 靜態(tài)鏈表用數(shù)組實現(xiàn) ， 每個數(shù)據(jù)元素除了存儲數(shù)據(jù)信息外 ，還要存儲邏輯相鄰的下一個數(shù)據(jù)元素在數(shù)組中的位置 ， 可見 ，靜態(tài)鏈表雖然是用數(shù)組實現(xiàn)的 ，但是邏輯相鄰的數(shù)據(jù)元素不一定在物理位置上也相鄰 。 ② pnextprior=pprior。 p x ① ② ③ ④ s a2 1 a2 p a2 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 43頁 2．雙向鏈表中結(jié)點的刪除操作 設(shè) p指向雙向鏈表中待刪除的結(jié)點 。 ③ snext=p。 … H a2 a1 an H 空表 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 42頁 當 p指向雙向循環(huán)鏈表中的某一結(jié)點時，則有以下等式： ppriornext=p； p=pnextprior； 1．雙向鏈表中結(jié)點的插入操作 設(shè) p指向雙向鏈表中某結(jié)點 ， s指向待插入的新結(jié)點 ， 將 *s插入到 *p的前面 ， 插入過程如圖 217所示 ， 尤其要注意操作順序 ，操作過程如下： sprior=p prior。 struct dlnode *prior, *next。特別是如果一根鏈失效了，還可以利用另一根鏈修復(fù)整個鏈表 。 a2 1 a2 an H 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 41頁 prior data next 結(jié)點結(jié)構(gòu) 特點 : (1)可從兩個方向搜索某個結(jié)點。 a2 ∧ 1 a2 an ∧ H 雙向循環(huán)鏈表 時間復(fù)雜度為 O(1) RB b1 bn … a1 an … RA p ① ④ ② ③ 存儲池 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 40頁 雙向鏈表 問題的引出 ： 在單鏈表中，從任何一個結(jié)點可以找到它的后繼結(jié)點，但是尋找它的前趨結(jié)點，就需要從表頭開始順序查找。 free(RBnext)。 a1 a2 an H 非空單向鏈表 H 空鏈表 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 39頁 例如對兩個單循環(huán)鏈表 HA、 HB的連接操作 ， ： p=RA–next。 循環(huán)條件 ： 1. 單鏈表的循環(huán)條件是 p 或 pnext 是否為空。 a1 a2 an H 循環(huán)鏈表 *(rearnext) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 38頁 定義 ： 循環(huán)鏈表是另一種形式的鏈表存儲結(jié)構(gòu)，實現(xiàn)方法是將表中最后一個結(jié)點的指針域指向單鏈表的表頭結(jié)點，這樣就形成了一個 環(huán) 。 a2 ∧ 1 a2 an ∧ H 雙向鏈表 a1 a2 an ∧ H 循環(huán)鏈表 單鏈表 《數(shù)據(jù)結(jié)構(gòu)》 第二章 線 性 表 承德石油高專計算機系 37 202219 }/* Delete_Linkst2 */ 80 76 80 90 ∧ 85 H p q 例如 x =80的情況。 } /* count +1*/ else q=p。 /*逐個判斷結(jié)點值，為 x則刪除 */ free(p)。 while( q next ) { p=qnext 。 q =H 。如何實現(xiàn)？ (2)如果在不帶頭結(jié)點的鏈表中第 i （ i=1） 個結(jié)點前插入一個值為 y的結(jié)點（在鏈表中值為 x的結(jié)點前插入一個值為 y的結(jié)點） ，如何實現(xiàn)？ 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 36頁 (2)刪除所有值為 x的結(jié)點，并返回 1值為 x的結(jié)點個數(shù) 。 (3)鏈表上實現(xiàn)的插入和刪除運算，不用移動結(jié)點，僅需修改指針。 } }/* Del_LinkList */ 時間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 35頁 從上面的討論可以看出 ： (1) 在單鏈表上插入、刪除一個結(jié)點，必須知道其前驅(qū)結(jié)點。 free(q)。} else {q=pnext。 } else { if(pnext==NULL) { printf(＂ 第 i個結(jié)點不存在＂ )。 if (p==NULL) { printf(＂ 第 i1個結(jié)點不存在＂ ) 。 x p q ① ② … H ai1 ai+1 p ① ② q ③ ④ … ai 釋放到存儲池 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 34頁 int Del_LinkList(LinkList H， int i) /* 刪除單鏈表 H上的第 i個數(shù)據(jù)結(jié)點 */ { LinkList p, q。 ① qnext=pnext。 }/* Insert_LinkList */ 時間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 33頁 5. 刪除操作 【 算法 】刪除鏈表中第 i 個結(jié)點。 snext=pnext。 } else { s=(