C語(yǔ)言動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

第七章動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu),目錄,態(tài)數(shù)據(jù)結(jié)構(gòu),本章開(kāi)始介紹動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，主要介紹鏈表結(jié)構(gòu)的建立、在鏈表中查找指定元素、插入一個(gè)新元素、刪除一個(gè)元素等操作。學(xué)完本章內(nèi)容后，要求深刻理解動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)的概念，并正確運(yùn)用。,7.1從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu),在此之前，我們涉及到的都是靜態(tài)數(shù)據(jù)結(jié)構(gòu)，像數(shù)組、簡(jiǎn)單類(lèi)型(int、float)等。靜態(tài)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是由系統(tǒng)分配固定大小的存儲(chǔ)空間，以后在程序運(yùn)行的過(guò)程中，存儲(chǔ)空間的位置和容量都不會(huì)再改變。而實(shí)際生活中常常有這樣的問(wèn)題，數(shù)據(jù)量的多少是動(dòng)態(tài)變化的。,7.1從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu),例如，圖書(shū)館的藏書(shū)量，在圖書(shū)館初建時(shí)，假設(shè)有10000本，隨著時(shí)間的推移，藏書(shū)的數(shù)量必定要增加。有人可能會(huì)想，在定義一個(gè)靜態(tài)變量時(shí)，預(yù)留出一部分空間，但這也會(huì)引起一些問(wèn)題，首先多出的那部分空間不知何時(shí)才能使用，在沒(méi)有被使用之前一直被閑置；其次，誰(shuí)又能保證增加的空間就足夠呢？,7.1從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu),問(wèn)題的關(guān)鍵在于，此問(wèn)題的數(shù)據(jù)本身就是變化的，而且是不確定的變化，什么時(shí)候變、怎么變都是未知的。對(duì)這樣的問(wèn)題用靜態(tài)存儲(chǔ)結(jié)構(gòu)來(lái)描述和存放顯然捉襟見(jiàn)肘，存在隱患。動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)不確定總的數(shù)據(jù)存儲(chǔ)量，而是為現(xiàn)有的每一個(gè)數(shù)據(jù)元素定義一個(gè)確定的初始大小的空間，若干個(gè)數(shù)據(jù)元素分配若干個(gè)同樣大小的空間；當(dāng)問(wèn)題的數(shù)據(jù)量發(fā)生變化時(shí)，數(shù)據(jù)的存儲(chǔ)空間的大小也發(fā)生變化。如果數(shù)據(jù)量增加，就重新向系統(tǒng)申請(qǐng)新的空間；如果數(shù)據(jù)量減少，就將現(xiàn)有的多余的空間歸還給系統(tǒng)。,7.2.動(dòng)態(tài)內(nèi)存分配,使用計(jì)算機(jī)解決問(wèn)題的所有方法都是通過(guò)使用系統(tǒng)提供給我們的基本命令或函數(shù)來(lái)實(shí)現(xiàn)的。所以首先讓我們來(lái)看看，c的標(biāo)準(zhǔn)函數(shù)中有哪些是用于動(dòng)態(tài)內(nèi)存分配的，怎樣使用。,7.2.1ANSIC中動(dòng)態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù),ANSIC中提供了若干個(gè)動(dòng)態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù)，它們的名稱(chēng)分別是malloc、calloc、realloc、free等。這些函數(shù)可以使用在任何的C環(huán)境中。,1malloc函數(shù),malloc函數(shù)是C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。原型為：void*malloc(unsignedintsize);其作用是向系統(tǒng)申請(qǐng)一個(gè)確定大小(size個(gè)字節(jié))的存儲(chǔ)空間，返回值為一個(gè)指向void類(lèi)型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。,1malloc函數(shù),使用格式：指針型變量=(基類(lèi)型*)malloc(需要的存儲(chǔ)空間的字節(jié)數(shù));例7-1：為一個(gè)整數(shù)分配存儲(chǔ)空間，需要的語(yǔ)句為：在文件的頭部：#include在說(shuō)明部分：int*p;在程序中：p=(int*)malloc(sizeof(int);,測(cè)試malloc的程序舉例：,#include#include#includevoidmain()int*p;/*定義一個(gè)指向整型的指針變量*/intx;p=(int*)malloc(sizeof(int);if(!p)exit(0);p=,2calloc函數(shù),calloc函數(shù)是C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。原型為：void*calloc(unsignedintn,unsignedintsize);其作用是向系統(tǒng)申請(qǐng)n個(gè)大小為size個(gè)字節(jié)的連續(xù)存儲(chǔ)空間，返回值為一個(gè)指向void類(lèi)型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。可以為一維數(shù)組開(kāi)辟一片連續(xù)的動(dòng)態(tài)存儲(chǔ)空間。,2calloc函數(shù),使用格式：指針型變量=(數(shù)組元素類(lèi)型*)calloc(n,每一個(gè)數(shù)組元素的存儲(chǔ)空間的字節(jié)數(shù))；例7-2：為一個(gè)有10個(gè)整數(shù)的一維數(shù)組分配存儲(chǔ)空間，需要的語(yǔ)句為：在文件的頭部：#include在說(shuō)明部分：int*p;在程序中：p=(int*)calloc(10,sizeof(int);,使用calloc函數(shù)程序舉例：,#include#include#includemain()int*p;intx;p=(int*)calloc(10,sizeof(int);if(!p)exit(0);for(i=0;idata=10;p-next=NULL;deletep;,new與malloc的相同點(diǎn)是他們的作用都是在程序的執(zhí)行過(guò)程中向系統(tǒng)申請(qǐng)存儲(chǔ)空間，返回值都是申請(qǐng)到的存儲(chǔ)空間的首地址，不同點(diǎn)是，malloc是c編譯系統(tǒng)提供的標(biāo)準(zhǔn)庫(kù)函數(shù)，new是c+系統(tǒng)提供的運(yùn)算符，new的操作效率要高于malloc；new不需要使用顯式的sizeof函數(shù)就能知道名字的大小，而malloc需要明確指出所申請(qǐng)的空間的大小(總的字節(jié)數(shù))；new的返回值是指向名字類(lèi)型的確定的指針類(lèi)型，不需要強(qiáng)制說(shuō)明，而malloc的返回值是一個(gè)指向void類(lèi)型的指針類(lèi)型，需要強(qiáng)制轉(zhuǎn)換成指向具體數(shù)據(jù)類(lèi)型的指針類(lèi)型。當(dāng)所申請(qǐng)的空間是一個(gè)變量所需的空間時(shí)，new運(yùn)算符還可以為所申請(qǐng)的空間賦初值，malloc不具有此功能。,7.3鏈表,計(jì)算機(jī)處理數(shù)據(jù)需要兩方面的工作，一方面是對(duì)數(shù)據(jù)信息的描述，另一方面是對(duì)數(shù)據(jù)的操作，而操作的方式取決于數(shù)據(jù)的描述方式，數(shù)據(jù)的描述方式又取決于數(shù)據(jù)本身固有的內(nèi)在聯(lián)系。這里僅介紹數(shù)據(jù)之間的線性關(guān)系。對(duì)于圖書(shū)館的藏書(shū)這類(lèi)數(shù)據(jù)信息可以用一種稱(chēng)為線性表的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來(lái)描述。簡(jiǎn)單的說(shuō)，線性表是n個(gè)數(shù)據(jù)元素的有限序列。各數(shù)據(jù)元素屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。記為：（a1，a2，ai，ai+1，an）,線性表中的數(shù)據(jù)元素之間存在嚴(yán)格的順序關(guān)系，有一個(gè)唯一的稱(chēng)為第一個(gè)的元素（首元），有唯一的稱(chēng)為最后一個(gè)的元素（尾元），其它元素都有唯一的直接后繼元素和唯一的直接前趨元素。線性表這種邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)表示時(shí)，可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即一個(gè)數(shù)據(jù)元素存放于一個(gè)結(jié)點(diǎn)中，不同的數(shù)據(jù)元素之間的先后順序用結(jié)點(diǎn)的指針域鏈接。一個(gè)結(jié)點(diǎn)就是一個(gè)結(jié)構(gòu)體類(lèi)型的變量。,7.3.1鏈表的定義,鏈表是表示具有線性關(guān)系的一組數(shù)據(jù)元素的動(dòng)態(tài)結(jié)構(gòu)。每一個(gè)數(shù)據(jù)元素占據(jù)一個(gè)獨(dú)立申請(qǐng)的存儲(chǔ)空間，這個(gè)存儲(chǔ)空間通常是一個(gè)結(jié)構(gòu)體型變量，主要包括兩部分，一部分用來(lái)存放數(shù)據(jù)元素的值稱(chēng)為值域，另一部分用來(lái)存放一個(gè)指向該結(jié)構(gòu)體類(lèi)型的指針變量值稱(chēng)為指針域。指針域的作用是存放邏輯上排在本結(jié)點(diǎn)后面的結(jié)點(diǎn)的存儲(chǔ)空間的首地址。數(shù)據(jù)元素結(jié)點(diǎn)的結(jié)構(gòu)如圖所示：,若干個(gè)結(jié)點(diǎn)首尾相連按照其邏輯順序鏈接成一排，稱(chēng)為線性鏈表。單向鏈表如下圖所示：,圖7.2單向鏈表,1.鏈表結(jié)點(diǎn)的C語(yǔ)句定義,對(duì)于鏈表這種數(shù)據(jù)結(jié)構(gòu)，ANSIC中，按如下方式描述：首先用結(jié)構(gòu)體類(lèi)型描述一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，定義一個(gè)結(jié)點(diǎn)類(lèi)型的語(yǔ)句格式：typedefstructLNodeElemTypedata；structLNode*next；LNode，*LinkList；,其中：,typedef語(yǔ)句定義了一個(gè)結(jié)構(gòu)體類(lèi)型和鏈表類(lèi)型LNode是一個(gè)結(jié)點(diǎn)的類(lèi)型名稱(chēng)。它有兩個(gè)成員，一個(gè)名稱(chēng)為data，類(lèi)型為數(shù)據(jù)元素的類(lèi)型，用來(lái)存放一個(gè)數(shù)據(jù)元素的值；另一個(gè)成員名稱(chēng)為next，類(lèi)型為指向本結(jié)構(gòu)體類(lèi)型的指針類(lèi)型，用來(lái)存放邏輯上排在本結(jié)點(diǎn)后面的結(jié)點(diǎn)的首地址。LinkList是指向LNode類(lèi)型的指針類(lèi)型。ElemType是數(shù)據(jù)元素的類(lèi)型的一般性描述，當(dāng)我們具體寫(xiě)程序時(shí)，應(yīng)該用確定類(lèi)型名稱(chēng)來(lái)替換，例如，int、float、char等。,例7-6：鏈表中的數(shù)據(jù)元素用來(lái)存放整數(shù)，定義鏈表的結(jié)點(diǎn)類(lèi)型的語(yǔ)句格式為：typedefstructLNodeintdata；structLNode*next；LNode，*LinkList；,定義一個(gè)指向結(jié)點(diǎn)類(lèi)型的指針類(lèi)型變量的語(yǔ)句：LNode*p;3定義一個(gè)鏈表類(lèi)型的指針變量：LinkListL;4訪問(wèn)結(jié)點(diǎn)變量p的各個(gè)成員：p-data,p-next說(shuō)明：本章的所有程序都是基于以上類(lèi)型定義。,7.3.2鏈表的建立,1.構(gòu)造一個(gè)空線性鏈表L首先，構(gòu)造一個(gè)空的線性鏈表。為了描述方便，通常將鏈表的第一個(gè)結(jié)點(diǎn)空置，不存放數(shù)據(jù)元素，只是作為鏈表的開(kāi)始標(biāo)志，稱(chēng)為頭結(jié)點(diǎn)。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開(kāi)始存放?？盏木€性表定義為沒(méi)有數(shù)據(jù)元素的表。一個(gè)空的線性鏈表就規(guī)定為，只有一個(gè)頭結(jié)點(diǎn)的鏈表。所以，構(gòu)造一個(gè)空的線性鏈表就是建立只有一個(gè)頭結(jié)點(diǎn)的鏈表。,（1）算法描述:申請(qǐng)一個(gè)結(jié)點(diǎn)的空間；將該結(jié)點(diǎn)作為線性鏈表的頭結(jié)點(diǎn)；將該結(jié)點(diǎn)的next域置空；,（2）完整程序（Example7_6.cpp）:,/*程序名：Example7_6.cpp*/voidInitList(LinkList*L)/*構(gòu)造一個(gè)空的線性鏈表*/(*L)=(LNode*)malloc(sizeof(LNode)；/*申請(qǐng)一個(gè)結(jié)點(diǎn)空間*/if(!（*L）)exit(0)；/*申請(qǐng)不成功，異常結(jié)束程序運(yùn)行*/（*L）-next=NULL；/*申請(qǐng)成功，頭結(jié)點(diǎn)的next域置空*/return(1)；,2逆序輸入n個(gè)數(shù)據(jù)元素，建立帶表頭結(jié)點(diǎn)的單線性鏈表L,現(xiàn)在開(kāi)始建立一個(gè)非空的線性鏈表。我們這里所建的鏈表的第一個(gè)結(jié)點(diǎn)都是頭結(jié)點(diǎn)。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開(kāi)始存放。一個(gè)非空的線性鏈表是除了頭結(jié)點(diǎn)以外至少有一個(gè)數(shù)據(jù)元素的鏈表。線性鏈表由若干個(gè)數(shù)據(jù)元素結(jié)點(diǎn)組成。那么，構(gòu)造一個(gè)非空的線性鏈表的過(guò)程就是逐個(gè)建立數(shù)據(jù)元素結(jié)點(diǎn)，并將它們依次插入到鏈表中的過(guò)程。,所謂頭插入，即每次將數(shù)據(jù)元素結(jié)點(diǎn)插入到表頭結(jié)點(diǎn)的之后，第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前。插入過(guò)程如圖7-3所示：,初始狀態(tài)：,插入第一個(gè)結(jié)點(diǎn)之后：,插入第二個(gè)結(jié)點(diǎn)之后：,插入第三個(gè)結(jié)點(diǎn)之后：,插入最后一個(gè)結(jié)點(diǎn)之后：,voidCreateList(LinkList*L，intn)inti;LNode*P;(*L)=(LNode*)malloc(sizeof(LNode)；if(!(*L)exit(0);(*L)-next=NULL；for(i=n；i0；i-)p=(LNode*)malloc(sizeof(LNode)；if(!p)exit(0);scanf(“%d”,以上的算法只是建立鏈表的一種方法，它的核心是新的數(shù)據(jù)元素結(jié)點(diǎn)插在鏈表的第一個(gè)數(shù)據(jù)元素的位置；我們也可以將新建立的數(shù)據(jù)元素結(jié)點(diǎn)每次都插在鏈表的尾部，大家可以思考一下，以尾插入的方式建立鏈表，程序怎樣編寫(xiě)？,7.3.3鏈表結(jié)點(diǎn)的插入,將一個(gè)數(shù)據(jù)元素插入到鏈表中，有三種情況：頭插入，尾插入以及在鏈表中的第i個(gè)數(shù)據(jù)元素的位置處插入。將一個(gè)新元素插入在鏈表的頭結(jié)點(diǎn)的后面，其它的所有結(jié)點(diǎn)之前稱(chēng)為頭插入。將一個(gè)新元素插入在鏈表的尾結(jié)點(diǎn)的后面，使得新插入的結(jié)點(diǎn)成為尾結(jié)點(diǎn)稱(chēng)為尾插入。將一個(gè)新元素插入在鏈表中的第i個(gè)數(shù)據(jù)元素的位置處，即插入在第i個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前，使得新插入的結(jié)點(diǎn)成為鏈表中的第i個(gè)結(jié)點(diǎn)。下面我們?cè)敿?xì)介紹每一種插入的算法實(shí)現(xiàn)。,例7-8：已有鏈表L如圖所示,鏈表中的元素按遞增有序排列：,圖7.4鏈表的插入過(guò)程其中每個(gè)結(jié)點(diǎn)中存放的值為學(xué)生的考試成績(jī)?，F(xiàn)在有另外三個(gè)學(xué)生的的成績(jī)分別為65、82、90。將他們插入到鏈表L中，要求插入之后鏈表依然遞增有序。,圖7.5頭插入過(guò)程,首先將65插入到鏈表L中:插入的過(guò)程：設(shè)p=L-next，因?yàn)閜非空，判斷p-data65,所以，65應(yīng)該插在L的后面，70結(jié)點(diǎn)的前面，插入之后的鏈表為：L:,80,70,85,s,p,實(shí)現(xiàn)語(yǔ)句：,p=L-next;s=(LNode*)malloc(sizeof(LNode);s-data=x;s-next=p;L-next=s;,將82插入到鏈表L中:,插入的過(guò)程：首先應(yīng)找到82應(yīng)在的位置：82應(yīng)該插在兩個(gè)結(jié)點(diǎn)之間，82前面結(jié)點(diǎn)的data域值小于82；82后面結(jié)點(diǎn)的data域值大于等于82；如圖所示：L:,實(shí)現(xiàn)語(yǔ)句：,q=*L;p=(*L)-next;while(p,將90插入到鏈表L中:,顯然，90應(yīng)插到鏈表的尾部，即：插到鏈表的最后一個(gè)結(jié)點(diǎn)的后面。插入的過(guò)程：首先找到插入的位置：設(shè)p=L-next，當(dāng)p非空并且p-datanext;循環(huán)一定以p為空結(jié)束。將新結(jié)點(diǎn)90插在q的后面，插入之后的鏈表為：,L:,實(shí)現(xiàn)語(yǔ)句：,x=90;p=L-next;s=(LNode*)malloc(sizeof(LNode);s-data=x;while(pq-next=s;s-next=p;,用一個(gè)程序來(lái)實(shí)現(xiàn)，程序如下：,intListInsert(LNode*L，inte)LNode*s，*q,*p;if(!(*L)return0；s=(LNode*)malloc(sizeof(LNode)；if(!s)exit(0)；s-data=e；p=(*L)-next;q=*L;,while(pq-next=s；return(1)；,7.3.4鏈表結(jié)點(diǎn)的刪除,在7.3.3節(jié)中，詳細(xì)的討論了在一個(gè)鏈表中插入一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)的算法。本節(jié)將討論刪除鏈表中的結(jié)點(diǎn)的算法。例7-9：已有鏈表L如圖所示：,刪除鏈表中數(shù)據(jù)元素值為76,解答：首先查找值為76的結(jié)點(diǎn)：設(shè)p=L-next，q=L;L:,q,p,當(dāng)p非空時(shí)，判斷p-data=76嗎？如果成立，則p所指的結(jié)點(diǎn)就是所要?jiǎng)h除的結(jié)點(diǎn)；此時(shí)，q指示所要?jiǎng)h除的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；否則，繼續(xù)查找；即p和q指針同時(shí)向后移。找到了值為76的結(jié)點(diǎn)：,q,p,刪除p所指的結(jié)點(diǎn)：,刪除之后的鏈表為：,q,p,程序如下: