[計(jì)算機(jī)軟件及應(yīng)用]棧和隊(duì)列-在線(xiàn)瀏覽
2024-12-03 23:17本頁(yè)面
【正文】 kEmpty(S)) exit(“Stack is empty”)。 } 4. 獲取棧頂元素內(nèi)容 void GetTop(STACK *S,StackEntry amp。 else item=Sitems[Stop]。 else FALSE。 else FALSE。 棧的鏈?zhǔn)酱鎯?chǔ) 若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈棧通常用一個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表表示。 由于棧的插入刪除操作只能在一端進(jìn)行，而對(duì)于單鏈表來(lái)說(shuō)，在首端插入刪除結(jié)點(diǎn)要比尾端相對(duì)地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。 //棧的數(shù)據(jù)元素類(lèi)型 struct node *next。 typedef struct stack{ NODE *top。 下面我們將給出鏈棧各項(xiàng)基本操作的算法。 } 2. 入棧 void Push(STACK *S,StackEntry item) { p=(NODE*)malloc(sizeof(NODE))。 else { pdata=item。 Stop=p。 else { *item=Stopdata。 Stop=pnext。 } } 4. 獲取棧頂元素內(nèi)容 void GetTop(STACK S,StackEntry *item) { if (StackEmpty(S)) exit(“Stack is empty”)。 } 5. 判斷棧 S是否空 int StackEmpty(STACK S) { if (==NULL) return TRUE。 } 棧的應(yīng)用舉例 【 舉例 1】 將從鍵盤(pán)輸入的字符序列逆置輸出 比如，從鍵盤(pán)上輸入： tset a si sihT；算法將輸出：This is a test 【 舉例 2】 十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制 使用展轉(zhuǎn)相除法將一個(gè)十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。最后將所有的余數(shù)反向輸出就是所對(duì)應(yīng)的二進(jìn)制數(shù)值。 void Decimal _ Binary ( ) { STACK S。S)。 //輸入十進(jìn)制正整數(shù) while (data) { Push(amp。 //余數(shù)入棧 data/=2。S,amp。 printf(“%d”,data)。比如， ...[...{...}...[...]...]...[...]...(...)..。 算術(shù)表達(dá)式中各種括號(hào)的使用規(guī)則為：出現(xiàn)左括號(hào)，必有相應(yīng)的右括號(hào)與之匹配，并且每對(duì)括號(hào)之間可以嵌套，但不能出現(xiàn)交叉情況。在檢驗(yàn)過(guò)程中，若遇到以下幾種情況之一，就可以得出括號(hào)不匹配的結(jié)論。 下面是解決這個(gè)問(wèn)題的完整算法。 int Check( ) { STACK S。 InitStack(amp。 //初始化棧 S while ((ch=getchar())!=?\n?) { //以字符序列的形式輸入表達(dá)式 switch (ch) { case(ch==?(?||ch== ?[?||ch== ?{?): Push(amp。break。 else {Pop(amp。ch)。 } break。 else {Pop(amp。ch)。 } break。 else {Pop(amp。ch)。 } break。 } } if (StackEmpty(S)) return TRUE。 } 隊(duì)列 隊(duì)列的定義 隊(duì)列特殊性在于限定插入在線(xiàn)性表的一端進(jìn)行，刪除在線(xiàn)性表的另外一端進(jìn)行。通常我們將插入端稱(chēng)為 隊(duì)尾 ，用一個(gè)“隊(duì)尾指針”指示；而刪除端被稱(chēng)為 隊(duì)頭 ，用一個(gè)“隊(duì)頭指針”指示。 舉例 1：到醫(yī)院看病，首先需要到掛號(hào)處掛號(hào)，然后，按號(hào)碼順序救診。 舉例 3：在 Windows這類(lèi)多任務(wù)的操作系統(tǒng)環(huán)境中，每個(gè)應(yīng)用程序響應(yīng)一系列的“消息”，像用戶(hù)點(diǎn)擊鼠標(biāo)；拖動(dòng)窗口這些操作都會(huì)導(dǎo)致向應(yīng)用程序發(fā)送消息。 下面我們給出隊(duì)列結(jié)構(gòu)的基本操作： InitQueue(amp。 QueueEmpty(Q) 初始條件：隊(duì)列 Q 已存在。 Delete(amp。e) 初始條件： Q 為非空隊(duì)列。 QueueLength(Q)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1