[計算機軟件及應(yīng)用]棧和隊列(編輯修改稿)
2025-11-12 23:17 本頁面
【文章內(nèi)容簡介】 檢驗表達式中的括號匹配情況 假設(shè)在一個算術(shù)表達式中，可以包含三種括號：圓括號“（”和“）”，方括號“ [”和“ ]”和花括號“ {”和“ }”，并且這三種括號可以按任意的次序嵌套使用。比如， ...[...{...}...[...]...]...[...]...(...)..?，F(xiàn)在需要設(shè)計一個算法，用來檢驗在輸入的算術(shù)表達式中所使用括號的合法性。 算術(shù)表達式中各種括號的使用規(guī)則為：出現(xiàn)左括號，必有相應(yīng)的右括號與之匹配，并且每對括號之間可以嵌套，但不能出現(xiàn)交叉情況。我們可以利用一個棧結(jié)構(gòu)保存每個出現(xiàn)的左括號，當(dāng)遇到右括號時，從棧中彈出左括號，檢驗匹配情況。在檢驗過程中，若遇到以下幾種情況之一，就可以得出括號不匹配的結(jié)論。 （ 1）當(dāng)遇到某一個右括號時，棧已空，說明到目前為止，右括號多于左括號； （ 2）從棧中彈出的左括號與當(dāng)前檢驗的右括號類型不同，說明出現(xiàn)了括號交叉情況； （ 3）算術(shù)表達式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。 下面是解決這個問題的完整算法。 typedef char StackEntry。 int Check( ) { STACK S。 //定義棧結(jié)構(gòu) S char ch。 InitStack(amp。S)。 //初始化棧 S while ((ch=getchar())!=?\n?) { //以字符序列的形式輸入表達式 switch (ch) { case(ch==?(?||ch== ?[?||ch== ?{?): Push(amp。S,ch)。break。 //遇左括號入棧 //在遇到右括號時 ， 分別檢測匹配情況 case (ch== ?)?): if (StackEmpty(S)) retrun FALSE。 else {Pop(amp。S,amp。ch)。 if (ch!= ?(?) return FALSE。 } break。 case (ch== ?]?): if (StackEmpty(S)) retrun FALSE。 else {Pop(amp。S,amp。ch)。 if (ch!= ?[?) return FALSE。 } break。 case (ch== ?}?): if (StackEmpty(S)) retrun FALSE。 else {Pop(amp。S,amp。ch)。 if (ch!= ?{?) return FALSE。 } break。 default:break。 } } if (StackEmpty(S)) return TRUE。 else return FALSE。 } 隊列 隊列的定義 隊列特殊性在于限定插入在線性表的一端進行，刪除在線性表的另外一端進行。如圖 35所示： a 1 a 2 a 3 ... a i ... a n1a n插入端 刪除端圖 35 插入端和刪除端都是浮動的。通常我們將插入端稱為 隊尾 ，用一個“隊尾指針”指示；而刪除端被稱為 隊頭 ，用一個“隊頭指針”指示。 結(jié)論： 先進先出 （ First In First Out），簡稱為FIFO線性表。 舉例 1：到醫(yī)院看病，首先需要到掛號處掛號，然后，按號碼順序救診。 舉例 2：乘坐公共汽車，應(yīng)該在車站排隊，車來后，按順序上車。 舉例 3：在 Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個應(yīng)用程序響應(yīng)一系列的“消息”，像用戶點擊鼠標(biāo)；拖動窗口這些操作都會導(dǎo)致向應(yīng)用程序發(fā)送消息。為此，系統(tǒng)將為每個應(yīng)用程序創(chuàng)建一個隊列，用來存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過程就是不斷地從隊列中讀取消息，并依次給予響應(yīng)。 下面我們給出隊列結(jié)構(gòu)的基本操作： InitQueue(amp。Q) 操作結(jié)果：構(gòu)造一個空隊列 Q。 QueueEmpty(Q) 初始條件：隊列 Q 已存在。 操作結(jié)果：若 Q 為空隊列，則返回 TRUE，否則返回 FALSE。 Delete(amp。Q,amp。e) 初始條件： Q 為非空隊列。 操作結(jié)果：刪除 Q 的隊頭元素，并用 e 返回其值。 QueueLength(Q) 初始條件：隊列 Q 已存在。 操作結(jié)果：返回 Q 的元素個數(shù)，即隊列的長度。 GetHead(Q,amp。e) 初始條件： Q 為非空隊列。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1