单向循环链表实现约瑟夫环

《单向循环链表实现约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单向循环链表实现约瑟夫环CirLinkList(单向循环链表实现约瑟夫环)/***************************************************************************描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素(有数据)的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操

2、作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。简而言之，头指针：指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点：在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）首元素结点：指链表

3、中存储线性表中第一个数据元素的结点。***************************************************************************//**************************************************************************约瑟夫环问题由来：约瑟夫环问题是以弗拉瓦斯·约瑟夫斯的名字命名的，他是一个著名的犹太历史学家，参加并记录了公元66－70年犹太人反抗罗马的起义。约瑟夫斯作为一个将军，设法守住了裘达伯特

4、的堡垒达47天之久，但在城市陷落了以后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫斯建议每个人应该轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫斯有预谋的抓到了最后一签，并且作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降罗马。（摘自《Introductiontothedesignandanalysisofalgorithms》）***********************************************************

5、****************///stdafx.h:标准系统包含文件的包含文件，//或是常用但不常更改的项目特定的包含文件//#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineNULL0typedefintStatus;typedefintElemType;typedefstructLNode{intnum;ElemTypedata;structLNode*next;/*指向后继结点

6、*/}LNode,*CirLinkList;//这是使用应用程序向导生成的VC++//应用程序项目的主项目文件。//线性表的单向循环链式表示和实现//josephus经典环#include"stdafx.h"#include"stdio.h"#include"malloc.h"#include"stdlib.h"//需要exit所加头文件#include"iostream.h"#include#using#includeusingnamespaceSy

7、stem;StatusCreateList(CirLinkList&L,intn){//尾插法//顺位序输入n个元素的值,建立带尾指针的循环链线性表L，//直接创建首元结点,即没有头结点。同时不设头指针。//设一“不带头结点”的单循环链表，其尾指针为rear，则//首元结点和终端结点的位置分别是rear->next和rear。//注意：首元结点是数据域非空的结点。它前面没有了头结点//头结点数据域一般是空的。inti;structLNode*p,*Head,*rear;//H为头指针p=NULL;Head=NULL;

8、rear=Head;if(n>0){for(i=1;i<=n;++i){p=(CirLinkList)malloc(sizeof(LNode));//创建新结点cout<<"Enter"<>p->data;//输入元素值p->num=i;if(Head==NULL)//创建首元结点，Head=p;else//将p插在尾结