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

CirLinkList(单向循环链表实现约瑟夫环)



/***************************************************************************
描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链
表中设置头结点的作用是什么？

答：首元结点是指链表中存储线性表中第一个数据元素(有数据)的结点。为了操作方便，
通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线
性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对
首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）
的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示
空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设
置头结点，是不同的存储结构表示同一逻辑结构的问题。

简而言之，

头指针：指向链表中第一个结点（或为头结点或为首元结点）的指针；

头结点：在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信
息（内放头指针？那还得另配一个头指针！！！）

首元素结点：指链表中存储线性表中第一个数据元素的结点。
***************************************************************************/

/**************************************************************************
约瑟夫环问题由来：

约瑟夫环问题是以弗拉瓦斯·约瑟夫斯的名字命名的，他是一个著名的犹太历史学家，参
加并记录了公元66－70年犹太人反抗罗马的起义。约瑟夫斯作为一个将军，设法守住了裘
达伯特的堡垒达47天之久，但在城市陷落了以后，他和40名死硬的将士在附近的一个洞穴
中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫斯建议每个人应该
轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫斯有预谋的抓到了最后一签，
并且作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降罗马。
（摘自《Introduction to the design and analysis of algorithms》）
***************************************************************************/


// stdafx.h : 标准系统包含文件的包含文件，
// 或是常用但不常更改的项目特定的包含文件
//

#define TRUE 1
#define FLASE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULL 0

typedef int Status;
typedef int ElemType;


typedef struct LNode{
int num;
ElemType data;
struct LNode *next; /*指向后继结点*/
}LNode,*CirLinkList;



// 这是使用应用程序向导

生成的 VC++
// 应用程序项
目的主项目文件。
// 线性表的单向循环链式表示和实现
// josephus经典环

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h" //需要exit所加头文件
#include "iostream.h"
#include <stdlib.h>

#using <mscorlib.dll>
#include <tchar.h>
using namespace System;



Status CreateList(CirLinkList &L,int n){ //尾插法
// 顺位序输入n个元素的值,建立带尾指针的循环链线性表L，
// 直接创建首元结点,即没有头结点。同时不设头指针。
// 设一“不带头结点”的单循环链表，其尾指针为rear，则
// 首元结点和终端结点的位置分别是rear->next 和 rear。
// 注意：首元结点是数据域非空的结点。它前面没有了头结点
// 头结点数据域一般是空的。
int i;
struct LNode *p,*Head,*rear; //H为头指针
p=NULL;
Head=NULL;
rear=Head;
if(n>0){
for(i=1;i<=n;++i){
p=(CirLinkList)malloc(sizeof(LNode)); //创建新结点
cout<<"Enter "<<i<<" :";
cin>>p->data; //输入元素值
p->num=i;

if(Head==NULL) //创建首元结点，
Head=p;
else //将p插在尾结点之后
rear->next=p;
rear=p;
}
rear->next=Head;
}
L=rear; //返回尾指针
return OK;
} //CreateList



Status DisplayList(CirLinkList &L){
//输出循环链表L
struct LNode *p,*Head;
if(L){
Head=L->next;
p=Head;
cout<<"CirList Head";
do{
cout<<"->"<<p->data;
p=p->next;
}while(p!=Head);
cout<<endl;
}
else
cout<<"单链线性表为空！"<<endl;
return OK;
} //DisplayList



int ListLength(CirLinkList &L){
//返回循环链表的长度
return L->num;
} //ListLength



Status Josephus(CirLinkList &L,int n,int r,int m){
// 链表一共有n个结点，从已经排好序的循环链表第r个结点位置
// 起数，数到第m个结点，让该结点出局，依次循环下去。
int i,k=0;
struct LNode *p,*q;

p=L->next; //此时的p为初始化时循环链表的头指针
i=1;
while(i!=r){ //扫描链表，找出第r个结点的指针p
p=p->next;
i++;
}

i=1;
while((n-k)>=m){
q=p; //q是前驱指针，p是当前结点指针
p=p->next;
i++;
if(i%m==0){ //删除指定结点
q->next=p->next;
k++; //k是用来计数的，计删除的元素个数
cout<<"删除第"<<k<<"个结点："<<p->data<<"["<<p->num<<"]"<<endl;
p=p->next;
i=1;
}
}
return OK;
} //Josephus


// 这是此应用程序的入口点
int _tmain(void)
{
// TODO: 请用您自己的代码替换下面的示例代码。
int n,from,interval;
CirLinkList newlist;

cout<<"

请输入你的循环链表的结点数：";
cin>>n;
CreateList(newlist,n);
DisplayList(newlist);
cout<<endl<<endl;

do{
cout<<"请输入你想从多少号开始报数from:";
cin>>from;
}while(0>=from || from>n);
cout<<"请输入你删除结点的间隔数interval:";
cin>>inte
rval;
Josephus(newlist,n,from,interval);

return 0;
}
============================================================================================================================================================//#define TRUE 1
//#define FLASE 0
//#define OK 1
//#define ERROR 0
//#define INFEASIBLE -1
//#define OVERFLOW -2
//#define NULL 0

//typedef int Status;
typedef int ElemType;


typedef struct LNode{
int num;
ElemType data;
struct LNode *next; /*指向后继结点*/
}LNode,*CirLinkList;



// 这是使用应用程序向导生成的 VC++
// 应用程序项目的主项目文件。
// 线性表的单向循环链式表示和实现
// josephus经典环


//#include "stdio.h"
//#include "malloc.h"
//#include "stdlib.h" //需要exit所加头文件
#include <stdio.h>
//#include "iostream.h"
#include <stdlib.h>


//#include <tchar.h>




void CreateList(CirLinkList &L,int n){ //尾插法
// 顺位序输入n个元素的值,建立带尾指针的循环链线性表L，
// 直接创建首元结点,即没有头结点。同时不设头指针。
// 设一“不带头结点”的单循环链表，其尾指针为rear，则
// 首元结点和终端结点的位置分别是rear->next 和 rear。
// 注意：首元结点是数据域非空的结点。它前面没有了头结点
// 头结点数据域一般是空的。
int i;
struct LNode *p,*Head,*rear; //H为头指针
p=NULL;
Head=NULL;
rear=Head;
if(n>0){
for(i=1;i<=n;++i){
p=(CirLinkList)malloc(sizeof(LNode)); //创建新结点
printf("Enter %d :",i);
scanf("%d",&p->data); //输入元素值
p->num=i;

if(Head==NULL) //创建首元结点，
Head=p;
else //将p插在尾结点之后
rear->next=p;
rear=p;
}
rear->next=Head;
}
L=rear; //返回尾指针
// return 1;
} //CreateList



void DisplayList(CirLinkList &L){
//输出循环链表L
struct LNode *p,*Head;
if(L){
Head=L->next;
p=Head;
printf("\n");
printf("CirList Head: ");
do{
printf("->%d ",p->data);
p=p->next;
}while(p!=Head);
printf("\n");
}
else
printf("单链线性表为空！\n");
//return 1;
} //DisplayList



int ListLength(CirLinkList &L){
//返回循环链表的长度
return L->num;
} //ListLength



void Josephus(CirLinkList &L,int n,int r,int m){
// 链表一共有n个结点，从已经排好序的循环链表第r个结点位置
// 起数，数到第

m个结点，让该结点出局，依次循环下去。
int i,k=0;
struct LNode *p,*q;

p=L->next; //此时的p为初始化时循环链表的头指针
i=1;
while(i!=r){ //扫描链表，找出第r个结点的指针p
p=p->next;
i++;
}

i=1;
while((n-k)>1){
q=p; //q是前驱指针，p是当前结点指针
p=p->next;
i++;
if(i%m==0){ //删除指定结点
q->next=p->next;
k++; //k是用来计数的，计删除的元素个数
printf("删除第 %d
个结点：[%d]%d\n",k,p->num,p->data);
p=p->next;
i=1;
}

}
//return 1;
} //Josephus


void main()
{

int n,from=1,interval;
CirLinkList newlist;

printf("请输入你的循环链表的结点数：");
scanf("%d",&n);
printf("\n");
CreateList(newlist,n);
DisplayList(newlist);
printf("\n\n");
printf("请输入你删除结点的间隔数:");
scanf("%d",&interval);
Josephus(newlist,n,from,interval);

// return 0;
}