西北电专大二电院_数据结构上机报告记录_第一次上机报告

/*
  约瑟夫环。
  编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
  现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。
  报m的人出圈，从他在顺时针方向上的下一个人开始，重新从1开始报数，
  如此下去，直至所有的人全部出列为止。请编写程序求出圈的顺序。
  1,2,3,4,5,6,7。从第1个人开始报数，报到3的人出列，出列顺序为3,6,2,7,5,1,4
  
  考虑新建一个循环链表来实现这个环，问题一是建立循环链表和存数据，问题二是怎么样实现约瑟夫的求解
  解决约瑟夫，设一共n人，报数m的时候第m个出列，然后重新报数，同时用flag来标记出列的人数，显然当flag=n-1时完成
 */
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
}Lnode;//建立链表的存储结构

Lnode*Tail_Creat(int n);
void YuesefuHuan(Lnode *L,int n,int m,int a[]);//声明调用的两个函数，一个尾插法一个处理约瑟夫环

int main()
{
    int n,m;
    scanf("%d\t%d",&n,&m);//输入总人数n和报数m
    Lnode*tail=NULL;//声明一个尾指针指向空，并在下面用尾插法返回值赋值
    tail=Tail_Creat(n);
    int a[n];//新建一个输出数组
    YuesefuHuan(tail,n,m,a);
    for(int i=0;i<n;i++)
    {
        printf("%d\t",a[i]);
    }
    return 0;
}


Lnode*Tail_Creat(int n)//尾插法建立新循环链表，这里假定了链表必定不为空表
{
    Lnode *head,*new_elem,*tail;
    head=NULL,new_elem=NULL,tail=NULL;//建立头指针，存放数据的指针和尾指针且初始指向空
    
    int i;
    for(i=1;i<=n;i++)//遍历，从1开始到n，并把i依次存入到链表中
    {
        new_elem=(Lnode*)malloc(sizeof(Lnode));//开辟空间
        new_elem->data=i;
        if(head==NULL)//考虑到每个结点都存数据，这里是不带头结点的尾插法，head是头指针指向第一个元素。如果带头结点呢？
        {
            head=new_elem;//初始状态，头指针存入第一个元素
        }
        else
        {
            tail->next=new_elem;//如果不是初始状态，用尾插法，将尾指针的后继指向新元素
        }
        tail=new_elem;//无论是第一个还是后续，都将尾指针指向更新后最后一个元素
    }
    tail->next=head;//构建循环链表，将尾指针的后继指向头指针
    return tail;//返回尾指针，考虑到约瑟夫实现里面循环链表不是双向，返回tail相当于返回i-1位指针
    
}

void YuesefuHuan(Lnode *L,int n,int m,int a[])//传入的是指针
{
    int cnt=0,flag=0,i=0;//cnt计数用判断是否到m，flag计数出列人数，到n-1时只剩下最后一个，结束
    Lnode*s=L,*p=L->next;//初始L传入的是尾指针，s指向一个结点，p指向s的下一个结点,实际上要出列看的是p,初始cnt从0自增1对照的是p的序号1
    while(flag!=n-1)
    {
        cnt++;//计数器从0自增，序号和p相同；
        if(cnt!=m)//如果还没到要出列的位置，后移两个指针，注意先s=p避免丢失
        {
            s=p;
            p=p->next;
        }
        else if(cnt==m)//如果到了要出列的位置（画图看比较容易看出）
        {
            cnt=0;
            flag++;//重新开始计数，出列人数自增1
            a[i++]=p->data;//存数据到要输出的数组中
            s->next=p->next;
            free(p);
            p=s->next;//注意这里s还是在上一个位置，只是把p（每次遍历判断是否要出列的结点）移向出列结点的后一个结点，所以不是写s=p->next
            
        }
    }
    a[i]=p->data;//传入最后一个数据
    free(p);
    p=NULL;
}

  1 /*
  2   约瑟夫环  
  3   时间限制
  4   2 S 
  5   内存限制
  6   10000 Kb 
  7   问题描述 
  8   编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
  9   现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。
 10   报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，
 11   如此下去，直至所有的人全部出圈为止。 
 12   问题输入 
 13   输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。 
 14   问题输出 
 15   用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔 
 16   输入样例 
 17   7 20
 18   3 1 7 2 4 8 4
 19   输出样例 
 20   6 1 4 7 2 3 5 
 21   提示 
 22   使用不带头节点的循环链表 
 23   
 24   考虑新建一个循环链表来实现这个环，问题一是建立循环链表和存数据，问题二是怎么样实现约瑟夫的求解
 25   解决约瑟夫，设一共n人，怎么出列？报数m的时候第m个出列，然后重新报数，同时用flag来标记出列的人数，怎么结束？显然当flag=n-1时完成
 26   这个问题输出的还是编号，只是m值作为变量会发生变化，每个人随身带有一个m值需要建立数组额外存取（考虑到结构体的思想，也写在链表的结构体里！另写一个c代码）
 27  */
 28 #include<stdio.h>
 29 #include<stdlib.h>
 30 
 31 typedef struct node
 32 {
 33     int data;
 34     struct node *next;
 35 }Lnode;//建立链表的存储结构
 36 
 37 Lnode*Tail_Creat(int n);
 38 void YuesefuHuan(Lnode *L,int n,int m,int a[],int b[]);//声明调用的两个函数，一个尾插法一个处理约瑟夫环
 39 
 40 int main()
 41 {
 42     /*
 43       流程描述
 44       输入 总人数和报数的值m
 45       建立两个新数组，一个存m值，一个输出编号
 46       for循环输入m值到一个数组
 47       
 48       尾插法建立链表
 49       函数处理约瑟夫环问题
 50       
 51       for循环输出另一个数组（显然上一个函数已经把数据存到了存编号的数组中）
 52      */
 53     int n,m,m_data,i;
 54     scanf("%d\t%d",&n,&m);//输入总人数n和报数m
 55     int a[n];//新建一个输出数组
 56     int b[n];//新建一个存储数组存储每个人的m值
 57     
 58     for(i=0;i<n;i++)
 59     {
 60         scanf("%d",&m_data);
 61         b[i]=m_data;
 62     }
 63     
 64     Lnode*tail=NULL;//声明一个尾指针指向空，并在下面用尾插法返回值赋值
 65     tail=Tail_Creat(n);
 66     YuesefuHuan(tail,n,m,a,b);
 67     for(i=0;i<n;i++)
 68     {
 69         printf("%d\t",a[i]);
 70     }
 71     return 0;
 72 }
 73 
 74 
 75 Lnode*Tail_Creat(int n)//尾插法建立新循环链表，这里假定了链表必定不为空表，同时不带头结点
 76 {
 77     Lnode *head,*new_elem,*tail;
 78     head=NULL,new_elem=NULL,tail=NULL;//建立头指针，存放数据的指针和尾指针且初始指向空
 79     
 80     int i;
 81     for(i=1;i<=n;i++)//遍历，从1开始到n，并把编号i依次存入到链表中
 82     {
 83         new_elem=(Lnode*)malloc(sizeof(Lnode));//开辟空间
 84         new_elem->data=i;
 85         if(head==NULL)//考虑到每个结点都存数据，这里是不带头结点的尾插法，head是头指针指向第一个元素。如果带头结点呢？
 86         {
 87             head=new_elem;//初始状态，头指针存入第一个元素
 88         }
 89         else
 90         {
 91             tail->next=new_elem;//如果不是初始状态，用尾插法，将尾指针的后继指向新元素
 92         }
 93         tail=new_elem;//无论是第一个还是后续，都将尾指针指向更新后最后一个元素
 94     }
 95     tail->next=head;//构建循环链表，将尾指针的后继指向头指针
 96     return tail;//返回尾指针，考虑到约瑟夫实现里面循环链表不是双向，返回tail相当于返回i-1位指针
 97     
 98 }
 99 
100 void YuesefuHuan(Lnode *L,int n,int m,int a[],int b[])
101 {
102     int cnt=0,flag=0,i=0;//cnt计数用判断是否到m，flag计数出列人数，到n-1时只剩下最后一个，结束
103     Lnode*s=L,*p=L->next;//初始L传入的是尾指针，s指向一个结点，p指向s的下一个结点,实际上要出列看的是p,初始cnt从0自增1对照的是p的序号1
104     while(flag!=n-1)
105     {
106         cnt++;//计数器从0自增，序号和p相同；
107         if(cnt!=m)//如果还没到要出列的位置，后移两个指针，注意先s=p避免丢失
108         {
109             s=p;
110             p=p->next;
111         }
112         else if(cnt==m)//如果到了要出列的位置（画图看比较容易看出）
113         {
114             cnt=0;
115             flag++;//重新开始计数，出列人数自增1
116             m=b[p->data-1];//把b数组存的m值更新到函数里即可，注意到数组的位序要比表的位序少1
117             a[i++]=p->data;//存数据到要输出的数组中
118             s->next=p->next;//避免断开
119             free(p);
120             p=s->next;//注意这里s还是在上一个位置，只是把p（每次遍历判断是否要出列的结点）移向出列结点的后一个结点，所以不是写s=p->next
121         
122         }
123     }
124     a[i]=p->data;//传入最后一个数据（这种细节不要忽视）
125     free(p);
126     p=NULL;
127 }