數(shù)據(jù)結(jié)構(gòu)第2章線性表

第2章線性表

2.1線性表及其邏輯結(jié)構(gòu)

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.4線性表的應(yīng)用

2.5有序表

12.1線性表及其邏輯結(jié)構(gòu)

2.1.1線性表的定義2.1.2線性表的抽象數(shù)據(jù)類型描述22.1.1線性表的定義

線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。該序列中所含元素的個(gè)數(shù)叫做線性表的長(zhǎng)度,用n表示,n≥0。當(dāng)n=0時(shí),表示線性表是一個(gè)空表,即表中不包含任何元素。設(shè)序列中第i(i表示位序)個(gè)元素為ai(1≤i≤n)。線性表的一般表示為:(a1,a2,…ai,ai+1,…,an)3

其中a1為第一個(gè)元素,又稱做表頭元素,a2為第二個(gè)元素,an為最后一個(gè)元素,又稱做表尾元素。例如,在線性表

(1,4,3,2,8,10)中,1為表頭元素,10為表尾元素。42.1.2線性表的抽象數(shù)據(jù)類型描述

線性表的基本運(yùn)算如下:(1)初始化線性表InitList(&L):構(gòu)造一個(gè)空的線性表L。(2)銷毀線性表DestroyList(&L):釋放線性表L占用的內(nèi)存空間。5

(3)判線性表是否為空表ListEmpty(L):若L為空表,則返回真,否則返回假。

(4)求線性表的長(zhǎng)度ListLength(L):返回L中元素個(gè)數(shù)。

(5)輸出線性表DispList(L):當(dāng)線性表L不為空時(shí),順序顯示L中各結(jié)點(diǎn)的值域。

(6)求線性表L中指定位置的某個(gè)數(shù)據(jù)元素

GetElem(L,i,&e):用e返回L中第i個(gè)元素的值

(1≤i≤ListLength(L))。6

(7)定位查找LocateElem(L,e):

返回L中第1個(gè)值域與e相等的位序。若這樣的元素不存在,則返回值為0。

(8)插入數(shù)據(jù)元素ListInsert(&L,i,e):

在L的第i(1≤i≤ListLength(L)+1)個(gè)元素之前插入新的元素e,L的長(zhǎng)度增1。

(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e):

刪除L的第i(1≤i≤ListLength(L))個(gè)元素,并用e返回其值,L的長(zhǎng)度減1。7定義線性表的抽象數(shù)據(jù)類型ADTList{數(shù)據(jù)對(duì)象：D={a1,a2,a3,…,an}

數(shù)據(jù)關(guān)系：R1={<a1,a2>,<a2,a3>,…,<an-1,an>}

基本運(yùn)算：

InitList(&L);DestroyList(&L);……..ListDelete(&L,i,&e)}8

例2.2假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示,即線性表中的數(shù)據(jù)元素即為集合中的成員。編寫(xiě)一個(gè)算法求一個(gè)新的集合C=A∪B,即將兩個(gè)集合的并集放在線性表LC中。

解:本算法思想是:先初始化線性表LC,將LA的所有元素復(fù)制到LC中,然后掃描線性表LB,若LB的當(dāng)前元素不在線性表LA中,則將其插入到LC中。算法如下:9voidunionList(ListLA,ListLB,List&LC){intlena,lenc,i;ElemTypee;

InitList(LC);for(i=1;i<=ListLength(LA);i++) /*將LA的所有元素插入到Lc中*/{ GetElem(LA,i,e);

ListInsert(LC,i,e);}lena=ListLength(LA);/*求線性表的長(zhǎng)度*/lenb=ListLength(LB);10

for(i=1;i<=lenb;i++) {

GetElem(LB,i,e); /*取LB中第i個(gè)數(shù)據(jù)元素賦給e*/ if(!LocateElem(LA,e))

ListInsert(LC,++lena,e); /*LA中不存在和e相同者,則插入到LC中*/ }}11

由于LocateElem(LA,e)運(yùn)算的時(shí)間復(fù)雜度為O(ListLength(LA)),所以本算法的時(shí)間復(fù)雜度為:O(ListLength(LA)*ListLength(LB))。122.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)—順序表2.2.2順序表基本運(yùn)算的實(shí)現(xiàn)132.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)—順序表

線性表的順序存儲(chǔ)結(jié)構(gòu)就是:把線性表中的所有元素按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)器中指定存儲(chǔ)位置開(kāi)始的一塊連續(xù)的存儲(chǔ)空間中。這樣,線性表中第一個(gè)元素的存儲(chǔ)位置就是指定的存儲(chǔ)位置,第i+1個(gè)元素(1≤i≤n-1)的存儲(chǔ)位置緊接在第i個(gè)元素的存儲(chǔ)位置的后面。14

假定線性表的元素類型為ElemType,則每個(gè)元素所占用存儲(chǔ)空間大小(即字節(jié)數(shù))為sizeof(ElemType),整個(gè)線性表所占用存儲(chǔ)空間的大小為:

n*sizeof(ElemType)其中,n表示線性表的長(zhǎng)度。15順序表示意圖16

在定義一個(gè)線性表的順序存儲(chǔ)類型時(shí),需要定義一個(gè)數(shù)組來(lái)存儲(chǔ)線線表中的所有元素和定義一個(gè)整型變量來(lái)存儲(chǔ)線性表的長(zhǎng)度。

假定數(shù)組用data[MaxSize]表示,長(zhǎng)度整型變量用length表示,并采用結(jié)構(gòu)體類型表示,則元素類型為通用類型標(biāo)識(shí)符ElemType的線性表的順序存儲(chǔ)類型可描述如下:17#defineMaxSize50typedefstruct{ ElemTypedata[MaxSize]; intlength;}SqList;/*順序表類型*/

其中,data成員存放元素,length成員存放線性表的實(shí)際長(zhǎng)度?；蛘撸簊tructSqList{ElemTypedata[MaxSize];intlength;};18例如：LA=(23,75,41,38,54,62,17)順序表內(nèi)存示意圖：SqListQ;Q就是順序表23754138546217data[0]lengthdata[1023]data[6]7Q第1個(gè)數(shù)據(jù)元素：Q.data[0]第i個(gè)數(shù)據(jù)元素：Q.data[i-1]表長(zhǎng)：Q.length19例如：LA=(23,75,41,38,54,62,17)用指針變量指向順序表：SqList*L;第1個(gè)數(shù)據(jù)元素：(*L).data[0]或L->data[0]第i個(gè)數(shù)據(jù)元素：(*L).data[i-1]或L->data[i-1]表長(zhǎng)：(*L).length或L->length23754138546217data[0]lengthdata[1023]data[6]7L→

202.2.2順序表基本運(yùn)算的實(shí)現(xiàn)

一旦采用順序表存儲(chǔ)結(jié)構(gòu),我們就可以用C/C++語(yǔ)言實(shí)現(xiàn)線性表的各種基本運(yùn)算。為了方便,假設(shè)ElemType為char類型,使用如下自定義類型語(yǔ)句:typedefcharElemType;typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;211.建立順序表將含有n個(gè)元素的數(shù)組的每個(gè)元素依次放入到順序表中。voidCreateList(SqList*&L,ElemTypea[],intn){inti;L=newSqList;//或L=(SqList*)malloc(sizeof(SqList));for(i=0;i<n;i++)L->data[i]=a[i];L->length=n;}本算法的時(shí)間復(fù)雜度為O(n)。22(1)初始化線性表InitList(L)

該運(yùn)算的結(jié)果是構(gòu)造一個(gè)空的線性表L。實(shí)際上只需將length成員設(shè)置為0即可。

voidInitList(SqList*&L)//引用型指針

{L=(SqList*)malloc(sizeof(SqList));//或L=newSqList;

/*分配存放線性表的空間*/L->length=0;}本算法的時(shí)間復(fù)雜度為O(1)。2.順序表基本運(yùn)算算法23(2)銷毀線性表DestroyList(L)

該運(yùn)算的結(jié)果是釋放線性表L占用的內(nèi)存空間。

voidDestroyList(SqList*&L){free(L);//或deleteL;}

本算法的時(shí)間復(fù)雜度為O(1)。24(3)判定是否為空表ListEmpty(L)

該運(yùn)算返回一個(gè)值表示L是否為空表。若L為空表,則返回1,否則返回0。

intListEmpty(SqList*L){ return(L->length==0);}本算法的時(shí)間復(fù)雜度為O(1)。25(4)求線性表的長(zhǎng)度ListLength(L)

該運(yùn)算返回順序表L的長(zhǎng)度。實(shí)際上只需返回length成員的值即可。

intListLength(SqList*L){ return(L->length);}

本算法的時(shí)間復(fù)雜度為O(1)。26(5)輸出線性表DispList(L)

該運(yùn)算當(dāng)線性表L不為空時(shí),順序顯示L中各元素的值。

voidDispList(SqList*L){ inti; if(ListEmpty(L))return; for(i=0;i<L->length;i++) printf("%c",L->data[i]);//或cout<<L->data[i]; printf(“\n”);//或cout<<endl;}

時(shí)間復(fù)雜度：O(L->length)或O(n)27(6)求某個(gè)數(shù)據(jù)元素值GetElem(L,i,e)

該運(yùn)算返回L中第i(1≤i≤ListLength(L))個(gè)元素的值,存放在e中。

boolGetElem(SqList*L,inti,ElemType&e){ if(i<1||i>L->length)returnfalse; e=L->data[i-1]; returntrue;}

本算法的時(shí)間復(fù)雜度為O(1)。28(7)按元素值查找LocateElem(L,e)

該運(yùn)算順序查找第1個(gè)值域與e相等的元素的位序。若這樣的元素不存在,則返回值為0。

intLocateElem(SqList*L,ElemTypee){ inti=0; while(i<L->length&&L->data[i]!=e)i++; if(i>=L->length) return0; elsereturni+1;}29

本算法中基本運(yùn)算為while循環(huán)中的i++語(yǔ)句,故時(shí)間復(fù)雜度與e的值有關(guān):若e=L->data[0],循環(huán)0次；若e=L->data[1],循環(huán)1次；若e=L->data[2],循環(huán)2次；……若e=L->data[n-1],循環(huán)n-1次；平均次數(shù)：O(n)或O(L->length)30(8)插入數(shù)據(jù)元素ListInsert(L,i,e)

該運(yùn)算在順序表L的第i個(gè)位置(1≤i≤ListLength(L)+1)上插入新的元素e。思路：如果i值不正確,則顯示相應(yīng)錯(cuò)誤信息；否則將順序表原來(lái)第i個(gè)元素及以后元素均后移一個(gè)位置,騰出一個(gè)空位置插入新元素,順序表長(zhǎng)度增1。31a1a2

…ai-1ai

…ana1a2

…ai-1

data[0]data[L->length-1]第i個(gè)結(jié)點(diǎn)：data[i-1]需要移動(dòng)的結(jié)點(diǎn):(共n-(i-1)個(gè)）

ai~anL->data[i-1]

~L->data[L->length-1]

//結(jié)點(diǎn)右移

for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];L->data[i-1]=e;

L->length++;

ean…ai32

boolListInsert(SqList*&L,inti,ElemTypee){intj;if(i<1||i>L->length+1) returnfalse;i--;/*將順序表邏輯位序轉(zhuǎn)化為data下標(biāo)即物理位序*/for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];/*將data[i]及后面元素后移一個(gè)位置*/L->data[i]=e;L->length++;/*順序表長(zhǎng)度增1*/returntrue;}33

對(duì)于本算法來(lái)說(shuō),元素移動(dòng)的次數(shù)不僅與表長(zhǎng)L.length=n有關(guān),而且與插入位置i有關(guān):當(dāng)i=n+1時(shí),移動(dòng)次數(shù)為0；當(dāng)i=1時(shí),移動(dòng)次數(shù)為n,達(dá)到最大值。在線性表L中共有n+1個(gè)可以插入元素的地方。假設(shè)pi(=)是在第i個(gè)位置上插入一個(gè)元素的概率,則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為:

因此插入算法的平均時(shí)間復(fù)雜度為O(n)。34(9)刪除數(shù)據(jù)元素ListDelete(L,i,e)

該運(yùn)算刪除順序表L的第i個(gè)元素(1≤i≤ListLength(L))。思路：如果i值不正確,則顯示相應(yīng)錯(cuò)誤信息；否則將線性表第i個(gè)元素以后元素均向前移動(dòng)一個(gè)位置,這樣覆蓋了原來(lái)的第i個(gè)元素,達(dá)到刪除該元素的目的,最后順序表長(zhǎng)度減1。35boolListDelete(SqList*&L,inti,ElemType&e){intj;if(i<1||i>L->length) returnfalse;i--; /*將順序表邏輯位序轉(zhuǎn)化為data下標(biāo)即物理位序*/e=L->data[i];for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];/*將data[i]之后的元素前移一個(gè)位置*/L->length--; /*順序表長(zhǎng)度減1*/returntrue;}36

對(duì)于本算法來(lái)說(shuō),元素移動(dòng)的次數(shù)也與表長(zhǎng)n和刪除元素的位置i有關(guān):當(dāng)i=n時(shí),移動(dòng)次數(shù)為0；當(dāng)i=1時(shí),移動(dòng)次數(shù)為n-1。在線性表sq中共有n個(gè)元素可以被刪除。假設(shè)pi(pi=)是刪除第i個(gè)位置上元素的概率,則在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為:

因此刪除算法的平均時(shí)間復(fù)雜度為O(n)。37例設(shè)計(jì)一個(gè)算法,將兩個(gè)元素有序(從小到大)的順序表合并成一個(gè)有序順序表。

思路:將兩個(gè)順序表進(jìn)行二路歸并。例如:

順序表p:(1,3,5)←i掃描p

順序表q:(2,4,10,20)←j掃描q

歸并到順序表r中←k記錄r中元素個(gè)數(shù)

r:(1,2,3,4,5,10,20)38data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r0ijk39data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r10ijkik40data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r120jikjk41data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r1230ijkik42data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r12340jikjk43data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r123450ijkik44data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r1234510200jikjk45data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r1234510207ijk46SqList*merge(SqList*p,SqList*q){SqList*r;inti=0,j=0,k=0;r=(SqList*)malloc(sizeof(SqList));//或r=newSqListwhile(i<p->length&&j<q->length){ if(p->data[i]<q->data[j]) {r->data[k]=p->data[i]; i++;k++; } else {r->data[k]=q->data[j]; j++;k++; }}

未完。。。47

while(i<p->length) {r->data[k]=p->data[i]; i++;k++; }while(j<q->length){r->data[k]=q->data[j]; j++;k++; } r->length=k;/*或p->length+q->length*/ return(r);}48

例2.3已知順序表L，設(shè)計(jì)一個(gè)算法，刪除所有元素值等于x的元素。

解:用i從頭開(kāi)始掃描順序表，用k累計(jì)不刪除的元素個(gè)數(shù)，重建順序表,最后修改L的長(zhǎng)度。對(duì)應(yīng)的算法如下:49voiddelelem1(SqList*&L,ElemTypex){inti,k=0;/*k記錄值等于x的元素個(gè)數(shù)*/for(i=0;i<L->length;i++){if(L->data[i]!=x) {L->data[k]=l->data[i];/*當(dāng)前元素前移*/k++;}}L->length=k;/*順序表L的長(zhǎng)度等于k*/}50voiddelelem2(SqList*&L,ElemTypex){inti=0,k=0;/*k記錄值等于x的元素個(gè)數(shù)*/while(i<L->length){if(L->data[i]==x)k++;else L->data[i-k]=L->data[i];/*當(dāng)前元素前移k位*/i++;}L->length=L->length-k;/*順序表A的長(zhǎng)度遞減*/}51

上述算法中只有一個(gè)while循環(huán),時(shí)間復(fù)雜度為O(n)。算法中只用了i,k兩個(gè)臨時(shí)變量,空間復(fù)雜度為O(1)。52例2.4有順序表L,所有元素為整型且所有元素均不相等。設(shè)計(jì)算法，以第一個(gè)元素為分界線，將所有小于它的元素移到該元素的前面，所有大于它的元素移到它的后面。如：L=(7,2,10,5,4,8,3,6)經(jīng)過(guò)處理后，

L(3,2,6,5,4,7,8,10)將第一個(gè)元素作為基準(zhǔn)，存入變量pivot.j從最后元素開(kāi)始往左掃描，找一個(gè)小于等于pivot的元素；i從第1個(gè)元素開(kāi)始往右掃描，找一個(gè)大于pivot的元素；交換兩者的值。繼續(xù)，直到i==j最后，交換下標(biāo)為0的元素和下標(biāo)為i的元素53如：L=(7,2,10,5,4,8,3,6)pivot=7ij(7,2,10,5,4,8,3,6)i→

ij交換(7,2,6,5,4,8,3,10)

i

→

ij←j交換(7,2,6,5,4,3,8,10)

ij交換(3,2,6,5,4,7,8,10)54voidmove1(SqList*&L){inti=0,j=L->length-1;ElemTypepivot=L->data[0];ElemTypetemp;while(i<j){while(i<j&&L->data[j]>pivot)j--;while(i<j&&L->data[i]<=pivot)i++;if(i<j){temp=L->data[i];L->data[i]=L->data[j];L->data[j]=temp;}}55temp=L->data[0];L->data[0]=L->data[j];L->data[j]=temp;}562.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)—鏈表2.3.2單鏈表2.3.3雙鏈表2.3.4循環(huán)鏈表572.3.1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)—鏈表

在鏈?zhǔn)酱鎯?chǔ)中,每個(gè)存儲(chǔ)結(jié)點(diǎn)不僅包含有所存元素本身的信息(稱之為數(shù)據(jù)域),而且包含有元素之間邏輯關(guān)系的信息,即前驅(qū)結(jié)點(diǎn)包含有后繼結(jié)點(diǎn)的地址信息,這稱為指針域,這樣可以通過(guò)前驅(qū)結(jié)點(diǎn)的指針域方便地找到后繼結(jié)點(diǎn)的位置,提高數(shù)據(jù)查找速度。一般地,每個(gè)結(jié)點(diǎn)有一個(gè)或多個(gè)這樣的指針域。若一個(gè)結(jié)點(diǎn)中的某個(gè)指針域不需要任何結(jié)點(diǎn),則僅它的值為空,用常量NULL表示。58

由于線性表中的每個(gè)元素至多只有一個(gè)前驅(qū)元素和一個(gè)后繼元素,即數(shù)據(jù)元素之間是一對(duì)一的邏輯關(guān)系,所以當(dāng)進(jìn)行鏈?zhǔn)酱鎯?chǔ)時(shí),一種最簡(jiǎn)單也最常用的方法是:

在每個(gè)結(jié)點(diǎn)中除包含有數(shù)據(jù)域外,只設(shè)置一個(gè)指針域,用以指向其后繼結(jié)點(diǎn),這樣構(gòu)成的鏈接表稱為線性單向鏈接表,簡(jiǎn)稱單鏈表；59帶頭結(jié)點(diǎn)單鏈表示意圖

在線性表的鏈?zhǔn)酱鎯?chǔ)中,為了便于插入和刪除算法的實(shí)現(xiàn),每個(gè)鏈表帶有一個(gè)頭結(jié)點(diǎn),并通過(guò)頭結(jié)點(diǎn)的指針惟一標(biāo)識(shí)該鏈表。

602000:10002000:10102000:10202000:10302000:10402000:10502000:1060...2000:4000a32000:1040a6NULLa12000:1060a42000:1050a52000:1020a22000:1010數(shù)據(jù)域指針域數(shù)據(jù)域(存數(shù)據(jù)元素）+指針域(存后繼結(jié)點(diǎn)地址)鏈表物理結(jié)構(gòu)（設(shè)開(kāi)始結(jié)點(diǎn)地址：2000：1030）邏輯結(jié)構(gòu)a1

a2a6^

61

在單鏈表中,由于每個(gè)結(jié)點(diǎn)只包含有一個(gè)指向后繼結(jié)點(diǎn)的指針,所以當(dāng)訪問(wèn)過(guò)一個(gè)結(jié)點(diǎn)后,只能接著訪問(wèn)它的后繼結(jié)點(diǎn),而無(wú)法訪問(wèn)它的前驅(qū)結(jié)點(diǎn)。

62

另一種可以采用的方法是:在每個(gè)結(jié)點(diǎn)中除包含有數(shù)值域外,設(shè)置有兩個(gè)指針域,分別用以指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn),這樣構(gòu)成的鏈接表稱之為線性雙向鏈接表,簡(jiǎn)稱雙鏈表。帶頭結(jié)點(diǎn)的雙鏈表示意圖63

在雙向鏈表中,由于每個(gè)結(jié)點(diǎn)既包含有一個(gè)指向后繼結(jié)點(diǎn)的指針,又包含有一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針,所以當(dāng)訪問(wèn)過(guò)一個(gè)結(jié)點(diǎn)后,既可以依次向后訪問(wèn)每一個(gè)結(jié)點(diǎn),也可以依次向前訪問(wèn)每一個(gè)結(jié)點(diǎn)。64

在單鏈表中,假定每個(gè)結(jié)點(diǎn)類型用LinkList表示,它應(yīng)包括存儲(chǔ)元素的數(shù)據(jù)域,這里用data表示,其類型用通用類型標(biāo)識(shí)符ElemType表示,還包括存儲(chǔ)后繼元素位置的指針域,這里用next表示。

LinkList類型的定義如下:

typedefstructLNode/*定義單鏈表結(jié)點(diǎn)類型*/{ ElemTypedata;structLNode*next;/*指向后繼結(jié)點(diǎn)*/}LinkList;652.3.2單鏈表1.建立單鏈表

先考慮如何建立單鏈表。假設(shè)我們通過(guò)一個(gè)含有n個(gè)數(shù)據(jù)的數(shù)組來(lái)建立單鏈表。建立單鏈表的常用方法有如下兩種:(1)頭插法建表該方法從一個(gè)空表開(kāi)始,讀取字符數(shù)組a中的字符,生成新結(jié)點(diǎn),將讀取的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下:66∧head采用頭插法建立單鏈表的過(guò)程head∧adcbai=0i=1i=2i=3∧aheadbheadcb∧aheaddcb∧a第1步:建頭結(jié)點(diǎn)第2步:i＝0,新建a結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第3步:i＝1,新建d結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第4步:i＝2,新建c結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第5步:i＝3,新建b結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后67

voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));//或L=newLinkList;/*創(chuàng)建頭結(jié)點(diǎn)*/L->next=NULL;for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));//或L=newLinkList;/*創(chuàng)建新結(jié)點(diǎn)*/s->data=a[i];s->next=L->next; /*將*s插在原開(kāi)始結(jié)點(diǎn)之前,頭結(jié)點(diǎn)之后*/L->next=s;}}68(2)尾插法建表

頭插法建立鏈表雖然算法簡(jiǎn)單,但生成的鏈表中結(jié)點(diǎn)的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上,為此必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。采用尾插法建表的算法如下:69adcbi=0i=1i=2i=3head頭結(jié)點(diǎn)adcbb∧采用尾插法建立單鏈表的過(guò)程70

voidCreateListR(LinkList*&L,ElemType

a[],

int

n){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點(diǎn)*/L->next=NULL;r=L;/*r始終指向終端結(jié)點(diǎn),開(kāi)始時(shí)指向頭結(jié)點(diǎn)*/for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*/s->data=a[i];r->next=s;/*將*s插入*r之后*/r=s;}r->next=NULL; /*終端結(jié)點(diǎn)next域置為NULL*/}712.插入結(jié)點(diǎn)運(yùn)算

插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到單鏈表的第i個(gè)結(jié)點(diǎn)的位置上。先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn),再在其后插入新結(jié)點(diǎn)。單鏈表插入結(jié)點(diǎn)的過(guò)程如下圖所示。72插入結(jié)點(diǎn)示意圖733.刪除結(jié)點(diǎn)運(yùn)算

刪除運(yùn)算是將單鏈表的第i個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn),再刪除其后的結(jié)點(diǎn)。刪除單鏈表結(jié)點(diǎn)的過(guò)程如下圖所示。74刪除結(jié)點(diǎn)示意圖待刪除754.線性表基本運(yùn)算實(shí)現(xiàn)

(1)初始化線性表InitList(L)

該運(yùn)算建立一個(gè)空的單鏈表,即創(chuàng)建一個(gè)頭結(jié)點(diǎn)。

voidInitList(LinkList*&L){ L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點(diǎn)*/ L->next=NULL;}∧L76(2)銷毀線性表DestroyList(L)

釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)的空間。

voidDestroyList(LinkList*&L){ LinkList*pre=L,*p=L->next; while(p!=NULL) {free(pre); pre=p;p=pre->next; } free(pre);}77(3)判線性表是否為空表ListEmpty(L)

若單鏈表L沒(méi)有數(shù)據(jù)結(jié)點(diǎn),則返回真,否則返回假。

intListEmpty(LinkList*L){ return(L->next==NULL);}∧L78(4)求線性表的長(zhǎng)度ListLength(L)

返回單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

intListLength(LinkList*L){ LinkList*p=L;inti=0; while(p->next!=NULL) {i++; p=p->next; } return(i);}79(5)輸出線性表DispList(L)

逐一掃描單鏈表L的每個(gè)數(shù)據(jù)結(jié)點(diǎn),并顯示各結(jié)點(diǎn)的data域值。

voidDispList(LinkList*L){ LinkList*p=L->next; while(p!=NULL) {printf("%c",p->data);//or:cout<<p->data; p=p->next; } printf("\n");//or:cout<<endl;}80(6)求線性表L中指定位置的某個(gè)數(shù)據(jù)元素GetElem(L,i,&e)

思路：在單鏈表L中從頭開(kāi)始找到第i個(gè)結(jié)點(diǎn),若存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn),則將其data域值賦給變量e。81

boolGetElem(LinkList*L,inti,ElemType&e){ intj=0; LinkList*p=L; while(j<i&&p!=NULL) {j++; p=p->next; } if(p==NULL)returnfalse;/*不存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ else /*存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ {e=p->data; returntrue; }}82(7)按元素值查找LocateElem(L,e)

思路：在單鏈表L中從頭開(kāi)始找第1個(gè)值域與e相等的結(jié)點(diǎn),若存在這樣的結(jié)點(diǎn),則返回位置,否則返回0。

intLocateElem(LinkList*L,ElemTypee){ LinkList*p=L->next;intn=1; while(p!=NULL&&p->data!=e) {p=p->next;n++;} if(p==NULL)return(0); elsereturn(n);}83(8)插入數(shù)據(jù)元素ListInsert(&L,i,e)

思路：先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)*p,若存在這樣的結(jié)點(diǎn),將值為e的結(jié)點(diǎn)*s插入到其后。

boolListInsert(LinkList*&L,inti,ElemTypee){intj=0;LinkList*p=L,*s;while(j<i-1&&p!=NULL)/*查找第i-1個(gè)結(jié)點(diǎn)*/{j++; p=p->next;}84

if(p==NULL)returnfalse;/*未找到位序?yàn)閕-1的結(jié)點(diǎn)*/ else /*找到位序?yàn)閕-1的結(jié)點(diǎn)*p*/ {s=(LinkList*)malloc(sizeof(LinkList)); /*或newLinkList創(chuàng)建新結(jié)點(diǎn)*s*/ s->data=e; s->next=p->next;/*將*s插入到*p之后*/ p->next=s; returntrue; }}85(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e)

思路：先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)*p,若存在這樣的結(jié)點(diǎn),且也存在后繼結(jié)點(diǎn),則刪除該后繼結(jié)點(diǎn)。

boolListDelete(LinkList*&L,inti,ElemType&e){ intj=0; LinkList*p=L,*q; while(j<i-1&&p!=NULL)/*查找第i-1個(gè)結(jié)點(diǎn)*/ {j++; p=p->next; }86

if(p==NULL)returnfalse;/*未找到位序?yàn)閕-1的結(jié)點(diǎn)*/ else /*找到位序?yàn)閕-1的結(jié)點(diǎn)*p*/ {q=p->next; /*q指向要?jiǎng)h除的結(jié)點(diǎn)*/ if(q==NULL)returnfalse; /*若不存在第i個(gè)結(jié)點(diǎn),返回0*/e=q->data; p->next=q->next; /*從單鏈表中刪除*q結(jié)點(diǎn)*/ free(q); /*釋放*q結(jié)點(diǎn)*/ returntrue; }}87

例2.5設(shè)L={a1,b1,a2,b2,…,an,bn}為一線性表,采用帶頭結(jié)點(diǎn)的L單鏈表存放,編寫(xiě)一個(gè)算法,將其拆分為兩個(gè)線性表,使得:L1={a1,a2,…,an},L2={bn,bn-1,…,b1}L1單鏈表由尾插法建立；L2由頭插法建立。

88

voidsplit(LinkList*L,LinkList*&L1,LinkList*&L2){LinkList*p=L->next,*q,*r1;L1=L; /*L1的頭結(jié)點(diǎn)利用L的頭結(jié)點(diǎn)*/r1=L1;/*r1始終指向L1表的尾結(jié)點(diǎn)*/L2=(LinkList*)malloc(sizeof(LinkList)); /*或L2=newLinkList創(chuàng)建L2的頭結(jié)點(diǎn)*/L2->next=NULL;89

while(p!=NULL){q=p->next;/*q指向*p的直接后繼結(jié)點(diǎn)*/r1->next=p;r1=p;/*將*p鏈到L1單鏈表未尾*/p=q;/*p指向下個(gè)結(jié)點(diǎn)*q*/q=p->next;p->next=L2->next;/*將*q結(jié)點(diǎn)插入到L2頭結(jié)點(diǎn)后*/L2->next=p;p=q; }r1->next=NULL;/*L1表的尾結(jié)點(diǎn)的next域置空*/}90

本算法實(shí)際上是采用尾插法和頭插法建立兩個(gè)新表。所以,頭插法和尾插法建表算法是很多類似習(xí)題的基礎(chǔ)！91例2.6有一個(gè)帶頭結(jié)點(diǎn)的單鏈表L,設(shè)計(jì)一個(gè)算法刪除元素值最大的結(jié)點(diǎn)。92voiddelmaxnode(LinkList*&L){LinkList*pre=L,*p=L->next,*maxpre=pre,*maxp=p;while(p!=NULL){if(maxp->data<p->data){maxpre=pre;maxp=p;}pre=p;p=p->next;}maxpre->next=maxp->next;free(maxp);}93

例2.7有一個(gè)帶頭結(jié)點(diǎn)的單鏈表L,設(shè)計(jì)一個(gè)算法使其元素遞增有序。解:若原單鏈表中有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn),先構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表(只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表一定是有序表)。掃描原單鏈表余下的結(jié)點(diǎn)*p(直到p==NULL為止),在有序表中通過(guò)比較找插入*p的前驅(qū)結(jié)點(diǎn)*pre,然后將*p插入到*pre之后(這里實(shí)際上采用的是直接插入排序方法)。

94

voidSort(LinkList*&L){ LinkList*pre,*p,*q; if(L->next==NULL)return;/*若單鏈表L空，結(jié)束*/p=L->next->next;//p指向第2個(gè)結(jié)點(diǎn)

L->next->next=NULL;//構(gòu)造只有1個(gè)結(jié)點(diǎn)的單鏈表

while(p!=NULL) {q=p->next;//q保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針

pre=L;while(pre->next!=NULL&&pre->next->data<p->data) pre=pre->next;//在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*prep->next=pre->next; //將*p插入到*pre之后

pre->next=p; p=q; //掃描原單鏈表余下的結(jié)點(diǎn)

}}952.3.3雙鏈表

對(duì)于雙鏈表,采用類似于單鏈表的類型定義,其DLinkList類型的定義如下:

typedefstructDNode/*定義雙鏈表結(jié)點(diǎn)類型*/{ ElemTypedata;structDNode*prior; /*指向前驅(qū)結(jié)點(diǎn)*/ structDNode*next;/*指向后繼結(jié)點(diǎn)*/}DLinkList;96頭插法建立雙鏈表與頭插法建立單鏈表類似：voidCreateListF(DLinkList*&L,ElemTypea[],intn){DLinkList*s;inti;L=(DLinkList*)malloc(sizeof(DLinkList));//L=newDLinkList;/*創(chuàng)建頭結(jié)點(diǎn)*/L->next=NULL;L->prior=NULL;for(i=0;i<n;i++){s=(DLinkList*)malloc(sizeof(DLinkList));/*創(chuàng)建新結(jié)點(diǎn)*/s->data=a[i];s->next=L->next; /*將*s插在原開(kāi)始結(jié)點(diǎn)之前,頭結(jié)點(diǎn)之后*/

if(L->next!=NULL)L->next->prior=s;L->next=s;s->prior=L;}}97

在雙鏈表中,有些操作如求長(zhǎng)度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的,這里不多討論。但在單鏈表中,進(jìn)行結(jié)點(diǎn)插入和刪除時(shí)涉及到前后結(jié)點(diǎn)的一個(gè)指針域的變化。而在雙鏈表中,結(jié)點(diǎn)的插入和刪除操作涉及到前后結(jié)點(diǎn)的兩個(gè)指針域的變化。98雙鏈表中插入結(jié)點(diǎn)示意圖99

歸納起來(lái),在雙鏈表中p所指的結(jié)點(diǎn)之后插入一個(gè)*s結(jié)點(diǎn)。其操作語(yǔ)句描述為:

s->next=p->next;/*將*s插入到*p之后*/if(p->next!=NULL)//若*p結(jié)點(diǎn)有后繼結(jié)點(diǎn)

p->next->prior=s;//則*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)往前指

s->prior=p;//*s結(jié)點(diǎn)往前指向*p結(jié)點(diǎn)

p->next=s;//*p結(jié)點(diǎn)往后指向*s結(jié)點(diǎn)100

在雙鏈表中插入數(shù)據(jù)元素ListInsert(&L,i,e)

思路：先在雙鏈表L中找到第i-1個(gè)結(jié)點(diǎn)*p,若存在這樣的結(jié)點(diǎn),將值為e的結(jié)點(diǎn)*s插入到其后。boolListInsert(DLinkList*&L,inti,ElemTypee){intj=0;DLinkList*p=L,*s;while(j<i-1&&p!=NULL)/*查找第i-1個(gè)結(jié)點(diǎn)*/{j++; p=p->next;}101

if(p==NULL)returnfalse;/*未找到位序?yàn)閕-1的結(jié)點(diǎn)*/ else /*找到位序?yàn)閕-1的結(jié)點(diǎn)*p*/ {s=(DLinkList*)malloc(sizeof(DLinkList)); /*或s=newDLinList創(chuàng)建新結(jié)點(diǎn)*s*/ s->data=e; s->next=p->next;/*將*s插入到*p之后*/if(p->next!=NULL)p->next->prior=s;s->prior=p; p->next=s; returntrue; }}102刪除結(jié)點(diǎn)示意圖

在雙鏈表中刪除一個(gè)結(jié)點(diǎn)的過(guò)程如右圖所示:103

歸納起來(lái),刪除雙鏈表L中*p結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)。其操作語(yǔ)句描述為:q=p->next;//q指向要?jiǎng)h除的結(jié)點(diǎn)

if(q==NULL)return0;

p->next=q->next;if(q->next!=NULL)q->next->prior=p;free(q);104例2.8有帶頭結(jié)點(diǎn)的雙鏈表L，設(shè)計(jì)算法將其所有元素逆置。解：先構(gòu)造一個(gè)只有頭結(jié)點(diǎn)的雙鏈表L,用指針p掃描雙鏈表的每個(gè)結(jié)點(diǎn)，采用頭插法將*p結(jié)點(diǎn)插入到表L中。105voidreverse(DLinkList*&L){DLinkList*p,*q;p=L->next;//p指向第1個(gè)數(shù)據(jù)結(jié)點(diǎn)

L->next=NULL;//構(gòu)造只有頭結(jié)點(diǎn)的空表Lwhile(p!=NULL){q=p->next;//q指向*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)

p->next=L->next;//用頭插法將*p插入雙鏈表L中

if(L->next!=NULL)L->next->prior=p;L->next=p;p->prior=L;p=q;//p指向下個(gè)要逆置的結(jié)點(diǎn)

}}1062.3.4循環(huán)鏈表

循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域不再是空,而是指向表頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)。由此,從表中任一結(jié)點(diǎn)出發(fā)均可找到鏈表中其他結(jié)點(diǎn)。107

帶頭結(jié)點(diǎn)的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖108例：寫(xiě)出計(jì)算單循環(huán)鏈表的長(zhǎng)度的算法intLength(LinkList*L){intlen=0;LinkList*p;

p=L->next;

while(p!=L)

{p=p->next;len++;}returnlen;}另一寫(xiě)法：intLength(LinkList*L){intlen=0;LinkList*p;

p=L;

while(p->next!=L)

{p=p->next;len++;}returnlen;}109

例2.10有一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈表L，設(shè)計(jì)算法統(tǒng)計(jì)其data域值為x的結(jié)點(diǎn)個(gè)數(shù)。a1a2…...anLppppp110

intcount(LinkList*L,ElemTypex){intn=0;LinkList*p=L->next;while(p!=L){if(p->data==x)n++;p=p->next;}returnn;}a1a2…...anLp111booldeleelem(DLinkList*&L,ElemTypex){DLinkList*p=L->next;while(p!=L&&p->data!=x)p=p->next;if(p!=L)//p指著值為x的結(jié)點(diǎn),下面刪除*p結(jié)點(diǎn)

{p->next->prior=p->prior;p->prior->next=p->next;free(p);returntrue;}elsereturnfalse;}例2.11：有一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L，設(shè)計(jì)一個(gè)算法刪除第一個(gè)data域值為x的結(jié)點(diǎn)1122.4線性表的應(yīng)用

通過(guò)計(jì)算任意兩個(gè)表的簡(jiǎn)單自然連接過(guò)程討論線性表的應(yīng)用。假設(shè)有兩個(gè)表A和B,分別是m1行、n1列和m2行、n2列,它們簡(jiǎn)單自然連接結(jié)果C=AB,其中i表示表A中列號(hào),j表示表B中的列號(hào),C為A和B的笛卡兒積中滿足指定連接條件的所有記錄組,該連接條件為表A的第i列與表B的第j列相等。例如:i=j113

C=AB的計(jì)算結(jié)果如下:

3=1114

由于每個(gè)表的行數(shù)不確定,為此,用單鏈表作為表的存儲(chǔ)結(jié)構(gòu),每行作為一個(gè)數(shù)據(jù)結(jié)點(diǎn)。另外,每行中的數(shù)據(jù)個(gè)數(shù)也是不確定的,但由于需要提供隨機(jī)查找行中的數(shù)據(jù),所以每行的數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu),這里用長(zhǎng)度為MaxCol的數(shù)組存儲(chǔ)每行的數(shù)據(jù)。因此,該單鏈表中數(shù)據(jù)結(jié)點(diǎn)類型定義如下:#defineMaxCol5 /*最大列數(shù)*/typedefstructNode1 /*定義數(shù)據(jù)結(jié)點(diǎn)類型*/{ElemTypedata[MaxCol];structNode1*next; /*指向后繼數(shù)據(jù)結(jié)點(diǎn)*/}DList;115

另外,需要指定每個(gè)表的行數(shù)和列數(shù),為此將單鏈表的頭結(jié)點(diǎn)類型定義如下:

typedefstructNode2 /*定義頭結(jié)點(diǎn)類型*/{intRow,Col; /*行數(shù)和列數(shù)*/DList*next; /*指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/}HList;33123233111A32351634B116頭結(jié)點(diǎn)33123233111A32351634B55123351233423335C2333411116117采用尾插法建表方法創(chuàng)建單鏈表,用戶先輸入表的行數(shù)和列數(shù),然后輸入各行的數(shù)據(jù),為了簡(jiǎn)便,假設(shè)表中數(shù)據(jù)為int型,因此定義:

typedefintElemType;

對(duì)應(yīng)的建表算法如下:118voidCreateTable(HList*&h){inti,j;DList*r,*s;h=newHList;h->next=NULL;cout<<"表的行數(shù),列數(shù):";cin>>h->Row>>h->Col;for(i=0;i<h->Row;i++){cout<<"第"<<i+1<<"行:";s=newDList; for(j=0;j<h->Col;j++) cin>>s->data[j]; if(h->next==NULL)h->next=s; elser->next=s; r=s;/*r始終指向最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/}r->next=NULL; }119對(duì)應(yīng)的輸出表的算法如下:voidDisplayTable(HList*h){intj;DList*p=h->next;while(p!=NULL){for(j=0;j<h->Col;j++) cout<<p->data[j]; cout<<"\n"; p=p->next;}}120

為了實(shí)現(xiàn)兩個(gè)表h1和h2的簡(jiǎn)單自然連接,先要輸入兩個(gè)表連接的列序號(hào)f1和f2,然后掃描單鏈表h1,對(duì)于h1的每個(gè)