C語言第9章2動態(tài)數(shù)據(jù)結(jié)構(gòu)(二級C的內(nèi)容,可參考).ppt

1,1,第九章 結(jié)構(gòu)體和指針,2,結(jié)構(gòu)體概述 結(jié)構(gòu)體類型和結(jié)構(gòu)體變量的定義 結(jié)構(gòu)體類型變量的引用 結(jié)構(gòu)體與數(shù)組 結(jié)構(gòu)體和指針 動態(tài)鏈表,主要內(nèi)容,動態(tài)數(shù)據(jù)結(jié)構(gòu),本節(jié)開始介紹動態(tài)數(shù)據(jù)結(jié)構(gòu)，主要介紹鏈表結(jié)構(gòu)的建立、在鏈表中查找指定元素、插入一個新元素、刪除一個元素等操作。 學(xué)完本節(jié)內(nèi)容后，要求深刻理解動態(tài)存儲結(jié)構(gòu)的概念，并正確運用。,3,6 動態(tài)鏈表,6.1 從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu) 6.2 動態(tài)內(nèi)存分配（4個函數(shù)） 6.3 鏈 表 6.4 小 結(jié),6.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)分配固定大小的存儲空間，以后在程序運行的過程中，存儲空間的位置和容量都不會再改變。 而實際生活中常常有這樣的問題，數(shù)據(jù)量的多少是動態(tài)變化的。,5,6.1 從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu),例如，圖書館的藏書量，在圖書館初建時，假設(shè)有10000本，隨著時間的推移，藏書的數(shù)量必定要增加。 有人可能會想，在定義一個靜態(tài)變量時，預(yù)留出一部分空間，但這也會引起一些問題， 首先多出的那部分空間不知何時才能使用，在沒有被使用之前一直被閑置； 其次，誰又能保證增加的空間就足夠呢？而且圖書館藏書也有減少的可能。,6,6.1 從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu),問題的關(guān)鍵在于，此問題的數(shù)據(jù)本身就是變化的，而且是不確定的變化，什么時候變、怎么變都是未知的。 對這樣的問題用靜態(tài)存儲結(jié)構(gòu)來描述和存放顯然捉襟見肘，存在隱患。,7,6.1 從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(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)。,8,6.2 動態(tài)內(nèi)存分配,使用計算機解決問題的所有方法都是通過使用系統(tǒng)提供給我們的基本命令或函數(shù)來實現(xiàn)的。所以首先讓我們來看看，c的標(biāo)準(zhǔn)函數(shù)中有哪些是用于動態(tài)內(nèi)存分配的，怎樣使用。 ANSI C 中動態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù) ANSI C中提供了若干個動態(tài)內(nèi)存操作標(biāo)準(zhǔn)函數(shù)，它們的名稱分別是malloc、calloc、realloc、free等。這些函數(shù)可以使用在任何的C環(huán)境中。 c+ 中為進行動態(tài)操作提供了運算符new和delete,9,1malloc函數(shù),malloc函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。 原型定義在malloc.h文件中。 原型為：void *malloc(unsigned int size); 其作用是向系統(tǒng)申請一個確定大小(size 個字節(jié))的存儲空間，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。 使用格式： 指針型變量 =(基類型*)malloc(需要的存儲空間的字節(jié)數(shù));,10,1malloc函數(shù),malloc函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。 原型為： void *malloc(unsigned int size); 其作用是向系統(tǒng)申請一個確定大小(size 個字節(jié))的存儲空間，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。 使用格式： 指針型變量 =(基類型*)malloc(需要的存儲空間的字節(jié)數(shù));,指針有確定的數(shù)據(jù)類型，如果想把其他類型賦給某個類型指針，編譯器會發(fā)出警告。為了解決這個問題，C語言引用了void *類型，即表示malloc函數(shù)的返回值可以指向任何類型。,為什么malloc函數(shù)返回值是void *而不是其它類型？,11,例：為一個整數(shù)申請一個存儲空間,需要的語句為： 在文件的頭部：#include 在說明部分： int *p; 在程序中：p = ( int * ) malloc ( sizeof ( int ) ) ; 說明： 動態(tài)管理內(nèi)存的標(biāo)準(zhǔn)函數(shù)的說明在malloc.h中。 動態(tài)管理內(nèi)存的標(biāo)準(zhǔn)函數(shù)的返回值都是指向void 類型的指針類型。在程序中需要的是指向具體類型的指針變量，應(yīng)該進行強制類型轉(zhuǎn)換，使得到的指針為指向確定類型的指針值。,12,測試malloc的程序舉例：,13,測試malloc的程序舉例：,14,2calloc函數(shù),calloc函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。 原型定義在malloc.h文件中。 原型為： void *calloc(unsigned int n , unsigned int size); 其作用是向系統(tǒng)申請 n 個大小為size 個字節(jié)的連續(xù)存儲空間，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空?？梢詾橐痪S數(shù)組開辟一片連續(xù)的動態(tài)存儲空間。,15,例：為一個有10個整數(shù)的一維數(shù)組分配存儲空間,使用格式： 指針型變量 =(數(shù)組元素類型*)calloc(n , 每一個數(shù)組元素的存儲空間的字節(jié)數(shù))； 需要的語句為： 在文件的頭部：#include 在說明部分： int *p; 在程序中：p = (int *)calloc( 10 , sizeof(int) ;,16,程序：,#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“, ,17,程序：,#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“, ,18,將該問題作以下修改：不申請空間，看結(jié)果如何？,19,程序：,#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“, ,20,3realloc函數(shù),realloc函數(shù)是 C的標(biāo)準(zhǔn)函數(shù)之一。原型定義在malloc.h文件中。 原型為：void *realloc( void *p, unsigned int size); 其作用是向系統(tǒng)重新申請一個確定大小的存儲空間，并將原存儲空間中的數(shù)據(jù)值傳送到新的地址空間的低端，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。原存儲空間的數(shù)據(jù)將丟失。,21,3realloc函數(shù),使用格式： 指針型變量 =(基類型*)realloc( 原存儲空間的首地址，新的存儲空間的字節(jié)數(shù))； realloc 函數(shù)主要的用于當(dāng)原分配空間已被占滿，而新的數(shù)據(jù)又要加入到該空間時的狀況。 優(yōu)點是可以自動地將原空間的內(nèi)容全部傳遞到新空間中，不必程序員再編語句來實現(xiàn)。 缺點是一旦新空間申請失敗，原空間的內(nèi)容也將丟失。對這一點，使用時應(yīng)加以注意。,22,例：現(xiàn)有一個為10個整數(shù)分配的存儲空間，其首地址為p1; 由于數(shù)據(jù)量的增加，原存儲空間已滿，需要擴大原空間為20個整數(shù)的大??；,需要的語句為： 在文件的頭部：#include 在說明部分： int *p2; 在程序中： p2 = ( int * )realloc( p1, sizeof( int ) * 20 );,23,程序：,#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;i10;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“); ,24,4free函數(shù),原型為：void free (void *p) 其作用是釋放由p所指的內(nèi)存區(qū)，將一個存儲空間歸還給系統(tǒng)。 使用格式：free(指針型變量); 例7-4：將一個已分配存儲空間釋放: 需要的語句為 在文件的頭部：#include 在說明部分： int *p; 在程序中：free( p ),25,程序舉例：,#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+) printf(“%4d“, *(p1+i); printf(“n“); free(p1); printf(“free 之后 p1=%u, p1中的值：“, p1); for(i=0;i10;i+) printf(“%4d“, *(p1+i); printf(“n“); ,28,6.3 鏈 表,計算機處理數(shù)據(jù)需要兩方面的工作，一方面是對數(shù)據(jù)信息的描述，另一方面是對數(shù)據(jù)的操作，而操作的方式取決于數(shù)據(jù)的描述方式，數(shù)據(jù)的描述方式又取決于數(shù)據(jù)本身固有的內(nèi)在聯(lián)系。這里僅介紹數(shù)據(jù)之間的線性關(guān)系。 數(shù)據(jù)本身固有的內(nèi)在聯(lián)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。有很多種。譬如，線性關(guān)系、層次關(guān)系、網(wǎng)狀（圖）關(guān)系等，我們這里僅介紹數(shù)據(jù)之間的線性關(guān)系。,29,6.3 鏈 表,對于圖書館的藏書這類數(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）,30,線性表中的數(shù)據(jù)元素之間存在嚴(yán)格的順序關(guān)系，有一個唯一的稱為第一個的元素（首元），有唯一的稱為最后一個的元素（尾元），其它元素都有唯一的直接后繼元素和唯一的直接前趨元素。 線性表這種邏輯結(jié)構(gòu)在計算機內(nèi)表示時，可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，即一個數(shù)據(jù)元素存放于一個結(jié)點中，不同的數(shù)據(jù)元素之間的先后順序用結(jié)點的指針域鏈接。一個結(jié)點就是一個結(jié)構(gòu)體類型的變量。,31,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)如圖所示：,32,若干個結(jié)點首尾相連按照其邏輯順序鏈接成一排，稱為線性鏈表。 單向鏈表如下圖所示：,單向鏈表,33,2 鏈表結(jié)點的 C 語句定義,首先用結(jié)構(gòu)體類型描述一個數(shù)據(jù)元素結(jié)點，定義一個結(jié)點類型的語句格式： typedef struct LNode ElemType data； struct LNode *next； LNode，*LinkList；,34,typedef struct LNode ElemType data； struct LNode *next； LNode，*LinkList；,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等。,typedef 語句定義了兩個數(shù)據(jù)類型結(jié)構(gòu)體類型（LNode）和鏈表類型（LinkList） ；,35,例：鏈表中的數(shù)據(jù)元素用來存放整數(shù)，定義鏈表的結(jié)點類型的語句格式為：,typedef struct LNode int data； struct LNode *next； LNode，*LinkList； 定義一個指向結(jié)點類型的指針類型變量的語句： LNode *p ; 定義一個鏈表類型的指針變量：LinkList L; 訪問結(jié)點變量 p 的各個成員： p-data , p-next 說明：本章的所有程序都是基于以上類型定義。,36,3 鏈表的建立,構(gòu)造一個空線性鏈表 L ： 為了描述方便，通常將鏈表的第一個結(jié)點空置，不存放數(shù)據(jù)元素，只是作為鏈表的開始標(biāo)志，稱為頭結(jié)點。數(shù)據(jù)元素從鏈表的第二個結(jié)點開始存放。 空的線性表定義為沒有數(shù)據(jù)元素的表。 一個空的線性鏈表就規(guī)定為，只有一個頭結(jié)點的鏈表。 所以，構(gòu)造一個空的線性鏈表就是建立只有一個頭結(jié)點的鏈表。,37,算法描述: 申請一個結(jié)點的空間； 將該結(jié)點作為線性鏈表的頭結(jié)點； 將該結(jié)點的 next 域置空； 完整程序 void InitList ( LinkList L ) L=(LNode*)malloc(sizeof(LNode); if ( !L) exit ( 0 ); L-next = NULL; ,38,4逆序輸入 n 個數(shù)據(jù)元素，建立帶表頭結(jié)點的單線性鏈表 L,現(xiàn)在開始建立一個非空的線性鏈表。我們這里所建的鏈表的第一個結(jié)點都是頭結(jié)點。數(shù)據(jù)元素從鏈表的第二個結(jié)點開始存放。 一個非空的線性鏈表是除了頭結(jié)點以外至少有一個數(shù)據(jù)元素的鏈表。線性鏈表由若干個數(shù)據(jù)元素結(jié)點組成。那么，構(gòu)造一個非空的線性鏈表的過程就是逐個建立數(shù)據(jù)元素結(jié)點，并將它們依次插入到鏈表中的過程。,39,所謂頭插入，即每次將數(shù)據(jù)元素結(jié)點插入到表頭結(jié)點的之后，第一個數(shù)據(jù)元素結(jié)點之前。 插入過程如圖所示：,初始狀態(tài)：,插入第一個結(jié)點之后：,40,插入第二個結(jié)點之后：,插入第三個結(jié)點之后：,插入最后一個結(jié)點之后：,41,完整程序：,#include #include #include typedef struct LNode int data; struct LNode *next; LNode,*LinkList;,42,void CreateList ( LinkList L, int n ) int i; LNode *p; printf(“現(xiàn)在建立鏈表：n“); for ( i = n;i 0;i-) printf(“請輸入第%d個結(jié)點的元素值：n“,i); p=(LNode*)malloc(sizeof(LNode); if ( !p ) exit (0); scanf(“%d“, ,43,void main() LNode *L,*p; int n; printf(“請輸入鏈表中的元素個數(shù)：“); scanf(“%d“, ,44,以上的算法只是建立鏈表的一種方法，它的核心是新的數(shù)據(jù)元素結(jié)點插在鏈表的第一個數(shù)據(jù)元素的位置； 我們也可以將新建立的數(shù)據(jù)元素結(jié)點每次都插在鏈表的尾部。 大家可以思考一下，以尾插入的方式建立鏈表，程序怎樣編寫？,48,5 鏈表結(jié)點的插入,將一個數(shù)據(jù)元素插入到鏈表中，有三種情況： 頭插入：將一個新元素插入在鏈表的頭結(jié)點的后面，其它的所有結(jié)點之前稱為頭插入。 尾插入：將一個新元素插入在鏈表的尾結(jié)點的后面，使得新插入的結(jié)點成為尾結(jié)點稱為尾插入。 在鏈表中的第i個數(shù)據(jù)元素的位置處插入：將一個新元素插入在鏈表中的第i個數(shù)據(jù)元素的位置處，即插入在第i個數(shù)據(jù)元素結(jié)點之前，使得新插入的結(jié)點成為鏈表中的第i個結(jié)點。,49,例：已有鏈表L 如圖所示,鏈表中的元素按遞增有序排列：,其中每個結(jié)點中存放的值為學(xué)生的考試成績?，F(xiàn)在有另外三個學(xué)生的的成績分別為65、82、90。將他們插入到鏈表L中，要求插入之后鏈表依然遞增有序。,鏈表的插入過程,L,50,頭插入過程,將 65 插入到鏈表L中: 為65申請一個結(jié)點空間，首地址放入s中；,p,將s插入到鏈表中：,設(shè)p=L-next，,L,p-data65嗎？,不小于！,65應(yīng)在p結(jié)點之前。,即s插在L結(jié)點之后。,L-next=s;,s-next=p;,51,實現(xiàn)語句：,p=L-next; s=(LNode*)malloc(sizeof(LNode); s-data=x; s-next=p; L-next=s; 插入之后的鏈表狀態(tài)：,L,52,將82 插入到鏈表L中:,插入的過程： 首先應(yīng)找到82 應(yīng)在的位置： 82應(yīng)該插在兩個結(jié)點之間，82前面結(jié)點的data域值小于82；82后面結(jié)點的data域值大于等于82；如圖所示： L:,53,實現(xiàn)語句：,q=L; p=L-next; while( p ,插入之后的鏈表：,54,插入過程：,q=L;,while( p ,p=L-next;,s,L,q,p,p,q,p,q,p,q,q-next=s; s-next=p;,p,55,將90 插入到鏈表L中:,顯然，90應(yīng)插到鏈表的尾部，即：插到鏈表的最后一個結(jié)點的后面。 插入的過程： 首先找到插入的位置：設(shè)p=L-next，當(dāng)p非空并且 p-data next; 循環(huán)一定以p為空結(jié)束。 將新結(jié)點90插在q的后面，插入過程如下：,56,找到90結(jié)點應(yīng)該的位置之后：,L:,p=NULL,q,s,s-next=NULL,q-next=s,57,實現(xiàn)語句：,x=90; p=L-next; s=(LNode*)malloc(sizeof(LNode); s-data=x; while( p ,58,用一個函數(shù)來實現(xiàn)，程序如下：,void ListInsert(LNode *L,int e ) LNode *s,*q, *p; if ( !(*L) ) exit(0); s = ( LNode* ) malloc ( sizeof ( LNode ); if ( !s ) exit ( 0 ); s-data = e; p=L-next ; q=L;,while ( p ,59,6 鏈表結(jié)點的刪除,例：已有鏈表L 如圖所示：,60,刪除鏈表中數(shù)據(jù)元素值為76,首先查找值為76的結(jié)點： 設(shè)p=L-next，q=L;,q,p,L:,61,當(dāng)p非空時，判斷p-data=76嗎？如果成立，則p所指的結(jié)點就是所要刪除的結(jié)點；此時，q指示所要刪除的結(jié)點的前驅(qū)結(jié)點；否則，繼續(xù)查找；即p和q指針同時向后移。找到了值為76的結(jié)點：,q,p,62,刪除p所指的結(jié)點：,刪除之后的鏈表為：,80,76,90,q,p,q-next=p-next;,free(p);,63,程序如下:,int Listdelete ( LNode *L, int *e ) LNode *q, *p; if ( !L ) return 0; p=L-next ; q=L; while ( p ,64,6.4 小 結(jié),本節(jié)介紹了線性鏈表的定義和建立算法，又介紹了插入一個結(jié)點、刪