棧和隊(duì)列ppt課件(2)(存儲(chǔ)版)
【正文】 yq(qu) 39 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) ? 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序隊(duì)，它由一個(gè)一維數(shù)組（用于存儲(chǔ)隊(duì)列中元素）及兩個(gè)分別指示隊(duì)頭和隊(duì)尾的變量組成， ? 這兩個(gè)變量分別稱為“隊(duì)頭指針”和“隊(duì)尾指針”（注意它們并非指針變量，而是數(shù)組的下標(biāo)）。 ? 為了能夠充分地使用數(shù)組中的存儲(chǔ)空間 ,把數(shù)組的前端和后端連接起來 ,形成一個(gè)環(huán)形的順序表 ,即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán) ,稱為 環(huán)形隊(duì)列 。 47 在環(huán)形隊(duì)列中 ,實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下 : (1)初始化隊(duì)列運(yùn)算算法 其主要操作是：創(chuàng)建一個(gè)隊(duì)列結(jié)點(diǎn) ， 用 sq指向該隊(duì)列結(jié)點(diǎn) ， 并指定 sqfront=sqrear=0 void InitQueue(SqQueue *amp。 return 1。 int GetHead(SqQueue *sq,ElemType amp。 隊(duì)列中最多能容納多少個(gè)元素？ 設(shè)計(jì)實(shí)現(xiàn)隊(duì)列基本運(yùn)算算法。 sqdata[(sqfront+sqcount)%QueueSize]=x。 } int GetHead(SqQueue *sq,ElemType amp。 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 58 ∧ ∧ f ro n t re a r q (a) 鏈隊(duì)初態(tài) f ro n t re a r q (b) 入隊(duì) 3 個(gè)元素 a b ∧ c f ro n t re a r q (c) 出隊(duì) 1 個(gè)元素 b ∧ c 鏈列的入隊(duì)和出隊(duì)操作示意圖 59 鏈隊(duì)的類型定義如下 : typedef struct QNode { ElemType data。 60 在鏈隊(duì)上實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下 : (1)初始化隊(duì)列運(yùn)算算法 其主要操作是：置結(jié)點(diǎn) lq*的 rear和 front均為 NULL: void InitQueue(LinkQueue *amp。 if (lqfront==NULLamp。 if (lqfront==NULL amp。 return 1。 return 1。當(dāng) p==NULL時(shí)隊(duì)列為空。 if (p==NULL) { p=s。 if (p==NULL) return 0。 } return 1。 70 void SeeDoctor () { int sel,flag=1。 while(flag==1) { cout “1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :”。 strcpy(sdata,name)。 cout “ 患者” sdata “看醫(yī)生” endl。 s=snext。 76 作業(yè)：練習(xí)題 3 ?書面作業(yè)： 1， 2， 5。 (3)重點(diǎn)掌握在順序隊(duì)上和鏈隊(duì)上實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法 ,注意環(huán)形隊(duì)列上隊(duì)滿和隊(duì)空的條件 。 cout “ 排隊(duì)患者 :”。 72 else { s=lqfrontnext。 cin name。 lqfrontnext=NULL。 Typedef struct qptr { Qtype *front,*rear。 pnext=snext。p,ElemType amp。 s=(Qnode *)malloc(sizeof(QNode))。 } 65 例 若使用循環(huán)鏈表來表示隊(duì)列， p是鏈表中一個(gè)指針。lqrear==NULL) return 0。 else lqfront=pnext。lq, ElemType amp。 sdata=x。 //鏈隊(duì)類型 在這樣的隊(duì)列中，隊(duì)空的條件是 lqfront=lqrear==NULL。 } 57 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為 鏈隊(duì) ， 它實(shí)際上是一個(gè)同時(shí)帶有首指針和尾指針的單鏈表 。 x= sqdata[sqfront]。 } int EnQueue(SqQueue *sq,ElemType x) //進(jìn)隊(duì) { if(sqcount==QueueSize) return 0。 } 52 例 對(duì)于環(huán)形隊(duì)列 ， 寫出求隊(duì)列中元素個(gè)數(shù)的公式 。 return 1。 sqrear=(sqrear+1)%QueueSize。 45 循環(huán)隊(duì)的入隊(duì)和出隊(duì)操作示意圖 rear 0 1 2 3 4 front (a) 空隊(duì) ( b ) A,B,C 入隊(duì) re ar 0 1 2 3 4 front A B C rear 0 1 2 3 4 A B C D front ( c )D 入隊(duì) , 隊(duì)滿 rear 0 1 2 3 4 C D front (d) 出隊(duì) 2 次 rear 0 1 2 3 4 front (e) 出隊(duì) 2 次 , 隊(duì)空 46 環(huán)形隊(duì)列 qu的 4要素： ? 隊(duì)空條件： = ? 隊(duì)滿條件： (+1)%QueueSize== ? 進(jìn)隊(duì)操作： 1；元素進(jìn)隊(duì)。 ? 那么能不能用 rear==QueueSize1作為隊(duì)滿的條件呢 ？ 顯然不能 ,在圖 (d)中 ,隊(duì)列為空 ,但仍滿足該條件 。排隊(duì)的規(guī)則是不允許“插隊(duì)”，新加入的成員只能排在隊(duì)尾，而且隊(duì)中全體成員只能按順序向前移動(dòng)，當(dāng)?shù)竭_(dá)隊(duì)頭（并得到服務(wù)）后離隊(duì)。in。因?yàn)樵?B中，先進(jìn)棧一次，立即出棧 2次，這會(huì)造成棧下溢。 return 1。 x=pdata。 pnext=ls。 27 在 鏈棧中 ,棧的基本運(yùn)算算法如下 : (1)初始化棧運(yùn)算算法 其主要操作是：創(chuàng)建一個(gè)頭結(jié)點(diǎn) *ls, 用 ls=NULL標(biāo)識(shí)棧為空棧 。其中，單鏈表的第一個(gè)節(jié)點(diǎn)就是鏈棧棧頂結(jié)點(diǎn)， ls稱為棧頂指針 。amp。 case ?]?: if(st[top]=?[?) top。top++。 int match(char *exps) { char st[Max],top=1,i=0。 int StackEmpty(SqStack st) { if (==1) return 1。 。 else { ++。 top=1表示棧空； top=StackSize1表示棧滿。習(xí)慣上將棧底放在數(shù)組下標(biāo)小的那端。 cout “輸入一串整數(shù)（以 0標(biāo)識(shí)結(jié)束） ” ； InitStack(st)。 (2)進(jìn)棧 Push(st,x):將元素 x插入到棧 st中作為棧頂元素。所以本題答案為 D。 這里 ， 人進(jìn)出胡同的原則是后進(jìn)去的先出來 。 處于棧頂位置的數(shù)據(jù)元素稱為 棧頂元素 。 棧的基本概念 4 棧的特點(diǎn)是后進(jìn)先出 。這表明棧修改的原則是 先進(jìn)后出 （或 后進(jìn)先出 ）。 10 例 4 設(shè) n個(gè)元素進(jìn)棧序列是 1,2,3,… ,n,其輸出序列是 p1,p2,… ,pn,若 p1=3,則 p2的值 。 (5)判斷棧是否為空 StackEmpty(st):若棧 st為空 ,則返回 1；否則返回 0。 //輸入值 n為 0時(shí)退出循環(huán) Push(st,n)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1