第3單元線(xiàn)性數(shù)據(jù)結(jié)構(gòu)二主講：劉志強(qiáng)-文庫(kù)吧資料
2024-11-01 15:18本頁(yè)面
【正文】 eue( ) { int x。 不為 1,修改頭指針 。若空 ,則顯示 隊(duì)列 ‘ 下溢 ’ 。 當(dāng)隊(duì)列長(zhǎng)度為 1時(shí) ,除了修改隊(duì)頭指針外 ,還要修改隊(duì)尾指針。 } } 下一頁(yè) 上一頁(yè) 停止放映 第 56/89 頁(yè) 鏈隊(duì)列的出隊(duì)操作 當(dāng)隊(duì)列長(zhǎng)度大于 1時(shí) ,只修改隊(duì)頭指針即可。 t data = x。 } else { rear next = t。 if （ t = = NULL） { printf（ ? 內(nèi)存無(wú)可用空間 \n”)。 下一頁(yè) 上一頁(yè) 停止放映 第 55/89 頁(yè) 鏈隊(duì)列的入隊(duì)操作 addqueue(int x) { QNODE *t。若空 ,表示 隊(duì)列已滿(mǎn) 。 下一頁(yè) 上一頁(yè) 停止放映 第 54/89 頁(yè) 鏈隊(duì)列的入隊(duì)操作 算法 114描述 : step1 申請(qǐng)建立一個(gè)新結(jié)點(diǎn) T。 y = 1 ； } else { front = front % MAXSIZE +1 ； y = queue[front] ； } return y ； } 下一頁(yè) 上一頁(yè) 停止放映 第 51/89 頁(yè) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 用帶頭結(jié)點(diǎn)的單鏈表作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)，稱(chēng)為隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 下一頁(yè) 上一頁(yè) 停止放映 第 50/89 頁(yè) 循環(huán)隊(duì)列出隊(duì)操作程序 delqueue( ) { int y。若空 ,則顯示隊(duì)列 ‘ 下溢 ’ 。 queue[rear] = x 。 exit(1)。 step2 隊(duì)尾指針后移一個(gè)位置 ,將新結(jié)點(diǎn)元素值存入當(dāng)前結(jié)點(diǎn)單元。 else rear＝ rear + 1。 else front ＝ front + 1。 這樣構(gòu)成循環(huán)隊(duì)列。 下一頁(yè) 上一頁(yè) 停止放映 第 44/89 頁(yè) 循環(huán)隊(duì)列 設(shè)定 queue[1]接在 queue[MAXSIZE]之后 ,使得 if （ rear MAXSIZE ） rear = 1 。 else rear = rear + 1 。 front front rear D E F G H rear 下一頁(yè) 上一頁(yè) 停止放映 第 43/89 頁(yè) 解決假溢出的方法 如果使當(dāng) rear = MAXSIZE+1 時(shí)，即超過(guò)隊(duì)列末端時(shí)，令 rear = 1；從而使隊(duì)列的首尾相連接。 front = front +1 ； x = queue [front ]； front rear a1 a2 … a n 下一頁(yè) 上一頁(yè) 停止放映 第 41/89 頁(yè) 舉例：順序隊(duì)列的入隊(duì)、出隊(duì)操作 （ A）空隊(duì)列 （ B） A、 B、 C、 D、 E入隊(duì) （ C） A、 B、 C出隊(duì) A B C D E front rear front rear D E front rear 入隊(duì)時(shí)， rear在變 出隊(duì)時(shí)， front在變 下一頁(yè) 上一頁(yè) 停止放映 第 42/89 頁(yè) 舉例 :順序隊(duì)列入隊(duì)、出隊(duì)操作 （ D） F、 G、 H入隊(duì) (E） D、 E、 F、 G、 H出隊(duì)，出現(xiàn)假 ? 溢出 ? 注： 一方面隊(duì)列中是空的，另一方面又出現(xiàn)溢出。 下一頁(yè) 上一頁(yè) 停止放映 第 40/89 頁(yè) 關(guān)于隊(duì)列表示的約定 為解決這個(gè)問(wèn)題，約定如下： 隊(duì)頭指針 front總是指向隊(duì)頭元素的前一個(gè)位置； 隊(duì)尾指針 rear總是指向隊(duì)尾元素的位置。 下一頁(yè) 上一頁(yè) 停止放映 第 39/89 頁(yè) 關(guān)于隊(duì)列表示的約定 問(wèn)題： 讀第 1個(gè)元素時(shí)： front = front +1 x = queue[front]； front = front +1； 讀其它元素時(shí)： x = queue[front]； front = front +1； 顯然，對(duì)于第 1個(gè)元素和其它元素的讀操作，將出現(xiàn)不一致。 front為隊(duì)頭指針 ,指示隊(duì)頭元素的位置 。非空 ,取值為 .F.。 隊(duì)列具有先進(jìn)先出（ FIFO）的特點(diǎn)。 進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。 注： 這是一個(gè)遞歸問(wèn)題， n階問(wèn)題可以分解為 n圓盤(pán)和 n1階問(wèn)題。現(xiàn)要求將 X軸上的 n個(gè)圓盤(pán)移至 Z塔上，并按同樣順序疊排。 } fac(1) fac(2) fac(3) fac(4) fac(5) top 1 fac(1)=1 2*fac(1) fac(2)=2*fac(1) 3*fac(2) fac(3)=3*fac(2) 4*fac(3) fac(4)=4*fac(3) 5*fac(4) fac(5)=5*fac(4) 下一頁(yè) 上一頁(yè) 停止放映 第 30/89 頁(yè) 舉例 3（子程序的嵌套調(diào)用） 有一主程序 main（）調(diào)用子程序示意圖如下： main sub1 sub2 sub3 end end end end sub3 sub2 sub1 main top 下一頁(yè) 上一頁(yè) 停止放映 第 31/89 頁(yè) 舉例 4 N階 Hanoi塔問(wèn)題 假設(shè)有 X、 Y、 Z三座塔。 舉例，計(jì)算： 3*（ 72） 輸入： 3*（ 72） 下一頁(yè) 上一頁(yè) 停止放映 第 28/89 頁(yè) 計(jì)算表達(dá)式的處理步驟 步驟 OPTR棧 OPND棧 輸入字符 主要操作 1 3 PUSH（ OPND， 3） 2 3 * PUSH（ OPTR，‘ *’） 3 * 3 （ PUSH（ OPTR，‘（’） 4 *（ 3 7 PUSH（ OPND， 7） 5 *（ 37 PUSH（ OPTR，‘ ?） 6 *（ 37 2 PUSH（ OPND， 2） 7 *（ 372 ） Operate（ 7，‘ ?， 2） 8 *（ 35 ） POP（ OPTR） 9 * 35 Operate（ 3，‘ *’， 5） 10 15 RETURN（ GETTOP（ OPND）） 表達(dá)式處理 3*(72) 下一頁(yè) 上一頁(yè) 停止放映 第 29/89 頁(yè) 舉例 2（遞歸過(guò)程實(shí)現(xiàn)） 計(jì)算 5的階乘（ 5！ =5X4X3X2X1） fac(long n) { if ( n = = 1) return (1)。 } } 下一頁(yè) 上一頁(yè) 停止放映 第 25/89 頁(yè) 棧的應(yīng)用 表達(dá)式計(jì)算 子程序的嵌套調(diào)用 參數(shù)傳遞 鍵盤(pán)緩沖區(qū) 遞歸過(guò)程的實(shí)現(xiàn) 下一頁(yè) 上一頁(yè) 停止放映 第 26/89 頁(yè) 舉例 1 表達(dá)式計(jì)算 計(jì)算表達(dá)式，首先要正確地定義運(yùn)算規(guī)則： – 先乘除、后加減 – 從左到右 – 先括號(hào)內(nèi)，再括號(hào)外 為了讓計(jì)算機(jī)能識(shí)別表達(dá)式，規(guī)定： – 表達(dá)式由操作數(shù)（ Operand）和操作符（ Operator）和定界符（ Delimiter）組成。 if( top = = NULL ) { printf(“棧溢出 \n”）； exit(1)。 下一頁(yè) 上一頁(yè) 停止放映 第 24/89 頁(yè) 算法 111 出棧操作程序 pop (SNODE * top) { SNODE *p。 step2 刪除 top所指結(jié)點(diǎn)，并使 top 指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)。 top= t
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1