约瑟夫问题
约瑟夫问题
设编号分别为：1,2,3,....n的n个人围坐成一圈。约定序号为k（1 <= k <= n）的人从1开始计数，数到m的那个人出列，他的下一位又从1开始计数，数到m的那个人又开始计数。依次类推，直到所有的人都出列为止。
如上图所示，假设n = 8，k = 3,m = 4时。则出列分别为
6,2,7,4,3,5,1,8。
解题思路：
用一个不带头节点的循环链表来处理joseph问题：先构成一个有n个节点的单向循环链表，然后从第k结点从1开始计数，计数到m的时候，对应结点从链表中删除。然后再从被删结点的下一个节点继续从1开始计数.......,以此类推，直到所有的结点都列出时，程序结束。
joseph.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//一、单向循环链表
//特点：尾结点的指针域保存了头结点的地址。
/*二、数据类型*/
typedef int DataType;
typedef struct node
{
DataType data;
struct node *next;
}loopnode,*looplist;
/*三、常用操作*/
/*1.创建空链表，只有一个头结点，且头结点的指针域保存了自己的地址*/
loopnode *create_empty_linklist()
{
//1.为头结点分配空间
loopnode *head = NULL;
head = (loopnode *)malloc(sizeof(loopnode));
//把NULL写在前面是为了防止出现head = NULL.这种情况
if(NULL == head)
{
printf("create head_loopnode is fail!\n");
return NULL;
}
//2.将头结点的指针域赋head
head->next = head;
//3.返回头结点首地址
return head;
}
//2.链表判空,比较head->next 和head。
int is_empty_linklist(loopnode *head)
{
//1.若是head->next 为head，返回 1.
return head->next == head;
// 否则返回0
}
/*3.头插法，在头节点后插入新节点*/
int insert_head_linklist(loopnode *head,DataType data)
{
//1.为新节点在堆区分配空间，用指针temp来保存
loopnode *temp = (loopnode *)malloc(sizeof(loopnode));
if(temp == NULL)
{
printf("create new_loopnode is failt\n");
return -1;
}
//2.把data数据填充到temp的数据域
temp->data = data;
//3.在头结点之后插入数据
//<1>先让新节点的指针域保存头结点的指针域
temp->next = head->next;
//<2>再让头节点的指针与保存新节点的首地址
head->next = temp;
return 0;
}
//4.输出链表所有数据
int print_linklist(loopnode *head)
{
//遍历所有节点，当指针域不为空的时候，
//每遍历一个节点，就输出一个数据。
loopnode *p = head->next;
while(p != head)
{
printf("%d ",p->data);
p = p->next;
}
putchar('\n');
return 0;
}
//5.创建不带头节点的带向循环链表。
//参数：带头结点的循环链表head
//思路：定义一个指针保存头结点的地址，
//然后遍历链表找到尾结点，然尾结点的指针域
//保存头节点下一个结点有效数据的地址，然后
//释放头结点.
loopnode *delete_head_linklist(loopnode *head)
{
loopnode *p = head;
//遍历完成之后，p->next保存了头节点的地址.
while(p->next != head)
{
p = p->next;
}
//尾结点保存头节点下一个节点的地址
//此时p->next为新的第一个结点的地址
p->next = head->next;
free(head);
head = NULL;
return p->next;
}
//6.输出新的删除了头结点的数据
int print_delete_head_data(loopnode *head)
{
loopnode *temp = head;
//输出第一个数据
printf("%d ",head->data);
//从第二个数据开始遍历
while(temp->next != head)
{
printf("%d ",temp->next->data);
temp = temp->next;
}
putchar('\n');
return 0;
}
void joseph_true(int n,int k,int m)
{
int i = 0;
loopnode *head = create_empty_linklist();
loopnode *temp = NULL;
//因为是链表，所以我们需要倒着插入数据
for(i = n;i > 0;i--)
{
insert_head_linklist(head,i);
}
print_linklist(head);
head = delete_head_linklist(head);
print_delete_head_data(head);
loopnode *p = head;
//找到第k个人，p需要移动k - 1次
//此时p指向了第k个人
//k = 3
for(i = 0;i < k - 1;i++)
{
p = p->next;
}
//循环m次，数到m的人出列，直到循环链表中的只剩
//一个节点（p->next == p）结束,
//循环内，数m次，指针p需要移动m - 1次,然后把移动后p的后一个结点
//的值给当前结点，然后把链表重新连接，在删除后一个结点
//上述删除之后，我们的p已经保存了下一个节点的地址了，不需要移动了
while(p != p->next)
{
//找到要删除的m的结点
for(i = 0;i < m - 1;i++)
{
p = p->next;
}
printf("%-4d",p->data);
//把m后一个节点的值赋值给m
p->data = p->next->data;
//temp保存后一个结点的地址
temp = p->next;
//把链表重新链接起来
p->next = p->next->next;
free(temp);
temp = NULL;
}
//循环结束，我们为空链表。只剩最后一个结点head,head中有数据。
printf("%-4d\n",p->data);
free(p);
p= NULL;
return ;
}
//注：此程序有bug，若是m = 1的话，我们的
//
//找到m前一个结点的地址
// for(i = 0;i < m - 2;i++)
// {
// p = p->next;
// }
void joseph(int n,int k,int m)
{
int i = 0;
loopnode *head = create_empty_linklist();
loopnode *temp = NULL;
//因为是链表，所以我们需要倒着插入数据
for(i = n;i > 0;i--)
{
insert_head_linklist(head,i);
}
print_linklist(head);
head = delete_head_linklist(head);
print_delete_head_data(head);
loopnode *p = head;
//找到第k个人，p需要移动k - 1次
//此时p指向了第k个人
//k = 3
for(i = 0;i < k - 1;i++)
{
p = p->next;
}
//循环m次，数到m的人出列，直到循环链表中的只剩
//一个节点（p->next == p）结束,
//循环内，数m次，指针p需要移动m - 1次，删除第m个人需要找到
//前一个人，指针p移动m - 2次，
//下一次从下一个人开始，p再移动一次
while(p != p->next)
{
//找到m前一个结点的地址
for(i = 0;i < m - 2;i++)
{
p = p->next;
}
temp = p->next;
printf("%-4d",temp->data);
p->next = p->next->next;
free(temp);
temp = NULL;
//下一次，从下一个人开始，p在移动一次
p = p->next;
}
//循环结束，我们为空链表。只剩最后一个结点head,head中有数据。
printf("%-4d\n",p->data);
free(p);
p= NULL;
return ;
}
int main(int argc, const char *argv[])
{
int n = 8,k = 3,m = 4;
joseph(n,k,m);
printf("==========================\n");
joseph_true(n,k,m);
return 0;
}