《動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)》ppt課件

1、第七章 動(dòng)態(tài)數(shù)據(jù)構(gòu)造教學(xué)目的n動(dòng)態(tài)數(shù)據(jù)構(gòu)造的概念n動(dòng)態(tài)懇求和釋放內(nèi)存的方法n鏈表的建立n鏈表結(jié)點(diǎn)的插入和刪除算法7.1 從靜態(tài)數(shù)據(jù)構(gòu)造到動(dòng)態(tài)數(shù)據(jù)構(gòu)造7.2 動(dòng)態(tài)內(nèi)存分配7.3 鏈表7.4 本章小結(jié)7.1 從靜態(tài)數(shù)據(jù)構(gòu)造到動(dòng)態(tài)數(shù)據(jù)構(gòu)造靜態(tài)數(shù)據(jù)構(gòu)造的特點(diǎn)是由系統(tǒng)分配固定大小的存靜態(tài)數(shù)據(jù)構(gòu)造的特點(diǎn)是由系統(tǒng)分配固定大小的存儲空間，以后在程序運(yùn)轉(zhuǎn)的過程中，存儲空間的儲空間，以后在程序運(yùn)轉(zhuǎn)的過程中，存儲空間的位置和容量都不會再改動(dòng)。如數(shù)組、簡單類型位置和容量都不會再改動(dòng)。如數(shù)組、簡單類型(int、float)等。等。實(shí)踐生活中經(jīng)常有這樣的問題，數(shù)據(jù)量的多少是實(shí)踐生活中經(jīng)常有這樣的問題，數(shù)據(jù)量的多少是動(dòng)態(tài)變

2、化的。如何處理？動(dòng)態(tài)變化的。如何處理？動(dòng)態(tài)數(shù)據(jù)構(gòu)造不確定總的數(shù)據(jù)存儲量，而是為現(xiàn)動(dòng)態(tài)數(shù)據(jù)構(gòu)造不確定總的數(shù)據(jù)存儲量，而是為現(xiàn)有的每一個(gè)數(shù)據(jù)元素定義一個(gè)確定的初始大小的有的每一個(gè)數(shù)據(jù)元素定義一個(gè)確定的初始大小的空間，假設(shè)干個(gè)數(shù)據(jù)元素分配假設(shè)干個(gè)同樣大小空間，假設(shè)干個(gè)數(shù)據(jù)元素分配假設(shè)干個(gè)同樣大小的空間；當(dāng)數(shù)據(jù)量發(fā)生變化時(shí)，數(shù)據(jù)存儲空間的的空間；當(dāng)數(shù)據(jù)量發(fā)生變化時(shí)，數(shù)據(jù)存儲空間的大小也發(fā)生變化。假設(shè)數(shù)據(jù)量添加，就重新向系大小也發(fā)生變化。假設(shè)數(shù)據(jù)量添加，就重新向系統(tǒng)懇求新的空間；假設(shè)數(shù)據(jù)量減少，就將現(xiàn)有的統(tǒng)懇求新的空間；假設(shè)數(shù)據(jù)量減少，就將現(xiàn)有的多余空間歸還給系統(tǒng)。多余空間歸還給系統(tǒng)。7.2. 動(dòng)態(tài)內(nèi)存

3、分配vANSI C 中用于動(dòng)態(tài)操作的規(guī)范函數(shù)vC+ 中用于動(dòng)態(tài)操作的運(yùn)算符new和delete不要求vANSI C 中用于動(dòng)態(tài)操作的規(guī)范函數(shù)ANSI C中提供了假設(shè)干個(gè)動(dòng)態(tài)內(nèi)存操作規(guī)范函數(shù)，中提供了假設(shè)干個(gè)動(dòng)態(tài)內(nèi)存操作規(guī)范函數(shù)，它們的稱號分別是它們的稱號分別是malloc、calloc、realloc、free等。這些函數(shù)可以運(yùn)用在任何的等。這些函數(shù)可以運(yùn)用在任何的C環(huán)境中，環(huán)境中，其原型定義在其原型定義在malloc.h文件中。文件中。qmalloc函數(shù)函數(shù)原型：原型：void *malloc(unsigned int size);功能：向系統(tǒng)懇求一個(gè)確定大小功能：向系統(tǒng)懇求一個(gè)確定大小(s

4、ize 個(gè)字節(jié)個(gè)字節(jié))的存儲空間，前往值為一個(gè)指向的存儲空間，前往值為一個(gè)指向void類型的分類型的分配域起始地址的指針值。假設(shè)此函數(shù)操作失敗，配域起始地址的指針值。假設(shè)此函數(shù)操作失敗，前往值為空。前往值為空。運(yùn)用格式：運(yùn)用格式：指針型變量指針型變量=(=(基類型基類型* *)malloc()malloc(需求的存儲空間的字需求的存儲空間的字節(jié)數(shù)節(jié)數(shù)););例例7-17-1：為一個(gè)整數(shù)分配存儲空間，需求的語句為：為一個(gè)整數(shù)分配存儲空間，需求的語句為：在文件的頭部：在文件的頭部：#include #include 在闡明部分：在闡明部分： int int * *p; p; 在程序中：在程序中：p

5、 = (int p = (int * *)malloc(sizeof(int);)malloc(sizeof(int);【例7-1】測試malloc的程序：#include #include #include void main()int *p; p = (int *)malloc(sizeof(int);if (!p) exit( 0 );*p=10;printf(*p=%dn, *p); free(p);qcalloc函數(shù)函數(shù)原型：原型：void *calloc(unsigned int n , unsigned int size);功能：向系統(tǒng)懇求功能：向系統(tǒng)懇求 n 個(gè)大小為個(gè)大小為s

6、ize 個(gè)字節(jié)的延續(xù)個(gè)字節(jié)的延續(xù)存儲空間，前往值為一個(gè)指向存儲空間，前往值為一個(gè)指向void類型的分配域類型的分配域起始地址的指針值。假設(shè)此函數(shù)操作失敗，前往起始地址的指針值。假設(shè)此函數(shù)操作失敗，前往值為空。運(yùn)用此函數(shù)可以為一維數(shù)組開辟一片延值為空。運(yùn)用此函數(shù)可以為一維數(shù)組開辟一片延續(xù)的動(dòng)態(tài)存儲空間。續(xù)的動(dòng)態(tài)存儲空間。運(yùn)用格式：運(yùn)用格式： 指針型變量指針型變量 =(數(shù)組元素類型數(shù)組元素類型 *)calloc(n , 每一個(gè)數(shù)組每一個(gè)數(shù)組元素的存儲空間的字節(jié)數(shù)元素的存儲空間的字節(jié)數(shù))；例例7-2：為一個(gè)有：為一個(gè)有10個(gè)整數(shù)的一維數(shù)組分配存儲空間，個(gè)整數(shù)的一維數(shù)組分配存儲空間，需求的語句為：需求

7、的語句為： 在文件的頭部：在文件的頭部：#include 在闡明部分：在闡明部分： int *p; 在程序中：在程序中：p = (int *)calloc(10 , sizeof(int) ;【例7-2】運(yùn)用calloc函數(shù)程序#include #include #include #define N 10void main() int *p;int x,i; p =(int *)calloc(N, sizeof(int); if(!p) exit(0);for(i=0;iN;i+)scanf(%d,&x); *(p+i) = x; for(i=0;iN;i+)printf(%6d, *

8、(p+i);free(p);scanf(%d,p+i);qrealloc函數(shù)函數(shù)原型：原型：void *realloc( void *p, unsigned int size);功能：向系統(tǒng)重新懇求一個(gè)確定大小的存儲空間，功能：向系統(tǒng)重新懇求一個(gè)確定大小的存儲空間，并將原存儲空間中的數(shù)據(jù)值傳送到新的地址空間并將原存儲空間中的數(shù)據(jù)值傳送到新的地址空間的低端，前往值為一個(gè)指向的低端，前往值為一個(gè)指向void類型的分配域起類型的分配域起始地址的指針值。假設(shè)此函數(shù)操作失敗，前往值始地址的指針值。假設(shè)此函數(shù)操作失敗，前往值為空為空,原存儲空間的數(shù)據(jù)也將喪失。原存儲空間的數(shù)據(jù)也將喪失。運(yùn)用格式：運(yùn)用格式：

9、 指針型變量指針型變量 =(基類型基類型 *)realloc( 原存儲空間的首地原存儲空間的首地址，新的存儲空間的字節(jié)數(shù)址，新的存儲空間的字節(jié)數(shù))；例例7-3：現(xiàn)有一個(gè)為：現(xiàn)有一個(gè)為10個(gè)整數(shù)分配的存儲空間，其首個(gè)整數(shù)分配的存儲空間，其首地址為地址為p; 由于數(shù)據(jù)量的添加，原存儲空間已滿，需求由于數(shù)據(jù)量的添加，原存儲空間已滿，需求擴(kuò)展原空間為擴(kuò)展原空間為20個(gè)整數(shù)的大?。恍枨蟮恼Z句為：個(gè)整數(shù)的大小；需求的語句為： 在文件的頭部：在文件的頭部：#include 在闡明部分：在闡明部分： int *p; 在程序中：在程序中：p=(int *)realloc(p,sizeof(int)*20 );

10、【例7-3】運(yùn)用realloc函數(shù)程序#include #include #include void main()int *p1,*p2; p1 =(int *)malloc(sizeof(int)*10); if(!p1) exit(0) ; p2=(int *)realloc(p1,sizeof(int)*20); if(!p2) exit(0) ; free(p2);#include #include #include void main() int *p; int i; p =(int *)malloc(sizeof(int)*3); / p =(int *)calloc(3,size

11、of(int); if(!p) exit(0) ; for(i=0;i3;i+)scanf(%d,p+i); p=(int *)realloc(p,sizeof(int)*2); if(!p) exit(0) ; for(i=0;i2;i+)printf(%6d, *(p+i);free(p);補(bǔ)充程序 realloc 函數(shù)主要用于當(dāng)原分配空間已被占滿，函數(shù)主要用于當(dāng)原分配空間已被占滿，而新的數(shù)據(jù)又要參與到該空間時(shí)的情況。而新的數(shù)據(jù)又要參與到該空間時(shí)的情況。優(yōu)點(diǎn)是可以自動(dòng)地將原空間的內(nèi)容全部傳送到優(yōu)點(diǎn)是可以自動(dòng)地將原空間的內(nèi)容全部傳送到新空間中，不用程序員再編語句來實(shí)現(xiàn)。新空間中，不用程序員再

12、編語句來實(shí)現(xiàn)。缺陷是一旦新空間懇求失敗，原空間的內(nèi)容也缺陷是一旦新空間懇求失敗，原空間的內(nèi)容也將喪失。對這一點(diǎn)，運(yùn)用時(shí)應(yīng)加以留意。將喪失。對這一點(diǎn)，運(yùn)用時(shí)應(yīng)加以留意。qfree函數(shù)函數(shù)原型：原型：void free (void void free (void * *p);p);功能：釋放由功能：釋放由p p所指的內(nèi)存區(qū)，將一個(gè)存儲空間歸所指的內(nèi)存區(qū)，將一個(gè)存儲空間歸還給系統(tǒng)。還給系統(tǒng)。運(yùn)用格式：運(yùn)用格式：free(free(指針型變量指針型變量); ); 例例7-47-4：將一個(gè)已分配存儲空間釋放，需求的語句：將一個(gè)已分配存儲空間釋放，需求的語句: :在文件的頭部：在文件的頭部：#includ

13、e #include 在闡明部分：在闡明部分： int int * *p; p; 在程序中：在程序中： free( p ) free( p )【例7-4】運(yùn)用free函數(shù)程序#include #include #include main() int *p; p =(int *)malloc(sizeof(int); if(!p) exit(0); free(p); v C+ 中用于動(dòng)態(tài)操作的運(yùn)算符-new和deletenANSI C中，在用malloc、calloc、reallloc等函數(shù)動(dòng)態(tài)懇求內(nèi)存空間都要求程序設(shè)計(jì)者知道應(yīng)開辟空間確實(shí)切大小(用sizeof)，并且前往值的類型需求強(qiáng)迫類型轉(zhuǎn)

14、換。nC+中對此進(jìn)展了改良，為進(jìn)展動(dòng)態(tài)內(nèi)存操作提供了運(yùn)算符new和delete，替代malloc和free。但在C+中依然保管了malloc和free，以便和C兼容。n運(yùn)用運(yùn)算符new和delete程序文件的文件名后綴必需為cpp。qnew 運(yùn)算符運(yùn)算符nnew 是C+中提供的用于開辟一個(gè)動(dòng)態(tài)存儲空間的運(yùn)算符。nnew 運(yùn)算符的普通格式：n變量指針 = new 類型(初值);n假設(shè)懇求勝利，前往指向新對象的指針；假設(shè)前往的指針為空指針，表示動(dòng)態(tài)空間分配失敗。n例如：懇求一個(gè)存放整數(shù)的空間： 語句格式： p = new int；執(zhí)行結(jié)果：開辟了一個(gè)整數(shù)大小的空間，并將該空間的首地址送入指向整型數(shù)

15、據(jù)的指針變量p中。懇求一個(gè)存放字符型數(shù)據(jù)的空間，并為該空間賦初值a： 語句格式： p = new char(a)；執(zhí)行結(jié)果：開辟了一個(gè)字節(jié)大小的空間，并將該空間的首地址送入指向字符型數(shù)據(jù)的指針變量p中。p所指空間中的數(shù)據(jù)值為字符 a 。n懇求一個(gè)存放實(shí)數(shù)的空間：n語句格式： p = new float(1.414)；n執(zhí)行結(jié)果：開辟了一個(gè)實(shí)數(shù)大小的空間，并將該空間的首地址送入指向?qū)嵭蛿?shù)據(jù)的指針變量p中。 p所指空間中的數(shù)據(jù)值為1.414。n懇求一個(gè)存放10個(gè)實(shí)數(shù)的數(shù)組的空間：n語句格式： p = new float10；n執(zhí)行結(jié)果：開辟了一個(gè)10個(gè)實(shí)數(shù)大小的空間，將該空間的首地址送入指向?qū)嵭蛿?shù)

16、據(jù)的指針變量p中。留意：用new 為數(shù)組分配空間不能指定初值。#include #include void main() float *p;int i;p = new float3;if(!p)exit(0);for(i=0;i3;i+)scanf(%f,p+i);for(i=0;i3;i+)printf(%f ,*(p+i);/delete p;補(bǔ)充程序不用加頭文件malloc.hqdelete 運(yùn)算符運(yùn)算符ndelete 運(yùn)算符是C+中提供的實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存釋放功能的運(yùn)算符，類似于規(guī)范庫函數(shù) free。n普通格式為：delete 名字指針；n例如：n釋放一個(gè)存放整數(shù)的空間：n假設(shè) p = ne

17、w int；，那么釋放一個(gè)存放整數(shù)的空間的語句為：delete p;n執(zhí)行結(jié)果：將該整數(shù)空間釋放掉，即將該資源歸還給系統(tǒng)。n釋放一個(gè)存放10個(gè)實(shí)數(shù)的數(shù)組的空間： n假設(shè)： p = new float10；，那么釋放一個(gè)數(shù)組空間的語句為：delete p;n執(zhí)行結(jié)果：將該數(shù)組空間釋放掉，即將該資源歸還給系統(tǒng)。n留意：delete只能用于用new分配的內(nèi)存的釋放。例7-5 懇求一個(gè)構(gòu)造體類型的存儲空間，用來存放相應(yīng)類型的數(shù)據(jù)。處理問題要點(diǎn)：包含相關(guān)的頭文件；定義一個(gè)構(gòu)造體類型；定義構(gòu)造體類型的變量；懇求空間；對指定空間賦值；釋放懇求的空間；【例7-5】程序舉例：#include #include

18、/#include #include typedef struct LNode int data;struct LNode *next; LNode;/typedef float REAL;void main() LNode *p; p= new LNode; if ( !p ) exit(0); p-data=10; p-next=NULL; delete p; struct LNode int data;struct LNode *next;qnew與malloc的一樣點(diǎn)和不同點(diǎn)n一樣點(diǎn)：它們的作用都是在程序的執(zhí)行過程中向系統(tǒng)懇求存儲空間，前往值都是懇求到的存儲空間的首地址。n不同點(diǎn)：nm

19、alloc 是C編譯系統(tǒng)提供的規(guī)范庫函數(shù)，new 是C+系統(tǒng)提供的運(yùn)算符，new的操作效率要高于malloc。nnew不需求運(yùn)用顯式的sizeof函數(shù)就能知道類型的大小，而malloc 需求明確指出所懇求的空間的大小(總的字節(jié)數(shù))。nnew 的前往值是指向名字類型確實(shí)定的指針類型，不需求強(qiáng)迫闡明，而malloc的前往值是一個(gè)指向void類型的指針類型，需求強(qiáng)迫轉(zhuǎn)換成指向詳細(xì)數(shù)據(jù)類型的指針類型。n當(dāng)所懇求的空間是一個(gè)變量所需的空間時(shí)，new 運(yùn)算符還可以為所懇求的空間賦初值，malloc不具有此功能。7.3 鏈鏈 表表n計(jì)算機(jī)處置數(shù)據(jù)需求兩方面的任務(wù)，一方面是對數(shù)據(jù)信息的描畫，另一方面是對數(shù)據(jù)的

20、操作，而操作的方式取決于數(shù)據(jù)的描畫方式，數(shù)據(jù)的描畫方式又取決于數(shù)據(jù)本身固有的內(nèi)在聯(lián)絡(luò)。這里僅引見數(shù)據(jù)之間的線性關(guān)系(線性表)。n線性表是 n 個(gè)數(shù)據(jù)元素的有限序列。各數(shù)據(jù)元素屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。記為：na1，a2，ai，ai+1，an7.3 鏈表v鏈表的定義v鏈表的建立v鏈表結(jié)點(diǎn)的插入v鏈表結(jié)點(diǎn)的刪除v循環(huán)鏈表n線性表中的數(shù)據(jù)元素之間存在嚴(yán)厲的順序關(guān)系，有一個(gè)獨(dú)一的稱為第一個(gè)的元素首元，有獨(dú)一的稱為最后一個(gè)的元素尾元，其它元素都有獨(dú)一的直接后繼元素和獨(dú)一的直接前趨元素。n線性表這種邏輯構(gòu)造在計(jì)算機(jī)內(nèi)表示時(shí)，可以采用鏈?zhǔn)酱鎯?gòu)造，即一個(gè)數(shù)據(jù)元素存放于一個(gè)結(jié)點(diǎn)中，不同的

21、數(shù)據(jù)元素之間的先后順序用結(jié)點(diǎn)的指針域鏈接。一個(gè)結(jié)點(diǎn)就是一個(gè)構(gòu)造體類型的變量。v鏈表的定義鏈表的定義n鏈表是表示具有線性關(guān)系的一組數(shù)據(jù)元素的動(dòng)態(tài)鏈表是表示具有線性關(guān)系的一組數(shù)據(jù)元素的動(dòng)態(tài)構(gòu)造。構(gòu)造。n每個(gè)數(shù)據(jù)元素占據(jù)一個(gè)獨(dú)立懇求的存儲空間，這每個(gè)數(shù)據(jù)元素占據(jù)一個(gè)獨(dú)立懇求的存儲空間，這個(gè)存儲空間通常是一個(gè)構(gòu)造體型變量，主要包括個(gè)存儲空間通常是一個(gè)構(gòu)造體型變量，主要包括兩部分，一部分用來存放數(shù)據(jù)元素的值兩部分，一部分用來存放數(shù)據(jù)元素的值稱為稱為值域，另一部分用來存放一個(gè)指向該構(gòu)造體類型值域，另一部分用來存放一個(gè)指向該構(gòu)造體類型的指針變量值的指針變量值稱為指針域。指針域的作用是稱為指針域。指針域的作用

22、是存放邏輯上排在本結(jié)點(diǎn)后面的結(jié)點(diǎn)的存儲空間的存放邏輯上排在本結(jié)點(diǎn)后面的結(jié)點(diǎn)的存儲空間的首地址。首地址。n數(shù)據(jù)元素結(jié)點(diǎn)的構(gòu)造如下圖：數(shù)據(jù)元素結(jié)點(diǎn)的構(gòu)造如下圖：n單向鏈表和單向循環(huán)鏈表如以下圖所示：單向鏈表和單向循環(huán)鏈表如以下圖所示：單向鏈表單向鏈表a1 an -1an 值域指針域a1 an -1an單向循環(huán)鏈表單向循環(huán)鏈表鏈表結(jié)點(diǎn)的鏈表結(jié)點(diǎn)的 C 語句定義語句定義n首先用構(gòu)造體類型描畫一個(gè)數(shù)據(jù)元素結(jié)首先用構(gòu)造體類型描畫一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，定義一個(gè)結(jié)點(diǎn)類型的語句格式：點(diǎn)，定義一個(gè)結(jié)點(diǎn)類型的語句格式：ntypedef struct LNoden n ElemType data;n struct LNo

23、de *next;n LNode, * LinkList;typedef struct Node ElemType data; struct Node *next; LNode,* LinkList;等價(jià)于等價(jià)于struct Node ElemType data; struct Node *next; ;typedef struct Node LNode;typedef struct Node* LinkList;闡明：闡明：ntypedef 語句定義了一個(gè)構(gòu)造體類型和鏈表類型語句定義了一個(gè)構(gòu)造體類型和鏈表類型(構(gòu)造體指針構(gòu)造體指針類型類型)。nNode 是一個(gè)結(jié)點(diǎn)的類型稱號。它有兩個(gè)成員，一

24、個(gè)稱號為是一個(gè)結(jié)點(diǎn)的類型稱號。它有兩個(gè)成員，一個(gè)稱號為data ，類型為數(shù)據(jù)元素的類型，用來存放一個(gè)數(shù)據(jù)元素的值；，類型為數(shù)據(jù)元素的類型，用來存放一個(gè)數(shù)據(jù)元素的值；另一個(gè)成員稱號為另一個(gè)成員稱號為next，類型為指向本構(gòu)造體類型的指針類型，類型為指向本構(gòu)造體類型的指針類型，用來存放邏輯上排在本結(jié)點(diǎn)后面的結(jié)點(diǎn)的首地址。用來存放邏輯上排在本結(jié)點(diǎn)后面的結(jié)點(diǎn)的首地址。nLNode類型等價(jià)于類型等價(jià)于struct Node類型，也等價(jià)于類型，也等價(jià)于Node類型。類型。nLinkList類型等價(jià)于類型等價(jià)于LNode 的指針類型。的指針類型。nElemType 是數(shù)據(jù)元素的類型的普通性描畫，當(dāng)我們詳細(xì)寫

25、程是數(shù)據(jù)元素的類型的普通性描畫，當(dāng)我們詳細(xì)寫程序時(shí)，應(yīng)該用確定類型稱號來交換，例如，序時(shí)，應(yīng)該用確定類型稱號來交換，例如，int、float 、char等。等。 例：鏈表中的數(shù)據(jù)元素用來存放整數(shù)，定義例：鏈表中的數(shù)據(jù)元素用來存放整數(shù)，定義鏈表的結(jié)點(diǎn)類型的語句格式為：鏈表的結(jié)點(diǎn)類型的語句格式為：typedef struct Node int data; struct Node *next; LNode,*LinkList;n定義一個(gè)結(jié)點(diǎn)類型的變量的語句：定義一個(gè)結(jié)點(diǎn)類型的變量的語句：n struct Node q; n LNode q ; n定義一個(gè)指向結(jié)點(diǎn)類型的指針變量的語句：定義一個(gè)指向結(jié)點(diǎn)

26、類型的指針變量的語句：nstruct Node * p;nLNode* p ;nLinkList L;n訪問結(jié)點(diǎn)變量的各個(gè)成員：訪問結(jié)點(diǎn)變量的各個(gè)成員： nq.data , q.next np-data , p-nextnL-data , L-nextv鏈表的建立鏈表的建立 1. 構(gòu)造一個(gè)空線性鏈表構(gòu)造一個(gè)空線性鏈表 首先，構(gòu)造一個(gè)空的線性鏈表。為了描畫方首先，構(gòu)造一個(gè)空的線性鏈表。為了描畫方便，通常將鏈表的第一個(gè)結(jié)點(diǎn)空置，不存放數(shù)便，通常將鏈表的第一個(gè)結(jié)點(diǎn)空置，不存放數(shù)據(jù)元素，只是作為鏈表的開場標(biāo)志，稱為頭結(jié)據(jù)元素，只是作為鏈表的開場標(biāo)志，稱為頭結(jié)點(diǎn)。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開場存放。點(diǎn)。

27、數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開場存放?？盏木€性表定義為沒有數(shù)據(jù)元素的表。一個(gè)空空的線性表定義為沒有數(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)的鏈表。算法描畫:懇求一個(gè)結(jié)點(diǎn)的空間；將該結(jié)點(diǎn)作為線性鏈表的頭結(jié)點(diǎn)；將該結(jié)點(diǎn)的 next 域置空；程序：程序：/*構(gòu)造一個(gè)空的線性鏈表*/LNode* InitList () LinkList L;/頭結(jié)點(diǎn)指針L = (LNode*) malloc(sizeof(LNode ); /*懇求一結(jié)點(diǎn)

28、空間*/ if ( !L) exit ( 0 );/*懇求不勝利，異常終了程序運(yùn)轉(zhuǎn)*/L-next = NULL;/*懇求勝利，頭結(jié)點(diǎn)的next域置空*/return(L);2 2逆序輸入逆序輸入n n個(gè)數(shù)據(jù)元素，建立帶表頭結(jié)點(diǎn)的單個(gè)數(shù)據(jù)元素，建立帶表頭結(jié)點(diǎn)的單向鏈表向鏈表n如今開場建立一個(gè)非空的線性鏈表。這里所建的如今開場建立一個(gè)非空的線性鏈表。這里所建的鏈表的第一個(gè)結(jié)點(diǎn)都是頭結(jié)點(diǎn)。數(shù)據(jù)元素從鏈表鏈表的第一個(gè)結(jié)點(diǎn)都是頭結(jié)點(diǎn)。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開場存放。的第二個(gè)結(jié)點(diǎn)開場存放。n一個(gè)非空的線性鏈表是除了頭結(jié)點(diǎn)以外至少有一一個(gè)非空的線性鏈表是除了頭結(jié)點(diǎn)以外至少有一個(gè)數(shù)據(jù)元素的鏈表。線性鏈表

29、由假設(shè)干個(gè)數(shù)據(jù)元個(gè)數(shù)據(jù)元素的鏈表。線性鏈表由假設(shè)干個(gè)數(shù)據(jù)元素結(jié)點(diǎn)組成。那么，構(gòu)造一個(gè)非空的線性鏈表的素結(jié)點(diǎn)組成。那么，構(gòu)造一個(gè)非空的線性鏈表的過程就是逐個(gè)建立數(shù)據(jù)元素結(jié)點(diǎn)，并將它們依次過程就是逐個(gè)建立數(shù)據(jù)元素結(jié)點(diǎn)，并將它們依次插入到鏈表中的過程。插入到鏈表中的過程。頭插入，即每次將數(shù)據(jù)元素結(jié)點(diǎn)插入到表頭結(jié)點(diǎn)頭插入，即每次將數(shù)據(jù)元素結(jié)點(diǎn)插入到表頭結(jié)點(diǎn)的之后，第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前。的之后，第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前。插入過程如以下圖所示：插入過程如以下圖所示：初始形狀：初始形狀：插入第一個(gè)結(jié)點(diǎn)之后：插入第一個(gè)結(jié)點(diǎn)之后：an頭結(jié)點(diǎn)n插入第二個(gè)結(jié)點(diǎn)之后：插入第二個(gè)結(jié)點(diǎn)之后：n 插入第三個(gè)結(jié)點(diǎn)之后：插入第

30、三個(gè)結(jié)點(diǎn)之后：n插入最后一個(gè)結(jié)點(diǎn)之后：插入最后一個(gè)結(jié)點(diǎn)之后：an-1an an-1an-2an an-1a1an LNode* CreateList(int n)int i;LNode *p;LinkList L ;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,&p-data);p-next =L-next;L-next =p;return L;

31、程序：頭結(jié)點(diǎn)頭結(jié)點(diǎn)頭插入頭插入v鏈表結(jié)點(diǎn)的插入n將一個(gè)數(shù)據(jù)元素插入到鏈表中，有三種情況：將一個(gè)數(shù)據(jù)元素插入到鏈表中，有三種情況：頭插入，尾插入以及在鏈表中的第頭插入，尾插入以及在鏈表中的第i i個(gè)數(shù)據(jù)元個(gè)數(shù)據(jù)元素的位置處插入。素的位置處插入。n將一個(gè)新元素插入在鏈表的頭結(jié)點(diǎn)的后面，其將一個(gè)新元素插入在鏈表的頭結(jié)點(diǎn)的后面，其它的一切結(jié)點(diǎn)之前稱為頭插入。它的一切結(jié)點(diǎn)之前稱為頭插入。n將一個(gè)新元素插入在鏈表的尾結(jié)點(diǎn)的后面，使將一個(gè)新元素插入在鏈表的尾結(jié)點(diǎn)的后面，使得新插入的結(jié)點(diǎn)成為尾結(jié)點(diǎn)稱為尾插入。得新插入的結(jié)點(diǎn)成為尾結(jié)點(diǎn)稱為尾插入。n將一個(gè)新元素插入在鏈表中的第將一個(gè)新元素插入在鏈表中的第i i個(gè)

32、數(shù)據(jù)元素個(gè)數(shù)據(jù)元素的位置處，即插入在第的位置處，即插入在第i i個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前，個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前，使得新插入的結(jié)點(diǎn)成為鏈表中的第使得新插入的結(jié)點(diǎn)成為鏈表中的第i i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。例：已有鏈表例：已有鏈表L 如下圖如下圖,鏈表中的元素按遞鏈表中的元素按遞增有序陳列：增有序陳列： 其中每個(gè)結(jié)點(diǎn)中存放的值為學(xué)生的考試成果。如其中每個(gè)結(jié)點(diǎn)中存放的值為學(xué)生的考試成果。如今有另外三個(gè)學(xué)生的的成果分別為今有另外三個(gè)學(xué)生的的成果分別為65、82、90。將他們插入到鏈表將他們插入到鏈表L中，要求插入之后鏈表依然中，要求插入之后鏈表依然遞增有序。遞增有序。pLq708085將將6565插入到鏈表插入到鏈表

33、L L中中: :s sp pL q65708085頭插入頭插入將將8282插入到鏈表插入到鏈表L L中中: :s sp pLq6570808285中間插入將將9090插入到鏈表插入到鏈表L L中中: :s sp=p=Lq657080828590尾插入實(shí)現(xiàn)語句：實(shí)現(xiàn)語句：LNode *p,*q, *s;LinkList L; /頭結(jié)點(diǎn)指針q=L; p=L-next;while( p & p-datanext;s=(LNode*)malloc(sizeof(LNode);s-data=e;s-next=p;q-next=s;程序：int ListInsert(LNode *L, int e

34、) LNode *p,*q, *s;if(!L)return 0;q=L;p=L-next ;while(p & p-data next ;s=(LNode *)malloc(sizeof(LNode);if(!s)exit(0);s-data =e;s-next =p;q-next =s;return 1;v鏈表結(jié)點(diǎn)的刪除例：已有鏈表如下圖：刪除鏈表中數(shù)據(jù)元素值為76的結(jié)點(diǎn)。80657690 qpL80657690 qpL80657690 qpL806590 qL程序程序:int ListDelete ( LNode *L, int e ) LNode *q, *p; if ( !L

35、 ) return 0 ; p=L-next ; q=L; while ( p & p-data != e ) q=p; p=p-next; if ( p ) q-next = p-next;free(p); return ( 1 ); else return(0); #include #include #include struct Node int data; struct Node *next;typedef struct Node LNode;typedef struct Node* LinkList;綜合程序綜合程序LNode* CreateList(int n) /創(chuàng)建鏈表

36、創(chuàng)建鏈表int i;LNode *p;LinkList L ;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,&p-data);p-next =L-next;L-next =p;return L;int ListInsert(LNode *L, int e) )/插入元素插入元素 LNode *p,*q, *s;if(!L)return 0;q=L;