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

第七章 動(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.1 ANSI C 中動(dòng)態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù),ANSI C中提供了若干個(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(unsigned int size); 其作用是向系統(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 #include void main() int *p; /*定義一個(gè)指向整型的指針變量*/ int x; p = ( int * )malloc( sizeof( int ) ); if ( !p ) exit( 0 ); p= ,2calloc函數(shù),calloc函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。 原型為： void *calloc(unsigned int n , unsigned int size); 其作用是向系統(tǒng)申請(qǐng) n 個(gè)大小為size 個(gè)字節(jié)的連續(xù)存儲(chǔ)空間，返回值為一個(gè)指向void類(lèi)型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空?？梢詾橐痪S數(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 #include main() int *p; int x; p =(int *)calloc(10, sizeof(int); if(!p) exit(0) ; for(i=0;i10;i+) scanf(“%d”, ,3realloc函數(shù),realloc函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。 原型為： void *realloc( void *p, unsigned int size); 其作用是向系統(tǒng)重新申請(qǐng)一個(gè)確定大小的存儲(chǔ)空間，并將原存儲(chǔ)空間中的數(shù)據(jù)值傳送到新的地址空間的低端，返回值為一個(gè)指向void類(lèi)型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。原存儲(chǔ)空間的數(shù)據(jù)將丟失。,3realloc函數(shù),使用格式： 指針型變量 =(基類(lèi)型*)realloc( 原存儲(chǔ)空間的首地址，新的存儲(chǔ)空間的字節(jié)數(shù))； 例7-3：現(xiàn)有一個(gè)為10個(gè)整數(shù)分配的存儲(chǔ)空間，其首地址為p1; 由于數(shù)據(jù)量的增加，原存儲(chǔ)空間已滿(mǎn)，需要擴(kuò)大原空間為20個(gè)整數(shù)的大??；需要的語(yǔ)句為： 在文件的頭部：#include 在說(shuō)明部分： int *p2; 在程序中： p2 = ( int * )realloc( p1, sizeof( int ) * 20 );,程序舉例：,#include #include #include main() int *p1,*p2; int x; p1 =(int *)malloc(sizeof(int)*10); if(!p1) exit(0) ; p2 =(int *)realloc(p1,sizeof(int)*20); if(!p2) exit(0) ; ,realloc 函數(shù)主要的用于當(dāng)原分配空間已被占滿(mǎn)，而新的數(shù)據(jù)又要加入到該空間時(shí)的狀況。它的優(yōu)點(diǎn)是可以自動(dòng)地將原空間的內(nèi)容全部傳遞到新空間中，不必程序員再編語(yǔ)句來(lái)實(shí)現(xiàn)。缺點(diǎn)是一旦新空間申請(qǐng)失敗，原空間的內(nèi)容也將丟失。對(duì)這一點(diǎn)，使用時(shí)應(yīng)加以注意。,4free函數(shù),free函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中， 原型為： void free (void *p) 其作用是釋放由p所指的內(nèi)存區(qū)，將一個(gè)存儲(chǔ)空間歸還給系統(tǒng)。 使用格式： free(指針型變量); 例7-4：將一個(gè)已分配存儲(chǔ)空間釋放，需要的語(yǔ)句為 在文件的頭部：#include 在說(shuō)明部分： int *p; 在程序中：free( p ),程序舉例：,#include #include #include main() int *p; p =(int *)malloc(sizeof(int); if(!p) exit(0) ; free(p)； ,c+ 中為進(jìn)行動(dòng)態(tài)操作提供的運(yùn)算符new和delete,在軟件的研制過(guò)程中，程序中動(dòng)態(tài)申請(qǐng)內(nèi)存空間和釋放內(nèi)存空間是一件很常見(jiàn)的事，前面一節(jié)中，我們講解了ANSI C 中的辦法。利用標(biāo)準(zhǔn)庫(kù)函數(shù)malloc、calloc、reallloc、free等。但malloc、calloc、reallloc等函數(shù)都要求程序設(shè)計(jì)者知道應(yīng)開(kāi)辟空間的確切大小，返回值的類(lèi)型需要強(qiáng)制類(lèi)型轉(zhuǎn)換。 c+ 中對(duì)此進(jìn)行了改進(jìn)，為進(jìn)行動(dòng)態(tài)內(nèi)存操作提供了運(yùn)算符new和delete，來(lái)代替malloc和free。但在c+中依然保留了malloc和free，以便和C兼容。,1new 運(yùn)算符,new 是c+中提供的用于開(kāi)辟一個(gè)動(dòng)態(tài)存儲(chǔ)空間的運(yùn)算符。 new 運(yùn)算符的一般格式： 變量指針 = new 類(lèi)型(初值)； 例如： (1)申請(qǐng)一個(gè)存放整數(shù)的空間： 語(yǔ)句格式： p = new int； 執(zhí)行結(jié)果：開(kāi)辟了一個(gè)整數(shù)大小的空間，并將該空間的首地址送入指向整型數(shù)據(jù)的指針變量p中。,(2)申請(qǐng)一個(gè)存放字符型數(shù)據(jù)的空間，并為該空間賦初值a： 語(yǔ)句格式： p = new char(a)； 執(zhí)行結(jié)果：開(kāi)辟了一個(gè)字節(jié)大小的空間，并將該空間的首地址送入指向字符型數(shù)據(jù)的指針變量p中。P所指空間中的數(shù)據(jù)值為字符 a 。 (3)申請(qǐng)一個(gè)存放實(shí)數(shù)的空間： 語(yǔ)句格式： p = new float(1.414)； 執(zhí)行結(jié)果：開(kāi)辟了一個(gè)實(shí)數(shù)大小的空間，并將該空間的首地址送入指向?qū)嵭蛿?shù)據(jù)的指針變量p中。并將該空間中賦入初值1.414。,(4)申請(qǐng)一個(gè)存放10個(gè)實(shí)數(shù)的數(shù)組的空間： 語(yǔ)句格式： p = new float10； 執(zhí)行結(jié)果：開(kāi)辟了一個(gè)10個(gè)實(shí)數(shù)大小的空間，將該空間的首地址送入指向?qū)嵭蛿?shù)據(jù)的指針變量p中。注意：用new 為數(shù)組分配空間不能指定初值。,2delete 運(yùn)算符：,delete 運(yùn)算符是c+中的提供的實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存釋放功能的運(yùn)算符，類(lèi)似于標(biāo)準(zhǔn)庫(kù)函數(shù) free。 一般格式為：delete 名字指針；例如： (1)釋放一個(gè)存放整數(shù)的空間： 如果 p = new int；則釋放一個(gè)存放整數(shù)的空間的語(yǔ)句為：delete p; 執(zhí)行結(jié)果：將該整數(shù)空間釋放掉，即將該資源歸還給系統(tǒng)。,2delete 運(yùn)算符：,(2)釋放一個(gè)存放10個(gè)實(shí)數(shù)的數(shù)組的空間： 如果： p = new float10；則釋放一個(gè)數(shù)組空間的語(yǔ)句為：delete p; 執(zhí)行結(jié)果：將該數(shù)組空間釋放掉，即將該資源歸還給系統(tǒng)。,2delete 運(yùn)算符：,new 試圖創(chuàng)建一個(gè)名字類(lèi)型的對(duì)象，向系統(tǒng)申請(qǐng)sizeof(名字)個(gè)字節(jié)大小的空間。新對(duì)象的生存周期始于創(chuàng)建點(diǎn)，直到delete將其釋放或到程序結(jié)束。如果申請(qǐng)成功，返回指向新對(duì)象的指針；若返回的指針為空指針，表示動(dòng)態(tài)空間分配失敗。注意：delete只能用于用new分配的內(nèi)存的釋放。,例7-5申請(qǐng)一個(gè)結(jié)構(gòu)體類(lèi)型的存儲(chǔ)空間，用來(lái)存放相應(yīng)類(lèi)型的數(shù)據(jù)。 解決問(wèn)題要點(diǎn)： 包含相關(guān)的頭文件； 定義一個(gè)結(jié)構(gòu)體類(lèi)型； 定義結(jié)構(gòu)體類(lèi)型的變量； 申請(qǐng)空間； 對(duì)指定空間賦值； 釋放申請(qǐng)的空間；,程序舉例：,#include #include #include #include typedef struct LNode int data; struct LNode *next; LNode;,main() LNode *p; p= new LNode; if ( !p ) exit(0); p-data=10; p-next=NULL; delete p; ,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)，ANSI C 中，按如下方式描述： 首先用結(jié)構(gòu)體類(lèi)型描述一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，定義一個(gè)結(jié)點(diǎn)類(lèi)型的語(yǔ)句格式： typedef struct LNode ElemType data； struct LNode *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ǔ)句格式為： typedef struct LNode int data； struct LNode *next； LNode，*LinkList；,定義一個(gè)指向結(jié)點(diǎn)類(lèi)型的指針類(lèi)型變量的語(yǔ)句： LNode *p ; 3定義一個(gè)鏈表類(lèi)型的指針變量：LinkList L; 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）完整程序（Example 7_6.cpp）:,/*程序名：Example7_6.cpp */ void InitList ( 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)之后：,void CreateList ( LinkList *L， int n ) int i; 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”, ,以上的算法只是建立鏈表的一種方法，它的核心是新的數(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ī)。現(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-data next; 循環(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-dat