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