項(xiàng)目二線性表-順序存儲(chǔ)

項(xiàng)目二線性表項(xiàng)目二線性表任務(wù)一：線性表的定義和基本運(yùn)算任務(wù)二：線性表的順序存儲(chǔ)結(jié)構(gòu)任務(wù)三：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，及它們之間的相互關(guān)系；定義與之相適應(yīng)的運(yùn)算；設(shè)計(jì)相應(yīng)的算法；分析算法的效率。任務(wù)一線性表的定義和基本操作一、線性表線性表是n個(gè)數(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外，每個(gè)元素有且僅有一個(gè)直接前驅(qū)元素；除an外，每個(gè)元素有且僅有一個(gè)直接后繼元素。線性表中數(shù)據(jù)元素的個(gè)數(shù)n（n>=0）稱為線性表的長(zhǎng)度，當(dāng)n=0，稱為空表。任務(wù)一線性表的定義和基本操作抽象數(shù)據(jù)類型線性表的定義：ADTList{

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

稱n=0時(shí)的線性表為空表。}

數(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)造一個(gè)空的線性表

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

DestroyList(L)

初始條件：線性表已存在

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

LA,Liner_ListLB){LA.len=ListLength(LA);

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

for(i=1;i<=LB.len;i++){//LB中第i個(gè)元素在LA中不存在，則將其插入到LA中

if(!Locate(LA,GetElem(LB,i)))

InsertList(&LA,++LA.len,GetElem(LB,i));}}算法思想：依次從LB中取出一個(gè)元素；判斷LA中是否存在；若不存在，則插入到LA中。任務(wù)一線性表的定義和基本操作例2-2歸并兩個(gè)有序的線性表LA和LB為一個(gè)新的線性表算法思想：（1）初始化：置LC為空表，設(shè)置變量i，j，初值為1，分別指向LA和LB的第一個(gè)元素，k表示LC的長(zhǎng)度，初值為0

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

LA,Liner_List

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

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

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

while(i<=LA.len&&j<=LB.len)//如果LA中第i個(gè)元素小于LB中//第j個(gè)元素,把LA中第i個(gè)元素插入到LC中，否則將LB中第j個(gè)元素插入到

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

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

O（ListLength(LA）+ListLength(LB）），若LA和LB的元素個(gè)數(shù)為同數(shù)量級(jí)n，則該算法的時(shí)間復(fù)雜度為O（n）任務(wù)二線性表的順序存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)

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

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

struct

{

ElemType

elem[MAXSIZE];//存儲(chǔ)線性表中數(shù)據(jù)元素的數(shù)組

intlength;//線性表的當(dāng)前長(zhǎng)度}SeqList;typedef

struct

{

ElemType*elem;//線性表中數(shù)據(jù)元素的基地址

intlength;//線性表的當(dāng)前長(zhǎng)度

int

listsize；//當(dāng)前為線性表分配的存儲(chǔ)容量}SeqList;定義一個(gè)順序表的方法有兩種：方法一：SeqListL，表示將L定義為SeqList類型的變量；方法二：SeqList*L，表示將L定義為指向SeqList類型的指針。對(duì)表中數(shù)據(jù)元素進(jìn)行操作應(yīng)使用L.elem[i]

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

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

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

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

intj；

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

returnFALSE;//i值不合法，出錯(cuò)處理

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

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

intj；

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

returnFALSE;//i值不合法，出錯(cuò)處理

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

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

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

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