数据结构实验报告.doc

数据结构实验报告
实验一线性表实验
约瑟夫问题求解

设有编号为1,2,···,n(n>0)的个人围成一个圈,每个人持有一个密码m。从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈······如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。

(1)建立模型,确定存储结构
(2)对任意n个人,密码为m,实现约瑟夫问题
(3)出圈次序依次输出

该实验主要要求用线性表完成一些具体问题的应用,在实验中需用到顺序表的定义,循环单链表的建立以及节点类型的选择等问题,将用到模板函数LinkList,其中各头文件的定义如下:
顺序表结点类型:
template<class T>
struct Node
{
T data;//存放个人的编号
Node<T> *next;//存放个人的密码
};
:
template<class T>
struct Node
{
T data;//存放个人的编号
T code;//存放个人密码
Node<T> *next;
};
单链表模板:
#include""
template<class T>
class LinkList
{
public:
Node<T> *first;
LinkList<T>(T a[],T b[],int n)
{
first=new Node<T>;
first->data=a[0];
first->code=b[0];
Node<T> *r=first,*s;
for(int i=1;i<n;i++)
{
s=new Node<T>;
s->data=a[i];
s->code=b[i];

r->next=s;
r=s;
}
r->next=first;
}//建立有n个元素的单链表
};

(1)顺序表存储时
A、m相同
void Josephus(int a[],int n,int m)
{
int s=0;//length表示表长
cout<<setw(3);
for(int length=n;length>=2;length--)//表示每次减一
{
s=(s+m-1)%length;
cout<<a[s]<<setw(7);//s为第s个人
for(int i=s+1;i<length;i++) a[i-1]=a[i];//删除
}
cout<<a[0]<<endl;//最后只剩下一个人
}
B、m不同
void Josephus(Node<int> data[],int n,int m)
{
int s=0,k;//k用于保存出圈人的密码
cout<<"个人的编号和密码分别为:"<<'\n';
for(int length=n;length>=2;length--)
{
if(length==n)
s=(s+m-1)%length;
else
s=(s+k-1)%length;
k=data[s].next->data;
cout<<data[s].data<<","<<k<<'\t';
for(int i=s+1;i<length;i++)
data[i-1]=data[i];
}
cout<<data[0].data<<","<<data[0].next->data<<endl;
}
(2)循环单链表存储时
A、m相同
void Josephus(LinkList<int> *d,int m)
{
Node<int> *p=d->first,*pre,*last=d->first;
int count;
cout<<"出队序号为:"<<'\n';
while(last->next!=d->first) last=last->next;
while(p->next!=p)
{
count=m;
if(count==1)
{
cout<<p->data<<'\t';
pre=p;
p=p->next;
delete pre;
last->next=p;
}
else
{
while(--count)
{
pre=p;
p=p->next;
}
cout<<p->data<<'\t';
pre->nex