【正文】 SLinkList[p].cur=k。 define MAXSIZE 1000 typedef struct{ ElemType data； int cur； }Snode,SLinkList[MAXSIZE]； 用數(shù)組的一個(gè)分量表示一個(gè)結(jié)點(diǎn)，同時(shí)用游標(biāo) cur代替指針指示結(jié)點(diǎn)在數(shù)組的相對(duì)位置。 ② pnextprior=pprior。 ④ pprior=S 。 ② ppriornext=S。 struct DulNode *next。 data prior next 結(jié)點(diǎn) typedef struct DulNode { ElemType data。 free(q)。 刪除操作主要步驟： 1）查找鏈表的第 i1個(gè)元素結(jié)點(diǎn) ,使指針 p指向它 , 將 指針 q指向第 i個(gè)結(jié)點(diǎn)； 2）修改第 i1個(gè)元素結(jié)點(diǎn)指針，使其指向第 i個(gè)元素 結(jié)點(diǎn)的后繼； 3）回收 q指針?biāo)傅牡?i個(gè)結(jié)點(diǎn)空間； ai+1 head an ai1 ai a1 p q pnext=qnext。 數(shù)據(jù)域 指針域 head an a1 a2 帶頭結(jié)點(diǎn)的鏈表 ? 鏈表 插入操作主要步驟： 1）查找鏈表 L的第 i1個(gè)結(jié)點(diǎn)； 2）為新元素建立結(jié)點(diǎn)； 3）修改第 i1個(gè)元素結(jié)點(diǎn)的指針和新元素結(jié)點(diǎn)指 針完成插入； ② ① 注意 的順序！ ① ② head an ai1 ai a1 x snext=pnext。 struct Node *next。 2)刪除 listn。j=listn1。 /*插入元素 */ listn++。j) /*向后移動(dòng)元素 */ listelement[j+1]= listelement[j]。 typedef struct sqlist *ptsqlist； 線性表小結(jié) ? 順序表 順序表插入 insert(L, i, x) 步驟： 1)定位 for (j=listn1。/*順序表數(shù)組 */ int n。 p=pnext。 q=s。 s=qnext。 //修改 *p的系數(shù) pre=p。 //刪除 *p free(p)。 //釋放 Lb表的頭結(jié)點(diǎn) } if(pexp==qexp) { x=pcoef+qcoef。 //q右移 }else 處理 pexp＝ qexp和 pexp＜ qexp if(q!=NULL) //若 Lb表未處理完則余下部分鏈入 La表尾 prenext=q。 pre=q。 prenext=q。amp。 q=Lbnext。 La 7 0 3 1 9 8 Lb 8 1 2 6 9 8 4 11 La 7 0 11 1 Lb 2 6 4 11 void PolyAdd(Polyn La,polyn Lb) { p=Lanext。 （ 3） pexp＜ qexp。 *p、 *q兩結(jié)點(diǎn)的系數(shù)就相加，若相加后為 0，則刪除結(jié)點(diǎn) *p與 *q。因?yàn)樯婕暗皆?*p前插入用，所以用指針 pre指向 *p的直接前驅(qū)。 用指針 p、 q分別掃描兩個(gè)多項(xiàng)式，比較當(dāng)前結(jié)點(diǎn) *p、*q的指數(shù)，會(huì)有下列三種情況： （ 1） pexp＞ qexp。 } *Polyn。 int exp。則 T(x)可表示 為： T= (1,0， 2,100， 3,10000) 若只對(duì)多項(xiàng)式求值，則不會(huì)改變多項(xiàng)式的系數(shù)和指數(shù)，宜用順序表；若對(duì)多項(xiàng)式求和，則要進(jìn)行插入、刪除操作，應(yīng)采用鏈表。 return()。ilist_blist_now_size。 ? 基于空間的考慮 順序表的存儲(chǔ)空間是靜態(tài)分配的 鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的 ? 基于語言考慮 線性表的應(yīng)用舉例 ? 一元多項(xiàng)式的表示及相加 數(shù)學(xué)表示： Pn(x)=p0+p1x+p2x2+… +pnxn 在計(jì)算機(jī)中，用線性表 P表示： P = ( p0,p1,p2,… ,pn ) 一元 m次多項(xiàng)式 Qm(x)可表示為： Q = ( q0,q1,q2,… ,qm ) R =( p0+q0,p1+q1,p2+q2,… pm+qm,pm+1,… pn) 設(shè) mn，則相加結(jié)果 Rn(x) = Pn(x) + Qm(x) void addlist(ptsqlist list_a,ptsqlist list_b) { int i。 i=s[i].cur為指針后移（類似于 p=pnext) 在靜態(tài)鏈表中，當(dāng)用戶需要結(jié)點(diǎn)時(shí)，必須向系統(tǒng)的存儲(chǔ)池中的空閑結(jié)點(diǎn)申請(qǐng)。 (a) 修改前狀態(tài) 1 Zhao 2 Qian 3 Sun 4 Li 5 Zhou 6 Wu 7 Zheng 8 Wang 1 10 1 0 1 2 3 4 5 6 7 8 9 10 1 Zhao 2 Qian 3 Sun 4 Li 5 Zhou 6 Wu 7 Zheng 8 Wang 1 Shi 5 1 0 1 2 3 4 5 6 7 8 9 10 8 9 (b) 修改后狀態(tài) 在 Li后插入 Shi； 刪除元素 Zheng shead SN 假設(shè) S為 SLinkList型變量，則 S[0].cur指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置，若 S[0].cur=i，則 S[i].data存儲(chǔ)線性表的第一個(gè)元素，且 S[i].cur指示第二個(gè)結(jié)點(diǎn)在數(shù)組中的位置。 } p a c b … … ① ② 靜態(tài)鏈表 針對(duì)不設(shè)“指針” 的編程語言，怎樣用不連續(xù)的內(nèi)存區(qū)域來描述線性表？我們想到用一維數(shù)組來表示這種情況下的鏈表。 free(p)。 ppriornext=pnext。 if(!p||ji) return 0。amp。j++。 int j=0。 return 1。 snext=p。 sprior=pprior。 if(!(s=(dLNode*)malloc(sizeof(dLNode)))) return 0。ji)。 }while(p!=Hnextamp。 do { p=pnext。 p a c b … … ① ② pprior pnext 插入操作算法 int dList_Insert(DlinkList H,int i,Etype e) { dLNode *p=Hnext。 刪除 ① ppriornext=pnext。 ③ Snext=p。 }dlNode,*DullinkList； head a b head ? 雙向鏈表圖示 p ① ② ③ ④ a b x s … … ? 雙向鏈表的基本操作算法 插入 ① Sprior=pprior。 struct DulNode *prior。 p a a1 an a2 q b b1 bn b2 p a a1 an a2 q b b1 bn b2 存儲(chǔ)數(shù)據(jù)元素 存儲(chǔ)后繼結(jié)點(diǎn) 的地址 存儲(chǔ)前趨結(jié)點(diǎn) 的地址 雙向鏈表 ? 雙向鏈表的概念 雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接后繼元素結(jié)點(diǎn)，另一個(gè)指向直接前趨元素結(jié)點(diǎn)。 b next=p。 q=b next。 }