【正文】 … an1 線性表（ a0, a1,a2 ... an1 ） 的順序存儲結(jié)構(gòu) 用順序存儲結(jié)構(gòu)存儲的線性表 ——稱為順序表 說明： ? 在順序存儲結(jié)構(gòu)下，線性表元素之間的邏輯關(guān)系，通過元素的存儲順序反映（表示）出來，即邏輯關(guān)系相鄰，物理位置也相鄰； ? 假設(shè)線性表中每個數(shù)據(jù)元素占用 d 個存儲單元，那么，在順序存儲結(jié)構(gòu)中，線性表的第 i個元素的存儲位置與第 1個元素的存儲位置的關(guān)系是： Loc(ai1 ) = Loc( a0 )+ ( i – 1) *d d個單元 Loc( a0 ) Loc(ai1 ) a0 a1 … ai1 ai ai+1 … an1 怎樣在計算機(jī)上實(shí)現(xiàn) 線性表的順序存儲結(jié)構(gòu)？ 因?yàn)楦呒壵Z言中的一維數(shù)組是采用順序結(jié)構(gòu)儲存的，因此我們使用一維數(shù)組來表示線性表，數(shù)組的類型由線性表中的數(shù)據(jù)元素的性質(zhì)決定。 typedef struct sqlist *ptsqlist； 設(shè) A = （ a0 , a1,a2 ,... an1 ）是一線性表， L是 sqlist 類型的結(jié)構(gòu)變量，用于存放線性表 A，則 L在內(nèi)存中的狀態(tài)如圖所示： 1 2 i1 i i+1 n [i] n 存放線性表元素 的一維數(shù)組 順序表通過 元素的存儲順序 反映線性表元素間的邏輯關(guān)系 a0 a1 … ai1 ai ai+1 … an1 二、順序表的基本操作算法 i的元素（ 0≤i≤n 1）并返回該元素 int Empty(ptsqlist list) { if listn==0 return(1)。 return(null)。 return(null)。 return(0)。j=i。 /*長度加 1*/ return(1)。 } for (j=i。 /*長度減 1 */ return(1)。z=listn1。 listelement[a]=listelement[z]。如表 L（ 21， 3， 5， 3， 21， 3， 90， 5）運(yùn)算后變?yōu)?L（ 21， 3， 5， 90） 算法思想應(yīng)該是怎樣的呢？ 相關(guān)代碼： void Purge(ptsqlist list) { int i,j,k。klistn 。 } i=i+1。 ai+1 a1 ai1 a2 ai an 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 1010 1012 1014 1016 1018 1020 1022 1024 1026 用線性鏈表存儲線性表時，數(shù)據(jù)元素之間的關(guān)系是通過保存直接后繼元素的存儲位置來實(shí)現(xiàn)的 線性鏈表 一，線性鏈表的概念 a4 a3 a1 a2 NULL 1010 1024 1014 a1 a4 a2 結(jié)點(diǎn) 數(shù)據(jù)域 指針域 ? 線性鏈表有關(guān)術(shù)語 ? 結(jié)點(diǎn)： 數(shù)據(jù)元素及直接后繼的存儲位置（地址）組成一個數(shù)據(jù)元素的存儲結(jié)構(gòu)，稱為一個結(jié)點(diǎn)； ? 結(jié)點(diǎn)的數(shù)據(jù)域 ： 結(jié)點(diǎn)中用于保存數(shù)據(jù)元素的部分 。 }LNode, *LinkList。 q=H。 pdata=ch。 scanf(ch)。 ? 空指針： 不指向任何結(jié)點(diǎn)，線性鏈表最后一個結(jié)點(diǎn)的指針通常是空指針 。 Lnext=p。 Lnext=NULL。 scanf(%d,amp。 } return(L)。j=0。 j++。 p=headnext。 /* 后移查找指針 */ if(p!=NULL) return p。 int ListInsert(LinkList L,int i,Etype e) { LinkList p。 sdata=e。 } 4. 插入操作 5. 刪除操作 int ListDelete(LinkList L,int i,Etype e) 功能： 刪除線性鏈表的第 i個結(jié)點(diǎn)； 刪除操作主要步驟： 1）查找鏈表的第 i1個元素結(jié)點(diǎn) ,使指針 p指向它 , 將 指針 q指向第 i個結(jié)點(diǎn)； 2）修改第 i1個元素結(jié)點(diǎn)指針，使其指向第 i個元素 結(jié)點(diǎn)的后繼； 3）回收 q指針?biāo)傅牡?i個結(jié)點(diǎn)空間； ai+1 head an ai1 ai a1 刪除前 刪除后 ai+1 head an ai1 ai a1 p q p q 插入操作圖示： pnext=qnext。int j。 q=pnext。 return OK。 pa=Lanext。amp。 } else { pcnext=pb。 free(Lb)。請寫出鏈表增加電視的算法。 }LNode,*LinkList。 while(p!=NULLamp。 } if (p!=NULLamp。 tcost=h。 } return (s)。 a next=q next。 data prior next 結(jié)點(diǎn) (a) 結(jié)點(diǎn)圖示 (b)空的雙向循環(huán)鏈表 headprior=headnext （ c）非空的雙向循環(huán)鏈表 typedef struct DulNode { ElemType data。 ② ppriornext=S。 ② pnextprior=pprior。j++。 if(!p||ji) return 0。 ppriornext=s。 } p ① ② ③ ④ a b e s … … 刪除操作算法 int dList_Delete(DLinkList H,int i,Etype *e) { dLNode *p=Hnext。 }while(p!=Hnextamp。 *e=pdata。 return 1。 若第 i個分量表示鏈表的第 k個結(jié)點(diǎn)，則 s[i].cur指示第k+1個結(jié)點(diǎn)的位置。 for (i=0。 } p0 p1 pn q0 q1 qm List_a List_b N+1 M+1 T（ x） =1－ 2x100+3x10000 通常情況下，多項(xiàng)式的次數(shù)可能很高且變化大，例如： 考慮用系數(shù)和指數(shù)一起來表示多項(xiàng)式的一個項(xiàng)，即用序偶 pi,i 表示多項(xiàng)式的一個非零項(xiàng) pixi(pi0)。 Pnode * next。 *q應(yīng)為結(jié)果多項(xiàng)式的一項(xiàng)，故把 *q插入到 *p之前。否則修改 *p的系數(shù)域并刪除結(jié)點(diǎn) *q。 pre=La。 q!=NULL) if(pexpqexp) { s=qnext。 q=s。 if(x==0) { prenext=pnext。 } p=prenext。 //q右移 } else //pexpqexp時 { pre=p。 /*當(dāng)前線性表長度 */ }。 2)插入 listelement[i]=x。j++) /*向前移動元素 */ listelement[j]= listelement[j+1]。 }LNode, *LinkList。 pnext=pnext next。 struct DulNode *prior。 ③ Snext=p。 p a c b … … ① ② pprior pnext 在不設(shè)“指針” 的編程語言中，用一維數(shù)組表示鏈表。 k p