【正文】 (void) { front = NULL 。 typedef struct queue { items data struct queue *next 。 4. 調(diào)用一次 stackpop(amp。 } else printf( ―棧下溢 \n‖ )。 if ( top != NULL ) { *x = topdata 。 pdata = x 。 pstacktype top 。 typedef struct stackcell { items data 。 類型定義形式 struct t { 基本數(shù)據(jù)部分； struct t *next 。 – 引進動態(tài)變量的目的是構(gòu)造動態(tài)數(shù)據(jù)結(jié)構(gòu)。使用 free特別注意，操作不當會產(chǎn)生不可預(yù)料的結(jié)果。 pdate=(struct date*)malloc(sizeof(struct date))。 free的參數(shù)ptr是一個指針，指向以前由 malloc申請的一個內(nèi)存區(qū)域。 ? free函數(shù) – 動態(tài)申請的內(nèi)存如果不再使用，應(yīng)當適時釋放這樣可以提高程序運行效率。 ? 例 : float *p 。 ?運算結(jié)果 是求得相應(yīng)類型的尺寸，即存儲相應(yīng)類型數(shù)據(jù)所需要的字節(jié)數(shù)。而是一般程序設(shè)計概念中的靜態(tài)變量、動態(tài)變量 管理動態(tài)變量 ? 動態(tài)變量在程序運行時，隨程序存儲數(shù)據(jù)的需要，向計算機系統(tǒng)申請；使用完后還回計算機系統(tǒng)。 ? 動態(tài)變量是在程序運行時 – 隨程序存儲數(shù)據(jù)的需要，申請空間函數(shù)（例如malloc，當然也是由程序員安排的）隨機的動態(tài)的申請來的空間。動態(tài)變量與靜態(tài)變量的區(qū)別在于 : ? 靜態(tài)變量是程序中由程序員 “ 顯式 ” 說明的變量。例如，要增加一張卡片 50 插入到 2 、3 之間，則只需要如下修改指針： ? 若刪除一節(jié)，只需要將其從鏈上摘下來即可。 第二，數(shù)組多大：為保存全部卡片，并且人數(shù)不固定，就應(yīng)該給一個足夠大的數(shù)組。 ? 首先，用什么數(shù)據(jù)結(jié)構(gòu)存儲：一張卡片是一個結(jié)構(gòu)體，所有卡片自然用結(jié)構(gòu)體數(shù)組。 ? 第三，操作問題： – 若增加一個人，應(yīng)該在數(shù)組中加一個元素，會產(chǎn)生數(shù)組不夠大的可能。 ? 最好把這些卡片存儲成動態(tài)的， – 需要多大存儲量（有多少張卡片）就用多大。例刪除 2節(jié)得 鏈上已經(jīng)沒有 2節(jié)了，刪掉的節(jié)所占的存儲空間還可以還回計算機系統(tǒng)，以便作其它用途。它有一個名字，在編譯時，編譯程序已經(jīng)給它分配存儲空間。它沒有名字，一般動態(tài)變量都由指針標識。 ? 本節(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)的向中間增長。 – sizeof(int) /* 結(jié)果是 2 */ – sizeof(char) /* 結(jié)果是 1 */ – sizeof(struct date) /* 若 struct date 是第十一章定義的日期類型，結(jié)果是 6 */ ? malloc 函數(shù) : – 原型 void *malloc(unsigned long size)。 p = (float*)malloc( sizeof(float) )。 free函數(shù)用來釋放經(jīng)過 malloc申請的動態(tài)空間。 ? 例 – 申請 float *p 。 – 釋放 free(p)。如下情況下使用 free都會造成災(zāi)難性后果。 – 例如象本章開始介紹的那樣，構(gòu)造一個鏈表等。 } 基本數(shù) 據(jù)部分 指針部分 一個數(shù)據(jù)項 1 2 3 … n . 棧 ── stack ? 在第六章已經(jīng)用數(shù)組實現(xiàn)過棧和隊列，但是，數(shù)組有一定的局限性。 struct stackcell *predocessor 。 top: ... ... . 棧 如下實現(xiàn)棧的操作： void stackinitial(void) { top = NULL 。 pprodocessor = top 。 p = top 。 } 看一下這三個操作 : 1. 初始化后 (調(diào)用 stackinitail)得。b)得 。 } queuetype 。 rear = NULL 。 p next = NULL 。 rear = p 。 p = front 。 } } 看一下這三個操作 : 1. 調(diào)用初始化后（調(diào)用一次 queueinitail） 得； 2. 調(diào)用一次 ingueue(1)得； 再調(diào)用一次 ingueue(2)得； 再調(diào)用一次 ingueue(3)得 。 再調(diào)用一次 outgueue(amp。 3 可以分成向鏈頭加入數(shù)據(jù)和向鏈尾加入數(shù)據(jù)兩種方式。 ? 遍歷單向鏈表 : 遍歷是指從頭到尾將鏈表上數(shù)據(jù)全部加工一遍。 p0 = NULL。 p = p next。 while (p != NULL amp。 } ? 向單向鏈表插入一項 : 設(shè)有下圖的鏈表，現(xiàn)在要把 r所指示的數(shù)據(jù)項插入到 p0、 p 所指兩項之間。刪除算法是： q = p 。現(xiàn)在要把 p 所指的項與 q 所指的項交換 為了表示操作方便，我們把該鏈表分兩段畫出。 /* 3 */ /*交換 p0 next 、 q0 next */ p0 next = q。 /* 7 */ 樹 ——tree ? 兩叉樹，兩叉樹的每個數(shù)據(jù)項附帶兩個指針，分別指向它的兩個分支。 稱 ti 的左指針連接的部分為 ti 的 左子樹 ， ti 的右指針連接的部分為 ti 的 右子樹 。 – 一個兩叉樹稱為檢索樹， – 如果對每個結(jié)點 ti ，它的左子樹中所有結(jié)點的 key 值都小于 ti 的 key 值； – ti 的右子樹中所有結(jié)點的 key 值都大于 ti 的 key 值。在訪問一個結(jié)點時，可以做任何信息加工工作。 – 中序遍歷 ：對任意一個結(jié)點 ti 來講，先遍歷左子樹；然后訪問及處理該結(jié)點的數(shù)據(jù)域；最后遍歷右子樹。 ?前序遍歷算法是： void preorder (treepointer p) { if ( p!=NULL ) { printf(―%c‖ , p data ) 。 printf(―%c‖ , p data ) 。 } } * + a / d * b c e f ＊ ＋ a / b c d * e f ? 檢索 檢索是按給定關(guān)鍵字值 c 在樹上找一個結(jié)點 ti ，且 ti 的關(guān)鍵字值 key 恰好等于 c 。 else if ( c p key ) return search( c , p left ) 。 void insert( keytype c , datatype d , treepointer *p ) { if ( *p == NULL ) { *p = (treepointer)malloc(sizeof(struct tree))。 (*p) right = NULL 。((*p)right) ) 。 以 amp。 d ((*p)right) ) insert 的形式參數(shù) p 指向本步的 (*p) right ，而 (*p) right 值為 NULL。 ... ... p: ?刪除一結(jié)點 設(shè)欲刪除結(jié)點為 r，則可能有如下幾種情況。 r 只有一個右子樹 r 兩個方向都有子樹 : 在 r 的左子樹上找到關(guān)鍵字 key 值最大的結(jié)點 s，把 s 結(jié)點的數(shù)據(jù) data及關(guān)鍵字 key 復(fù)制到 r 結(jié)點上，然后刪除掉 s 結(jié)點。 ③ 把 s 的左子樹連在 s 的父結(jié)點（圖中為 結(jié)點 (5) ）的右鏈上，在圖中即連到 (5) 結(jié)點的右鏈上。 deletenode的調(diào)用形式是： deletenode( valueofkey , amp。 if ( *p == NULL ) printf( ―not found:%d\n‖ , c )。((*p) right ) ) 。(rleft),p ) 。root ) r: r 只有一個左子樹 treepointer del( treepointer *s, treepointer *p ) { /* 處理第三種情況，僅第三種情況調(diào)用 */ treepointer r。 r = *s 。 // 把將釋放的變量指針帶回主程序 } 1 2 3 4 5 9 7 6 8 10 11 12 13 14 15 p: s: 9 r: root: 圖 G=(V， E)。 0 4 3 1 6 7 5 2 0 1 2 1 1 0 3 4 1 2 0 4 5 1 3 1 4 1 4 1 2 3 6 7 1 5 2 6 7 1 6 4 5 1 7 4 5 1 (二 ) 鄰接矩陣方法 設(shè) 圖 G有 k個結(jié)點，使用一個 k*k的 bool類型矩陣 g表示 圖 G 矩陣元素 利用這種表示法，左圖的網(wǎng)表示