数据结构复习------------循环单链表实现约瑟夫问题

用链表求约瑟夫问题：

前面小编试过用顺序表来实现约瑟夫问题，用的是连用起始结点加报数然后球余出列，这次利用循环单链表来实现。可能思考不周，但欢迎各路大神赐教！

算法思路 ：

   由于约瑟夫问题是n个人围坐一圈，所以采用循环链表实现，又由于报数可能循环到开始，所以采用不带头结点的循环链表结构。

算法步骤：

     （1）在不带头结点的循环链表中查找第s个结点，用p作为第s个结点的指针。
     （2）从p所指的结点开始计数查找第m个结点，pre指向p的前驱。
     （3）输出该结点的函数值。
     （4）删除该结点，同时将该结点的下一结点的指针作为当前指针即p指针，重复到步骤（2），直至链表中所有结点被删除为止。

算法如下所示：

int Joesphus_LinkList(LinkList josephus_Link,int s,int m)
{
   /*求约瑟夫算法的出列元素的顺序，入口参数：已经存放数据的链表头指针，起始为止s，从1报到数m，入口参数：1表示成功，0表示表中无元素。*/
    LinkList p,pre;       /*p指向前结点，pre指向其前驱结点*/
    int count;
    if(!josephus_Link){
        printf("表中无元素！\n");
        return 0;
    }
    p=L;
    for(count=1;count<s;count++){   /*查找第s个结点，用p作为第s个结点的指针*/
        p=p->next;
    }
    printf("输出约瑟夫序列：");
    while(p!=p->next)               /*输出n-1个结点*/
    {
        pre=p->next;
    while(pre->next!=p)             /*pre指针初始化，pre是p的前驱指针*/
        pre=pre->next;
    for(count=1;count<m;count++){

        pre=p;
        p=p->next;
    }
        printf("%d\t",p->data);
        pre->next=p->next;
        free(p);
        p=pre->next;
    }                               /*for*/
    printf("%d\t",p->data);
    free(p);
    return 1;
}
该算法的时间复杂度：O(nxm)。

程序完整实现：

#include <cstdio>
#include <cstdlib>
#define MAXSIZE 100
typedef struct node{
    int data;
    struct node *next;
}Lnode,*LinkList;
LinkList CreateLinkList(int n,int a[MAXSIZE]){
      LinkList S,H,q,r;
      int i;
        H=(LinkList*)malloc(sizeof(Lnode));
        if(H==NULL)
        {
            printf("申请内存失败！\n");
            return 0;
        }
    H->data=a[0];
    q=H;
    for(i=1;i<n;i++){
        S=(LinkList*)malloc(sizeof(Lnode));
        if(S==NULL)
        {
            printf("申请内存失败！\n");
            return 0;
        }
        S->data=a[i];     /*尾插法实现单链表的链接*/
        H->next=S;
        H=S;
    }
     H->next=q;      /*这里用q保存初始H的结点*,然后用H->next指向q完成首尾的链接*/
     r=H->next;      /*这里我试过输出q，但初始值都指向每次输入的最后的结点，所以用r指代H头结点*/
     return r;
}
int Joesphus_LinkList(LinkList L,int s,int m)
{
    LinkList p,pre;
    int count;
    if(!L){
        printf("表中无元素！\n");
        return 0;
    }
    p=L;
    for(count=1;count<s;count++){
        p=p->next;
    }
    printf("输出约瑟夫序列：");
    while(p!=p->next)
    {
        pre=p->next;
    while(pre->next!=p)
        pre=pre->next;
    for(count=1;count<m;count++){

        pre=p;
        p=p->next;
    }
        printf("%d\t",p->data);
        pre->next=p->next;
        free(p);
        p=pre->next;
    }
    printf("%d\t",p->data);
    free(p);
    return 1;
}
void main(){
    LinkList L,S,q;
    int i,n,s,m;
    int a[MAXSIZE];
    printf("请输入约瑟夫问题中的人数 n= ");
    scanf("%d",&n);
    putchar('\n');
    printf("输入约瑟夫问题中的编号： ");
    for(i=0;i<n;i++){

        scanf("%d",&a[i]);
    }
    putchar('\n');
    printf("输入起始编号 s= ");
    scanf("%d",&s);
    putchar('\n');
    printf("计数值 m= ");
    scanf("%d",&m);
    putchar('\n');
    /*个人感觉以函数的实现更加使main函数简洁明了，所以用这个CreateLinkList(n,&a)函数实现。其实代码都一样*/
    /* 
    H=(LinkList*)malloc(sizeo
    putchar('\n');f(Lnode));
    H->data=a[0];
    q=H;
    for(i=1;i<n;i++){
        S=(LinkList*)malloc(sizeof(Lnode));
        S->data=a[i];
        H->next=S;
        H=S;
    }
    H->next=q;
    */
    L=CreateLinkList(n,&a);
    Joesphus_LinkList(L,s,m);
    putchar('\n');
}

实验结果截图：