




版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO 7435:2024 EN Fasteners - Slotted set screws with dog point
- 【正版授權(quán)】 ISO 15784-2:2024 EN Intelligent transport systems - Data exchange involving roadside modules communication - Part 2: Centre to field device communications using Simple Netwo
- 2025年度二手房貸款買(mǎi)賣(mài)合同(智能家居升級(jí)版)
- 2025版醫(yī)療器械臨床試驗(yàn)臨床試驗(yàn)現(xiàn)場(chǎng)監(jiān)查服務(wù)合同
- 2025年度密封膠產(chǎn)品環(huán)保認(rèn)證與評(píng)價(jià)合同
- 2025年度環(huán)保設(shè)備研發(fā)與制造合同
- 2025高考作文預(yù)測(cè):需求誠(chéng)可貴創(chuàng)新價(jià)更高
- 制定市場(chǎng)推廣計(jì)劃的實(shí)施步驟
- 固定資產(chǎn)管理流程優(yōu)化計(jì)劃
- 如何制定有效的危機(jī)應(yīng)對(duì)計(jì)劃
- 2024年中國(guó)養(yǎng)老產(chǎn)業(yè)商學(xué)研究報(bào)告-銀發(fā)經(jīng)濟(jì)專(zhuān)題
- 高教版2023年中職教科書(shū)《語(yǔ)文》(基礎(chǔ)模塊)下冊(cè)教案全冊(cè)
- 人教版英語(yǔ)七年級(jí)上冊(cè)閱讀理解專(zhuān)項(xiàng)訓(xùn)練16篇(含答案)
- GA∕T 1193-2014 人身?yè)p害誤工期、護(hù)理期、營(yíng)養(yǎng)期評(píng)定
- 現(xiàn)場(chǎng)組織機(jī)構(gòu)框圖及說(shuō)明5
- LeapMotion教程之手勢(shì)識(shí)別
- Join-in-六年級(jí)下冊(cè)教案-Starter-unit-Join-in-us
- 建設(shè)工程檢測(cè)試驗(yàn)收費(fèi)標(biāo)準(zhǔn)
- 靜脈導(dǎo)管的護(hù)理與固定方法
- word上機(jī)操作題
- 房地產(chǎn)公司管理制度
評(píng)論
0/150
提交評(píng)論