數(shù)據(jù)結(jié)構(gòu)第二章 線性表part2

1、 已知線性表已知線性表LA和和LB中的數(shù)據(jù)元素按值非遞減有序排中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將列，現(xiàn)要求將LA和和LB歸并為一個新的線性表歸并為一個新的線性表LC，且，且LC中的數(shù)據(jù)元素仍按值非遞減有序排列。中的數(shù)據(jù)元素仍按值非遞減有序排列。例如，設(shè)例如，設(shè) LA=(3,5,8,11) i LB=(2,6,8,9,11,15,20) j 則則 LC=(2, 3, 5,6,8,8,9,11,11,15,20) k 例例 2-3 Void MergeList (List La , List Lb, List &Lc) INITIATE(Lc); i=j=1; k=0; /初始化初始

2、化 La_len= LENGTH (La) ; Lb_len= LENGTH (Lb) ; while (i=La_len)& (j=Lb_len) /La和和Lb均非空均非空 GetElem(La,i,ai); GetElem (Lb,j,bj); if (ai=bj) ListInsert(LC, +k,ai); + i else ListInsert(LC,+k,bj); + j ; while (i=La_len) / 插入插入 La 表中剩余元素表中剩余元素 GetElem(La, i+,ai); ListInsert(LC,+k,ai) ; while (j=Lb_len)

3、 / 插入插入 Lb 表中剩余元素表中剩余元素 GetElem(Lb, j+,bj); ListInsert(LC,+k,bj ; / MergeList2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)一、線性表的順序存儲結(jié)構(gòu)一、線性表的順序存儲結(jié)構(gòu)順序映象順序映象二、順序存儲結(jié)構(gòu)的特點二、順序存儲結(jié)構(gòu)的特點三、線性表的順序存貯結(jié)構(gòu)示意圖及描述三、線性表的順序存貯結(jié)構(gòu)示意圖及描述四、線性表的基本操作在順序表中的實現(xiàn)四、線性表的基本操作在順序表中的實現(xiàn)五、順序存儲結(jié)構(gòu)的優(yōu)缺點五、順序存儲結(jié)構(gòu)的優(yōu)缺點一、線性表的順序存儲結(jié)構(gòu)一、線性表的順序存儲結(jié)構(gòu) 順序映象順序映象 最簡單的一種順序映象方法是

4、：最簡單的一種順序映象方法是： 令令y y的存儲位置和的存儲位置和x x的存儲位置相鄰的存儲位置相鄰。 以以 x 的存儲位置和的存儲位置和 y 的存儲位置之間的存儲位置之間某種關(guān)系表示邏輯關(guān)系某種關(guān)系表示邏輯關(guān)系。順序存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)： 用一組地址連續(xù)地址連續(xù)的存儲單元依次存放依次存放線性表中的數(shù)據(jù)元素。 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址稱作線性表的基地址基地址 假設(shè)線性表的每個數(shù)據(jù)元素要占假設(shè)線性表的每個數(shù)據(jù)元素要占c個存儲單個存儲單元，則元，則 LOC(ai+1)=LOC(ai)+c 所有數(shù)據(jù)元素的存儲位置均取決于第一個所有數(shù)據(jù)元素的存儲位置均取決于第

5、一個數(shù)據(jù)元素的存儲位置，即數(shù)據(jù)元素的存儲位置，即 LOC(ai)=LOC(a1)+(i-1)*c 起始地址（基地址）起始地址（基地址）以“存儲位置相鄰存儲位置相鄰”表示有序?qū)Χ㈨樞虼鎯Y(jié)構(gòu)的特點二、順序存儲結(jié)構(gòu)的特點 表中相鄰的兩個元素其物理存儲位置也相鄰。表中相鄰的兩個元素其物理存儲位置也相鄰。即以元素在計算機(jī)內(nèi)物理位置上的相鄰來表示線性即以元素在計算機(jī)內(nèi)物理位置上的相鄰來表示線性表中數(shù)據(jù)元素之間相鄰的邏輯關(guān)系。每個數(shù)據(jù)元素表中數(shù)據(jù)元素之間相鄰的邏輯關(guān)系。每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)；只要

6、確定了起素在線性表中的序號成正比的常數(shù)；只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取。始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取。順順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。 三、線性表的順序存貯結(jié)構(gòu)示意圖及描述三、線性表的順序存貯結(jié)構(gòu)示意圖及描述aia2a1內(nèi)存狀態(tài)內(nèi)存狀態(tài)序號序號存儲地址存儲地址Loc(a1)Loc(a1) + CLoc(a1) + C * (i-1)12iannLoc(a1) + C * (n-1)空閑空閑Loc(a1) + (maxlen-1)*c順序映像的順序映像的 C C 語言描述語言描述typedef struct SqLis

7、t; /俗稱順序表俗稱順序表#define LIST_INIT_SIZE 80 / 線性表存儲空間的初始分配量線性表存儲空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲空間的分配增量線性表存儲空間的分配增量ElemType *elem; / 存儲空間基址存儲空間基址int length; / 當(dāng)前長度當(dāng)前長度int listsize; / 當(dāng)前分配的存儲容量當(dāng)前分配的存儲容量 / ( (以以sizeof(ElemTypesizeof(ElemType) )為單位為單位) )四、線性表的基本操作在順序表中的實現(xiàn)四、線性表的基本操作在順序表中的實現(xiàn)InitList(

8、&L) / 結(jié)構(gòu)初始化結(jié)構(gòu)初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 刪除元素刪除元素Status InitList_Sq( SqList& L ) / 構(gòu)造一個空的線性表構(gòu)造一個空的線性表 / InitList_Sq算法時間復(fù)雜度時間復(fù)雜度： O(1)L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType);if (!L.elem) exit (OVERFLOW);

9、 / 存儲分配失敗存儲分配失敗L.length = 0; / 空表長度為零空表長度為零L.listsize = LIST_INIT_SIZE / 初始存儲容量初始存儲容量return OK;例如：查找順序表例如：查找順序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可見，基本操作是：將順序表中的元素逐個和給定值e相比較。 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) /在順序表中查詢第一個滿

10、足判定條件的數(shù)據(jù)元素，在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素， / 若存在，則返回它的位序，否則返回若存在，則返回它的位序，否則返回 0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的時間復(fù)雜度時間復(fù)雜度為：為：i = 1; / i i 的初值為第的初值為第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值為第的初值為第 1 1 元素的存儲位置元素的存儲位置while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i; else return

11、 0;線性表操作 ListInsert(&L, i, e)的實現(xiàn)：首先分析首先分析:插入元素時，線性表的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)發(fā)生什么變化發(fā)生什么變化？ (a1, , ai-1, ai, , an) 改變?yōu)?(a1, , ai-1, e, ai , , an)a1 a2 ai-1 ai an a1 a2 ai-1 ai ean, 表的長度增加 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序表L的第 i 個元素之前插入新的元素e, / i 的合法范圍為 1iL.length+1 / ListInsert_Sq 算法算法時

12、間復(fù)雜度時間復(fù)雜度為為: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入e+L.length; / 表長增表長增1return OK;if (L.length = L.listsize) / 當(dāng)前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCR

13、EMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲分配失敗 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存儲容量if (i L.length+1) return ERROR; / 插入位置不合法 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序表L的第 i 個元素之前插入新的元素e, / i 的合法范圍為 1iL.length+1 / ListInsert_Sq 算法算法時間復(fù)雜度時間

14、復(fù)雜度為為: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入e+L.length; / 表長增表長增1return OK;考慮移動元素的平均情況考慮移動元素的平均情況: : 假設(shè)在第 i 個元素之前插入的概率為 ， 則在長度為n 的線性表中插入一個元素所需移插入一個元素所需移動元素次數(shù)的期望值動元素次數(shù)的期望值為：ip11) 1(ni

15、iisinpE11) 1(11niisinnE2n 若假定假定在線性表中任何一個位置上進(jìn)行插入插入的概率的概率都是相等相等的，則移動元素的期望值移動元素的期望值為：21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p線性表操作線性表操作 ListDelete(&L, i, &e)的實現(xiàn)的實現(xiàn)：

16、首先分析：首先分析：刪除元素時，刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ (a1, , ai-1, ai, ai+1, , an) 改變?yōu)?(a1, , ai-1, ai+1, , an)ai+1an, 表的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被刪除元素之后的元素左移被刪除元素之后的元素左移-L.length

17、; / 表長減表長減1 1return OK;算法時間復(fù)雜度算法時間復(fù)雜度為為: : O( ListLength(L)p = &(L.elemi-1); / p 為被刪除元素的位置為被刪除元素的位置e = *p; / 被刪除元素的值賦給被刪除元素的值賦給 eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 刪除位置不合法刪除位置不合法考慮移動元素的平均情況考慮移動元素的平均情況: : 假設(shè)刪除第 i 個元素的概率為 , 則在長度為n 的線性表中刪除一個元素所需移動元素次數(shù)的移動元素次數(shù)的期望值期

18、望值為：iqniidlinqE1)(nidlinnE1)(121n 若假定在線性表中任何一個位置上進(jìn)行刪除的概率都是相等的，則移動元素的期望值移動元素的期望值為：21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p = q; +p) *(p-1) = *p; 例如：ListDelete_Sq(L, 5, e) p 在順序存儲結(jié)構(gòu)的線性表中插入或刪除一個數(shù)在順序存儲結(jié)構(gòu)的線性表中插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動元素上，移動次據(jù)元素時，其時間主要耗費在移動元素上，移動次數(shù)不僅依賴于線性表的長度數(shù)不僅依賴于線性表的長度L.length，還依賴于元，還依賴于元素插入或刪除的位置