数据结构课程设计-（一）线性结构（约瑟夫环）

迷南。 2022-12-27 07:45 143阅读 0赞

joseph环  
任务：编号是1,2,…,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。  
要求：利用单向循环链表存储结构模1拟此过程，按照出列的顺序输出各个人的编号。  
测试数据：m的初值为20，n=7 ，7个人的密码依次为3，1，7，2，4，7，4，首先m=6，则正确的输出是什么？  
要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。  
输出形式：建立一个输出函数，将正确的输出序列  
数据结构：  
typedef struct Node  
\{  
int data;  
int password;  
struct Node \*next;  
\}Node, \*LinkList;  
基本操作：初始化单链表；给每个人赋密码；确定需要处理的人数；确定开始的上限值；得到正确的顺序；输出结果。

利用单向循环链表实现。

#include <bits/stdc++.h>
    using namespace std;
    typedef struct node
    {
        
        int num;//序号
        int code;//密码
        struct node *next;
    }lnode;
    lnode *buildring(int m,int n)//建立单向循环链表
    {
        
        int t=1,flag=0;
        lnode *head=new node,*pre=new node;//都要申请空间
        pre=head;
        while(t<=n)
        {
        
            lnode *q;
            q=new node;
            scanf("%d",&q->code);
            q->num=t;
            t++;
            pre->next=q;
            q->next=NULL;
            pre=q;
            if(t==(n+1))
            {
        
                q->next=head->next;//最后一个节点指向第一个节点。（循环）
            }
        }
        return head;
    }
    void print(lnode *head)//只是查看建立完的样子
    {
        
        int num=10;
        lnode *p=head->next;
        while(num--)
        {
        
            printf("num:%d code:%d\n",p->num,p->code);
            p=p->next;
        }
    }
    void testing(lnode *head,int m,int n)
    {
        
        int out=0,Count=1,stop=m;
        lnode *p=new node,*pre=new node;
        p=head->next;
        pre=head;
        while(1)
        {
        
            if(out==(n-1))break;//只剩一个时候结束
            while(Count<stop)
            {
        
                pre=pre->next;
                p=p->next;
                Count++;
            }
            printf("%d ",p->num);
            out++;
            stop=p->code;
            lnode *del=p;
            p=p->next;
            pre->next=p;//删除数到的节点
            free(del);
            Count=1;
        }
    }
    int main()
    {
        
        int m,n;
        scanf("%d%d",&m,&n);
        lnode *head=buildring(m,n);
        testing(head,m,n);
        return 0;
    }

仅用于记录位置的节点也要申请空间，否则也会出错。