C語(yǔ)言動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)(二級(jí)C的內(nèi)容,可參考)

1、第七章第七章 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)1動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)本章開(kāi)始介紹動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，主要介紹鏈表結(jié)構(gòu)本章開(kāi)始介紹動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，主要介紹鏈表結(jié)構(gòu)的建立、在鏈表中查找指定元素、插入一個(gè)新元的建立、在鏈表中查找指定元素、插入一個(gè)新元素、刪除一個(gè)元素等操作。學(xué)完本章內(nèi)容后，要素、刪除一個(gè)元素等操作。學(xué)完本章內(nèi)容后，要求深刻理解動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)的概念，并正確運(yùn)用。求深刻理解動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)的概念，并正確運(yùn)用。27.1 從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) 在此之前，我們涉及到的都是在此之前，我們涉及到的都是靜態(tài)數(shù)據(jù)結(jié)構(gòu)靜態(tài)數(shù)據(jù)結(jié)構(gòu)，像數(shù)組、簡(jiǎn)，像數(shù)組、簡(jiǎn)單類型單類型(int、float

2、)等。靜態(tài)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是由系統(tǒng)分配等。靜態(tài)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是由系統(tǒng)分配固定大小的存儲(chǔ)空間，以后在程序運(yùn)行的過(guò)程中，存儲(chǔ)空固定大小的存儲(chǔ)空間，以后在程序運(yùn)行的過(guò)程中，存儲(chǔ)空間的位置和容量都不會(huì)再改變。而實(shí)際生活中常常有這樣間的位置和容量都不會(huì)再改變。而實(shí)際生活中常常有這樣的問(wèn)題，數(shù)據(jù)量的多少是動(dòng)態(tài)變化的。的問(wèn)題，數(shù)據(jù)量的多少是動(dòng)態(tài)變化的。 例如，圖書館的藏書量，在圖書館初建時(shí)，假設(shè)有例如，圖書館的藏書量，在圖書館初建時(shí)，假設(shè)有10000本，隨著時(shí)間的推移，藏書的數(shù)量必定要增加。有人可能本，隨著時(shí)間的推移，藏書的數(shù)量必定要增加。有人可能會(huì)想，在定義一個(gè)靜態(tài)變量時(shí)，預(yù)留出一部分空間，但這會(huì)想，在定義

3、一個(gè)靜態(tài)變量時(shí)，預(yù)留出一部分空間，但這也會(huì)引起一些問(wèn)題，首先多出的那部分空間不知何時(shí)才能也會(huì)引起一些問(wèn)題，首先多出的那部分空間不知何時(shí)才能使用，在沒(méi)有被使用之前一直被閑置；其次，誰(shuí)又能保證使用，在沒(méi)有被使用之前一直被閑置；其次，誰(shuí)又能保證增加的空間就足夠呢？而且圖書館藏書也有減少的可能。增加的空間就足夠呢？而且圖書館藏書也有減少的可能。37.1 從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) 問(wèn)題的關(guān)鍵問(wèn)題的關(guān)鍵在于，此問(wèn)題的數(shù)據(jù)本身就是變化的，而且是在于，此問(wèn)題的數(shù)據(jù)本身就是變化的，而且是不確定的變化，什么時(shí)候變、怎么變都是未知的。對(duì)這樣不確定的變化，什么時(shí)候變、怎么變都是未知的。

4、對(duì)這樣的問(wèn)題用靜態(tài)存儲(chǔ)結(jié)構(gòu)來(lái)描述和存放顯然捉襟見(jiàn)肘，存在的問(wèn)題用靜態(tài)存儲(chǔ)結(jié)構(gòu)來(lái)描述和存放顯然捉襟見(jiàn)肘，存在隱患。隱患。 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)不確定總的數(shù)據(jù)存儲(chǔ)量，而是為現(xiàn)有的每一不確定總的數(shù)據(jù)存儲(chǔ)量，而是為現(xiàn)有的每一個(gè)數(shù)據(jù)元素定義一個(gè)確定的初始大小的空間，若干個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)元素定義一個(gè)確定的初始大小的空間，若干個(gè)數(shù)據(jù)元素分配若干個(gè)同樣大小的空間；當(dāng)問(wèn)題的數(shù)據(jù)量發(fā)生變?cè)胤峙淙舾蓚€(gè)同樣大小的空間；當(dāng)問(wèn)題的數(shù)據(jù)量發(fā)生變化時(shí)，數(shù)據(jù)的存儲(chǔ)空間的大小也發(fā)生變化。如果數(shù)據(jù)量增化時(shí)，數(shù)據(jù)的存儲(chǔ)空間的大小也發(fā)生變化。如果數(shù)據(jù)量增加，就重新向系統(tǒng)申請(qǐng)新的空間；如果數(shù)據(jù)量減少，就將加，就重新向系統(tǒng)申請(qǐng)新的空間；

5、如果數(shù)據(jù)量減少，就將現(xiàn)有的多余的空間歸還給系統(tǒng)?，F(xiàn)有的多余的空間歸還給系統(tǒng)。47.2. 動(dòng)態(tài)內(nèi)存分配動(dòng)態(tài)內(nèi)存分配 使用計(jì)算機(jī)解決問(wèn)題的所有方法都是通過(guò)使用系統(tǒng)提使用計(jì)算機(jī)解決問(wèn)題的所有方法都是通過(guò)使用系統(tǒng)提供給我們的基本命令或函數(shù)來(lái)實(shí)現(xiàn)的。所以首先讓我供給我們的基本命令或函數(shù)來(lái)實(shí)現(xiàn)的。所以首先讓我們來(lái)看看，們來(lái)看看，c的標(biāo)準(zhǔn)函數(shù)中有哪些是用于動(dòng)態(tài)內(nèi)存分的標(biāo)準(zhǔn)函數(shù)中有哪些是用于動(dòng)態(tài)內(nèi)存分配的，怎樣使用。配的，怎樣使用。 ANSI C 中動(dòng)態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù)中動(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ù)，中提供了若干個(gè)動(dòng)態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù)，它們的名稱分別是它們的名稱分別是ma

6、lloc、calloc、realloc、free等。這些函數(shù)可以使用在任何的等。這些函數(shù)可以使用在任何的C環(huán)境中。環(huán)境中。 c+ 中為進(jìn)行動(dòng)態(tài)操作提供了運(yùn)算符中為進(jìn)行動(dòng)態(tài)操作提供了運(yùn)算符new和和delete51malloc函數(shù)函數(shù) malloc函數(shù)是函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。文件中。 原型為：原型為： void *malloc(unsigned int size); 其作用是向系統(tǒng)申請(qǐng)一個(gè)確定大小其作用是向系統(tǒng)申請(qǐng)一個(gè)確定大小(size 個(gè)字節(jié)個(gè)字節(jié))的存儲(chǔ)空的存儲(chǔ)空間，返回值為一個(gè)指向間，返回值為一個(gè)指向void類型的分配域起始地

7、址的指針類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。值。如果此函數(shù)操作失敗，返回值為空。 使用格式：使用格式：指針型變量指針型變量 =(基類型基類型*)malloc(需要的存儲(chǔ)空間的字節(jié)數(shù)需要的存儲(chǔ)空間的字節(jié)數(shù));61malloc函數(shù)函數(shù) malloc函數(shù)是函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。文件中。 原型為：原型為： void *malloc(unsigned int size); 其作用是向系統(tǒng)申請(qǐng)一個(gè)確定大小其作用是向系統(tǒng)申請(qǐng)一個(gè)確定大小(size 個(gè)字節(jié)個(gè)字節(jié))的存儲(chǔ)空的存儲(chǔ)空間，返回值為一個(gè)指向間，返回值為一個(gè)指向v

8、oid類型的分配域起始地址的指針類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。值。如果此函數(shù)操作失敗，返回值為空。 使用格式：使用格式：指針型變量指針型變量 =(基類型基類型*)malloc(需要的存儲(chǔ)空間的字節(jié)數(shù)需要的存儲(chǔ)空間的字節(jié)數(shù)); 指針有確定的數(shù)據(jù)類型，如果想把其他類型指針有確定的數(shù)據(jù)類型，如果想把其他類型賦給某個(gè)類型指針，編譯器會(huì)發(fā)出警告。為了解賦給某個(gè)類型指針，編譯器會(huì)發(fā)出警告。為了解決這個(gè)問(wèn)題，決這個(gè)問(wèn)題，C語(yǔ)言引用了語(yǔ)言引用了void *類型，即表示類型，即表示malloc函數(shù)的返回值可以指向任何類型。函數(shù)的返回值可以指向任何類型。為什么為什么malloc函數(shù)

9、返回值是函數(shù)返回值是void *而不是其它類型？而不是其它類型？7例例7-1：為一個(gè)整數(shù)申請(qǐng)一個(gè)存儲(chǔ)空間：為一個(gè)整數(shù)申請(qǐng)一個(gè)存儲(chǔ)空間 需要的語(yǔ)句為：需要的語(yǔ)句為： 在文件的頭部：在文件的頭部：#include 在說(shuō)明部分：在說(shuō)明部分： int *p; 在程序中：在程序中：p = ( int * ) malloc ( sizeof ( int ) ) ; 說(shuō)明：說(shuō)明： 動(dòng)態(tài)管理內(nèi)存的標(biāo)準(zhǔn)函數(shù)的說(shuō)明在動(dòng)態(tài)管理內(nèi)存的標(biāo)準(zhǔn)函數(shù)的說(shuō)明在malloc.h中。中。 動(dòng)態(tài)管理內(nèi)存的標(biāo)準(zhǔn)函數(shù)的返回值都是指向動(dòng)態(tài)管理內(nèi)存的標(biāo)準(zhǔn)函數(shù)的返回值都是指向void 類型類型的指針類型。在程序中需要的是指向具體類型的指針變的

10、指針類型。在程序中需要的是指向具體類型的指針變量，應(yīng)該進(jìn)行強(qiáng)制類型轉(zhuǎn)換，使得到的指針為指向確定量，應(yīng)該進(jìn)行強(qiáng)制類型轉(zhuǎn)換，使得到的指針為指向確定類型的指針值。類型的指針值。 sizeof 是是ANSI C的一個(gè)標(biāo)準(zhǔn)函數(shù)，它的作用是返回指的一個(gè)標(biāo)準(zhǔn)函數(shù)，它的作用是返回指定類型的變量在內(nèi)存中所占的空間大小。值為字節(jié)數(shù)。定類型的變量在內(nèi)存中所占的空間大小。值為字節(jié)數(shù)。8測(cè)試測(cè)試malloc的程序舉例：的程序舉例：#include #include #include void main()int *p; /*定義一個(gè)指向整型的指針變量定義一個(gè)指向整型的指針變量*/int x; p = ( int * )

11、malloc( sizeof( int ) );if ( !p ) exit( 0 ); /*判斷分配是否不成功，如果分配不判斷分配是否不成功，如果分配不*/ /*成功，結(jié)束整個(gè)程序的執(zhí)行成功，結(jié)束整個(gè)程序的執(zhí)行*/printf(請(qǐng)輸入一個(gè)整數(shù)值到請(qǐng)輸入一個(gè)整數(shù)值到p=%ld 中中: , p); scanf(%d, p); x=*p; printf(x=%dn, x); 92calloc函數(shù)函數(shù) calloc函數(shù)是函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。文件中。 原型為：原型為：void *calloc(unsigned int n , unsig

12、ned int size); 其作用是向系統(tǒng)申請(qǐng)其作用是向系統(tǒng)申請(qǐng) n 個(gè)大小為個(gè)大小為size 個(gè)字節(jié)的連續(xù)個(gè)字節(jié)的連續(xù)存儲(chǔ)空間，返回值為一個(gè)指向存儲(chǔ)空間，返回值為一個(gè)指向void類型的分配域起始類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。地址的指針值。如果此函數(shù)操作失敗，返回值為空?？梢詾橐痪S數(shù)組開(kāi)辟一片連續(xù)的動(dòng)態(tài)存儲(chǔ)空間?？梢詾橐痪S數(shù)組開(kāi)辟一片連續(xù)的動(dòng)態(tài)存儲(chǔ)空間。10例例7-2：為一個(gè)有：為一個(gè)有10個(gè)整數(shù)的一維數(shù)組分配存?zhèn)€整數(shù)的一維數(shù)組分配存儲(chǔ)空間儲(chǔ)空間使用格式：使用格式： 指針型變量指針型變量 =(數(shù)組元素類型數(shù)組元素類型*)calloc(n , 每一個(gè)數(shù)每一個(gè)數(shù)組

13、元素的存儲(chǔ)空間的字節(jié)數(shù)組元素的存儲(chǔ)空間的字節(jié)數(shù))；需要的語(yǔ)句為：需要的語(yǔ)句為：在文件的頭部：在文件的頭部：#include 在說(shuō)明部分：在說(shuō)明部分： int *p; 在程序中：在程序中：p = (int *)calloc( 10 , sizeof(int) ; 11程序：程序：#include #include #include void main() int *p; int x,i; p =(int *)calloc(10, sizeof(int); if(!p) exit(0) ; printf(p=%ldn, p); for(i=0;i10;i+) scanf(%d,&x); *

14、(p+i) = x; for(i=0;i10;i+) if(i%5=0) printf(n); printf(the address of p%d=%ld%6dn, i, p+i,*(p+i); 12將該問(wèn)題作以下修改：不申請(qǐng)空間，看結(jié)果如何？13程序：程序：#include #include #include void main() int *p; int x,i; /*p =(int *)calloc(10, sizeof(int); */* if(!p) exit(0) ; */ printf(p=%ldn, p); for(i=0;i10;i+) scanf(%d,&x); *

15、(p+i) = x; for(i=0;i10;i+) if(i%5=0) printf(n); printf(the address of p%d=%ld%6dn, i,&pi,*(p+i); 143realloc函數(shù)函數(shù) realloc函數(shù)是函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。文件中。 原型為：原型為： void *realloc( void *p, unsigned int size); 其作用是向系統(tǒng)重新申請(qǐng)一個(gè)確定大小的存儲(chǔ)空間，其作用是向系統(tǒng)重新申請(qǐng)一個(gè)確定大小的存儲(chǔ)空間，并將原存儲(chǔ)空間中的數(shù)據(jù)值傳送到新的地址空間的低并將原存

16、儲(chǔ)空間中的數(shù)據(jù)值傳送到新的地址空間的低端，返回值為一個(gè)指向端，返回值為一個(gè)指向void類型的分配域起始地址的類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。原存儲(chǔ)指針值。如果此函數(shù)操作失敗，返回值為空。原存儲(chǔ)空間的數(shù)據(jù)將丟失。空間的數(shù)據(jù)將丟失。153realloc函數(shù)函數(shù)使用格式：使用格式： 指針型變量指針型變量 =(基類型基類型*)realloc( 原存儲(chǔ)空間的首原存儲(chǔ)空間的首地址，新的存儲(chǔ)空間的字節(jié)數(shù)地址，新的存儲(chǔ)空間的字節(jié)數(shù))； realloc 函數(shù)主要的用于當(dāng)原分配空間已被占滿，函數(shù)主要的用于當(dāng)原分配空間已被占滿，而新的數(shù)據(jù)又要加入到該空間時(shí)的狀況。它的優(yōu)而新的數(shù)據(jù)又要加

17、入到該空間時(shí)的狀況。它的優(yōu)點(diǎn)是可以自動(dòng)地將原空間的內(nèi)容全部傳遞到新空點(diǎn)是可以自動(dòng)地將原空間的內(nèi)容全部傳遞到新空間中，不必程序員再編語(yǔ)句來(lái)實(shí)現(xiàn)。缺點(diǎn)是一旦間中，不必程序員再編語(yǔ)句來(lái)實(shí)現(xiàn)。缺點(diǎn)是一旦新空間申請(qǐng)失敗，原空間的內(nèi)容也將丟失。對(duì)這新空間申請(qǐng)失敗，原空間的內(nèi)容也將丟失。對(duì)這一點(diǎn)，使用時(shí)應(yīng)加以注意。一點(diǎn)，使用時(shí)應(yīng)加以注意。16例例7-3：現(xiàn)有一個(gè)為：現(xiàn)有一個(gè)為10個(gè)整數(shù)分配的存儲(chǔ)空間，個(gè)整數(shù)分配的存儲(chǔ)空間，其首地址為其首地址為p1; 由于數(shù)據(jù)量的增加，原存儲(chǔ)空由于數(shù)據(jù)量的增加，原存儲(chǔ)空間已滿，需要擴(kuò)大原空間為間已滿，需要擴(kuò)大原空間為20個(gè)整數(shù)的大小；個(gè)整數(shù)的大小；需要的語(yǔ)句為：需要的語(yǔ)句為：

18、 在文件的頭部：在文件的頭部：#include 在說(shuō)明部分：在說(shuō)明部分： int *p2; 在程序中：在程序中： p2 = ( int * )realloc( p1, sizeof( int ) * 20 ); 17程序：程序：#include #include #include void main() int *p1,*p2; int i; p1 =(int *)malloc(sizeof(int)*10); if(!p1) exit(0) ; for(i=0;i10;i+) scanf(%d, p1+i); printf(p1=%u, p1中的值：中的值：, p1); for(i=0;i1

19、0;i+) printf(%4d, *(p1+i); printf(n); p2 =(int *)realloc(p1,sizeof(int)*20); if(!p2) exit(0) ; printf(p2=%u, p2中的值：中的值：, p2); for(i=0;i20;i+) printf(%4d, *(p2+i); printf(n);184free函數(shù)函數(shù)原型為原型為：void free (void *p)其作用是釋放由其作用是釋放由p所指的內(nèi)存區(qū)，將一個(gè)存儲(chǔ)空間所指的內(nèi)存區(qū)，將一個(gè)存儲(chǔ)空間歸還給系統(tǒng)。歸還給系統(tǒng)。使用格式：使用格式：free(指針型變量指針型變量); 例例7-4：將

20、一個(gè)已分配存儲(chǔ)空間釋放：將一個(gè)已分配存儲(chǔ)空間釋放:需要的語(yǔ)句為需要的語(yǔ)句為 在文件的頭部：在文件的頭部：#include 在說(shuō)明部分：在說(shuō)明部分： int *p; 在程序中：在程序中：free( p )19程序舉例：程序舉例：#include #include #include void main() int *p1; int i; p1 =(int *)malloc(sizeof(int)*10); if(!p1) exit(0) ; for(i=0;i10;i+) scanf(%d, p1+i); printf(p1=%u, p1中的值：中的值：, p1); for(i=0;i10;i+)

21、 printf(%4d, *(p1+i); printf(n); free(p1); printf(free 之后之后 p1=%u, p1中的值：中的值：, p1); for(i=0;idata , p-next1.說(shuō)明：本章的所有程序都是基于以上類型定義。說(shuō)明：本章的所有程序都是基于以上類型定義。28鏈表的建立鏈表的建立 n構(gòu)造一個(gè)空線性鏈表構(gòu)造一個(gè)空線性鏈表 L ：為了描述方便，通常將鏈表的第一個(gè)結(jié)點(diǎn)空置，為了描述方便，通常將鏈表的第一個(gè)結(jié)點(diǎn)空置，不存放數(shù)據(jù)元素，只是作為鏈表的開(kāi)始標(biāo)志，不存放數(shù)據(jù)元素，只是作為鏈表的開(kāi)始標(biāo)志，稱為稱為頭結(jié)點(diǎn)頭結(jié)點(diǎn)。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開(kāi)。數(shù)據(jù)元素從鏈

22、表的第二個(gè)結(jié)點(diǎn)開(kāi)始存放。始存放?？盏木€性表定義為沒(méi)有數(shù)據(jù)元素的表。一個(gè)空空的線性表定義為沒(méi)有數(shù)據(jù)元素的表。一個(gè)空的線性鏈表就規(guī)定為，只有一個(gè)頭結(jié)點(diǎn)的鏈表。的線性鏈表就規(guī)定為，只有一個(gè)頭結(jié)點(diǎn)的鏈表。所以，構(gòu)造一個(gè)空的線性鏈表就是建立只有一所以，構(gòu)造一個(gè)空的線性鏈表就是建立只有一個(gè)頭結(jié)點(diǎn)的鏈表。個(gè)頭結(jié)點(diǎn)的鏈表。29 算法描述算法描述:申請(qǐng)一個(gè)結(jié)點(diǎn)的空間；申請(qǐng)一個(gè)結(jié)點(diǎn)的空間；將該結(jié)點(diǎn)作為線性鏈表的頭結(jié)點(diǎn)；將該結(jié)點(diǎn)作為線性鏈表的頭結(jié)點(diǎn)；將該結(jié)點(diǎn)的將該結(jié)點(diǎn)的 next 域置空；域置空； 完整程序完整程序void InitList ( LinkList L ) L=(LNode*)malloc(sizeo

23、f(LNode); if ( !L) exit ( 0 ); L-next = NULL;302逆序輸入逆序輸入 n 個(gè)數(shù)據(jù)元素，建立帶表頭結(jié)點(diǎn)個(gè)數(shù)據(jù)元素，建立帶表頭結(jié)點(diǎn)的單線性鏈表的單線性鏈表 L現(xiàn)在開(kāi)始建立一個(gè)非空的線性鏈表。我們這里所現(xiàn)在開(kāi)始建立一個(gè)非空的線性鏈表。我們這里所建的鏈表的第一個(gè)結(jié)點(diǎn)都是頭結(jié)點(diǎn)。數(shù)據(jù)元素從建的鏈表的第一個(gè)結(jié)點(diǎn)都是頭結(jié)點(diǎn)。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開(kāi)始存放。鏈表的第二個(gè)結(jié)點(diǎn)開(kāi)始存放。一個(gè)非空的線性鏈表是除了頭結(jié)點(diǎn)以外至少有一一個(gè)非空的線性鏈表是除了頭結(jié)點(diǎn)以外至少有一個(gè)數(shù)據(jù)元素的鏈表。線性鏈表由若干個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素的鏈表。線性鏈表由若干個(gè)數(shù)據(jù)元素結(jié)點(diǎn)組成。那么

24、，構(gòu)造一個(gè)非空的線性鏈表的過(guò)結(jié)點(diǎn)組成。那么，構(gòu)造一個(gè)非空的線性鏈表的過(guò)程就是逐個(gè)建立數(shù)據(jù)元素結(jié)點(diǎn)，并將它們依次插程就是逐個(gè)建立數(shù)據(jù)元素結(jié)點(diǎn)，并將它們依次插入到鏈表中的過(guò)程。入到鏈表中的過(guò)程。31所謂頭插入，即每次將數(shù)據(jù)元素結(jié)點(diǎn)插入到表頭結(jié)所謂頭插入，即每次將數(shù)據(jù)元素結(jié)點(diǎn)插入到表頭結(jié)點(diǎn)的之后，第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前。點(diǎn)的之后，第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前。插入過(guò)程如圖插入過(guò)程如圖7-3所示：所示：插入第一個(gè)結(jié)點(diǎn)之后：插入第一個(gè)結(jié)點(diǎn)之后：an32 插入第二個(gè)結(jié)點(diǎn)之后：插入第二個(gè)結(jié)點(diǎn)之后：n插入第三個(gè)結(jié)點(diǎn)之后：n插入最后一個(gè)結(jié)點(diǎn)之后：an-1anan-1an-2anan-1a1an 33完整程序：完整程序

25、：#include #include #include typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;34void CreateList ( LinkList L, int n ) int i; LNode *p; printf(現(xiàn)在建立鏈表：現(xiàn)在建立鏈表：n); for ( i = n;i 0;i-) printf(請(qǐng)輸入第請(qǐng)輸入第%d個(gè)結(jié)點(diǎn)的元素值：個(gè)結(jié)點(diǎn)的元素值：n,i); p=(LNode*)malloc(sizeof(LNode); if ( !p ) exit (0); scanf(%d, &

26、p-data); p-next = L-next ; L-next = p ; 35 void main() LNode *L,*p; int n; printf(請(qǐng)輸入鏈表中的元素個(gè)數(shù)：請(qǐng)輸入鏈表中的元素個(gè)數(shù)：); scanf(%d,&n); printf(現(xiàn)在建立鏈表的頭結(jié)點(diǎn)：現(xiàn)在建立鏈表的頭結(jié)點(diǎn)：n); L = (LNode*) malloc( sizeof ( LNode ) ); if ( !L ) exit ( 0); L-next = NULL; printf(現(xiàn)在開(kāi)始建立鏈表：現(xiàn)在開(kāi)始建立鏈表：n); CreateList(L,n); printf(鏈表建立結(jié)束，開(kāi)始輸

27、出鏈表中的元素值！鏈表建立結(jié)束，開(kāi)始輸出鏈表中的元素值！n); for(p=L;p;p=p-next) if(p=L) printf(頭結(jié)點(diǎn)的地址值：頭結(jié)點(diǎn)的地址值：%u , p); else printf(當(dāng)前結(jié)點(diǎn)的地址值：當(dāng)前結(jié)點(diǎn)的地址值：%u , p); printf(tp-data=%d n, p-data); printf(n); 36以上的算法只是建立鏈表的一種方法，它以上的算法只是建立鏈表的一種方法，它的核心是新的數(shù)據(jù)元素結(jié)點(diǎn)插在鏈表的第的核心是新的數(shù)據(jù)元素結(jié)點(diǎn)插在鏈表的第一個(gè)數(shù)據(jù)元素的位置；我們也可以將新建一個(gè)數(shù)據(jù)元素的位置；我們也可以將新建立的數(shù)據(jù)元素結(jié)點(diǎn)每次都插在鏈表的尾部

28、，立的數(shù)據(jù)元素結(jié)點(diǎn)每次都插在鏈表的尾部，大家可以思考一下，以大家可以思考一下，以尾插入尾插入的方式建立的方式建立鏈表，程序怎樣編寫？鏈表，程序怎樣編寫？37鏈表結(jié)點(diǎn)的插入鏈表結(jié)點(diǎn)的插入將一個(gè)數(shù)據(jù)元素插入到鏈表中，有三種情況：將一個(gè)數(shù)據(jù)元素插入到鏈表中，有三種情況：頭插入頭插入：將一個(gè)新元素插入在鏈表的頭結(jié)點(diǎn)的后：將一個(gè)新元素插入在鏈表的頭結(jié)點(diǎn)的后面，其它的所有結(jié)點(diǎn)之前稱為頭插入。面，其它的所有結(jié)點(diǎn)之前稱為頭插入。尾插入尾插入：將一個(gè)新元素插入在鏈表的尾結(jié)點(diǎn)的后：將一個(gè)新元素插入在鏈表的尾結(jié)點(diǎn)的后面，使得新插入的結(jié)點(diǎn)成為尾結(jié)點(diǎn)稱為尾插入。面，使得新插入的結(jié)點(diǎn)成為尾結(jié)點(diǎn)稱為尾插入。在鏈表中的第在鏈

29、表中的第i個(gè)數(shù)據(jù)元素的位置處插入個(gè)數(shù)據(jù)元素的位置處插入：將一個(gè)：將一個(gè)新元素插入在鏈表中的第新元素插入在鏈表中的第i個(gè)數(shù)據(jù)元素的位置處，個(gè)數(shù)據(jù)元素的位置處，即插入在第即插入在第i個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前，使得新插入的個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前，使得新插入的結(jié)點(diǎn)成為鏈表中的第結(jié)點(diǎn)成為鏈表中的第i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。38例例7-8：已有鏈表：已有鏈表L 如圖所示如圖所示,鏈表中的元素按鏈表中的元素按遞增有序排列：遞增有序排列： 其中每個(gè)結(jié)點(diǎn)中存放的值為學(xué)生的考試成績(jī)?，F(xiàn)其中每個(gè)結(jié)點(diǎn)中存放的值為學(xué)生的考試成績(jī)?，F(xiàn)在有另外三個(gè)學(xué)生的的成績(jī)分別為在有另外三個(gè)學(xué)生的的成績(jī)分別為65、82、90。將他們插入到鏈表將他們插入到

30、鏈表L中，要求插入之后鏈表依然中，要求插入之后鏈表依然遞增有序。遞增有序。807085圖圖7.4 鏈表的插入過(guò)程鏈表的插入過(guò)程L39圖圖7.5 頭插入過(guò)程頭插入過(guò)程 將將 65 插入到鏈表插入到鏈表L中中: 為為65申請(qǐng)一個(gè)結(jié)點(diǎn)空間，首地址放入申請(qǐng)一個(gè)結(jié)點(diǎn)空間，首地址放入s中；中；807085 p p65s sq將將s插入到鏈表中：插入到鏈表中： 設(shè)設(shè)p=L-next，L Lp-datanext=s;s-next=p;40實(shí)現(xiàn)語(yǔ)句：實(shí)現(xiàn)語(yǔ)句： p=L-next; s=(LNode*)malloc(sizeof(LNode); s-data=x; s-next=p; L-next=s; 插入之后

31、的鏈表狀態(tài)：插入之后的鏈表狀態(tài)：807085 65L L41將將82 插入到鏈表插入到鏈表L中中:插入的過(guò)程：插入的過(guò)程：首先應(yīng)找到首先應(yīng)找到82 應(yīng)在的位置：應(yīng)在的位置： 82應(yīng)該插在兩個(gè)結(jié)應(yīng)該插在兩個(gè)結(jié)點(diǎn)之間，點(diǎn)之間，82前面結(jié)點(diǎn)的前面結(jié)點(diǎn)的data域值小于域值小于82；82后后面結(jié)點(diǎn)的面結(jié)點(diǎn)的data域值大于等于域值大于等于82；如圖所示：；如圖所示：L: 65807085 8242實(shí)現(xiàn)語(yǔ)句：實(shí)現(xiàn)語(yǔ)句：q=L; p=L-next;while( p & p-datadata ) q=p; p=p-next; 6580708285 插入之后的鏈表：插入之后的鏈表：43插入過(guò)程：插入過(guò)

32、程：q=L; 6580708285 while( p & p-datadata ) q=p; p=p-next; p=L-next;sLqppqpqpqq-next=s; s-next=p;85 p44將將90 插入到鏈表插入到鏈表L中中: 顯然，顯然，90應(yīng)插到鏈表的尾部，即：插到鏈應(yīng)插到鏈表的尾部，即：插到鏈表的最后一個(gè)結(jié)點(diǎn)的后面。表的最后一個(gè)結(jié)點(diǎn)的后面。 插入的過(guò)程：插入的過(guò)程： 首先找到插入的位置：設(shè)首先找到插入的位置：設(shè)p=L-next，當(dāng)，當(dāng)p非空并且非空并且 p-data next; 循環(huán)一定以循環(huán)一定以p為空結(jié)束。為空結(jié)束。 將新結(jié)點(diǎn)將新結(jié)點(diǎn)90插在插在q的后面，插入過(guò)

33、程如下：的后面，插入過(guò)程如下：45找到找到90結(jié)點(diǎn)應(yīng)該的位置之后：結(jié)點(diǎn)應(yīng)該的位置之后：L:6580709085 p=NULLqss-next=NULLq-next=s 90 46實(shí)現(xiàn)語(yǔ)句：實(shí)現(xiàn)語(yǔ)句：x=90; p=L-next; s=(LNode*)malloc(sizeof(LNode); s-data=x; while( p & p-data next;q-next=s; s-next=p; 47用一個(gè)函數(shù)來(lái)實(shí)現(xiàn)，程序如下：用一個(gè)函數(shù)來(lái)實(shí)現(xiàn)，程序如下：void ListInsert(LNode *L,int e ) LNode *s,*q, *p; if ( !(*L) ) exi

34、t(0); s = ( LNode* ) malloc ( sizeof ( LNode ); if ( !s ) exit ( 0 ); s-data = e; p=L-next ; q=L;while ( p & p-datanext; s-next = p;q-next = s; 48鏈表結(jié)點(diǎn)的刪除鏈表結(jié)點(diǎn)的刪除例例7-9：已有鏈表：已有鏈表L 如圖所示：如圖所示：80657690 49刪除鏈表中數(shù)據(jù)元素值為刪除鏈表中數(shù)據(jù)元素值為76首先查找值為首先查找值為76的結(jié)點(diǎn)：的結(jié)點(diǎn)：設(shè)設(shè)p=L-next，q=L;80657690 qpL:50當(dāng)當(dāng)p非空時(shí)，判斷非空時(shí)，判斷p-data=

35、76嗎？如果成立，則嗎？如果成立，則p所指的結(jié)點(diǎn)就是所要?jiǎng)h除的結(jié)點(diǎn)；此時(shí)，所指的結(jié)點(diǎn)就是所要?jiǎng)h除的結(jié)點(diǎn)；此時(shí)，q指示指示所要?jiǎng)h除的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；否則，繼續(xù)查找；所要?jiǎng)h除的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；否則，繼續(xù)查找；即即p和和q指針同時(shí)向后移。找到了值為指針同時(shí)向后移。找到了值為76的結(jié)點(diǎn)：的結(jié)點(diǎn)：80657690 qp51刪除刪除p所指的結(jié)點(diǎn)：所指的結(jié)點(diǎn)：刪除之后的鏈表為：刪除之后的鏈表為：65807690 qp q-next=p-next; 658090qfree(p);52程序如下程序如下:int Listdelete ( LNode *L, int *e ) LNode *q, *p; if (

36、!L ) return 0; p=L-next ; q=L; while ( p & p-data != (*e) ) q=p; p=p-next; if ( p ) q-next = p-next; (*e)=p-data; free(p); return ( 1 ); else return(0); 537.4 小小 結(jié)結(jié)本章介紹了線性鏈表的定義和建立算法，又介紹本章介紹了線性鏈表的定義和建立算法，又介紹了插入一個(gè)結(jié)點(diǎn)、刪除一個(gè)結(jié)點(diǎn)等算法的實(shí)現(xiàn)。了插入一個(gè)結(jié)點(diǎn)、刪除一個(gè)結(jié)點(diǎn)等算法的實(shí)現(xiàn)。通過(guò)這一章的學(xué)習(xí)，我們初步了解了動(dòng)態(tài)數(shù)據(jù)結(jié)通過(guò)這一章的學(xué)習(xí)，我們初步了解了動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和使

37、用方式。構(gòu)的特點(diǎn)和使用方式。還有許多的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，如堆棧、隊(duì)列、樹、還有許多的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，如堆棧、隊(duì)列、樹、圖等。它們都被廣泛的應(yīng)用于計(jì)算機(jī)系統(tǒng)中，在圖等。它們都被廣泛的應(yīng)用于計(jì)算機(jī)系統(tǒng)中，在計(jì)算的系統(tǒng)和應(yīng)用軟件中起著非常重要的作用。計(jì)算的系統(tǒng)和應(yīng)用軟件中起著非常重要的作用。動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的更詳細(xì)內(nèi)容將在后續(xù)課程動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的更詳細(xì)內(nèi)容將在后續(xù)課程數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)中講述。中講述。54關(guān)于鏈表的完整程序：#include #include #include typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;55建立鏈

38、表：void CreateList ( LinkList L, int n ) int i; LNode *p; printf(現(xiàn)在建立鏈表：現(xiàn)在建立鏈表：n); for( i=n; i0;i-) printf(請(qǐng)輸入第請(qǐng)輸入第%d個(gè)結(jié)點(diǎn)的元素值：個(gè)結(jié)點(diǎn)的元素值：n,i); p=(LNode*)malloc(sizeof(LNode); if (!p) exit (0); scanf(%d, &p-data); p-next = L-next ; L-next = p ; 56插入結(jié)點(diǎn)：void ListInsert(LNode *L, int e ) LNode *s,*q, *p; if ( !L ) exit(0); s = ( LNode* ) malloc ( size