#include<stdio.h>
#include<stdlib.h>
typedef struct jnode /*typedef是对已有的类型重新定义一个新的名字*/
{
int num;
struct jnode *next;
} *linklist;
linklist creat_linklist(int n); /*头插法建立循环单链表 无头结点*/
linklist find_linklist(linklist p,int xk); /*寻找开始报数的结点*/
linklist delete_linklist(linklist p,linklist head); /*删除某个节点的后继 注意：删除某个结点必须
知道前一个结点,保存要删除的结点，执行free()释放空间 */
void main()
{
linklist head,p,xp;
int n,i,k,m;
printf("输入结点总数");
scanf("%d",&n);
printf("开始报数的位置:");
scanf("%d",&k);
printf("每次报数的最大值:");
scanf("%d",&m);
head=creat_linklist(n);
xp=head;
printf("输出所有的节点数");
for(i=1;i<=n;i++)
{ /*输出创建链表里的所有的结点*/
printf("%-6d",xp->num);
xp=xp->next;
}
printf("/n");
p=find_linklist(head,k);
printf("输出开始报数的结点");
printf("%d/n",p->num);
printf("按照约瑟夫问题，以此出列的序号是：");
for(i=0;i<n;i++) /*开始执行约瑟夫问题*/
{
p=find_linklist(p,m-1); /*找出要删除结点的前一个结点*/
if(p->next==head)
head=head->next;
p=delete_linklist(p,head);
}
printf("/n");
}
linklist creat_linklist(int n) /*头插法建立循环单链表 无头结点*/
{
linklist head,s;
int i;
head=(linklist)malloc(sizeof(struct jnode));
if(!head)
exit(1);
head->num=1;
head->next=head;
for(i=n;i>1;i--)
{
s=(linklist)malloc(sizeof(struct jnode));
if(!s)
exit(1);
s->num=i;
s->next=head->next;
head->next=s;
}
return head;
}
linklist find_linklist(linklist p,int xk) /*寻找开始报数的结点*/
{
int i;
for(i=1;i<xk;i++)
p=p->next;
return p;
}
linklist delete_linklist(linklist p,linklist head)
{
linklist q;
if(p!=p->next)
{
q=p->next; /*保留要删除的结点*/
p->next=p->next->next;
printf("]",q->num);
free(q); /*释放已删除结点的空间*/
return p->next;
}
else
{
printf("]",p->num);
free(head);
return head;
}
}
