數(shù)據(jù)結(jié)構(gòu)2-2線性表的順序表示和實(shí)現(xiàn)

1、2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)。用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)。例：例：（34, 23, 67, 43）34236743 4存儲(chǔ)要點(diǎn)存儲(chǔ)要點(diǎn)用一段地址用一段地址連續(xù)連續(xù)的存儲(chǔ)單元的存儲(chǔ)單元依次依次存儲(chǔ)線性表中的數(shù)據(jù)元素存儲(chǔ)線性表中的數(shù)據(jù)元素2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)順序表順序表線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)例：例：（34, 23, 67, 43）34236743存儲(chǔ)空間的起始位置存儲(chǔ)空間的起始位置 4用什么屬性來描述順序表？用什么屬性來描述順序表？順序表的容量（最大長度）順序表的容量（最大長度）順序表的

2、當(dāng)前長度順序表的當(dāng)前長度2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)順序表順序表線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)例：例：（34, 23, 67, 43）34236743 4如何實(shí)現(xiàn)順序表的內(nèi)存分配？如何實(shí)現(xiàn)順序表的內(nèi)存分配？順序表順序表一維數(shù)組一維數(shù)組邏輯相鄰邏輯相鄰位置相鄰位置相鄰如何求得任意元素的存儲(chǔ)地址？如何求得任意元素的存儲(chǔ)地址？ 0 i-2 i-1 n-1 Listsize-1 a1 ai-1 ai an 空閑空閑 長度長度2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)順序表順序表一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲(chǔ)

3、：的順序存儲(chǔ)：cLoc(ai)Loc(a1) 0 i-2 i-1 n-1 Listsize-1 a1 ai-1 ai an 空閑空閑 長度長度Loc(ai)=Loc(a1) + (i - -1)l隨機(jī)存取隨機(jī)存?。涸谠贠(1)時(shí)間內(nèi)存取數(shù)據(jù)元素時(shí)間內(nèi)存取數(shù)據(jù)元素2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)順序表順序表一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲(chǔ)：的順序存儲(chǔ)：cLoc(ai)Loc(a1)C語言中用語言中用一維數(shù)組一維數(shù)組來表示順序表：來表示順序表：2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)#define LISTINCRE

4、MENT 10 /存儲(chǔ)空間的分配增量存儲(chǔ)空間的分配增量typedef struct ElemType *elem; /存儲(chǔ)空間基址存儲(chǔ)空間基址 int length; /線性表當(dāng)前的大小線性表當(dāng)前的大小 int listsize; /當(dāng)前分配的存儲(chǔ)容量當(dāng)前分配的存儲(chǔ)容量SqList;#define LIST_INIT_SIZE 100 /線性表初始分配量線性表初始分配量線性表的初始化：線性表的初始化：2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)Status InitList_Sq (SqList &L) L.elem=(ElemType *) malloc (LIST_INIT_SIZ

5、E * sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; 8 82.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)0a111a222a33 i-1aii n-1ann89 9順序表的特點(diǎn)順序表的特點(diǎn)n關(guān)系線性化關(guān)系線性化n結(jié)點(diǎn)順序存結(jié)點(diǎn)順序存91010n插入插入n刪除刪除n查找查找n線性表的合并線性表的合并101111定義：定義：在第在第i（1 i n）個(gè)元素前插入一個(gè)新的數(shù)據(jù)元素個(gè)元素前插入一個(gè)新的數(shù)據(jù)元素e，使長度為使長度為n的線性表的線性表(a1

6、 ， a2 ， ai-1 ， ai ， an)變成長度為變成長度為n+1的線性表的線性表(a1 ， a2 ， ai-1 ，e， ai ， an)111212插入前：插入前：(a1, , ai-1, ai, , an)插入后：插入后：(a1, , ai-1, e , ai, , an)n 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)插入插入ai-1和和ai之間的邏輯關(guān)系發(fā)生了變化之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化存儲(chǔ)位置要反映這個(gè)變化12131333例：例：（35，12，24，42），），在在a2的位置上插入的位置上插入33。表滿：表滿：L

7、.lengthL.listsize合理的插入位置：合理的插入位置：1iL.length（i指的是元素的序號(hào)）指的是元素的序號(hào)） 435122442a1a2a3a40 1 2 3 4422412335什么時(shí)候不能插入什么時(shí)候不能插入？注意邊界條件注意邊界條件n5. 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)插入插入1314141. 如果元素的插入位置不合理，則插入如果元素的插入位置不合理，則插入位置位置非法非法;2. 如果表滿了，則如果表滿了，則上溢上溢;3. 將最后一個(gè)元素至第將最后一個(gè)元素至第i個(gè)元素分別向后移動(dòng)一個(gè)位置；個(gè)元素分別向后移動(dòng)一個(gè)位置；4. 將元素將元素 e 填入位置填入位置i處；處；5. 表長

8、加表長加1；算法描述算法描述偽代碼偽代碼n 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)插入插入141515Status ListInsert_Sq (SqList &L, int i, ElemType e) If( iL.length +1 ) return ERROR; If(L.length=L.listsize) newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); If(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCRE

9、MENT; /if q=&(L.elemi-1); For(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; Return OK;在第在第i個(gè)位置前插入個(gè)位置前插入e1616最好最好情況（情況（ i=n+1）：）： 基本語句執(zhí)行基本語句執(zhí)行0次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(1)。最壞最壞情況（情況（ i=1）：）： 基本語句執(zhí)行基本語句執(zhí)行n次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(n)。平均平均情況（情況（1in+1）：）： 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)。時(shí)間性能分析時(shí)間性能分析: + +- -+ += =11)=1(nii

10、inp + +- -+ + += =11)=1(11niinn2n=O(n)161717 設(shè)設(shè)Pi是在第是在第i個(gè)元素之前插入一個(gè)元素個(gè)元素之前插入一個(gè)元素的的概率，則在概率，則在長度為長度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的次數(shù)的期望值期望值（平均次數(shù)平均次數(shù)）為：為：+=+-=11)1(niiinPEis nOnTninnEisnPnii=+-+=+=+=112)1(1111則若認(rèn)為171818定義：定義：使長度為使長度為n的線性表的線性表(a1 ， a2 ， ai-1 ， ai ， an)變成長度為變成長度為n-1的線性表的線性表(a

11、1 ， a2 ， ai-1 ，ai+1 ， an)算法分析：算法分析：刪除第刪除第i（1i n）個(gè)元素，需將從第）個(gè)元素，需將從第i+1個(gè)元素至第個(gè)元素至第n個(gè)個(gè)元素依次向前移動(dòng)一個(gè)位置。元素依次向前移動(dòng)一個(gè)位置。181919刪除前：刪除前：( (a1, , ai- -1, ,ai, ,ai+1, , ,an) )刪除后：刪除后：( (a1, , ,ai- -1, ,ai+1, , ,an) ) 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)刪刪 除除ai-1和和ai+1之間的邏輯關(guān)系發(fā)生了變化之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化存儲(chǔ)位置要反

12、映這個(gè)變化192020例：（例：（35, 33, 12, 24, 42），），刪除刪除i=2的數(shù)據(jù)元素。的數(shù)據(jù)元素。仿照順序表的插入操作，完成：仿照順序表的插入操作，完成：1. 分析邊界條件；分析邊界條件；2. 分別給出偽代碼和分別給出偽代碼和C語言描述的算法；語言描述的算法；3. 分析時(shí)間復(fù)雜度。分析時(shí)間復(fù)雜度。 535a1a2a3a40 1 2 3 4422412334a5122442順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)刪刪 除除202121刪除順序表中第刪除順序表中第i個(gè)位置元素個(gè)位置元素eStatus ListDelete_Sq(SqList &L, int i, ElemType &e)If(i

13、L.length) return ERROR;p=&(L.elemi-1); /刪除位置刪除位置e=*p;q=L.elem+L.length-1; /表尾位置表尾位置for(+p;p=q;+p) *(p-1)=*p;-L.length;return OK;212222算法時(shí)間復(fù)雜度：算法時(shí)間復(fù)雜度：n設(shè)設(shè)Qi是刪除第是刪除第i個(gè)元素的概率，則在長度為個(gè)元素的概率，則在長度為n的線性的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的(期望值）期望值）平均次數(shù)為：平均次數(shù)為：=-=niideinQE1)( nOnTninnEnQnidei=-=-=121)(11則若認(rèn)為

14、222323順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)按值查找按值查找 535a1a2a3a40 1 2 3 442241233a5例：在（例：在（35, 33, 12, 24, 42） 中查找值為中查找值為12的元素，的元素，返回在表中的序號(hào)。返回在表中的序號(hào)。iii注意序號(hào)和下標(biāo)之間的關(guān)系注意序號(hào)和下標(biāo)之間的關(guān)系232424在順序表中查找第一個(gè)與在順序表中查找第一個(gè)與e滿足滿足compare（）的元素位置（）的元素位置int LocateElem_Sq(SqList L, ElemType e,Status (*compare(ElemType, ElemType) i=1;p=L.elem; /p為第一個(gè)

15、元素位置為第一個(gè)元素位置while(i=L.length &!(*compare)(*p+,e) +i;if(i=L.length) return i;else return 0;242525252n+1 = =1=*niiip = =1=1niin=O(n)2626void MergeList_Sq( SqList La, SqList Lb, SqList &Lc)pa=La.elem; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType *) malloc( Lc.listsize * siz

16、eof(ElemType);if(!Lc.elem) exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;262727while(pa=pa_last & pb=pb_last) if(*pa= *pb) *pc+=*pa+; else *pc+=*pb+; while(pa=pa_last) *pc+=*pa+;while(pb=pb_last) *pc+=*pb+; 272828順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn) 順序表的優(yōu)點(diǎn)：順序表的優(yōu)點(diǎn)： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；存儲(chǔ)空間； 隨機(jī)存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑?。隨機(jī)存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑?。 順序表的缺點(diǎn)：順序表的缺點(diǎn)： 插入和刪除操作需要移動(dòng)大量元素；插入和刪除操作需要移動(dòng)大量元素； 表的容量難以確定，表的容量難以擴(kuò)充；表的容量難以確定，表的容量難以擴(kuò)充； 造成存儲(chǔ)空間的造成存儲(chǔ)空間的碎片碎片。 282929n 線性表線性表 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)n順序順序表表 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)293030算法練習(xí)算法練習(xí)n設(shè)線性表設(shè)線性表La中的數(shù)據(jù)元素遞增有序，試中的數(shù)據(jù)元素遞增有序，試寫一算法，將寫一算法，將e插入到順序表的適當(dāng)位插入到順序表的適當(dāng)位