约瑟夫环实习报告(参考)

1. 本程序将模拟约瑟夫问题，求出出列的编号，并在每次出列后显示此时的顺序，本程序

采用循环链表作为存储结构，无带头结点。

2. 输入可以是文件输入或标准输入，链表长度size>0，各个结点所带的密码值secret>0,

第一次的报数m>0，若m<1，将提示更正。

3. 本程序在输入完毕后将先输出刚输入的内容,再提供报数后，开始进行运算,每出列一次

将显示出列者和出列后链表顺序。

4. 测试数据：长度7，密码：3,1,7,2,4,8,4，报数初值6；长度-1，密码：3,2,5,6,4；长度5，

密码：3,2,5,0,4; 长度5，密码：3,2,5,6,4，报数初值-1,4。

二﹑概要设计

采用循环链表表示约瑟夫环 1. 循环链表的抽象定义： ADT CycList{

数据对象:D={ai,bi|ai,bi∈I,i=1,2,…3,n>0} 数据关系:R={|ai,bi∈D,I=1,2…3}

基本操作:

CreatList(&L,&in)

初始条件：输入流有效，输入的值合法，申请空间成功 操作结果：构造一个非空的循环链表 PrintList(const L)

初始条件：循环链表L已存在 操作结果：输出L Fun(&L,Secret)

初始条件：循环链表L已存在 操作结果：得到出列顺序 }

2. 本程序包含两个模块：

1) 主程序模块 2) 循环链表模块

三﹑详细设计

#include using namespace std; //每个人的号码和密码。 struct people { int NO; int pass; }node;

template class Link { private:

static Link* freelist;//静态数据成员的头接点。 public:

struct people element; Link* next;

Link(people elemval,Link* nextval=NULL) {

element.NO=elemval.NO; element.pass=elemval.pass; next=nextval; }

Link(Link* nextval=NULL) {

next=nextval; }

void* operator new(size_t);// 重载new 函数。 void operator delete(void*);//重载delete函数。 };

template class LList { private:

Link *head; Link *tail; Link *fence; void init() {

head=tail=fence=new Link;

tail->next=head->next; //生成链表是要把它的头接点和尾接点连接起来构成循环链表。

//因为有一个空的头接点。所以要把他的尾接点接到头接点的下一个指针。 }

void removeall() {

while(head!=NULL) {

fence=head; fence=fence->next; delete fence;

} } public: LList() { init(); } ~LList() {

removeall(); }

bool insert(const people& T); bool remove(Elem&); void getOut(int&,int&); void prev();

bool append(const people& T); };

template

Link* Link::freelist=NULL;//静态数据成员的初始化。 //重载的实现。 template

void* Link::operator new(size_t) {

if(freelist==NULL) return ::new Link; Link* temp=freelist; freelist=freelist->next; return temp; }

//重载的实现 template

void Link::operator delete(void* ptr) {

((Link*)ptr)->next=freelist;

freelist=(Link*)ptr; }

//插入函数。此程序并没有用到次函数。 template

bool LList::insert(const people& T) {

fence->next=new Link(T,fence->next);//通过调用构造函数的初始化。 if(tail==fence) {

tail=fence->next; tail->next=head->next; } return true; }

//从链表的尾插入。 template

bool LList::append(const people& T)

{

tail=tail->next=new Link(T,head->next);//通过调用构造函数的初始化。 return true; }

template

bool LList::remove(Elem& it) {

if(tail==head) return false;

if(fence->next==NULL) {

it=fence->element.pass;

cout<element.NO<<\"-- \"; return true; }

it=fence->next->element.pass;

cout<next->element.NO<<\"-- \";

Link* temp=fence->next; fence->next=temp->next; if(temp==tail) {

tail=fence;//当是尾接点的时候要把他的尾指针指向标记指针 }

delete temp; return true; }

//找下一个接点。 template void LList::prev() {

if(fence->next!=head) fence=fence->next; else

{

fence->next=head->next; fence=fence->next; } }

//程序的主题// template

void LList::getOut(int &it,int& sum) {

int sign,n=1;

fence=tail;//因为是从报到数的上一个人开始找到的删除点。所以要记得从head的上一个接点tail开始。

cout<<\"Enter you want to first get out:\"; cin>>sign;//报数值。 while(sum>0) {

if(sign>sum&&sign>1) //为避免多次的循环找数通过取模可以节省时间。 sign=sign%sum; if(sign==n||sum==1) {

remove(it); sign=it; sum--;

n=0;//重新做标记从下一个人1开始。 } else

prev();//找下个接点。 n++; } } int main()

{

LList A; struct people T; int item,it,sum;

cout<<\"Enter you want to people:\"; cin>>sum;

for(int i=1;i<=sum;i++) {

cout<<\"enter the--\"<>item; T.NO=i; T.pass=item;

A.append(T);//我这里是从尾插入的。 cout<A.getOut(it,sum); return 0;

}四﹑调试分析

做此题关键点看是否把循环链表真的循环了，还有就是在删除接点的时候.

要连接.特别是删除了尾接点.做好这些了，就是在进行报数出列的时候对报数和你做标记的处理.还有就是在当密码数大于个数是要进行取模减少循环次数.节约时间. 此程序已经运行过是正确的.

五．测试结果

输入人数，密码

(1) 测试数据：size=7；secret=3,1,7,2,4,8,1；第一次报数:6；

(2) 测试数据：size=-1；第一次报数:无

(3) 测试数据：size=5；secret=3,2,5,0,4；

(4) 测试数据：size=5；secret=3,2,5,6,4；第一次报数-1；