C语言数据结构-用链表解决约瑟夫环问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言数据结构-用链表解决约瑟夫环问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前记

只是普通的大学生一枚，不会很牛的技巧和算法，只是在做数据结构作业中的一点感悟和思考。也不知道自己写得对不对，有什么意见和建议都可以直接指出来哦，我虚心接受（低头鞠躬.jpg）......

题目

试用线性表的链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序为48521376。

思路

首先刚开始的次序为1，2，3，...，7，8。从第一个人开始遍历，数到m，也就是第m个人就出去，先打印出列人的序号，再把这个结点从表中删除，继续遍历，继续找到下一个出列的人打印序号。如果用单链表解决的话，就出现了一个问题，遍历到尾结点时，无法继续报数了。所以此时需要用到循环单链表，将尾结点和头部连接起来。这样就能继续进行遍历。重复打印序号、删除结点操作，直到只剩下最后一个人。

函数代码

创建结点的结构体

typedef int ElemType;
typedef struct LNode  
{
    ElemType data;
    struct LNode *next;    
} LinkNode;

创建循环单链表

void CreateList(LinkNode *&L,int n)  //创建循环单链表 
{
    LinkNode *s,*r;
    L=(LinkNode *)malloc(sizeof(LinkNode));  
    L->next=NULL;
    r=L;                
    for (int i=1;i<n;i++)  //这里从1开始循环是因为是从头结点的下一个结点开始赋值
    {    
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=i;
        r->next=s;            
        r=s;
    }
    r->next=L;     //尾结点连接到头结点   
    L->data=n;   //头结点赋值为最后一个数k
}

初始化单链表

void InitList(LinkNode *&L)    //初始化 
{
    L=(LinkNode *)malloc(sizeof(LinkNode)); 
    L->next=NULL;
}

打印链表

void DispList(LinkNode *L)   //打印 
{
    LinkNode *p=L->next;
    while ( p != L)  
    //因为是循环单链表，所以一直到指针移到头结点才结束循环
    {    
        printf("%d ",p->data);
        p=p->next;
    }
    printf("%d ",p->data);  //因为头结点存放的是最后一个值，所以单独打印出来
    printf("\n");
}

基本的一些函数就写完了，接下来开写重头戏——约瑟夫环。我习惯写在主函数里了......

主函数

int main()
{
    LinkNode *L,*p,*r;
    InitList(L);
    int num;           //圆桌上的总人数
    int outnum;        //喊到就要出列的数字
    printf("请输入具体坐在圆桌上的人数："); 
    scanf("%d",&num);
    printf("请输入代表出列的数字：");
    scanf("%d",&outnum);
    CreateList(L,num);   //创建初始的次序链表
    printf("初始的人员次序为：");
    DispList(L);
    printf("出列的新人员次序为："); 
    p = L->next;    //将指针指向头结点的下一个
    while (p->next != p)  
    //循环条件，因为最后剩下一个人的话，指针下一个指向的还是自身
    //所以当p->next = p时，循环结束。此时剩下最后一人。
    {
        for (int i = 1; i < outnum; i++)   //从第一个人开始依次报数、出列
        {
            r = p;       //r指针用来记录具体删除某结点后遍历的位置，为删除做准备
            p = p->next; 
        }
        //当循环结束时也就意味着找到了出列的人，此时p指向该出列序号，r指向前一个人
        printf("%d ", p->data);   //打印出列人的序号
        r->next = p->next;   
        p = p->next;    //删除p指向结点
    }
    printf("%d ", p->data);   //打印最后一人的序号
}

完整代码

#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
typedef struct LNode  
{
    ElemType data;
    struct LNode *next;    
} LinkNode;                    

void CreateList(LinkNode *&L,int n) 
{
    LinkNode *s,*r;
    L=(LinkNode *)malloc(sizeof(LinkNode));  
    L->next=NULL;
    r=L;                
    for (int i=1;i<n;i++)
    {    
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=i;
        r->next=s;            
        r=s;
    }
    r->next=L;    
    L->data = n;
}

void InitList(LinkNode *&L)   
{
    L=(LinkNode *)malloc(sizeof(LinkNode)); 
    L->next=NULL;
}

void DispList(LinkNode *L)    
{
    LinkNode *p=L->next;
    while ( p != L)
    {    printf("%d ",p->data);
        p=p->next;
    }
    printf("%d ",p->data);
    printf("\n");
}

int main()
{
    LinkNode *L,*p,*r;
    InitList(L);
    int num;
    int outnum;
    printf("请输入具体坐在圆桌上的人数："); 
    scanf("%d",&num);
    printf("请输入代表出列的数字：");
    scanf("%d",&outnum);
    CreateList(L,num);
    printf("初始的人员次序为：");
    DispList(L);
    printf("出列的新人员次序为："); 
    p = L->next;
    while (p->next != p)
    {
        for (int i = 1; i < outnum; i++) 
        {
            r = p;
            p = p->next;
        }
        printf("%d ", p->data); 
        r->next = p->next;
        p = p->next;
    }
    printf("%d ", p->data);
}

你们看，我把注释都删了，多方便复制啊！！