数据结构实验报告2.3.docx

数据结构实验报告2.3

第一篇：数据结构实验报告2.3计科101冯康201000814128题目三：舞伴问题【实验目的】1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。【问题描述】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。【实验要求】利用队列实现，存储结构采用顺序或链式均可【编程思路】男女配对问题的原则是先入先出进行配对，因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。如果某组有剩余则参与第二轮的配对，并将第一个需要配对学生的信息返回；如果完全配对，则返回信息，不再进行下一轮的配对。开始时男士和女士的记录存放在一个结构体数组中作为输入，另外需要构建两个队列来保存男队和女队。无论是结构体数组还男女队列的元素或结点都采取结构体类型。作为输入的结构体数组可以事先创建即初始化时便将数据保存进去，也可以在程序运行时创建。男女队列的存储类型可以采取顺序或链式结构。二者的原理基本一致，但在操作上却有所不同：1、顺序存储结构的长度确定，存储容量有限。开辟空间很大的话又浪费存储空间，一种解决方案是采用循环队列，可是本题目是将所用元素都存储完成以后才进行删除，采用循环队列便失去了意义。2、链式存储结构长度不固定，输入数据可以不固定。相比于顺序存储结构操作简单。由于，输入数据是放在结构体数组中的，其最大长度已确定，间接限制了队列的最大长度，故采用顺序存储结构。确定好存储的类型之后，将结点的类型定义如下：结点类型：结构体Node结构体的数据成员：string型变量Name用来保存姓名Char型变量Sex用来保存性别typedefstruct计科101冯康201000814128{Node*base;intFront;intRear;}LinkQueue;用此结构体创建结构体变量来完成队列的各项操作。接下来进行队列的创建、出队列和判断队列是否为空等，具体操作将在代码解析中介绍。【代码解析】男女队列创建函数：voidCreat(LinkQueue&p,LinkQueue&q,Nodes[])注：p、q分别是操纵男女队列的结构体，s[]为保存男女学生信息的数组通过p.base=newNode[n]和q.base=newNode[n]分别为为男女队列开辟数组空间，空间大小n由主函数中输入。为了程序的健壮性，需要判空。代码如下：if(!p.base&&!q.base){coutexit(1);}如果开辟内存空间成功，则将队列中的各个元素进行赋初值：p.Front=p.Rear=0;q.Front=q.Rear=0;根据性别信息将n个男女学生对号入座放入上面开辟的空间中:for(inti=0;iif(s[i].Sex==0){p.base[p.Rear].Name=s[i].Name;p.base[p.Rear].Sex=s[i].Sex;p.Rear++;}else{q.base[q.Rear].Name=s[i].Name;q.base[q.Rear].Sex=s[i].Sex;q.Rear++;}}进行男女学生配对及确定下一轮要进行跳舞学生信息。其函数为：LinkQueue*Dance(LinkQueue&p,LinkQueue&q)一直进行循环，将男女生进行配对。最后的结束条件是至少有一个队列为空：while(p.Front!=p.Rear&&q.Front!=q.Rear)//循环结束条件{coutp.Front++;q.Front++;//进行学生配对}if(p.Front!=p.Rear)return&p;//如果男生队列有剩余则将男生队列返回计科101冯康201000814128}elseif(q.Front!=q.Rear)return&q;//如果女生队列有剩余则将女生队列返回elsereturnNULL;//如果男女学生刚好配对则返回空指针【测试数据】【实验体会】对于面向过程编程而言，程序=数据+算法，在编写程序之前首先要对题目要求进行分析和思考。等把问题弄明白后，就要根据事件发展过程，依靠程序来模仿事件，进而形成编程思路，最后确定算法。一般而言，在编程思路路形成以后，根据程序执行过程选择