数据结构课程设计之学生配对问题.doc

##大学 数据结构课程设计报告 题目： 学生配对问题 院（系）： 计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011.6.19——2011.6.30 指导教师: 2010—2011年度 第 2 学期 一、需求分析 1.问题描述： 学生搭配问题 一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下: 1) 输出每曲配对情况 2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值. 2.基本功能 核心问题: 循环队列的应用 数据模型（逻辑结构）: 循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。 存储结构: 循环链表 核心算法: 循环队列的入队，出队，判队满，判队空。 3.输入输出 输入数据: 男生人数、女生人数，歌曲数量，都是整型 输出数据: 每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）。 二、 概要设计 1.设计思路： 该程序主要运用了循环队列 2.数据结构设计： 循环队列： #define NAXSIZE 100//队列长度 typedef struct｛ QElemType *base；//初始化的动态分配存储空间 int front;//头指针，队列不为空，指向队列头元素 int rear；//尾指针，若队列不为空，指向对列尾元素的下一个位置 ｝SqQueue; Status InitQueue(LinkQueueQ) //构造一个空数列 Status EnQueue(LinkQueue Q,QElemType e) //插入元素e为Q的新的队尾元素 Status DnQueue(LinkQueue Q,QElemType e) //若队列不为空，则删除Q的对头元素，用e返回其指，并返回OK //否则返回ERROR 3.软件结构设计： ①主程序模块 ②输入模块：通过Get函数输入 ③输出模块：PrintF PrintM函数实现输出 ④数据处理模块：通过循环队列的InitQueue、EnQueue、DnQueue基本操作实现 三、 详细设计 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(ni) { printf(_ ); n++; } p=F.front-next; while(F.rear!=p) { printf(%d ,p-num); p=p-next;} printf(%d \n,p-num); 2、主函数： void main() { int m,n,k,i,a,b; int count=0,num; int c[10]={0}; int *t=c; int tag=1; QueuePtr p,q; LinkQueue F; //女生队 LinkQueue M; //男生队 print