【正文】 sq=(SqQueue *)malloc (sizeof(SqQueue))。 //指針初始化 } 48 (2)入隊(duì)運(yùn)算算法 其主要操作是：先判斷隊(duì)列是否已滿 ， 若不滿 ，將隊(duì)尾指針增 1,在該位置存放 x。sq,ElemType x) { if ((sqrear+1)%QueueSize==sqfront) //隊(duì)滿 return 0。 //隊(duì)尾循環(huán)進(jìn) 1 sqdata[sqrear]=x。 } 49 (3)出隊(duì)運(yùn)算算法 其主要操作是：先判斷隊(duì)列是否已空 ,若不空 ， 讓隊(duì)頭指針增 1,將該位置的元素值賦給 x。x) { if (sqrear==sqfront) return 0。 //隊(duì)頭循環(huán)進(jìn) 1 x=sqdata[sqfront]。 } 50 (4)取隊(duì)頭元素運(yùn)算算法 其主要操作是：先判斷隊(duì)列是否已空 ,若不空 ， 讓隊(duì)頭指針上一個(gè)位置的元素值賦給 x。x) { if (sqrear==sqfront) return 0。 return 1。 對(duì)應(yīng)算法如下 : int QueueEmpty(SqQueue *q) { return(qfront==qrear)。 解：根據(jù)環(huán)形隊(duì)列的特點(diǎn) ， 有以下情況： 0 隊(duì)空 ， 即 front=rear 元素個(gè)數(shù) = rearfront 若 rearfront rear+QueueSizefront 若 rearfront QueueSzie 若隊(duì)列滿即 (rear+1)%QueueSize==front 歸納起來(lái) ， 環(huán)形隊(duì)列元素個(gè)數(shù)的計(jì)算公式如下： (rear+QueueSizefront)% QueueSize 53 例 如果用一個(gè)環(huán)形數(shù)組 qu[QueueSzie]表示隊(duì)列，該隊(duì)列只有一個(gè)頭指針 front，不設(shè)隊(duì)尾指針 rear，而設(shè)置計(jì)數(shù)器 count，用以記錄隊(duì)列中的元素個(gè)數(shù)。 解： 隊(duì)列中最多容納 QueueSize個(gè)元素，因?yàn)檫@里不需要空出一個(gè)位置以區(qū)分隊(duì)列空和隊(duì)列滿的情況。 在這種隊(duì)列上實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下： 54 void InitQueue(SqQueue *amp。 sqfront=qucount=0。 sqcount++。 return 1。x) //出隊(duì) { if(sqcount==0) return 0。 sqfront=(sqfront+1)%QueueSize。 return 1。x) //取隊(duì)頭 { if(sqcount==0) return 0。 return 1。 else return 0。 首指針指向隊(duì)頭結(jié)點(diǎn) ， 尾指針指向隊(duì)尾結(jié)點(diǎn)即單鏈表的最后一個(gè)結(jié)點(diǎn) 。 struct QNode *next。 //鏈隊(duì)中結(jié)點(diǎn)的類(lèi)型 typedef struct qptr { QType *front。 } LinkQueue。 一般情況下，鏈隊(duì)是不會(huì)出現(xiàn)隊(duì)滿的情況。lq) { lqrear=lqfront=NULL。 void EnQueue(LinkQueue *amp。 s=(QType *)malloc(sizeof(QType))。 snext=NULL。amp。 else { lqrearnext=s。 } } 62 (3)出隊(duì)運(yùn)算算法 int DeQueue(LinkQueue *amp。x) { QType *p。amp。 p=lqfront。 if (lq rear==lq front) lqrear=lqfront=NULL。 free(p)。 } 63 (4)取隊(duì)頭元素運(yùn)算算法 其主要操作是：將 *front結(jié)點(diǎn)的 data域值賦給 x。lq,ElemType amp。amp。 x=lqfrontdata 。 } 64 (5)判斷隊(duì)空運(yùn)算算法 其主要操作是：若鏈隊(duì)為空 ， 則返回 1；否則返回 0。amp。 else return 0。試基于此結(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)。隊(duì)列的入隊(duì)和出隊(duì)算法如下： typedef struct node { ElemType data。 }Qnode。p,ElemType x) //入隊(duì) { Qnode *s。 sdata=x。 pnext=p。 pnext=s。 } } pnext ② pnext=s ① snext=pnext p s x ③ p 67 int DeQueue(Qnode *amp。x) //出隊(duì) { Qnode *s。 if ( pnext==p) //只有一個(gè)結(jié)點(diǎn)時(shí) {x=pnextdata。 p=NULL。 x=sdata。 free(s)。 } 68 s=p→next p→next free(s)釋放空間 p p→next=s→next data x=sdata 69 例 設(shè)計(jì)一個(gè)程序，反映病人到醫(yī)院看病、排隊(duì)看醫(yī)生的情況。完整的程序如下： include include include Typedef struct QNode { char data[10]。 }Qtype。 }LinkQueue。 LinkQueue *lq。 char name(10)。 lqfront=(Qtype *)malloc(sizeof(QType))。 lqrear=lqfront。 cin sel。 flag=0。 case 1: cout “ 輸入患者姓名 :”。 s=(QType *)malloc(sizeof(QType))。snext=NULL。lqrear=s。 case2: if(lqfront==lqrear) cout “ 沒(méi)有排隊(duì)的患者” endl。 if(lqrear==s) lqrear=lqfront。 lqfrontnext=snext。 } break。 73 else { s=lqfrontnext。 while(s!=NULL) {cout sdata “ ”。 } cout endl。 } } } 74 void main() { SeeDoctor。 (2)重點(diǎn)掌握在順序棧上和鏈棧上實(shí)現(xiàn)棧的基本運(yùn)算算法 ,注意棧滿和?？盏臈l件 。 (4)靈活運(yùn)用棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問(wèn)題 。 （ 修改部分?jǐn)?shù)據(jù) ） ? 上機(jī)作業(yè)： 例 4， 7， 修改為： …… ， 表示輸入結(jié)束 ， 要求將隊(duì)列處理成循環(huán)鏈?zhǔn)?隊(duì)列 ，