項目二 線性表-順序存儲課件

項目二線性表項目二線性表項目二線性表任務(wù)一：線性表的定義和基本運算任務(wù)二：線性表的順序存儲結(jié)構(gòu)任務(wù)三：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，及它們之間的相互關(guān)系；定義與之相適應(yīng)的運算；設(shè)計相應(yīng)的算法；分析算法的效率。項目二線性表任務(wù)一：線性表的定義和基本運算任務(wù)一線性表的定義和基本操作一、線性表線性表是n個數(shù)據(jù)元素的有限序列，記為：L=(a1，a2，……，an)數(shù)據(jù)元素之間的關(guān)系是：ai-1領(lǐng)先于ai

，ai領(lǐng)先于ai+1

。稱ai-1是ai的直接前驅(qū)元素；ai+1是ai的直接后繼元素。除a1外，每個元素有且僅有一個直接前驅(qū)元素；除an外，每個元素有且僅有一個直接后繼元素。線性表中數(shù)據(jù)元素的個數(shù)n（n>=0）稱為線性表的長度，當(dāng)n=0，稱為空表。任務(wù)一線性表的定義和基本操作一、線性表數(shù)據(jù)元素之間的關(guān)系是任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：ADTList{

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,……n,n>=0}{稱n為線性表的表長；

稱n=0時的線性表為空表。}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}{設(shè)線性表為(a1，a2，……，an)，稱i為ai在線性表中的位序}

基本操作：{結(jié)構(gòu)初始化}InitList(L)

操作結(jié)果：構(gòu)造一個空的線性表

{銷毀結(jié)構(gòu)}DestroyList(L)

初始條件：線性表已存在

操作結(jié)果：構(gòu)造一個空的線性表任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：AD任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{引用型操作}ListEmpty(L)ListLength(L)PriorElem(L,e)NextElem(L,e)GetElem(L,i)Locate(L,e)任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{引ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。ListEmpty(L)ListLength（L）初始條件：線性表L已存在。操作結(jié)果：返回L中元素的個數(shù)。PriorElem（L,e）初始條件：線性表L已存在。操作結(jié)果：若e是L的元素，但不是第一個，則返回它的前驅(qū)，否則操作失敗。ListLength（L）NextElem（L,e）初始條件：線性表L已存在。操作結(jié)果：若e是L的元素，但不是最后一個，則返回e的后繼，否則操作失敗。GetElem（L，i）初始條件：線性表L已存在，1<=i<=LengthList(L)操作結(jié)果：返回L中第i個元素的值NextElem（L,e）Locate（L，e）初始條件：線性表L已存在。操作結(jié)果：返回L中e的位序。若這樣的元素不存在，則返回值0Locate（L，e）任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{加工型操作}ClearList(L)InsertList(L，i,e)DeleteList(L，i,e)任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{加ClearList（L）初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。InsertList（L，i，e）初始條件：線性表L已存在。1<=i<=LengthList(L)+1操作結(jié)果：在L的第i個元素之前插入新的元素e，L的長度增1。ClearList（L）DeleteList（L，i，e）初始條件：線性表L已存在。1<=i<=LengthList(L)操作結(jié)果：刪除L的第i個元素，并用e返回其值，L的長度減1。DeleteList（L，i，e）利用上述定義的線性表，可以完成其他更復(fù)雜的操作。利用上述定義的線性表，可以完成其他更復(fù)雜的操作。任務(wù)一線性表的定義和基本操作例2-1求兩個集合的并集，即A=A∪B分析：設(shè)A、B分別由兩個線性表LA、LB表示，要求將LB中存在而LA中不存在的數(shù)據(jù)元素插入到表LA中任務(wù)一線性表的定義和基本操作例2-1求兩個集合的并集，即任務(wù)一線性表的定義和基本操作算法描述如下（類C）：voidUnion(Liner_ListLA,Liner_ListLB){LA.len=ListLength(LA);LB.len=ListLength(LB);//求線性表的長度for(i=1;i<=LB.len;i++){//LB中第i個元素在LA中不存在，則將其插入到LA中if(!Locate(LA,GetElem(LB,i)))InsertList(&LA,++LA.len,GetElem(LB,i));}}算法思想：依次從LB中取出一個元素；判斷LA中是否存在；若不存在，則插入到LA中。任務(wù)一線性表的定義和基本操作算法描述如下（類C）：void任務(wù)一線性表的定義和基本操作例2-2歸并兩個有序的線性表LA和LB為一個新的線性表算法思想：（1）初始化：置LC為空表，設(shè)置變量i，j，初值為1，分別指向LA和LB的第一個元素，k表示LC的長度，初值為0

。（2）當(dāng)i<=LENGTH(LA)ANDJ<=LENGTH(LB)時，判斷：若i所指的元素<=j所指的元素，則將i所指的元素插入在LC的k+1，并且i，k的值分別加1；否則，將j所指的元素插入在LC的k+1前，并且j，k的值分別加1（3）重復(fù)（2）直到某個表的元素插入完畢。（4）將未插入完的表的余下的元素，依次插入在LC后。任務(wù)一線性表的定義和基本操作例2-2歸并兩個有序的線性表任務(wù)一線性表的定義和基本操作算法設(shè)計如下（類C）：voidMerge_List(Liner_ListLA,Liner_ListLB,Liner_ListLC){LA.len=ListLength(LA);LB.len=ListLength(LB);//求線性表的長度InitList(LC);//初始化線性表LCwhile(i<=LA.len&&j<=LB.len)//如果LA中第i個元素小于LB中//第j個元素,把LA中第i個元素插入到LC中，否則將LB中第j個元素插入到if(GetElem(LA,i)<=GetElem(LB,j)){InsertList(LC,k+1,GetElem(LA,i));k++;i++;}else{InsertList(LC,k+1,GetElem(LB,j));k++;j++;}while(i<=LA.len){InsertList(LC,k+1,GetElem(LA,i));k++;i++;}while(j<=LB.len){InsertList(LC,k+1,GetElem(LB,j));k++;j++;}}任務(wù)一線性表的定義和基本操作算法設(shè)計如下（類C）：void任務(wù)一線性表的定義和基本操作算法分析：該算法中包含了三個WHILE語句，其中，第一個處理了某一張表的全部元素和另一張表的部分元素；后兩個WHILE循環(huán)只可能有一個執(zhí)行，用來完成將未歸并到LC中的余下部分元素插入到LC中，“插入”是估量歸并算法時間復(fù)雜度的基本操作，其語句頻度為：

ListLength(LA）+ListLength(LB）該算法的時間復(fù)雜度為：

O（ListLength(LA）+ListLength(LB）），若LA和LB的元素個數(shù)為同數(shù)量級n，則該算法的時間復(fù)雜度為O（n）任務(wù)一線性表的定義和基本操作算法分析：該算法中包含了三個W任務(wù)二線性表的順序存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元依次存儲線性表的元素。設(shè)線性表的每個元素占用k個存儲單元，則第i個元素ai的存儲位置為：Loc(ai)=Loc（a1）+（i-1）*k,其中，Loc（ai）為線性表的起止任務(wù)二線性表的順序存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。

若已知線性表的起始位置（基地址）和表中每個數(shù)據(jù)元素所占存儲單元的大小k，就可以計算出線性表中任意一個數(shù)據(jù)元素的存儲地址，這種存取元素的方法稱為隨機存取法任務(wù)二線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。若已知線性表任務(wù)二線性表的順序存儲結(jié)構(gòu)線性表順序存儲結(jié)構(gòu)的定義為：#defineMAXSIZE100//線性表的最大長度typedefstruct

{ElemTypeelem[MAXSIZE];//存儲線性表中數(shù)據(jù)元素的數(shù)組intlength;//線性表的當(dāng)前長度}SeqList;typedefstruct

{ElemType*elem;//線性表中數(shù)據(jù)元素的基地址intlength;//線性表的當(dāng)前長度intlistsize；//當(dāng)前為線性表分配的存儲容量}SeqList;任務(wù)二線性表的順序存儲結(jié)構(gòu)線性表順序存儲結(jié)構(gòu)的定義為：#d定義一個順序表的方法有兩種：方法一：SeqListL，表示將L定義為SeqList類型的變量；方法二：SeqList*L，表示將L定義為指向SeqList類型的指針。對表中數(shù)據(jù)元素進行操作應(yīng)使用L.elem[i]

對表中數(shù)據(jù)元素進行操作應(yīng)使用L->elem[i]（（*L）.elem[i]）

任務(wù)二線性表的順序存儲結(jié)構(gòu)定義一個順序表的方法有兩種：方法一：SeqListL，表任務(wù)二線性表的順序存儲結(jié)構(gòu)順序表的優(yōu)缺點優(yōu)點：隨機存取元素、簡單直觀缺點：插入和刪除結(jié)點困難、擴展不靈活、容易造成浪費任務(wù)二線性表的順序存儲結(jié)構(gòu)順序表的優(yōu)缺點二、順序表的基本操作1．初始化順序表2．插入數(shù)據(jù)元素3．刪除數(shù)據(jù)元素4．查找數(shù)據(jù)元素任務(wù)二線性表的順序存儲結(jié)構(gòu)二、順序表的基本操作1．初始化順序表2．插入數(shù)據(jù)元素3任務(wù)二線性表的順序存儲結(jié)構(gòu)1、初始化順序表StatusInitList(SeqList*L){//初始化順序表

L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));//分配存儲空間If(!L->elem)returnOVERFLOW;//存儲空間分配失敗L->length=0;//當(dāng)前線性表長度為0L->listsize=MAXSIZE;//初始化存儲容量returnTRUE;}算法思想：給順序表分配存儲空間，elem指針指向該順序表；判斷分配空間是否成功；設(shè)置順序表的長度為0；初始化存儲容量；任務(wù)二線性表的順序存儲結(jié)構(gòu)1、初始化順序表StatusI任務(wù)二線性表的順序存儲結(jié)構(gòu)2、插入和刪除操作(1)插入數(shù)據(jù)元素InsertList（L，i，e）插入前：L=(a1，a2，…ai-1，ai…，an)插入后：L=(a1，a2，…ai-1，e，ai…，an)為了在順序表中第i（1≤i≤n）個位置插入數(shù)據(jù)元素e，需先將第i個至第n個元素（共n－i＋1個）依次向后移動一個位置，再將e插入到第i個位置。若i＝n＋1，則只需在線性表的末尾插入e即可。任務(wù)二線性表的順序存儲結(jié)構(gòu)2、插入和刪除操作為了在順序表中任務(wù)二線性表的順序存儲結(jié)構(gòu)算法描述如下：StatusInsertList(SeqList*L,inti,ElemTypee){//在順序表L中第i個位置插入數(shù)據(jù)元素e，其中1<=i<=n+1intj；

if（i<1||i>L->length+1）

returnFALSE;//i值不合法，出錯處理

if(L->length=L.listsize)returnOVERFLOW;//當(dāng)前存儲空間滿for(j=L->length-1;j>=i-1;j--)L->elem[j+1]=L-elem[j];//第i個位置之后的元素依次向后移L->elem[i-1]=e;//將e插入到第i個位置L->length++;//表長增1returnTRUE;}算法思想：進行合法性檢查，1<=i<=n+1；判斷線性表是否已滿；將第n個至第i個元素逐一后移一個單元；在第i個位置處插入新元素；將表的長度加1.任務(wù)二線性表的順序存儲結(jié)構(gòu)算法描述如下：StatusIn任務(wù)二線性表的順序存儲結(jié)構(gòu)插入算法時間復(fù)雜度分析：最壞情況是在第1個元素前插入（i=1），此時要后移n個元素，因此T（n）=O(n)任務(wù)二線性表的順序存儲結(jié)構(gòu)插入算法時間復(fù)雜度分析：任務(wù)二線性表的順序存儲結(jié)構(gòu)(2)刪除運算DeleteList（L,i）刪除前：L=(a1，a2，…ai-1，ai,，ai+1…，an)插入后：L=(a1，a2，…ai-1，ai+1，…，an)刪除順序表中第i（1≤i≤n）個數(shù)據(jù)元素，需將第i＋1個至第n個元素（共n－i個）依次向前移動一個位置。順序表進行刪除操作的前后，其數(shù)據(jù)元素在存儲空間中的位置變化如圖2-3所示。任務(wù)二線性表的順序存儲結(jié)構(gòu)(2)刪除運算DeleteLis任務(wù)二線性表的順序存儲結(jié)構(gòu)算法描述如下：StatusDeleteList(SeqList*L,inti){//在順序表L中刪除第i個數(shù)據(jù)元素e，其中1<=i<=nintj；

if（i<1||i>L->length）

returnFALSE;//i值不合法，出錯處理for(j=i;j<L->length;j++)L->elem[j-1]=L->elem[j];//第i個位置之后的元素依次向前移L->length--;//表長減1returnTRUE;}算法思想：進行合法性檢查，1<=i<=n；將第i+1個至第n個元素逐一向前移一個位置；將表的長度減1.任務(wù)二線性表的順序存儲結(jié)構(gòu)算法描述如下：StatusDe任務(wù)二線性表的順序存儲結(jié)構(gòu)刪除算法時間復(fù)雜度分析：最壞情況是刪除第1個元素，此時要前移n-1個元素，因此T（n）=O(n)任務(wù)二線性表的順序存儲結(jié)構(gòu)刪除算法時間復(fù)雜度分析：任務(wù)二線性表的順序存儲結(jié)構(gòu)(3)查找運算Locate（L,e）在順序表中查找值為e的數(shù)據(jù)元素，并返回該元素在表中的位置。方法：從第一個數(shù)據(jù)元素開始，依次將表中的元素與e進行比較，若相等，則返回該元素在表中的位置；否則，查找失敗。任務(wù)二線性表的順序存儲結(jié)構(gòu)(3)查找運算Locate（L,任務(wù)二線性表的順序存儲結(jié)構(gòu)順序表查找算法描述如下：intLocate(SeqList*L,ElemTypee){//在順序表L中查找值為e的數(shù)據(jù)元素查找成功，返回該元素位置，否則返回0intj；for(j=0;j<L->length;j++)if（L->elem[j]==e）

returnj+1;return0;}算法思想：將第0個至第n-1個元素逐一與元素e比較，如值相等，返回該元素在表中位置，否則返回0；任務(wù)二線性表的順序存儲結(jié)構(gòu)順序表查找算法描述如下：int例3一個線性表L中的數(shù)據(jù)元素按升序排列，編寫一個算法，實現(xiàn)在線性表中插入一個數(shù)據(jù)元素item，使得線性表仍然保持升序排列。算法設(shè)計如下：voidInsert(SqListL,ElemTypeitem){inti;intj;if(item>=L.elem[L.length-1])//item值大于表中最大的數(shù)據(jù)元素

L.elem[L.length]=item; //將item插入到表尾else{i=0;while(item>=L.elem[i]) //尋找item的插入位置ii++;ListInsert(&L,i,item);} //將item插入到位置iL.length++;} //表長增1例3一個線性表L中的數(shù)據(jù)元素按升序排列，編寫一個算法，實現(xiàn)任務(wù)二線性表的順序存儲結(jié)構(gòu)五、線性表順序存儲結(jié)構(gòu)的特點1、邏輯上相鄰的元素，其物理位置也相鄰；2、可隨機存取表中任一元素；3、必須按最大可能長度預(yù)分配存儲空間，存儲空間利用率低，表的容量難以擴充，是一種靜態(tài)存儲結(jié)構(gòu)；4、插入刪除時，需移動大量元素，平均移動元素為n/2。任務(wù)二線性表的順序存儲結(jié)構(gòu)五、線性表順序存儲結(jié)構(gòu)的特點1）在一個長度為n的順序存儲的線性表中，向第i個元素（1≤i≤n+1）位置插入一個新元素時，需要從后向前依次后移（

）個元素。A、n-iB、n-i+1C、n-i-1D、i2）在一個長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，需要從前向后依次前移（

）個元素。A、n-iB、n-i+1C、n-i-1D、i1）在一個長度為n的順序存儲的線性表中，向第i個元素（1≤i項目二線性表項目二線性表項目二線性表任務(wù)一：線性表的定義和基本運算任務(wù)二：線性表的順序存儲結(jié)構(gòu)任務(wù)三：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，及它們之間的相互關(guān)系；定義與之相適應(yīng)的運算；設(shè)計相應(yīng)的算法；分析算法的效率。項目二線性表任務(wù)一：線性表的定義和基本運算任務(wù)一線性表的定義和基本操作一、線性表線性表是n個數(shù)據(jù)元素的有限序列，記為：L=(a1，a2，……，an)數(shù)據(jù)元素之間的關(guān)系是：ai-1領(lǐng)先于ai

，ai領(lǐng)先于ai+1

。稱ai-1是ai的直接前驅(qū)元素；ai+1是ai的直接后繼元素。除a1外，每個元素有且僅有一個直接前驅(qū)元素；除an外，每個元素有且僅有一個直接后繼元素。線性表中數(shù)據(jù)元素的個數(shù)n（n>=0）稱為線性表的長度，當(dāng)n=0，稱為空表。任務(wù)一線性表的定義和基本操作一、線性表數(shù)據(jù)元素之間的關(guān)系是任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：ADTList{

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,……n,n>=0}{稱n為線性表的表長；

稱n=0時的線性表為空表。}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}{設(shè)線性表為(a1，a2，……，an)，稱i為ai在線性表中的位序}

基本操作：{結(jié)構(gòu)初始化}InitList(L)

操作結(jié)果：構(gòu)造一個空的線性表

{銷毀結(jié)構(gòu)}DestroyList(L)

初始條件：線性表已存在

操作結(jié)果：構(gòu)造一個空的線性表任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：AD任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{引用型操作}ListEmpty(L)ListLength(L)PriorElem(L,e)NextElem(L,e)GetElem(L,i)Locate(L,e)任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{引ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。ListEmpty(L)ListLength（L）初始條件：線性表L已存在。操作結(jié)果：返回L中元素的個數(shù)。PriorElem（L,e）初始條件：線性表L已存在。操作結(jié)果：若e是L的元素，但不是第一個，則返回它的前驅(qū)，否則操作失敗。ListLength（L）NextElem（L,e）初始條件：線性表L已存在。操作結(jié)果：若e是L的元素，但不是最后一個，則返回e的后繼，否則操作失敗。GetElem（L，i）初始條件：線性表L已存在，1<=i<=LengthList(L)操作結(jié)果：返回L中第i個元素的值NextElem（L,e）Locate（L，e）初始條件：線性表L已存在。操作結(jié)果：返回L中e的位序。若這樣的元素不存在，則返回值0Locate（L，e）任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{加工型操作}ClearList(L)InsertList(L，i,e)DeleteList(L，i,e)任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：{加ClearList（L）初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。InsertList（L，i，e）初始條件：線性表L已存在。1<=i<=LengthList(L)+1操作結(jié)果：在L的第i個元素之前插入新的元素e，L的長度增1。ClearList（L）DeleteList（L，i，e）初始條件：線性表L已存在。1<=i<=LengthList(L)操作結(jié)果：刪除L的第i個元素，并用e返回其值，L的長度減1。DeleteList（L，i，e）利用上述定義的線性表，可以完成其他更復(fù)雜的操作。利用上述定義的線性表，可以完成其他更復(fù)雜的操作。任務(wù)一線性表的定義和基本操作例2-1求兩個集合的并集，即A=A∪B分析：設(shè)A、B分別由兩個線性表LA、LB表示，要求將LB中存在而LA中不存在的數(shù)據(jù)元素插入到表LA中任務(wù)一線性表的定義和基本操作例2-1求兩個集合的并集，即任務(wù)一線性表的定義和基本操作算法描述如下（類C）：voidUnion(Liner_ListLA,Liner_ListLB){LA.len=ListLength(LA);LB.len=ListLength(LB);//求線性表的長度for(i=1;i<=LB.len;i++){//LB中第i個元素在LA中不存在，則將其插入到LA中if(!Locate(LA,GetElem(LB,i)))InsertList(&LA,++LA.len,GetElem(LB,i));}}算法思想：依次從LB中取出一個元素；判斷LA中是否存在；若不存在，則插入到LA中。任務(wù)一線性表的定義和基本操作算法描述如下（類C）：void任務(wù)一線性表的定義和基本操作例2-2歸并兩個有序的線性表LA和LB為一個新的線性表算法思想：（1）初始化：置LC為空表，設(shè)置變量i，j，初值為1，分別指向LA和LB的第一個元素，k表示LC的長度，初值為0

。（2）當(dāng)i<=LENGTH(LA)ANDJ<=LENGTH(LB)時，判斷：若i所指的元素<=j所指的元素，則將i所指的元素插入在LC的k+1，并且i，k的值分別加1；否則，將j所指的元素插入在LC的k+1前，并且j，k的值分別加1（3）重復(fù)（2）直到某個表的元素插入完畢。（4）將未插入完的表的余下的元素，依次插入在LC后。任務(wù)一線性表的定義和基本操作例2-2歸并兩個有序的線性表任務(wù)一線性表的定義和基本操作算法設(shè)計如下（類C）：voidMerge_List(Liner_ListLA,Liner_ListLB,Liner_ListLC){LA.len=ListLength(LA);LB.len=ListLength(LB);//求線性表的長度InitList(LC);//初始化線性表LCwhile(i<=LA.len&&j<=LB.len)//如果LA中第i個元素小于LB中//第j個元素,把LA中第i個元素插入到LC中，否則將LB中第j個元素插入到if(GetElem(LA,i)<=GetElem(LB,j)){InsertList(LC,k+1,GetElem(LA,i));k++;i++;}else{InsertList(LC,k+1,GetElem(LB,j));k++;j++;}while(i<=LA.len){InsertList(LC,k+1,GetElem(LA,i));k++;i++;}while(j<=LB.len){InsertList(LC,k+1,GetElem(LB,j));k++;j++;}}任務(wù)一線性表的定義和基本操作算法設(shè)計如下（類C）：void任務(wù)一線性表的定義和基本操作算法分析：該算法中包含了三個WHILE語句，其中，第一個處理了某一張表的全部元素和另一張表的部分元素；后兩個WHILE循環(huán)只可能有一個執(zhí)行，用來完成將未歸并到LC中的余下部分元素插入到LC中，“插入”是估量歸并算法時間復(fù)雜度的基本操作，其語句頻度為：

ListLength(LA）+ListLength(LB）該算法的時間復(fù)雜度為：

O（ListLength(LA）+ListLength(LB）），若LA和LB的元素個數(shù)為同數(shù)量級n，則該算法的時間復(fù)雜度為O（n）任務(wù)一線性表的定義和基本操作算法分析：該算法中包含了三個W任務(wù)二線性表的順序存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元依次存儲線性表的元素。設(shè)線性表的每個元素占用k個存儲單元，則第i個元素ai的存儲位置為：Loc(ai)=Loc（a1）+（i-1）*k,其中，Loc（ai）為線性表的起止任務(wù)二線性表的順序存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。

若已知線性表的起始位置（基地址）和表中每個數(shù)據(jù)元素所占存儲單元的大小k，就可以計算出線性表中任意一個數(shù)據(jù)元素的存儲地址，這種存取元素的方法稱為隨機存取法任務(wù)二線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。若已知線性表任務(wù)二線性表的順序存儲結(jié)構(gòu)線性表順序存儲結(jié)構(gòu)的定義為：#defineMAXSIZE100//線性表的最大長度typedefstruct

{ElemTypeelem[MAXSIZE];//存儲線性表中數(shù)據(jù)元素的數(shù)組intlength;//線性表的當(dāng)前長度}SeqList;typedefstruct

{ElemType*elem;//線性表中數(shù)據(jù)元素的基地址intlength;//線性表的當(dāng)前長度intlistsize；//當(dāng)前為線性表分配的存儲容量}SeqList;任務(wù)二線性表的順序存儲結(jié)構(gòu)線性表順序存儲結(jié)構(gòu)的定義為：#d定義一個順序表的方法有兩種：方法一：SeqListL，表示將L定義為SeqList類型的變量；方法二：SeqList*L，表示將L定義為指向SeqList類型的指針。對表中數(shù)據(jù)元素進行操作應(yīng)使用L.elem[i]

對表中數(shù)據(jù)元素進行操作應(yīng)使用L->elem[i]（（*L）.elem[i]）

任務(wù)二線性表的順序存儲結(jié)構(gòu)定義一個順序表的方法有兩種：方法一：SeqListL，表任務(wù)二線性表的順序存儲結(jié)構(gòu)順序表的優(yōu)缺點優(yōu)點：隨機存取元素、簡單直觀缺點：插入和刪除結(jié)點困難、擴展不靈活、容易造成浪費任務(wù)二線性表的順序存儲結(jié)構(gòu)順序表的優(yōu)缺點二、順序表的基本操作1．初始化順序表2．插入數(shù)據(jù)元素3．刪除數(shù)據(jù)元素4．查找數(shù)據(jù)元素任務(wù)二線性表的順序存儲結(jié)構(gòu)二、順序表的基本操作1．初始化順序表2．插入數(shù)據(jù)元素3任務(wù)二線性表的順序存儲結(jié)構(gòu)1、初始化順序表StatusInitList(SeqList*L){//初始化順序表

L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));//分配存儲空間If(!L->elem)returnOVERFLOW;//存儲空間分配失敗L->length=0;//當(dāng)前線性表長度為0L->listsize=MAXSIZE;//初始化存儲容量returnTRUE;}算法思想：給順序表分配存儲空間，elem指針指向該順序表；判斷分配空間是否成功；設(shè)置順序表的長度為0；初始化存儲容量；任務(wù)二線性表的順序存儲結(jié)構(gòu)1、初始化順序表StatusI任務(wù)二線性表的順序存儲結(jié)構(gòu)2、插入和刪除操作(1)插入數(shù)據(jù)元素InsertList（L，i，e）插入前：L=(a1，a2，…ai-1，ai…，an)插入后：L=(a1，a2，…ai-1，e，ai…，an)為了在順序表中第i（1≤i≤n）個位置插入數(shù)據(jù)元素e，需先將第i個至第n個元素（共n－i＋1個）依次向后移動一個位置，再將e插入到第i個位置。若i＝n＋1，則只需在線性表的末尾插入e即可。任務(wù)二線性表的順序存儲結(jié)構(gòu)2、插入和刪除操作為了在順序表中任務(wù)二線性表的順序存儲結(jié)構(gòu)算法描述如下：StatusInsertList(SeqList*L,inti,ElemTypee){//在順序表L中第i個位置插入數(shù)據(jù)元素e，其中1<=i<=n+1intj；

if（i<1||i>L->length+1）

returnFALSE;//i值不合法，出錯處理

if(L->length=L.listsize)returnOVERFLOW;//當(dāng)前存儲空間滿for(j=L->length-1;j>=i-1;j--)L->elem[j+1]=L-elem[j];//第i個位置之后的元素依次向后移L->elem[i-1]=e;//將e插入到第i個位置L->length++;//表長增1returnTRUE;}算法思想：進行合法性檢查，1<=i<=n+1；判斷線性表是否已滿；將第n個至第i個元素逐一后移一個單元；在第i個位置處插入新元素；將表的長度加1.任務(wù)二線性表的順序存儲結(jié)構(gòu)算法描述如下：StatusIn任務(wù)二線性表的順序存儲結(jié)構(gòu)插入算法時間復(fù)雜度分析：最壞情況是在第1個元素前插入（i=1），此時要后移n個元素，因此T（n）=O(n)任務(wù)二線性表的順序存儲結(jié)構(gòu)插入算法時間復(fù)雜度分析：任務(wù)二線性表的順序存儲結(jié)構(gòu)(2)刪除運算DeleteList（L,i）刪除前：L=(a1，a2，…ai-1，ai,，ai+1…，an)插入后：L=(a1，a2，…ai-1，ai+1，…，an)刪除順序表中第i（1≤i≤n）個數(shù)據(jù)元素，需將第i＋1個至第n個元素（共n－i個）依次向前移動一個位置。順序表進行刪除操作的前后，其數(shù)據(jù)元素在存儲空間中的位置變化如圖2-3所示。任務(wù)二線性表的順序存儲結(jié)構(gòu)(2)刪除運算DeleteLis任務(wù)二線性表的順序存儲結(jié)構(gòu)算法描述如下：StatusDeleteList(SeqList*L,inti){//在順序表L中刪除第i個數(shù)據(jù)元素e，其中1<=i<=nintj；

if（i<1||i>L->length）

returnFALSE;//i值不合法，出錯處理for(j=i;j<L->length;j++