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