Joseph ring - known to n - (numbered 1, 2, 3... n, respectively) sitting around a round table. Number of people began to count off, from Numbers for 1 to 3 out the man; His next start from 1 number off, the man count to three
and break the ranks; In accordance with the law repeatedly, until the round out all the people around you.
Can use the list to solve the problem:
1. Manner to establish a chain of n nodes, the headless circular linked list of nodes;
2. Determine the position of the first count off people;
3. Continuously is removed from the list chain node, until the list is empty.
Create a one-way chain cycle table, the head,Tail, cur. Head to the head of the list pointer, the addition of cur for the new node, tail to tail node,
约瑟夫环————已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到3的那个人出列;他的下一个人又从1开始报数,数到3的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
可采用链表解决问题:
⒈建立一个具有n个链结点,无头结点的循环链表;
⒉确定第1个报数人的位置;
⒊不断地从链表中删除链结点,直到链表为空。
创建一个单向链循环表,head为链表的头指针,新增的cur为新建的节点,tail为尾节点,
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int id;
struct node *next;
}*LIST;
LIST JoCreate(int nu)
{
int i;
LIST head = NULL;
LIST tail = NULL;
LIST cur;
for(i = 1; i <= nu; i++)
{
if(head != NULL)
{
cur = malloc(sizeof(*cur));
if(NULL == cur)//dispose
return NULL;
cur->id = i;
tail->next = cur;
cur->next = head;
tail = cur;
}
else
{
head = malloc(sizeof(*head));
if(NULL == head)
return NULL;
head->id = i;
head->next = head;
tail = head;
}
}
return head;
}
void JoDispaly(LIST jo)
{
LIST p = jo;
do
{
printf("%d ", p->id);
p = p->next;
}while(p != jo);
printf("\n");
}
LIST JoKill(LIST jo, int nu)
{
int i;
LIST p = jo;
LIST q;
while(p->next != p)
{
for(i = 1; i < nu - 1; i++, p = p->next);
q = p->next;
p->next = q->next;
p = q->next;
free(q);
}
return p;
}
void JoDispose(LIST jo)
{
LIST q;
LIST p = jo->next;
while(p != jo)
{
q = p;
p = p->next;
free(q);
}
free(jo);
}
int main()
{
LIST jo = JoCreate(41);
JoDispaly(jo);
jo = JoKill(jo, 3);
JoDispaly(jo);
return 0;
}