各位大侠,帮我看看哪里错了。
1.**约瑟夫环问题。
[问题描述]
设编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人手持一密码(正整数)。开始任选一个正整数作为报数上限m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值。从他在顺时针方向的下一个人重新从1开始报数,如此下去,直到所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求]
利用单向循环链表和顺序存储两种结构实现。
[测试数据]
m=20;n=7;个人密码依次为:3,1,7,2,4,8,4(正确的出列顺序应为6,1,4,7,2,3,5)
[实现提示]
程序运行时先输入人数n和报数上限m。建议用数学取模方式确定下一出列人;
////////////////////////////////////////////////////////////
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
int xia;
struct node *next;
}lnode,*link;
/////////////////////////////////////////////////////////////////////
link linkwei() ////////////尾插法建立头结点
{
link l;
l=(lnode*)malloc(sizeof(lnode));
if(l==NULL) ////////////分配内存空间
{
printf("没有分配内存空间!\n");
exit(0);
}
return l;
}
///////////////////////////////////////////////////////////////////
link linkint(link l,int pe) //////////////为链表赋值
{
link p,r;
int pa,i;
l->next=NULL;
r=l;
printf("请为这些节点赋值(密码)\n");
for(i=0;i<pe;i++)
{
scanf("%d",&pa);
p=(lnode*)malloc(sizeof(lnode));
p->xia=i+1;
p->data=pa;
p->next=r->next;
r->next=p;
r=p;
}
p->next=l->next; ////////////////单循环链表
return l;
}
///////////////////////////////////////////////////////////////////
void linkcharge(link l,int max) //////////////////插入链表
{
link pre,p,t;
int i=1;
pre=l;
p=l->next;
while(p!=NULL)
{
if(i!=max)
{
pre=p;
p=p->next;
i++;
}
else
{
t=p->next;
printf("报数的人是%d\n",p->xia);
max=p->data;
pre->next=p->next;
free(p);
p=t;
i=1;
}
}
}
////////////////////////////////////////////////////////////////////
void main()
{
int pe,max;
link l;
printf("请输入人数,最大上限\n");
scanf("%d,%d",&pe,&max);
l=linkwei();
l=linkint(l,pe);
linkcharge(l,max);
}
/////////////////////////////////////////////////////////////////////
答案输出正确,可是执行完却会弹出个错误的标志,怎么回事?
[解决办法]
while(p!=NULL)
这个判断可能有点问题因为当最后一个节点被free掉之后p并没有被赋值为NULL,所以还将继续执行导致出错。
应该用while(p->next!=p)然后最后一个节点单独处理一下。