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