约瑟夫环--C语言

分手后的思念是犯贱 2022-04-02 08:21 184阅读 0赞

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈。每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，令其出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新报数，如此下去，直到所有人全部出列为止。  
  试设计一个程序求出出列顺序。  
  测试数据：m的初值为20；n=7,7个人的密码依次为：3，1，7，2，4，8，4（对应于节点的密码），首先m值为20，则正确的出列顺序应为6，1，4，7，2，3，5（对应于节点的编号）  
在设计程序时要特别注意第一个插入的节点和最后一个删除的节点的处理；还有就是密码为1的节点出列后的下一个节点的处理（因为密码为1的节点出列后下一个出列的节点即为该节点出列之前的下一个节点）。

代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct JoseCycleNode
    {
        
        int pwd;//密码
        int num;//节点编号
        struct JoseCycleNode *next;//指向链表下一个节点的指针
    }JoseCycleNode;//链表结构体
    
    //创建约瑟夫环
    JoseCycleNode *createLinkList(int num)
    {
        
        int i = 0;
        JoseCycleNode *p = NULL;
        JoseCycleNode *last = NULL;//指向链表中最后插入的节点的指针
        while(i < num)
        {
        
            p = (JoseCycleNode *)malloc(sizeof(JoseCycleNode));
            printf("Please input %ds node's password!\n",i + 1);
            scanf("%d",&p->pwd);
            p->num = i + 1;
            if(0 == i)
            {
        
                p->next = p;//i = 0代表是第一个插入的节点，循环链表的第一个节点的next指针指向节点本身
            }
            else
            {
        
                p->next = last->next;
                last->next = p;
            }
            last = p;
            i ++;
        }
        last = last->next;//将指针指向第一个插入的节点
        return last;
    }
    
    //按照删除节点的顺序输出节点编号
    void putNum(JoseCycleNode *List,int pwd)
    {
        
        int i = 0;
        JoseCycleNode *p = List;
        while(List->next != List)
        {
        
            for(i = 1;i < pwd - 1;i++)
            {
        
                p = p->next;
            }
            List = p;
            p = p->next;
            pwd = p->pwd;
            List->next = p->next;
            printf("%d ",p->num);
            free(p);
            if(pwd == 1)
            {
        
                p = List;//当密码为1时，只需要删除List节点的下一个节点即可
            }
            else
            {
        
                p = List->next;//因为计数是从被删除节点的下一个节点开始
            }
        }
        printf("%d\n",p->num);//输出最后一个节点的节点编号
        free(p);//删除最后一个节点
    }
    
    int main()
    {
        
        JoseCycleNode *List = NULL;
        int num = 0;//链表节点个数
        int pwd = 0;
        printf("Please input node number:");
        scanf("%d",&num);
        List = createLinkList(num);
        printf("Please input first limit cycle num!\n");
        scanf("%d",&pwd);
        putNum(List,pwd);
        return 0;
    }

这个是当时上大学时没有实现的代码，好像当时没有处理好只有一个节点的情况。今天突然想到了就写了一下，用的时间不算很少，但也还好～坚持下去吧～自己会越来越强大的！