【文章內(nèi)容簡(jiǎn)介】 第 i個(gè)元素前插入一個(gè)元素 e。 分析 ：由于鏈表的特殊性，在某個(gè)元素前插入一個(gè)元素，無需移動(dòng)元素，只需修改相應(yīng)的指針即可，如下圖所示： 上述指針修改用語句描述即為： snext = pnext。 pnext = s。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 27/58 算法描述如下： void ListInsert_L(LinkList amp。L, int i, ElemType e) {//在帶頭結(jié)點(diǎn)的線性表 L的第 i個(gè)結(jié)點(diǎn)之前插入新的元素 e p=L； j=0； while(pamp。amp。ji1) //尋找第 i1個(gè)結(jié)點(diǎn) { p=pnext； ++j； } if( !p || ji1 ) exit(0)； //i大于表長(zhǎng)或者小于 1 s = (LinkList)malloc(sizeof(LNode))； //生成新結(jié)點(diǎn) sdata = e； snext = pnext； pnext = s； //插入 } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 28/58 ③ 刪除：在以 L為頭結(jié)點(diǎn)的單鏈表中刪除第 i個(gè)元素。 分析 ：在單鏈表中刪除結(jié)點(diǎn)其操作類似于插入操作，無需移動(dòng)元素，只需修改相應(yīng)的指針即可，如下圖所示： 上述指針修改用語句描述即為： q=pnext。 pnext=qnext。 free(q)。 在單鏈表中刪除結(jié)點(diǎn)時(shí)指針變化狀態(tài) q 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 29/58 算法描述如下： void ListDelete_L(LinkList amp。L, int i, ElemType amp。e) {//在帶頭結(jié)點(diǎn)的線性表 L中刪除第 i個(gè)結(jié)點(diǎn) p=L。 j=0。 while(pnextamp。amp。ji1) //尋找第 i個(gè)結(jié)點(diǎn)，及其前趨 p { p=pnext； ++j； } if( !(pnext) || ji1) exit(0)； //刪除位置不合理 q = pnext； pnext = qnext； //刪除并釋放結(jié)點(diǎn) e = qdata； free(q)； } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 30/58 ④ 建表：根據(jù)給定的元素值，建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。 分析 ：根據(jù)前面的插入操作可以看到，整個(gè)可用存儲(chǔ)空間可為多個(gè)鏈表共同享用，每個(gè)鏈表占用的空間不需預(yù)先分配，而是可以由系統(tǒng)應(yīng)需求即時(shí)生成。因此，建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程。即從 “ 空表 ” 的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。建立鏈表的方法有頭插法和尾插法，用尾插法建立鏈表的過程如下所示： La1a2…^anpre pre p p prenext = p。 pre = p。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 31/58 用尾插法建立鏈表的算法描述如下： void CreateList_L(LinkList amp。L， int n) {//輸入 n個(gè)數(shù)據(jù)元素，利用尾插法建立帶頭結(jié)點(diǎn)的線性鏈表 L=(LinkList)malloc(sizeof(LNode))； pre=L。 for(i = 0； i n； ++i) { p = (LinkList)malloc(sizeof(LNode))； scanf(amp。pdata)； //輸入元素值 prenext = p； pre = p； //插入 } prenext = NULL； //修改尾指針 } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 32/58 用頭插法建立鏈表 ? 分析，尾插法使得每次插入的元素都是最后一個(gè)結(jié)點(diǎn)，而頭插法恰恰相反，每次插入的元素都是首元結(jié)點(diǎn)，而且這個(gè)鏈表帶有頭結(jié)點(diǎn)。 a1p p next = Lnext。 Lnext = p。 L ^ Lp a1^ a2p La1^ a2p . . . 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 33/58 用頭插法建立鏈表的算法描述如下： void CreateList_L(LinkList amp。L， int n) {//輸入 n個(gè)數(shù)據(jù)元素，利用頭插法建立帶頭結(jié)點(diǎn)的線性鏈表 L=(LinkList)malloc(sizeof(LNode))； Lnext=NULL； //先建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表 for( i = 0； i n； ++i ) { p = (LinkList)malloc(sizeof(LNode))； //生成新結(jié)點(diǎn) scanf(amp。pdata)； //輸入元素值 pnext = Lnext； Lnext = p； //插入到表頭 } } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 34/58 ⑤ 歸并：將兩個(gè)按值遞增單鏈表合并成一個(gè)遞增有序的單鏈表，并利用原來的存儲(chǔ)空間。 分析 ：在歸并兩個(gè)鏈表為一個(gè)鏈表時(shí)，不需要另建新表的結(jié)點(diǎn)空間，而只需將原來兩個(gè)鏈表中結(jié)點(diǎn)之間的關(guān)系解除，重新按元素值非遞減的關(guān)系將所有結(jié)點(diǎn)鏈接成一個(gè)鏈表即可，算法描述如下： void MergeList_L(LinkList amp。La， LinkList amp。Lb， LinkList amp。Lc) { //已知單鏈線性表 La和 Lb的元素按值非遞減排列歸并 La和 //Lb得到新的單鏈線性表 Lc， Lc的元素也按值非遞減排列 pa = Lanext； pb = Lbnext； Lc = pc = La； while(paamp。amp。pb) //若兩者均不為空 if(padata = pbdata) { pcnext = pa； pc = pa； pa = panext； } else { pcnext = pb； pc = pb； pb = pbnext。 } pcnext = pa?pa： pb； //插入剩余段 ,若 Pa不為空 ,則 pc next = pa //否則 , pc next = pb free(Lb)； //釋放 Lb的頭結(jié)點(diǎn) } 算法的時(shí)間復(fù)雜度為 O(m+n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 35/58 靜態(tài)鏈表 在有的高級(jí)語言中沒有指針這種數(shù)據(jù)類型，此時(shí)，也可借用一維數(shù)組來描述線性鏈表，為了和指針型描述的線性鏈表相區(qū)別，我們給這種用數(shù)組描述的鏈表起名叫 靜態(tài)鏈表 ，其類型說明如下所示： define MAXSIZE 1000 // 鏈表的最大長(zhǎng)度 typedef struct { ElemType data； int cur； //游標(biāo)，指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置 }ponent， SLinkList[MAXSIZE]； 假設(shè) S為 SLinkList型變量，若第 i個(gè)分量表示鏈表的第 k個(gè)結(jié)點(diǎn)，則S[i].cur指示第 k+1個(gè)結(jié)點(diǎn)的位置。因此在靜態(tài)鏈表中實(shí)現(xiàn)線性表的操作和動(dòng)態(tài)鏈表相似，插入與刪除操作不用移動(dòng)元素。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 36/58 例：以靜態(tài)鏈表實(shí)現(xiàn)集合運(yùn)算 (AB)U(BA) 分析 ： 假設(shè)由終端輸入集合元素，先建立表示集合 A的靜態(tài)鏈表 S，而后在輸入集合 B的元素的同時(shí)查找 S表，若存在和 B相同的元素，則從 S表中刪除之，否則將此元素插入 S表。 為使算法清晰起見，我們先給出三個(gè)過程： 1)將整個(gè)數(shù)組空間初始化成一個(gè)鏈表； 2)從備用空間取得一個(gè)結(jié)點(diǎn)； 3)將空閑結(jié)點(diǎn)鏈結(jié)到備用鏈表上 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 37/58 void InitSpace_SL(SLinkList amp。space) { // 將一維數(shù)組 space中各分量鏈成一個(gè)備用鏈表， space[0].cur為頭指針，“ 0”表示空指針 for(i=0； iMAXSIZE1； ++i) space[i].cur= i+1； space[MAXSIZE1].cur=0； }// InitSpace_SL int Malloc_SL(SLinkList amp。space) {// 若備用空間鏈表非空，則返回分配的結(jié)點(diǎn)下標(biāo)，否則返回 0 i=space[0].cur； if (space[0].cur) space[0].cur = space[i].cur； return i； }// Malloc_SL void Free_SL(