软件实践报告.docx

《软件实践报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件课程设计报告班级：0308501姓名：杨春宇学号：030850123指导老师：陆熊27目录1.约瑟夫问题--------------------------------------32.停车场问题--------------------------------------83.排序算法的比较---------------------------------1727约瑟夫斯问题一．问题描述1.实验题目：约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）

2、。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。2.基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。3.测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。二．需求分析1.程序所能达到的基本可能：该程序用循

3、环链表来模拟n个人顺时针围坐一圈，用链表中的每一个结点代表一个人，结点结构体中设置两个变量，分别存放其编号以及密码。在输入初始密码后，对该链表进行遍历，直到遍历到第m个结点，释放其空间，使其出列。然后用被释放空间结点的密码值作为新的密码值，重复上述过程，直至所有结点被释放空间出列，链表成为空链表。2.输入形式及输入值范围：程序运行后显示提示信息："Pleaseinputadata:"，提示用户输入密码信息，在输入达预定次数后自动跳出该循环，同时循环链表创建成功，在主函数中有相应的输出给予检验。然后程序显示提示信息："Plea

4、seinputthenumberm:"，提示用户输入初始密码，输入值须为正整数。3.输出形式：程序执行结束后会输出相应的出列结点的顺序，亦即其编号。用户输入完毕后，程序自动输出运行结果。4.测试数据要求：无。三．概要设计为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号及密码信息，因此需要循环链表结构体这个抽象数据类型。1.循环链表结构体抽象数据类型定义：ADTcnode{数据对象：D={

5、(cnode*),i=1,2,3....,n,n};数据关系：R=;27基本操作：Create_node()//构造

6、循环链表display_number(p)//输出循环链表结点编号信息}ADTcnode2.本程序保护模块：主函数模块、循环链表结构体模块调用关系：四．详细设计1.相关头文件库的调用说明：#include2.循环链表结构体的定义：structLNode{intdata,code;LNode*next;};//部分基本操作的伪码实现：（1）创建循环链表：voidCreate(LNode*head)//初始化单向循环链表{LNode*p;inti;cout<<"输入各人密码:"<d

7、ata=1;cin>>head->code;p=head;for(i=2;i<=n;i++){LNode*s=newLNode;s->data=i;cin>>s->code;p->next=s;p=s;}p->next=head;}（2）输出每次出列结点的编号：intPut(LNode*q)//处理出列顺序27{inti;LNode*p;p=q;while(n!=1){for(i=2;i<=m;i++){q=p;p=p->next;}q->next=p->next;m=p->code;cout<data<

8、deletep;p=q->next;n--;i=2;}returnp->data;}3.主函数的伪码实现：voidmain(){LNode*head,*q;head=newLNode;q=head;cout<<"输入初始报数上限值m:"<>m;cout<<"输入人数n:"<>n;Create(head);cout<<"出列顺序为："<

9、各结点的编号，难以实现将结点与其对应的编号很紧密地联系在一起，故后来定义了一个结构体，将各结点的编号和密码信息放在一个结构体里，很好地绑定在一起，免去结点与编号不能统一的麻烦。2.方法优缺点分析：优点：用循环链表模拟，与真实情境相似，数学模型选取得当；27缺点：本程序采用循环链表模拟本题，