实习报告一：用顺序表实现约瑟夫环.doc
文本预览下载声明
实习报告一：用顺序表实现约瑟夫环
题目：用顺序表和循环链表实现约瑟夫环的出列顺序。
班级：06计算机B班 姓名： 学号：0621121005 完成日期:2008-6-14
顺序表实现
一、需求分析
1.本程序中，需要输入的内容均为整型数，输入完成后以“回车符”作为结束标志。
2.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入程序的相关数据。
3.程序执行的命令包括：
（1）请输入原始密码m和人数n（n不大于30）；（2）请依次输入每个人的密码；（3）屏幕上将依次显示出列者的编号；（4）结束。
4.测试数据：
m的初值为20；n＝7，7个人的密码依次为：3，1，7，2，4，8，4。
实验结果应该为：6，1，4，7，2，3，5。
二、概要设计
要用顺序链表实现上述的功能，需要一个抽象数据类型：顺序表。
1.顺序表数据类型定义：
ADT sqlist {
数据对象：D={ ai |ai ∈elemset,i=1,2,…,n, n≥0}
数据关系：R1={ ai-1,ai | ai-1,ai ∈D,i=2,3,…,n}
基本操作：
initlist_sq（l）
操作结果：构造一个空的顺序表l。
}ADT sqlist
2.本程序包含一个模块:
主程序模块：
顺序表抽象数据类型；
Int main(){
接受命令；
处理命令；
}
三、详细设计
1.源程序
#includeiostream
using namespace std;
#define maxlen 30
typedef int elemtype;
typedef struct{
elemtype elem[maxlen];
int length;
}sqlist;
sqlist joseph;
void initlist_sq(sqlist l){
l.length=0;
}
void jos(int m, int n){
cout请依次输入n个密码:;
for(;joseph.lengthn;joseph.length++)
cinjoseph.elem[joseph.length];//赋密码值
cout出列顺序为:;
int i=-1;//i为数组下标（下一值为0）
for(int k=0;kn;k++){
for(int j=0;jm;){
i=(i+1)%n;
if(joseph.elem[i]!=0)
j++;
}
couti+1 ;
m=joseph.elem[i];
joseph.elem[i]=0;
}
coutendl;
}
void main(){
int m,n;//m为密码，n为小孩个数
cout请输入初始密码m和人数n(n不大于30):;
do
{
cinmn;
if(n1||n30) cout人数不合法，请重输(n不大于30)：endl;
}while(n1||n30);
initlist_sq(joseph);// 初始化线性表
jos(m,n);
}
2.函数调用关系： main→jos。
四、调试分析
算法时空分析：
时间复杂度为O(n*m)。
五、用户手册
1.本程序的运行环境为DOS操作系统。
2.运行程序后按提示输入相应的数据。
六、测试结果
七、附录
源程序文件清单：Joseph_sq.cpp //主程序
循环链表实现
一、需求分析
1.本程序中，需要输入的内容均为整型数，输入完成后以“回车符”作为结束标志。
2.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序的相关数据。
3.程序执行的命令包括：
（1）请输入原始密码m和人数n（n不大于30）；（2）请依次输入每个人的密码；（3）屏幕上将依次显示出列者的编号；（4）结束。
4.测试数据：
m的初值为20；n＝7，7个人的密码依次为：3，1，7，2，4，8，4。
实验结果应该为：6，1，4，7，2，3，5。
二、概要设计
为了用循环链表实现上述功能，需要一个抽象数据类型：循环链表。
1.循环链表数据类型定义：
ADT sqlist {
数据对象：D={ ai |ai ∈elemset,i=1,2,…,n, n≥0}
数据关系：R1={ ai-1,ai | ai-1,ai ∈D,i=2,3,…,n}
基本操作：
create_l（l）
操作结果：构造一个空的顺序表l。
}ADT sqlist
2.本
显示全部