【正文】 *prior, *next。 }DLNode, *DLinkList。 … H a2 a1 an H 空表 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 42頁 當 p指向雙向循環(huán)鏈表中的某一結點時，則有以下等式： ppriornext=p； p=pnextprior； 1．雙向鏈表中結點的插入操作 設 p指向雙向鏈表中某結點 ， s指向待插入的新結點 ， 將 *s插入到 *p的前面 ， 插入過程如圖 217所示 ， 尤其要注意操作順序 ，操作過程如下： sprior=p prior。 ② ppriornext=s。 ③ snext=p。 ④ pprior=s。 p x ① ② ③ ④ s a2 1 a2 p a2 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 43頁 2．雙向鏈表中結點的刪除操作 設 p指向雙向鏈表中待刪除的結點 。 ① ppriornext=pnext。 ② pnextprior=pprior。 ③ free(p)。 ① p ② 靜態(tài)鏈表 靜態(tài)鏈表用數(shù)組實現(xiàn) ， 每個數(shù)據(jù)元素除了存儲數(shù)據(jù)信息外 ，還要存儲邏輯相鄰的下一個數(shù)據(jù)元素在數(shù)組中的位置 ， 可見 ，靜態(tài)鏈表雖然是用數(shù)組實現(xiàn)的 ，但是邏輯相鄰的數(shù)據(jù)元素不一定在物理位置上也相鄰 。 a1 a2 a3 a4 a5 4 5 3 1 2 4 0 1 2 3 4 5 6 data next SL=0 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 44頁 typedef struct {ElemType data 。 int next 。 }SNode 。 /* 結點類型 */ SNode sd[MAXSIZE]。 int SL。 /* 頭指針變量 */ 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)。 (2) 不用為表示結點間的邏輯關系而增加額外的存儲開銷。 (3) 順序表具有按元素序號隨機訪問的特點。 但它也有兩個 缺點 ： (1) 插入、刪除操作時，平均移動大約表中一半元素，效率低。 (2) 需要預先分配足夠大的存儲空間。 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 45頁 在實際中怎樣選取存儲結構的幾點考慮： (2) 基于運算的考慮 如果對線性表的主要操作是查找，適宜采用順序表結構。對于頻繁進行插入和刪除操作的線性表，適宜采用鏈表結構。 (3)基于環(huán)境的考慮 順序表的實現(xiàn)基于數(shù)組類型，鏈表的操作是基于指針。 (1) 基于存儲的考慮 順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定“ MAXSIZE”大小，估計過大，造成浪費，過小造成溢出。 鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低。 存儲密度 是指一個結點中數(shù)據(jù)元素所占的存儲單元數(shù)和整個結點所占的存儲單元之比。顯然順序表的存儲密度為 1，鏈式存儲結構的存儲密度小于１。 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 46頁 線性表的典型應用 在數(shù)學上，一個多項式可寫成下列形式： P(x)=anxn+an1xn1+…..+a 1x1+a0 ， 其中 ai為 xi的非零系數(shù) 。 可采用單鏈表來表示。多項式中的每一項為單鏈表中的一個結點，每個結點包含三個域：系數(shù)域、指數(shù)域和指針域。 現(xiàn)有多項式： (x) =5 x9+8 x7+3 x 2 可表示為： pa ∧ 2 3 7 8 9 5 exp coef next 系數(shù)域 指數(shù)域 指針域 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 47頁 現(xiàn)在設有兩個多項式：做相加運算： A(x)=5 x9+8 x7+3 x 2 B(x)=6x12+10 x93 x 212 pb 0 12 ∧ 2 3 9 10 12 6 pa 2 3 ∧ 7 8 9 5 運算前 pa 0 12 ∧ 7 8 9 15 12 6 運算后 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 48頁 核心算法 ：首先設三個指針變量： pre、 qa 和 qb，其中 pre 永遠指向 “ 和多項式 ” 鏈表的尾結點， qa和qb分別從多項式 pa和 pb鏈表的首項開始掃描，比較 qa和 qb所指結點指數(shù)域的值，可能出現(xiàn)下列三種情況之一 ： (1) qaexp大于 qbexp， qa繼續(xù)向后掃描。 (2) qaexp等于 qbexp， 系數(shù)相加。若結果不為零，將結果放人 qacoef中，并刪除 qb所指結點，否則同時刪除 qa和 qb所指結點。然后 qa、 qb繼續(xù)向后掃描。 (3)qaexp小于 qbexp， 則將 qb 結點插入到 qa所指結點之前，然后 qb繼續(xù)向后掃描。 一直進行到 qa或 qb有一個為空為止，然后將有剩余結點的鏈表連接到 “ 和多項式 ” 鏈表尾部。 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 49頁 掃描過程一直進行到 qa或 qb有一個為空為止，然后將有剩余結點的鏈表接在結果鏈表上。所得 pa指向的鏈表即為兩個多項式之和。 算法： Polyadd （ void ployadd(PNode *pa,PNode *pb) { PNode *qa,*qb,*q,*pre。int sum。 pre=pa。 qa=panext。qb=pbnext。 while(qaamp。amp。qb) { if(qaexp==qbexp) { sum=qacoef+qbcoef。 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 50頁 if(sum){ qacoef=sum。pre=qa。 } else {prenext=qanext。free(qa)。} qa=prenext。 q=qb。qb=qbnext。free(q)。} } else { if(qaexpqbexp) { pre=qa。qa=qanext。 } else{prenext=qb。 pre=qb。 qb=qbnext。 prenext=qa。} } } if(qb) prenext=qb。 free(pb)。 }/* ployadd */ 算法的時間復雜度為 O(m+n) 數(shù)據(jù)結構 (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 51頁 線性表的概念及表示方法 線性表的兩種存儲方式： 順序存儲 和 鏈式存儲 線性表的基本運算及其實現(xiàn)算法 線性表在兩種存方式下的運算實現(xiàn) 線性表的典型應用 小 結