关于约瑟夫环的实现

时间：2006-11-19 来源：1jjk

约瑟夫环是数据结构中的比较经典的环式结构，只的是尾节点与头节点相连接，也就是tail->next=head的意思。这样就组成了一个环

/*
name: JOSEPHUS.c
written by: 1jjk
*/
#include<stdio.h>
#include<stdlib.h>
/*Include files*/
typedef struct node
{
int data;
struct node *next;
}*pointer,*klist;
/*define a struct and new type.*/
/*creat new list,as long as you want*/
struct node *insert_list()
{
klist q,d,list;
int x;
d=malloc(sizeof(struct node));
list=d;
scanf("%d", &x);
while(x!=0)
{
  q=malloc(sizeof(struct node));
  list->data=x;
  list->next=q;
  list=q;
  scanf("%d", &x);
}
list->next=d;
return d;
}
/*find the node of the list*/
struct node *search_list(klist list,int i)
{
klist p=list;
int j=0;
while((p->next!=NULL)&&(j<i))
{
  p=p->next;
  j++;
}
if(i==j)
{
  return p;
}
else
{
  return NULL;
}
}

/*delete the node as you want.*/
struct node *delete_list(klist list,int i)
{
klist p,q;
int j=0;
p=list;
if((search_list(list,i))==NULL)
{
  printf("delete error\n");
  return 0;
}
while((p->next!=NULL)&&(j<i))
{
  p=p->next;
  j++;
}
if(j==i)
{
  q=p->next;
  printf("%d\n",q->data);
  p->next=q->next;
  free(q);
  return p;
}
else
{
  return p;
}
}
int main()
{
klist p;
int i;
p=insert_list();
printf("please input which node do you want to delete:\n");
scanf("%d",&i);
printf("the output is:\n");
while(p->next!=p)
p=delete_list(p,i);
printf("%d\n",p->data);
free(p);
return 1;
}