【正文】 } void outgueue ( item *x ) { pqueuetype p。 else { *x = front data 。 front = front next。 free( p ) 。 3. 調(diào)用一次 outgueue(amp。b) 得 。a) 得 。 a: rear: front: 2 1 p: b: 2 3NULL NULL 鏈表 ——linkage table base: 1 . 2 N1 N 下邊介紹單向鏈表的一般操作 : ? 創(chuàng)建單向鏈表 : 創(chuàng)建單向鏈表，是指用一項(xiàng)一項(xiàng)的數(shù)據(jù)逐步建立、形成一個(gè)鏈表。 創(chuàng)建單向鏈表可以分成向鏈頭加入數(shù)據(jù)和向鏈尾加入數(shù)據(jù)兩種方式。只要反復(fù)調(diào)用那里的函數(shù)或?qū)⒑瘮?shù)體放在循環(huán)語句中即可，這里不贅述。可用如下左端的算法。 p = base 。 while (p != NULL ) { p = base 。 加工 p } p0 = p 。 } ? 在單向鏈表上檢索 : 檢索是指在單向鏈表上查找關(guān)鍵字等于某給定值的節(jié)點(diǎn) , 若找到則帶回相應(yīng)節(jié)點(diǎn)的指針；否則帶回 NULL 。 p = base 。amp。 p = p next。操作是 : r next = p 。 p0 = r /* 使 p0 仍為 p 的前一項(xiàng) */ r: 5 p0: p: 1 2 3 4 ... ... ? 從單向鏈表上刪除一項(xiàng) : 設(shè)有下圖的鏈表，現(xiàn)在要?jiǎng)h除 p所指項(xiàng)。 p = p next 。 free(q) p0: 1 2 3 4 ... ... p: q: ? 交換單向鏈表上兩項(xiàng) : 設(shè)有如圖所示鏈表。 p0 p 1 2 3 ... q0 q 4 5 6 ... ... p0: p: 1 2 3 ... q0 q: 4 5 6 ... … … g: /*交換 p next 、 q next */ g = p next。 /* 2 */ q next = g。 /* 4 */ q0 next = p。 /* 6 */ q = q0 next 。兩叉樹的定義 : – 空是樹； – 一個(gè)結(jié)點(diǎn)連接兩個(gè)不相交的樹 ,仍為樹； – 所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類型。 設(shè) ti 為二叉樹的一個(gè)結(jié)點(diǎn)，一般 ti 由兩部分組成： ?基本數(shù)據(jù)部分 保存本結(jié)點(diǎn)上的基本數(shù)據(jù)； ?指針部分連 接本結(jié)點(diǎn)以下的其它結(jié)點(diǎn)。 ti的指針部分有兩個(gè)指針：左指針、右指針。 若左、右子樹均空，則稱 ti 為 葉結(jié)點(diǎn) 。兩叉檢索樹的定義是： – 設(shè)樹中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)部分有一個(gè)數(shù)據(jù)項(xiàng) key 是有序的 , 稱該數(shù)據(jù)項(xiàng)為關(guān)鍵字。 ? 二叉檢索樹的操作有 : – 遍歷 – 檢索 – 插入一個(gè)結(jié)點(diǎn) – 刪除一個(gè)結(jié)點(diǎn) 由于樹是遞歸定義的，所以樹的操作用遞歸算法十分簡潔。 typedef treetype * treepointer ； treepointer root ； ? 遍歷 遍歷二叉樹是指按一定規(guī)律走遍樹的每個(gè)結(jié)點(diǎn)，使每一結(jié)點(diǎn)被訪問一次，而且只被訪問一次。下例打印結(jié)點(diǎn)的 data域，并設(shè)該域?yàn)?char型的。 – 前序遍歷 ：對(duì)任意一個(gè)結(jié)點(diǎn) ti 來講，先訪問及處理該結(jié)點(diǎn)的數(shù)據(jù)域；然后遍歷左子樹；最后遍歷右子樹。 – 后序遍歷 ：對(duì)任意一個(gè)結(jié)點(diǎn) ti 來講，先遍歷左子樹；然后遍歷右子樹；最后訪問及處理該結(jié)點(diǎn)的數(shù)據(jù)域。 ? 前序遍歷過程是：得到表達(dá)式的波蘭表示式（運(yùn)算符在兩個(gè)運(yùn)算分量前）。 preorder( p left ) 。 中序遍歷算法是： void inorder (treepointer p) { /*中序遍歷 */ if ( p!=NULL ) { inorder( p left ) 。 inorder( p right ) } } * + a / d * b c e f ＊ ＋ a / b c d * e f ? 后序遍歷過程是： 得到表達(dá)式的表達(dá)式的逆波蘭表示式（運(yùn)算符在兩個(gè)運(yùn)算分量之后）。 postorder( p right ) printf(―%c‖ , p data ) 。若檢索到，函數(shù)將帶回相應(yīng)結(jié)點(diǎn)指針；否則若沒檢索到，函數(shù)將帶回 NULL 。 treepointer search( typekey c , treepointer p ) { if ( ( p key == c ) || ( p == NULL ) ) return p 。 else return search( c , p right ) 。顯然，首先要按 key值查出應(yīng)該插入的位置，然后再插入。 (*p) key = c 。 (*p) left = NULL 。 }else if ( c (*p) key ) insert( c , d , amp。 else insert( c , d , amp。 } 由于 insert 的參數(shù) p 是指向指針的指針類型，在 insert 內(nèi) p 指向 指針類型的實(shí)在參數(shù) 。 1) 若調(diào)用 insert 時(shí)，如圖 root 為空樹。root 作實(shí)在參數(shù)調(diào)用 insert , 即 insert(c,d,amp。 轉(zhuǎn)插入功能，執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)) 得 : 再執(zhí)行后邊的幾個(gè)賦值語句 , 得 : root: c 。 ((*p)right) 作實(shí)在參數(shù)遞歸調(diào)用 insert，即執(zhí)行 insert(c,d, amp。 轉(zhuǎn)插入功能，執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)) 再執(zhí)行后邊的幾個(gè)賦值語句 , 得 : c 。 針對(duì)不同情況刪除算法不同 . r 是葉結(jié)點(diǎn) :簡單刪掉 r 結(jié)點(diǎn)，并把 r 的父結(jié)點(diǎn)連接處改成 NULL 即可 。 然后刪掉 r結(jié)點(diǎn) 。 9 s: 10 r: 4 5 14 15 12 13 3 1 2 11 8 6 7 9當(dāng)然也可以在 r的右子樹上找到關(guān)鍵字 key值最小的結(jié)點(diǎn)s，把 s結(jié)點(diǎn)的數(shù)據(jù) data及關(guān)鍵字 key復(fù)制到 r結(jié)點(diǎn)上，然后刪除掉 s結(jié)點(diǎn)。 ② 把該結(jié)點(diǎn) s 的值復(fù)制到結(jié)點(diǎn) r（即欲刪除 的結(jié)點(diǎn)。 ④ 刪除 s結(jié)點(diǎn)，即圖中的 (9)結(jié)點(diǎn)。 9 s: 10 r: 4 5 14 15 12 13 3 1 2 11 8 6 7 9 綜合上述三種情況，下述函數(shù) deletenode 完成刪除一個(gè)結(jié)點(diǎn)。root ) 其中 ? value_of_key是欲刪除結(jié)點(diǎn)的關(guān)鍵字值； ? root是指針類型（ treepointer）變量，指向樹根。 treepointer del( treepointer * , treepointer * )； /* 處理第三種情況的函數(shù)的函數(shù)原型 */ void deletenode( keytype c , treepointer *p ) { /* 刪除關(guān)鍵字值等于 c 的結(jié)點(diǎn) */ treepointer r。 else if ( c (*p) key ) /* c 當(dāng)前結(jié)點(diǎn)的 key 值，被刪結(jié)點(diǎn)在左子樹上 */ deletenode( c , amp。 else if ( c (*p) key ) /* c 當(dāng)前結(jié)點(diǎn)的 key 值，被刪結(jié)點(diǎn)在右子樹上 */ deletenode( c , amp。 else{ r = *p 。 /* 左子樹空，接右分支 */ else r=del( amp。 /* 左右均非空 */ free( r ) 。 4 5 6 2 7 1 3 8 root: p: deletenode( 4 , amp。 if ((*s)right != NULL ) /* 右分支非空 ? */ r=del( amp。 /* 復(fù)制 *s的關(guān)鍵字、數(shù)據(jù)到 *p結(jié)點(diǎn) */ (*p)data =(*s) data 。 /* r記載該 *s結(jié)點(diǎn)，為 free做準(zhǔn)備 */ *s =(*s) left ； /* 刪除 *s所指結(jié)點(diǎn)。 */ } return r。其中 , ?V=(v1 ,v2 , … ,vn) 為圖 G的結(jié)點(diǎn)集合 ?vi為圖 G中結(jié)點(diǎn) ?E={ (vi , vj ) |vi, vj∈ V} 是圖中邊的集合 ?(vi ,vj)表示連接結(jié)點(diǎn) vi到結(jié)點(diǎn) vj的邊。則 圖 G表示成右圖的鄰接表。 g i j [