Q.frontOrear队空： Q.front==Q.rear队满：Q.front==Q.rear50NQrearJ5J45J3,J4,J5出队0431J32J6.J7.J8入队Q.frontJ5J6J4540初始状态32J7J3J8Q.front解决方案：1.另外设一个标志以区别队空、队满Q.rear2.少用一个元素空间：队空：Q.front==Q.rear队满：(Q.rear+1)%M==Q.front
0 1 2 3 4 5 Q.rear Q.front J4 J5 J6 0 1 2 3 4 5 Q.rear Q.front J3 J8 J7 J4 J5 J3 0 1 2 3 4 5 Q.rear Q.front 初始状态 队空：Q.front= =Q.rear 队满：Q.front= =Q.rear 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：Q.front= =Q.rear 队满：(Q.rear+1)%M= =Q.front
一实现InitQueue Sq(SqQueue &Q,int maxsize,int incresize)DestroyQueue Sq(LinkQueue &Q);Queuelength Sq （SqQueue Q)EnQueue Sq （ SqQueue &Q, ElemType e)Dequeue(SqQueue &Q,ElemType &e)12中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 12 中国科学技术大学 – 实现 InitQueue_Sq(SqQueue &Q,int maxsize,int incresize) DestroyQueue_Sq(LinkQueue &Q); Queuelength_Sq（SqQueue Q） EnQueue_Sq（SqQueue &Q, ElemType e） Dequeue(SqQueue &Q, ElemType &e)
5oIncrementQueuesize(&SqQueue Q)QElemtype *a;a=new QElemType[Q.queuesize+Q. increment]:for(i=0;i<Q.queuesize-1;i++)a[i]=Q.elem[(i+Q.front)%Q.queuesize]:delete [1 Q.elem;Q.elem=a;Q.queuesize+=Q.increment;13中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 13 中国科学技术大学 IncrementQueuesize(&SqQueue Q){ QElemtype *a; a=new QElemType[Q.queuesize+Q. increment]; for(i=0;i<Q.queuesize-1;i++) a[i]=Q.elem[(i+Q.front)%Q.queuesize]; delete [] Q.elem; Q.elem=a; Q.queuesize+=Q.increment; }
>链队列头结点Q.front一表示结构：带头结点的单链表typedefLinklist Queueptr;队首typedef struct {front;//指向头结点Queueptrrear；//指向队尾Queueptr队尾Q.rear.}LinkQueue;一操作实现voidInitQueueL(LinkQueue&Q)voidDestroyQueueL(LinkQueue&Q)void GetHead L(LinkQueue &Q, Qelemtype e);void EnQueue_L(LinkQueue&Q,Qelemtype e);voidDeQueueL(LinkQueue&Q,Qelemtype&e);注意：删除元素时为最后一个元素时应改写rear指针14ypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 ➢ 链队列 –表示结构:带头结点的单链表 typedefLinklist Queueptr; typedefstruct { Queueptr front; //指向头结点 Queueptr rear; //指向队尾 }LinkQueue; –操作实现 void InitQueue_L(LinkQueue&Q); void DestroyQueue_L(LinkQueue&Q); void GetHead_L(LinkQueue&Q, Qelemtype e); void EnQueue_L(LinkQueue&Q,Qelemtype e); void DeQueue_L(LinkQueue&Q,Qelemtype &e); 注意：删除元素时为最后一个元素时应改写rear指针。 Q.front . 头结点 队尾 队首 Q.rear
3.6队列应用>例3.5打印二项式系数 算法3.27 void yanghui(int n)MuosoftmPit灯片放一注意：最后一行单独处理>例3.6舞伴组合问题一M name[m]男士姓名，F name[n]女士姓名一m男士，n个女士，舞厅同时容纳X对舞伴-m>n>X,模拟跳舞进程，给出所有舞伴组合情况voidDancePartnerO15中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 15 中国科学技术大学 3.6队列应用 ➢ 例3.5 打印二项式系数 – 算法3.27 void yanghui(int n) – 注意：最后一行单独处理 ➢ 例3.6 舞伴组合问题 – M_name[m]男士姓名，F_name[n]女士姓名。 – m男士，n个女士，舞厅同时容纳X对舞伴 – m>n>X,模拟跳舞进程，给出所有舞伴组合情况 – void DancePartner()