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

ElemType*elem;

//存儲空間基址

intlength;

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

//線性表初始分配量線性表的初始化：2.2線性表的順序表示和實現(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線性表的順序表示和實現(xiàn)數(shù)組下標(biāo)結(jié)點內(nèi)容線性表中位序0a111a222a33∶∶∶i-1aii∶∶∶n-1ann899順序表的特點關(guān)系線性化結(jié)點順序存91010順序表的操作實現(xiàn)插入刪除查找線性表的合并101111插入運算定義：在第i（1in）個元素前插入一個新的數(shù)據(jù)元素e，使長度為n的線性表(a1

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

如果元素的插入位置不合理，則插入位置非法;2.如果表滿了，則上溢;3.將最后一個元素至第i個元素分別向后移動一個位置；4.將元素e填入位置i處；5.表長加1；算法描述——偽代碼順序表的實現(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個位置前插入e1616最好情況（i=n+1）：基本語句執(zhí)行0次，時間復(fù)雜度為O(1)。最壞情況（i=1）：基本語句執(zhí)行n次，時間復(fù)雜度為O(n)。平均情況（1≤i≤n+1）：時間復(fù)雜度為O(n)。時間性能分析:?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)161717運算時間復(fù)雜度分析設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的期望值（平均次數(shù)）為：171818結(jié)點刪除運算定義：使長度為n的線性表(a1

，a2

，……，ai-1

，ai

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

，a2

，……，ai-1

，ai+1

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

順序表的實現(xiàn)——刪除ai-1和ai+1之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化192020例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出偽代碼和C語言描述的算法；3.分析時間復(fù)雜度。535a1a2a3a401234422412334a5122442順序表的實現(xiàn)——刪除202121刪除運算：刪除順序表中第i個位置元素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算法時間復(fù)雜度：設(shè)Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的(期望值）平均次數(shù)為：222323順序表的實現(xiàn)——按值查找535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

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

順序表的優(yōu)點：⑴無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間；⑵隨機存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑亍?/p>

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