單向循環(huán)鏈表（約瑟夫環(huán)）

#include<stdio.h>

#include<stdlib.h>

#define N 10

typedef struct node{

   int  data;

   struct node * next;

}ElemSN;

ElemSN*Createlink(int a[],int n){

int i;

        ElemSN*h=NULL,*p,*t;

       for(i=0;i<N;i++){

    p=(ElemSN*)malloc(sizeof(ElemSN));

             p->data=a[i];

if(!h)

h=t=p;

else

p->next=h;

t=t->next=p;

     }

     return t;

}//創(chuàng)建單向循環(huán)鏈表

ElemSN*Fun(ElemSN*t,int s){

       int i;

       ElemSN*h2=NULL,*t1,*h; //t1是行鏈表的尾結點指針，h是建立新鏈表的結點（出約瑟夫環(huán)的結點），h2新鏈表的頭結點

       while(t-t->next){//截止條件是環(huán)中只剩下一個結點，循環(huán)結束直接出環(huán)

            for(i=0;i<s-1;i++)

    t=t->next; //每隔幾個結點出環(huán)S，指針t的下一個加點就是要出環(huán)的結點

    h=t->next;  //h表示要出環(huán)的結點

    t->next=h->next;//出環(huán)

    h->next=NULL;//指針域為空斷鏈，出環(huán)的結點和約瑟夫環(huán)沒有聯(lián)系

            if(!h2)//新鏈表為空時，頭結點h2，尾結點t1，在同一個結點上

          h2=t1=h;

    else//新鏈表頭結點不空，出環(huán)的結點h掛在新鏈表的尾結點上，尾結點t1后移，繼續(xù)標志鏈表的尾結點

                  t1=t1->next=h;

       }

        if(!h2)//環(huán)中只剩下一個結點，直接出環(huán)，判斷新鏈表為空，說明約瑟夫環(huán)中只有一個結點

h2=t;//環(huán)中的結點直接為新鏈表的頭結點

else{

       t1->next=t; //新鏈表頭結點不空，出環(huán)的結點直接掛到新鏈表的尾結點上，

       t->next=NULL;//指針域為空，否則新鏈表中有為結點的next是自己，在尾結點上出現(xiàn)一個環(huán)（循環(huán)）

}

   return h2;

}

void Printlink(ElemSN*h){

ElemSN*p;

for(p=h;p;p=p->next)

printf("%2d\n",p->data);

}

int main(void){

int a[N]={1,2,3,4,5,6,7,8,9,10};

int s;

ElemSN*head;

head=Createlink(a,9);

printf("請輸入s=");

scanf("%2d",&s);

        head=Fun(head,s);

Printlink(head);

}