嚴蔚敏數(shù)據(jù)結構 (9)

1、2.1 線性表的類型定義2.3 線性表的鏈式表示和實現(xiàn)2.4 一元多項式的表示及相加2.2 線性表的順序表示和實現(xiàn)第二章 線性表12.2 線性表的順序表示和實現(xiàn) 線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。22.2 線性表的順序存儲結構（1）線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。如下圖2.1所示： 線性表的這種機內表示稱做線性表的順序存儲結構或順序映像(sequential mapping)。通常稱這種存儲結構的線性表為順序表。特點：以元素在計算機內“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關系存儲地址 內存狀態(tài) 數(shù)據(jù)元素在線

2、性表中的位序 ba1 1 b+la22 b+(i-1)l ai i b+(n-1)lann b+nl 空閑 b+(maxlen-1)l3（2）求址公式 假設線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。 線性表中第i1個數(shù)據(jù)元素的存儲位置 和第i個數(shù)據(jù)元素的存儲位置 之間滿足下列關系： 線性表的第i個數(shù)據(jù)元素ai的存儲位置為：式中 是線性表的第一個數(shù)據(jù)元素 的存儲位置，通常稱做線性表的起始位置或基地址。 只要確定了存儲線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機存取。線性表的順序存儲結構是一種隨機存取的存儲結構。4順序映像的 C 語言描述typed

3、ef struct SqList; / 俗稱 順序表ElemType *elem; / 存儲空間基址int length; / 當前長度int listsize; / 當前分配的存儲容量 / (以sizeof(ElemType)為單位)#define LIST_INIT_SIZE 100 /線性表存儲空間的初始分配量#define LISTINCREMENT 10 /線性表存儲空間的分配增量5Status InitList_Sq( SqList& L, int maxsize ) / 構造一個最大容量為 maxsize 的順序表 / InitList_Sq算法時間復雜度：O(1)L.elem

4、= new ElemTypemaxsize; / 為順序表分配大小為 maxsize 的數(shù)組空間if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = maxsize;return OK;6序號 數(shù)據(jù)元素 序號 數(shù)據(jù)元素 序號 數(shù)據(jù)元素 序號 數(shù)據(jù)元素 1 121 12 1 12 1 12 2 132 13 2 13 2 13 3 21 3 21 3 21 3 21 4 24 4 24 4 24 4 28 5 28 5 25 5 28 5 30 6 30 6 28 6 30 6 42 7 42 7 30 7 42 7 77 8 77 8 42

5、 8 77 9 77 (a) (b) (a) (b)圖2.2 線性表插入前后的情況 圖2.3 線性表刪除前后的情況 (a)插入前n8 (a)刪除前n8 (b)插入后n9 (b)刪除后n7插入25刪除24（4）線性表的插入和刪除運算7Status ListInsert_Sq (SqList &L, int i, ElemType e) /在順序線性表L中第i個位置之前插入新的元素e，/i的合法值為1iListLength_Sq(L)+1if (iL.length+1)return ERROR;/i值不合法if (L.length=L.listsize) /當前存儲空間已滿，增加分配newbase

6、 = (ElemType *) realloc (L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType);if (!newbase)exit(OVERFLOW);/存儲分配失敗L.elem = newbase;/新基址L.listsize += LISTINCREMENT;/增加存儲容量q = & (L.elemi1);/q為插入位置for (p = & (L.elemL.length1); p=q; p)* (p+1) = *p;/插入位置及之后的元素右移* q = e;/插入e+L.length;/表長增1return OK; /ListIn

7、sert_Sq插入運算 算法2.3如下：8Status ListDelete_Sq (SqList &L, int i, ElemType &e) /在順序線性表L中刪除第i個元素，并用e返回其值/i的合法值為1iListLength_Sq(L)if (iL.length)return ERROR;/i值不合法p = & (L.elemi1);/p為被刪除元素的位置e = *p;/被刪除元素的值賦給eq = L.elem + L.length1;/表尾元素的位置for (+p; p=q; +p)* (p1) = *p;/被刪除元素之后的元素左移L.length;/表長減1return OK;

8、/ListDelete_Sq刪除運算 算法2.4如下：9（5）時間復雜度 從上述算法可見，當在順序存儲結構的線性表中某個位置上插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動元素上，而移動元素的個數(shù)取決于插入或刪除元素的位置。 假設pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時所需移動元素次數(shù)的期望值為： 不失一般性，若在線性表的任何位置插入元素都是等概率的，即 ，上式可化簡為： 對于刪除過程，假設qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素時所需移動元素次數(shù)的期望值為： 同樣假設是等概率的情況，即 ，則有： 結論：由此可見，在順序存儲結構的線性

9、表中插入或刪除一個數(shù)據(jù)元素，平均約移動表中一半元素。若表長為n，則算法ListInsert_Sq和ListDelete_Sq的時間復雜度為O(n)。10 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素， / 若存在，則返回它的位序，否則返回 0 / LocateElem_Sq O( ListLength(L) )if (i = L.length) return i; else return 0; 算法的時間復雜度為：i = 1; / i 的

10、初值為第 1 元素的位序p = L.elem; / p 的初值為第 1 元素的存儲位置while (i = L.length & !(*compare)(*p+, e) +i;(*compare)(*p+, e)/找到滿足條件的元素/ 沒有找到滿足條件的元素11（6）順序表的 算法2.5如下： void MergeList_Sq (SqList La, SqList Lb, SqList &Lc)/已知順序線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。/歸并La和Lb得到新的順序線性表Lc，Lc的數(shù)據(jù)元素也按值非遞減排列。pa = La.elem;pb = Lb.elem;Lc.listsize = Lc.length = La.length + Lb.length;pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType);if (!Lc.elem)exit (OVERFLOW);/存儲分配失敗pa_last = La.elem + La.length 1;pb_last = Lb.elem + Lb.length 1;while (pa = pa_last