【正文】 第十二章 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) ? 管理動(dòng)態(tài)變量 ? 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) – 棧 ── stack – 隊(duì)列 ── queue – 鏈表 ——linkage table – 樹 ——tree – 圖 —— graph ? 程序設(shè)計(jì)實(shí)例 ? 本章小結(jié) ? 作業(yè) ? 考慮上一章的職工卡片問題，用計(jì)算機(jī)管理這些卡片 , 要把卡片保存在計(jì)算機(jī)內(nèi)。 ? 首先，用什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)：一張卡片是一個(gè)結(jié)構(gòu)體，所有卡片自然用結(jié)構(gòu)體數(shù)組。 ? 第三，操作問題： – 若增加一個(gè)人，應(yīng)該在數(shù)組中加一個(gè)元素，會(huì)產(chǎn)生數(shù)組不夠大的可能。 – 若增加一張卡片在數(shù)組中間，應(yīng)該把加入位置以后的其它元素依次向后移動(dòng)。 – 若在中間刪除一張卡片，會(huì)在數(shù)組中間留下一個(gè) “ 洞 ” ，應(yīng)該把 “ 洞 ” 以后的元素依次向前移動(dòng) ? 使用數(shù)組帶來(lái)的問題是： – 操作不方便； – 數(shù)組尺寸不好確定。 第二，數(shù)組多大：為保存全部卡片，并且人數(shù)不固定，就應(yīng)該給一個(gè)足夠大的數(shù)組。 ? 最好把這些卡片存儲(chǔ)成動(dòng)態(tài)的， – 需要多大存儲(chǔ)量（有多少?gòu)埧ㄆ┚陀枚啻蟆? – 中間加一張卡片時(shí)不要向后串別的卡片， – 刪除一張卡片時(shí)不要留下 “ 洞 ” 。 如圖的鏈?zhǔn)浇Y(jié)構(gòu)可以滿足要求 : ? 當(dāng)增加一張卡片時(shí)，只需要向計(jì)算機(jī)系統(tǒng)申請(qǐng)一塊空間，聯(lián)到鏈的適當(dāng)位置上。例如，要增加一張卡片 50 插入到 2 、3 之間，則只需要如下修改指針： ? 若刪除一節(jié)，只需要將其從鏈上摘下來(lái)即可。例刪除 2節(jié)得 鏈上已經(jīng)沒有 2節(jié)了，刪掉的節(jié)所占的存儲(chǔ)空間還可以還回計(jì)算機(jī)系統(tǒng)，以便作其它用途。 1 2 3 … n . 50 ? 這就是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的 ——鏈表。動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)上的一項(xiàng)是一個(gè)動(dòng)態(tài)變量，指針是標(biāo)識(shí)動(dòng)態(tài)變量的有力手段。動(dòng)態(tài)變量與靜態(tài)變量的區(qū)別在于 : ? 靜態(tài)變量是程序中由程序員 “ 顯式 ” 說(shuō)明的變量。它有一個(gè)名字，在編譯時(shí)，編譯程序已經(jīng)給它分配存儲(chǔ)空間。這塊存儲(chǔ)空間用變量的名字來(lái)標(biāo)識(shí)。 ? 動(dòng)態(tài)變量在程序中沒有 “ 顯式 ” 說(shuō)明，它沒有名字 ? 在編譯時(shí)編譯程序不知道有該變量，不給（也不可能給）它分配空間。 ? 動(dòng)態(tài)變量是在程序運(yùn)行時(shí) – 隨程序存儲(chǔ)數(shù)據(jù)的需要，申請(qǐng)空間函數(shù)（例如malloc，當(dāng)然也是由程序員安排的）隨機(jī)的動(dòng)態(tài)的申請(qǐng)來(lái)的空間。它沒有名字，一般動(dòng)態(tài)變量都由指針標(biāo)識(shí)。 – 當(dāng)使用完畢后，由釋放空間函數(shù)（例如 free）釋放，還回計(jì)算機(jī)存儲(chǔ)管理系統(tǒng)，以備它用。 ? 注意：這里所說(shuō)的靜態(tài)變量不是 C語(yǔ)言中由靜態(tài)存儲(chǔ)類別 static聲明的變量；動(dòng)態(tài)變量也不是 C語(yǔ)言中由自動(dòng)存儲(chǔ)類別 auto聲明的變量。而是一般程序設(shè)計(jì)概念中的靜態(tài)變量、動(dòng)態(tài)變量 管理動(dòng)態(tài)變量 ? 動(dòng)態(tài)變量在程序運(yùn)行時(shí)，隨程序存儲(chǔ)數(shù)據(jù)的需要，向計(jì)算機(jī)系統(tǒng)申請(qǐng)；使用完后還回計(jì)算機(jī)系統(tǒng)。 ? 本節(jié)介紹 – 申請(qǐng)計(jì)算機(jī)存儲(chǔ)空間函數(shù) malloc – 釋放存儲(chǔ)空間函數(shù) free 目標(biāo)代碼空間 靜態(tài)區(qū)空間 庫(kù)代碼空間 堆區(qū)空間 棧區(qū)空間 內(nèi)存 程序運(yùn)行時(shí)，涉及用戶程序的內(nèi)存存儲(chǔ)結(jié)構(gòu)如右圖所示，首先是目標(biāo)代碼區(qū)；然后是靜態(tài)存儲(chǔ)區(qū)，用于存放那些可用絕對(duì)地址標(biāo)識(shí)的，主要是具有靜態(tài)存儲(chǔ)類別的數(shù)據(jù)和變量；接著是目標(biāo)代碼運(yùn)行時(shí)用到的庫(kù)程序代碼區(qū)；最后剩余空間是棧區(qū)和堆區(qū)，棧區(qū)和堆區(qū)從剩余空間的兩端，動(dòng)態(tài)的向中間增長(zhǎng)。棧區(qū)用來(lái)存儲(chǔ)程序中聲明的函數(shù)的局部變量等具有自動(dòng)存儲(chǔ)類別的數(shù)據(jù)和變量；堆區(qū)用來(lái)存儲(chǔ)經(jīng)過動(dòng)態(tài)申請(qǐng)空間函數(shù)申請(qǐng)的變量。 ? sizeof 運(yùn)算符 – 單目運(yùn)算符 sizeof 的 ?操作數(shù) 是類型。 ?運(yùn)算結(jié)果 是求得相應(yīng)類型的尺寸，即存儲(chǔ)相應(yīng)類型數(shù)據(jù)所需要的字節(jié)數(shù)。 – sizeof(int) /* 結(jié)果是 2 */ – sizeof(char) /* 結(jié)果是 1 */ – sizeof(struct date) /* 若 struct date 是第十一章定義的日期類型，結(jié)果是 6 */ ? malloc 函數(shù) : – 原型 void *malloc(unsigned long size)。 – 功能 申請(qǐng)足夠大內(nèi)存區(qū)域用來(lái)存儲(chǔ)長(zhǎng)度為 size的數(shù)據(jù)對(duì)象，返回該區(qū)域的首指針，并保證該區(qū)域符合任何數(shù)據(jù)類型對(duì)存儲(chǔ)區(qū)域開始地址和對(duì)齊的要求。 返回指針是 void類型的，調(diào)用者必須使用顯示強(qiáng)制類型轉(zhuǎn)換，把該指針轉(zhuǎn)換成所需要類型的指針。 ? 例 : float *p 。 p = (float*)malloc( sizeof(float) )。 struct date *pdate。 pdate=(struct date*)malloc(sizeof(struct date))。 ? free函數(shù) – 動(dòng)態(tài)申請(qǐng)的內(nèi)存如果不再使用，應(yīng)當(dāng)適時(shí)釋放這樣可以提高程序運(yùn)行效率。 free函數(shù)用來(lái)釋放經(jīng)過 malloc申請(qǐng)的動(dòng)態(tài)空間。 free的函數(shù) – 原型 void free ( void *ptr ) 。 – 功能 釋放由 malloc申請(qǐng)的內(nèi)存區(qū)域。 free的參數(shù)ptr是一個(gè)指針，指向以前由 malloc申請(qǐng)的一個(gè)內(nèi)存區(qū)域。 ? 例 – 申請(qǐng) float *p 。 p = (float*)malloc( sizeof(float) )。 struct date *pdate。 pdate=(struct date*)malloc(sizeof(struct date))。 – 釋放 free(p)。 free(pdate)。 – free(ptr) /* 釋放 ptr所指向由 malloc申請(qǐng)的內(nèi)存空間 */ – 一塊存儲(chǔ)區(qū)域一經(jīng)釋放，便不能再使用。使用 free特別注意，操作不當(dāng)會(huì)產(chǎn)生不可預(yù)料的結(jié)果。如下情況下使用 free都會(huì)造成災(zāi)難性后果。 ? ptr無(wú)值； ? ptr的值為 NULL； ? ptr所指向的空間不是經(jīng)過 malloc申請(qǐng)來(lái)的； ? 對(duì)一次申請(qǐng)的存儲(chǔ)區(qū)進(jìn)行多次釋放（實(shí)際可能是ptr無(wú)值或值為 NULL）。 ? 實(shí)用問題 : – 若指針變量指向的用 malloc申請(qǐng)來(lái)的動(dòng)態(tài)變量，是孤立的不能與其它變量相聯(lián)系，顯然作用不大。 – 引進(jìn)動(dòng)態(tài)變量的目的是構(gòu)造動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。 – 例如象本章開始介紹的那樣，構(gòu)造一個(gè)鏈表等。 – 這就要求一個(gè)數(shù)據(jù)項(xiàng)上除基本的數(shù)據(jù)信息外，還應(yīng)包含與其它數(shù)據(jù)項(xiàng)相聯(lián)系的信息，也就是包含指針。 – 該結(jié)構(gòu)必須用結(jié)構(gòu)體類型描述，鏈表上一節(jié)的類型定義形式。 類型定義形式 struct t { 基本數(shù)據(jù)部分； struct t *next 。 } 基本數(shù) 據(jù)部分 指針部分 一個(gè)數(shù)據(jù)項(xiàng) 1 2 3 … n . 棧 ── stack ? 在第六章已經(jīng)用數(shù)組實(shí)現(xiàn)過棧和隊(duì)列，但是，數(shù)組有一定的局限性。如圖可以用單向鏈表實(shí)現(xiàn)棧，指針變量 top指向棧頂。棧的操作有 : ① 初始化： stackintial ② 壓棧： stackpush ③ 彈棧： stackpop 設(shè)有聲明 : typedef ... items 。 typedef struct stackcell { items data 。 struct stackcell *predocessor 。 } stackcelltype 。 typedef stackcelltype *pstacktype 。 pstacktype top 。 top: ... ... . 棧 如下實(shí)現(xiàn)棧的操作： void stackinitial(void) { top = NULL 。 } void stackpush ( items x ) { pstacktype p 。 p = (pstacktype)malloc(sizeof(stackcelltype))。 pdata = x 。 pprodocessor = top 。 top = p 。 } void stackpop ( items *x ) { pstacktype p 。 if ( top != NULL ) { *x = topdata 。 p = top 。 top = toppredecessor 。 free(p)。 } else printf( ―棧下溢 \n‖ )。 } 看一下這三個(gè)操作 : 1. 初始化后 (調(diào)用 stackinitail)得。 2. 調(diào)用一次 stackpush(1) 得。 3. 再調(diào)用一次 stackpush(2)得 。 4. 調(diào)用一次 stackpop(amp。b)得 。 top: 1 . 2 b: 2 隊(duì)列 ? 如圖可用單向鏈表實(shí)現(xiàn)隊(duì)列，現(xiàn)在要用兩個(gè)指針變量，一個(gè)指向隊(duì)頭（ front），一個(gè)指向隊(duì)尾（ rear）。隊(duì)列的操作有 ① 初始化（ queueinitial ） ② 進(jìn)隊(duì) ── 排在隊(duì)尾（ inqueue） ③ 出隊(duì) ── 從隊(duì)頭刪一項(xiàng)（ outqueue） rear: front: ... . 設(shè)有如下說(shuō)明 : typedef ... items 。 typedef struct queue { items data struct queue *next 。 } queuetype 。 typedef queuetype *pqueuetype 。 pqueuetype front,rear 。 操作： void queueinital(void) { front = NULL 。 rear = NULL 。 } void inqueue (item x) { pqueuetype p。 p = (pqueuetype)malloc(sizeof(queuetype))。 p data = x 。 p next = NULL 。 if ( rear==NULL ) { rear = p 。 front = p 。 } else { rear next