【正文】 eSize。 } int EnQueue(SqQueue *sq,ElemType x) //進(jìn)隊(duì) { if(sqcount==QueueSize) return 0。 } 55 int DeQueue(SqQueue *sq,ElemType amp。 x= sqdata[sqfront]。 x= sqdata[(sqfront+1)%QueueSize]。 } 57 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為 鏈隊(duì) ， 它實(shí)際上是一個(gè)同時(shí)帶有首指針和尾指針的單鏈表 。 } QType。 //鏈隊(duì)類(lèi)型 在這樣的隊(duì)列中，隊(duì)空的條件是 lqfront=lqrear==NULL。 //初始情況 } 61 (2)入隊(duì)運(yùn)算算法 其主要操作是：創(chuàng)建一個(gè)新結(jié)點(diǎn) ， 將其鏈接到鏈隊(duì)的末尾 ， 并由 rear指向它 。 sdata=x。 lqrear==NULL) lqrear=qfront=s。lq, ElemType amp。 lqrear==NULL) return 0。 else lqfront=pnext。 int GetHead(LinkQueue *amp。lqrear==NULL) return 0。 對(duì)應(yīng)算法如下 : int QueueEmpty(LinkQueue *lq) { if (lqfront==NULLamp。 } 65 例 若使用循環(huán)鏈表來(lái)表示隊(duì)列， p是鏈表中一個(gè)指針。 struct Qnode *next。 s=(Qnode *)malloc(sizeof(QNode))。 } else { snext=pnext。p,ElemType amp。 free(p)。 pnext=snext。 解：病人排隊(duì)看醫(yī)生采用先到先看的方式，所以要用到一個(gè)隊(duì)列，這里設(shè)計(jì)了一個(gè)帶頭結(jié)點(diǎn)的單鏈表作為隊(duì)列。 Typedef struct qptr { Qtype *front,*rear。 Qtype *s。 lqfrontnext=NULL。 71 case 0: ifype(lqfront!=lqrear) cout “ 請(qǐng)排隊(duì)的患者明天就醫(yī)” endl。 cin name。 lqrearnext=s。 72 else { s=lqfrontnext。 free(s)。 cout “ 排隊(duì)患者 :”。 } break。 (3)重點(diǎn)掌握在順序隊(duì)上和鏈隊(duì)上實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法 ,注意環(huán)形隊(duì)列上隊(duì)滿(mǎn)和隊(duì)空的條件 。 。 76 作業(yè)：練習(xí)題 3 ?書(shū)面作業(yè)： 1， 2， 5。 } 本程序的一 次執(zhí)行結(jié)果： 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :1 輸入患者姓名 :Smith 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :1 輸入患者姓名 :John 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :3 排隊(duì)患者 :Smith John 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :1 輸入患者姓名 :Mary 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :2 患者 Smith看醫(yī)生 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :2 患者 John看醫(yī)生 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :0 請(qǐng)排隊(duì)的患者就醫(yī) 75 本章小結(jié) 本章基本學(xué)習(xí)要點(diǎn)如下 : (1)理解棧和隊(duì)列的特性以及它們之間的差異 ,知道在何時(shí)使用哪種數(shù)據(jù)結(jié)構(gòu) 。 s=snext。 case3: if(lqfront==lqrear) cout “ 沒(méi)有排隊(duì)的患者” endl。 cout “ 患者” sdata “看醫(yī)生” endl。 break。 strcpy(sdata,name)。 break。 while(flag==1) { cout “1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請(qǐng)選擇 :”。 lq=(LinkQueue *)malloc(sizeof(LinkQueue))。 70 void SeeDoctor () { int sel,flag=1。 struct QNode *next。 } return 1。 } else { s=pnext。 if (p==NULL) return 0。 p=s。 if (p==NULL) { p=s。 66 void EnQueue(Qnode *amp。當(dāng) p==NULL時(shí)隊(duì)列為空。 lqrear==NULL) return 1。 return 1。x) { if (lqfront==NULL amp。 return 1。 x=pdata 。 if (lqfront==NULL amp。 lqrear=s。 if (lqfront==NULLamp。lq,ElemType x) { QType *s。 60 在鏈隊(duì)上實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下 : (1)初始化隊(duì)列運(yùn)算算法 其主要操作是：置結(jié)點(diǎn) lq*的 rear和 front均為 NULL: void InitQueue(LinkQueue *amp。 *rear。 隊(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ì)的類(lèi)型定義如下 : typedef struct QNode { ElemType data。 } 56 int QueueEmpty(SqQueue *sq) //判斷隊(duì)空 { if(sqcount==0) return 1。 } int GetHead(SqQueue *sq,ElemType amp。 sqcount。 sqdata[(sqfront+sqcount)%QueueSize]=x。sq) //隊(duì)初始化 { sq=(SqQueue *)malloc(sizeof(SqQueue))。 隊(duì)列中最多能容納多少個(gè)元素？ 設(shè)計(jì)實(shí)現(xiàn)隊(duì)列基本運(yùn)算算法。 } 51 (5)判斷隊(duì)列是否為空 若隊(duì)列 q滿(mǎn)足 qfront==qrear條件 ,則返回 1；否則返回 0。 int GetHead(SqQueue *sq,ElemType amp。 sqfront=(sqfront+1)%QueueSize。 return 1。 對(duì)應(yīng)算法如下 : int EnQueue(SqQueue *amp。 47 在環(huán)形隊(duì)列中 ,實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下 :