1.循环链表和约瑟夫
循环链表：将单链表的首尾连接，使其成为了一个环状链表，通常称为循环链表。
约瑟夫环：是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
2.算法思路
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int number;
struct node* next;
}person;
person *initLink(int n)
{
person *head=(person*)malloc(sizeof(person));
head->number=1;
head->next=NULL;
person *cyclic=head;
int i;
for(i=2;i<=n;i++)
{
person *temp=(person*)malloc(sizeof(person));
temp->number=i;
temp->next=NULL;
head->next=temp;
head=head->next;
}
head->next=cyclic;
return cyclic;
}
void linkPrint(person *temp)
{
person *head=temp;
if(!temp)
printf("the link is empty\n");
else
{
while(temp)
{
printf("%d\t",temp->number);
temp=temp->next;
if(temp==head)
break;
}
}
}
void findANDkill(person *head,int k,int m)
{
person *tail=head;
//找到链表第一个结点的上一个结点，为删除操作做准备
while(tail->next!=head)
tail=tail->next;
person * p=head;
//找到编号为k的人
while(p->number!=k)
{
tail=p;
p=p->next;
}
//从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，
while(p->next!=p)
{
//找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。
for(int i=1;i<m;i++)
{
tail=p;
p=p->next;
}
tail->next=p->next;//从链表上将p结点摘下来
printf("出列人的编号为:%d\n",p->number);
free(p);
p=tail->next;//继续使用p指针指向出列编号的下一个编号，游戏继续
}
printf("出列人的编号为:%d\n",p->number);
free(p);
}
int main()
{
int n,k,m;
printf("请输入圆桌上的人数：\n");
scanf("%d",&n);
person *head=initLink(n);
//linkPrint(head);
printf("从第k人开始报数(k>1且k<%d)：",n);
scanf("%d",&k);
printf("数到m的人出列：");
scanf("%d",&m);
findANDkill(head,k,m);
return 0;
}
| 
楼主
标题置顶
标题高亮
