棧與隊(duì)列-資料下載頁(yè)
2024-10-17 14:53本頁(yè)面
【導(dǎo)讀】插入和刪除操作的線(xiàn)性表。稱(chēng)為棧頂，另一端稱(chēng)為棧底。則后進(jìn)棧的元素必然先出棧，頂指針標(biāo)志棧頂位置。儲(chǔ)在棧頂指針top中，它隨著元素進(jìn)棧出棧而變化。為-1表示空棧，top等于stacksize-1則表示棧滿(mǎn)。若棧不空，則刪除棧頂元素，用result返回其值。假定表達(dá)式是由加減乘除和數(shù)字構(gòu)成。達(dá)式都可寫(xiě)成前綴式或后綴式。用前綴式或后綴式更為簡(jiǎn)單。S1OPS2并將結(jié)果入棧，繼續(xù)讀取后綴式。只應(yīng)該有一個(gè)數(shù)據(jù)，即結(jié)果數(shù)據(jù)。出棧，計(jì)算2*9后將結(jié)果18入棧。程序來(lái)求解該算式的結(jié)果?？崭褡鳛閮蓚€(gè)操作數(shù)的分隔符；若遇到運(yùn)算符，括號(hào)，則一直退棧輸出，直到退到左括號(hào)止。現(xiàn)在用棧來(lái)實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果如下：
【正文】 an ∧ front rear 非空鏈隊(duì)列 鏈隊(duì)列的結(jié)點(diǎn)可定義如下： struct QNode { ElemType data。 struct QNode *next。 }。 鏈隊(duì)列有兩個(gè)指針 ， 因此可采用下面定義 : class LinkQueue { public: QNode *front。 // 隊(duì)頭指針 QNode *rear。 // 隊(duì)尾指針 ( 下頁(yè)繼續(xù) …… ) ( 接上頁(yè) ) LinkQueue() { front = new QNode。 //建立頭結(jié)點(diǎn) frontnext=NULL。 rear = front。 //尾指針也指向頭結(jié)點(diǎn) } int Length()。 //求隊(duì)列長(zhǎng)度 void EnQueue(ElemType x)。 //入隊(duì)操作 void DeQueue (ElemType amp。e)。 //出隊(duì)操作 void GetHead(ElemType amp。e)。 //求隊(duì)頭元素 }。 （ 1） 求隊(duì)列的長(zhǎng)度 返回隊(duì)列的元素個(gè)數(shù) ， 即隊(duì)列的長(zhǎng)度 。 int LinkQueue::Length() { QNode * p=front。 int len=0。 while(p!=rear){ len++。 p= pnext。 } return len。 } （ 2） 入隊(duì)列操作 插入元素 x為隊(duì)列新的隊(duì)尾元素 。 void LinkQueue::EnQueue(ElemType x) { QNode *s=new QNode。 //建立新結(jié)點(diǎn) s sdata = x。 snext =NULL。 rear next = s。 //在隊(duì)尾插入結(jié)點(diǎn) s rear = s。 //修改隊(duì)尾指針 } （ 3） 出隊(duì)列操作 若隊(duì)列不空 ， 則刪除隊(duì)頭元素 ， 用 e返回其值 。 void LinkQueue::DeQueue (ElemType amp。e) { QNode *p。 if( front== rear) cout隊(duì)列已空 。 else { p= frontnext。 e=pdata。 frontnext=pnext。 if(rear==p) rear=front。 delete p。 } } 刪除最后一個(gè)元素時(shí) ， 需要修改尾指針 ， 使其指向頭結(jié)點(diǎn) （ 4） 取隊(duì)頭元素 若隊(duì)列不空 ， 則用 e返回隊(duì)頭元素； void LinkQueue::GetHead(ElemType amp。e) { QNode *p。 if(front==rear) cout隊(duì)列已空 。 else { p= frontnext。 e=pdata。 } } 求 k階斐波那切數(shù)列某一項(xiàng) k階斐波那切數(shù)列 {ai}定義如下： 解決方法 : 建立一個(gè)容量為 k的循環(huán)隊(duì)列，將前 k個(gè)元素依次入隊(duì)。然后計(jì)算第 k+1個(gè)元素，它等于隊(duì)列中全部元素之和。而后將對(duì)頭元素出隊(duì)，將第k+1個(gè)元素入隊(duì)。重復(fù)上述過(guò)程，就可求得任意指定項(xiàng)元素的值 。 【 例 24】 利用循環(huán)隊(duì)列求 k階斐波那切數(shù)列某一式的值。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1