演示文稿數(shù)據(jù)結(jié)構(gòu)線性表課件

演示文稿數(shù)據(jù)結(jié)構(gòu)線性表第一頁，共一百零六頁。（優(yōu)選）數(shù)據(jù)結(jié)構(gòu)線性表第二頁，共一百零六頁。2.1線性表的基本概念

2.1.1線性表的定義2.1.2線性表的運算第三頁，共一百零六頁。2.1.1線性表的定義

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

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

(1,4,3,2,8,10)中,1為表頭元素,10為表尾元素。第五頁，共一百零六頁。2.1.2線性表的運算線性表的基本運算如下:(1)初始化線性表InitList(&L):構(gòu)造一個空的線性表L。

(2)銷毀線性表DestroyList(&L):釋放線性表L占用的內(nèi)存空間。第六頁，共一百零六頁。

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

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

(5)輸出線性表DispList(L):當線性表L不為空時,順序顯示L中各結(jié)點的值域。

(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))個元素的值。第七頁，共一百零六頁。

(7)定位查找LocateElem(L,e):返回L中第1個值域與e相等的位序。若這樣的元素不存在,則返回值為0。

(8)插入數(shù)據(jù)元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)個元素之前插入新的元素e,L的長度增1。

(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e):刪除L的第i(1≤i≤ListLength(L))個元素,并用e返回其值,L的長度減1。第八頁，共一百零六頁。

例2.1

假設(shè)有兩個集合A和B分別用兩個線性表LA和LB表示,即線性表中的數(shù)據(jù)元素即為集合中的成員。編寫一個算法求一個新的集合C=A∪B,即將兩個集合的并集放在線性表LC中。解:本算法思想是:先初始化線性表LC,將LA的所有元素復(fù)制到LC中,然后掃描線性表LB,若LB的當前元素不在線性表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);/*求線性表的長度*/lenB=ListLength(LB);第十頁，共一百零六頁。

for(i=1;i<=lenb;i++) { GetElem(LB,i,e); /*取LB中第i個數(shù)據(jù)元素賦給e*/ if(!LocateElem(LA,e)) ListInsert(LC,++lenc,e); /*LA中不存在和e相同者,則插入到LC中*/ }}第十一頁，共一百零六頁。

由于LocateElem(LA,e)運算的時間復(fù)雜度為O(ListLength(LA)),所以本算法的時間復(fù)雜度為:O(ListLength(LA)*ListLength(LB))。第十二頁，共一百零六頁。2.2線性表的順序存儲2.2.1線性表的順序存儲—順序表2.2.2順序表基本運算的實現(xiàn)第十三頁，共一百零六頁。2.2.1線性表的順序存儲—順序表

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

線性表邏輯結(jié)構(gòu)順序表存儲結(jié)構(gòu)第十四頁，共一百零六頁。

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

n*sizeof(ElemType)其中,n表示線性表的長度。第十五頁，共一百零六頁。順序表示意圖第十六頁，共一百零六頁。

在定義一個線性表的順序存儲類型時,需要定義一個數(shù)組來存儲線線表中的所有元素和定義一個整型變量來存儲線性表的長度。假定數(shù)組用data[MaxSize]表示,長度整型變量用length表示,并采用結(jié)構(gòu)體類型表示,則元素類型為通用類型標識符ElemType的線性表的順序存儲類型可描述如下:第十七頁，共一百零六頁。

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

其中,data成員存放元素,length成員存放線性表的實際長度。

說明：由于C/C++中數(shù)組的下標從0開始，線性表的第i個元素ai存放順序表的第i-1位置上。為了清楚，將ai在邏輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理位序。第十八頁，共一百零六頁。2.2.2順序表基本運算的實現(xiàn)

一旦采用順序表存儲結(jié)構(gòu),我們就可以用C/C++語言實現(xiàn)線性表的各種基本運算。為了方便,假設(shè)ElemType為char類型,使用如下自定義類型語句:

typedefcharElemType;第十九頁，共一百零六頁。1.建立順序表其方法是將給定的含有n個元素的數(shù)組的每個元素依次放入到順序表中，并將n賦給順序表的長度成員。算法如下：

voidCreateList(SqList*&L,ElemTypea[],intn)

/*建立順序表*/

{

inti;L=(SqList*)malloc(sizeof(SqList));

for(i=0;i<n;i++) L->data[i]=a[i];

L->length=n;

}第二十頁，共一百零六頁。2.順序表基本運算算法(1)初始化線性表InitList(L)

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

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

{L=(SqList*)malloc(sizeof(SqList)); /*分配存放線性表的空間*/L->length=0;}

本算法的時間復(fù)雜度為O(1)。順序表L第二十一頁，共一百零六頁。(2)銷毀線性表DestroyList(L)

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

voidDestroyList(SqList*&L){free(L);}

本算法的時間復(fù)雜度為O(1)。第二十二頁，共一百零六頁。(3)判定是否為空表ListEmpty(L)

該運算返回一個值表示L是否為空表。若L為空表,則返回1,否則返回0。

intListEmpty(SqList*L){ return(L->length==0);}本算法的時間復(fù)雜度為O(1)。第二十三頁，共一百零六頁。(4)求線性表的長度ListLength(L)

該運算返回順序表L的長度。實際上只需返回length成員的值即可。

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

本算法的時間復(fù)雜度為O(1)。第二十四頁，共一百零六頁。(5)輸出線性表DispList(L)

該運算當線性表L不為空時,順序顯示L中各元素的值。

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

第二十五頁，共一百零六頁。

本算法中基本運算為for循環(huán)中的printf語句,故時間復(fù)雜度為:O(L->length)或O(n)第二十六頁，共一百零六頁。(6)求某個數(shù)據(jù)元素值GetElem(L,i,e)

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

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

本算法的時間復(fù)雜度為O(1)。第二十七頁，共一百零六頁。(7)按元素值查找LocateElem(L,e)

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

intLocateElem(SqList*L,ElemTypee){ inti=0; while(i<L->length&&L->data[i]!=e)i++; if(i>=L->length) return0; elsereturni+1;}第二十八頁，共一百零六頁。

本算法中基本運算為while循環(huán)中的i++語句,故時間復(fù)雜度為:O(L->length)或O(n)第二十九頁，共一百零六頁。(8)插入數(shù)據(jù)元素ListInsert(L,i,e)

該運算在順序表L的第i個位置(1≤i≤ListLength(L)+1)上插入新的元素e。思路：如果i值不正確,則顯示相應(yīng)錯誤信息；否則將順序表原來第i個元素及以后元素均后移一個位置,騰出一個空位置插入新元素,順序表長度增1。第三十頁，共一百零六頁。intListInsert(SqList*&L,inti,ElemTypee){intj;if(i<1||i>L->length+1) return0;i--;/*將順序表邏輯位序轉(zhuǎn)化為elem下標即物理位序*/for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];/*將data[i]及后面元素后移一個位置*/L->data[i]=e;L->length++;/*順序表長度增1*/return1;}a0…ai-1ai…an-1……邏輯位序1

ii+1nMaxSize第三十一頁，共一百零六頁。

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

因此插入算法的平均時間復(fù)雜度為O(n)。第三十二頁，共一百零六頁。(9)刪除數(shù)據(jù)元素ListDelete(L,i,e)

刪除順序表L中的第i(1≤i≤ListLength(L))個元素。思路：如果i值不正確,則顯示相應(yīng)錯誤信息；否則將線性表第i個元素以后元素均向前移動一個位置,這樣覆蓋了原來的第i個元素,達到刪除該元素的目的,最后順序表長度減1。第三十三頁，共一百零六頁。intListDelete(SqList*&L,inti,ElemType&e){intj;if(i<1||i>L->length) return0;i--; /*將順序表邏輯位序轉(zhuǎn)化為elem下標即物理位序*/e=L->data[i];for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];/*將data[i]之后的元素后前移一個位置*/L->length--; /*順序表長度減1*/return1;}a0…ai-1ai…an-1……邏輯位序1

ii+1nMaxSize第三十四頁，共一百零六頁。

對于本算法來說,元素移動的次數(shù)也與表長n和刪除元素的位置i有關(guān):當i=n時,移動次數(shù)為0；當i=1時,移動次數(shù)為n-1。在線性表sq中共有n個元素可以被刪除。假設(shè)pi(pi=)是刪除第i個位置上元素的概率,則在長度為n的線性表中刪除一個元素時所需移動元素的平均次數(shù)為:=因此刪除算法的平均時間復(fù)雜度為O(n)。第三十五頁，共一百零六頁。

例2.2

設(shè)計一個算法,將x插入到一個有序(從小到大排序)的線性表(順序存儲結(jié)構(gòu)即順序表)的適當位置上,并保持線性表的有序性。解:先通過比較在順序表L中找到存放x的位置i,然后將x插入到L.data[i]中,最后將順序表的長度增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++;}查找插入位置元素后移一個位置a0…ai-1ai…an-1……邏輯位序1

ii+1nMaxSize第三十七頁，共一百零六頁。

例2.3

設(shè)計一個算法,將兩個元素有序(從小到大)的順序表合并成一個有序順序表。

求解思路:將兩個順序表進行二路歸并。

第三十八頁，共一百零六頁。歸并到順序表r中←k記錄r中元素個數(shù)

1(i=0)2(j=0)

將1(i=1)插入r(k=1)3(i=1)2(j=0)將2(j=1)插入r(k=2)3(i=1)4(j=1)將3(i=2)插入r(k=3)5(i=2)4(j=1)將4(j=2)插入r(k=4)5(i=2)10(j=2)將5(j=3)插入r(k=5)

將q中余下元素插入r中。

順序表p：1

3

5i順序表q：2

4

10

20j順序表r：1

k第三十九頁，共一百零六頁。SqList*merge(SqList*p,SqList*q){SqList*r;inti=0,j=0,k=0;r=(SqList*)malloc(sizeof(SqList));while(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++; }}第四十頁，共一百零六頁。

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);}第四十一頁，共一百零六頁。

例2.4

已知長度為n的線性表A采用順序存儲結(jié)構(gòu),編寫一個時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法,該算法刪除線性表中所有值為item的數(shù)據(jù)元素。解:用k記錄順序表A中等于item的元素個數(shù),邊掃描A邊統(tǒng)計k,并將不為item的元素前移k個位置,最后修改A的長度。對應(yīng)的算法如下:第四十二頁，共一百零六頁。voiddelnode1(SqList&A,ElemTypeitem){intk=0,i;/*k記錄值不等于item的元素個數(shù)*/for(i=0;i<A.length;i++)if(A.data[i]!=item) {A.data[k]=A.data[i]; k++;/*不等于item的元素增1*/}A.length=k;/*順序表A的長度等于k*/}算法1：類似于建順序表第四十三頁，共一百零六頁。voiddelnode2(SqList&A,ElemTypeitem){intk=0,i=0;/*k記錄值等于item的元素個數(shù)*/while(i<A.length){if(A.data[i]==item)k++; elseA.data[i-k]=A.data[i];/*當前元素前移k個位置*/ i++;}A.length=A.length-k;/*順序表A的長度遞減*/}算法2第四十四頁，共一百零六頁。

上述算法中只有一個while循環(huán),時間復(fù)雜度為O(n)。算法中只用了i,k兩個臨時變量,空間復(fù)雜度為O(1)。第四十五頁，共一百零六頁。2.3線性表的鏈式存儲

2.3.1線性表的鏈式存儲—鏈表2.3.2單鏈表基本運算的實現(xiàn)2.3.3雙鏈表2.3.4循環(huán)鏈表2.3.5靜態(tài)鏈表第四十六頁，共一百零六頁。2.3.1線性表的鏈式存儲—鏈表

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

由于順序表中的每個元素至多只有一個前驅(qū)元素和一個后繼元素,即數(shù)據(jù)元素之間是一對一的邏輯關(guān)系,所以當進行鏈式存儲時,一種最簡單也最常用的方法是:

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

第四十八頁，共一百零六頁。帶頭結(jié)點單鏈表示意圖

在線性表的鏈式存儲中,為了便于插入和刪除算法的實現(xiàn),每個鏈表帶有一個頭結(jié)點,并通過頭結(jié)點的指針惟一標識該鏈表。

第四十九頁，共一百零六頁。

在單鏈表中,由于每個結(jié)點只包含有一個指向后繼結(jié)點的指針,所以當訪問過一個結(jié)點后,只能接著訪問它的后繼結(jié)點,而無法訪問它的前驅(qū)結(jié)點。

第五十頁，共一百零六頁。

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

在雙鏈表中,由于每個結(jié)點既包含有一個指向后繼結(jié)點的指針,又包含有一個指向前驅(qū)結(jié)點的指針,所以當訪問過一個結(jié)點后,既可以依次向后訪問每一個結(jié)點,也可以依次向前訪問每一個結(jié)點。雙鏈表的特點第五十三頁，共一百零六頁。

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

LinkList類型的定義如下:

typedefstructLNode/*定義單鏈表結(jié)點類型*/{ElemTypedata;structLNode*next;/*指向后繼結(jié)點*/}LinkList;第五十四頁，共一百零六頁。2.3.2單鏈表基本運算的實現(xiàn)

1.建立單鏈表

先考慮如何建立單鏈表。假設(shè)我們通過一個含有n個數(shù)據(jù)的數(shù)組來建立單鏈表。建立單鏈表的常用方法有如下兩種:(1)頭插法建表該方法從一個空表開始,讀取字符數(shù)組a中的字符,生成新結(jié)點,將讀取的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下:第五十五頁，共一百零六頁。voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結(jié)點*/L->next=NULL;for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點*/s->data=a[i];s->next=L->next; /*將*s插在原開始結(jié)點之前,頭結(jié)點之后*/L->next=s;}}第五十六頁，共一百零六頁。adcbi=0i=1i=2i=3∧head采用頭插法建立單鏈表的過程heada∧headda∧headcda∧headbcda∧第1步:建頭結(jié)點第2步:i＝0,新建a結(jié)點,插入到頭結(jié)點之后第3步:i＝1,新建d結(jié)點,插入到頭結(jié)點之后第4步:i＝2,新建c結(jié)點,插入到頭結(jié)點之后第5步:i＝3,新建b結(jié)點,插入到頭結(jié)點之后第五十七頁，共一百零六頁。(2)尾插法建表

頭插法建立鏈表雖然算法簡單,但生成的鏈表中結(jié)點的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點插到當前鏈表的表尾上,為此必須增加一個尾指針r,使其始終指向當前鏈表的尾結(jié)點。采用尾插法建表的算法如下:第五十八頁，共一百零六頁。voidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點*/r=L;/*r始終指向終端結(jié)點,開始時指向頭結(jié)點*/for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點*/s->data=a[i];r->next=s;/*將*s插入*r之后*/r=s;}r->next=NULL; /*終端結(jié)點next域置為NULL*/}第五十九頁，共一百零六頁。bcdai=0i=1i=2i=3head頭結(jié)點adcb∧b采用尾插法建立單鏈表的過程第六十頁，共一百零六頁。2.插入結(jié)點運算插入運算是將值為x的新結(jié)點插入到單鏈表的第i個結(jié)點的位置上。先在單鏈表中找到第i-1個結(jié)點,再在其后插入新結(jié)點。單鏈表插入結(jié)點的過程如下圖所示。第六十一頁，共一百零六頁。插入結(jié)點示意圖第六十二頁，共一百零六頁。3.刪除結(jié)點運算刪除運算是將單鏈表的第i個結(jié)點刪去。先在單鏈表中找到第i-1個結(jié)點,再刪除其后的結(jié)點。刪除單鏈表結(jié)點的過程如下圖所示。第六十三頁，共一百零六頁。刪除結(jié)點示意圖第六十四頁，共一百零六頁。4.線性表基本運算實現(xiàn)

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

該運算建立一個空的單鏈表,即創(chuàng)建一個頭結(jié)點。

voidInitList(LinkList*&L){ L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點*/ L->next=NULL;}第六十五頁，共一百零六頁。(2)銷毀線性表DestroyList(L)

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

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沒有數(shù)據(jù)結(jié)點,則返回真,否則返回假。

intListEmpty(LinkList*L){ return(L->next==NULL);}第六十七頁，共一百零六頁。

(4)求線性表的長度ListLength(L)

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

intListLength(LinkList*L){ LinkList*p=L;inti=0; while(p->next!=NULL) {i++; p=p->next; } return(i);}第六十八頁，共一百零六頁。(5)輸出線性表DispList(L)

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

voidDispList(LinkList*L){ LinkList*p=L->next; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");}第六十九頁，共一百零六頁。(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e)

思路：在單鏈表L中從頭開始找到第i個結(jié)點,若存在第i個數(shù)據(jù)結(jié)點,則將其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個數(shù)據(jù)結(jié)點*/ else /*存在第i個數(shù)據(jù)結(jié)點*/ {e=p->data; return1; }}第七十一頁，共一百零六頁。(7)按元素值查找LocateElem(L,e)

思路：在單鏈表L中從頭開始找第1個值域與e相等的結(jié)點,若存在這樣的結(jié)點,則返回位置,否則返回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個結(jié)點*p,若存在這樣的結(jié)點,將值為e的結(jié)點*s插入到其后。

intListInsert(LinkList*&L,inti,ElemTypee){intj=0;LinkList*p=L,*s;while(j<i-1&&p!=NULL)/*查找第i-1個結(jié)點*/{j++; p=p->next;}第七十三頁，共一百零六頁。

if(p==NULL)return0;/*未找到位序為i-1的結(jié)點*/ else /*找到位序為i-1的結(jié)點*p*/ {s=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建新結(jié)點*s*/ s->data=e; s->next=p->next;/*將*s插入到*p之后*/ p->next=s; return1; }}第七十四頁，共一百零六頁。(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e)

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

intListDelete(LinkList*&L,inti,ElemType&e){ intj=0; LinkList*p=L,*q; while(j<i-1&&p!=NULL)/*查找第i-1個結(jié)點*/ {j++; p=p->next; }第七十五頁，共一百零六頁。 if(p==NULL)return0;/*未找到位序為i-1的結(jié)點*/ else /*找到位序為i-1的結(jié)點*p*/ {q=p->next; /*q指向要刪除的結(jié)點*/ if(q==NULL)return0; /*若不存在第i個結(jié)點,返回0*/ p->next=q->next; /*從單鏈表中刪除*q結(jié)點*/ free(q); /*釋放*q結(jié)點*/ return1; }}第七十六頁，共一百零六頁。

例2.5

設(shè)C={a1,b1,a2,b2,…,an,bn}為一線性表,采用帶頭結(jié)點的hc單鏈表存放,編寫一個算法,將其拆分為兩個線性表,使得:A={a1,a2,…,an},B={b1,b2,…,bn}第七十七頁，共一百零六頁。

解:設(shè)拆分后的兩個線性表都用帶頭結(jié)點的單鏈表存放。先建立兩個頭結(jié)點*ha和*hb,它們用于存放拆分后的線性表A和B,ra和rb分別指向這兩個單鏈表的表尾,用p指針掃描單鏈表hc,將當前結(jié)點*p鏈到ha未尾,p沿next域下移一個結(jié)點,若不為空,則當前結(jié)點*p鏈到hb未尾,p沿next域下移一個結(jié)點,如此這樣,直到p為空。最后將兩個尾結(jié)點的next域置空。對應(yīng)算法如下:第七十八頁，共一百零六頁。voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb;ha=hc; /*ha的頭結(jié)點利用hc的頭結(jié)點*/ra=ha;/*ra始終指向ha的末尾結(jié)點*/hb=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建hb頭結(jié)點*/rb=hb;/*rb始終指向hb的末尾結(jié)點*/第七十九頁，共一百零六頁。while(p!=NULL){ra->next=p;ra=p;/*將*p鏈到ha單鏈表未尾*/p=p->next;if(p!=NULL){rb->next=p;rb=p; /*將*p鏈到hb單鏈表未尾*/p=p->next;}}ra->next=rb->next=NULL;/*兩個尾結(jié)點的next域置空*/}第八十頁，共一百零六頁。

本算法實際上是采用尾插法建立兩個新表。所以,尾插法建表算法是很多類似習(xí)題的基礎(chǔ)！第八十一頁，共一百零六頁。

例2.6

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

第八十二頁，共一百零六頁。voidSort(LinkList*&head){ LinkList*p=head->next,*q,*r; if(p!=NULL)/*head有一個或以上的數(shù)據(jù)結(jié)點*/ {r=p->next;/*r保存*p結(jié)點后繼結(jié)點的指針*/ p->next=NULL;/*構(gòu)造只含一個數(shù)據(jù)結(jié)點的有序表*/ p=r; while(p!=NULL) { r=p->next; /*r保存*p結(jié)點后繼結(jié)點的指針*/第八十三頁，共一百零六頁。

q=head; while(q->next!=NULL&&q->next->data<p->data) q=q->next;/*在有序表中找插入*p的前驅(qū)結(jié)點*q*/p->next=q->next; /*將*p插入到*q之后*/ q->next=p; p=r; /*掃描原單鏈表余下的結(jié)點*/}}}第八十四頁，共一百零六頁。2.3.3雙鏈表

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

typedefstructDNode/*定義雙鏈表結(jié)點類型*/{ ElemTypedata;structDNode*prior;/*指向前驅(qū)結(jié)點*/ structDNode*next;/*指向后繼結(jié)點*/}DLinkList;第八十五頁，共一百零六頁。

在雙鏈表中,有些操作如求長度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的,這里不多討論。但在單鏈表中,進行結(jié)點插入和刪除時涉及到前后結(jié)點的一個指針域的變化。而在雙鏈表中,結(jié)點的插入和刪除操作涉及到前后結(jié)點的兩個指針域的變化。第八十六頁，共一百零六頁。雙鏈表中插入結(jié)點示意圖第八十七頁，共一百零六頁。

歸納起來,在雙鏈表中p所指的結(jié)點之后插入一個*s結(jié)點。其操作語句描述為:s->next=p->next;/*將*s插入到*p之后*/p->next->prior=s;s->prior=p;p->next=s;第八十八頁，共一百零六頁。刪除結(jié)點示意圖

在雙鏈表中刪除一個結(jié)點的過程如右圖所示:第八十九頁，共一百零六頁。

歸納起來,刪除雙鏈表L中*p結(jié)點的后續(xù)結(jié)點。其操作語句描述為:p->next=q->next;q->next->prior=p;第九十頁，共一百零六頁。2.3.4循環(huán)鏈表

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

第九十一頁，共一百零六頁。

帶頭結(jié)點的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖第九十二頁，共一百零六頁。

例2.7

編寫出判斷帶頭結(jié)點的雙向循環(huán)鏈表L是否對稱相等的算法。解:p從左向右掃描L,q從右向左掃描L,若對應(yīng)數(shù)據(jù)結(jié)點的data域不相等,則退出循環(huán),否則繼續(xù)比較,直到p與q相等或p的下一個結(jié)點為*q為止。對應(yīng)算法如下:第九十三頁，共一百零六頁。intEqueal(DLinkList*L){intsame=1;DLinkList*p=L->next; /*p指向第一個數(shù)據(jù)結(jié)點*/DLinkList*q=L->prior;/*q指向最后數(shù)據(jù)結(jié)點*/while(same==1)if(p->data!=q->data)same=0; else{ if(p==q)break; /*數(shù)據(jù)結(jié)點為奇數(shù)的情況*/ q=q->prior; if(p==q)break; /*數(shù)據(jù)結(jié)點為偶數(shù)的情況*/p=p->next; }returnsame;}第九十四頁，共一百零六頁。2.3.5靜態(tài)鏈表

靜態(tài)鏈表借用一維數(shù)組來描述線性鏈表。數(shù)組中的一個分量表示一個結(jié)點,同時使用游標(指示器cur即為偽指針)代替指針以指示結(jié)點在數(shù)組中的相對位置。數(shù)組中的第0個分量可以看成頭結(jié)點,其指針域指示靜態(tài)鏈表的第一個結(jié)點。這種存儲結(jié)構(gòu)仍然需要預(yù)先分配一個較大空間,但是在進行線性表的插入和刪除操作時不需要移動元素,僅需要修改“指針”,因此仍然具有鏈式存儲結(jié)構(gòu)的主要優(yōu)點。第九十五頁，共一百零六頁。

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

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

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

3=1第九十八頁，共一百零六頁。

由于每個表的行數(shù)不確定,為此,用單鏈表作為表的存儲結(jié)構(gòu),每行作為一個數(shù)據(jù)結(jié)點。另外,每行中的數(shù)據(jù)個數(shù)也是不確定的,但由于提供隨機查找行中的數(shù)據(jù),所以每行的數(shù)據(jù)采用順序存儲結(jié)構(gòu),這里用長度為MaxCol的數(shù)組存儲每行的數(shù)據(jù)。因此,該單鏈表中數(shù)據(jù)結(jié)點類型定義如下:#defineMaxCol10 /*最大列數(shù)*/typedefstructNode1 /*定義數(shù)據(jù)結(jié)點類型*/{ElemTypedata[MaxCol];structNode1*next; /*指向后繼數(shù)據(jù)結(jié)點*/}DList;第九十九頁，共一百零六頁。

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

typedefstructNode2 /*定義頭結(jié)點類型*/{intRow,Col; /*行數(shù)和列數(shù)*/DList*next; /*指向第一個數(shù)據(jù)結(jié)點*/}HList;

采用尾插法建表方法創(chuàng)建單鏈表,用戶先輸入表的行數(shù)和列數(shù),然后輸入各行的數(shù)據(jù),為了簡便,假設(shè)表中數(shù)據(jù)為int型,因此定義:

typedefintElemType;

對應(yīng)的建表算法