數(shù)據(jù)結構線性表

第2章線性表

2.1線性表的基本概念

2.2線性表的順序存儲2.3線性表的鏈式存儲2.4線性表的應用

本章小結

2.5有序表

1精選ppt2.1線性表的基本概念

2.1.1線性表的定義2.1.2線性表的運算2精選ppt2.1.1線性表的定義

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

其中a1為第一個元素,又稱做表頭元素,a2為第二個元素,an為最后一個元素,又稱做表尾元素。例如,在線性表(1,4,3,2,8,10)中,1為表頭元素,10為表尾元素。4精選ppt2.1.2線性表的運算線性表的基本運算如下:(1)初始化線性表InitList(&L):構造一個空的線性表L。(2)銷毀線性表DestroyList(&L):釋放線性表L占用的內(nèi)存空間。5精選ppt

(3)判線性表是否為空表ListEmpty(L):若L為空表,則返回真,否則返回假。(4)求線性表的長度ListLength(L):返回L中元素個數(shù)。(5)輸出線性表DispList(L):當線性表L不為空時,順序顯示L中各結點的值域。(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))個元素的值。6精選ppt

(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。7精選ppt

例2.1假設有兩個集合A和B分別用兩個線性表LA和LB表示,即線性表中的數(shù)據(jù)元素即為集合中的成員。編寫一個算法求一個新的集合C=A∪B,即將兩個集合的并集放在線性表LC中。解:本算法思想是:先初始化線性表LC,將LA的所有元素復制到LC中,然后掃描線性表LB,若LB的當前元素不在線性表LA中,則將其插入到LC中。算法如下:8精選pptvoidunionList(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);9精選ppt

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中*/ }}10精選ppt

由于LocateElem(LA,e)運算的時間復雜度為O(ListLength(LA)),所以本算法的時間復雜度為:O(ListLength(LA)*ListLength(LB))。11精選ppt2.2線性表的順序存儲2.2.1線性表的順序存儲—順序表2.2.2順序表基本運算的實現(xiàn)12精選ppt2.2.1線性表的順序存儲—順序表

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

線性表邏輯結構順序表存儲結構13精選ppt

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

在定義一個線性表的順序存儲類型時,需要定義一個數(shù)組來存儲線線表中的所有元素和定義一個整型變量來存儲線性表的長度。假定數(shù)組用data[MaxSize]表示,長度整型變量用length表示,并采用結構體類型表示,則元素類型為通用類型標識符ElemType的線性表的順序存儲類型可描述如下:16精選ppt

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

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

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

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

typedefcharElemType;18精選ppt1.建立順序表其方法是將給定的含有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;}19精選ppt2.順序表基本運算算法(1)初始化線性表InitList(L)該運算的結果是構造一個空的線性表L。實際上只需將length成員設置為0即可。

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

voidDestroyList(SqList*&L){free(L);}本算法的時間復雜度為O(1)。21精選ppt(3)判定是否為空表ListEmpty(L)該運算返回一個值表示L是否為空表。若L為空表,則返回1,否則返回0。

intListEmpty(SqList*L){ return(L->length==0);}本算法的時間復雜度為O(1)。22精選ppt(4)求線性表的長度ListLength(L)該運算返回順序表L的長度。實際上只需返回length成員的值即可。

intListLength(SqList*L){ return(L->length);}本算法的時間復雜度為O(1)。23精選ppt(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");}24精選ppt

本算法中基本運算為for循環(huán)中的printf語句,故時間復雜度為:O(L->length)或O(n)25精選ppt(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;}本算法的時間復雜度為O(1)。26精選ppt(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;}27精選ppt

本算法中基本運算為while循環(huán)中的i++語句,故時間復雜度為:O(L->length)或O(n)28精選ppt(8)插入數(shù)據(jù)元素ListInsert(L,i,e)該運算在順序表L的第i個位置(1≤i≤ListLength(L)+1)上插入新的元素e。思路：如果i值不正確,則顯示相應錯誤信息；否則將順序表原來第i個元素及以后元素均后移一個位置,騰出一個空位置插入新元素,順序表長度增1。29精選pptintListInsert(SqList*&L,inti,ElemTypee){intj;if(i<1||i>L->length+1) return0;i--;/*將順序表邏輯位序轉化為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……邏輯位序1ii+1nMaxSize30精選ppt

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

因此插入算法的平均時間復雜度為O(n)。31精選ppt(9)刪除數(shù)據(jù)元素ListDelete(L,i,e)刪除順序表L中的第i(1≤i≤ListLength(L))個元素。思路：如果i值不正確,則顯示相應錯誤信息；否則將線性表第i個元素以后元素均向前移動一個位置,這樣覆蓋了原來的第i個元素,達到刪除該元素的目的,最后順序表長度減1。32精選pptintListDelete(SqList*&L,inti,ElemType&e){intj;if(i<1||i>L->length) return0;i--; /*將順序表邏輯位序轉化為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……邏輯位序1ii+1nMaxSize33精選ppt

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

例2.2設計一個算法,將x插入到一個有序(從小到大排序)的線性表(順序存儲結構即順序表)的適當位置上,并保持線性表的有序性。解:先通過比較在順序表L中找到存放x的位置i,然后將x插入到L.data[i]中,最后將順序表的長度增1。35精選pptvoidInsert(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……邏輯位序1ii+1nMaxSize36精選ppt

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

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

37精選ppt歸并到順序表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：135i順序表q：241020j順序表r：1k38精選pptSqList*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++; }}39精選ppt

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);}40精選ppt

例2.4已知長度為n的線性表A采用順序存儲結構,編寫一個時間復雜度為O(n)、空間復雜度為O(1)的算法,該算法刪除線性表中所有值為item的數(shù)據(jù)元素。解:用k記錄順序表A中等于item的元素個數(shù),邊掃描A邊統(tǒng)計k,并將不為item的元素前移k個位置,最后修改A的長度。對應的算法如下:41精選pptvoiddelnode1(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：類似于建順序表42精選pptvoiddelnode2(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的長度遞減*/}算法243精選ppt

上述算法中只有一個while循環(huán),時間復雜度為O(n)。算法中只用了i,k兩個臨時變量,空間復雜度為O(1)。44精選ppt2.3線性表的鏈式存儲

2.3.1線性表的鏈式存儲—鏈表2.3.2單鏈表基本運算的實現(xiàn)2.3.3雙鏈表2.3.4循環(huán)鏈表2.3.5靜態(tài)鏈表45精選ppt2.3.1線性表的鏈式存儲—鏈表

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

由于順序表中的每個元素至多只有一個前驅(qū)元素和一個后繼元素,即數(shù)據(jù)元素之間是一對一的邏輯關系,所以當進行鏈式存儲時,一種最簡單也最常用的方法是:在每個結點中除包含有數(shù)據(jù)域外,只設置一個指針域,用以指向其后繼結點,這樣構成的鏈接表稱為線性單向鏈接表,簡稱單鏈表；

47精選ppt帶頭結點單鏈表示意圖

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

48精選ppt

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

49精選ppt

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

在雙鏈表中,由于每個結點既包含有一個指向后繼結點的指針,又包含有一個指向前驅(qū)結點的指針,所以當訪問過一個結點后,既可以依次向后訪問每一個結點,也可以依次向前訪問每一個結點。雙鏈表的特點52精選ppt

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

LinkList類型的定義如下:

typedefstructLNode/*定義單鏈表結點類型*/{ElemTypedata;structLNode*next;/*指向后繼結點*/}LinkList;53精選ppt2.3.2單鏈表基本運算的實現(xiàn)

1.建立單鏈表

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

頭插法建立鏈表雖然算法簡單,但生成的鏈表中結點的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結點插到當前鏈表的表尾上,為此必須增加一個尾指針r,使其始終指向當前鏈表的尾結點。采用尾插法建表的算法如下:57精選pptvoidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結點*/r=L;/*r始終指向終端結點,開始時指向頭結點*/for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結點*/s->data=a[i];r->next=s;/*將*s插入*r之后*/r=s;}r->next=NULL; /*終端結點next域置為NULL*/}58精選pptbcdai=0i=1i=2i=3head頭結點adcb∧b采用尾插法建立單鏈表的過程59精選ppt2.插入結點運算插入運算是將值為x的新結點插入到單鏈表的第i個結點的位置上。先在單鏈表中找到第i-1個結點,再在其后插入新結點。單鏈表插入結點的過程如下圖所示。60精選ppt插入結點示意圖61精選ppt3.刪除結點運算刪除運算是將單鏈表的第i個結點刪去。先在單鏈表中找到第i-1個結點,再刪除其后的結點。刪除單鏈表結點的過程如下圖所示。62精選ppt刪除結點示意圖63精選ppt4.線性表基本運算實現(xiàn)(1)初始化線性表InitList(L)該運算建立一個空的單鏈表,即創(chuàng)建一個頭結點。

voidInitList(LinkList*&L){ L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結點*/ L->next=NULL;}64精選ppt(2)銷毀線性表DestroyList(L)釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結點的空間。voidDestroyList(LinkList*&L){ LinkList*p=L,*q=p->next; while(q!=NULL) {free(p); p=q;q=p->next; } free(p);}65精選ppt(3)判線性表是否為空表ListEmpty(L)若單鏈表L沒有數(shù)據(jù)結點,則返回真,否則返回假。

intListEmpty(LinkList*L){ return(L->next==NULL);}66精選ppt

(4)求線性表的長度ListLength(L)返回單鏈表L中數(shù)據(jù)結點的個數(shù)。intListLength(LinkList*L){ LinkList*p=L;inti=0; while(p->next!=NULL) {i++; p=p->next; } return(i);}67精選ppt(5)輸出線性表DispList(L)逐一掃描單鏈表L的每個數(shù)據(jù)結點,并顯示各結點的data域值。

voidDispList(LinkList*L){ LinkList*p=L->next; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");}68精選ppt(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e)思路：在單鏈表L中從頭開始找到第i個結點,若存在第i個數(shù)據(jù)結點,則將其data域值賦給變量e。69精選pptintGetElem(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ù)結點*/ else /*存在第i個數(shù)據(jù)結點*/ {e=p->data; return1; }}70精選ppt(7)按元素值查找LocateElem(L,e)思路：在單鏈表L中從頭開始找第1個值域與e相等的結點,若存在這樣的結點,則返回位置,否則返回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);}71精選ppt(8)插入數(shù)據(jù)元素ListInsert(&L,i,e)思路：先在單鏈表L中找到第i-1個結點*p,若存在這樣的結點,將值為e的結點*s插入到其后。intListInsert(LinkList*&L,inti,ElemTypee){intj=0;LinkList*p=L,*s;while(j<i-1&&p!=NULL)/*查找第i-1個結點*/{j++; p=p->next;}72精選ppt

if(p==NULL)return0;/*未找到位序為i-1的結點*/ else /*找到位序為i-1的結點*p*/ {s=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建新結點*s*/ s->data=e; s->next=p->next;/*將*s插入到*p之后*/ p->next=s; return1; }}73精選ppt(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e)思路：先在單鏈表L中找到第i-1個結點*p,若存在這樣的結點,且也存在后繼結點,則刪除該后繼結點。intListDelete(LinkList*&L,inti,ElemType&e){ intj=0; LinkList*p=L,*q; while(j<i-1&&p!=NULL)/*查找第i-1個結點*/ {j++; p=p->next; }74精選ppt if(p==NULL)return0;/*未找到位序為i-1的結點*/ else /*找到位序為i-1的結點*p*/ {q=p->next; /*q指向要刪除的結點*/ if(q==NULL)return0; /*若不存在第i個結點,返回0*/ p->next=q->next; /*從單鏈表中刪除*q結點*/ free(q); /*釋放*q結點*/ return1; }}75精選ppt

例2.5設C={a1,b1,a2,b2,…,an,bn}為一線性表,采用帶頭結點的hc單鏈表存放,編寫一個算法,將其拆分為兩個線性表,使得:A={a1,a2,…,an},B={b1,b2,…,bn}76精選ppt

解:設拆分后的兩個線性表都用帶頭結點的單鏈表存放。先建立兩個頭結點*ha和*hb,它們用于存放拆分后的線性表A和B,ra和rb分別指向這兩個單鏈表的表尾,用p指針掃描單鏈表hc,將當前結點*p鏈到ha未尾,p沿next域下移一個結點,若不為空,則當前結點*p鏈到hb未尾,p沿next域下移一個結點,如此這樣,直到p為空。最后將兩個尾結點的next域置空。對應算法如下:77精選pptvoidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb;ha=hc; /*ha的頭結點利用hc的頭結點*/ra=ha;/*ra始終指向ha的末尾結點*/hb=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建hb頭結點*/rb=hb;/*rb始終指向hb的末尾結點*/78精選pptwhile(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;/*兩個尾結點的next域置空*/}79精選ppt

本算法實際上是采用尾插法建立兩個新表。所以,尾插法建表算法是很多類似習題的基礎！80精選ppt

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

81精選pptvoidSort(LinkList*&head){ LinkList*p=head->next,*q,*r; if(p!=NULL)/*head有一個或以上的數(shù)據(jù)結點*/ {r=p->next;/*r保存*p結點后繼結點的指針*/ p->next=NULL;/*構造只含一個數(shù)據(jù)結點的有序表*/ p=r; while(p!=NULL) { r=p->next; /*r保存*p結點后繼結點的指針*/82精選ppt

q=head; while(q->next!=NULL&&q->next->data<p->data) q=q->next;/*在有序表中找插入*p的前驅(qū)結點*q*/p->next=q->next; /*將*p插入到*q之后*/ q->next=p; p=r; /*掃描原單鏈表余下的結點*/}}}83精選ppt2.3.3雙鏈表

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

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

歸納起來,在雙鏈表中p所指的結點之后插入一個*s結點。其操作語句描述為:s->next=p->next;/*將*s插入到*p之后*/p->next->prior=s;s->prior=p;p->next=s;87精選ppt刪除結點示意圖在雙鏈表中刪除一個結點的過程如右圖所示:88精選ppt

歸納起來,刪除雙鏈表L中*p結點的后續(xù)結點。其操作語句描述為:p->next=q->next;q->next->prior=p;89精選ppt2.3.4循環(huán)鏈表

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

90精選ppt

帶頭結點的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖91精選ppt

例2.7編寫出判斷帶頭結點的雙向循環(huán)鏈表L是否對稱相等的算法。解:p從左向右掃描L,q從右向左掃描L,若對應數(shù)據(jù)結點的data域不相等,則退出循環(huán),否則繼續(xù)比較,直到p與q相等或p的下一個結點為*q為止。對應算法如下:92精選pptintEqueal(DLinkList*L){intsame=1;DLinkList*p=L->next; /*p指向第一個數(shù)據(jù)結點*/DLinkList*q=L->prior;/*q指向最后數(shù)據(jù)結點*/while(same==1)if(p->data!=q->data)same=0; else{ if(p==q)break; /*數(shù)據(jù)結點為奇數(shù)的情況*/ q=q->prior; if(p==q)break; /*數(shù)據(jù)結點為偶數(shù)的情況*/p=p->next; }returnsame;}93精選ppt2.3.5靜態(tài)鏈表

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

下圖給出了一個靜態(tài)鏈表的示例。圖(a)是一個修改之前的靜態(tài)鏈表,圖(b)是刪除數(shù)據(jù)元素“陳華”之后的靜態(tài)鏈表,圖(c)插入數(shù)據(jù)元素“王華”之后的靜態(tài)鏈表,圖中用陰影表示修改的游標。95精選ppt2.4線性表的應用

計算任意兩個表的簡單自然連接過程討論線性表的應用。假設有兩個表A和B,分別是m1行、n1列和m2行、n2列,它們簡單自然連接結果C=AB,其中i表示表A中列號,j表示表B中的列號,C為A和B的笛卡兒積中滿足指定連接條件的所有記錄組,該連接條件為表A的第i列與表B的第j列相等。例如:i=j96精選ppt

C=AB的計算結果如下:

3=197精選ppt由于每個表的行數(shù)不確定,為此,用單鏈表作為表的存儲結構,每行作為一個數(shù)據(jù)結點。另外,每行中的數(shù)據(jù)個數(shù)也是不確定的,但由于提供隨機查找行中的數(shù)據(jù),所以每行的數(shù)據(jù)采用順序存儲結構,這里用長度為MaxCol的數(shù)組存儲每行的數(shù)據(jù)。因此,該單鏈表中數(shù)據(jù)結點類型定義如下:#defineMaxCol10 /*最大列數(shù)*/typedefstructNode1 /*定義數(shù)據(jù)結點類型*/{ElemTypedata[MaxCol];structNode1*next; /*指向后繼數(shù)據(jù)結點*/}DList;98精選ppt另外,需要指定每個表的行數(shù)和列數(shù),為此將單鏈表的頭結點類型定義如下:

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

typedefintElemType;對應的建表算法如下:99精選pptvoidcreate(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",&s->data[j]); if(h->next==NULL)h->next=s; elser->next=s; r=s;/*r始終指向最后一個數(shù)據(jù)結點*/}r->next=NULL; }采用尾插法建表100精選ppt