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