约瑟夫环实习报告

实习报告

题目：编制一个程序求出约瑟夫环问题的出列顺序。

班级：06计算机A班 姓名：林树地 学号：0615111044 完成日期：2008-05-01

顺序表实现

一、需求分析

1. 本程序需要由用户在键盘上输入程序中的相关数据。 2. 先输入初始密码m (m>0)和环中人的个数n（n<50），再依次输入每个人的密码。输入形式是以“回车”为结束标志的整型数。 3. 依次输出约瑟夫环中的出列者的编号。 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∈Elemtype,i=1,2,„„n；n≥0} 数据关系：R1={| ai-1,ai∈D,i=2,„„,n} 基本操作：

initlist_sq(&l)

操作结果：构造一个空的顺序表 }ADT sqlist

2．本程序包含两个模块 ①主程序模块

void main(){

接受命令； 处理命令；

}

②顺序表单元模块——实现顺序表抽象数据类型； 各模式块之间的调用关系如下； 主程序模块→顺序表单元模块

三、详细设计

1．顺序表类型 typedef struct{

int elem[50];//存密码

int length; }sqlist;

2．主函数和其他函数的伪码算法 void main() {

int m,n;//m为密码，n为小孩个数

cout<<\"请输入初始密码m和人数n(n不大于50):\"; while(n<1||n>50) {

cin>>m>>n;

if(n<1||n>50) cout<<\"人数不合法，请重输\"<sqlist Jos;

initlist_sq(Jos);// 初始化线性表 cout<<\"请依次输入\"<cin>>Jos.elem[Jos.length];//存密码

cout<<\"出列顺序为：\";

int i=-1;//i为数组下标（下一值为0） for(int k=0;kfor(int j=0;ji=(i+1)%n;//对下标加1求模

if(Jos.elem[i]!=0)//判断是否已出列 j++; }

cout<m=Jos.elem[i];//输出已出列的编号 Jos.elem[i]=0;//标识已出列 }

cout<void initlist_sq(sqlist &l){ l.length=0; }

3. 函数调用关系：

main

InitList

四、调试分析

1. 刚开始忽略了对输入数据合法性的判断，可能造成存储空间不足。

2. 算法时空分析

主函数中，时间复杂度为O(n*m)。

五、测试结果

循环链表实现

一、 需求分析

1. 本程序需要由用户在键盘上输入程序中的相关数据。

2. 先输入初始密码m (m>0)和环中人的个数n (n>0)，再依次输入每个人的密码。输入形式是以“回车”为结束标志的整型数。 3. 依次输出约瑟夫环中的出列者的编号。 4. 测试数据：

初值m=20，n=7，7个人的密码依次为：3，1，7，2，4，8，4。 出列顺序应为6，1，4，7，2，3，5。

二、 概要设计

以循环链表存储结构表示环中的人。 1．本程序包含两个模块 ①主程序模块

void main(){

初始化； 接受命令；

②顺序表单元模块——实现循环链表抽象数据类型； 各模式块之间的调用关系如下； 主程序模块→循环链表单元模块

三、 详细设计

1． 元素类型、节点类型和指针类型 typedef struct Lnode

{

int data; int secret;

struct Lnode* next;

}*p,*q,*t,h,*head，*linklist;//p为当前指针，head为头指针，q为跟随指针，h为头节点

2. 主函数的算法

void main() {

cout<<\"请输入人数n，报数上限值m和这n个人的密码:\"<string s;vectora; getline(cin,s);

istringstream sin(s);

for(int b;sin>>b;a.push_back(b)); cout<<\"您输入这n个人的密码是：\"; for(i=2;ihead=&h; p=head; n=a[0]; //创建循环链表 for(i=1;i<=n;i++) { p->next=(Lnode*)malloc(sizeof(Lnode)); p=p->next; p->data=i;

p->secret=a[i+1]; if(i!=n) p->next=NULL; else { p->next=head->next; p=p->next; } } //小孩出列 q=head;

m=a[1]; while(p->next!=p)

{

for(i=1;ip=p->next; q=q->next; }

cout<data<<\" \"; m=p->secret; q->next=p->next; t=p;

p=p->next; free(t); }

cout<data<main

四、 调试分析

1. 算法的时空分析：

主函数中时间复杂度为O(n*m)。

五、测试结果