数据结构(C++语言)---舞伴问题.doc

问题叙述： 在一个舞会上，男士们和女士们进入舞厅，各自排成一队。跳舞开始时，依次从男队和女队的队列头上各出一个人进行配对。若两队初始人数不同，则较长的那一队中未配对者等待下一轮舞曲。先入队的男士或女士先出队配成舞伴，因此该问题是具有先进先出的特性，可以用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两对当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队列仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。具体代码如下：#include #include using namespace std;templateclass CirQueueprivate:T *q;int front;int rear;int maxSize;public:CirQueue(int m);CirQueue();void EnQueue(T x);T DeQueue();T GetHead();T GetLast();T InitQueue();int IsEmpty();int IsFull();void Clear();templateCirQueue:CirQueue(int m)q =new Tm;maxSize=m;front=rear=0;templateCirQueue:CirQueue()delete q;front=rear=0;maxSize=0;templatevoid CirQueue:EnQueue(T x)if (rear+1)%maxSize=front)coutFullendl;qrear=x;rear=(rear+1)%maxSize;templateT CirQueue:DeQueue()T x;if(front=rear)cout下溢endl;x=qfront;front=(front+1)%maxSize;return x;templateT CirQueue:GetHead()T x;if (front=rear)cout队空，无队顶元素endl;x=qfront;return x;templateT CirQueue:GetLast()T x;if(rear=front)cout队空，无队尾元素endl;x=qrear;return x;template int CirQueue:IsEmpty()if (rear = front) return 1;else return 0;template int CirQueue:IsFull()if (rear+1)%maxSize = front) return 1;else return 0;struct dancer char name20; char sex;int main() cout请输入舞伴总数量endl;CirQueue mdancer(10);CirQueue fdancer(10);ifstream in(source.txt);while(!in.eof() cout请输入舞者性别（f（女）or m（男）及姓名 temp.sex;in ;if (temp.sex = f)fdancer.EnQueue(temp);elsemdancer.EnQueue(temp);while( (!mdancer.IsEmpty()&!(fdancer.IsEmpty() ) cout mdancer.DeQueue().name - fdancer.DeQueue().name endl; if(!mdancer.IsEmpty() coutmdancer.GetHead().nameendl;e