实习报告一：用顺序表实现约瑟夫环
题目：用顺序表和循环链表实现约瑟夫环的出列顺序。
班级：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 ∈D,i=2,3,…,n} 基本操作：initlist_sq（&l）
操作结果：构造一个空的顺序表l。
}ADT sqlist
2.本程序包含一个模块: 主程序模块：
顺序表抽象数据类型； Int main(){
接受命令； 处理命令； }
三、详细设计
1.源程序
#include 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<<\"请依次输入\"<cin>>joseph.elem[joseph.length];//赋密码值 cout<<\"出列顺序为:\"; int i=-1;//i为数组下标（下一值为0） for(int k=0;kvoid main(){ int m,n;//m为密码，n为小孩个数 cout<<\"请输入初始密码m和人数n(n不大于30):\"; do { cin>>m>>n; if(n<1||n>30) cout<<\"人数不合法，请重输(n不大于30)：\"<30); 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 ∈D,i=2,3,…,n} 基本操作：create_l（&l）
操作结果：构造一个空的顺序表l。
}ADT sqlist
2.本程序包含一个模块: 主程序模块：
循环链表抽象数据类型； Int main(){
接受命令； 处理命令； }
三、详细设计
1.源程序
#include using namespace std;typedef struct { int num;//位号 int m;//密码 }elemtype;
typedef struct lnode{ elemtype data; struct lnode *next; }lnode, *linklist;
linklist p;
void create_l(linklist &l,int n){
//输入n个元素的值，建立不带表头的循环链表l l=(linklist)malloc(sizeof(lnode)); p=l;
for(int i=0;i>p->data.m; p->data.num=i+1; if(i==n-1) break; p->next=(linklist)malloc(sizeof(lnode)); p=p->next; }p->next=l; }
void jos(int m,int n){ linklist l;
cout<<\"请依次输入\"<cout<<\"出列顺序为:\"; p=l; linklist r;while(p->next!=l) p=p->next; linklist q=p; p=l; do{ for(int i=1;inext; } q->next=p->next;r=p; p=p->next; cout<data.num<<\" \"; m=r->data.m; free (r);}while(p->next!=p);
cout<data.num<void main() {int n,m;
cout<<\"请输入初始密码m和人数n：\"; cin>>m>>n; jos(m,n); }
2.函数的调用：
main→jos→create_l
四、调试分析
算法的时空分析：
时间复杂度为O(n*m)。
五、用户手册
1.本程序的运行环境为DOS操作系统。 2.运行程序后按提示输入相应的数据。
六、测试结果
七、附录
源程序文件名清单： Joseph_l.cpp //主程序
