數(shù)據(jù)結(jié)構(gòu)-線性表_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)-線性表_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)-線性表_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)-線性表_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)-線性表_第5頁(yè)
已閱讀5頁(yè),還剩71頁(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)介

2線性表信息學(xué)院暑期培訓(xùn)2線性表線性結(jié)構(gòu)是最常用、最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點(diǎn)是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中:①存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素;②存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素;③除第一個(gè)元素外,每個(gè)元素均有唯一一個(gè)直接前驅(qū);④除最后一個(gè)元素外,每個(gè)元素均有唯一一個(gè)直接后繼。2.1線性表的邏輯結(jié)構(gòu)線性表(LinearList):是由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1,a2,…an組成的有限序列。該序列中的所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí),稱為空表。當(dāng)n>0時(shí),將非空的線性表記作:(a1,a2,…an)a1稱為線性表的第一個(gè)(首)結(jié)點(diǎn),an稱為線性表的最后一個(gè)(尾)結(jié)點(diǎn)。2.1.1

線性表的定義a1,a2,…ai-1都是ai(2≦i≦n)的前驅(qū),其中ai-1是ai的直接前驅(qū);ai+1,ai+2,…an都是ai(1≦i≦n-1)的后繼,其中ai+1是ai的直接后繼。2.1.2線性表的邏輯結(jié)構(gòu)

線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)用的不同而不同,在線性表的定義中,只不過(guò)是一個(gè)抽象的表示符號(hào)?!艟€性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng))。例1:26個(gè)英文字母組成的字母表:(A,B,C、…、Z)例2:某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況:(6,17,28,50,92,188)例3:一副撲克的點(diǎn)數(shù)(2,3,4,…,J,Q,K,A)2.1.2線性表的邏輯結(jié)構(gòu)◆

線性表中的結(jié)點(diǎn)可以是記錄型元素,每個(gè)元素含有多個(gè)數(shù)據(jù)項(xiàng),每個(gè)項(xiàng)稱為結(jié)點(diǎn)的一個(gè)域。每個(gè)元素有一個(gè)可以唯一標(biāo)識(shí)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組,稱為關(guān)鍵字。例4:某校2001級(jí)同學(xué)的基本情況:{(‘2001414101’,‘張里戶’,‘男’,06/24/1983),(‘2001414102’,‘張化司’,‘男’,08/12/1984)…,(‘2001414102’,‘李利辣’,‘女’,08/12/1984)}◆若線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的,稱線性表是有序的。2.1.3線性表的抽象數(shù)據(jù)類型定義

線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu),其長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短。

對(duì)線性表的數(shù)據(jù)元素可以訪問(wèn)、插入和刪除。2.1.3線性表的抽象數(shù)據(jù)類型定義ADTList{

數(shù)據(jù)對(duì)象: 數(shù)據(jù)關(guān)系: 基本操作:

InitList(&L)/*初始化線性表*/ DestroyList(&L)/*銷毀線性表*/ ListEmpty(L)/*判斷是否為空線性表*/ ...... }2.1.3線性表的抽象數(shù)據(jù)類型定義2.2線性表的順序存儲(chǔ)

順序存儲(chǔ):把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。順序存儲(chǔ)的線性表的特點(diǎn):

◆線性表的邏輯順序與物理順序一致;

◆數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)體現(xiàn)。設(shè)有非空的線性表:(a1,a2,…an)。順序存儲(chǔ)如圖2-1所示。2.2.1

線性表的順序存儲(chǔ)結(jié)構(gòu)

在具體的機(jī)器環(huán)境下:設(shè)線性表的每個(gè)元素需占用L個(gè)存儲(chǔ)單元,以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系:

LOC(ai+1)=LOC(ai)+L

線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為:

LOC(ai)=LOC(a1)+(i-1)*L

…a1a2…ai…an…Loc(a1)Loc(ai)+(i-1)*L圖2-1

線性表的順序存儲(chǔ)表示2.2線性表的順序存儲(chǔ)

在高級(jí)語(yǔ)言(如C語(yǔ)言)環(huán)境下:數(shù)組具有隨機(jī)存取的特性,因此,借助數(shù)組來(lái)描述順序表。除了用數(shù)組來(lái)存儲(chǔ)線性表的元素之外,順序表還應(yīng)該有表示線性表的長(zhǎng)度屬性,所以用結(jié)構(gòu)類型來(lái)定義順序表類型。#defineOK1/*預(yù)定義正確標(biāo)識(shí)*/#defineERROR-1/*預(yù)定義錯(cuò)誤標(biāo)識(shí)*/#defineMAX_SIZE100/*預(yù)定義數(shù)組長(zhǎng)度*/typedefintStatus;/*聲明元素類型*/typedefintElemType;/*聲明數(shù)據(jù)元素的類型*/typedefstructsqlist{ElemTypeelem_array[MAX_SIZE];intlength;/*數(shù)組的當(dāng)前長(zhǎng)度*/}SqList;2.2.2順序表的基本操作

順序存儲(chǔ)結(jié)構(gòu)中,很容易實(shí)現(xiàn)線性表的一些操作:初始化、賦值、查找、修改、插入、刪除、求長(zhǎng)度等。以下將對(duì)幾種主要的操作進(jìn)行討論。1順序線性表初始化

StatusInit_SqList(SqList*L){L->elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L->elem_array)returnERROR;else{L->length=0;returnOK;}}補(bǔ)充C語(yǔ)言中malloc是動(dòng)態(tài)內(nèi)存分配函數(shù)。

函數(shù)原型:void*malloc(unsignedintnum_bytes);

參數(shù):num_bytes是無(wú)符號(hào)整型,用于表示分配的字節(jié)數(shù)。

返回值:如果分配成功則返回指向被分配內(nèi)存的指針(此存儲(chǔ)區(qū)中的初始值不確定),否則返回空指針NULL。void*表示未確定類型的指針,void*可以指向任何類型的數(shù)據(jù),更明確的說(shuō)是指申請(qǐng)內(nèi)存空間時(shí)還不知道用戶是用這段空間來(lái)存儲(chǔ)什么類型的數(shù)據(jù)(比如是char還是int或者...)

功能:分配長(zhǎng)度為num_bytes字節(jié)的內(nèi)存塊

注意:當(dāng)內(nèi)存不再使用時(shí),應(yīng)使用free()函數(shù)將內(nèi)存塊釋放。函數(shù)返回的指針一定要適當(dāng)對(duì)齊,使其可以用于任何數(shù)據(jù)對(duì)象。關(guān)于該函數(shù)的原型,在以前malloc返回的是char型指針,新的ANSIC標(biāo)準(zhǔn)規(guī)定,該函數(shù)返回為void型指針,因此必要時(shí)要進(jìn)行類型轉(zhuǎn)換。2.2.2順序表的基本操作2

順序線性表的插入

在線性表L=(a1,…ai-1,ai,ai+1,…,an)中的第i(1≦i≦n)個(gè)位置上插入一個(gè)新結(jié)點(diǎn)e,使其成為線性表:

L=(a1,…ai-1,e,ai,ai+1,…,an)

實(shí)現(xiàn)步驟(1)

將線性表L中的第i個(gè)至第n個(gè)結(jié)點(diǎn)后移一個(gè)位置。(2)將結(jié)點(diǎn)e插入到結(jié)點(diǎn)ai-1之后。(3)線性表長(zhǎng)度加1。2.2.2順序表的基本操作算法描述StatusInsert_SqList(Sqlist*L,inti,ElemTypee)

{intj;if(i<0||i>L->length-1)returnERROR;if(L->length>=MAX_SIZE){printf(“線性表溢出!\n”);returnERROR;}for(j=L->length–1;j>=i-1;--j)L->Elem_array[j+1]=L->Elem_array[j];/*i-1位置以后的所有結(jié)點(diǎn)后移*/L->Elem_array[i-1]=e;/*在i-1位置插入結(jié)點(diǎn)*/L->length++;returnOK;}2.2.2順序表的基本操作

時(shí)間復(fù)雜度分析

在線性表L中的第i個(gè)元素之前插入新結(jié)點(diǎn),其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上,因此,可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。設(shè)在線性表L中的第i個(gè)元素之前插入結(jié)點(diǎn)的概率為Pi,不失一般性,設(shè)各個(gè)位置插入是等概率,則Pi=1/(n+1),而插入時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i+1??偟钠骄苿?dòng)次數(shù):Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在順序表上做插入運(yùn)算,平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí),算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。2.2.2順序表的基本操作3順序線性表的刪除在線性表L=(a1,…ai-1,ai,ai+1,…,an)中刪除結(jié)點(diǎn)ai(1≦i≦n),使其成為線性表:

L=(a1,…ai-1,ai+1,…,an)

實(shí)現(xiàn)步驟(1)將線性表L中的第i+1個(gè)至第n個(gè)結(jié)點(diǎn)依此向前移動(dòng)一個(gè)位置。(2)線性表長(zhǎng)度減1。2.2.2順序表的基本操作算法描述ElemTypeDelete_SqList(Sqlist*L,inti){intk;ElemTypex;if(L->length==0){printf(“線性表L為空!\n”);returnERROR;}elseif(i<1||i>L->length){printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!\n”);returnERROR;}else{x=L->Elem_array[i-1];/*保存結(jié)點(diǎn)的值*/for(k=i;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];/*i位置以后的所有結(jié)點(diǎn)前移*/L->length--;return(x);}}2.2.2順序表的基本操作

時(shí)間復(fù)雜度分析刪除線性表L中的第i個(gè)元素,其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上,因此,可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。設(shè)在線性表L中刪除第i個(gè)元素的概率為Pi,不失一般性,設(shè)刪除各個(gè)位置是等概率,則Pi=1/n,而刪除時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i。則總的平均移動(dòng)次數(shù):Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在順序表上做刪除運(yùn)算,平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí),算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。2.2.2順序表的基本操作4順序線性表的查找定位刪除在線性表L=(a1,a2,…,an)中刪除值為x的第一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)步驟(1)

在線性表L查找值為x的第一個(gè)數(shù)據(jù)元素。(2)將從找到的位置至最后一個(gè)結(jié)點(diǎn)依次向前移動(dòng)一個(gè)位置。

(3)線性表長(zhǎng)度減1。2.2.2順序表的基本操作算法描述StatusLocate_Delete_SqList(Sqlist*L,ElemTypex)/*刪除線性表L中值為x的第一個(gè)結(jié)點(diǎn)*/{inti=0,k;while(i<L->length)/*查找值為x的第一個(gè)結(jié)點(diǎn)*/{if(L->Elem_array[i]!=x)i++;else{for(k=i+1;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];L->length--;break;}}if(i>L->length){printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!\n”);returnERROR;}returnOK;}2.2.2順序表的基本操作

時(shí)間復(fù)雜度分析時(shí)間主要耗費(fèi)在數(shù)據(jù)元素的比較和移動(dòng)操作上。首先,在線性表L中查找值為x的結(jié)點(diǎn)是否存在;其次,若值為x的結(jié)點(diǎn)存在,且在線性表L中的位置為i,則在線性表L中刪除第i個(gè)元素。設(shè)在線性表L刪除數(shù)據(jù)元素概率為Pi,不失一般性,設(shè)各個(gè)位置是等概率,則Pi=1/n。

◆比較的平均次數(shù):Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2。

◆刪除時(shí)平均移動(dòng)次數(shù):Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。平均時(shí)間復(fù)雜度:Ecompare+Edelete=n,即為O(n)2.3線性表的鏈?zhǔn)酱鎯?chǔ)

2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ):用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱線性鏈表。存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的,甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系,在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí),還必須存儲(chǔ)指示其直接后繼結(jié)點(diǎn)的地址(或位置),稱為指針(pointer)或鏈(link),這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu),如圖2-2所示。鏈表是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。每一個(gè)結(jié)只包含一個(gè)指針域的鏈表,稱為單鏈表。為操作方便,總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)(頭指針)head指向第一結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息(或鏈表長(zhǎng)度等信息)。datanext圖2-2鏈表結(jié)點(diǎn)結(jié)構(gòu)data:數(shù)據(jù)域,存放結(jié)點(diǎn)的值。next:指針域,存放結(jié)點(diǎn)的直接后繼的地址。2.3線性表的鏈?zhǔn)酱鎯?chǔ)

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat?head

圖2-3

帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式單鏈表是由表頭唯一確定,因此單鏈表可以用頭指針的名字來(lái)命名。例1、線性表L=(bat,cat,eat,fat,hat)其帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲(chǔ)方式如圖2-3所示。2.3線性表的鏈?zhǔn)酱鎯?chǔ)1結(jié)點(diǎn)的描述與實(shí)現(xiàn)

C語(yǔ)言中用帶指針的結(jié)構(gòu)體類型來(lái)描述typedefstructLnode{ ElemTypedata;/*數(shù)據(jù)域,保存結(jié)點(diǎn)的值*/structLnode*next;/*指針域*/}LNode;/*結(jié)點(diǎn)的類型*/2結(jié)點(diǎn)的實(shí)現(xiàn)結(jié)點(diǎn)是通過(guò)動(dòng)態(tài)分配和釋放來(lái)的實(shí)現(xiàn),即需要時(shí)分配,不需要時(shí)釋放。實(shí)現(xiàn)時(shí)是分別使用C語(yǔ)言提供的標(biāo)準(zhǔn)函數(shù):malloc(),realloc(),sizeof(),free()。2.3線性表的鏈?zhǔn)酱鎯?chǔ)補(bǔ)充原型:externvoid*realloc(void*ptr,size_tnewsize);用法:#include<stdlib.h>功能:改變ptr所指內(nèi)存區(qū)域的大小為newsize長(zhǎng)度。說(shuō)明:如果重新分配成功則返回指向被分配內(nèi)存的指針,否則返回空指針NULL。當(dāng)內(nèi)存不再使用時(shí),應(yīng)使用free()函數(shù)將內(nèi)存塊釋放。補(bǔ)充Sizeof是計(jì)算對(duì)象所占的字節(jié)個(gè)數(shù),通常用來(lái)查看變量或結(jié)構(gòu)體等所占的字節(jié)個(gè)數(shù)。比如:int

a;

sizeof(a);

//

計(jì)算變量a所占的字節(jié)數(shù),等價(jià)于sizeof(int)

struct

{

int

num;

char

name[];

int

age;

}person;

sizeof(person);

//

計(jì)算整個(gè)結(jié)構(gòu)所占的字節(jié)總數(shù)

補(bǔ)充C語(yǔ)言中,free可以釋放calloc,malloc,realloc動(dòng)態(tài)分配的空間。首先說(shuō)明一下,你要釋放的不是你定義的指針,而是你定義的指針指向的空間。至于你定義的普通指針是不是可以通過(guò)free釋放,這個(gè)要看情況。如果你定義的指針指向動(dòng)態(tài)分配的地址空間,則可以使用free釋放指針指向的這段空間;否則,就不能使用free釋放指針指向的空間。下面舉兩個(gè)例子:

例1:char*p=NULL;p=(char*)malloc(1024);if(p!=NULL)free(p);

例2:char*p=NULL;charbuf[1024];p=(char*)buf;free(p);其中,例1是對(duì)的,例2是錯(cuò)誤的。

動(dòng)態(tài)分配

p=(LNode*)malloc(sizeof(LNode));函數(shù)malloc分配了一個(gè)類型為L(zhǎng)Node的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中。動(dòng)態(tài)釋放

free(p);系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)。P必須是最近一次調(diào)用malloc函數(shù)時(shí)的返回值。2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.3線性表的鏈?zhǔn)酱鎯?chǔ)⑴

結(jié)點(diǎn)的賦值

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL3最常用的基本操作及其示意圖⑵

常見(jiàn)的指針操作①

q=p;pa……操作前pa……q操作后②

q=p->next;bpa……操作前操作后qbpa……③

p=p->next;bpa……操作前操作后pba……④

q->next=p;c…pbqa……操作前操作后qb……ac…p(a)2.3線性表的鏈?zhǔn)酱鎯?chǔ)⑤

q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.3.2單線性鏈?zhǔn)降幕静僮?建立單鏈表假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是整型,以32767作為結(jié)束標(biāo)志。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種:頭插入法,尾插入法。⑴頭插入法建表從一個(gè)空表開(kāi)始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點(diǎn),將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到讀入結(jié)束標(biāo)志為止。即每次插入的結(jié)點(diǎn)都作為鏈表的第一個(gè)結(jié)點(diǎn)。算法描述LNode*create_LinkList(void)/*頭插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值*/{intdata;LNode*head,*p;head=(LNode*)malloc(sizeof(LNode));head->next=NULL;/*創(chuàng)建鏈表的表頭結(jié)點(diǎn)head*/while(1){scanf(“%d”,&data);if(data==32767)break;p=(LNode*)malloc(sizeof(LNode));p–>data=data;/*數(shù)據(jù)域賦值*/p–>next=head–>next;head–>next=p;/*鉤鏈,新創(chuàng)建的結(jié)點(diǎn)總是作為第一個(gè)結(jié)點(diǎn)*/}return(head);}2.3.2單線性鏈?zhǔn)降幕静僮?2)尾插入法建表頭插入法建立鏈表雖然算法簡(jiǎn)單,但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致,可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾,使其成為當(dāng)前鏈表的尾結(jié)點(diǎn)。2.3.2單線性鏈?zhǔn)降幕静僮?.3.2單線性鏈?zhǔn)降幕静僮魉惴枋鯨Node*create_LinkList(void)/*尾插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值*/{intdata;LNode*head,*p,*q;head=p=(LNode*)malloc(sizeof(LNode));p->next=NULL;/*創(chuàng)建單鏈表的表頭結(jié)點(diǎn)head*/while(1){scanf(“%d”,&data);if(data==32767)break;q=(LNode*)malloc(sizeof(LNode));q–>data=data;/*數(shù)據(jù)域賦值*/q–>next=p–>next;p–>next=q;p=q;

/*鉤鏈,新創(chuàng)建的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)*/}return(head);}2.3.2單線性鏈?zhǔn)降幕静僮鳠o(wú)論是哪種插入方法,如果要插入建立的單線性鏈表的結(jié)點(diǎn)是n個(gè),算法的時(shí)間復(fù)雜度均為O(n)。對(duì)于單鏈表,無(wú)論是哪種操作,只要涉及到鉤鏈(或重新鉤鏈),如果沒(méi)有明確給出直接后繼,鉤鏈(或重新鉤鏈)的次序必須是“先右后左”。2.3.2單線性鏈?zhǔn)降幕静僮?單鏈表的查找(1)按序號(hào)查找取單鏈表中的第i個(gè)元素。對(duì)于單鏈表,不能象順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn),而只能從鏈表的頭結(jié)點(diǎn)出發(fā),沿鏈域next逐個(gè)結(jié)點(diǎn)往下搜索,直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此,鏈表不是隨機(jī)存取結(jié)構(gòu)。設(shè)單鏈表的長(zhǎng)度為n,要查找表中第i個(gè)結(jié)點(diǎn),僅當(dāng)1≦i≦n時(shí),i的值是合法的。算法描述ElemTypeGet_Elem(LNode*L,inti){intj;LNode*p;p=L->next;j=1;/*使p指向第一個(gè)結(jié)點(diǎn)*/while(p!=NULL&&j<i){p=p–>next;j++;}/*移動(dòng)指針p,j計(jì)數(shù)*/if(j!=i)return(-32768);elsereturn(p->data);/*p為NULL表示i太大;j>i表示i為0*/}移動(dòng)指針p的頻度:i<1時(shí):0次;i∈[1,n]:i-1次;i>n:n次。∴時(shí)間復(fù)雜度:O(n)。2.3.2單線性鏈?zhǔn)降幕静僮?2)

按值查找

按值查找是在鏈表中,查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)?若有,則返回首次找到的值為key的結(jié)點(diǎn)的存儲(chǔ)位置;否則返回NULL。查找時(shí)從開(kāi)始結(jié)點(diǎn)出發(fā),沿鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。2.3.2單線性鏈?zhǔn)降幕静僮魉惴枋鯨Node*Locate_Node(LNode*L,intkey)/*在以L為頭結(jié)點(diǎn)的單鏈表中查找值為key的第一個(gè)結(jié)點(diǎn)*/{LNode*p=L–>next;while(p!=NULL&&p–>data!=key)p=p–>next;if(p–>data==key)returnp;else{printf(“所要查找的結(jié)點(diǎn)不存在!!\n”);retutn(NULL);}}算法的執(zhí)行與形參key有關(guān),平均時(shí)間復(fù)雜度為O(n)。2.3.2單線性鏈?zhǔn)降幕静僮?單鏈表的插入

插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上,即插入到ai-1與ai之間。因此,必須首先找到ai-1所在的結(jié)點(diǎn)p,然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)q,q結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn)。設(shè)鏈表的長(zhǎng)度為n,合法的插入位置是1≦i≦n。算法的時(shí)間主要耗費(fèi)移動(dòng)指針p上,故時(shí)間復(fù)雜度亦為O(n)。算法描述voidInsert_LNode(LNode*L,inti,ElemTypee)/*在以L為頭結(jié)點(diǎn)的單鏈表的第i個(gè)位置插入值為e的結(jié)點(diǎn)*/{intj=0;LNode*p,*q;p=L–>next;while(p!=NULL&&j<i-1){p=p–>next;j++;}if(j!=i-1)printf(“i太大或i為0!!\n”);else{q=(LNode*)malloc(sizeof(LNode));q–>data=e;q–>next=p–>next;p–>next=q;}}2.3.2單線性鏈?zhǔn)降幕静僮?單鏈表的刪除⑴

按序號(hào)刪除

刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。為了刪除第i個(gè)結(jié)點(diǎn)ai,必須找到結(jié)點(diǎn)的存儲(chǔ)地址。該存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的next域中,因此,必須首先找到ai-1的存儲(chǔ)位置p,然后令p–>next指向ai的直接后繼結(jié)點(diǎn),即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間,將其歸還給“存儲(chǔ)池”。設(shè)單鏈表長(zhǎng)度為n,則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≦i≦n時(shí)是合法的。則當(dāng)i=n+1時(shí),雖然被刪結(jié)點(diǎn)不存在,但其前趨結(jié)點(diǎn)卻存在,是終端結(jié)點(diǎn)。故判斷條件之一是p–>next!=NULL。顯然此算法的時(shí)間復(fù)雜度也是O(n)。2.3.2單線性鏈?zhǔn)降幕静僮魉惴枋鰒oidDelete_LinkList(LNode*L,inti)/*刪除以L為頭結(jié)點(diǎn)的單鏈表中的第i個(gè)結(jié)點(diǎn)*/{intj=1;LNode*p,*q;p=L;q=L->next;while(p->next!=NULL&&j<i){p=q;q=q–>next;j++;}if(j!=i)printf(“i太大或i為0!!\n”);else{p–>next=q–>next;free(q);}}2.3.2單線性鏈?zhǔn)降幕静僮鳍瓢粗祫h除

刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。與按值查找相類似,首先要查找值為key的結(jié)點(diǎn)是否存在?若存在,則刪除;否則返回NULL。2.3.2單線性鏈?zhǔn)降幕静僮魉惴枋鰒oidDelete_LinkList(LNode*L,intkey)/*刪除以L為頭結(jié)點(diǎn)的單鏈表中值為key的第一個(gè)結(jié)點(diǎn)*/{LNode*p=L,*q=L–>next;while(q!=NULL&&q–>data!=key){p=q;q=q–>next;}if(q–>data==key){p->next=q->next;free(q);}elseprintf(“所要?jiǎng)h除的結(jié)點(diǎn)不存在!!\n”);}2.3.2單線性鏈?zhǔn)降幕静僮魉惴ǖ膱?zhí)行與形參key有關(guān),平均時(shí)間復(fù)雜度為O(n)。從上面的討論可以看出,鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算,無(wú)需移動(dòng)結(jié)點(diǎn),僅需修改指針。解決了順序表的插入或刪除操作需要移動(dòng)大量元素的問(wèn)題。變形之一:刪除單鏈表中值為key的所有結(jié)點(diǎn)。與按值查找相類似,但比前面的算法更簡(jiǎn)單?;舅枷耄簭膯捂湵淼牡谝粋€(gè)結(jié)點(diǎn)開(kāi)始,對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行檢查,若結(jié)點(diǎn)的值為key,則刪除之,然后檢查下一個(gè)結(jié)點(diǎn),直到所有的結(jié)點(diǎn)都檢查。2.3.2單線性鏈?zhǔn)降幕静僮魉惴枋鰒oidDelete_LinkList_Node(LNode*L,intkey)/*刪除以L為頭結(jié)點(diǎn)的單鏈表中值為key的第一個(gè)結(jié)點(diǎn)*/{LNode*p=L,*q=L–>next;while(q!=NULL){if(q–>data==key){p->next=q->next;free(q);q=p->next;}else{p=q;q=q–>next;}}}2.3.2單線性鏈?zhǔn)降幕静僮髯冃沃簞h除單鏈表中所有值重復(fù)的結(jié)點(diǎn),使得所有結(jié)點(diǎn)的值都不相同。與按值查找相類似,但比前面的算法更復(fù)雜?;舅枷耄簭膯捂湵淼牡谝粋€(gè)結(jié)點(diǎn)開(kāi)始,對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行檢查:檢查鏈表中該結(jié)點(diǎn)的所有后繼結(jié)點(diǎn),只要有值和該結(jié)點(diǎn)的值相同,則刪除之;然后檢查下一個(gè)結(jié)點(diǎn),直到所有的結(jié)點(diǎn)都檢查。2.3.2單線性鏈?zhǔn)降幕静僮魉惴枋鰒oidDelete_Node_value(LNode*L)/*刪除以L為頭結(jié)點(diǎn)的單鏈表中所有值相同的結(jié)點(diǎn)*/{LNode*p=L->next,*q,*ptr;while(p!=NULL)/*檢查鏈表中所有結(jié)點(diǎn)*/{*q=p,*ptr=p–>next;/*檢查結(jié)點(diǎn)p的所有后繼結(jié)點(diǎn)ptr*/while(ptr!=NULL){if(ptr–>data==p->data){q->next=ptr->next;free(ptr);ptr=q->next;}else{q=ptr;ptr=ptr–>next;}}p=p->next;}}2.3.2單線性鏈?zhǔn)降幕静僮?單鏈表的合并

設(shè)有兩個(gè)有序的單鏈表,它們的頭指針?lè)謩e是La、Lb,將它們合并為以Lc為頭指針的有序鏈表。合并前的示意圖如圖2-4所示。15?圖2-4兩個(gè)有序的單鏈表La,Lb的初始狀態(tài)-249……Lb

pb-7312……23?La

Lcpapc2.3.2單線性鏈?zhǔn)降幕静僮骱喜⒘酥禐?7,-2的結(jié)點(diǎn)后示意圖如圖2-5所示。圖2-5

合并了值為-7,-2的結(jié)點(diǎn)后的狀態(tài)-249……

15?Lb

pcpbLc-7312……

23?La

pa算法說(shuō)明——算法中pa,pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn),pc是合并過(guò)程中合并的鏈表的最后一個(gè)結(jié)點(diǎn)。2.3.2單線性鏈?zhǔn)降幕静僮魉惴枋鯨Node*Merge_LinkList(LNode*La,LNode*Lb)/*合并以La,Lb為頭結(jié)點(diǎn)的兩個(gè)有序單鏈表*/{LNode*Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL &&pb!=NULL){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}/*將pa所指的結(jié)點(diǎn)合并,pa指向下一個(gè)結(jié)點(diǎn)*/if(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}/*將pa所指的結(jié)點(diǎn)合并,pa指向下一個(gè)結(jié)點(diǎn)*/if(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;free(ptr);}/*將pa所指的結(jié)點(diǎn)合并,pb所指結(jié)點(diǎn)刪除*/}if(pa!=NULL)pc->next=pa;elsepc->next=pb;/*將剩余的結(jié)點(diǎn)鏈上*/free(Lb);return(Lc);}2.3.2單線性鏈?zhǔn)降幕静僮魉惴ǚ治鋈鬖a,Lb兩個(gè)鏈表的長(zhǎng)度分別是m,n,則鏈表合并的時(shí)間復(fù)雜度為O(m+n)。2.3.2單線性鏈?zhǔn)降幕静僮?.3.3循環(huán)鏈表循環(huán)鏈表(CircularLinkedList):是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn),整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)。從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn),使得表處理更加方便靈活。圖2-6是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖??毡韴D2-6單循環(huán)鏈表示意圖非空表a1

a2

……anhead

head

循環(huán)鏈表的操作對(duì)于單循環(huán)鏈表,除鏈表的合并外,其它的操作和單線性鏈表基本上一致,僅僅需要在單線性鏈表操作算法基礎(chǔ)上作以下簡(jiǎn)單修改:⑴判斷是否是空鏈表:head->next==head;⑵判斷是否是表尾結(jié)點(diǎn):p->next==head;2.3.3循環(huán)鏈表2.4雙向鏈表雙向鏈表(DoubleLinkedList):指的是構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)中設(shè)立兩個(gè)指針域:一個(gè)指向其直接前趨的指針域prior,一個(gè)指向其直接后繼的指針域next。這樣形成的鏈表中有兩個(gè)方向不同的鏈,故稱為雙向鏈表。和單鏈表類似,雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表,并稱之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。1雙向鏈表的結(jié)點(diǎn)及其類型定義雙向鏈表的結(jié)點(diǎn)的類型定義如下。其結(jié)點(diǎn)形式如圖2-7所示,帶頭結(jié)點(diǎn)的雙向鏈表的形式如圖2-8所示。typedefstructDulnode{ElemTypedata;structDulnode*prior,*next;}DulNode;datanextprior圖2-7雙向鏈表結(jié)點(diǎn)形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??圖2-8帶頭結(jié)點(diǎn)的雙向鏈表形式2.4雙向鏈表雙向鏈表結(jié)構(gòu)具有對(duì)稱性,設(shè)p指向雙向鏈表中的某一結(jié)點(diǎn),則其對(duì)稱性可用下式描述:(p->prior)->next=p=(p->next)->prior;結(jié)點(diǎn)p的存儲(chǔ)位置存放在其直接前趨結(jié)點(diǎn)p->prior的直接后繼指針域中,同時(shí)也存放在其直接后繼結(jié)點(diǎn)p->next的直接前趨指針域中。2.4雙向鏈表2雙向鏈表的基本操作(1)

雙向鏈表的插入將值為e的結(jié)點(diǎn)插入雙向鏈表中。插入前后鏈表的變化如圖2-9所示。Sep…………aiai+1Sep…………aiai+1圖2-9雙向鏈表的插入2.4雙向鏈表①

插入時(shí)僅僅指出直接前驅(qū)結(jié)點(diǎn),鉤鏈時(shí)必須注意先后次序是:“先右后左”

。部分語(yǔ)句組如下:S=(DulNode*)malloc(sizeof(DulNode));S->data=e;S->next=p->next;p->next->prior=S;p->next=S;S->prior=p;/*鉤鏈次序非常重要

*/②

插入時(shí)同時(shí)指出直接前驅(qū)結(jié)點(diǎn)p和直接后繼結(jié)點(diǎn)q,鉤鏈時(shí)無(wú)須注意先后次序。部分語(yǔ)句組如下:S=(DulNode*)malloc(sizeof(DulNode));S->data=e;p->next=S;S->next=q;S->prior=p;q->prior=S;

2.4雙向鏈表

(2)

雙向鏈表的結(jié)點(diǎn)刪除

設(shè)要?jiǎng)h除的結(jié)點(diǎn)為p,刪除時(shí)可以不引入新的輔助指針變量,可以直接先斷鏈,再釋放結(jié)點(diǎn)。部分語(yǔ)句組如下:p->prior->next=p->next;p->next->prior=p->prior;free(p);注意:

與單鏈表的插入和刪除操作不同的是,在雙向鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針域的指向。2.4雙向鏈表2.5一元多項(xiàng)式的表示和相加1一元多項(xiàng)式的表示一元多項(xiàng)式p(x)=p0+p1x+p2x2+…+pnxn,由n+1個(gè)系數(shù)唯一確定。則在計(jì)算機(jī)中可用線性表(p0

,p1

,p2

,…

,pn

)表示。既然是線性表,就可以用順序表和鏈表來(lái)實(shí)現(xiàn)。兩種不同實(shí)現(xiàn)方式的元素類型定義如下:(1)順序存儲(chǔ)表示的類型typedefstruct{floatcoef;/*系數(shù)部分*/intexpn;/*指數(shù)部分*/}ElemType;(2)鏈?zhǔn)酱鎯?chǔ)表示的類型typedefstructploy{floatcoef;/*系數(shù)部分*/intexpn;/*指數(shù)部分*/structploy*next;}Ploy;2.5一元多項(xiàng)式的表示和相加2一元多項(xiàng)式的相加

不失一般性,設(shè)有兩個(gè)一元多項(xiàng)式:P(x)=p0+p1x+p2x2+…+pnxn,Q(x)=q0+q1x+q2x2+…+qmxm(m<n)R(x)=P(x)+Q(x)R(x)由線性表R((p0+q0),(p1+q1),(p2+q2),…,(pm+qm),…,pn)唯一表示。2.5一元多項(xiàng)式的表示和相加⑴

順序存儲(chǔ)表示的相加線性表的定義typedefstruct{ElemTypea[MAX_SIZE];intlength;}Sqlist;

用順序表示的相加非常簡(jiǎn)單。訪問(wèn)第5項(xiàng)可直接訪問(wèn):L.a[4].coef,L.a[4].expn(2)

鏈?zhǔn)酱鎯?chǔ)表示的相加當(dāng)采用鏈?zhǔn)酱鎯?chǔ)表示時(shí),根據(jù)結(jié)點(diǎn)類型定義,凡是系數(shù)為0的項(xiàng)不在鏈表中出現(xiàn),從而可以大大減少鏈表的長(zhǎng)度。2.5一元多項(xiàng)式的表示和相加一元多項(xiàng)式相加的實(shí)質(zhì)是:指數(shù)不同:是鏈表的合并。指數(shù)相同:系數(shù)相加,和為0,去掉結(jié)點(diǎn),和不為0,修改結(jié)點(diǎn)的系數(shù)域。算法之一:就在原來(lái)兩個(gè)多項(xiàng)式鏈表的基礎(chǔ)上進(jìn)行相加,相加后原來(lái)兩個(gè)多項(xiàng)式鏈表就不在存在。當(dāng)然再要對(duì)原來(lái)兩個(gè)多項(xiàng)式進(jìn)行其它操作就不允許了。2.5一元多項(xiàng)式的表示和相加算法描述Ploy*add_ploy(ploy*La,ploy*Lb)/*將以La,Lb為頭指針表示的一元多項(xiàng)式相加*/{ploy*Lc,*pc,*pa,*pb,*ptr;floatx;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->expn<pb->expn){pc->next=pa;pc=pa;pa=pa->next;}/*將pa所指的結(jié)點(diǎn)合并,pa指向下一個(gè)結(jié)點(diǎn)*/if(pa->expn>pb->expn){pc->next=pb;pc=pb;pb=pb->next;}/*將pb所指的結(jié)點(diǎn)合并,pb指向下一個(gè)結(jié)點(diǎn)*/2.5一元多項(xiàng)式的表示和相加else{x=pa->coef+pb->coef;if(abs(x)<=1.0e-6)/*如果系數(shù)和為0,刪除兩個(gè)結(jié)點(diǎn)*/{ptr=pa;pa=pa->next;free(ptr);ptr=pb;pb=pb->next;free(ptr);}else/*如果系數(shù)和不為0,修改其中一個(gè)結(jié)點(diǎn)的系數(shù)域,刪除另一個(gè)結(jié)點(diǎn)*/{pc->next=pa;pa->coef=x;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;free(p

溫馨提示

  • 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)論