约瑟夫环课程设计实验报告.doc

《数据结构》
课程设计报告

课程名称：
《数据结构》课程设计
课程设计题目：
joseph环
姓名：

院系：
计算机学院
专业：

年级：

学号：

指导教师：

2011年12月18日

目 录
1 课程设计的目的………………………………………………………………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<<"请输入密码:"<>head->code;
head->next=head;
}
else
{
head=elem=new LinkNode;
head->data=1;
cout<<"请依次输入各个密码:"<>head->code;
LinkNode*q=head;
q=head;
for(int i=1;iber;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<inext; //找到需要出列的结点
q=elem;
elem=elem->next; //此处的elem指针指向要删除的结点的下一个结点，下次递归调用时从这里开始向下循环报数
int a=q->code;
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、测试结果：

6 程序清单：
#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<<"请输入密码:"<>head->code;
head->next=head;
}
else
{
head=elem=new LinkNode;
head->data=1;
cout<<"请依次输入各个密码:"<>head->code;
LinkNode*q=head;
q=head;
for(int i=1;idata=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< else
{
for(int i=1;inext;
q=elem;
elem=elem->next;
int a=q->code;
cout<data;
}

int main()
{
int num,code;
cout<<"请输入人数: ";
cin>>num;

LinkList L;
L.Creat(num);

cout<<"请输入第一个上限数: ";
cin>>code;

cout<<"出列顺序:"<