数据结构报告--约瑟夫环范文

第一篇：数据结构报告--约瑟夫环范文

实习报告

题目:约瑟夫环

班级：08052712学号: 08052211姓名: 葛俊峰

一、需求分析

1.本演示程序中，编号为1，2，„，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，如此下去，直到所有人全部出列为止。

2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即总人数，m的值，每个人所持的密码），运算结果显示在其后。

3.程序执行的命令包括：

（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。

4.测试数据：

m的初始值为20；n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。

二、概要设计

为了实现上述操作，应以单向循环链表为存储结构。为此，需要1个抽象数据类型：线性表。

1.线性表的抽象数据类型为：

ADT List{

数据对象：D={ai|ai∈ElemSet,i=1,2,„，n,n≥0}

数据关系：R1={|ai-1,ai∈D,i=2,3,„,n}

基本操作：

InitList(&L)

操作结果：构造一个空的线性表L。

}ADT List

2.本程序包括三个模块:

1）主程序模块：

void main（）{

初始化；

输入数据；

函数调用；

}

2）构造链表并输入每个人信息的模块-----实现线性表的抽象数据类型；

3）运行模块-----模拟约瑟夫环依次出列；

各模块之间调用关系如下：

主程序模块

↓

构造链表并输入每个人信息的模块

↓

运行模块

三、详细设计

1.结点类型和指针类型

typedef struct Node{

int num;

int password;

struct Node *next;

}LNode,*LinkList;//结点类型,指针类型

Status MakeNode（LinkList &p，Elem Type e）

{

//分配由p指向的数据元素为e、后继为“空”的特点，并返回TRUE，//若分配失败，则返回FALSE

P=(LinkType)malloc（sizeof（NodeType））；

If（！p）return FALSE；

p->data=e；p->next=null；return TRUE；

}

viod Free Node（Link Type &p）

{

//释放p所指结点

}

2.主函数和其他函数

int main()

{

//主函数

LinkList L = NULL;

LinkList s ,r;

int n,i,j,m;//初始化

printf(“请输入人数nn”);

scanf(“%d”,&n);

printf(“请输入mn”);

scanf(“%d”,&m);

printf(“请依次输入每个人的密码n”);//输入数据

CreatList(L,s,r,n);//创建链表run(L,n,m);//模拟约瑟夫环并输出

return 0;

}//main

void CreatList(LinkList &L,LinkList &s,LinkList &r,int n)

{

//创建链表

int i=1;

s=(LNode*)malloc(sizeof(LNode));//分配空间

scanf(“%d”,&s->password);//输入密码

s->num = i;//序号为i

if(L==NULL)

L=s;

else

r->next=s;

r=s;//为下次连接做准备

for(i=2;i<=n;i++)

{

s=(LNode*)malloc(sizeof(LNode));//分配空间

scanf(“%d”,&s->password);

s->num = i;

r->next=s;//连接到下个结点

r=s;//为下次连接做准备

}

r->next = L;//闭合L = r;

} // void CreatList

void run(LinkList &L,int n,int m)

{

//模拟约瑟夫环并输出

LinkList s,r;

int i,j;

for(i = 0;i < n;i ++)

{

for(j = 1;j < m;j ++)

L = L->next;//报数

s = L->next;

r = s->next;

printf(“%dn”,s->num);//输出序号

m = s->password;

L->next = r;

free(s);//删除结点

}

}//run

3.函数的调用关系图反映了演示程序的层次结构:

main

↓↓

CreatListrun

↓↓

Make NodeFree Node

四、调试分析

1.刚开始由于使用头结点,使得程序不符合要求。

2.在写程序时忽略了一些变量参数的标识“&”,使调试程序费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。

3.本程序模块划分比较简单且容易看懂，但头指针赋空不太合理。

4.本实习作业采用数据抽象的设计方法，将程序划分为3个层次，使得设计时思路清晰，实现调试顺利

五、用户手册

1.本程序运行环境为DOS操作系统，执行文件为约瑟夫环.exe。

2． 进入演示程序后出现提示信息：

“请输入人数n”

输入后，出现提示信息：

“请输入m”

输入后，出现提示信息：

“请依次输入每个人的密码”

输入后，显示相应的结果。

第二篇：数据结构课程设计——约瑟夫环报告(含代码)

#include #include

typedef struct LNode {

//数据域

int cipher;

//密码

int number;

//编号

struct LNode *next;

//指针域 }LNode,*LinkList;

void InitList(LinkList &L)

//创建一个只有头结点链表 { L =(LinkList)malloc(sizeof(LNode));if(!L){

exit(1);

printf(“/n/nError!/n/n”);} L->next = L;}

void CreateList(int n,LinkList &L)//初始化循环单链表 { LinkList p,q;q = L;printf(“分别输入每个人的密码：”);for(int i = 1;i <= n;i++){

int k;

scanf(“%d”,&k);

if(k <= 0)

{

printf(“nn密码有误!nn”);

exit(1);

}

p =(LinkList)malloc(sizeof(LNode));

if(!p)

{

exit(1);

printf(“/n/nError!/n/n”);

}

p->cipher = k;

p->number = i;

L->next = p;

L = p;} L->next = q->next;free(q);}

void PrintList(int x,int n,LinkList L)//输出出列顺序 { LinkList p,q;p = L;for(int i = 1;i <= n;i++){

for(int j = 1;j < x;j++)

p = p->next;

q = p->next;

x = q->cipher;

printf(“%d ”,q->number);

p->next = q->next;

free(q);} }

int main(){ printf(“=============约瑟夫环==============nnn”);

int n,x;LinkList L;L = NULL;InitList(L);

//构造空链表

printf(“输入初始密码：”);scanf(“%d”,&x);

//初始密码为x printf(“n”);printf(“输入参与总人数：”);scanf(“%d”,&n);

//总共的人数n printf(“n”);CreateList(n,L);

//建立好一个约瑟夫环

printf(“nnn===================================nn”);

printf(“出列编号为：”);PrintList(x,n,L);

//输出出列顺序

printf(“nn”);return 0;}

第三篇：约瑟夫环课程设计实验报告

《数据结构》

课程设计报告

课程名称：

课程设计题目：姓名： 院系： 专业： 年级： 学号： 指导教师： 《数据结构》课程设计

joseph环

计算机学院

2011年12月18日

目 录 课程设计的目的………………………………………………………………2 2 需求分析………………………………………………………………………2 3 课程设计报告内容……………………………………………………………3

1、概要设计……………………………………………………………………3

2、详细设计……………………………………………………………………3

3、调试分析……………………………………………………………………x

4、用户手册……………………………………………………………………x

5、测试结果……………………………………………………………………6

6、程序清单……………………………………………………………………7 4 小结 …………………………………………………………………………10

1、课程设计的目的

（1）熟练使用C++编写程序，解决实际问题；

（2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

2、需求分析

1、问题描述：

编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

2、要求：

利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

3、测试数据：

m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

输出形式：建立一个输出函数，将正确的输出序列

3、课程设计报告内容

概要设计：

在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。

详细设计：

我先建立一个结构体，与单链表一样，只是多了一个存密码的code域

struct LinkNode {

int data;

//顺序

int code;

//密码

LinkNode *next;

};建立一个类LinkList ,包含的函数：

LinkList();

//构造函数

void Creat(const int);

//创建循环链表

int Delete(LinkNode*);

//删除报到数的结点

int Joseph(int);

// 约瑟夫环 私有成员是

LinkNode* head;

//指向第一个结点的指针 LinkNode* elem;

// 同上

int len;

//长度

我定义了一个elem指针是为了约瑟夫环里运行方便，elem只在约瑟夫环这个函数里用到，其他函数没有特别大的用处。

构造函数与书上的没什么大差别，创建循环链表时，要考虑几个问题，一个是题目要求是不带头结点，所以head指针直接指向了第一个结点，我在创建链表时把第一个结点初始化data为1，表明这个结点是第一个结点。具体如下：

void LinkList::Creat(const int number)

//number为结点个数，也就是参与的人数 {

if(number==1)

//只有一个人的情况 {

head=elem=new LinkNode;

head->data=1;

cout<<“请输入密码:”<

cin>>head->code;

head->next=head;}

else {

head=elem=new LinkNode;

head->data=1;

cout<<“请依次输入各个密码:”<

cin>>head->code;LinkNode*q=head;

q=head;

for(int i=1;i

//将每个结点链接上，在链接时填入密码 {

LinkNode*p=new LinkNode;

p->data=i+1;

cin>>p->code;

q->next=p;

q=p;}

q->next=head;

//构成循环链表 }

len=number;}

在构建约瑟夫环的执行函数时，我首先考虑了递归调用的函数，原本的这个程序的所有的都定为elemtype类型的，虽然编译没出错，但是在连接时发生了错误，在老师的指导下改成了具体的int型。int LinkList::Joseph(int m){

if(len>1){

LinkNode *q;if(m==1)

//在初始报数为1的情况下

{ q=elem;int a=q->code;

//将选中的结点的密码记录在a中 elem=elem->next;cout<

//用已经删除的结点的存的密码作为下一次循环的报数值 } else

//一般情况下 { for(int i=1;i

elem=elem->next;//找到需要出列的结点

q=elem;elem=elem->next;

//此处的elem指针指向要删除的结点的下一个结点，下

次递归调用时从这里开始向下循环报数

int a=q->code;

cout<

//在只有一个结点的情况下 cout<data;}

最后还有一个Delete函数，在删除结点的时候要考虑几个特殊情况，头尾结点。删除第一个结点时，需要将head指针下移，尾结点的next也要指向第二个结点；删除尾结点时，要将尾结点前的结点与第一个结点相连。在设计这个函数时，我只考虑了当len大于1的情况，在只剩下一个结点时，不必要删除，直接输出data的值即可（在约瑟夫函数中有写）。具体函数如下： int LinkList::Delete(LinkNode *a)

{

if(len>1)//只考虑长度大于1的情况

{

if(head==a){

int out=head->data;LinkNode* q=head;

while(q->next!=head){

q=q->next;} q->next=head->next;head=head->next;delete a;len--;

//用len记录删除后的循环链表的长度 return out;}

else

{ LinkNode* q=head;int out=a->data;

while(q->next!=a){

q=q->next;} if(a->next=head).//删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）

{

q->next=head;

//重新链接

delete a;

len--;

return out;} else

{

q->next=a->next;

delete a;

len--;

return out;

} }

} }

5、测试结果： 程序清单：

#include struct LinkNode {

int data;

int code;

LinkNode *next;};

class LinkList { public:

LinkList();

void Creat(const int);

//~LinkList();

int Delete(LinkNode*);

int Joseph(int);

private:

LinkNode* head;

LinkNode* elem;

int len;

};

LinkList::LinkList()

{

head=elem=NULL;

len=0;}

void LinkList::Creat(const int number)

{

if(number==1){

head=elem=new LinkNode;

head->data=1;

cout<<“请输入密码:”<

cin>>head->code;

head->next=head;}

else {

head=elem=new LinkNode;

head->data=1;

cout<<“请依次输入各个密码:”<

cin>>head->code;

LinkNode*q=head;

q=head;

for(int i=1;i

{

LinkNode*p=new LinkNode;

p->data=i+1;

cin>>p->code;

q->next=p;

q=p;

}

q->next=head;}

len=number;}

int LinkList::Delete(LinkNode *a)

{

if(len>1)

{

if(head==a)

{

int out=head->data;

LinkNode* q=head;

while(q->next!=head)

{

q=q->next;

}

q->next=head->next;

head=head->next;

delete a;

len--;

return out;

}

else

{

LinkNode* q=head;

int out=a->data;

while(q->next!=a)

{

q=q->next;

}

q->next=a->next;

delete a;

len--;

return out;

}

} }

int LinkList::Joseph(int m){

if(len>1){

LinkNode *q;

if(m==1)

{

q=elem;

int a=q->code;

elem=elem->next;

cout<

Joseph(a);

}

else

{

for(int i=1;i

elem=elem->next;

q=elem;

elem=elem->next;

int a=q->code;

cout<

Joseph(a);

} } else

cout<data;}

int main(){

int num,code;

cout<<“请输入人数: ”;

cin>>num;

LinkList L;

L.Creat(num);

cout<<“请输入第一个上限数:

”;

cin>>code;

cout<<“出列顺序:”<

L.Joseph(code);

return 0;}

4、小结

一、这次课程设计的心得体会通过实践我的收获如下：

一开始接触数据结构课程设计真的挺难的，好多都不会，不是逻辑方面的问题，而是不具备动手能力，脑子里总有一团火，比如对于这个题目，一开始有很多的想法，想到了从逻辑上怎么实现他，要编写哪些程序，但是一到需要编写了就开始为难了，可以说是几乎不知道从哪里入手，参考了书本里的程序，仿照他的结构一步一步做下来，现在对于单链表的各种操作已经算是比较熟练了，让我知道光有理论知识还远远不够，需要多动手，写的多了自然就能手到擒来。

二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：

1、认真上好专业实验课，多在实践中锻炼自己。

2、写程序的过程中要考虑周到，严密。

3、在做设计的时候要有信心，有耐心，切勿浮躁。

4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。

5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。

第四篇：数据结构实验二 求解约瑟夫问题

数据结构实验二

求解约瑟夫问题

问题描述：使用代表头节点的循环单链表解决此问题。设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人离开。接着从出列的下一个人开始重新从1开始报数，数到m的人又出列，如此下去直到所有的人都出列为止。求出他们的出列序列。

问题分析：例如，当n=8,m=4时，若从第一个人开始报数（设从1开始编号），则得到的序列是：4，8，5，2，1，3，7，6。算法：

void Josephus(int n, int m,int s)

{ //生成表头节点，空单循环链表

LNode * HL = new LNode;

HL-> next = HL;

int i;//生成含有 n 个节点的、节点值依次为1，2……，n的带表头节点的循环单链表

For(i = n;i>=1;i--)

{ LNode * newptr = new LNode;

Newptr-> data = i;

newptr-> next = HL-> next;

HL-> next = newptr;}

//从表头开始顺序查找出第s个节点，对应第一个开始报数的人 LNode * ap = HL, *cp = HL->next;for(i= 1;i

ap = cp;

cp = cp->next;if(cp = = HL){ ap = HL;cp = HL->next;} } //依次使n-1个人出列 for(i=1;i

//顺序查找出待出列的人，即为循环结束后cp所指向的节点

for(int j=1;jnext;if(cp ==HL){ ap = HL;cp = HL->next;} } //输出cp节点的值，即出列的人

cout << cp->data <<”

“;//从单链表中删除cp节点

ap-> next = cp-> next;delete cp;//使cp指向被删除节点的后续节点

cp = ap-> next;//若cp指向了表头节点，则后移ap和cp指针 if(cp = = HL){ ap = HL;cp = HL-> next;} }

//使最后一人出列

count << HL->next-> data << end1;

//删除表头节点和表头附加节点

delete HL->next;

delete HL;}

补充操作系统练习：

1、有一个虚拟存储系统, 每个进程在内存占有3页数据区、1页程序区.刚开始时数据区为空.有以下访页序列: 1、5、4、1、2、3、2、1、5、4、2、4、6、5、1

试给出下列情形下的缺页次数:

(1)系统采用先进先出(FIFO)淘汰算法.(2)系统采用最近最少使用(LRU)淘汰算法.(3)若采用优化(OPT)淘汰算法呢?

2、设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：

最大需求量

已分配资源量

剩余资源量

A

B

C

A

B

C

A

B

C

P1 8

P2 4

P3 10 1

P4 3

P5 5(1)系统是否处于安全状态？如是，则给出进程安全序列.(2)如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？

3、在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示.作业号

进入时刻

估计运行时间

优先级

JOB1

8：00

90分钟

JOB2

8：10

30分钟

JOB3

8：30

20分钟

JOB4

8：50

15分钟

JOB5

9：20

10分钟

JOB6

9：40

5分钟系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以按照优先级进行进程调度.（1）试给出各个作业的运行时间序列.（例如：JOB1：8：00-8：30，9：10-9：20，…）

（2）试计算出作业的平均周转时间.

第五篇：题目：约瑟夫环问题

数据结构上机实验报告

02090401 12 雒文杰 题目：约瑟夫环问题

一．问题描述

设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。

二．基本要求

运用循环单链表解决约瑟夫环问题。

三．算法说明

本程序采用循环单链表的算法来解决约瑟夫环问题：建立一个循环单链表，按顺序查找指定结点，找到后删除，最后打印删除的编号序列。

四 ．源程序清单 #include #include #define n 7 #define NULL 0 struct clist {int data,order;

/* 人的序号, 密码*/ struct clist *next;

/* 指向下一个节点的指针 */ };typedef struct clist cnode;typedef cnode *clink;clink createclist(int *array,int len)

/* 建立循环链表 */ {clink head;clink before;clink new_node;int i;head=(clink)malloc(sizeof(cnode));if(!head)return NULL;head->data=array[0];head->order=1;head->next=NULL;before=head;for(i=1;i

if(!new_node)

return NULL;

new_node->data=array[i];

new_node->order=i+1;

new_node->next=NULL;

before->next=new_node;

before=new_node;} new_node->next=head;return head;} void main(){clink head,ptr;int find,j,i,a,list[n];printf(“Please input 'm'n”);for(i=0;i

printf(“n”);} head=createclist(list,n);printf(“input first 's'n”);scanf(“%d”,&a);for(i=1;inext;ptr=head->next;head->next=ptr->next;find=ptr->data;printf(“order is %dn”,ptr->order);free(ptr);for(j=1;j

head=head->next;

ptr=head->next;

head->next=ptr->next;

find=ptr->data;

printf(“order is %dn”,ptr->order);

free(ptr);

/* 让最后一个人也出列 */ } }