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

2.2線性表的順序表示和實(shí)現(xiàn)用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)。例：（34,23,67,43）342367434存儲(chǔ)要點(diǎn)用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素2.2線性表的順序表示和實(shí)現(xiàn)順序表——線性表的順序存儲(chǔ)結(jié)構(gòu)例：（34,23,67,43）34236743存儲(chǔ)空間的起始位置4用什么屬性來(lái)描述順序表？順序表的容量（最大長(zhǎng)度）順序表的當(dāng)前長(zhǎng)度2.2線性表的順序表示和實(shí)現(xiàn)順序表——線性表的順序存儲(chǔ)結(jié)構(gòu)例：（34,23,67,43）342367434如何實(shí)現(xiàn)順序表的內(nèi)存分配？順序表一維數(shù)組邏輯相鄰位置相鄰如何求得任意元素的存儲(chǔ)地址？0…i-2i-1…n-1Listsize-1a1…ai-1ai…an空閑長(zhǎng)度2.2線性表的順序表示和實(shí)現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲(chǔ)：cLoc(ai)Loc(a1)0…i-2i-1…n-1Listsize-1a1…ai-1ai…an空閑長(zhǎng)度Loc(ai)=Loc(a1)+(i-1)×l隨機(jī)存?。涸贠(1)時(shí)間內(nèi)存取數(shù)據(jù)元素2.2線性表的順序表示和實(shí)現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲(chǔ)：cLoc(ai)Loc(a1)C語(yǔ)言中用一維數(shù)組來(lái)表示順序表：2.2線性表的順序表示和實(shí)現(xiàn)#defineLISTINCREMENT10//存儲(chǔ)空間的分配增量typedefstruct{

ElemType*elem;

//存儲(chǔ)空間基址

intlength;

//線性表當(dāng)前的大小intlistsize;//當(dāng)前分配的存儲(chǔ)容量}SqList;#defineLIST_INIT_SIZE100

//線性表初始分配量線性表的初始化：2.2線性表的順序表示和實(shí)現(xiàn)StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}

882.2線性表的順序表示和實(shí)現(xiàn)數(shù)組下標(biāo)結(jié)點(diǎn)內(nèi)容線性表中位序0a111a222a33∶∶∶i-1aii∶∶∶n-1ann899順序表的特點(diǎn)關(guān)系線性化結(jié)點(diǎn)順序存91010順序表的操作實(shí)現(xiàn)插入刪除查找線性表的合并101111插入運(yùn)算定義：在第i（1in）個(gè)元素前插入一個(gè)新的數(shù)據(jù)元素e，使長(zhǎng)度為n的線性表(a1

，a2

，……，ai-1

，ai

，……，an)變成長(zhǎng)度為n+1的線性表(a1

，a2

，……，ai-1

，e，ai

，……，an)111212插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,e

,ai,…,an)順序表的實(shí)現(xiàn)——插入ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化12131333例：（35，12，24，42），在a2的位置上插入33。表滿：L.length>L.listsize合理的插入位置：1≤i≤L.length（i指的是元素的序號(hào)）435122442a1a2a3a401234422412335什么時(shí)候不能插入？注意邊界條件5.順序表的實(shí)現(xiàn)——插入1314141.

如果元素的插入位置不合理，則插入位置非法;2.如果表滿了，則上溢;3.將最后一個(gè)元素至第i個(gè)元素分別向后移動(dòng)一個(gè)位置；4.將元素e填入位置i處；5.表長(zhǎng)加1；算法描述——偽代碼順序表的實(shí)現(xiàn)——插入141515StatusListInsert_Sq(SqList&L,inti,ElemTypee){If(i<1||i>L.length+1)returnERROR;If(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));If(!newbase)exit(OVERFLOW);L.elem=newbase;

L.listsize+=LISTINCREMENT;}//ifq=&(L.elem[i-1]);For(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;ReturnOK;}插入算法：在第i個(gè)位置前插入e1616最好情況（i=n+1）：基本語(yǔ)句執(zhí)行0次，時(shí)間復(fù)雜度為O(1)。最壞情況（i=1）：基本語(yǔ)句執(zhí)行n次，時(shí)間復(fù)雜度為O(n)。平均情況（1≤i≤n+1）：時(shí)間復(fù)雜度為O(n)。時(shí)間性能分析:?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)161717運(yùn)算時(shí)間復(fù)雜度分析設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的期望值（平均次數(shù)）為：171818結(jié)點(diǎn)刪除運(yùn)算定義：使長(zhǎng)度為n的線性表(a1

，a2

，……，ai-1

，ai

，……，an)變成長(zhǎng)度為n-1的線性表(a1

，a2

，……，ai-1

，ai+1

，……，an)算法分析：刪除第i（1≤i≤n）個(gè)元素，需將從第i+1個(gè)元素至第n個(gè)元素依次向前移動(dòng)一個(gè)位置。181919刪除前：(a1,…,ai-1,ai,ai+1,…,an)刪除后：(a1,…,ai-1,ai+1,…,an)

順序表的實(shí)現(xiàn)——?jiǎng)h除ai-1和ai+1之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化192020例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出偽代碼和C語(yǔ)言描述的算法；3.分析時(shí)間復(fù)雜度。535a1a2a3a401234422412334a5122442順序表的實(shí)現(xiàn)——?jiǎng)h除202121刪除運(yùn)算：刪除順序表中第i個(gè)位置元素eStatusListDelete_Sq(SqList&L,inti,ElemType&e){If(i<1||i>L.length)returnERROR;p=&(L.elem[i-1]);//刪除位置e=*p;q=L.elem+L.length-1;//表尾位置for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}212222算法時(shí)間復(fù)雜度：設(shè)Qi是刪除第i個(gè)元素的概率，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的(期望值）平均次數(shù)為：222323順序表的實(shí)現(xiàn)——按值查找535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值為12的元素，返回在表中的序號(hào)。iii注意序號(hào)和下標(biāo)之間的關(guān)系232424查找運(yùn)算：在順序表中查找第一個(gè)與e滿足compare（）的元素位置intLocateElem_Sq(SqListL,ElemTypee,Status(*compare(ElemType,ElemType))){i=1;p=L.elem;//p為第一個(gè)元素位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}242525查找算法分析：252n+1?=1=*niiip?=1=1niin=O(n)2626合并運(yùn)算：合并成一個(gè)有序表voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){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;262727合并運(yùn)算：while(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)

順序表的優(yōu)點(diǎn)：⑴無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；⑵隨機(jī)存取：可以快速地存取表中任一位置的元素。

順序表的缺點(diǎn)：⑴插入和刪除操作需要移動(dòng)大量元素；⑵表的容量難以確定，表的容量難以擴(kuò)充；⑶造成存