【正文】 ee(p)。 return 1。 } 63 (4)取隊(duì)頭元素運(yùn)算算法 其主要操作是：將 *front結(jié)點(diǎn)的 data域值賦給 x。 int GetHead(LinkQueue *amp。lq,ElemType amp。x) { if (lqfront==NULL amp。amp。lqrear==NULL) return 0。 x=lqfrontdata 。 return 1。 } 64 (5)判斷隊(duì)空運(yùn)算算法 其主要操作是：若鏈隊(duì)為空 ， 則返回 1；否則返回 0。 對應(yīng)算法如下 : int QueueEmpty(LinkQueue *lq) { if (lqfront==NULLamp。amp。 lqrear==NULL) return 1。 else return 0。 } 65 例 若使用循環(huán)鏈表來表示隊(duì)列， p是鏈表中一個(gè)指針。試基于此結(jié)構(gòu)給出隊(duì)列的入隊(duì)（ EnQueue）和出隊(duì)（ DeQueue ）算法， p為何值時(shí)隊(duì)列空？ 解：這里使用的循環(huán)鏈表不帶頭結(jié)點(diǎn)，規(guī)定 p始終指向隊(duì)尾結(jié)點(diǎn) , pnext即為隊(duì)頭結(jié)點(diǎn)。當(dāng) p==NULL時(shí)隊(duì)列為空。隊(duì)列的入隊(duì)和出隊(duì)算法如下： typedef struct node { ElemType data。 struct Qnode *next。 }Qnode。 66 void EnQueue(Qnode *amp。p,ElemType x) //入隊(duì) { Qnode *s。 s=(Qnode *)malloc(sizeof(QNode))。 sdata=x。 if (p==NULL) { p=s。 pnext=p。 } else { snext=pnext。 pnext=s。 p=s。 } } pnext ② pnext=s ① snext=pnext p s x ③ p 67 int DeQueue(Qnode *amp。p,ElemType amp。x) //出隊(duì) { Qnode *s。 if (p==NULL) return 0。 if ( pnext==p) //只有一個(gè)結(jié)點(diǎn)時(shí) {x=pnextdata。 free(p)。 p=NULL。 } else { s=pnext。 x=sdata。 pnext=snext。 free(s)。 } return 1。 } 68 s=p→next p→next free(s)釋放空間 p p→next=s→next data x=sdata 69 例 設(shè)計(jì)一個(gè)程序，反映病人到醫(yī)院看病、排隊(duì)看醫(yī)生的情況。 解：病人排隊(duì)看醫(yī)生采用先到先看的方式，所以要用到一個(gè)隊(duì)列，這里設(shè)計(jì)了一個(gè)帶頭結(jié)點(diǎn)的單鏈表作為隊(duì)列。完整的程序如下： include include include Typedef struct QNode { char data[10]。 struct QNode *next。 }Qtype。 Typedef struct qptr { Qtype *front,*rear。 }LinkQueue。 70 void SeeDoctor () { int sel,flag=1。 LinkQueue *lq。 Qtype *s。 char name(10)。 lq=(LinkQueue *)malloc(sizeof(LinkQueue))。 lqfront=(Qtype *)malloc(sizeof(QType))。 lqfrontnext=NULL。 lqrear=lqfront。 while(flag==1) { cout “1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :”。 cin sel。 71 case 0: ifype(lqfront!=lqrear) cout “ 請排隊(duì)的患者明天就醫(yī)” endl。 flag=0。 break。 case 1: cout “ 輸入患者姓名 :”。 cin name。 s=(QType *)malloc(sizeof(QType))。 strcpy(sdata,name)。snext=NULL。 lqrearnext=s。lqrear=s。 break。 case2: if(lqfront==lqrear) cout “ 沒有排隊(duì)的患者” endl。 72 else { s=lqfrontnext。 if(lqrear==s) lqrear=lqfront。 cout “ 患者” sdata “看醫(yī)生” endl。 lqfrontnext=snext。 free(s)。 } break。 case3: if(lqfront==lqrear) cout “ 沒有排隊(duì)的患者” endl。 73 else { s=lqfrontnext。 cout “ 排隊(duì)患者 :”。 while(s!=NULL) {cout sdata “ ”。 s=snext。 } cout endl。 } break。 } } } 74 void main() { SeeDoctor。 } 本程序的一 次執(zhí)行結(jié)果： 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :1 輸入患者姓名 :Smith 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :1 輸入患者姓名 :John 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :3 排隊(duì)患者 :Smith John 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :1 輸入患者姓名 :Mary 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :2 患者 Smith看醫(yī)生 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :2 患者 John看醫(yī)生 1:排隊(duì) 2:看醫(yī)生 3:查看排隊(duì) 0:下班 請選擇 :0 請排隊(duì)的患者就醫(yī) 75 本章小結(jié) 本章基本學(xué)習(xí)要點(diǎn)如下 : (1)理解棧和隊(duì)列的特性以及它們之間的差異 ,知道在何時(shí)使用哪種數(shù)據(jù)結(jié)構(gòu) 。 (2)重點(diǎn)掌握在順序棧上和鏈棧上實(shí)現(xiàn)棧的基本運(yùn)算算法 ,注意棧滿和?？盏臈l件 。 (3)重點(diǎn)掌握在順序隊(duì)上和鏈隊(duì)上實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法 ,注意環(huán)形隊(duì)列上隊(duì)滿和隊(duì)空的條件 。 (4)靈活運(yùn)用棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問題 。 76 作業(yè)：練習(xí)題 3 ?書面作業(yè)： 1， 2， 5。 （ 修改部分?jǐn)?shù)據(jù) ） ? 上機(jī)作業(yè)： 例 4， 7， 修改為： …… ， 表示輸入結(jié)束 ， 要求將隊(duì)列處理成循環(huán)鏈?zhǔn)?隊(duì)列 ， …… 。