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