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

會計學(xué)1C語言動態(tài)數(shù)據(jù)結(jié)構(gòu)態(tài)數(shù)據(jù)結(jié)構(gòu)本章開始介紹動態(tài)數(shù)據(jù)結(jié)構(gòu)，主要介紹鏈表結(jié)構(gòu)的建立、在鏈表中查找指定元素、插入一個新元素、刪除一個元素等操作。學(xué)完本章內(nèi)容后，要求深刻理解動態(tài)存儲結(jié)構(gòu)的概念，并正確運(yùn)用。第1頁/共62頁7.1從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu)在此之前，我們涉及到的都是靜態(tài)數(shù)據(jù)結(jié)構(gòu)，像數(shù)組、簡單類型(int、float)等。靜態(tài)數(shù)據(jù)結(jié)構(gòu)的特點是由系統(tǒng)分配固定大小的存儲空間，以后在程序運(yùn)行的過程中，存儲空間的位置和容量都不會再改變。而實際生活中常常有這樣的問題，數(shù)據(jù)量的多少是動態(tài)變化的。第2頁/共62頁7.1從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu)例如，圖書館的藏書量，在圖書館初建時，假設(shè)有10000本，隨著時間的推移，藏書的數(shù)量必定要增加。有人可能會想，在定義一個靜態(tài)變量時，預(yù)留出一部分空間，但這也會引起一些問題，首先多出的那部分空間不知何時才能使用，在沒有被使用之前一直被閑置；其次，誰又能保證增加的空間就足夠呢？第3頁/共62頁7.1從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu)問題的關(guān)鍵在于，此問題的數(shù)據(jù)本身就是變化的，而且是不確定的變化，什么時候變、怎么變都是未知的。對這樣的問題用靜態(tài)存儲結(jié)構(gòu)來描述和存放顯然捉襟見肘，存在隱患。動態(tài)數(shù)據(jù)結(jié)構(gòu)不確定總的數(shù)據(jù)存儲量，而是為現(xiàn)有的每一個數(shù)據(jù)元素定義一個確定的初始大小的空間，若干個數(shù)據(jù)元素分配若干個同樣大小的空間；當(dāng)問題的數(shù)據(jù)量發(fā)生變化時，數(shù)據(jù)的存儲空間的大小也發(fā)生變化。如果數(shù)據(jù)量增加，就重新向系統(tǒng)申請新的空間；如果數(shù)據(jù)量減少，就將現(xiàn)有的多余的空間歸還給系統(tǒng)。第4頁/共62頁7.2.動態(tài)內(nèi)存分配使用計算機(jī)解決問題的所有方法都是通過使用系統(tǒng)提供給我們的基本命令或函數(shù)來實現(xiàn)的。所以首先讓我們來看看，c的標(biāo)準(zhǔn)函數(shù)中有哪些是用于動態(tài)內(nèi)存分配的，怎樣使用。第5頁/共62頁7.2.1ANSIC中動態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù)ANSIC中提供了若干個動態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù)，它們的名稱分別是malloc、calloc、realloc、free等。這些函數(shù)可以使用在任何的C環(huán)境中。第6頁/共62頁1．malloc函數(shù)malloc函數(shù)是C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。原型為：void*malloc(unsignedintsize);其作用是向系統(tǒng)申請一個確定大小(size個字節(jié))的存儲空間，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。第7頁/共62頁1．malloc函數(shù)使用格式：指針型變量=(基類型*)malloc(需要的存儲空間的字節(jié)數(shù));例7-1：為一個整數(shù)分配存儲空間，需要的語句為：在文件的頭部：#include<malloc.h>

在說明部分：int*p;

在程序中：p=(int*)malloc(sizeof(int));第8頁/共62頁測試malloc的程序舉例：#include<malloc.h>#include<stdio.h>#include<stdlib.h>voidmain(){int*p;/*定義一個指向整型的指針變量*/intx;p=(int*)malloc(sizeof(int));if(!p)exit(0);p=&x;scanf(“%d”,p);printf(“x=%d”,x);

}第9頁/共62頁2．calloc函數(shù)calloc函數(shù)是C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。原型為：void*calloc(unsignedintn,unsignedintsize);其作用是向系統(tǒng)申請n個大小為size個字節(jié)的連續(xù)存儲空間，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。可以為一維數(shù)組開辟一片連續(xù)的動態(tài)存儲空間。第10頁/共62頁2．calloc函數(shù)使用格式：指針型變量=(數(shù)組元素類型*)calloc(n,每一個數(shù)組元素的存儲空間的字節(jié)數(shù))；例7-2：為一個有10個整數(shù)的一維數(shù)組分配存儲空間，需要的語句為：在文件的頭部：#include<malloc.h>

在說明部分：int*p;

在程序中：p=(int*)calloc(10,sizeof(int));

第11頁/共62頁使用calloc函數(shù)程序舉例：#include<malloc.h> #include<stdio.h> #include<stdlib.h> main(){int*p;intx;p=(int*)calloc(10,sizeof(int));if(!p)exit(0);for(i=0;i<10;i++) {scanf(“%d”,&x);*(p+i)=x;} for(i=0;i<10;i++) printf(“%6d”,*(p+i));}第12頁/共62頁3．realloc函數(shù)realloc函數(shù)是C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。原型為：void*realloc(void*p,unsignedintsize);其作用是向系統(tǒng)重新申請一個確定大小的存儲空間，并將原存儲空間中的數(shù)據(jù)值傳送到新的地址空間的低端，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。原存儲空間的數(shù)據(jù)將丟失。第13頁/共62頁3．realloc函數(shù)使用格式：指針型變量=(基類型*)realloc(原存儲空間的首地址，新的存儲空間的字節(jié)數(shù))；例7-3：現(xiàn)有一個為10個整數(shù)分配的存儲空間，其首地址為p1;由于數(shù)據(jù)量的增加，原存儲空間已滿，需要擴(kuò)大原空間為20個整數(shù)的大?。恍枰恼Z句為：在文件的頭部：#include<malloc.h>

在說明部分：int*p2;

在程序中：p2=(int*)realloc(p1,sizeof(int)*20);第14頁/共62頁程序舉例：

#include<malloc.h>#include<stdio.h>#include<stdlib.h>main(){int*p1,*p2;intx;p1=(int*)malloc(sizeof(int)*10);if(!p1)exit(0);p2=(int*)realloc(p1,sizeof(int)*20);if(!p2)exit(0);}第15頁/共62頁realloc函數(shù)主要的用于當(dāng)原分配空間已被占滿，而新的數(shù)據(jù)又要加入到該空間時的狀況。它的優(yōu)點是可以自動地將原空間的內(nèi)容全部傳遞到新空間中，不必程序員再編語句來實現(xiàn)。缺點是一旦新空間申請失敗，原空間的內(nèi)容也將丟失。對這一點，使用時應(yīng)加以注意。第16頁/共62頁4．free函數(shù)

free函數(shù)是

C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中，原型為：voidfree(void*p)其作用是釋放由p所指的內(nèi)存區(qū)，將一個存儲空間歸還給系統(tǒng)。使用格式：

free(指針型變量);例7-4：將一個已分配存儲空間釋放，需要的語句為在文件的頭部：#include<malloc.h>

在說明部分：int*p;

在程序中：free(p)第17頁/共62頁程序舉例：#include<malloc.h>#include<stdio.h>#include<stdlib.h>main(){int*p;p=(int*)malloc(sizeof(int));if(!p)exit(0);free(p)；}第18頁/共62頁c++中為進(jìn)行動態(tài)操作提供的運(yùn)算符——new和delete在軟件的研制過程中，程序中動態(tài)申請內(nèi)存空間和釋放內(nèi)存空間是一件很常見的事，前面一節(jié)中，我們講解了ANSIC中的辦法。利用標(biāo)準(zhǔn)庫函數(shù)malloc、calloc、reallloc、free等。但malloc、calloc、reallloc等函數(shù)都要求程序設(shè)計者知道應(yīng)開辟空間的確切大小，返回值的類型需要強(qiáng)制類型轉(zhuǎn)換。c++中對此進(jìn)行了改進(jìn)，為進(jìn)行動態(tài)內(nèi)存操作提供了運(yùn)算符new和delete，來代替malloc和free。但在c++中依然保留了malloc和free，以便和C兼容。第19頁/共62頁1．new運(yùn)算符new是c++中提供的用于開辟一個動態(tài)存儲空間的運(yùn)算符。new運(yùn)算符的一般格式：變量指針=new類型(初值)；例如：(1)申請一個存放整數(shù)的空間：語句格式：p=newint；執(zhí)行結(jié)果：開辟了一個整數(shù)大小的空間，并將該空間的首地址送入指向整型數(shù)據(jù)的指針變量p中。第20頁/共62頁(2)申請一個存放字符型數(shù)據(jù)的空間，并為該空間賦初值‘a(chǎn)’：語句格式：p=newchar(‘a(chǎn)’)；執(zhí)行結(jié)果：開辟了一個字節(jié)大小的空間，并將該空間的首地址送入指向字符型數(shù)據(jù)的指針變量p中。P所指空間中的數(shù)據(jù)值為字符’a’。(3)申請一個存放實數(shù)的空間：語句格式：p=newfloat(1.414)；執(zhí)行結(jié)果：開辟了一個實數(shù)大小的空間，并將該空間的首地址送入指向?qū)嵭蛿?shù)據(jù)的指針變量p中。并將該空間中賦入初值1.414。第21頁/共62頁(4)申請一個存放10個實數(shù)的數(shù)組的空間：語句格式：p=newfloat[10]；執(zhí)行結(jié)果：開辟了一個10個實數(shù)大小的空間，將該空間的首地址送入指向?qū)嵭蛿?shù)據(jù)的指針變量p中。注意：用new為數(shù)組分配空間不能指定初值。第22頁/共62頁2．delete運(yùn)算符：delete運(yùn)算符是c++中的提供的實現(xiàn)動態(tài)內(nèi)存釋放功能的運(yùn)算符，類似于標(biāo)準(zhǔn)庫函數(shù)free。一般格式為：delete名字指針；例如：(1)釋放一個存放整數(shù)的空間：如果p=newint；則釋放一個存放整數(shù)的空間的語句為：deletep;執(zhí)行結(jié)果：將該整數(shù)空間釋放掉，即將該資源歸還給系統(tǒng)。第23頁/共62頁2．delete運(yùn)算符：(2)釋放一個存放10個實數(shù)的數(shù)組的空間：如果：p=newfloat[10]；則釋放一個數(shù)組空間的語句為：delete[]p;執(zhí)行結(jié)果：將該數(shù)組空間釋放掉，即將該資源歸還給系統(tǒng)。第24頁/共62頁2．delete運(yùn)算符：new試圖創(chuàng)建一個名字類型的對象，向系統(tǒng)申請sizeof(名字)個字節(jié)大小的空間。新對象的生存周期始于創(chuàng)建點，直到delete將其釋放或到程序結(jié)束。如果申請成功，返回指向新對象的指針；若返回的指針為空指針，表示動態(tài)空間分配失敗。注意：delete只能用于用new分配的內(nèi)存的釋放。第25頁/共62頁例7-5申請一個結(jié)構(gòu)體類型的存儲空間，用來存放相應(yīng)類型的數(shù)據(jù)。解決問題要點：包含相關(guān)的頭文件；定義一個結(jié)構(gòu)體類型；定義結(jié)構(gòu)體類型的變量；申請空間；對指定空間賦值；釋放申請的空間；第26頁/共62頁程序舉例：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>typedefstructLNode{intdata;structLNode*next;}LNode;main(){LNode*p;p=newLNode;if(!p)exit(0);p->data=10;p->next=NULL; deletep;}第27頁/共62頁new與malloc的相同點是他們的作用都是在程序的執(zhí)行過程中向系統(tǒng)申請存儲空間，返回值都是申請到的存儲空間的首地址，不同點是，malloc是c編譯系統(tǒng)提供的標(biāo)準(zhǔn)庫函數(shù)，new是c++系統(tǒng)提供的運(yùn)算符，new的操作效率要高于malloc；new不需要使用顯式的sizeof函數(shù)就能知道名字的大小，而malloc需要明確指出所申請的空間的大小(總的字節(jié)數(shù))；new的返回值是指向名字類型的確定的指針類型，不需要強(qiáng)制說明，而malloc的返回值是一個指向void類型的指針類型，需要強(qiáng)制轉(zhuǎn)換成指向具體數(shù)據(jù)類型的指針類型。當(dāng)所申請的空間是一個變量所需的空間時，new運(yùn)算符還可以為所申請的空間賦初值，malloc不具有此功能。第28頁/共62頁7.3鏈表計算機(jī)處理數(shù)據(jù)需要兩方面的工作，一方面是對數(shù)據(jù)信息的描述，另一方面是對數(shù)據(jù)的操作，而操作的方式取決于數(shù)據(jù)的描述方式，數(shù)據(jù)的描述方式又取決于數(shù)據(jù)本身固有的內(nèi)在聯(lián)系。這里僅介紹數(shù)據(jù)之間的線性關(guān)系。 對于圖書館的藏書這類數(shù)據(jù)信息可以用一種稱為線性表的動態(tài)數(shù)據(jù)結(jié)構(gòu)來描述。簡單的說，線性表是n個數(shù)據(jù)元素的有限序列。各數(shù)據(jù)元素屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。記為：（a1，a2，…，ai，ai+1，…，an）第29頁/共62頁線性表中的數(shù)據(jù)元素之間存在嚴(yán)格的順序關(guān)系，有一個唯一的稱為第一個的元素（首元），有唯一的稱為最后一個的元素（尾元），其它元素都有唯一的直接后繼元素和唯一的直接前趨元素。 線性表這種邏輯結(jié)構(gòu)在計算機(jī)內(nèi)表示時，可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，即一個數(shù)據(jù)元素存放于一個結(jié)點中，不同的數(shù)據(jù)元素之間的先后順序用結(jié)點的指針域鏈接。一個結(jié)點就是一個結(jié)構(gòu)體類型的變量。第30頁/共62頁7.3.1鏈表的定義鏈表是表示具有線性關(guān)系的一組數(shù)據(jù)元素的動態(tài)結(jié)構(gòu)。每一個數(shù)據(jù)元素占據(jù)一個獨立申請的存儲空間，這個存儲空間通常是一個結(jié)構(gòu)體型變量，主要包括兩部分，一部分用來存放數(shù)據(jù)元素的值——稱為值域，另一部分用來存放一個指向該結(jié)構(gòu)體類型的指針變量值——稱為指針域。指針域的作用是存放邏輯上排在本結(jié)點后面的結(jié)點的存儲空間的首地址。數(shù)據(jù)元素結(jié)點的結(jié)構(gòu)如圖所示：值域指針域第31頁/共62頁若干個結(jié)點首尾相連按照其邏輯順序鏈接成一排，稱為線性鏈表。單向鏈表如下圖所示：a1a2……an-1an^圖7.2單向鏈表第32頁/共62頁1.鏈表結(jié)點的C語句定義對于鏈表這種數(shù)據(jù)結(jié)構(gòu)，ANSIC中，按如下方式描述：首先用結(jié)構(gòu)體類型描述一個數(shù)據(jù)元素結(jié)點，定義一個結(jié)點類型的語句格式：

typedefstructLNode{ ElemTypedata；structLNode*next；

}LNode，*LinkList；第33頁/共62頁其中：typedef語句定義了一個結(jié)構(gòu)體類型和鏈表類型LNode是一個結(jié)點的類型名稱。它有兩個成員，一個名稱為data，類型為數(shù)據(jù)元素的類型，用來存放一個數(shù)據(jù)元素的值；另一個成員名稱為next，類型為指向本結(jié)構(gòu)體類型的指針類型，用來存放邏輯上排在本結(jié)點后面的結(jié)點的首地址。LinkList是指向LNode類型的指針類型。ElemType是數(shù)據(jù)元素的類型的一般性描述，當(dāng)我們具體寫程序時，應(yīng)該用確定類型名稱來替換，例如，int、float、char等。第34頁/共62頁例7-6：鏈表中的數(shù)據(jù)元素用來存放整數(shù)，定義鏈表的結(jié)點類型的語句格式為：

typedefstructLNode{ intdata；

structLNode*next；

}LNode，*LinkList；第35頁/共62頁定義一個指向結(jié)點類型的指針類型變量的語句：LNode*p;3．定義一個鏈表類型的指針變量：LinkListL;4．訪問結(jié)點變量p的各個成員：p->data,p->next說明：本章的所有程序都是基于以上類型定義。 第36頁/共62頁7.3.2鏈表的建立1.構(gòu)造一個空線性鏈表L首先，構(gòu)造一個空的線性鏈表。為了描述方便，通常將鏈表的第一個結(jié)點空置，不存放數(shù)據(jù)元素，只是作為鏈表的開始標(biāo)志，稱為頭結(jié)點。數(shù)據(jù)元素從鏈表的第二個結(jié)點開始存放。空的線性表定義為沒有數(shù)據(jù)元素的表。一個空的線性鏈表就規(guī)定為，只有一個頭結(jié)點的鏈表。所以，構(gòu)造一個空的線性鏈表就是建立只有一個頭結(jié)點的鏈表。第37頁/共62頁（1）算法描述:申請一個結(jié)點的空間；將該結(jié)點作為線性鏈表的頭結(jié)點；將該結(jié)點的next域置空；第38頁/共62頁（2）完整程序（Example7_6.cpp）:

/*程序名：Example7_6.cpp*/ voidInitList(LinkList*L){ /*構(gòu)造一個空的線性鏈表*/ (*L)=((LNode*)malloc(sizeof(LNode))；/*申請一個結(jié)點空間*/ if(!（*L）)exit(0)；/*申請不成功，異常結(jié)束程序運(yùn)行*/

（*L）->next=NULL；/*申請成功，頭結(jié)點的next域置空*/return(1)；

}第39頁/共62頁2．逆序輸入n個數(shù)據(jù)元素，建立帶表頭結(jié)點的單線性鏈表L現(xiàn)在開始建立一個非空的線性鏈表。我們這里所建的鏈表的第一個結(jié)點都是頭結(jié)點。數(shù)據(jù)元素從鏈表的第二個結(jié)點開始存放。一個非空的線性鏈表是除了頭結(jié)點以外至少有一個數(shù)據(jù)元素的鏈表。線性鏈表由若干個數(shù)據(jù)元素結(jié)點組成。那么，構(gòu)造一個非空的線性鏈表的過程就是逐個建立數(shù)據(jù)元素結(jié)點，并將它們依次插入到鏈表中的過程。第40頁/共62頁所謂頭插入，即每次將數(shù)據(jù)元素結(jié)點插入到表頭結(jié)點的之后，第一個數(shù)據(jù)元素結(jié)點之前。

插入過程如圖7-3所示：∧初始狀態(tài)：插入第一個結(jié)點之后：an∧第41頁/共62頁插入第二個結(jié)點之后：插入第三個結(jié)點之后：插入最后一個結(jié)點之后：an-1an∧an-1an-2an∧an-1a1an∧……第42頁/共62頁voidCreateList(LinkList*L，intn){ inti; LNode*P;(*L)=(LNode*)malloc(sizeof(LNode))；if(!(*L))exit(0);(*L)->next=NULL；for(i=n；i>0；i--){p=(LNode*)malloc(sizeof(LNode))；if(!p))exit(0);scanf(“%d”,&p->data);p->next=(*L)->next;(*L)->next=p;}return(1);}第43頁/共62頁以上的算法只是建立鏈表的一種方法，它的核心是新的數(shù)據(jù)元素結(jié)點插在鏈表的第一個數(shù)據(jù)元素的位置；我們也可以將新建立的數(shù)據(jù)元素結(jié)點每次都插在鏈表的尾部，大家可以思考一下，以尾插入的方式建立鏈表，程序怎樣編寫？第44頁/共62頁7.3.3鏈表結(jié)點的插入將一個數(shù)據(jù)元素插入到鏈表中，有三種情況：頭插入，尾插入以及在鏈表中的第i個數(shù)據(jù)元素的位置處插入。將一個新元素插入在鏈表的頭結(jié)點的后面，其它的所有結(jié)點之前稱為頭插入。將一個新元素插入在鏈表的尾結(jié)點的后面，使得新插入的結(jié)點成為尾結(jié)點稱為尾插入。將一個新元素插入在鏈表中的第i個數(shù)據(jù)元素的位置處，即插入在第i個數(shù)據(jù)元素結(jié)點之前，使得新插入的結(jié)點成為鏈表中的第i個結(jié)點。下面我們詳細(xì)介紹每一種插入的算法實現(xiàn)。第45頁/共62頁例7-8：已有鏈表L如圖所示,鏈表中的元素按遞增有序排列：圖7.4鏈表的插入過程其中每個結(jié)點中存放的值為學(xué)生的考試成績。現(xiàn)在有另外三個學(xué)生的的成績分別為65、82、90。將他們插入到鏈表L中，要求插入之后鏈表依然遞增有序。807085∧第46頁/共62頁圖7.5頭插入過程首先將65插入到鏈表L中:插入的過程：設(shè)p=L->next，因為p非空，判斷p->data>65,所以，65應(yīng)該插在L的后面，70結(jié)點的前面，插入之后的鏈表為：L:

65807085∧sp65s第47頁/共62頁實現(xiàn)語句：

p=L->next;s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=p;L->next=s;第48頁/共62頁將82插入到鏈表L中:插入的過程：首先應(yīng)找到82應(yīng)在的位置：82應(yīng)該插在兩個結(jié)點之間，82前面結(jié)點的data域值小于82；82后面結(jié)點的data域值大于等于82；如圖所示：L:65807085∧82第49頁/共62頁實現(xiàn)語句：q=*L;p=(*L)->next;while(p&&p->data<x) {q=p;p=p->next;}第50頁/共62頁將90插入到鏈表L中:

顯然，90應(yīng)插到鏈表的尾部，即：插到鏈表的最后一個結(jié)點的后面。插入的過程：首先找到插入的位置：設(shè)p=L->next，當(dāng)p非空并且p->data<90，做：q=p;p=p->next;循環(huán)一定以p為空結(jié)束。將新結(jié)點90插在q的后面，插入之后的鏈表為：第51頁/共62頁L:6580708590∧第52頁/共62頁實現(xiàn)語句：x=90;p=L->next;s=(LNode*)malloc(sizeof(LNode));s->data=x;while(p&&p->data<x){q=p;p=p->next; }q->next=s;s->next=p;}第53頁/共62頁用一個程序來實現(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;