实验五 队列的设计及应用.doc

实验六 队列的设计及应用 一．实验目的 1．掌握队列的逻辑结构。 2．掌握循环队列、链队列的设计过程。 3．使用设计的队列实现进制转换。 二、实验内容 1．设计循环队列：设计头文件CirQueue.h，其内容如下： #include stdlib.h #define MaxSize 20 typedef struct { Qelemtype data[MaxSize]; int front,rear; }CirQueue; void InitQueue(CirQueue Q) { Q.front=Q.rear=0; } int QueueEmpty(CirQueue Q) { return Q.front==Q.rear; } int QueueFull(CirQueue Q) { return (Q.rear+1)%MaxSize==Q.front; } void EnQueue(CirQueue Q,Qelemtype e) { if(QueueFull(Q)) { coutoverfull!endl; exit(-1); } Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%MaxSize; } void DeQueue(CirQueue Q,Qelemtype e) { if(QueueEmpty(Q)) { coutThe Queue is empty!endl; exit(-1); } e=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; } void GetFront(CirQueue Q,Qelemtype e) { if(QueueEmpty(Q)) { coutThe Queue is empty!endl; exit(-1); } e=Q.data[Q.front]; } 2．设计链式队列：设计头文件LinkQueue.h，其内容如下： #include stdio.h #include stdlib.h typedef struct Qnode { Qelemtype data; Qnode *next; }QNode; typedef struct { QNode *front; QNode *rear; }LinkQueue; void InitQueue(LinkQueue Q) { Q.front=Q.rear=new QNode; Q.front-next=NULL; } int QueueEmpty(LinkQueue Q) { return Q.front==Q.rear; } void EnQueue(LinkQueue Q,Qelemtype e) { Qnode *p=new Qnode; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; } void DeQueue(LinkQueue Q,Qelemtype e) { if(QueueEmpty(Q)) { coutThe Queue is empty!; exit(-1); } QNode *p; p=Q.front-next; e=p-data; Q.front-next=p-next; if(p==Q.rear) { Q.rear=Q.front; } delete p; } void GetFront(LinkQueue Q,Qelemtype e) { if(QueueEmpty(Q)) { coutThe Queue is empty!; exit(-1); } e=Q.front-next-data; } 3．利用循环队列或链式队列实现舞伴配对问题：设计测试文件test.cpp，其内容如下： #include iostream.h typedef int Qelemtype; #include LinkQueue.h void main() { LinkQueue Q; InitQueue(Q); for(int i=1;i=3;i++) { EnQueue(Q,i*2-1); } while(!QueueEmpty(Q)) { Qelemtype e; DeQueue(Q,e); coute ; } coutendl; } 4