【正文】 的數(shù)據(jù) data及關(guān)鍵字 key 復(fù)制到 r 結(jié)點(diǎn) 上，然后刪除掉 s 結(jié)點(diǎn)。 8 s: 5 r: 4 10 13 14 11 12 3 1 2 9 7 6 6使用在左子樹上找最大結(jié)點(diǎn)的方法，按如下步驟進(jìn)行 : ① 沿 r 左子樹的右方向，向下找一個(gè)沒有 右子樹的結(jié)點(diǎn) s ，圖中結(jié)點(diǎn) (9) 。 4 2 5 1 3 r: r 只有一個(gè)左子樹 7 8 5 6 3 1 2 4 r: 7 8 5 6 4 2 3 1 r: r 只有一個(gè)子樹 : 把 r 以下部分接入 r 的父結(jié)點(diǎn)連接 r 處。 d p: 2) 若調(diào)用 insert時(shí)， root非空，在中間某一個(gè)結(jié)點(diǎn)查到空指 針，如圖；設(shè)查到該結(jié)點(diǎn)后，應(yīng)該繼續(xù)向右查，以 amp。root) insert 的形式參數(shù) p 指向 root ，而 root 值為 NULL。所以在執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)) 時(shí)，將使實(shí)在參數(shù)指針變量指向新申請(qǐng)來的結(jié)點(diǎn)。((*p)left) ) 。 (*p) data = d 。 } ? 插入一個(gè)結(jié)點(diǎn) 插入是指將一個(gè)數(shù)據(jù)項(xiàng)插入到樹中某一恰當(dāng)位置，使樹仍保持檢索樹的性質(zhì)。下述檢索算法的前提條件是， p 是檢索樹。 后序遍歷算法是： void postorder (treepointer p) { /*后序遍歷 */ if ( p!=NULL ) { postorder( p left ) 。 preorder( p right ) } } * + a / d * b c e f ＊ ＋ a / b c d * e f ? 中序遍歷過程是： 得到表達(dá)式的原形式，只是沒有括號(hào)。 【 例 121】 設(shè)有下圖所示樹 ,這是由表達(dá)式 (a+b/c)*(de*f) 生成的樹，這棵樹反映了表達(dá)式的結(jié)構(gòu)，同時(shí)也反映了表達(dá)式的運(yùn)算次序。 ? 遍歷算法可分為前序，中序，后序遍歷三種。 設(shè)有說明部分 : typedef ... keytype ； typedef ... datatype ； typedef struct tree { keytype key ； datatype data ； struct tree *left ； struct tree *right ； }treetype。 ti 7 8 5 6 3 1 2 4 ti: ? 為了檢索操作方便，一般把兩叉樹組織成兩叉檢索樹。 結(jié)點(diǎn) ti 的指針連接的結(jié)點(diǎn)稱為 ti 的 子結(jié)點(diǎn) ， 相應(yīng) ti 稱為其子結(jié)點(diǎn)的 父結(jié)點(diǎn) 。 * + a / d * b c e f ( a + b / c ) * ( d – e * f ) root: /* 5 */ /*交換 p 、 q */ p = p0 next 。 /* 1 */ p next = q next。 p0 next = p 。 p0 next = r 。 pkey !=key0 ) { p0 = p。設(shè)關(guān)鍵字域域名為 key ；欲檢索的關(guān)鍵字值為 key0 . 如下算法實(shí)現(xiàn)檢索： p0 = NULL。 加工 p while (p != NULL ) { p = p next。但實(shí)用中，經(jīng)常用如下右端 的算法來遍歷單向鏈表。新項(xiàng)加入鏈頭就是壓棧的算法；新項(xiàng)加入鏈尾就是隊(duì)列中入隊(duì)的算法。 ... 雙向鏈 base: 1 2 N1 N ... 單向鏈 base: 1 2 N1 N ... 環(huán)形鏈 base: 1 2 N1 N ... 雙向 環(huán)形鏈 實(shí)際上前邊講的棧，隊(duì)列都是單向鏈表，但是棧和隊(duì)列只是單向鏈表的兩種特殊應(yīng)用 ——操作只在頭尾進(jìn)行。 1 a) 得； 再調(diào)用一次 outgueue(amp。 if ( front==NULL ) rear = NULL 。 if ( front==NULL ) printf( ―隊(duì)空 \n‖ )。 front = p 。 p = (pqueuetype)malloc(sizeof(queuetype))。 pqueuetype front,rear 。隊(duì)列的操作有 ① 初始化（ queueinitial ） ② 進(jìn)隊(duì) ── 排在隊(duì)尾（ inqueue） ③ 出隊(duì) ── 從隊(duì)頭刪一項(xiàng)（ outqueue） rear: front: ... . 設(shè)有如下說明 : typedef ... items 。 3. 再調(diào)用一次 stackpush(2)得 。 free(p)。 } void stackpop ( items *x ) { pstacktype p 。 p = (pstacktype)malloc(sizeof(stackcelltype))。 typedef stackcelltype *pstacktype 。棧的操作有 : ① 初始化： stackintial ② 壓棧： stackpush ③ 彈棧： stackpop 設(shè)有聲明 : typedef ... items 。 – 該結(jié)構(gòu)必須用結(jié)構(gòu)體類型描述，鏈表上一節(jié)的類型定義形式。 ? 實(shí)用問題 : – 若指針變量指向的用 malloc申請(qǐng)來的動(dòng)態(tài)變量，是孤立的不能與其它變量相聯(lián)系，顯然作用不大。 – free(ptr) /* 釋放 ptr所指向由 malloc申請(qǐng)的內(nèi)存空間 */ – 一塊存儲(chǔ)區(qū)域一經(jīng)釋放，便不能再使用。 struct date *pdate。 – 功能 釋放由 malloc申請(qǐng)的內(nèi)存區(qū)域。 pdate=(struct date*)malloc(sizeof(struct date))。 返回指針是 void類型的，調(diào)用者必須使用顯示強(qiáng)制類型轉(zhuǎn)換，把該指針轉(zhuǎn)換成所需要類型的指針。 ? sizeof 運(yùn)算符 – 單目運(yùn)算符 sizeof 的 ?操作數(shù) 是類型。 ? 注意：這里所說的靜態(tài)變量不是 C語言中由靜態(tài)存儲(chǔ)類別 static聲明的變量；動(dòng)態(tài)變量也不是 C語言中由自動(dòng)存儲(chǔ)類別 auto聲明的變量。 ? 動(dòng)態(tài)變量在程序中沒有 “ 顯式 ” 說明，它沒有名字 ? 在編譯時(shí)編譯程序不知道有該變量，不給（也不可能給）它分配空間。動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)上的一項(xiàng)是一個(gè)動(dòng)態(tài)變量，指針是標(biāo)識(shí)動(dòng)態(tài)變量的有力手段。 如圖的鏈?zhǔn)浇Y(jié)構(gòu)可以滿足要求 : ? 當(dāng)增加一張卡片時(shí)，只需要向計(jì)算機(jī)系統(tǒng)申請(qǐng)一塊空間，聯(lián)到鏈的適當(dāng)位置上。 – 若在中間刪除一張卡片，會(huì)在數(shù)組中間留下一個(gè) “ 洞 ” ，應(yīng)該把 “ 洞 ” 以后的元素依次向前移動(dòng) ? 使用數(shù)組帶來的問題是： – 操作不方便； – 數(shù)組尺寸不好確定。第十二章 動(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ù)組中間，應(yīng)該把加入位置以后的其它元素依次向后移動(dòng)。 – 中間加一張卡片時(shí)不要向后串別的卡片， – 刪除一張卡片時(shí)不要留下 “ 洞 ” 。 1 2 3 … n . 50 ? 這就是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的 ——鏈表。這塊存儲(chǔ)空間用變量的名字來標(biāo)識(shí)。 – 當(dāng)使用完畢后，由釋放空間函數(shù)（例如 free）釋放，還回計(jì)算機(jī)存儲(chǔ)管理系統(tǒng)，以備它用。棧區(qū)用來存儲(chǔ)程序中聲明的函數(shù)的局部變量等具有自動(dòng)存儲(chǔ)類別的數(shù)據(jù)和變量；堆區(qū)用來存儲(chǔ)經(jīng)過動(dòng)態(tài)申請(qǐng)空間函數(shù)申請(qǐng)的變量。 – 功能 申請(qǐng)足夠大內(nèi)存區(qū)域用來存儲(chǔ)長度為 size的數(shù)據(jù)對(duì)象，返回該區(qū)域的首指針，并保證該區(qū)域符合任何數(shù)據(jù)類型對(duì)存儲(chǔ)區(qū)域開始地址和對(duì)齊的要求。 struct date *pdate。 free的函數(shù) – 原型 void free ( void *ptr ) 。 p = (float*)malloc( sizeof(float) )。 free(pdate)。 ? ptr無值； ? ptr的值為 NULL； ? ptr所指向的空間不是經(jīng)過 malloc申請(qǐng)來的； ? 對(duì)一次申請(qǐng)的存儲(chǔ)區(qū)進(jìn)行多次釋放（實(shí)際可能是ptr無值或值為 NULL）。 – 這就要求一個(gè)數(shù)據(jù)項(xiàng)上除基本的數(shù)據(jù)信息外，還應(yīng)包含與其它數(shù)據(jù)項(xiàng)相聯(lián)系的信息，也就是包含指針。如圖可以用單向鏈表實(shí)現(xiàn)棧，指針變量 top指向棧頂。 } stackcelltype 。 } void stackpush ( items x ) { pstacktype p 。 top = p 。 top = toppredecessor 。 2. 調(diào)用一次 stackpush(1) 得。 top: 1 . 2 b: 2 隊(duì)列 ? 如圖可用單向鏈表實(shí)現(xiàn)隊(duì)列，現(xiàn)在要用兩個(gè)指針變量，一個(gè)指向隊(duì)頭（ front），一個(gè)指向隊(duì)尾（ rear）。 typedef queuetype *pqueuetype 。 } void inqueue (item x) { pqueuetype p。 if ( rear==NULL ) { rear = p 。 } } void outgueue ( item *x ) { pqueuetype p。 front = front next。 3. 調(diào)用一次 outgueu