Q.front 队空：Q.front==Q.rear Qrear 队满：Q.font==Q.rear Qrear J5 J4 0 J3,J4,J5出队 J3 Q.front J6.J7.J8入队 J5 J4 5 J6 初始状态 4 0 J3 2 J7 解决方案： Q.front J8 1.另外设一个标志以区别队空、队满 Q.rear 2少用一个元素空间： 队空：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) ypb@ustc.edu.cn 12 中国科学技术大学
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)
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; ypb@ustc.edu.cn 13 中国科学技术大学
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; 队首 typedefstruct{ Queueptr font;/指向头结点 Queueptr rear;/指向队尾 }LinkQueue; Q.rear- 队尾 一操作实现 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指针。 ypb@ustc.edu.cn 14 中国科学技术大学
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(intn) 智片故 一注意：最后一行单独处理 >例3.6舞伴组合问题 -M name[ml男士姓名，F name[nl女士姓名。 -m男士，n个女士，舞厅同时容纳X对舞伴 >n>X,模拟跳舞进程，给出所有舞伴组合情况 void DancePartner() ypb@ustc.edu.cn 15 中国科学技术大学
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()