【正文】 T_SIZE。 //初始存儲(chǔ)容量 }//InitList_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 14/58 （ 2）插入：在線性表的第 i個(gè)元素前插入一個(gè)元素 分析 ：若要在線性表的第 i個(gè)元素前插入一個(gè)元素，除非 i=n+1，否則，須將第 n至第 i（共 ni+1）個(gè)元素依次往后移動(dòng)一個(gè)位臵，如下圖所示 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 插入 25 25 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 9 表的長(zhǎng)度增加 1 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 15/58 順序表的插入 void ListInsert_Sq(SqList amp。L， int i， ElemType e) {//在順序表 L的第 i個(gè)元素之前插入新的元素 e if(i1||i+1) exit(0)； //插入位置不合法 if(=) //當(dāng)前存儲(chǔ)空間已滿，增加空間 { newbase=(ElemType*)realloc(， (+LISTINCREMENT)*sizeof(ElemType))； if(!newbase) exit(0)； //存儲(chǔ)分配失敗 =newbase； //新基址 +=LISTINCREMENT； //增加存儲(chǔ)容量 } for(j = 。 j=i1。 j) //插入位置及之后的元素后移 [j+1]=[j]。 [i1] = e。 //插入 e ++； //表長(zhǎng)增 1 } ListInsert_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 16/58 （ 3）刪除：刪除線性表中的第 i個(gè)元素 分析 ：若要?jiǎng)h除線性表中的第 i個(gè)元素，除非 i=n，否則，須將第 i+1至第 n（共 ni）個(gè)元素依次往前移動(dòng)一個(gè)位置，如下圖所示 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 刪除 24 12 13 21 28 30 42 77 1 2 3 4 5 6 7 序號(hào) 數(shù)據(jù)元素 表的長(zhǎng)度減少 1 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 17/58 順序表的刪除 void ListDelete_Sq(SqList amp。L， int i， ElemType amp。e) {//在順序表 L中刪除第 i個(gè)元素，并用 e返回其值 if(i1||i) exit(0)。 //i值不合法 e=[i1]。 for(j = i1。 j。 j) //被刪元素之后的元素前移 [j] = [j+1]。 ； //表長(zhǎng)減 1 }// ListDelete_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 18/58 插入 /刪除操作時(shí)間復(fù)雜度分析 ?基本操作：移動(dòng)元素操作 ?順序表進(jìn)行插入及刪除操作的時(shí)間復(fù)雜度為 O(n)。 ?插入操作移動(dòng)元素次數(shù)的期望值 )1(11??? ???inpE ni iis?刪除操作移動(dòng)元素次數(shù)的期望值 )(1inqE ni idl?? ???等概率情況下 ( , ) 11?? npi nqi 1?111 ( 1 )12nisinE n in??? ? ? ?? ?111()2ndlinE n in ??? ? ??數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 19/58 （ 4）兩個(gè)順序表的合并 假設(shè)利用兩個(gè)線性表 LA和 LB分別表示兩個(gè)集合 A和 B(即：線性表中的數(shù)據(jù)元素即為集合中的成員 )，現(xiàn)要求一個(gè)新的集合 A=AUB。 void Union(SqList amp。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。amp。 ([j] != [i])) j++； if (j = ) [k++] = [i]； } = k； }//Union 算法 union的時(shí)間復(fù)雜度為 O( ) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 20/58 （ 5）兩個(gè)有序表的合并 void MergeList_Sq(SqList La， SqList Lb， SqList amp。Lc) {// 已知順序線性表 La和 Lb的元素按值非遞減排列， // 歸并 La和 Lb得到新的順序線性表 Lc， Lc的元素也按值非遞減排列 i = j = k = 0。 ==+； = (ElemType*)malloc(*sizeof(ElemType))； if (!) exit(0)； // 存儲(chǔ)分配失敗 while(i amp。amp。 j ) // 歸并 if ( [i] = [j]) [k++] = [i++]。 else [k++] = [j++]。 while( i ) [k++] = [i++]。 // 插入 La的剩余元素 while( j ) [k++] = [j++]。 // 插入 Lb的剩余元素 }// MergeList_Sq 算法 MergeList的時(shí)間復(fù)雜度為 O(+) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 21/58 三、線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 線性鏈表 靜態(tài)鏈表 循環(huán)鏈表 雙向鏈表 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 22/58 線性鏈表 順序存儲(chǔ)結(jié)構(gòu)弱點(diǎn) ：在作插入或刪除操作時(shí)需要移動(dòng)大量元素。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn) ：邏輯上相鄰的元素在物理位臵上不一定相鄰 ,沒有順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn) , 但也失去了順序表可隨機(jī)存取的優(yōu)點(diǎn)。 （ 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。 struct LNode *next。 }LNode, *LinkList。 ^Lana1a2…L^( a ) 非 空 表( b ) 空 表帶 頭 結(jié) 點(diǎn) 的 單 鏈 表數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 25/58 ① 查找：在以 L為頭結(jié)點(diǎn)的單鏈表中查找值為 e的結(jié)點(diǎn)。 分析 ：由于單鏈表的結(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。amp。 pdata != e) p = pnext； return p； } （ 4） 線性鏈表的基本操作 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 26/58 ② 插入：在以 L為頭結(jié)點(diǎn)的單鏈表中的