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

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

ID:14117707

大小:47.00 KB

页数:12页

时间:2018-07-26

单向循环链表实现约瑟夫环_第1页
单向循环链表实现约瑟夫环_第2页
单向循环链表实现约瑟夫环_第3页
单向循环链表实现约瑟夫环_第4页
单向循环链表实现约瑟夫环_第5页
资源描述:

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

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插在尾结

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。