【正文】 第 2章 線性表 3/58 線性結(jié)構(gòu)的特點 ：在數(shù)據(jù)元素的非空有限集中 （ 1）存在惟一的一個被稱作“第一個”的數(shù)據(jù)元素； （ 2）存在惟一的一個被稱作“最后一個”的數(shù)據(jù)元素； （ 3）除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個直接前驅(qū)； （ 4）除最后一個之外，集合中的每個數(shù)據(jù)元素均只有一個直接后繼。線性表是n(n≥0)個具有相同特性的數(shù)據(jù)元素的有限序列。當(dāng) n=0時，線性表為 空表 。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 5/58 2. 抽象數(shù)據(jù)類型線性表的定義 ADT List{ 數(shù)據(jù)對象： D={ai | ai∈ ElemSet， i=1， 2， … ， n， n≥0 } 數(shù)據(jù)關(guān)系： R={ai1, ai | ai1, ai ∈ D, i=1, 2, …, n } 基本操作： InitList(amp。e) 求表 L中的第 i個元素，結(jié)果由 e返回； ListInsert(amp。L, i, amp。 例如，設(shè) La=(3， 5， 8， 11) Lb=(2， 6， 8， 9， 11， 15， 20) 則 Lc=(2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20) 分析 ：從上述問題要求可知， LC中的數(shù)據(jù)元素或是 LA中的數(shù)據(jù)元素，或是 LB中的數(shù)據(jù)元素，只要先設(shè) LC為空表，然后將 LA和 LB中的元素按照順序逐個插入到 LC中即可。 ??????時當(dāng)時當(dāng)babbaac數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 7/58 1）初始化 i， j， k的值 2）分別求 La和 Lb的長度 La_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。 //歸并 La和 Lb得到新的線性表 Lc， Lc的數(shù)據(jù)元素也按值非遞減排列。amp。 存儲結(jié)構(gòu)示意圖 順序存儲結(jié)構(gòu)特點： 所以：線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu) 1）線性表的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)（物理結(jié)構(gòu)）一致； 2）只要確定了存儲線性表的起始位臵，可以計算出任何一個數(shù)據(jù)元素的存儲地址。 數(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 空閑 存儲地址 內(nèi)存狀態(tài) 數(shù)據(jù)元素在線性表中的位臵 線性表的順序存儲結(jié)構(gòu)圖 相鄰數(shù)據(jù)元素位臵關(guān)系： LOC(ai+1)=LOC(ai)+l ai的存儲位臵： 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。 //當(dāng)前長度 int listsize。 線性表順序存儲類型定義 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 13/58 （ 1）初始化線性表 void InitList_Sq(SqList amp。 if ( ! ) exit (0)。 //空表長度為 0 = LIST_INIT_SIZE。L， int i， ElemType e) {//在順序表 L的第 i個元素之前插入新的元素 e if(i1||i+1) exit(0)； //插入位置不合法 if(=) //當(dāng)前存儲空間已滿，增加空間 { newbase=(ElemType*)realloc(， (+LISTINCREMENT)*sizeof(ElemType))； if(!newbase) exit(0)； //存儲分配失敗 =newbase； //新基址 +=LISTINCREMENT； //增加存儲容量 } for(j = 。 j) //插入位置及之后的元素后移 [j+1]=[j]。 //插入 e ++； //表長增 1 } ListInsert_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 16/58 （ 3）刪除：刪除線性表中的第 i個元素 分析 ：若要刪除線性表中的第 i個元素，除非 i=n，否則，須將第 i+1至第 n（共 ni）個元素依次往前移動一個位置，如下圖所示 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號 數(shù)據(jù)元素 刪除 24 12 13 21 28 30 42 77 1 2 3 4 5 6 7 序號 數(shù)據(jù)元素 表的長度減少 1 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 17/58 順序表的刪除 void ListDelete_Sq(SqList amp。e) {//在順序表 L中刪除第 i個元素，并用 e返回其值 if(i1||i) exit(0)。 for(j = i1。 j) //被刪元素之后的元素前移 [j] = [j+1]。 ?插入操作移動元素次數(shù)的期望值 )1(11??? ???inpE ni iis?刪除操作移動元素次數(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）兩個順序表的合并 假設(shè)利用兩個線性表 LA和 LB分別表示兩個集合 A和 B(即：線性表中的數(shù)據(jù)元素即為集合中的成員 )，現(xiàn)要求一個新的集合 A=AUB。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。 ([j] != [i])) j++； if (j = ) [k++] = [i]； } = k； }//Union 算法 union的時間復(fù)雜度為 O( ) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 20/58 （ 5）兩個有序表的合并 void MergeList_Sq(SqList La， SqList Lb， SqList amp。 ==+； = (ElemType*)malloc(*sizeof(ElemType))； if (!) exit(0)； // 存儲分配失敗 while(i amp。 j ) // 歸并 if ( [i] = [j]) [k++] = [i++]。 while( i ) [k++] = [i++]。 // 插入 Lb的剩余元素 }// MergeList_Sq 算法 MergeList的時間復(fù)雜度為 O(+) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 21/58 三、線性表的鏈?zhǔn)奖硎九c實現(xiàn) 線性鏈表 靜態(tài)鏈表 循環(huán)鏈表 雙向鏈表 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 22/58 線性鏈表 順序存儲結(jié)構(gòu)弱點 ：在作插入或刪除操作時需要移動大量元素。 （ 1）順序存儲與鏈?zhǔn)酱鎯Φ谋容^： 數(shù)據(jù)結(jié)構(gòu)