循环链表实现约瑟夫问题
问题来历
解决方法与过程
方法
初学数据结构的循环链表，正好利用循环链表可以很容易的解决上述问题。
代码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int Elemtype;
#define len sizeof(Node)
#define N 41 //总人数 41
#define m 3 //密码固定为3
typedef struct Node
{
Elemtype data;
struct Node* next;
}Node;
typedef struct Node Linklist;
Linklist* Creat_list();
void Out_list(Linklist *L);
void ysf_out_list(Linklist *L);
void main()
{
Linklist *L;
L = Creat_list();
printf("链表输出：");
Out_list(L);
printf("死亡序列：");
ysf_out_list(L);
}
// <初始化函数>
Linklist* Creat_list()
{
Linklist *h;
Linklist *p;
Linklist *s;
int i = 1;
h = (struct Node*)malloc(len);
h->next = NULL;
p = h;
while(i<=N)
{
s = (struct Node*)malloc(len);
s->data = i; //循环链表的编号域data域从1依次赋值
s->next = NULL;
p->next = s;
p = s;
i++;
}
p->next = h->next;
free(h);
return p;
}
// <初始化链表输出函数>
void Out_list(Linklist *L)
{
Linklist *p;
int i = 1;
p = L->next;
while(i<=N)
{
if(i<N)
{
printf("%d->",p->data);
p = p->next;
}
if(i == N)
{
printf("%d",p->data);
}
i++;
}
//printf("\n%d\n",p->next->data); //仅用于测试
printf("\n\n");
}
// <约瑟夫环问题函数>
void ysf_out_list(Linklist *L)
{
Linklist *temp;
Linklist *p;
int i = 1;
int j = 1;
int t;
p = L;
t = m%N;
while(i<=N)
{
for(j=1;j<t;j++)
{
p = p->next;
}
if(i<N)
{
printf("%d->",p->next->data);
}
if(i==N)
{
printf("%d",p->next->data);
}
temp = p->next;
p->next = temp->next;
free(temp);
i++;
}
printf("\n\n");
}
运行测试结果
进阶约瑟夫问题
问题的修改与陈述
区别
<1> 每个节点多了一个密码域，用来储存各自的报数上限。
<2> 相比简单的约瑟夫问题，只需要克服密码值会动态变换的问题即可，利用循环链表对上述代码简单修改即可。
代码
// ★★★假设共有5个节点(如果想增加更多的节点，可以在宏定义中，仅修改N的值即可)★★★
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int Elemtype;
#define len sizeof(Node)
#define N 5 //★★★总人数确定值，本例假设为 5
typedef struct Node
{
int skew; //密码
Elemtype data; //编号、数据
struct Node* next; //指针
}Node;
typedef struct Node Linklist;
Linklist* Creat_list();
void Out_list(Linklist *L);
void ysf_out_list(Linklist *L);
void main()
{
Linklist *L;
L = Creat_list();
printf("链表输出：");
Out_list(L);
printf("死亡序列：");
ysf_out_list(L);
}
Linklist* Creat_list()
{
Linklist *h;
Linklist *p;
Linklist *s;
int i = 1;
printf("★★★进阶约瑟夫问题★★★\n\n");
h = (struct Node*)malloc(len);
h->next = NULL;
p = h;
while(i<=N)
{
s = (struct Node*)malloc(len);
s->data = i; // 循环链表的编号域data域从1依次赋值
printf("请输入第%d个节点的密码：",i);
scanf("%d",&s->skew); // 循环链表的密码域skew
printf("\n");
//s->skew = N-i+1;
s->next = NULL;
p->next = s;
p = s;
i++;
}
p->next = h->next;
free(h);
return p;
}
// <初始化链表输出函数>
void Out_list(Linklist *L)
{
Linklist *p;
int i = 1;
p = L->next;
while(i<=N)
{
if(i<N)
{
printf("%d->",p->data);
p = p->next;
}
if(i == N)
{
printf("%d",p->data);
}
i++;
}
//printf("\n%d\n",p->next->data); 仅仅用于测试，可以忽略
printf("\n\n");
}
// <进阶约瑟夫环问题>
void ysf_out_list(Linklist *L)
{
Linklist *temp;
Linklist *p;
int i = 1;
int j = 1;
int t;
p = L;
//printf("%d\n",p->next->data); //仅仅用于测试，可以忽略
//printf("%d\n",p->next->skew);
t = p->next->skew; //★★★将第一个节点的skew值作为初始报数上限,并从此处开始执行循环
while(i<=N)
{
//t = m%N; //仅仅用于测试，可以忽略
for(j=1;j<t;j++)
{
p = p->next;
}
if(i<N)
{
printf("%d->",p->next->data);
}
if(i==N)
{
printf("%d",p->next->data);
}
temp = p->next;
t = p->next->skew; //★★★修改t值：将出列的下一个的skew值作为t值->报数上限
p->next = temp->next;
free(temp);
i++;
}
printf("\n\n");
}
运行测试结果
总结
初学数据结构，继续加油！！！！