数据结构实训-学生分配问题.doc

. .
XX工学院
算法设计技能训练实习报告

题目： 学生搭配问题

系 （院）:计算机工程学院
专 业： 微软
班 级： 计1137
学 号： 1131317726
姓 名： 陆炎炜
指导教师： 周海岩
学年学期: 2014 ~ 2015 学年 第 1 学期

2015年 1月 1 日
算法设计技能训练任务书
课题
名称
学生搭配问题
设计
目的

1、 通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握
算法设计的知识。
2、 能够针对某一具体问题，设计算法进行解决。
3、 锻炼实践动手能力，提高解决问题的能力。
实验
环境

硬件：1、PC机，奔腾Ⅳ以上CPU， 512MB以上内存，80G以上硬盘；

软件：Visual C++编程工具
任务
要求
1、 应用数据结构基础知识进行实际问题求解与分析
2、 作为一个完整的系统，应具有友好的界面和较强的容错能力
3、 上机能正常运行代码
4、 分析算法的运行效率
5、 按要求撰写课程设计报告和设计总结
工作进度计划
序号
起止日期
工 作 容
1
2014.12.29
任务下达，查阅文献资料
2
2014.12.29～2014.12.31
总体设计、素材搜集、课题详细设计、调试
3
2014.12.31～2015.1.3
完善设计、撰写报告
4
2015.1.4
答辩
指导教师（签章）：
年月日

摘要

针对学生搭配问题，循环队列是一种重要的链式结构，其特殊性在于需附设 两个指针front和rear分别指示对头元素及队尾元素的位置且对头和队尾相邻接。在程序的设计过程中，运用了各种基本的算法，有判断队空及队满，出队，入队等.循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。
本文用循环队列会很好的把这个程序设计出来，会有很好的效果。得出的程序运行结果能够很形象的把结果表示出来。

关键词： 学生搭配数据结构 循环队列目录

一、设计目的............................................

二、课程设计............................................
1、设计内容.......................................
2、设计思想.......................................
3、关键算法.......................................
4、测试结果.......................................

三、实验程序...........................................

四、结论...............................................

五、 致谢..............................................

六、参考文献...........................................

. .word..
. .
一、设计目的
1、通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握
算法设计的知识。
2、能够针对某一具体问题，设计算法进行解决。
3、锻炼实践动手能力，提高解决问题的能力。

二、 课程设计
1.设计内容
一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.
请设计一系统模拟动态地显示出上述过程,要求如下:
1) 输出每曲配对情况
2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的 情况.至少求出K的两个值.
3) 尽量设计出多种算法及程序,可视情况适当加分

2、设计思想
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。
循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。
（1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。
（2） 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。
（3） 利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。
（4） 循环队列的长度分别设为男女生的个数即可。
（5） 在计算机终端输出的结果是：根据要求输出男生女生搭配情况。

3、关键算法

建立两个链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输
出。为充分利用向量空间，克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆
环，存储在其中成为循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝
前移动。只不过当头尾指针指向向量上界时、其加1操作是指向向量的下界。这样就可以通过
出队再入队来实现男生女生的循环搭配。
课程设计过程中的关键算法如下：
1)关键算法之一：初始化队列
void InitQ(LinkQueue &Q) 
 { 

QueuePtr p;  

 p=(QueuePtr)malloc(sizeof(QNode)); 
 Q.front=p; 
 Q.rear=p; 

Q.front->next=NULL;
 }
(2)关键算法之二：入队函数 

void EnQueue(LinkQueue &Q,int num)//入队函数 
{

 QueuePtr p;

 p=(QueuePtr)malloc(sizeof(QNode));
  p->num=num;
  p->next=NULL;
  Q.rear->next=p;
  Q.rear=p;
 }
(3)关键算法之三：出队函数

void DeQueue(LinkQueue &Q, int &num)//出队函数
 {

 QueuePtr p,q;
   if(Q.front==Q.rear)   printf("队列为空");
  p=Q.front->next;
  num=p->num;

 Q.front->next=p->next;
  q=p->next;
  if(Q.rear==q)
   Q.rear=Q.front;
  free(p);
 }
(4)关键算法之四：输出第i首曲子时女队的情况

void printF(LinkQueue &F,int i) //输出第i首曲子时女队的情况
 { 
 QueuePtr p;
   int n=1;
  while(n<i)  
{  
 printf("_ ");
   n++;
   }

 p=F.front->next;
  while(F.rear!=p)
  {
    printf("%d ",p->num);
   p=p->next;
}

 printf("%d \n",p->num);
 }

. .word..
. .
4、测试结果：

. .word..
. .

三、实验程序
#include<iostream>
template <class T>
class cirularQueue //定义一个一个循环队列
{ private:
int MaxSize;
int front; //头指针
int rear; //尾指针
T *data;
public:
cirularQueue(int MaxLength)
{ MaxSize=MaxLength;
front=rear=0;
data=new T[MaxLength];
}
~cirularQueue() //定义析构函数，使对象在撤销时释放
{ front=rear=0;
delete []data;
}
void Initqueue() //队列的申明
{ for(int i=0;i<maxSize-1;i++)
push(i);
}
bool IsFull() //判断队列是否已满
{ if((rear+1)%MaxSize==front)
return true;
else return false;
}
bool IsEmpty() //判断队列是否为空
{ if(front==rear)
return true;
else return false;
}
void push(T info) //入队
{ if(IsFull())
{ cout<<"错误！队列已满！"<<endl;
exit(-1);
}
else
{ data[rear]=info;
rear=(rear+1)%MaxSize;
}
}
void Pop(T &info) //出队
{ if(IsEmpty())
{ cout<<"错误！队列为空！"<<endl;
exit(-1);
}
else
{ info=data[front];
front=(front+1)%MaxSize;
}
}
void GetHead(T &info) //取队首元素
{ if(IsEmpty())
{ cout<<"错误！队列为空！"<<endl;
exit (-1);
}
else
{ info=data[front];
}
}
};

void Initqueue(cirularQueue<int>&,int);
void display(int,int);
void charge(int,int);
using namespace std;
static int songnum=0; //定义歌曲的数量并初始化为0
static int m=0,n=0; //男生和女生的人数
int main() //主函数
{ cout<<"请分别输入男生和女生的人数:";
cin>>m>>n;
display(m,n);
int a=0,b=0; //男生和女生的编号，以判断他们在第几首歌时能在一起跳舞
char quit='y'; //判断是否继续输入,如果继续输入，则输入'y'；否则输入'n'
while(quit!='n')
{ cout<<"请输入男生和女生的编号:";
cin>>a>>b;
while((a>m)||(b>n)) //如果输入错误
{ cout<<"输入的编号过大，请重新输入:";
cin>>a>>b;
}
charge(a,b);
cout<<"是否继续(是请输入'y',否则请输入'n'):";
cin>>quit;
}
return 0;
}
void Initqueue(cirularQueue<int> &Q,int m) //初始化队列
{ for(int i=1;i<=m;i++)
Q.push(i);
}
void display(int m,int n)
{ cirularQueue<int> man(m+1);
cirularQueue<int> woman(n+1);
Initqueue(man,m);
Initqueue(woman,n);
cout<<"请输入曲目数:";
cin>>songnum;
cout<<"每曲的配对情况为:"<<endl;
for(int k=1;k<=songnum;k++)
{ int x=0,y=0; //男生和女生的编号
man.Pop(x); //男生按顺序出对跳舞
woman.Pop(y); //女生按顺序出对跳舞
cout<<"第"<<k<<"曲:\t"<<x<<"号男生<->"<<y<<"号女生"<<endl; //他们在一起跳舞
man.push(x); //跳完舞后男生再次进入队列等在下一次跳舞
woman.push(y); //跳完舞后男生再次进入队列等在下一次跳舞
}
}
void charge(int a,int b)
{ int count=0; //定义舞曲计数以记录他们能在第几曲时在一起跳舞
cirularQueue<int> man1(m+1);
cirularQueue<int> woman1(n+1);
Initqueue(man1,m);
Initqueue(woman1,n);
while(count<=songnum)
{ int x, y;
count++;
man1.Pop(x);
woman1.Pop(y);
man1.push(x);
woman1.push(y);
if((x==a)&&(y==b))
{ cout<<"第"<<count<<"首曲:\t"<<a<<"号男生<->"<<b<<"号女生"<<endl;
break;
}
}
//如果他们在这个舞会上不能在一起跳舞，则输出
if(count==songnum+1)
cout<<"他们在这个舞会上不可能在一起跳舞"<<endl;
}

结 论
设计采用的是循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。
本次程序设计中所用语言为C++，程序开始定义了类cirular，其中有头指针，尾指针及数据域等。随之定义了析构函数，释放对象，然后进行了队列的基本操作，有队列的申明，判断队空及队满，出队，入队，其核心是display()函数和charge()函数，其中display()用于对各位同学编号和每队的输出情况，charge()用于计算已编号的同学在第几曲中进行配对。循环队列是一种环状的队列并且对头元素指向队尾元素，学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。

致
踉踉跄跄地忙碌近三四天，我的实训报告也终将告一段落。点击运行，也基本达到预期的效果，虚荣的成就感在没人的时候也总会冒上心头。但由于能力和时间的关系，总是觉得有很多不尽人意的地方。可是，我又会有点自恋式地安慰自己：做一件事情，不必过于在乎最终的结果，可贵的是过程中的收获。以此语言来安抚我尚没平复的心。感谢，衷心的感谢。在实训设计完成之际，衷心感谢我的老师周海岩老师对我的导和教诲。周老师开阔的思维、敏锐的洞察力以及详细的修改意见给我大的启发。金老师不仅专业学识渊博、治学严谨，待人平易近人；同时他对工作的积极热情、对学生认真负责、实事求是的态度，给我留下了深刻的印象，使我受益非浅。唯一的遗憾是我自己不够主动，错过了许多与您交流的机会。在此，我再次向周老师表示衷心的感谢和深深的敬意。
感谢我的母校给我们授课的各位尊敬的老师和计算机系培养我的领导与辅导老师，正是由于他们的以言传身教、解惑，让我学到了专业知识和许多做人的道理。我要特别感谢我的实训老师，与他们在相处的时间里，从他们身上学到了如何求知治学、如何为人处事。我也要感谢我的母校，是她为我提供了良好的学习环境和生活环境，让我的大学生活丰富充实，为我的人生留下了一段难忘的回忆。
感谢在整个实训设计期间和我密切合作的同学，在我弄实训设计过程中，他们热切关心我的设计进度，认真帮忙提出设计的修改意见，为我提供免费的设计数据并帮助我收集查找一些资料。
感谢我的朋友，感谢他们在我失意时给我鼓励，在失落时给我支持，感谢他们和我一路走来，让我在此过程中倍感温暖。 感谢我的家人和亲人，没有他们，就不会有今天的我。他们给予我的关爱、理解和支持是我勇于进取的动力。

参 考 文 献

1、 殷人昆编著。数据结构实用教程（C/C++描述）。：清华大学 2007
2、 钱能编著。C++程序设计教程。：清华大学 1999
3、 孙巧萍主编。数据结构实训教程。 ： 科学 ， 2000
4、 严蔚敏，数据结构题集（C语言版）。：清华大学，2006

指导教师评语
学号

班级

选题
名称

序号
评价内容
权重（%）
得分
1
考勤记录、学习态度、工作作风与表现。
5

2
自学情况：
上网检索机时数、文献阅读情况（笔记）。
10

3
论文选题是否先进，是否具有前沿性或前瞻性。
5

4
成果验收：
是否完成设计任务；能否运行、可操作性如何等。
20

5
报告的格式规X程度、是否图文并茂、语言规X及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。
30

6
文献引用是否合理、充分、真实。
5

7
答辩情况：
自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。
25

合计

指导教师（签章）：
年月日

. .word..