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

第七章 動態(tài)數(shù)據(jù)結(jié)構(gòu),目錄,態(tài)數(shù)據(jù)結(jié)構(gòu),本章開始介紹動態(tài)數(shù)據(jù)結(jié)構(gòu)，主要介紹鏈表結(jié)構(gòu)的建立、在鏈表中查找指定元素、插入一個新元素、刪除一個元素等操作。學完本章內(nèi)容后，要求深刻理解動態(tài)存儲結(jié)構(gòu)的概念，并正確運用。,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)分配固定大小的存儲空間，以后在程序運行的過程中，存儲空間的位置和容量都不會再改變。而實際生活中常常有這樣的問題，數(shù)據(jù)量的多少是動態(tài)變化的。,7.1 從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu),例如，圖書館的藏書量，在圖書館初建時，假設(shè)有10000本，隨著時間的推移，藏書的數(shù)量必定要增加。有人可能會想，在定義一個靜態(tài)變量時，預留出一部分空間，但這也會引起一些問題，首先多出的那部分空間不知何時才能使用，在沒有被使用之前一直被閑置；其次，誰又能保證增加的空間就足夠呢？,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ù)元素分配若干個同樣大小的空間；當問題的數(shù)據(jù)量發(fā)生變化時，數(shù)據(jù)的存儲空間的大小也發(fā)生變化。如果數(shù)據(jù)量增加，就重新向系統(tǒng)申請新的空間；如果數(shù)據(jù)量減少，就將現(xiàn)有的多余的空間歸還給系統(tǒng)。,7.2. 動態(tài)內(nèi)存分配,使用計算機解決問題的所有方法都是通過使用系統(tǒng)提供給我們的基本命令或函數(shù)來實現(xiàn)的。所以首先讓我們來看看，c的標準函數(shù)中有哪些是用于動態(tài)內(nèi)存分配的，怎樣使用。,7.2.1 ANSI C 中動態(tài)內(nèi)存操作標準函數(shù),ANSI C中提供了若干個動態(tài)內(nèi)存操作標準函數(shù)，它們的名稱分別是malloc、calloc、realloc、free等。這些函數(shù)可以使用在任何的C環(huán)境中。,1malloc函數(shù),malloc函數(shù)是 C的標準函數(shù)之一。原型定義在malloc.h文件中。 原型為： void *malloc(unsigned int size); 其作用是向系統(tǒng)申請一個確定大小(size 個字節(jié))的存儲空間，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。,1malloc函數(shù),使用格式： 指針型變量 =(基類型*)malloc(需要的存儲空間的字節(jié)數(shù)); 例7-1：為一個整數(shù)分配存儲空間，需要的語句為： 在文件的頭部：#include 在說明部分： int *p; 在程序中：p = ( int * )malloc ( sizeof( int ) ) ;,測試malloc的程序舉例：,#include #include #include void main() int *p; /*定義一個指向整型的指針變量*/ int x; p = ( int * )malloc( sizeof( int ) ); if ( !p ) exit( 0 ); p= ,2calloc函數(shù),calloc函數(shù)是 C的標準函數(shù)之一。原型定義在malloc.h文件中。 原型為： void *calloc(unsigned int n , unsigned int size); 其作用是向系統(tǒng)申請 n 個大小為size 個字節(jié)的連續(xù)存儲空間，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空?？梢詾橐痪S數(shù)組開辟一片連續(xù)的動態(tài)存儲空間。,2calloc函數(shù),使用格式： 指針型變量 =(數(shù)組元素類型*)calloc(n , 每一個數(shù)組元素的存儲空間的字節(jié)數(shù))； 例7-2：為一個有10個整數(shù)的一維數(shù)組分配存儲空間，需要的語句為： 在文件的頭部：#include 在說明部分： 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的標準函數(shù)之一。原型定義在malloc.h文件中。 原型為： void *realloc( void *p, unsigned int size); 其作用是向系統(tǒng)重新申請一個確定大小的存儲空間，并將原存儲空間中的數(shù)據(jù)值傳送到新的地址空間的低端，返回值為一個指向void類型的分配域起始地址的指針值。如果此函數(shù)操作失敗，返回值為空。原存儲空間的數(shù)據(jù)將丟失。,3realloc函數(shù),使用格式： 指針型變量 =(基類型*)realloc( 原存儲空間的首地址，新的存儲空間的字節(jié)數(shù))； 例7-3：現(xiàn)有一個為10個整數(shù)分配的存儲空間，其首地址為p1; 由于數(shù)據(jù)量的增加，原存儲空間已滿，需要擴大原空間為20個整數(shù)的大??；需要的語句為： 在文件的頭部：#include 在說明部分： 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ù)主要的用于當原分配空間已被占滿，而新的數(shù)據(jù)又要加入到該空間時的狀況。它的優(yōu)點是可以自動地將原空間的內(nèi)容全部傳遞到新空間中，不必程序員再編語句來實現(xiàn)。缺點是一旦新空間申請失敗，原空間的內(nèi)容也將丟失。對這一點，使用時應加以注意。,4free函數(shù),free函數(shù)是 C的標準函數(shù)之一。原型定義在malloc.h文件中， 原型為： void free (void *p) 其作用是釋放由p所指的內(nèi)存區(qū)，將一個存儲空間歸還給系統(tǒng)。 使用格式： free(指針型變量); 例7-4：將一個已分配存儲空間釋放，需要的語句為 在文件的頭部：#include 在說明部分： int *p; 在程序中：free( p ),程序舉例：,#include #include #include main() int *p; p =(int *)malloc(sizeof(int); if(!p) exit(0) ; free(p)； ,c+ 中為進行動態(tài)操作提供的運算符new和delete,在軟件的研制過程中，程序中動態(tài)申請內(nèi)存空間和釋放內(nèi)存空間是一件很常見的事，前面一節(jié)中，我們講解了ANSI C 中的辦法。利用標準庫函數(shù)malloc、calloc、reallloc、free等。但malloc、calloc、reallloc等函數(shù)都要求程序設(shè)計者知道應開辟空間的確切大小，返回值的類型需要強制類型轉(zhuǎn)換。 c+ 中對此進行了改進，為進行動態(tài)內(nèi)存操作提供了運算符new和delete，來代替malloc和free。但在c+中依然保留了malloc和free，以便和C兼容。,1new 運算符,new 是c+中提供的用于開辟一個動態(tài)存儲空間的運算符。 new 運算符的一般格式： 變量指針 = new 類型(初值)； 例如： (1)申請一個存放整數(shù)的空間： 語句格式： p = new int； 執(zhí)行結(jié)果：開辟了一個整數(shù)大小的空間，并將該空間的首地址送入指向整型數(shù)據(jù)的指針變量p中。,(2)申請一個存放字符型數(shù)據(jù)的空間，并為該空間賦初值a： 語句格式： p = new char(a)； 執(zhí)行結(jié)果：開辟了一個字節(jié)大小的空間，并將該空間的首地址送入指向字符型數(shù)據(jù)的指針變量p中。P所指空間中的數(shù)據(jù)值為字符 a 。 (3)申請一個存放實數(shù)的空間： 語句格式： p = new float(1.414)； 執(zhí)行結(jié)果：開辟了一個實數(shù)大小的空間，并將該空間的首地址送入指向?qū)嵭蛿?shù)據(jù)的指針變量p中。并將該空間中賦入初值1.414。,(4)申請一個存放10個實數(shù)的數(shù)組的空間： 語句格式： p = new float10； 執(zhí)行結(jié)果：開辟了一個10個實數(shù)大小的空間，將該空間的首地址送入指向?qū)嵭蛿?shù)據(jù)的指針變量p中。注意：用new 為數(shù)組分配空間不能指定初值。,2delete 運算符：,delete 運算符是c+中的提供的實現(xiàn)動態(tài)內(nèi)存釋放功能的運算符，類似于標準庫函數(shù) free。 一般格式為：delete 名字指針；例如： (1)釋放一個存放整數(shù)的空間： 如果 p = new int；則釋放一個存放整數(shù)的空間的語句為：delete p; 執(zhí)行結(jié)果：將該整數(shù)空間釋放掉，即將該資源歸還給系統(tǒng)。,2delete 運算符：,(2)釋放一個存放10個實數(shù)的數(shù)組的空間： 如果： p = new float10；則釋放一個數(shù)組空間的語句為：delete p; 執(zhí)行結(jié)果：將該數(shù)組空間釋放掉，即將該資源歸還給系統(tǒng)。,2delete 運算符：,new 試圖創(chuàng)建一個名字類型的對象，向系統(tǒng)申請sizeof(名字)個字節(jié)大小的空間。新對象的生存周期始于創(chuàng)建點，直到delete將其釋放或到程序結(jié)束。如果申請成功，返回指向新對象的指針；若返回的指針為空指針，表示動態(tài)空間分配失敗。注意：delete只能用于用new分配的內(nèi)存的釋放。,例7-5申請一個結(jié)構(gòu)體類型的存儲空間，用來存放相應類型的數(shù)據(jù)。 解決問題要點： 包含相關(guān)的頭文件； 定義一個結(jié)構(gòu)體類型； 定義結(jié)構(gòu)體類型的變量； 申請空間； 對指定空間賦值； 釋放申請的空間；,程序舉例：,#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 的相同點是他們的作用都是在程序的執(zhí)行過程中向系統(tǒng)申請存儲空間，返回值都是申請到的存儲空間的首地址，不同點是，malloc 是c編譯系統(tǒng)提供的標準庫函數(shù)，new 是c+ 系統(tǒng)提供的運算符，new的操作效率要高于malloc； new不需要使用顯式的sizeof函數(shù)就能知道名字的大小，而malloc 需要明確指出所申請的空間的大小(總的字節(jié)數(shù))；new 的返回值是指向名字類型的確定的指針類型，不需要強制說明，而malloc的返回值是一個指向void類型的指針類型，需要強制轉(zhuǎn)換成指向具體數(shù)據(jù)類型的指針類型。當所申請的空間是一個變量所需的空間時，new 運算符還可以為所申請的空間賦初值，malloc 不具有此功能。,7.3 鏈 表,計算機處理數(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）,線性表中的數(shù)據(jù)元素之間存在嚴格的順序關(guān)系，有一個唯一的稱為第一個的元素（首元），有唯一的稱為最后一個的元素（尾元），其它元素都有唯一的直接后繼元素和唯一的直接前趨元素。 線性表這種邏輯結(jié)構(gòu)在計算機內(nèi)表示時，可以采用鏈式存儲結(jié)構(gòu)，即一個數(shù)據(jù)元素存放于一個結(jié)點中，不同的數(shù)據(jù)元素之間的先后順序用結(jié)點的指針域鏈接。一個結(jié)點就是一個結(jié)構(gòu)體類型的變量。,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)如圖所示：,若干個結(jié)點首尾相連按照其邏輯順序鏈接成一排，稱為線性鏈表。 單向鏈表如下圖所示：,圖7.2 單向鏈表,1. 鏈表結(jié)點的 C 語句定義,對于鏈表這種數(shù)據(jù)結(jié)構(gòu)，ANSI C 中，按如下方式描述： 首先用結(jié)構(gòu)體類型描述一個數(shù)據(jù)元素結(jié)點，定義一個結(jié)點類型的語句格式： typedef struct LNode ElemType data； struct LNode *next； LNode，*LinkList；,其中：,typedef 語句定義了一個結(jié)構(gòu)體類型和鏈表類型 LNode 是一個結(jié)點的類型名稱。它有兩個成員，一個名稱為data ，類型為數(shù)據(jù)元素的類型，用來存放一個數(shù)據(jù)元素的值；另一個成員名稱為next，類型為指向本結(jié)構(gòu)體類型的指針類型，用來存放邏輯上排在本結(jié)點后面的結(jié)點的首地址。 LinkList 是指向 LNode 類型的指針類型。 ElemType 是數(shù)據(jù)元素的類型的一般性描述，當我們具體寫程序時，應該用確定類型名稱來替換，例如，int、float 、char等。,例7-6：鏈表中的數(shù)據(jù)元素用來存放整數(shù)，定義鏈表的結(jié)點類型的語句格式為： typedef struct LNode int data； struct LNode *next； LNode，*LinkList；,定義一個指向結(jié)點類型的指針類型變量的語句： LNode *p ; 3定義一個鏈表類型的指針變量：LinkList L; 4訪問結(jié)點變量 p 的各個成員： p-data , p-next 說明：本章的所有程序都是基于以上類型定義。,7.3.2 鏈表的建立,1. 構(gòu)造一個空線性鏈表 L 首先，構(gòu)造一個空的線性鏈表。為了描述方便，通常將鏈表的第一個結(jié)點空置，不存放數(shù)據(jù)元素，只是作為鏈表的開始標志，稱為頭結(jié)點。數(shù)據(jù)元素從鏈表的第二個結(jié)點開始存放。 空的線性表定義為沒有數(shù)據(jù)元素的表。一個空的線性鏈表就規(guī)定為，只有一個頭結(jié)點的鏈表。所以，構(gòu)造一個空的線性鏈表就是建立只有一個頭結(jié)點的鏈表。,（1）算法描述: 申請一個結(jié)點的空間； 將該結(jié)點作為線性鏈表的頭結(jié)點； 將該結(jié)點的 next 域置空；,（2）完整程序（Example 7_6.cpp）:,/*程序名：Example7_6.cpp */ void InitList ( LinkList *L ) /*構(gòu)造一個空的線性鏈表*/ (*L) = (LNode*)malloc(sizeof(LNode )；/*申請一個結(jié)點空間*/ if ( !（*L）) exit ( 0 )；/*申請不成功，異常結(jié)束程序運行*/ （*L）-next = NULL；/*申請成功，頭結(jié)點的next域置空*/ return(1)； ,2逆序輸入 n 個數(shù)據(jù)元素，建立帶表頭結(jié)點的單線性鏈表 L,現(xiàn)在開始建立一個非空的線性鏈表。我們這里所建的鏈表的第一個結(jié)點都是頭結(jié)點。數(shù)據(jù)元素從鏈表的第二個結(jié)點開始存放。 一個非空的線性鏈表是除了頭結(jié)點以外至少有一個數(shù)據(jù)元素的鏈表。線性鏈表由若干個數(shù)據(jù)元素結(jié)點組成。那么，構(gòu)造一個非空的線性鏈表的過程就是逐個建立數(shù)據(jù)元素結(jié)點，并將它們依次插入到鏈表中的過程。,所謂頭插入，即每次將數(shù)據(jù)元素結(jié)點插入到表頭結(jié)點的之后，第一個數(shù)據(jù)元素結(jié)點之前。 插入過程如圖7-3所示：,初始狀態(tài)：,插入第一個結(jié)點之后：,插入第二個結(jié)點之后：,插入第三個結(jié)點之后：,插入最后一個結(jié)點之后：,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é)點插在鏈表的第一個數(shù)據(jù)元素的位置；我們也可以將新建立的數(shù)據(jù)元素結(jié)點每次都插在鏈表的尾部，大家可以思考一下，以尾插入的方式建立鏈表，程序怎樣編寫？,7.3.3 鏈表結(jié)點的插入,將一個數(shù)據(jù)元素插入到鏈表中，有三種情況：頭插入，尾插入以及在鏈表中的第i個數(shù)據(jù)元素的位置處插入。將一個新元素插入在鏈表的頭結(jié)點的后面，其它的所有結(jié)點之前稱為頭插入。將一個新元素插入在鏈表的尾結(jié)點的后面，使得新插入的結(jié)點成為尾結(jié)點稱為尾插入。將一個新元素插入在鏈表中的第i個數(shù)據(jù)元素的位置處，即插入在第i個數(shù)據(jù)元素結(jié)點之前，使得新插入的結(jié)點成為鏈表中的第i個結(jié)點。下面我們詳細介紹每一種插入的算法實現(xiàn)。,例7-8：已有鏈表L 如圖所示,鏈表中的元素按遞增有序排列：,圖7.4 鏈表的插入過程 其中每個結(jié)點中存放的值為學生的考試成績。現(xiàn)在有另外三個學生的的成績分別為65、82、90。將他們插入到鏈表L中，要求插入之后鏈表依然遞增有序。,圖7.5 頭插入過程,首先將65 插入到鏈表L中: 插入的過程：設(shè)p=L-next，因為p非空，判斷p-data65,所以，65應該插在L的后面，70結(jié)點的前面，插入之后的鏈表為： L:,80,70,85,s,p,實現(xiàn)語句：,p=L-next; s=(LNode*)malloc(sizeof(LNode); s-data=x; s-next=p; L-next=s;,將82 插入到鏈表L中:,插入的過程： 首先應找到82 應在的位置： 82應該插在兩個結(jié)點之間，82前面結(jié)點的data域值小于82；82后面結(jié)點的data域值大于等于82；如圖所示： L:,實現(xiàn)語句：,q=*L; p=(*L)-next; while( p ,將90 插入到鏈表L中:,顯然，90應插到鏈表的尾部，即：插到鏈表的最后一個結(jié)點的后面。 插入的過程： 首先找到插入的位置：設(shè)p=L-next，當p非空并且 p-data next; 循環(huán)一定以p為空結(jié)束。 將新結(jié)點90插在q的后面，插入之后的鏈表為：,L:,實現(xiàn)語句：,x=90; p=L-next; s=(LNode*)malloc(sizeof(LNode); s-dat