【正文】 入 (4) 刪除 97 【 學(xué)習(xí)內(nèi)容 】 ? 棧的抽象數(shù)據(jù)類型、順序表示、鏈表表示及相應(yīng)操作 (特別注意棧空和棧滿的條件） ? 隊(duì)列的定義 、 特性 ? 隊(duì)列的抽象數(shù)據(jù)類型 、 順序表示 、 鏈表表示及相應(yīng)操作 （ 特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況 ） ? 棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性 DS。試寫一算法，將 x 插入線性表適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜性。 A、 B，編寫算法將兩表合并為一個(gè)按元素值遞減的線性表 C。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 93 167。 free(p)。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) b a c p 92 ppriornext = pnext。 pnextprior=pprior。 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 90 b c a P ppriornext=pnext。③ pprior = s。 ① snext = p。 sdata = x。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?雙向鏈表圖例 88 x S P a b 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?雙向鏈表圖例 87 b c a p ppriornext= p= pnextproir。 struct node *prior,*next。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?循環(huán)鏈表 操作與單鏈表基本一致 ,循環(huán)條件不同 ?單鏈表 : p或 pnext=NULL ?循環(huán)鏈 : p或 pnext=H h h ^ 85 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表具有單向性的缺點(diǎn) ?單鏈表特點(diǎn) 83 167。 free(Lb)。 pb= pbnext。 } else{pcnext = pb。pc = pa。amp。 Lc = pc = La。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?兩個(gè)有序單鏈表合并為一個(gè)有序單鏈表 (非遞減 ) MergeList_L(Linklist La,LinkList Lb,LinkList Lc){ pa = Lanext。 return OK。 //刪除并釋放結(jié)點(diǎn) *e = q data 。//刪除位置不合理 q = pnext。 ++ j。amp。 j= 0。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?刪除元素 ： 80 167。 return OK。snext = pnext。} //創(chuàng)建新結(jié)點(diǎn) ,數(shù)據(jù)為 x,指針為 NULL s=(LinkList * )malloc(sizeof(LinkList))。}//找第 i1個(gè)結(jié)點(diǎn) if ((p= =NULL )|| (j i1)){ printf( “ 無(wú)效的插入位置 !\n” )。j i1){p=pnext。 while (pamp。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) Status ListInsert_L ( LinkList L, ElemType x, const int i ) { p=L。 return OK； } 77 167。} if(p) return ERROR。 ji){ p = pnext。 While(!p amp。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?在帶頭節(jié)點(diǎn)的單鏈表中查找第 i 個(gè)結(jié)點(diǎn) Status ListSearch_L(LinkList L,int i, ElemType **e){ P = Lnext。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?頭結(jié)點(diǎn) ：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)的一個(gè)結(jié)點(diǎn)。 ?系統(tǒng)回收 p結(jié)點(diǎn)： free(p) 167。 LNode *h,*p 167。 struct node *next。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 43 存儲(chǔ)地址 數(shù)據(jù)域 指針域 ZHOU 43 LI QIAN SUN WANG WU ZHAO ZHENG 1 7 13 19 25 31 37 13 1 NULL 37 7 19 25 ? 定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表，也叫單鏈表 例 線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 72 LI ZHAO QIAN SUN ZHOU WU ZHENG WANG ^ H 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?單鏈表 (線性鏈表 ) 特點(diǎn) : 用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 每個(gè)數(shù)據(jù)元素 ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息 70 ?單鏈表 (線性鏈表 ) 特點(diǎn) : 用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 每個(gè)數(shù)據(jù)元素 ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息 指針 數(shù)據(jù)域 結(jié)點(diǎn) 167。} } } 68 167。[i]=[j]。 while ([j]%2==l) j。 ElemType temp。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) [解 ] 從左向右找到偶數(shù) [i]，從右向左找到奇數(shù) [j]，將兩 者交換；循環(huán)這個(gè)過(guò)程直到 i大于 j為止 67 167。設(shè)計(jì) 把所有奇數(shù)移到所有的偶數(shù)前邊的算法 (要求 時(shí)間最少，輔助空間最少 )。 return 1。 j++) [j1] = 。} for(int j = i+1。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?從線性表中刪除等于給定值的元素 2 if(i = = ){ printf( “ Deleted element is not exist!” )。 i++) if([i] = = itme) break 。 } for(i = 0。 L, const ElemType item){ if( = = 0){ printf( “ L is an empty list!” )。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?刪除算法評(píng)價(jià) 設(shè) Qi是刪除第 i個(gè)元素的概率，則在長(zhǎng)度為 n的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為 ： 64 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?刪 除 一 個(gè) 元 素圖示 1 62 內(nèi)存 a1 a2 ai+1 V數(shù)組下標(biāo) 0 1 i1 n2 i n1 1 2 i 元素序號(hào) i+1 n1 n an ai+2 167。 return (1)。j++) v[j1]=v[j]。 for(j=i。 n=*p。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?刪 除 一 個(gè) 元 素 定義：線性表的刪除是指將第 i（ 1 i n）個(gè)元素刪除，使長(zhǎng)度為 n的線性表 60 167。 ++。 return。 L,const ElemTypeamp。} 58 167。 [i] = item。 j=i 。 i++) if(item [i]) break。} for(int i=0。 item){ if( = = MaxSize){ printf( “ List overflow!” )。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 向線性表中滿足條件的位置插入一個(gè)元素 void Insert(Listamp。 ++。 i ) [i+1] = [i]。 } for(i = – 1。 item){ if( = = MaxSize){ printf(“ List overflow!” )。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?向線性表中表頭插入一個(gè)元素 InsertFront(Listamp。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?插入一個(gè)元素圖示 2 x 55 ? ? ? ?nOnTninnE i snPnii????????????11 2)1(1111則若認(rèn)為??????11)1(nii inPE i s167。 } } 53 167。 *p=++n。j) v[j]=v[j1]。 else { for(j=n。 n=*p。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) )11( ??? ni?插入一個(gè)元素 定義： 線性表的插入是指在第 i 個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素 x，使長(zhǎng)度為 n的線性表 ( a1, a2 , …, a i1, ai, …a n) 變成長(zhǎng)度為 n+1的線性表 (a1, a2, …, a i1, x, ai, … a n ) 52 167。 free(pData )； 167。 50 可以定義為靜態(tài)數(shù)組或變量 DATATYPE library[M]。 float price。 char author[10]。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?線性表的順序存儲(chǔ)示例 （圖書(shū)資料） typedef struct card{ int num。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 元素地址計(jì)算方法 ： lLOC(ai)=LOC(a1)+(i1)*L lLOC(ai+1)=LOC(ai)+L 其中： uL一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù) uLOC(ai)—線性表第 i個(gè)元素的地址 48 a1 an 0 1 n1 1 2 n 內(nèi)存 V數(shù)組下標(biāo) 元素序號(hào) M1 a2 備用空間 167。即用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表 ?特點(diǎn)： ? 實(shí)現(xiàn)邏輯上相鄰 —物理地址相鄰 ? 實(shí)現(xiàn)隨機(jī)存取 ?實(shí)現(xiàn)： （ 一維 ） 數(shù)組 46 下標(biāo)位置 0 1 … i1 i … n1 … MaxSize1 數(shù)組存貯空間 a1 a2 … ai ai+1 … an … 167。 } //若在線性表 B中 }} //找到 ， 將其插入 C 45 167。 //在線性表 B中查 x if (k0) {Insert(C,x,j)。C){ int i， k， j=1； ElemType x； InitList(C)； for (i=1； i=Getlen(A)； i++) { x=GetElem(A,i)。 線性表的類型定義 [解 ] 先始化線性表 C，然后依次檢查線性表 A中的每個(gè)元素，看它是否在線性表 B中；若在線性表 B中，則將其插入到線性表 C中 . 基本運(yùn)算 [例 ] 利用線性表的基本運(yùn)算，編寫將線性表 A和 B中公共元素生成線性表 C的算法 44 167。 //在線性表 A中查找 x if (k0) ListDelete (A， k)。i++){ x=GetElem(B,i)。 for(i=l。A， sqlist B) { //A為引用型參數(shù) int i, k。 42 167。若在表A中，則將其從 A中刪除 。另一方面，在實(shí)際應(yīng)用中，可以根據(jù)具體需要選擇適當(dāng)?shù)幕具\(yùn)算 41 167。否則，返回 NULL 40 167。否則，返回 NULL。 39 167。其作用是刪除線性表 sq的第 i個(gè)元素 ai,使 sq由 (a1， … ， ai1，ai， ai+l， … ， an)變?yōu)?(a1， … ， ai1，ai+1， …