学步园

  测试空间旗下大头针出品

   我们班的C语言刚刚学习到第七章，昨天107班的耿**（曾就读于浙江大学）同学素质相当好，自己写了一个约瑟夫环。不过问题挺多的。这个题目非常经典，记得以前001班的陈*（曾就读于清华大学）同学去华为面试的时候考过这道题目。所以跟大家分享一下。

什么是约瑟夫环呢？

约瑟夫环问题
[问题描述]
编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
[基本要求]
利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。
[测试数据]

n的初值为3，m=2 ,3个人的密码依次为3，1，2首先m=则正确的输出是什么？
要求：
输入数据：首先输入待处理人员数及他们的密码，然后输入m的初值，建立单循环链表。
输出形式：建立一个输出函数，将正确的出列序列输出

 

 下面是耿启富一开始所写的程序：主要问题还是有关内存方面的：1.内存越界问题。2.野指针问题

#include<stdio.h>
#include<stdlib.h>
typedef struct Node *PNode;

struct Node {
       int num;
       int key;
       PNode next;
};

 

typedef struct Node *Linklist;

bool InitList(Linklist *L)//建立一个空链表
{
     L=NULL;
       
}

bool MakeNode( PNode p,int e,int n)//分配由p指向的数据元素为e,编号为n,后继为空的结点，并返回TRUE,若分配失败，则返回FALSE;
{
     p=(PNode) malloc(sizeof(Node));
     if(!p) return false;
     p->key=e;
     p->num=n;
     p->next=NULL;
     return true;
}

void Append(Linklist *L, PNode s)//将s所指向的结点链接到链表尾部
{
     if(*L)
     {
           PNode p;
           p=*L;
           while(p->next!=*L) p=p->next;
           p->next=s;
           s->next=*L;
     }
     else 
     {
           *L=s;
           s->next=*L;
     }
}

void DeleteNode(Linklist *L, PNode p)//从链表中删除p所指向的结点,并打印该结点的编号
{
    PNode temp;
    temp=*L;
    //if(p!=*L)//这行代码没有意义故去掉
    //{
                  while(temp->next!=p) temp=temp->next;
                  temp->next=p->next;

//在删除结点的时候，整个程序都用*L指向头结点，如果你删除的是头结点，那必

//须重新指向一个结点使其为头结点。也就是加如下语句：

//if(p==*L&&p->next!=p)

//*L=temp->next;删除头结点后，应该再为其指定一个头接点。

//如果现在只有1个结点，怎么办？

//if(p->next==p)  

//     *L=NULL;//防止出现野指针。                                   
                  printf("%d/t",p->num);
                  free(p);
    //}
    //else
    //{
    //    printf("%d/t",p->num);
   //     *L=NULL;
   // }
}

void CreatJoseph(int n, Linklist *L)//建立一个长为n的Joseph环，n的上限为30
{
     if(n>30) { printf("overflow!!/n"); exit(0); }
     InitList(L);
     int i;
     for(i=1;i<=n;i++)
     {
                      int k;
                      printf("Please input the key:");
                      scanf("%d",&k);
                      PNode p;

//用MakeNode(p,k,i)申请内存，生成节点的时候犯了一个非常常见的错误，

//就是p的内存区域不是申请的内存区的问题，这里应该改为MakeNode

//(&p,k,i);

               MakeNode(p,k,i);//                     

               Append(L, p);
     }
}

void Joseph(Linklist *L, int m)
{
     int nm=m;
     PNode p,temp,head;
     temp=*L;
     while(*L!=NULL)
     {
                      p=temp;
                      int i=1;
                      while(i!=nm) { i++; p=p->next; }
                      nm=p->key;
                      temp=p->next;
                     DeleteNode(L,p);//有问题主要是内存越界的问题和野指

                                      //针问题
     }
}

int main()
{
    int n,m;
    printf("Please input the mumbe n and m:");
    scanf("%d%d",&n,&m);
   Linklist *L;//用到了2级指针,但主函数中1级指针较好，所以改为Linklist L;
    InitList(L);//InitList(&L);
    CreatJoseph(n, L);//CreatJoseph(n,&L);
    Joseph(L, m);//Joseph(&L,m);
    return 0;
}                      
修改后的程序请点击： 
华为笔试题目--约瑟夫环（Joseph）修改版