嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu) (9)

1、2.1 線性表的類型定義2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4 一元多項(xiàng)式的表示及相加2.2 線性表的順序表示和實(shí)現(xiàn)第二章 線性表12.2 線性表的順序表示和實(shí)現(xiàn) 線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。22.2 線性表的順序存儲(chǔ)結(jié)構(gòu)（1）線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。如下圖2.1所示： 線性表的這種機(jī)內(nèi)表示稱做線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像(sequential mapping)。通常稱這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。特點(diǎn)：以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系存儲(chǔ)地址 內(nèi)存狀態(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）求址公式 假設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。 線性表中第i1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 之間滿足下列關(guān)系： 線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：式中 是線性表的第一個(gè)數(shù)據(jù)元素 的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。 只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取。線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。4順序映像的 C 語言描述typed

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

4、= new ElemTypemaxsize; / 為順序表分配大小為 maxsize 的數(shù)組空間if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = maxsize;return OK;6序號(hào) 數(shù)據(jù)元素 序號(hào) 數(shù)據(jù)元素 序號(hào) 數(shù)據(jù)元素 序號(hào) 數(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）線性表的插入和刪除運(yùn)算7Status ListInsert_Sq (SqList &L, int i, ElemType e) /在順序線性表L中第i個(gè)位置之前插入新的元素e，/i的合法值為1iListLength_Sq(L)+1if (iL.length+1)return ERROR;/i值不合法if (L.length=L.listsize) /當(dāng)前存儲(chǔ)空間已滿，增加分配newbase

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

7、sert_Sq插入運(yùn)算 算法2.3如下：8Status ListDelete_Sq (SqList &L, int i, ElemType &e) /在順序線性表L中刪除第i個(gè)元素，并用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;/表長(zhǎng)減1return OK;

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

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

10、初值為第 1 元素的位序p = L.elem; / p 的初值為第 1 元素的存儲(chǔ)位置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);/存儲(chǔ)分配失敗pa_last = La.elem + La.length 1;pb_last = Lb.elem + Lb.length 1;while (pa = pa_last