【正文】 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 1/58 第 2章 線性表 學(xué)習(xí)目的與要求： 1．了解線性表的邏輯結(jié)構(gòu)； 2．掌握順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法； 3．掌握線性表在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本操作：查找、插入和刪除的算法； 4．能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合； 5．理解靜態(tài)鏈表的定義及使用方法，并區(qū)分與單鏈表的不同。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 2/58 基本內(nèi)容 一、線性表的定義 二、線性表的順序表示與實(shí)現(xiàn) 三、線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 四、一元多項(xiàng)式的表示及相加 五、本章小結(jié) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 3/58 線性結(jié)構(gòu)的特點(diǎn) ：在數(shù)據(jù)元素的非空有限集中 （ 1）存在惟一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素； （ 2）存在惟一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素； （ 3）除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接前驅(qū)； （ 4）除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接后繼。 一、線性表的定義 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 4/58 1. 線性表的定義 線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是n(n≥0)個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 根據(jù)它們之間的關(guān)系可以排成一個(gè)線性序列，記作： (a1， a2， … ， an) 這里的 ai(1≤i≤n)屬于 同一數(shù)據(jù)對象 ， n代表線性表的 表長 ，即線性表中數(shù)據(jù)元素的個(gè)數(shù)。當(dāng) n=0時(shí)，線性表為 空表 。 對于 ai，當(dāng) 1i≤n 時(shí)，它有一個(gè)直接前驅(qū) ai1；當(dāng) 1≤in 時(shí)，它有一個(gè)直接后繼 ai+1。 數(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。L) 初始化線性表 L，設(shè)臵為空表； ListLength(L) 求線性表的長度 ； GetElem(L, i, amp。e) 求表 L中的第 i個(gè)元素，結(jié)果由 e返回； ListInsert(amp。L, i, x) 在線性表中第 i個(gè)元素之后 (或之前 ) 插入一個(gè)新元素 x； ListDelete(amp。L, i, amp。e) 刪除線性表中的第 i個(gè)元素； … … }ADT List 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 6/58 利用上面的基本操作，還可以進(jìn)行一些更復(fù)雜的操作，例如： 已知線性表 La和 Lb中的元素按值非遞減有序排列，現(xiàn)要求將 La和 Lb歸并為一個(gè)新的線性表 Lc，且 Lc中的數(shù)據(jù)元素仍按值非遞減有序排列。 例如，設(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中的元素按照順序逐個(gè)插入到 LC中即可。為使 LC中元素按值非遞減有序排列，可設(shè)兩個(gè)指針 i和 j分別指向 LA和 LB中某個(gè)元素，若設(shè) i當(dāng)前所指的元素為 a， j當(dāng)前所指的元素為 b，則當(dāng)前應(yīng)插入到 LC中的元素 c為： 顯然，指針 i和 j的初值均為 1，在所指元素插入 LC之后，在 LA或 LB中順序后移。 ??????時(shí)當(dāng)時(shí)當(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。Lc) {//已知線性表 La和 Lb中的數(shù)據(jù)元素按值非遞減排列。 //歸并 La和 Lb得到新的線性表 Lc， Lc的數(shù)據(jù)元素也按值非遞減排列。 InitList(Lc)； i=j=1； k=0； La_len=ListLength(La)； Lb_len=ListLength(Lb)； while((i=La_len)amp。amp。(j=Lb_len)) {//La和 Lb均非空 GetElem(La， i， ai)； GetElem(Lb， j， bj)； if(ai=bj) { ListInsert(Lc， ++k， ai)； ++i； } else { Listlnsert(Lc， ++k， bj)； ++j； } } while(i=Lalen) { GetElem(La， i++， ai)； ListInsert(Lc， ++k， ai)； } while(j=Lb_len) { GetElem(Lb， j++， bj)； ListInsert(Lc， ++k， bj)； } }//MergeList 該算法的時(shí)間復(fù)雜度為： O(m+n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 9/58 二、線性表的順序表示與實(shí)現(xiàn) 線性表的順序表示描述 類型定義 基本操作 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 10/58 線性表順序表示 ：是指用一組 地址連續(xù) 的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。 存儲(chǔ)結(jié)構(gòu)示意圖 順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)： 所以：線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) 1）線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）一致； 2）只要確定了存儲(chǔ)線性表的起始位臵，可以計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。 3）做插入或刪除操作時(shí)需移動(dòng)大量元素，效率不高，適合做查詢操作。 數(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ǔ)空間基址 int length。 //當(dāng)前長度 int listsize。 //當(dāng)前分配存儲(chǔ)容量 }SqList。 線性表順序存儲(chǔ)類型定義 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 13/58 （ 1）初始化線性表 void InitList_Sq(SqList amp。L){ // 構(gòu)造一個(gè)空的線性表 L = (ElemType *) malloc (LIST_INIT_SIZE *sizeof(ElemType))。 if ( ! ) exit (0)。 //存儲(chǔ)分配失敗 = 0。 //空表長度為 0 = LIST_INI