線性表順序表算法設(shè)計(jì)

2.2.3順序表算法設(shè)計(jì)順序表算法設(shè)計(jì)：數(shù)據(jù)采用順序表存儲(chǔ)，利用順序表的根本操作來完成求解任務(wù)。1/16【例2-3】長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為x的數(shù)據(jù)元素。如果每刪除一個(gè)值為x的元素都進(jìn)行移動(dòng)，其時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。如果借助一個(gè)新的順序表，存放將A中所有不為x的元素，其時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。以下兩種方法都不滿足要求：2/16解法一〔重建法〕：設(shè)刪除A中所有值等于x元素后的順序表為A1，顯然A1包含在A中，為此A1重用A的空間。思路：掃描順序表A，重建A只包含不等于x的元素。3/16011222刪除所有x=2的元素〔k記錄保存的元素個(gè)數(shù)，初值=0〕：2345k=3，L->length=k=31刪除順序表中所有值為x的元素〔方法1〕演示length63刪除完成3k=0k=1k=2k=34/16對(duì)應(yīng)的算法如下：voiddelnode1(SqList*&A，ElemTypex){intk=0，i; //k記錄值不等于x的元素個(gè)數(shù)for(i=0;i<A->length;i++)if(A->data[i]!=x)//假設(shè)當(dāng)前元素不為x，將其插入A中{A->data[k]=A->data[i]; k++; //不等于x的元素增1}A->length=k; //順序表A的長(zhǎng)度等于k}算法1：類似于建順序表5/16解法二〔前移法〕：用k記錄順序表A中等于x的元素個(gè)數(shù)，一邊掃描A一邊統(tǒng)計(jì)k值。思路：將不為x的元素前移k個(gè)位置，最后修改A的長(zhǎng)度。6/160112232刪除所有x=2的元素〔k記錄刪除的元素個(gè)數(shù)，初值=0〕2345k=0，前移0個(gè)位置1k=1k=1，前移1個(gè)位置k=2k=2，前移2個(gè)位置k=3順序表長(zhǎng)度=6-k=3刪除順序表中所有值為x的元素〔方法2〕演示length63刪除完成7/16對(duì)應(yīng)的算法如下：voiddelnode2(SqList*&A，ElemTypex){intk=0，i=0;

//k記錄值等于x的元素個(gè)數(shù)

while(i<A->length)

{if(A->data[i]==x)//當(dāng)前元素值為x時(shí)k增1 k++;

else

//當(dāng)前元素不為x時(shí)將其前移k個(gè)位置

A->data[i-k]=A->data[i];

i++;

}

A->length-=k; //順序表A的長(zhǎng)度遞減k}8/16思考題

為什么說上述兩個(gè)算法都能夠滿足題目的要求？9/16【例2-4】設(shè)順序表L有10個(gè)整數(shù)。設(shè)計(jì)一個(gè)算法，以第一個(gè)元素為分界線〔基準(zhǔn)〕，將所有小于等于它的元素移到該元素的前面，將所有大于它的元素移到該元素的后面。x無序整數(shù)序列≤xx>x10/160812273145536476809pivotijpivot=L->data[0]〔基準(zhǔn)〕j從后向前找≤pivot的元素i從前向后找>pivot的元素3兩者交換31

0

2

3

3

5

7

4

6

8解法1〔前后交換法〕：11/16voidmove1(SqList*&L){inti=0，j=L->length-1;ElemTypetmp;ElemTypepivot=L->data[0]; //以data[0]為基準(zhǔn)while(i<j)

{ while(i<j&&L->data[j]>pivot)

j--;

//從后向前掃描，找一個(gè)≤pivot的元素

while(i<j&&L->data[i]<=pivot)

i++;

//從前向后掃描，找一個(gè)>pivot的元素

if(i<j) {tmp=L->data[i]; //L->data[i]

L->data[j]

L->data[i]=L->data[j];

L->data[j]=tmp; }

}

tmp=L->data[0];

//L->data[0]

L->data[j]

L->data[0]=L->data[j];L->data[j]=tmp;}12/1630812273145536476809pivot〔基準(zhǔn)〕ijpivot=L->data[0]〔基準(zhǔn)〕j從后向前找小于等于pivot的元素：前移i從前向后找大于pivot的元素：后移0

3

2

1

3

5

7

4

6

8解法2〔前后交換法〕：算法時(shí)間復(fù)雜度為O(n)。13/16voidmove2(SqList*&L){

inti=0，j=L->length-1;

ElemTypepivot=L->data[0]; //以data[0]為基準(zhǔn)

while(i<j)

{while(j>i&&L->data[j]>pivot)

j--; //從右向左掃描，找≤pivot的data[j]

L->data[i]=L->data[j]; //將其放入data[i]處while(i<j&&L->data[i]<=pivot)

i++; //從左向右掃描，找>pivot的記錄data[i]

L->data[j]=L->data[i]; //將其放入data[j]處}

L->data[i]=pivot; //放置基準(zhǔn)}14/16兩個(gè)記錄a、b交換：tmp=a;a=b;b=tmp;需要3次移動(dòng)多個(gè)相鄰記錄連續(xù)交換，如a、b、c：

位置1和位置2的元素交換

b、a、c需要3次移動(dòng)

位置2和位置3的元素交換

b、c、a需要3次移動(dòng)

為什么解法2比解法1更好？而采用：tmp=a;a=b;b=c;c=tmp;4次移動(dòng)性能得到提高。共6次移動(dòng)15/16線性表中每個(gè)結(jié)點(diǎn)有唯一的前驅(qū)結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)。2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)—鏈表設(shè)計(jì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，每個(gè)邏輯結(jié)點(diǎn)存儲(chǔ)單獨(dú)存儲(chǔ)，為了表示邏輯關(guān)系，增加指針域。

每個(gè)物理結(jié)點(diǎn)增加一個(gè)指向后繼結(jié)點(diǎn)的指針域

單鏈表。每個(gè)物理結(jié)點(diǎn)增加一個(gè)指向后繼結(jié)點(diǎn)的指針域和一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針域

雙鏈表。2.3

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)16/35線性表(a1，a2，…，ai，…an)映射邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)a1a2an∧…L帶頭結(jié)點(diǎn)單鏈表示意圖17/35a1a2an∧…第一個(gè)結(jié)點(diǎn)的操作和表中其他結(jié)點(diǎn)的操作相一致，無需進(jìn)行特殊處理；無論鏈表是否為空，都有一個(gè)頭結(jié)點(diǎn)，因此空表和非空表的處理也就統(tǒng)一了。單鏈表增加一個(gè)頭結(jié)點(diǎn)的優(yōu)點(diǎn)如下：帶頭結(jié)點(diǎn)單鏈表18/35

存儲(chǔ)密度是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)結(jié)構(gòu)中所占的存儲(chǔ)量之比，即：一般地，存儲(chǔ)密度越大，存儲(chǔ)空間的利用率就越高。顯然，順序表的存儲(chǔ)密度為1〔100%〕，而鏈表的存儲(chǔ)密度小于1。存儲(chǔ)密度=結(jié)點(diǎn)數(shù)據(jù)本身占用的空間結(jié)點(diǎn)占用的空間總量a18個(gè)字節(jié)4個(gè)字節(jié)存儲(chǔ)密度=8/12=67%例如19/35思考題：

線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的差異？20/352.3.2

單鏈表單鏈表中結(jié)點(diǎn)類型LinkNode的定義如下:

typedefstructLNode

//定義單鏈表結(jié)點(diǎn)類型{ElemTypedata;

structLNode*next;

//指向后繼結(jié)點(diǎn)}LinkNode;a21/35當(dāng)訪問過一個(gè)結(jié)點(diǎn)后，只能接著訪問它的后繼結(jié)點(diǎn)，而無法訪問它的前驅(qū)結(jié)點(diǎn)。單鏈表的特點(diǎn)ab…p…22/35插入操作：將值為x的新結(jié)點(diǎn)*s插入到*p結(jié)點(diǎn)之后。1、插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)操作特點(diǎn)：只需修改相關(guān)結(jié)點(diǎn)的指針域，不需要移動(dòng)結(jié)點(diǎn)?！?〕插入結(jié)點(diǎn)23/35abx…p…s

s->next=p->next

p->next=s插入操作語句描述如下：

s->next=p->next;

p->next=s;單鏈表插入結(jié)點(diǎn)演示24/35刪除操作：刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)。特點(diǎn)：只需修改相關(guān)結(jié)點(diǎn)的指針域，不需要移動(dòng)結(jié)點(diǎn)?！?〕刪除結(jié)點(diǎn)25/35abx…p…p->next=p->next->next刪除操作語句描述如下：

p->next=p->next->next;單鏈表刪除結(jié)點(diǎn)演示26/35先考慮如何整體建立單鏈表。

2、建立單鏈表a[0..n-1]帶頭結(jié)點(diǎn)的單鏈表L整體創(chuàng)立建立單鏈表的常用方法有兩種。27/35從一個(gè)空表開始，創(chuàng)立一個(gè)頭結(jié)點(diǎn)。依次讀取字符數(shù)組a中的元素，生成新結(jié)點(diǎn)將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到結(jié)束為止。Lai-1a1…ais〔1〕頭插法建表注意：鏈表的結(jié)點(diǎn)順序與邏輯次序相反。28/35voidCreateListF(LinkNode*&L，ElemTypea[]，intn){LinkNode*s;inti;L=(LinkNode*)malloc(sizeof(LinkNode));L->next=NULL; //創(chuàng)立頭結(jié)點(diǎn)，其next域置為NULL頭插法建表算法如下：∧L29/35for(i=0;i<n;i++) //循環(huán)建立數(shù)據(jù)結(jié)點(diǎn){ s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=a[i]; //創(chuàng)立數(shù)據(jù)結(jié)點(diǎn)*s s->next=L->next; //將*s插在原開始結(jié)點(diǎn)之前，頭結(jié)點(diǎn)之后 L->next=s;}}Lai-1a1…aiss->next=L->next;L->next=s;30/35La1aj…aisr〔2〕尾插法建表注意：鏈表的結(jié)點(diǎn)順序與邏輯次序相同。從一個(gè)空表開始，創(chuàng)立一個(gè)頭結(jié)點(diǎn)。依次讀取字符數(shù)組a中的元素，生成新結(jié)點(diǎn)將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，直到結(jié)束為止。增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)31/35voidCreateListR(LinkNode*&L，ElemTypea[]，intn){LinkNode*s，*r;inti;L=(LinkNode*)malloc(sizeof(LinkNode));//創(chuàng)立頭結(jié)點(diǎn)r=L; //r始終指向尾結(jié)點(diǎn)，開始時(shí)指向頭結(jié)點(diǎn)尾插法建表算法如下：∧Lr32/35for(i=0;i<n;i++) //循環(huán)建立數(shù)據(jù)結(jié)點(diǎn){ s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=a[i]; //創(chuàng)立數(shù)據(jù)結(jié)點(diǎn)*s r->next=s; //將*s插入*r之后 r=s;}r->next=NULL; //尾結(jié)點(diǎn)next域置為NULL}rLa1ai-1…aisr->next=s33/353、線性表根本運(yùn)算在單鏈表上的實(shí)現(xiàn)〔1〕初始化線性表InitList(L)該運(yùn)算建立一個(gè)空的單鏈表，即創(chuàng)立一個(gè)頭結(jié)點(diǎn)。voidInitList(LinkNode*&L){L=(LinkNode*)malloc(sizeof(LinkNode));//創(chuàng)立頭結(jié)點(diǎn)L->next=NULL;}∧L34/35〔2〕銷毀線性表DestroyList(L)釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)的空間。voidDestroyList(LinkNode*&L){

LinkNode*pre=L，*p=L->next;

//pre指向*p的前驅(qū)結(jié)點(diǎn)

初始時(shí)L∧…prep35/35while(p!=NULL) //掃描單鏈表L

{free(pre); //釋放*pre結(jié)點(diǎn)

pre=p; //pre、p同步后移一個(gè)結(jié)點(diǎn)

p=pre->next;

}

free(pre);

//循環(huán)結(jié)束時(shí)，p為NULL，pre指向尾結(jié)點(diǎn)，釋放它}循環(huán)結(jié)束時(shí)L∧prep=NULL…36/35〔3〕判線性表是否為空表ListEmpty(L)假設(shè)單鏈表L沒有數(shù)據(jù)結(jié)點(diǎn)，那么返回真，否那么返回假。boolListEmpty(LinkNode*L){

return(L->next==NULL);}∧L空表的情況37/35〔4〕求線性表的長(zhǎng)度ListLength(L)返回單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。intListLength(LinkNode*L){intn=0;LinkNode*p=L; //p指向頭結(jié)點(diǎn)，n置為0〔即頭結(jié)點(diǎn)的序號(hào)為0〕

初始時(shí)L∧…pn=038/35while(p->next!=NULL)

{ n++; p=p->next;

}

return(n); //循環(huán)結(jié)束，p指向尾結(jié)點(diǎn)，其序號(hào)n為結(jié)點(diǎn)個(gè)數(shù)}循環(huán)結(jié)束時(shí)L∧pn為結(jié)點(diǎn)個(gè)數(shù)…39/35〔5〕輸出線性表DispList(L)逐一掃描單鏈表L的每個(gè)數(shù)據(jù)結(jié)點(diǎn)，并顯示各結(jié)點(diǎn)的data域值。voidDispList(LinkNode*L){LinkNode*p=L->next; //p指向開始結(jié)點(diǎn)

while(p!=NULL)

//p不為NULL，輸出*p結(jié)點(diǎn)的data域

{ printf("%d"，p->data); p=p->next; //p移向下一個(gè)結(jié)點(diǎn)

}

printf("\n");}L∧p…40/35〔6〕求線性表L中位置i的數(shù)據(jù)元素GetElem(L，i，&e)思路：在單鏈表L中從頭開始找到第i個(gè)結(jié)點(diǎn)，假設(shè)存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)，那么將其data域值賦給變量e。41/35boolGetElem(LinkNode*L，inti，ElemType&e){intj=0;LinkNode*p=L; //p指向頭結(jié)點(diǎn)，j置為0〔即頭結(jié)點(diǎn)的序號(hào)為0〕while(j<i&&p!=NULL){ j++; p=p->next;}找第i個(gè)結(jié)點(diǎn)*p循環(huán)結(jié)束時(shí)Lean∧…i…p42/35if(p==NULL) //不存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)，返回false

returnfalse;

else

//存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)，返回true

{e=p->data;

returntrue;

}}Lean∧…i…p43/35〔7〕按元素值查找LocateElem(L，e)思路：在單鏈表L中從頭開始找第1個(gè)值域與e相等的結(jié)點(diǎn)，假設(shè)存在這樣的結(jié)點(diǎn)，那么返回位置，否那么返回0。intLocateElem(LinkNode*L，ElemTypee){

inti=1;

LinkNode*p=L->next; //p指向開始結(jié)點(diǎn)，i置為1

while(p!=NULL&&p->data!=e)

{p=p->next; //查找data值為e的結(jié)點(diǎn)，其序號(hào)為ii++;

}

循環(huán)結(jié)束時(shí)Le∧…i…p44/35Le∧…i…if(p==NULL) //不存在元素值為e的結(jié)點(diǎn)，返回0return(0);

else

//存在元素值為e的結(jié)點(diǎn)，返回其邏輯序號(hào)i

return(i);}算法的時(shí)間復(fù)雜度為O(n)

不具有隨機(jī)存取特性45/35〔8〕插入數(shù)據(jù)元素ListInsert(&L，i，e)思路：先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)*p，假設(shè)存在這樣的結(jié)點(diǎn)，將值為e的結(jié)點(diǎn)*s插入到其后。boolListInsert(LinkNode*&L，inti，ElemTypee){

intj=0;

LinkNode*p=L，*s; //p指向頭結(jié)點(diǎn)，j置為0

while(j<i-1&&p!=NULL)

{ j++; p=p->next;

}查找第