关于约瑟夫环的实现

约瑟夫环是数据结构中的比较经典的环式结构，只的是尾节点与头节点相连接，也就是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;
}