項目二線性表-順序存儲

項目二線性表項目二線性表任務一：線性表的定義和基本運算任務二：線性表的順序存儲結構任務三：線性表的鏈式存儲結構線性表的邏輯結構、存儲結構，及它們之間的相互關系；定義與之相適應的運算；設計相應的算法；分析算法的效率。任務一線性表的定義和基本操作一、線性表線性表是n個數據元素的有限序列，記為：L=(a1，a2，……，an)數據元素之間的關系是：ai-1領先于ai

，ai領先于ai+1

。稱ai-1是ai的直接前驅元素；ai+1是ai的直接后繼元素。除a1外，每個元素有且僅有一個直接前驅元素；除an外，每個元素有且僅有一個直接后繼元素。線性表中數據元素的個數n（n>=0）稱為線性表的長度，當n=0，稱為空表。任務一線性表的定義和基本操作抽象數據類型線性表的定義：ADTList{

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

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

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

基本操作：{結構初始化}

InitList(L)

操作結果：構造一個空的線性表

{銷毀結構}

DestroyList(L)

初始條件：線性表已存在

操作結果：構造一個空的線性表任務一線性表的定義和基本操作抽象數據類型線性表的定義：{引用型操作}ListEmpty(L)ListLength(L)PriorElem(L,e)NextElem(L,e)GetElem(L,i)Locate(L,e)ListEmpty(L)初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則FALSE。ListLength（L）初始條件：線性表L已存在。操作結果：返回L中元素的個數。PriorElem（L,e）初始條件：線性表L已存在。操作結果：若e是L的元素，但不是第一個，則返回它的前驅，否則操作失敗。NextElem（L,e）初始條件：線性表L已存在。操作結果：若e是L的元素，但不是最后一個，則返回e的后繼，否則操作失敗。GetElem（L，i）初始條件：線性表L已存在，1<=i<=LengthList(L)操作結果：返回L中第i個元素的值Locate（L，e）初始條件：線性表L已存在。操作結果：返回L中e的位序。若這樣的元素不存在，則返回值0任務一線性表的定義和基本操作抽象數據類型線性表的定義：{加工型操作}ClearList(L)InsertList(L，i,e)DeleteList(L，i,e)ClearList（L）初始條件：線性表L已存在。操作結果：將L重置為空表。InsertList（L，i，e）初始條件：線性表L已存在。1<=i<=LengthList(L)+1操作結果：在L的第i個元素之前插入新的元素e，L的長度增1。DeleteList（L，i，e）初始條件：線性表L已存在。1<=i<=LengthList(L)操作結果：刪除L的第i個元素，并用e返回其值，L的長度減1。利用上述定義的線性表，可以完成其他更復雜的操作。任務一線性表的定義和基本操作例2-1求兩個集合的并集，即A=A∪B分析：設A、B分別由兩個線性表LA、LB表示，要求將LB中存在而LA中不存在的數據元素插入到表LA中任務一線性表的定義和基本操作算法描述如下（類C）：voidUnion(Liner_List

LA,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中。任務一線性表的定義和基本操作例2-2歸并兩個有序的線性表LA和LB為一個新的線性表算法思想：（1）初始化：置LC為空表，設置變量i，j，初值為1，分別指向LA和LB的第一個元素，k表示LC的長度，初值為0

。（2）當i<=LENGTH(LA)ANDJ<=LENGTH(LB)時，判斷：若i所指的元素<=j所指的元素，則將i所指的元素插入在LC的k+1，并且i，k的值分別加1；否則，將j所指的元素插入在LC的k+1前，并且j，k的值分別加1（3）重復（2）直到某個表的元素插入完畢。（4）將未插入完的表的余下的元素，依次插入在LC后。任務一線性表的定義和基本操作算法設計如下（類C）：voidMerge_List(Liner_List

LA,Liner_List

LB,Liner_ListLC){LA.len=ListLength(LA);

LB.len=ListLength(LB);//求線性表的長度

InitList(LC);//初始化線性表LC

while(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++;}}任務一線性表的定義和基本操作算法分析：該算法中包含了三個WHILE語句，其中，第一個處理了某一張表的全部元素和另一張表的部分元素；后兩個WHILE循環(huán)只可能有一個執(zhí)行，用來完成將未歸并到LC中的余下部分元素插入到LC中，“插入”是估量歸并算法時間復雜度的基本操作，其語句頻度為：

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

O（ListLength(LA）+ListLength(LB）），若LA和LB的元素個數為同數量級n，則該算法的時間復雜度為O（n）任務二線性表的順序存儲結構一、順序存儲結構

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

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

struct

{

ElemType

elem[MAXSIZE];//存儲線性表中數據元素的數組

intlength;//線性表的當前長度}SeqList;typedef

struct

{

ElemType*elem;//線性表中數據元素的基地址

intlength;//線性表的當前長度

int

listsize；//當前為線性表分配的存儲容量}SeqList;定義一個順序表的方法有兩種：方法一：SeqListL，表示將L定義為SeqList類型的變量；方法二：SeqList*L，表示將L定義為指向SeqList類型的指針。對表中數據元素進行操作應使用L.elem[i]

對表中數據元素進行操作應使用L->elem[i]（（*L）.elem[i]）

任務二線性表的順序存儲結構任務二線性表的順序存儲結構順序表的優(yōu)缺點優(yōu)點：隨機存取元素、簡單直觀缺點：插入和刪除結點困難、擴展不靈活、容易造成浪費二、順序表的基本操作1．初始化順序表2．插入數據元素3．刪除數據元素4．查找數據元素任務二線性表的順序存儲結構任務二線性表的順序存儲結構1、初始化順序表StatusInitList(SeqList*L){//初始化順序表

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

i,ElemTypee){//在順序表L中第i個位置插入數據元素e，其中1<=i<=n+1

intj；

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

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

if(L->length=L.listsize)returnOVERFLOW;//當前存儲空間滿

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.任務二線性表的順序存儲結構插入算法時間復雜度分析：最壞情況是在第1個元素前插入（i=1），此時要后移n個元素，因此T（n）=O(n)任務二線性表的順序存儲結構(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）個數據元素，需將第i＋1個至第n個元素（共n－i個）依次向前移動一個位置。順序表進行刪除操作的前后，其數據元素在存儲空間中的位置變化如圖2-3所示。任務二線性表的順序存儲結構算法描述如下：StatusDeleteList(SeqList*L,inti){//在順序表L中刪除第i個數據元素e，其中1<=i<=n

intj；

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.任務二線性表的順序存儲結構刪除算法時間復雜度分析：最壞情況是刪除第1個元素，此時要前移n-1個元素，因此T（n）=O(n)任務二線性表的順序存儲結構(3)查找運算Locate（L,e）在順序表中查找值為e的數據元素，并返回該元素在表中的位置。方法：從第一個數據元素開始，依次將表中的元素與e進行比較，若相等，則返回該元素在表中的位置；否則，查找失敗。任務二線性表的順序存儲結構順序表查找算法描述如下：int

Locate(SeqList*L,ElemTypee){//在順序表L中查找值為e的數據元素查找成功，返回該元素位置，否則返回0

intj；for(j=0;j<L->length;j++)if（L->elem[j]==e）

returnj+1;return0;}算法思想：將第0個至第n-1個元素逐一與元素e比較，如值相等，返回該元素在表中位置，否則返回0；例3一個線性表L中的數據元素按升序排列，編寫一個算法，實現在線性表中插入一個數據元素item，使得線性表仍然保持升序排列。算法設計如下：voidInsert(SqListL,ElemTypeitem){int