【正文】 L= D,S ，其中 D={ a0,a1, a2, ... an1} S= {R} R={ a 0,a1 , a1,a2, a2,a3 … a n2, an1 } 圖示表示 ai+1 a0 ai1 a1 ai an1 頂點(diǎn)：表示一個(gè)數(shù)據(jù)元素 邊：表示是數(shù)據(jù)間的順序結(jié)構(gòu)關(guān)系 ? 線性表的基本操作 ? 初始化操作 ： Initiate（ L） 設(shè)定一個(gè)空的線性表 L ； ? 求長度函數(shù) ： Length（ L） 求線性表 L中數(shù)據(jù)元素的個(gè)數(shù) ； ? 查找函數(shù) ： Get（ L,i） 取得線性表 L的第 i個(gè)數(shù)據(jù)元素 ； ? 定位函數(shù) ： Locate（ L,x） 求數(shù)據(jù)元素 x在線性表 L中的位置 ； ? 插入操作 ： Insert（ L,i,x） 在線性表中第 i個(gè)位置插入一個(gè)數(shù)據(jù)元素 。 4. 插入 insert(L, i, x) 功能： 在順序表 L中第 i個(gè)位置后插入一元素插入 一 個(gè)新 元素 x, 插入前線性表為 (a0, a1, a2, … , ai1, ai,… an1 ) 插入后 ,線性表長度為 n+1, 線性表為 (a0, a1, a2, … , ai1, x, ai,… an1 ) 插入前 n=7 插入后 n=8 插入操作示意圖： insert(p,3,11) 12 34 3 11 27 16 147 44 a0 a1 a2 a3 a4 a5 a6 a7 11 12 34 3 27 16 147 44 a0 a1 a2 a3 a4 a5 a6 a7 插入操作算法 int Insert(ptsqlist list,int i,elementtype x) { int j。j++) /*向前移動(dòng)元素 */ listelement[j]= listelement[j+1]。 while (ilistn) { j=i+1。 LinkList H,p,q。 Lnext=p。int j。 } 4. 插入操作 int ListInsert(LinkList L,int i,Etype e) 功能： 在線性鏈表的第 i個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(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 head an ai1 ai a1 插入前 插入后 x snext=pnext。 p=Get_List_Node(L,i1)。pc=pa。 q=s。如將一個(gè)鏈表鏈在另一個(gè)鏈表的后面； rear a1 an a2 p=anext。 int j=0。 do { p=pnext。 ? 順序表和鏈?zhǔn)奖淼谋容^ ? 基于時(shí)間的考慮 順序存儲(chǔ)是一種隨機(jī)存取的結(jié)構(gòu)， 而鏈表則是一種順序存取的結(jié)構(gòu)。 （ 2） pexp＝ qexp。 free(pb)。j=i。 ? 循環(huán)鏈表的概念 循環(huán)鏈表是線性表的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它的特點(diǎn)是將線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的頭結(jié)點(diǎn) ? 循環(huán)鏈表圖示 (c) 給出尾指針的循環(huán)鏈表 rear a1 an a2 ? 雙向鏈表 雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接后繼元素結(jié)點(diǎn)，另一個(gè)指向直接前趨元素結(jié)點(diǎn)。 ? 靜態(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 SLinkList[k].cur= SLinkList[p].cur。 pnext=s。 } pexp＝ qexp和 pexp＜ qexp的處理部分 為了把線性表的表元素和當(dāng)前長度整合作為該線性表的特性，我們定義一個(gè)結(jié)構(gòu)體如下： struct sqlist { elementtype element[Maxnum]。 //*q插入 *pre之后 qnext=p。 對兩個(gè)多項(xiàng)式 La、 Lb，可以這樣實(shí)現(xiàn)運(yùn)算 La+Lb： 實(shí)現(xiàn)方法：把多項(xiàng)式 Lb的元素插入 La中。 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ù)組的相對位置。 pprior=s。 ④ pprior=S 。 qnext=t。 int number。 Lc=pc=La。 free(q)。amp。 pnext=Lnext。 return H。 存儲(chǔ)數(shù)據(jù)元素 存儲(chǔ)直接后繼 結(jié)點(diǎn)的地址 怎樣在計(jì)算機(jī)上 實(shí)現(xiàn)線性鏈表？ 結(jié)點(diǎn)變量圖示 LNode ：結(jié)構(gòu)類型名； LNode類型結(jié)構(gòu)變量有兩個(gè)域： data： 用于存放線性表的數(shù)據(jù)元素， next： 用于存放元素直接后繼結(jié)點(diǎn)的地址； 該類型結(jié)構(gòu)變量用于表示線性鏈表中的一個(gè)結(jié)點(diǎn)； data next LNode類型 結(jié)構(gòu)變量 p p是 LNode類型的指針變量 線性鏈表的結(jié)點(diǎn)類型定義及指向結(jié)點(diǎn)的指針類型定義 typedef struct Node { Etype data。 } } a0 a1 … ai1 ai ai+1 … an1 mid 怎樣分析插入和刪除算法 的 T（ n）呢？ 在下標(biāo)為 i的位置 (第 i+1個(gè)位置 )前插入 元素下標(biāo) 移動(dòng)元素個(gè)數(shù) 0 n 1 n1 i ni n1 1 n 0 三、算法時(shí)間復(fù)雜度分析 在順序表中插入元素，時(shí)間主要耗費(fèi)在移動(dòng)元素上，而移動(dòng)的個(gè)數(shù)取決于插入的位置以及表的長度。 if (i0||i=listn){ /*位置不合理 */ printf(“not exist!\n”)。 return(list)。 2. 1 線性表的基本概念 ? 線性表的定義 線性表是 n 個(gè)類型相同數(shù)據(jù)元素的有限序列， Linearlist=(D,R) 其中： D={ai | ai ∈ datatype , i=0,1,…n 1} R={ai,ai+1| ai ,ai+1 ∈ D, 1≤i≤n1 } 或記作（ a0, a1, a2, …, a n1 ）。 /*當(dāng)前線性表長度 */ }。 } for (j=listn1。 a=0。 }else j=j+1。) { p=(LinkList)malloc(sizeof(LNode))。 L=(LinkList)malloc(sizeof(LNode))。ji) {