【正文】 函數(shù)定義中 ， 被定義項 n！ 在定義中的應(yīng)用(n1)!具有比原來 n更小的 “ 尺度 ” n1；同時 n！ 在最小“ 尺度 ” 為 0上的定義由自然數(shù) 1直接定義不是遞歸的 。 這兩個條件實際上構(gòu)成了遞歸程序設(shè)計的基本原則 。 ?此外 ， 通常把反映條件 ② 的部分 （ 即遞歸結(jié)束條件 ） 寫在遞歸程序模塊的開頭處 。 遞歸的實現(xiàn) ——求階乘 (續(xù) ) ?許多實際問題是可以遞歸定義的 ， 對于這些問題很容易寫出它們的遞歸求解算法 。 ?計算階乘函數(shù)的遞歸算法如下： int fact(int n) {if(n==0) return 1。 else return n*fact(n1)。 } 遞歸的實現(xiàn) ——求階乘 (續(xù) ) ?遞歸函數(shù)的運行引起遞歸調(diào)用 。 ?例如 ， fact(4)的執(zhí)行中遞歸函數(shù)出現(xiàn)的調(diào)用 —返回過程如下圖所示： fact(4) fact(3) fact(2) fact(1) fact(0) 1 1 2 6 24 函數(shù) 調(diào)用與返回 返回值 函數(shù)的調(diào)用與返回 ?通常 ， 當(dāng)一個函數(shù)調(diào)用另一個函數(shù)時 ， 在執(zhí)行被調(diào)用函數(shù)前系統(tǒng)要預(yù)先做三件事情： ?將所有的實參和函數(shù)返回地址等信息傳遞給被調(diào)用函數(shù)； ?為被調(diào)用函數(shù)的局部變量分配存儲空間 ?將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口處 。 ?而在從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前 ， 系統(tǒng)也需要做如下三件事情： ?保存被調(diào)用函數(shù)的計算結(jié)果； ?釋放為被調(diào)用函數(shù)局部變量分配的數(shù)據(jù)空間； ?按返回地址將控制轉(zhuǎn)移給調(diào)用函數(shù) 。 函數(shù)的嵌套調(diào)用 ?當(dāng)多個函數(shù)構(gòu)成嵌套調(diào)用時 ， 系統(tǒng)按照先調(diào)用后返回的原則進行工作 。 ?這種信息的傳遞和控制轉(zhuǎn)移符合后進先出的原則 ，使用棧來實現(xiàn)是非常自然的 。 ?系統(tǒng)將整個程序運行期間所需要的存儲空間都利用一個工作棧來管理 ， 每當(dāng)調(diào)用 （ 或執(zhí)行 ） 一個函數(shù)時 ， 就為它在棧頂分配一個存儲區(qū)； ?每當(dāng)退出 （ 或執(zhí)行完 ） 一個函數(shù)時 ， 就釋放為它所分配的存儲區(qū)； ?當(dāng)前工作的函數(shù)的數(shù)據(jù)區(qū)總在工作棧的當(dāng)前棧頂位置 。 函數(shù)的嵌套調(diào)用時棧變化過程 ?函數(shù)嵌套調(diào)用時工作棧的變化情況如下圖 ， 其中的 1和 2表示返回地址 ， 是程序中的語句標號 。 遞歸函數(shù)的執(zhí)行過程 ?遞歸函數(shù)的執(zhí)行過程類似于嵌套調(diào)用時的情況 ，只不過是在直接遞歸時的調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)罷了 。 ?例如前述的 fact函數(shù) ， 從遞歸調(diào)用開始 ， 每遞歸調(diào)用深入一層 ， 就在工作棧的棧頂為所有形參局部變量和返回地址開辟空間保存 ， 每退出一層遞歸就從棧頂釋放為本層開辟的空間并返回調(diào)用層 。 ?由于是同一個函數(shù) ， 其返回地址應(yīng)為同一語句位置設(shè)為 r。 遞歸調(diào)用 fact(4)的工作棧變量情況 遞歸的實現(xiàn)小結(jié) ?利用遞歸算法 （ 函數(shù) 、 過程 、 子程序等 ） 編寫的程序具有結(jié)構(gòu)簡潔清晰 、 易讀易理解等優(yōu)點 。 ?然而由于使用棧來實現(xiàn)這種 “ 調(diào)用 —返回 ” 的遞歸過程 ， 無論在時間上還是在空間上都比相應(yīng)的非遞歸程序的開銷要大 。 ?因此人們往往是借助遞歸的思想來分析和設(shè)計算法 ，然后把設(shè)計好的遞歸算法借助程序中設(shè)立的棧轉(zhuǎn)化為非遞歸算法 ， 以提高程序的時間與空間效率 。 ?所以可以說 ， 棧是實現(xiàn)遞歸和轉(zhuǎn)化遞歸算法為非遞歸算法的有力工具 ， 而遞歸技術(shù)又是算法和程序的分析與設(shè)計的有力工具 。 第 3章 簡單數(shù)據(jù)結(jié)構(gòu) 順序表 鏈表 棧 隊列 廣義表 隊列 隊列的概念及其運算 順序隊列及運算實現(xiàn) 鏈隊列及運算實現(xiàn) 隊列的應(yīng)用舉例 ——I/O緩沖區(qū)管理及其它 隊列的概念 ?和棧類似 ， 隊列 （ queue） 也是一種操作受限的線性表 。 ?和棧不同的是 ， 隊列是限定所有的插入操作只能在表的一端進行 ， 而所有的刪除操作都只能在表的另一端進行 。 ?允許插入的一端叫做 隊尾 （ rear） ， ?允許刪除的一端叫做 隊頭 （ front） 。 ?新插入的元素只能添加到隊尾 ， 被刪除的只能是排在隊頭的元素 。 隊列的概念（續(xù)） ?如下圖所示的隊列中 ， a1是隊頭元素 ， an是隊尾元素 ， 元素以 a1,a2,… ,an的次序依次進入隊列 ， 而 a1是第一個出隊列的元素 。 ?即先進入隊列的元素總是先離開隊列 ， 或者說隊列的操作是按先進先出的原則進行的 。 ?因此 ， 隊列也稱作先進先出 （ First In First Out） 的線性表 ， 簡稱 FIFO表 。 隊列的概念（續(xù)） ?數(shù)據(jù)結(jié)構(gòu)中的隊列與現(xiàn)實生活中的排隊極為相似 。為了維護正常的社會秩序 ， 人們經(jīng)常要靠排隊來獲得某種服務(wù) ， 如購物 、 購票 、 打水 、 買飯 、 上車 、登機等等 。 ?排隊的規(guī)則是新加入的成員只能排在隊尾不允許“ 加塞兒 ” ；而且隊中全體成員只能按順序向前移動 ， 在到達隊頭得到服務(wù)后離隊 。 ?當(dāng)然 ， 在現(xiàn)實生活中的排隊時 ， 隊中任何成員可以“ 中途離隊 ” ； ?而對數(shù)據(jù)結(jié)構(gòu)中的隊列來說 ， 是不允許成員中途離隊的 ， 除此之外隊列與普通的隊完全一致 。 隊列的基本運算（五種） ?初始化隊列 iniqueue(q)：設(shè)置一個空隊列 q。 ?入隊列 addqueue(q,x)：把元素 x插入隊列 q中使 x成為新的隊尾元素 。 ?出隊列 outqueue(q)：若隊列 q不空 ， 則刪除隊頭元素并返回其值 ， 該隊頭元素的后繼成為新的隊頭元素；否則返回空元素 NULL。 ?讀隊頭元素 gethead(q)：若隊列 q不空返回隊頭元素的值 ， 否則返回空元素值 NULL。 ?判隊列空 empty(q)：若 q為空返回 1， 否則返回 0。 隊列 隊列的概念及其運算 順序隊列及運算實現(xiàn) 鏈隊列及運算實現(xiàn) 隊列的應(yīng)用舉例 ——I/O緩沖區(qū)管理及其它 順序隊列 ?隊列的順序存儲結(jié)構(gòu)實現(xiàn)稱作 順序隊列 。 ?與順序表一樣 ， 順序隊列也是用一維數(shù)組來存儲其數(shù)據(jù)元素的 。 ?由于隊列中數(shù)據(jù)元素的變化 ， 其隊頭和隊尾位置也隨之變化 ， 故需要設(shè)兩個指針分別指向當(dāng)前的隊頭和隊尾元素位置； ?為了方便運算 ， 通常約定隊尾指針 rear指向當(dāng)前隊尾元素的實際位置 ， 而隊頭指針 front指向當(dāng)前隊頭元素實際位置的前一個位置 。 順序隊列的類型定義 ?順序隊列的類型定義如下： typedef struct {elemtype queue[MAXSIZE]。 int front, rear。 }sequeue。 sequeue *q。 ?在這個定義之下 ， 入隊列的基本操作為隊列尾指針加 1后填入入隊列的元素 ， 即： qqueue[++qrear]=x。 ?出隊列的基本操作為隊列頭指針加 1， 即： qfront++。 ?隊列的長度 （ 即元素個數(shù) ） 為 qrear－ qfront， 隊列為空的條件是 qrear==qfront， ?而隊列滿的條件為 qrear－ qfront==MAXSIZE。 順序隊列的幾種狀態(tài) 順序隊列的 假溢出 ?由 順序隊列的幾種狀態(tài) 圖可以看出 ， 除了真正的隊滿之外還有一種假的隊滿如 (f)， 此時雖然 qrear－ qfrontMAXSIZE，但隊列尾指針已到達 MAXSIZE1， 再進行入隊操作時指針會越界 ， 而在所分配空間中還有部分尚無元素 ， 空間可以利用 ，把這種情況下發(fā)生的上溢稱之為 “ 假溢出 ” 。 ?產(chǎn)生假溢出的 原因 是由于被刪除元素所占用的空間使用不到 ，這種現(xiàn)象應(yīng)該設(shè)法避免 。 ?解決的辦法 是在每次刪除元素之后將整個隊列中的數(shù)據(jù)元素都向前依次移動一個元素位置 ， 或者在發(fā)生假溢出時再將隊列中所有數(shù)據(jù)元素向前移動 。 ?然而這樣做都會引起大量的元素移動 ， 所以實際應(yīng)用中很少使用這樣的方法 。 循環(huán)隊列 ?解決 “ 假溢出 ” 的常用辦法是將順序隊列假想成為一個首尾相接的圓環(huán) ， 即 qqueue[0]接在 qqueue[MAXSIZE1]之后 ，我們把這種設(shè)想之下的隊列稱之為 循環(huán)隊列 （ circular queue） 。 ?此時隊列的主要操作入隊列的指針變化為 if(qrear+1==MAXSIZE) qrear=0。 else qrear++。 ?或利用模運算簡潔地描述為 qrear=（ qrear+1） % MAXSIZE。 循環(huán)隊列（續(xù)） ?而出隊操作為 if(qfront+1==MAXSIZE) qfront=0。 else qfront++。 ?或簡記為 qfront=（ qfront+1） % MAXSIZE。 ?而此時的隊列空與隊列滿的條件都是 qrear==qfront，是無法區(qū)分 隊列空 和 隊列滿 這兩種不同狀態(tài)的 。 ?解決這一矛盾的辦法有設(shè)置隊列滿和隊列空的標志來區(qū)別是滿是空的；還有在類型定義中增加隊列長度域 ， 利用隊列長度值來區(qū)分是滿是空 。 解決循環(huán)隊列的隊空和隊滿矛盾 ?常用的是一種更簡潔的方法 ， 在入隊列前測試隊尾指針加 1是否等于隊頭指針 ， 相等時認為隊列滿 ， 即（（ qrear+1） % MAXSIZE==qfront時隊列滿；少使用一個元素空間區(qū)分了隊列滿與空 ， 避免了隊列滿與空條件一致的矛盾 ， 顯然比設(shè)置標志和利用隊列長度兩種方法時間效率更高 。 ?需要說明的是 ， 順序隊列的常用形式就是 循環(huán)隊列 ，循環(huán)隊列中的元素個數(shù) （ 即隊列長度 ） 為 (qrearqfront+MAXSIZE)%MAXSIZE。 循環(huán)隊列的幾種狀態(tài) 順序隊列的基本運算 —初始化 ?初始化算法：只要將隊頭和隊尾指針同時指向 0到MAXSIZE1的任一位置即可 。 void iniqueue(sequeue *q) { qfront=0。 qrear=0。 } 順序隊列的基本運算 —入隊列 ?入隊列算法：若隊列未滿插入隊尾并返回入隊成功標志 1， 否則返回隊列已滿入隊不成功標志 0。 int addqueue(sequeue *q,elemtype x) {if((qrear+1)%MAXSIZE==qfront) return 0。 /*隊列已滿無法插入返回 0*/ else {qrear=(qrear+1)%MAXSIZE。 qqueue[qrear]=x。 return 1。 /*返回插入成功標志 1*/ } } 順序隊列的基本運算 —出隊列 ?出隊列算法：若隊列不空 ， 刪除隊頭元素并返回其值 ， 否則返回 NULL。 elemtype outqueue(sequeue *q) {if(qrear==qfront) return NULL。 else {qfront=(qfront+1)%MAXSIZE。 return qqueue[qfront]。 } } 順序隊列的基本運算 —讀隊頭元素 ?讀隊頭元素：與出隊列的差別僅在于沒有修改隊頭指針 。 elemtype getqueue(sequeue *q) {if(qrear==qfront) return NULL。 else return qqueue[(qfront+1)%MAXSIZE]。 } 順序隊列的基本運算 —判隊列空 ?判隊列空算法：若隊列為空返回 1否則返回 0。 int empty(sequeue *q) {if(qrear==qfront) return 1。 else return 0。 } 隊列 隊列的概念及其運算 順序隊列及運算實現(xiàn) 鏈隊列及運算實現(xiàn) 隊列的應(yīng)用舉例 ——I/O緩沖區(qū)管理及其它 鏈隊列 ?隊列的鏈式存儲結(jié)構(gòu)實現(xiàn)稱作 鏈隊列 。 與鏈棧類似 ， 鏈隊列實質(zhì)上也是單鏈表 。 ?為了操作上的方便 ， 根據(jù)隊列的 FIFO特點 ， 需要設(shè)隊頭和隊尾兩個指針 ， 并把這兩個指針封裝在同一個結(jié)構(gòu)體內(nèi)； ?此外 ， 常采用帶頭結(jié)點的單鏈表