第2部分線表說(shuō)課材料

第2章線性表

2.1線性表的基本概念

2.2線性表的順序存儲(chǔ)2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.4線性表的應(yīng)用

本章小結(jié)

2.5有序表

2.1線性表的基本概念

2.1.1線性表的定義2.1.2線性表的運(yùn)算A1a2a3a4a5a6a72.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)

其中a1為第一個(gè)元素,又稱做表頭元素,a2為第二個(gè)元素,an為最后一個(gè)元素,又稱做表尾元素。例如,在線性表(1,4,3,2,8,10)中,1為表頭元素,10為表尾元素。抽象數(shù)據(jù)類型描述ADTList{

數(shù)據(jù)對(duì)象：D={ai|ai屬于Elemtype,i=1,2,…,n,n>=0} 數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai屬于D,i=2,…,n} 基本操作： InitList(＆L) DestroyList(＆L) ListEmpty(L) ListLength(L)DispList(L) GetElem(L,i,＆e) LocateElem(L,e) ListInsert(&L,i,e) ListDelete(&L,i,&e) }ADTList2.1.2線性表的運(yùn)算線性表的基本運(yùn)算如下:(1)初始化線性表InitList(&L):構(gòu)造一個(gè)空的線性表L。(2)銷毀線性表DestroyList(&L):釋放線性表L占用的內(nèi)存空間。

(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(1≤i≤ListLength(L))個(gè)元素的值。

(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。

例2.1假設(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中。算法如下:voidunionList(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);

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中*/ }}

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

線性表的順序存儲(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ǔ)位置的后面。

假定線性表的元素類型為ElemType,則每個(gè)元素所占用存儲(chǔ)空間大小(即字節(jié)數(shù))為sizeof(ElemType),整個(gè)線性表所占用存儲(chǔ)空間的大小為:n*sizeof(ElemType)其中,n表示線性表的長(zhǎng)度。順序表示意圖

在定義一個(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ǔ)類型可描述如下:

typedefstruct{ ElemTypedata[MaxSize]; intlength;}SqList;/*順序表類型*/

其中,data成員存放元素,length成員存放線性表的實(shí)際長(zhǎng)度。說(shuō)明：由于C/C++中數(shù)組的下標(biāo)從0開(kāi)始，線性表的第i個(gè)元素ai存放順序表的第i-1位置上。為了清楚，我們ai在邏輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理位序。/*分配存放線性表的空間*/SqListL=(SqList*)malloc(sizeof(SqList))/*訪問(wèn)線性表的數(shù)據(jù)域*/L->data[i]/*訪問(wèn)線性表的長(zhǎng)度域*/L->lengthdatalength2.2.2順序表基本運(yùn)算的實(shí)現(xiàn)

一旦采用順序表存儲(chǔ)結(jié)構(gòu),我們就可以用C/C++語(yǔ)言實(shí)現(xiàn)線性表的各種基本運(yùn)算。為了方便,假設(shè)ElemType為char類型,使用如下自定義類型語(yǔ)句:typedefcharElemType;建立順序表其方法是將給定的含有n個(gè)元素的數(shù)組的每個(gè)元素依次放入到順序表中，并將n賦給順序表的長(zhǎng)度成員。算法如下：

voidCreateList(SqList*&L,ElemTypea[],intn)/*建立順序表*/{ inti; for(i=0;i<n;i++) L->data[i]=a[i]; L->length=n;}順序表基本運(yùn)算算法(1)初始化線性表InitList(L)該運(yùn)算的結(jié)果是構(gòu)造一個(gè)空的線性表L。實(shí)際上只需將length成員設(shè)置為0即可。

voidInitList(SqList*&L)//引用型指針{L=(SqList*)malloc(sizeof(SqList)); /*分配存放線性表的空間*/L->length=0;}本算法的時(shí)間復(fù)雜度為O(1)。(2)銷毀線性表DestroyList(L)該運(yùn)算的結(jié)果是釋放線性表L占用的內(nèi)存空間。

voidDestroyList(SqList*&L){free(L);}本算法的時(shí)間復(fù)雜度為O(1)。(3)判定是否為空表ListEmpty(L)該運(yùn)算返回一個(gè)值表示L是否為空表。若L為空表,則返回1,否則返回0。

intListEmpty(SqList*L){ return(L->length==0);}本算法的時(shí)間復(fù)雜度為O(1)。(4)求線性表的長(zhǎng)度ListLength(L)該運(yùn)算返回順序表L的長(zhǎng)度。實(shí)際上只需返回length成員的值即可。

intListLength(SqList*L){ return(L->length);}本算法的時(shí)間復(fù)雜度為O(1)。(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]); printf("\n");}

本算法中基本運(yùn)算為for循環(huán)中的printf語(yǔ)句,故時(shí)間復(fù)雜度為:O(L->length)或O(n)(6)求某個(gè)數(shù)據(jù)元素值GetElem(L,i,e)該運(yùn)算返回L中第i(1≤i≤ListLength(L))個(gè)元素的值,存放在e中。

intGetElem(SqList*L,inti,ElemType&e){ if(i<1||i>L->length)return0; e=L->data[i-1]; return1;}本算法的時(shí)間復(fù)雜度為O(1)。(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;}

本算法中基本運(yùn)算為while循環(huán)中的i++語(yǔ)句,故時(shí)間復(fù)雜度為:O(L->length)或O(n)(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。intListInsert(SqList*&L,inti,ElemTypee){intj;if(i<1||i>L->length+1) return0;i--;/*將順序表邏輯位序轉(zhuǎn)化為elem下標(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*/return1;}

對(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á)到最大值。在線性表sq中共有n+1個(gè)可以插入元素的地方。假設(shè)pi(=)是在第i個(gè)位置上插入一個(gè)元素的概率,則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為:

因此插入算法的平均時(shí)間復(fù)雜度為O(n)。(9)刪除數(shù)據(jù)元素ListDelete(L,i,e)刪除順序表L中的第i(1≤i≤ListLength(L))個(gè)元素。思路：如果i值不正確,則顯示相應(yīng)錯(cuò)誤信息；否則將線性表第i個(gè)元素以后元素均向前移動(dòng)一個(gè)位置,這樣覆蓋了原來(lái)的第i個(gè)元素,達(dá)到刪除該元素的目的,最后順序表長(zhǎng)度減1。intListDelete(SqList*&L,inti,ElemType&e){intj;if(i<1||i>L->length) return0;i--; /*將順序表邏輯位序轉(zhuǎn)化為elem下標(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*/return1;}

對(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)。

例2.2設(shè)計(jì)一個(gè)算法,將x插入到一個(gè)有序(從小到大排序)的線性表(順序存儲(chǔ)結(jié)構(gòu)即順序表)的適當(dāng)位置上,并保持線性表的有序性。解:先通過(guò)比較在順序表L中找到存放x的位置i,然后將x插入到L.data[i]中,最后將順序表的長(zhǎng)度增1。voidInsert(SqList*&L,ElemTypex){inti=0,j;while(i<L->length&&L->data[i]<x) i++;for(j=L->length-1;j>=i;j--) L->data[j+1]=L->data[j];L->data[i]=x;L->length++;}查找插入位置L[0]L[1]…L[i]L[i+1]…L[n-1]元素后移一個(gè)位置2.3線性表的鏈?zhǔn)酱鎯?chǔ)

2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)—鏈表2.3.2單鏈表基本運(yùn)算的實(shí)現(xiàn)2.3.3雙鏈表2.3.4循環(huán)鏈表2.3.5靜態(tài)鏈表2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)—鏈表

在鏈?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表示。由于順序表中的每個(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)稱單鏈表；帶頭結(jié)點(diǎn)單鏈表示意圖

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

在單鏈表中,由于每個(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)。

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

在雙鏈表中,由于每個(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)。雙鏈表的特點(diǎn)

在單鏈表中,假定每個(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;2.3.2單鏈表基本運(yùn)算的實(shí)現(xiàn)

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é)束為止。采用頭插法建表的算法如下:adcbi=0i=1i=2i=3∧head采用頭插法建立單鏈表的過(guò)程heada∧headda∧headcda∧headbcda∧第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)之后voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結(jié)點(diǎn)*/L->next=NULL;for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(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;}}(2)尾插法建表頭插法建立鏈表雖然算法簡(jiǎn)單,但生成的鏈表中結(jié)點(diǎn)的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上,為此必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。采用尾插法建表的算法如下:adcbi=0i=1i=2i=3head頭結(jié)點(diǎn)adcbb∧采用尾插法建立單鏈表的過(guò)程voidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點(diǎn)*/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*/}2.插入結(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ò)程如下圖所示。插入結(jié)點(diǎn)示意圖3.刪除結(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ò)程如下圖所示。刪除結(jié)點(diǎn)示意圖4.線性表基本運(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;}(2)銷毀線性表DestroyList(L)釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)的空間。voidDestroyList(LinkList*&L){ LinkList*p=L,*q=p->next; while(q!=NULL) {free(p); p=q;q=p->next; } free(p);}(3)判線性表是否為空表ListEmpty(L)若單鏈表L沒(méi)有數(shù)據(jù)結(jié)點(diǎn),則返回真,否則返回假。

intListEmpty(LinkList*L){ return(L->next==NULL);}

(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);}(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); p=p->next; } printf("\n");}(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。intGetElem(LinkList*L,inti,ElemType&e){ intj=0; LinkList*p=L; while(j<i&&p!=NULL) {j++; p=p->next; } if(p==NULL)return0;/*不存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ else /*存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ {e=p->data; return1; }}(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);}(8)插入數(shù)據(jù)元素ListInsert(&L,i,e)思路：先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)*p,若存在這樣的結(jié)點(diǎn),將值為e的結(jié)點(diǎn)*s插入到其后。intListInsert(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;}

if(p==NULL)return0;/*未找到位序?yàn)閕-1的結(jié)點(diǎn)*/ else /*找到位序?yàn)閕-1的結(jié)點(diǎn)*p*/ {s=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建新結(jié)點(diǎn)*s*/ s->data=e; s->next=p->next;/*將*s插入到*p之后*/ p->next=s; return1; }}(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e)思路：先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)*p,若存在這樣的結(jié)點(diǎn),且也存在后繼結(jié)點(diǎn),則刪除該后繼結(jié)點(diǎn)。intListDelete(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; } if(p==NULL)return0;/*未找到位序?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)return0; /*若不存在第i個(gè)結(jié)點(diǎn),返回0*/ p->next=q->next; /*從單鏈表中刪除*q結(jié)點(diǎn)*/ free(q); /*釋放*q結(jié)點(diǎn)*/ return1; }}

例2.6有一個(gè)帶頭結(jié)點(diǎn)的單鏈表head,其ElemType類型為char,設(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)*q,然后將*p插入到*q之后(這里實(shí)際上采用的是直接插入排序方法)。

voidSort(LinkList*&head){ LinkList*p=head->next,*q,*r; if(p!=NULL)/*head有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn)*/ {r=p->next;/*r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針*/ p->next=NULL;/*構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表*/ p=r; while(p!=NULL) { r=p->next; /*r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針*/

q=head; while(q->next!=NULL&&q->next->data<p->data) q=q->next;/*在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*q*/p->next=q->next; /*將*p插入到*q之后*/ q->next=p; p=r; /*掃描原單鏈表余下的結(jié)點(diǎn)*/}}}2.3.3雙鏈表

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

typedefstructDNode/*定義雙鏈表結(jié)點(diǎn)類型*/{ ElemTypedata;structDNode*prior;/*指向前驅(qū)結(jié)點(diǎn)*/ structDNode*next;/*指向后繼結(jié)點(diǎn)*/}DLinkList;在雙鏈表中,有些操作如求長(zhǎng)度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的,這里不多討論。但在單鏈表中,進(jìn)行結(jié)點(diǎn)插入和刪除時(shí)涉及到前后結(jié)點(diǎn)的一個(gè)指針域的變化。而在雙鏈表中,結(jié)點(diǎn)的插入和刪除操作涉及到前后結(jié)點(diǎn)的兩個(gè)指針域的變化。雙鏈表中插入結(jié)點(diǎn)示意圖

歸納起來(lái),在雙鏈表中p所指的結(jié)點(diǎn)之后插入一個(gè)*s結(jié)點(diǎn)。其操作語(yǔ)句描述為:s->next=p->next;/*將*s插入到*p之后*/p->next->prior=s;s->prior=p;p->next=s;刪除結(jié)點(diǎn)示意圖在雙鏈表中刪除一個(gè)結(jié)點(diǎn)的過(guò)程如右圖所示:

歸納起來(lái),刪除雙鏈表L中*p結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)。其操作語(yǔ)句描述為:p->next=q->next;q->next->prior=p;2.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)。

帶頭結(jié)點(diǎn)的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖判斷表尾結(jié)點(diǎn)p的條件：p->next==head判斷表空的條件：p->next==head例2.6有一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表head，設(shè)計(jì)一個(gè)算法，統(tǒng)計(jì)其data域?yàn)閤的結(jié)點(diǎn)的個(gè)數(shù)。解:掃描整個(gè)單循環(huán)鏈表，用n累計(jì)data域值為x的個(gè)數(shù)。算法如下：Intcount(LinkList*head,Elemtypex){intn=0;LinkList*p=head->next;While(P!=head){if(p->data==x)n++;p=p->next;}Return(n)}2.3.5靜態(tài)鏈表

靜態(tài)鏈表借用一維數(shù)組來(lái)描述線性鏈表。數(shù)組中的一個(gè)分量表示一個(gè)結(jié)點(diǎn),同時(shí)使用游標(biāo)(指示器cur即為偽指針)代替指針以指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置。數(shù)組中的第0個(gè)分量可以看成頭結(jié)點(diǎn),其指針域指示靜態(tài)鏈表的第一個(gè)結(jié)點(diǎn)。這種存儲(chǔ)結(jié)構(gòu)仍然需要預(yù)先分配一個(gè)較大空間,但是在進(jìn)行線性表的插入和刪除操作時(shí)不需要移動(dòng)元素,僅需要修改“指針”,因此仍然具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)。

下圖給出了一個(gè)靜態(tài)鏈表的示例。圖(a)是一個(gè)修改之前的靜態(tài)鏈表,圖(b)是刪除數(shù)據(jù)元素“陳華”之后的靜態(tài)鏈表,圖(c)插入數(shù)據(jù)元素“王華”之后的靜態(tài)鏈表,圖中用陰影表示修改的游標(biāo)。2.4線性表的應(yīng)用

計(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=j

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

3=1由于每個(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)類型定義如下:#defineMaxCol10 /*最大列數(shù)*/typedefstructNode1 /*定義數(shù)據(jù)結(jié)點(diǎn)類型*/{ElemTypedata[MaxCol];structNode1*next; /*指向后繼數(shù)據(jù)結(jié)點(diǎn)*/}DList;另外,需要指定每個(gè)表的行數(shù)和列數(shù),為此將單鏈表的頭結(jié)點(diǎn)類型定義如下:

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

typedefintElemType;對(duì)應(yīng)的建表算法如下:voidcreate(HList*&h){inti,j;DList*r,*s;h=(HList*)malloc(sizeof(HList));h->next=NULL;printf("表的行數(shù),列數(shù):");scanf("%d%d",&h->Row,&h->Col);for(i=0;i<h->Row;i++){printf("第%d行:",i+1);s=(DList*)malloc(sizeof(DList)); for(j=0;j<h->Col;j++) scanf("%d"