【正文】 a_len， Lb_len 3） i從 1到 La_len， j從 1到 Lb_len 4）分別取 La和 Lb當(dāng)前的值進(jìn)行比較 5）如果 a=b,就把 a插入到 Lc中，反之把 b插入到 Lc中 6）一直到 La或者 Lb結(jié)束為止 7）將剩余的元素直接插入到 Lc中 算法描述： 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 8/58 歸并算法如下所示 : void MergeList(List La， List Lb， List amp。amp。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 11/58 a1 a2 ai an b b+l … … b+(i1)l b+(n1)l … … … … 1 2 i n 空閑 存儲(chǔ)地址 內(nèi)存狀態(tài) 數(shù)據(jù)元素在線性表中的位臵 線性表的順序存儲(chǔ)結(jié)構(gòu)圖 相鄰數(shù)據(jù)元素位臵關(guān)系： LOC(ai+1)=LOC(ai)+l ai的存儲(chǔ)位臵： LOC(ai)=LOC(a1)+(i1) l 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 12/58 define LIST_INIT_SIZE 100 //空間初始分配量 define LISTINCREMENT 10 //空間分配增量 typedef struct{ ElemType *elem。 線性表順序存儲(chǔ)類型定義 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 13/58 （ 1）初始化線性表 void InitList_Sq(SqList amp。 //空表長度為 0 = LIST_INIT_SIZE。 j) //插入位置及之后的元素后移 [j+1]=[j]。e) {//在順序表 L中刪除第 i個(gè)元素，并用 e返回其值 if(i1||i) exit(0)。 j) //被刪元素之后的元素前移 [j] = [j+1]。La， SqList Lb) {// 將所有在順序表 Lb中但不在 La中的數(shù)據(jù)元素插入到 La中 La_len = k = ； Lb_len = ； for (i = 0； i Lb_len； i++) { j = 0； while ((j) amp。 ==+； = (ElemType*)malloc(*sizeof(ElemType))； if (!) exit(0)； // 存儲(chǔ)分配失敗 while(i amp。 while( i ) [k++] = [i++]。 （ 1）順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較： 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 23/58 （ 2）線性鏈表的相關(guān)概念： 25 ZHOU 43 19 ZHENG 37 7 ZHAO 31 37 WU 25 NULL WANG 19 1 SUN 13 頭指針 H 13 QIAN 7 43 LI 1 指針域 數(shù)據(jù)域 存儲(chǔ)地址 31 相關(guān)概念 : 結(jié)點(diǎn)，包括兩個(gè)域 :數(shù)據(jù)域和指針域 頭結(jié)點(diǎn) 首元結(jié)點(diǎn) ZHANG ? ? ? ? WANG ZHAO QIAN SUN LI ZHOU WU ^ H ? ? ? ? ? 線性鏈表的邏輯狀態(tài) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 24/58 （ 3） 存儲(chǔ)結(jié)構(gòu)的定義 typedef struct LNode{ ElemType data。 分析 ：由于單鏈表的結(jié)點(diǎn)的地址都在其前驅(qū)的指針域中，因此，要查找值為 e的結(jié)點(diǎn)，就必須從頭指針出發(fā)尋找，因此，單鏈表 是非隨機(jī)存取 的存儲(chǔ)結(jié)構(gòu)，算法描述如下： LinkList GetElem_L(LinkList L， ElemType e) {//在帶頭結(jié)點(diǎn)的單鏈表 L中，查找值為 e的元素 p=Lnext； while( p amp。 pnext = s。ji1) //尋找第 i1個(gè)結(jié)點(diǎn) { p=pnext； ++j； } if( !p || ji1 ) exit(0)； //i大于表長或者小于 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)時(shí)指針變化狀態(tài) q 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 29/58 算法描述如下： void ListDelete_L(LinkList amp。 while(pnextamp。因此，建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 31/58 用尾插法建立鏈表的算法描述如下： void CreateList_L(LinkList amp。 a1p p next = Lnext。pdata)； //輸入元素值 pnext = Lnext； Lnext = p； //插入到表頭 } } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 34/58 ⑤ 歸并：將兩個(gè)按值遞增單鏈表合并成一個(gè)遞增有序的單鏈表，并利用原來的存儲(chǔ)空間。Lc) { //已知單鏈線性表 La和 Lb的元素按值非遞減排列歸并 La和 //Lb得到新的單鏈線性表 Lc， Lc的元素也按值非遞減排列 pa = Lanext； pb = Lbnext； Lc = pc = La； while(paamp。因此在靜態(tài)鏈表中實(shí)現(xiàn)線性表的操作和動(dòng)態(tài)鏈表相似，插入與刪除操作不用移動(dòng)元素。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(SLinkList amp。space[i].data)； // 輸入 A的元素值 space[r].cur=i； r=i； // 插入到表尾 }// for space[r].cur=0； // 尾結(jié)點(diǎn)的指針為空 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 39/58 for(j=1； j=n； ++j) {// 依次輸入 B的元素，若不在當(dāng)前表中，則插入，否則刪除 scanf(b)； p=S； k=space[S].cur； // k指向集合 A中第一個(gè)結(jié)點(diǎn) while(k!=space[r].cur amp。amp。 P=5,k=6, space[5].cur= space[6].cur=7 space[6].cur= space[0].cur=9 space[0].cur=k=6 （ 7） 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 47/58 循環(huán)鏈表 循環(huán)鏈表 (CircularLinked List)是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 說明： 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 48/58 (a)兩個(gè)鏈表 (b)合并后的表 合并操作： HB=Bnext。 A=B。 } DuLNode, *DuLinkList。e) {// 刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表 L的第 i個(gè)元素 if(!(p=GetElemP_DuL(L， i))) //在 L中確定第 i個(gè)元素的位置指針 p return 0； // p=NULL，即第 i個(gè)元素不存在 e=pdata； ppriornext=pnext； pnextprior=pprior； free(p)； return 1。C) {// 對(duì)用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的兩個(gè)一元多項(xiàng)式 A和 B進(jìn)行相加運(yùn)算，結(jié)果放在 C中 qa=Anext； qb=Bnext； // qa和 qb分別指向 A和 B多項(xiàng)式鏈表中的第一個(gè)結(jié)點(diǎn) C=pre=A； // pre指向 qa的前驅(qū)； C指向多項(xiàng)式 C的頭結(jié)點(diǎn) while (qa a