第二章線性表A_第1頁(yè)
第二章線性表A_第2頁(yè)
第二章線性表A_第3頁(yè)
第二章線性表A_第4頁(yè)
第二章線性表A_第5頁(yè)
已閱讀5頁(yè),還剩70頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1第2章線性表2.1線性表的基本概念2.2線性表的順序存儲(chǔ)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.4一元多項(xiàng)式的表示及相加2

從本章開(kāi)始到第四章討論的線性表、棧、隊(duì)列和串的邏輯結(jié)構(gòu)都屬于線性結(jié)構(gòu)。在線性結(jié)構(gòu)中,元素之間存在一個(gè)對(duì)一個(gè)的相互關(guān)系,其邏輯特征為:在數(shù)據(jù)元素的非空有限集中:(1)存在唯一的一個(gè)被稱(chēng)為“起始”的數(shù)據(jù)元素。(2)存在唯一的一個(gè)被稱(chēng)為“終端”的元素。

2.1線性表的類(lèi)型定義 3

(3)除起始元素外,其它每個(gè)元素有且僅有一個(gè)直接前趨。(4)除終端元素之外,其它每個(gè)元素有且僅有一個(gè)直接后繼。本章的基本內(nèi)容:線性表的邏輯結(jié)構(gòu)定義和各種存儲(chǔ)結(jié)構(gòu)、描述方法及其建立在這兩種存儲(chǔ)結(jié)構(gòu)上的運(yùn)算實(shí)現(xiàn)。42.1.1線性表的邏輯結(jié)構(gòu)

在實(shí)際應(yīng)用中,線性表是最常用而且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。線性表定義:線性表是由n個(gè)數(shù)據(jù)元素組成的有限序列,其中,n即數(shù)據(jù)元素的個(gè)數(shù),定義為線性表的長(zhǎng)度,當(dāng)n為零時(shí)稱(chēng)為空表,一般將n>0時(shí)的線性表記為:

其中,是第一個(gè)數(shù)據(jù)元素,又稱(chēng)為起始結(jié)點(diǎn),是最后一個(gè)數(shù)據(jù)元素,又稱(chēng)為終端結(jié)點(diǎn)。5

當(dāng)i=1,2,…,n-1時(shí),有且僅有一個(gè)直接后繼;當(dāng)i=2,3,…n時(shí),有且僅有一個(gè)直接前趨。注意這里(1≤i≤n)僅僅是一個(gè)抽象的符號(hào),其具體含義,在不同的情況下各不相同,它可以是一個(gè)數(shù),一條記錄或一個(gè)符號(hào),甚至是更復(fù)雜的信息。例如,英文字母表(A,B,……Z)是一個(gè)線性表,職工工資表等。線性表的結(jié)點(diǎn)之間的邏輯關(guān)系符合線性結(jié)構(gòu)的邏輯特征,是一種線性結(jié)構(gòu)。

6線性表的特點(diǎn):同一線性表中的元素必定具有相同特性;相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系;線性表中元素個(gè)數(shù)n(n>=0)為線性表的長(zhǎng)度,當(dāng)n=0時(shí)稱(chēng)為空表;在非空線性表中,每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置;線性表的長(zhǎng)度可以根據(jù)需要增長(zhǎng)或縮短。7抽象數(shù)據(jù)類(lèi)型線性表的定義格式ADTlist{

數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:基本操作:以下是一些常用操作,以函數(shù)方式出現(xiàn)

……}ADTlistElemSet是某個(gè)確定的、將由用戶自行定義的、含某個(gè)關(guān)系運(yùn)算的數(shù)據(jù)對(duì)象8

常見(jiàn)的線性表的基本運(yùn)算:(1)置空表ClearList(L):將線性表L置成空表。(2)求長(zhǎng)度ListLenght(L):求給定線性表L中數(shù)據(jù)元素的個(gè)數(shù)。(3)取元素GetElem(L,i,&e):用e返回線性表L中的第i個(gè)數(shù)據(jù)元素。(4)插入ListInsert(&L,i,e):在線性表L中第i個(gè)位置之前插入新的元素e,L的長(zhǎng)度加1。

2.1.2線性表的運(yùn)算9

(5)刪除ListDelete(&L,i,&e):刪除L中第i個(gè)元素,并用e返回其值,L的長(zhǎng)度減1。(6)判定ListEmpty(L):若L為空表,則返回true,否則返回false。利用基本運(yùn)算可以實(shí)現(xiàn)線性表的其它復(fù)雜運(yùn)算。需要指出的是,這里給出的只是定義在邏輯結(jié)構(gòu)上的抽象運(yùn)算,即只關(guān)心這些運(yùn)算是“做什么”的,至于“怎樣實(shí)現(xiàn)”則依賴(lài)于所選定的存儲(chǔ)結(jié)構(gòu)。102.2線性表的順序表示和實(shí)現(xiàn)

順序表是線性表的順序存儲(chǔ)結(jié)構(gòu),即按順序存儲(chǔ)方式構(gòu)成的線性表的存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)方式是:線性表的第一個(gè)元素存放在個(gè)一片連續(xù)的存儲(chǔ)空間開(kāi)始位置處,第二個(gè)元素緊跟著存放在第一元素之后…,以此類(lèi)推。利用順序表來(lái)存儲(chǔ)線性表,可借助數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的物理位置相鄰特性來(lái)表示線性表中數(shù)據(jù)元素之間的線性邏輯關(guān)系。線性表中第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置計(jì)算公式為:

L是每個(gè)元素占用的存儲(chǔ)單元

11

這樣,一旦起始地址LOC(a1)(圖2.2中設(shè)為b)和一個(gè)數(shù)據(jù)元素占用的存儲(chǔ)單元的大?。↙值)確定下來(lái),就可求出任一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址,顯然,這種表便于進(jìn)行隨機(jī)訪問(wèn),因此,順序表是一種隨機(jī)存取的結(jié)構(gòu)。1213

在具體實(shí)現(xiàn)時(shí),可利用高級(jí)程序設(shè)計(jì)語(yǔ)言中的一維數(shù)組即向量來(lái)為線性表的順序存儲(chǔ)開(kāi)辟存儲(chǔ)空間,存儲(chǔ)空間大小應(yīng)大于等于線性表長(zhǎng)度,用一個(gè)整型變量來(lái)表示線性表的長(zhǎng)度,從而可將順序表描述為:

#defineList_INIT100typedefintelemtype;/*elemtype表示元素類(lèi)型,此處設(shè)為int*/typedefstruct{elemtypevec[List_INIT];

intlenght;

}sequenlist;

14

在上面描述中,順序表是一個(gè)結(jié)構(gòu)體類(lèi)型。其中,vec成員(又稱(chēng)為數(shù)據(jù)域)指線性表數(shù)據(jù)元素所占用的存儲(chǔ)空間,而lenght成員(又稱(chēng)為長(zhǎng)度域)則用于存儲(chǔ)線性表長(zhǎng)度,它表示線性表最后一個(gè)元素在向量中的位置,elemtype則為線性表中數(shù)據(jù)元素類(lèi)型。15

本節(jié)討論在定義線性表順序存儲(chǔ)結(jié)構(gòu)之后,如何在這種結(jié)構(gòu)上實(shí)現(xiàn)有關(guān)數(shù)據(jù)運(yùn)算。下面重點(diǎn)討論線性表的順序表的建立、數(shù)據(jù)元素的插入和刪除運(yùn)算。

2.2.2順序表上的基本運(yùn)算163.順序表的常用算法算法1順序表的建立(P23算法2.3)輸入n個(gè)整數(shù),產(chǎn)生一個(gè)存儲(chǔ)這些整數(shù)的順序表A的函數(shù)如下:voidcreate(A,n)vectorA;intn;{inti;for(i=1;i<=n;i++)cin>>A[i];/*scanf(“%d”,A[i]);*/}typedefintvector[m]定義了一個(gè)新的類(lèi)型,順序表中n小于或等于mmain(){vectorB;intj,n;cin>>n;create(B,n);for(j=1;j<=n;j++)cout<<B[j];/*Printf(“%d”,B[j]);*/}172.插入運(yùn)算線性表的插入運(yùn)算是指在表的第i個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素,插入的結(jié)果使得線性表的長(zhǎng)度由n變?yōu)閚+1,線性表的數(shù)據(jù)元素間的邏輯關(guān)系發(fā)生了變化,使得物理存儲(chǔ)順序也發(fā)生相應(yīng)的變化。插入過(guò)程如圖2.3所示。18121321242830427712345678插入25121321242528304277123456789插入后(a)(b)19算法2順序表的插入(如圖2.3)121321242830427712345678插入25

在一個(gè)有n個(gè)元素的順序表A中的第i個(gè)元素之前插入一個(gè)元素x的函數(shù)如下:

voidinsert(A,n,x)vectorA;intn,x;{inti,j;scanf(“%d”,&i);/*確定插入位置*/if(i<1||i>n)print(“i值錯(cuò)誤!\n”);else{for(j=n;j>=i;j--)A[j+1]=A[j];A[i]=x;n++;}}20intInsert(ElemtypeList[],int*num,inti,Elemtypex){/*在順序表List[]中,*num為表尾元素下標(biāo)位置,在第i個(gè)元素前插入數(shù)據(jù)元素x,若成功,返回TRUE,否則返回FALSE。*/intj;if(i<0||i>*num+1){printf(“Error!”); /*插入位置出錯(cuò)*/returnFALSE;}if(*num>=MAXNUM-1){printf(“overflow!”);returnFALSE;} /*表已滿*/for(j=*num;j>=i;j--)List[j+1]=List[j]; /*數(shù)據(jù)元素后移*/List[i]=x; /*插入x*/(*num)++; /*長(zhǎng)度加1*/returnTRUE;}

P24【算法2.4順序表的插入】21

在本算法中是從最后一個(gè)元素開(kāi)始后移,直到第i個(gè)元素為止。該算法時(shí)間主要花費(fèi)在for循環(huán)語(yǔ)句上,執(zhí)行的次數(shù)為n-i+1。當(dāng)i=1時(shí),全部元素均參加移動(dòng),共需要移動(dòng)n次;當(dāng)i=n+1時(shí),不需移動(dòng)元素。算法在最壞情況下,時(shí)間復(fù)雜度為O(n),最好情況下時(shí)間復(fù)雜度為O(1)。顯然,元素移動(dòng)的次數(shù)直接影響了算法執(zhí)行時(shí)間,平均移動(dòng)次數(shù)。

假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率,且為等概率,則平均移動(dòng)次數(shù)的期望值為:

其中,當(dāng)1≤i≤n+1時(shí),p1=p2=……=pn+1=

可見(jiàn),在順序存儲(chǔ)的線性表中插入一個(gè)元素,約平均移動(dòng)線性表中一半的元素,顯然,當(dāng)n較大時(shí),算法效率較低,算法的平均時(shí)間復(fù)雜度為O(n)。

22

在本算法中是從最后一個(gè)元素開(kāi)始后移,直到第i個(gè)元素為止。該算法時(shí)間主要花費(fèi)在for循環(huán)語(yǔ)句上,執(zhí)行的次數(shù)為n-i+1。當(dāng)i=1時(shí),全部元素均參加移動(dòng),共需要移動(dòng)n次;當(dāng)i=n+1時(shí),不需移動(dòng)元素。算法在最壞情況下,時(shí)間復(fù)雜度為O(n),最好情況下時(shí)間復(fù)雜度為O(1)。顯然,元素移動(dòng)的次數(shù)直接影響了算法執(zhí)行時(shí)間,平均移動(dòng)次數(shù)。

假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率,且為等概率,則平均移動(dòng)次數(shù)的期望值為:

其中,當(dāng)1≤i≤n+1時(shí),p1=p2=……=pn+1=

23

可見(jiàn),在順序存儲(chǔ)的線性表中插入一個(gè)元素,約平均移動(dòng)線性表中一半的元素,顯然,當(dāng)n較大時(shí),算法效率較低,算法的平均時(shí)間復(fù)雜度為O(n)。

243.刪除運(yùn)算

刪除運(yùn)算是指將線性表中的第i個(gè)元素刪除,使線性表的長(zhǎng)度由n變成n-1,由:

(a1,a2,…,ai-1,ai,ai+1,…,an)

變成為:(a1,a2,…,ai-1,ai+1,…,an)

其中,1≤i≤n。線性表進(jìn)行刪除元素后,仍是一個(gè)線性表。刪除過(guò)程如圖2.4所示。25算法3順序表的刪除(如圖2.4)具體算法如下:

voiddelete(L,i)sequenlist*L;

inti;

{intj;

if((i<1)||(i>(*L).len+1))printf(“deletefail!\n”);/*刪除位置不正確*/else{*y=(*L).vec[i-1];/*y為一外部變量,用于接收被刪除的元素*/for(j=i;j<=(*L).len;j++)(*L).vec[j-1]=(*L).vec[j];/*元素前移*/(*L).Len--;/*修改表長(zhǎng)*/}}/*delete*/26

與插入算法相似,要?jiǎng)h除一個(gè)元素需向前移動(dòng)元素,刪除第i個(gè)元素時(shí),將第i+1,i+2,…,n個(gè)元素依次前移,其移動(dòng)次數(shù)為n-i,假設(shè)刪除線性表中的任一位置上元素的概率相等(等于1/n),則刪除運(yùn)算所需的移動(dòng)元素的平均移動(dòng)次數(shù)如下所示。

由此可見(jiàn),對(duì)線性表刪除一個(gè)元素時(shí),約需有一半的元素參加移動(dòng)。

27

顯然,該算法的時(shí)間復(fù)雜度為O(n)。通過(guò)以上討論可以發(fā)現(xiàn),當(dāng)表長(zhǎng)較大時(shí),對(duì)順序存儲(chǔ)結(jié)構(gòu)進(jìn)行插入和刪除運(yùn)算,由于要移動(dòng)元素,運(yùn)算效率低,但這種存儲(chǔ)結(jié)構(gòu)對(duì)于隨機(jī)存取元素卻十分方便。28

例如,一個(gè)線性表中可能含有重復(fù)的元素(值相同),現(xiàn)要求刪除重復(fù)元素中的多余元素,只保留其中位序最小的一個(gè)。如線性表(5,2,2,3,5,2),經(jīng)過(guò)清除重復(fù)元素后變?yōu)?5,2,3)。

假定線性表以順序存儲(chǔ)方式存儲(chǔ),則其算法可描述如下:

voidpurge(sequenlist*L)

{inti=0,j,k;

while(i<=(*L).Len-1){j=i+1;

while(j<=(*L).Len-1)

if((*L).vec[i]==(*L).vec[j])

{for(k=j;k<=(*L).Len-1;k++)(*L).vec[k–1]=(*L).vec[k];/*元素前移*/

(*L).Len--;/*修改表長(zhǎng)度*/}else

j++;i++;}}/*purge*/29算法4順序表的查找(P26算法2.6)在一個(gè)有n個(gè)元素線性表A中查找值為x的元素的函數(shù)如下:

voidfind(A[],n,x)intn.x;{intj;i=1;while(i<=n&&A[i]!=x)i++;if(i<=n)printf(“找到了!\n”);elseprintf(“沒(méi)找到\n”);}30算法5:順序表的合并(P26算法2.7)

有兩個(gè)順序表A(有m個(gè)元素)和B(有n個(gè)元素),其元素均以從小到大的升序排列,編寫(xiě)一個(gè)函數(shù)將它們合并成一個(gè)順序表C,要求C的元素也是從小到大的升序排列.

解:本題的解法思想是:依次掃描A和B的元素,比較當(dāng)前的元素的值,將較小值的元素賦給C,如此直到一個(gè)表掃描完畢,然后將未完的一個(gè)表余下所有元素賦給C即可.31Voidlink(intA[],intB[];intm,n;intC[]){inti=1,j=1,k=1,s;while(i<=m&&j<=n)/*掃描A和B,將當(dāng)前的較小元素賦給C*/ifA[i]<B[j]){C[k]=A[I];i++;k++;}else{C[k]=B[j];j++;k++;}if(j==n)/*當(dāng)A未完時(shí),將A余下的元素賦給C*/for(s=i+1;s<=m;s++){C[k]=A[s];k++;}if(i==m)/*當(dāng)B未完時(shí),將B余下元素賦給C*/for(s=j+1;s<=n;s++){C[k]=B[s];k++;}}算法2.7C語(yǔ)言代碼為:321.基礎(chǔ)知識(shí):題集2.1;

2.算法實(shí)現(xiàn):寫(xiě)出教材算法2.4、2.5(線性表中元素的插入和刪除算法)的C/C++語(yǔ)言程序,并上機(jī)調(diào)試;

3.算法設(shè)計(jì)題:題集2.10、2.11。作業(yè)33

線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn):(1)邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也是相鄰的,因此可以隨機(jī)存取表中任意元素(可用地址公式).

(2)無(wú)需為表示數(shù)據(jù)元素之間的關(guān)系而增加額外存儲(chǔ)空間;(3)可以方便地隨機(jī)存取表中任一元素。(4)必須預(yù)先為線性表分配空間,表容量難以擴(kuò)充,必須按線性表最大可能的長(zhǎng)度分配空間,有可能造成存儲(chǔ)空間浪費(fèi)。2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)34

(5)插入和刪除運(yùn)算時(shí)必須移動(dòng)大量元素,效率較低;為避免大量元素的移動(dòng),本節(jié)討論線性表的另一種存儲(chǔ)結(jié)構(gòu),即鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),是最常用的存儲(chǔ)方法之一,它不僅可以表示線性表,而且可以表示各種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。這種結(jié)構(gòu)按不同的分類(lèi)方法可分為單鏈表、循環(huán)鏈表和雙向鏈表等。35

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)是:邏輯關(guān)系上相鄰的兩個(gè)元素,在物理位置上不一定相鄰,不能隨機(jī)存取鏈中數(shù)據(jù).2.3.1線性鏈表a.一個(gè)結(jié)點(diǎn)——數(shù)據(jù)元素ai的存儲(chǔ)映象。ai存入的數(shù)據(jù)指向其后繼如:鏈表中存入數(shù)據(jù)6,9,3,76937^Head(頭指針)3637

這樣,利用每個(gè)結(jié)點(diǎn)的指針域就可以將n個(gè)結(jié)點(diǎn)按其邏輯次序連成一個(gè)鏈表,這種鏈表中每個(gè)結(jié)點(diǎn)只含一個(gè)指針域,故稱(chēng)為線性鏈表或單鏈表。例如,線性表(red,orange,white,yellow,green,blue),其單鏈表的存儲(chǔ)方式如圖2.5所示。由于單鏈表中第一個(gè)結(jié)點(diǎn)無(wú)直接前趨,可另設(shè)一個(gè)頭指針head存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址。同樣,最后一個(gè)結(jié)點(diǎn)無(wú)直接后繼,其指針域?yàn)榭罩导礊镹ULL,有時(shí)用^表示。整個(gè)單鏈表可由頭指針唯一地確定。單鏈表是一種非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

38

也可以將圖2.5中的單鏈表直觀地畫(huà)成如圖2.6所示,其中箭頭用來(lái)表示鏈域中的指針。39b.結(jié)構(gòu)指針定義

單鏈表可以用C語(yǔ)言中的指針數(shù)據(jù)類(lèi)型實(shí)現(xiàn),描述如下:

typedefintelemtype;

typedefstructnode/*結(jié)點(diǎn)類(lèi)型定義*/

{elemtypedata;/*數(shù)據(jù)域*/

structnode*next;/*定義指針域*/

}linklist;

linklist*head,*p;/*head,p為單鏈表指針類(lèi)型*/

另外,利用C語(yǔ)言中的指針數(shù)據(jù)類(lèi)型要注意指針變量和結(jié)點(diǎn)變量,其關(guān)系如圖2.7所示。40單鏈表上的基本運(yùn)算

為了便于實(shí)現(xiàn)各種運(yùn)算,常在單鏈表的第一個(gè)結(jié)點(diǎn)之前增設(shè)一個(gè)附加的結(jié)點(diǎn),稱(chēng)為頭結(jié)點(diǎn),其它的結(jié)點(diǎn)稱(chēng)為表結(jié)點(diǎn)。本章若無(wú)特殊說(shuō)明,均采用帶頭結(jié)點(diǎn)的單鏈表,如圖2.8的(a),(b)所示。411.

建立一個(gè)單鏈表

(1)算法2.8C語(yǔ)言程序輸入一系列整數(shù),以0標(biāo)志結(jié)束,將這些整數(shù)作為data域建立一個(gè)單鏈表的函數(shù):

voidcrea(){node*head,*p,*s;intx,cycle=1;/*cycle是循環(huán)變量*/head=(node*)malloc(sizeof(node));/*建立頭結(jié)點(diǎn),由dead所指向*/p=head;while(cycle){scanf(“%d”,&x);if(x!=0){s=(node*)malloc(sizef(node));/*建立下一個(gè)結(jié)點(diǎn),由s所指向*/42s->data=x;p->next=s;p=s;}/*把s結(jié)點(diǎn)鏈接到前面建立的單鏈表中*/elsecycle=0;}head=head->next;/*刪除頭結(jié)點(diǎn)*/p->next=NULL;}如果輸入的整數(shù)序列是:

6103675043

linklist*creatlist()/*函數(shù)返回一個(gè)指向單鏈表表頭的指針*/

{charch;intx;

linklist*head,*r,*p;

p=(linklist*)malloc(sizeof(linklist));

head=p;

p->next=NULL;/*生成頭結(jié)點(diǎn)*/

r=p;/*建立單鏈表表尾指針*/

ch=getchar();/*ch為建立與否標(biāo)志*/

while(ch!=‘?’)/*‘?’為輸入結(jié)束標(biāo)志符*/

{scanf(“%d”,&x);/*讀入新數(shù)據(jù)元素*/

p=(linklist*)malloc(sizeof(linklist));

p->data=x;

p->next=NULL;/*生成新結(jié)點(diǎn)*/

r->next=p;/*連接新結(jié)點(diǎn)*/

r=r->next;/*修改尾指針*/

ch=getchar();/*讀入建立與否的標(biāo)志*/

}

return(head);/*返回表頭指針head*/

}/*creatlist*/(2)建立帶頭結(jié)點(diǎn)的單鏈表44(3)建立不帶頭結(jié)點(diǎn)的單鏈表

linklist*creatlist()/*函數(shù)返回一個(gè)指向鏈表表頭的指針*/

{charch;intx;linklist*head,*p,*r

head=NULL;r=NULL;/*設(shè)立尾指針r,其初值為空*/

ch=getchar();/*讀入建立與否標(biāo)志*/

while(ch!=‘?’)/*‘?’為輸入結(jié)束標(biāo)志符*/

{p=(linklist*)malloc(sizeof(linklist));/*申請(qǐng)新結(jié)點(diǎn)空間*/

scanf(“%d”,&x);

p->data=x;

if(head==NULL)head=p;

elser->next=p;/*非空表,則新結(jié)點(diǎn)*p插入到*r之后*/

r=p;/*尾指針移動(dòng),指向新的表尾*/

ch=getchar();/*讀入建立與否的標(biāo)志*/

}

if(r!=NULL)r->next=NULL;

returnhead;/*返回表頭指針head*/

}/*creatlist*/

在算法中引入頭結(jié)點(diǎn)可以不必區(qū)分空表與非空表,可以統(tǒng)一空鏈表與非空鏈表的處理。上述兩個(gè)算法的時(shí)間復(fù)雜度都為O(n)。45

插入結(jié)點(diǎn)的指針變化圖2.9所示。指針的修改操作為:①s->next=p->next;②p->next=s;上述指針進(jìn)行相互賦值的語(yǔ)句順序不能顛倒,若次序變化為:①p->next=s;②s->next=p->next;則會(huì)導(dǎo)致錯(cuò)誤。同樣,要?jiǎng)h除單鏈表結(jié)點(diǎn)*p的后繼結(jié)點(diǎn)也很簡(jiǎn)單,只要用一個(gè)指針指向被刪除結(jié)點(diǎn),修改*p的指針域,最后釋放結(jié)點(diǎn)*p即可,如圖2.10所示。刪除一個(gè)結(jié)點(diǎn)*p的后繼結(jié)點(diǎn)的指針操作為:

p->next=p->next->next;

不難發(fā)現(xiàn),在單鏈表存儲(chǔ)結(jié)構(gòu)中進(jìn)行元素的插入和刪除時(shí),只需要修改有關(guān)的指針內(nèi)容,而不需要移動(dòng)元素。

2.單鏈表上元素的插入和刪除運(yùn)算4647

(a)

insert(linklist*p,elemtypex)

/*將值為x的新結(jié)點(diǎn)插入*p之后*/

{linklist*s;

s=(linklist*)malloc(sizeof(linklist));/*生成x的新結(jié)點(diǎn)*s*/

s->data=x;

s->next=p->next;/*新結(jié)點(diǎn)鏈入單鏈表*/

p->next=s;

}/*insert*/

(1)插入算法48

(b)voidinsert(linklist*head,elemtypek,elemtypex)

/*在單鏈表中值為k的結(jié)點(diǎn)之前插入一個(gè)值為x的新結(jié)點(diǎn)*/

{linklist*q,*p,*r;

r=(linklist*)malloc(sizeof(linklist));/*生成新結(jié)點(diǎn)*/

r->data=x;

if(head->next==NULL){head->next=r;

r->next=NULL;

}

else

{q=head->next;

p=head->next->next;

while(p!=NULL)

{if(p->data!=k)*/

{q=p;

p=p->next;

}

elsebreak;49if(p!=NULL)

{q->next=r;

r->next=p;

}

else/*在鏈表表尾處插入新結(jié)點(diǎn)*/

{q->next=r;

r->next=NULL;

}

}

}/*insert*/

該算法的時(shí)間主要耗費(fèi)在查找值為k的結(jié)點(diǎn)位置上,算法時(shí)間復(fù)雜度為O(n)。50

算法2.9單鏈表的插入(C語(yǔ)言函數(shù))

在單鏈表中第i個(gè)結(jié)點(diǎn)(i>=0)之后插入一個(gè)元素為x的結(jié)點(diǎn)。voidinser(head,i)node*head;inti,x;{node*s,*p;intj;s=(node*)malloc(sizeof(node));/*建立一個(gè)待插入的結(jié)點(diǎn)s*/scanf(“%s”,&x);s->data=x;if(i==0)/*如果i=0,則將s所指結(jié)點(diǎn)插入到表頭后返回*/{s->next=head;head=s;}else{p=head;j=i;/*在單鏈表中查找第i個(gè)結(jié)點(diǎn),由p指向*/while(p!=NULL&&j<i){j++;p=p->next;}if(p!=NULL)/*若找查成功,則把s插入到其后*/{s->next=p->next;p->next=s;}elseprintf(“未找到!\n”);}}51(a)

delete(linklist*p)/*刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/

{linklist*r;

r=p->next;

if(r!=NULL)

{p->next=r->next;

free(r);

}}/*delete*/

(b)linklist*delete(linklist*head,inti)/*刪除單鏈表head的第i個(gè)結(jié)點(diǎn)*/

{intj=0;

linklist*p,*s,*q;

p=head;j=0;

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

{p=p->next;

j++;

}(2)刪除算法52if(p->next!=NULL)

{q=p->next;

p->next=p->next->next;

free(q);

}

else

returnNULL;

s=head;

returns;

}/*delete*/

該算法時(shí)間復(fù)雜度為O(n)。53一般情況下,可以按某個(gè)元素的序號(hào)或按某給定值兩種方法檢索。

(1)按值檢索

按值檢索,即是檢索單鏈表中是否存在值為給定值k的結(jié)點(diǎn),整個(gè)過(guò)程可以通過(guò)結(jié)點(diǎn)的值和給定值的比較而實(shí)現(xiàn)。

linklist*locate(linklist*head,elemtypek)

{linklist*s;

s=head->next;/*從第一個(gè)結(jié)點(diǎn)起開(kāi)始比較*/

while(s!=NULL)/*掃描整個(gè)鏈表*/

if(s->data!=k)s=s->next;

elsebreak;returns;/*返回結(jié)點(diǎn)的位置或NULL*/

}/*Locate*/

算法時(shí)間復(fù)雜度為O(n)。3.單鏈表上元素的檢索54

即利用被訪問(wèn)結(jié)點(diǎn)的序號(hào)而檢索或查找結(jié)點(diǎn)的過(guò)程。

linklist*get(linklist*head,inti)

{intj;

linklist*p;

p=head;j=0;

while((p->next!=NULL)&&(i>j))

{p=p->next;

j++;

}

if(i==j)returnp;

else

returnNULL;

}/*get*/

該算法中最壞情況下的時(shí)間復(fù)雜度為O(n)。(2)按序號(hào)檢索55

例,將兩個(gè)遞增的單鏈表合并為一個(gè)遞增單鏈表,且要求不重新開(kāi)辟空間,其算法可描述如下:

void*union(linklist*heada,linklist*headb)/*合并單鏈表heada與headb*/

{linklist*p,*q,*r,*u;

p=heada->next;

q=headb->next;

r=heada;

while(p!=NULL)&&(q!=NULL)

{if(p->data>q->data;

{u=q->next;

r->next=q;

r=q;

q->next=p;

q=u;

}

56else

if(p->data<=q->data)

{r=p;

p=p->next;

}}if(q!=NULL)r->next=q;

}/*union*/57

1.基礎(chǔ)知識(shí):題集2.1、2.4、2.5、2.6、2.7;

2.算法實(shí)現(xiàn):寫(xiě)出教材算法2.10單鏈表的刪除C/C++語(yǔ)言程序,并上機(jī)調(diào)試通過(guò);2.算法設(shè)計(jì)題:2.15、2.16。作業(yè)58

如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)(或第一個(gè)表結(jié)點(diǎn))的地址值,就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán),如圖2.12所示,這樣的鏈表稱(chēng)為循環(huán)鏈表。顯然,它是一種首尾相接的鏈表,從循環(huán)鏈表中任一個(gè)結(jié)點(diǎn)出發(fā)都可訪問(wèn)到表中所有其它結(jié)點(diǎn)。對(duì)單鏈表的鏈接方式稍作一些改變,就可構(gòu)成一個(gè)新的存儲(chǔ)結(jié)構(gòu)——單循環(huán)鏈表。同樣,也有多重鏈的循環(huán)鏈表。在循環(huán)鏈表中,為了使空表和非空表的處理一致,同樣可設(shè)置一個(gè)頭結(jié)點(diǎn)。2.3.2循環(huán)鏈表59

循環(huán)鏈表的基本運(yùn)算與單鏈表基本一致,差別只在于最后一個(gè)結(jié)點(diǎn)的循環(huán)處理上。只要將單鏈表算法中出現(xiàn)NULL處改為頭指針即可。例如,將單循環(huán)鏈表倒置或逆置。

linklist*invert(head)

linklist*head;

{linklist*p,*q,*s;

q=head;

p=head->next;

while(p!=head)

{s=q;

q=p;

p=p->next;

q->next=s;

}

p->next=q;

returnhead;

}/*invert*/60

在單循環(huán)鏈表中,從任一個(gè)已知結(jié)點(diǎn)出發(fā)可以找到其前趨結(jié)點(diǎn),但時(shí)間耗費(fèi)需O(n),若希望能快速確定一個(gè)結(jié)點(diǎn)的直接前趨,可以再加上一個(gè)指針域存儲(chǔ)其直接前趨的信息,這樣就可以構(gòu)成雙向鏈表,它有兩個(gè)方向不同的鏈,如果將每個(gè)方向的鏈表構(gòu)成一個(gè)環(huán),則可以構(gòu)成雙向循環(huán)鏈表。

雙向鏈表的C語(yǔ)言描述:

typedefstructdupnode

{elemtypedata;

structdupnode*next,*prior;

}dulinklist;

dulinklist*head;

雙向循環(huán)鏈表也可由頭指針head唯一確定,同樣可增加頭結(jié)點(diǎn),使得雙鏈表的某些運(yùn)算簡(jiǎn)便一些,如圖2.14所示。2.3.3雙向鏈表6162

由于雙向鏈表在其結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)既有指向其直接前趨的指針域,又有指向其直接后繼的指針域,因此比起單鏈表來(lái),要在一個(gè)雙向鏈表中檢索某一個(gè)已知結(jié)點(diǎn)的直接前趨和后繼結(jié)點(diǎn)要方便得多。結(jié)點(diǎn)*p可通過(guò)多種方式訪問(wèn),設(shè)指針p指向雙向鏈表中某個(gè)結(jié)點(diǎn),則有:p->next->prior=p=p->prior->next

雙向鏈表中結(jié)點(diǎn)的插入情況如圖2.16所示。63

在*p結(jié)點(diǎn)之前插入結(jié)點(diǎn)*s的正確步驟應(yīng)為:

①p->prior->next=s;②s->prior=p->prior;③s->next=p;④p->prior=s;

由于雙向鏈表中每個(gè)結(jié)點(diǎn)涉及兩個(gè)指針的運(yùn)算,對(duì)于某些運(yùn)算要注意運(yùn)算順序。在上面的步驟中指針p->prior的修改必須在*p結(jié)點(diǎn)的前趨結(jié)點(diǎn)*(p->prior)的后繼指針修改之后方可改動(dòng),否則會(huì)不能正確地插入結(jié)點(diǎn)。

在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)*p的指針變化如圖2.15所示。指針修改的運(yùn)算步驟為:①p->prior->next=p->next;②p->next->prior=p->prior;64voidindulist(dulinklist*head,inti,elemtypex)

/*在雙向循環(huán)鏈表head中的第i個(gè)結(jié)點(diǎn)之前插入值為x的新結(jié)點(diǎn)*/

{dulinklist*p,*s;intj;

p=head;j=0;

while((p->next!=head)&&(j<i-1))

{p=p->next;

j++;}

if((i>0)&&(j==i-1))

{s=malloc(sizeof(dulinklist));s->data=x;

s->next=p->next;

s->prior=p;

p->next=s;

s->next->prior=s;}

elseprintf(“error!\n”)

/*indulist*/1.插入算法(算法2.18)65voiddeledulist(dulinklist*head,inti)/*刪除雙向鏈表head中的第i個(gè)結(jié)點(diǎn)*/

{dulinklist*p;intj;

p=head;j=0;

while((p->next!=head)&&(j<i))

{p=p->next;

j++;

}

if((i>0)&&(j==i))

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論