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