软件实践报告

《软件实践报告》由会员分享，可在线阅读，更多相关《软件实践报告（27页珍藏版）》请在金锄头文库上搜索。

1、1软件课程设计报告软件课程设计报告班级：班级：03085010308501 姓名：杨春宇姓名：杨春宇学号：学号：030850123030850123 指导老师：陆熊指导老师：陆熊2目录目录1.1.约瑟夫问题约瑟夫问题-3-32.2.停车场问题停车场问题-8-83.3.排序算法的比较排序算法的比较-17-173约瑟夫斯问题约瑟夫斯问题一问题描述一问题描述 1.1.实验题目：实验题目： 约瑟夫斯（Josephus）问题的一种描述是：编号为 1，2，n 的 n 个人按 顺时针方向围坐一圈，每人持有一个密码（正整数） 。一开始任选一个正整数作 为报数上限值 m，从第一个人开始按顺时针方向自 1 开始报

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

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

4、，提示用户输入初始密码，输入值须为正整数。 3.3. 输出形式：输出形式： 程序执行结束后会输出相应的出列结点的顺序，亦即其编号。用户输入完毕后， 程序自动输出运行结果。 4.4.测试数据要求：无。测试数据要求：无。 三概要设计三概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应 的编号及密码信息，因此需要循环链表结构体这个抽象数据类型。 1.循环链表结构体抽象数据类型定义：ADT cnode数据对象：D=|(cnode *),i=1,2,3,n,n;iiicba,iiicbaint,int,04数据关系：R=;基本操作：Create_node() /构造循环链表dis

5、play_number(p) /输出循环链表结点编号信息ADT cnode 2.2.本程序保护模块：本程序保护模块： 主函数模块、循环链表结构体模块 调用关系：主函数模 块循环链表结 构体模块4 4详细设计详细设计 1.1.相关头文件库的调用说明：相关头文件库的调用说明：#include 2.2.循环链表结构体的定义：循环链表结构体的定义：struct LNode int data,code; LNode *next; ; /部分基本操作的伪码实现：部分基本操作的伪码实现： （1）创建循环链表： void Create(LNode *head) /初始化单向循环链表 LNode *p; int

6、 i; coutdata=1; cinhead-code ; p=head; for(i=2;idata=i; cins-code; p-next=s; p=s; p-next=head; 5（2）输出每次出列结点的编号： int Put(LNode *q) /处理出列顺序 int i; LNode *p; p=q; while(n!=1) for(i=2;inext; q-next=p-next; m=p-code; coutdatanext; n-; i=2; return p-data; 3.3.主函数的伪码实现：主函数的伪码实现：void main() LNode *head,*q;

7、head=new LNode; q=head; coutm; coutn; Create(head); cout struct LNode int data,code; LNode *next; ; int m,n; void Create(LNode *head) /初始化单向循环链表 LNode *p; int i; coutdata=1; cinhead-code ; p=head; for(i=2;idata=i; cins-code; p-next=s; p=s; p-next=head; int Put(LNode *q) /处理出列顺序 int i; LNode *p; p=q;

8、 while(n!=1) for(i=2;inext; q-next=p-next; m=p-code; coutdatanext; n-; i=2; return p-data; void main() LNode *head,*q; head=new LNode; q=head; coutm; coutn; Create(head); cout #include 2.2.部分基本操作的伪码实现：部分基本操作的伪码实现：void InCar(CarStack #define MAX_SIZE 2/停车场能够容纳的车的数量 #define FARE 5/表示停车场的收费为每小时 FARE 元

9、int CountForStack=0;/ 此全局变量用来计数堆栈现有的车数 int CountForQueue=0;/ 此全局变量用来计数队列现有的车数 typedef struct/这个节点用来保存每辆车的信息 char Condition ;/用来表示“到达”或者“离开”的状态,“ “表示还没有到 达，也没有离开 int ArriveTime;/用来记录到达时间，默认为-1，说明还没有到达 int LeaveTime;/ 用来记录离开时间，默认为-1，说明还没有离开 int License;/ 记录车牌号11CarNode; typedef struct /栈的定义 CarNode *b

10、ase;/栈底指针,指向 0 CarNode *top;/栈顶指针，如果指向 0，说明栈为空 int stacksize;/栈的容量大小CarStack; typedef struct QNode/队列节点的定义char Condition ; int ArriveTime;/用来记录到达时间，默认为-1，说明还没有到达 int LeaveTime;/ 用来记录离开时间，默认为-1，说明还没有离开 int License;/ 记录车牌号QNode *next; QNode; typedef struct QNode *front; QNode *rear;/ Queue; bool InitS

11、tack(CarStack if(!S.base ) coutnext =0; return true; bool EnQueue(Queue if(!p) coutArriveTime =qnode.ArriveTime ;12p-Condition =qnode.Condition ; p-LeaveTime =qnode.LeaveTime ; p-License =qnode.License ; p-next =0; Q.rear -next =p;Q.rear =p;return true; bool DeQueue(Queue t.ArriveTime =p-ArriveTime

12、; t.Condition =p-Condition ; t.LeaveTime =p-LeaveTime ; t.License =p-License ; Q.front -next =p-next ; if(Q.rear =p)/如果 P 是指向最后一个出队的元素Q.rear =Q.front ; free(p); return true; void InitCarNode(CarNode C.Condition =condition; C.LeaveTime =leavetime;C.License=license; bool Push(CarStack else return fals

13、e; bool IsStackEmputy(CarStack else return false; bool IsQueueEmputy(Queue else return false; bool SearchInStack(CarStack if(!IsStackEmputy(S) CarNode *p=S.top-1 ; while(p!=S.base ) if(*p).License =a) tag=true;-p; if(*p).License =a)tag=true; return tag; bool SearchInQueue(Queue if(!IsQueueEmputy(Q)/

14、如果队列非空QNode *p=Q.front-next ; while(p!=Q.rear) if(*p).License =a) tag=true; if(*p).License =a)tag=true;14return tag; void InCar(CarStack while(tag!=1int a1;unsigned int a2; switch(tag) case 1:couta1;couta2;InCar(S,Q,a2,a1); break; case 2:couta1;couta2;OutCar(S,Q,a2,a1); break; case 3: return ; break; char ch; coutch; if(ch!=E void main() CarStack carstack; InitStack(carstack);/ 建立并且初始化用于停车场的堆栈Queue carqueue; InitQueue(carqueue);/建立并且初始化用于通道的队列showmenu(carstack,carqueue);17排序算法的比较一、一、 问题描述问题描述 1.1.实验题目：实验题目：排序算法的比较,掌握各种排序算法（直接插入排序、冒泡排序、 快速排序、简单选择排序）的思路核比较他们之间的优劣。 2.2.基本要求基本要求： a.友好性：界面要友好，输入有