【正文】 = p 。 rear = p 。 } } void outgueue ( item *x ) { pqueuetype p。 if ( front==NULL ) printf( ―隊空 \n‖ )。 else { *x = front data 。 p = front 。 front = front next。 if ( front==NULL ) rear = NULL 。 free( p ) 。 } } 看一下這三個操作 : 1. 調(diào)用初始化后（調(diào)用一次 queueinitail） 得； 2. 調(diào)用一次 ingueue(1)得； 再調(diào)用一次 ingueue(2)得； 再調(diào)用一次 ingueue(3)得 。 3. 調(diào)用一次 outgueue(amp。a) 得； 再調(diào)用一次 outgueue(amp。b) 得 。 再調(diào)用一次 outgueue(amp。a) 得 。 1 a: rear: front: 2 3 1 p: b: 2 3NULL NULL 鏈表 ——linkage table base: 1 . 2 N1 N ... 雙向鏈 base: 1 2 N1 N ... 單向鏈 base: 1 2 N1 N ... 環(huán)形鏈 base: 1 2 N1 N ... 雙向 環(huán)形鏈 實際上前邊講的棧，隊列都是單向鏈表，但是棧和隊列只是單向鏈表的兩種特殊應(yīng)用 ——操作只在頭尾進行。下邊介紹單向鏈表的一般操作 : ? 創(chuàng)建單向鏈表 : 創(chuàng)建單向鏈表，是指用一項一項的數(shù)據(jù)逐步建立、形成一個鏈表?？梢苑殖上蜴滎^加入數(shù)據(jù)和向鏈尾加入數(shù)據(jù)兩種方式。 創(chuàng)建單向鏈表可以分成向鏈頭加入數(shù)據(jù)和向鏈尾加入數(shù)據(jù)兩種方式。新項加入鏈頭就是壓棧的算法；新項加入鏈尾就是隊列中入隊的算法。只要反復(fù)調(diào)用那里的函數(shù)或?qū)⒑瘮?shù)體放在循環(huán)語句中即可，這里不贅述。 ? 遍歷單向鏈表 : 遍歷是指從頭到尾將鏈表上數(shù)據(jù)全部加工一遍?？捎萌缦伦蠖说乃惴ā５珜嵱弥?，經(jīng)常用如下右端 的算法來遍歷單向鏈表。 p = base 。 p0 = NULL。 while (p != NULL ) { p = base 。 加工 p while (p != NULL ) { p = p next。 加工 p } p0 = p 。 p = p next。 } ? 在單向鏈表上檢索 : 檢索是指在單向鏈表上查找關(guān)鍵字等于某給定值的節(jié)點 , 若找到則帶回相應(yīng)節(jié)點的指針；否則帶回 NULL 。設(shè)關(guān)鍵字域域名為 key ；欲檢索的關(guān)鍵字值為 key0 . 如下算法實現(xiàn)檢索： p0 = NULL。 p = base 。 while (p != NULL amp。amp。 pkey !=key0 ) { p0 = p。 p = p next。 } ? 向單向鏈表插入一項 : 設(shè)有下圖的鏈表，現(xiàn)在要把 r所指示的數(shù)據(jù)項插入到 p0、 p 所指兩項之間。操作是 : r next = p 。 p0 next = r 。 p0 = r /* 使 p0 仍為 p 的前一項 */ r: 5 p0: p: 1 2 3 4 ... ... ? 從單向鏈表上刪除一項 : 設(shè)有下圖的鏈表，現(xiàn)在要刪除 p所指項。刪除算法是： q = p 。 p = p next 。 p0 next = p 。 free(q) p0: 1 2 3 4 ... ... p: q: ? 交換單向鏈表上兩項 : 設(shè)有如圖所示鏈表?，F(xiàn)在要把 p 所指的項與 q 所指的項交換 為了表示操作方便，我們把該鏈表分兩段畫出。 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。 /* 1 */ p next = q next。 /* 2 */ q next = g。 /* 3 */ /*交換 p0 next 、 q0 next */ p0 next = q。 /* 4 */ q0 next = p。 /* 5 */ /*交換 p 、 q */ p = p0 next 。 /* 6 */ q = q0 next 。 /* 7 */ 樹 ——tree ? 兩叉樹，兩叉樹的每個數(shù)據(jù)項附帶兩個指針，分別指向它的兩個分支。兩叉樹的定義 : – 空是樹； – 一個結(jié)點連接兩個不相交的樹 ,仍為樹； – 所有結(jié)點具有相同的數(shù)據(jù)類型。 * + a / d * b c e f ( a + b / c ) * ( d – e * f ) root: 設(shè) ti 為二叉樹的一個結(jié)點，一般 ti 由兩部分組成： ?基本數(shù)據(jù)部分 保存本結(jié)點上的基本數(shù)據(jù)； ?指針部分連 接本結(jié)點以下的其它結(jié)點。 結(jié)點 ti 的指針連接的結(jié)點稱為 ti 的 子結(jié)點 ， 相應(yīng) ti 稱為其子結(jié)點的 父結(jié)點 。 ti的指針部分有兩個指針：左指針、右指針。 稱 ti 的左指針連接的部分為 ti 的 左子樹 ， ti 的右指針連接的部分為 ti 的 右子樹 。 若左、右子樹均空，則稱 ti 為 葉結(jié)點 。 ti 7 8 5 6 3 1 2 4 ti: ? 為了檢索操作方便，一般把兩叉樹組織成兩叉檢索樹。兩叉檢索樹的定義是： – 設(shè)樹中每個結(jié)點的數(shù)據(jù)部分有一個數(shù)據(jù)項 key 是有序的 , 稱該數(shù)據(jù)項為關(guān)鍵字。 – 一個兩叉樹稱為檢索樹， – 如果對每個結(jié)點 ti ，它的左子樹中所有結(jié)點的 key 值都小于 ti 的 key 值； – ti 的右子樹中所有結(jié)點的 key 值都大于 ti 的 key 值。 ? 二叉檢索樹的操作有 : – 遍歷 – 檢索 – 插入一個結(jié)點 – 刪除一個結(jié)點 由于樹是遞歸定義的，所以樹的操作用遞歸算法十分簡潔。 設(shè)有說明部分 : typedef ... keytype ； typedef ... datatype ； typedef struct tree { keytype key ； datatype data ； struct tree *left ； struct tree *right ； }treetype。 typedef treetype * treepointer ； treepointer root ； ? 遍歷 遍歷二叉樹是指按一定規(guī)律走遍樹的每個結(jié)點，使每一結(jié)點被訪問一次，而且只被訪問一次。在訪問一個結(jié)點時，可以做任何信息加工工作。下例打印結(jié)點的 data域，并設(shè)該域為 char型的。 ? 遍歷算法可分為前序，中序，后序遍歷三種。 – 前序遍歷 ：對任意一個結(jié)點 ti 來講，先訪問及處理該結(jié)點的數(shù)據(jù)域；然后遍歷左子樹；最后遍歷右子樹。 – 中序遍歷 ：對任意一個結(jié)點 ti 來講，先遍歷左子樹；然后訪問及處理該結(jié)點的數(shù)據(jù)域；最后遍歷右子樹。 – 后序遍歷 ：對任意一個結(jié)點 ti 來講，先遍歷左子樹；然后遍歷右子樹；最后訪問及處理該結(jié)點的數(shù)據(jù)域。 【 例 121】 設(shè)有下圖所示樹 ,這是由表達式 (a+b/c)*(de*f) 生成的樹，這棵樹反映了表達式的結(jié)構(gòu)，同時也反映了表達式的運算次序。 ? 前序遍歷過程是：得到表達式的波蘭表示式（運算符在兩個運算分量前）。 ?前序遍歷算法是： void preorder (treepointer p) { if ( p!=NULL ) { printf(―%c‖ , p data ) 。 preorder( p left ) 。 preorder( p right ) } } * + a / d * b c e f ＊ ＋ a / b c d * e f ? 中序遍歷過程是： 得到表達式的原形式，只是沒有括號。 中序遍歷算法是： void inorder (treepointer p) { /*中序遍歷 */ if ( p!=NULL ) { inorder( p left ) 。 printf(―%c‖ , p data ) 。