中法计122班实验一.docx

中法计122班实验一.docx

《中法计122班实验一.docx》由会员分享，可在线阅读，更多相关《中法计122班实验一.docx（13页珍藏版）》请在冰点文库上搜索。

中法计122班实验一

数据结构实验一

约瑟夫环问题

班级：

中法计122班

【实验内容】

约瑟夫（Joseph）问题的一种描述是：

编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

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

m的初值为20；n=7，7个人的密码依次为：

3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。

【实验目的】

掌握链表的基本操作：

插入、删除、查找等运算，能够灵活应用链表这种数据结构。

【程序清单】

#include

usingnamespacestd;

structpeople

{

intNUMBER;

intPASSWORD;//每个人的编号和密码

}eachNode;

template//定义类模板

classLink

{

private:

staticLink*freelist;//静态数据成员的头接点。

public:

structpeopleelement;

Link*next;

Link（peopleelemval,Link*nextval=NULL）

{

element.NUMBER=elemval.NUMBER;

element.PASSWORD=elemval.PASSWORD;

next=nextval;

}

Link（Link*nextval=NULL）

{

next=nextval;

}

void*operatornew（size_t）;//重载new函数。

voidoperatordelete（void*）;//重载delete函数。

};

template//类模板

classLinkList

{

private:

Link*headNode;

Link*tailNode;

Link*sta;

voidinitialize（）

{

headNode=tailNode=sta=newLink;

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

//因为有一个空的头接点。

所以要把他的尾接点接到头接点的下一个指针。

}

voidremoveall（）

{

while（headNode!

=NULL）

{

sta=headNode;

sta=sta->next;

deletesta;

}

}

public:

LinkList（）

{

initialize（）;

}

~LinkList（）

{

removeall（）;

}

boolinsert（constpeople&T）;

boolremove（Elem&）;

voidgetOut（int&,int&）;

voidprevious（）;

boolappend（constpeople&T）;

};

template

Link*Link:

:

freelist=NULL;//静态数据成员的初始化。

//重载的实现。

template

void*Link:

:

operatornew（size_t）

{

if（freelist==NULL）

return:

:

newLink;

Link*temp=freelist;

freelist=freelist->next;

returntemp;

}

////当中的new和delete采用了重载函数。

//重载的实现

template

voidLink:

:

operatordelete（void*ptr）

{

（（Link*）ptr）->next=freelist;

freelist=（Link*）ptr;

}

//插入函数。

template//值得注意的是,在类定义外完成函数实现时,必须以关键字template和类模板定义中相同

boolLinkList:

:

insert（constpeople&T）

{

sta->next=newLink（T,sta->next）;//通过调用构造函数的初始化。

if（tailNode==sta）

{

tailNode=sta->next;

tailNode->next=headNode->next;

}

returntrue;

}

//从链表的尾端插入。

template

boolLinkList:

:

append（constpeople&T）

{

tailNode=tailNode->next=newLink（T,headNode->next）;//通过调用构造函数的初始化。

returntrue;

}

template

boolLinkList:

:

remove（Elem&it）

{

if（tailNode==headNode）

returnfalse;

if（sta->next==NULL）

{

it=sta->element.PASSWORD;

cout<element.NUMBER<<"--";

returntrue;

}

it=sta->next->element.PASSWORD;

cout<next->element.NUMBER<<"--";

Link*temp=sta->next;

sta->next=temp->next;

if（temp==tailNode）

{

tailNode=sta;//当是尾接点的时候要把他的尾指针指向标记指针

}

deletetemp;

returntrue;

}

template//寻找下一个接点。

voidLinkList:

:

previous（）

{

if（sta->next!

=headNode）

sta=sta->next;

else

{

sta->next=headNode->next;

sta=sta->next;

}

}

//程序的主体//

template

voidLinkList:

:

getOut（int&it,int&sum）

{

intsign,n=1;

sta=tailNode;//因为是从报到数的上一个人开始找到的删除点。

所以要记得从headNode的上一个接点tailNode开始。

cout<<"请输入第一个出列的人:

";

cin>>sign;//报数值。

if（sign>20）

{

cout<<"请重新输入（不大于20）：

";

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

previous（）;//找下个接点。

n++;

}

}

intmain（）

{

cout<<"中法计122班-122930-徐彤坤\n";

LinkListA;

structpeopleT;

intitem,it,sum;

cout<<"您希望一共有多少人:

";

cin>>sum;

for（inti=1;i<=sum;i++）

{

cout<

";

cin>>item;

T.NUMBER=i;

T.PASSWORD=item;

A.append（T）;//从尾插入的。

cout<

}

A.getOut（it,sum）;

return0;

}

【算法的基本思想】

为了实现上述操作，应以单向循环链表为存储结构。

1． 基本操作：

template定义类模板 

  操作结果：

构造空链表，若成功就初始化每个人的相关信息 

  初始条件：

线性链表存在 

  操作结果：

释放指向出列的人的结点，并重新报数 

2． 本程序包含三个模块：

（1） 主程序模块； 

template

voidLinkList:

:

getOut（int&it,int&sum）

{

intsign,n=1;

sta=tailNode;//因为是从报到数的上一个人开始找到的删除点。

所以要记得从headNode的上一个接点tailNode开始。

cout<<"请输入第一个出列的人:

";

cin>>sign;//报数值。

if（sign>20）

{

cout<<"请重新输入（不大于20）：

";

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

previous（）;//找下个接点。

n++;

}

（2） 插入函数：

boolLinkList:

:

insert（constpeople&T）

{

sta->next=newLink（T,sta->next）;//通过调用构造函数的初始化。

if（tailNode==sta）

{

tailNode=sta->next;

tailNode->next=headNode->next;

}

returntrue;

}

定义类模板：

template//定义类模板

classLink

{

private:

staticLink*freelist;//静态数据成员的头接点。

public:

structpeopleelement;

Link*next;

Link（peopleelemval,Link*nextval=NULL）

{

element.NUMBER=elemval.NUMBER;

element.PASSWORD=elemval.PASSWORD;

next=nextval;

}

Link（Link*nextval=NULL）

{

next=nextval;

}

（3） 释放结点模块；

【调试步骤】

m的初值为20；n=7，7个人的密码依次为：

3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。

首先输入您希望的人数，然后一次输入对应人数的密码，然后再选择在您队列中第一个出列的人。

【运行结果】

【分析与思考】

通过这次实验，让我对链表的基本操作有了更好的认识，达到了实验目的。

在编写程序时我发现本程序的关键点看你是否把循环链表真的循环了，还有就是在删除接点的时候.要记得连接.特别是删除尾接点，做好这些了，就是在进行报数出列的时候对报数和做标记的处理.还有就是在当密码数大于个数是要进行取模减少循环次数.节约时间.

用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。

通过这个设计实例，了解了单链表和单循环链表的相同与不同之处，进一步加深了对链表结构类型及链表操作的理解