约瑟夫循环单链表 高手看看我的程序 望赐教
我的程序,但运行错误,麻烦帮我看下哪里有错,谢谢啦!! 题目是输入n和m,然后从1到n围成一个圈,并从1开始报数,到m时,退出一个数。下一个又从1开始,报到m时退出,以此类推。求最后留下的一个数是多少。
#include<stdio.h>
#include<stdlib.h>
struct sNode \建立结构体类型\
{
int data;
struct sNode *next;
};
void Initilist(struct sNode **HL) \初始化一个循环单链表\
{
*HL=NULL;
}
void InsertLastlist(struct sNode **HL,int x) \将1-n依次插入单链表最后\
{
struct sNode *newp;\创建一个新节点,用来存储要插入的数字\
newp=(struct sNode*)malloc(sizeof(struct sNode));
if(newp==NULL)\如果创建失败,退出运行\
{
printf("内存动态空间用完,退出!\n");
exit(1);
}
newp->data=x;\让新节点的数值域等于插入的数字\
if(*HL==NULL)\当单链表为空的情况\
{
*HL=newp;
newp->next=*HL;
}
else\单链表不为空的情况\
{
struct sNode *p=*HL;
while(p->next!=*HL)\查找到单链表的最后一个节点\
p=p->next;
p->next=newp;\把新节点插入最后\
newp=*HL;\令新节点指向第一个节点,构成循环\
}
}
void Deleteposlist(struct sNode **HL,int x)\删除节点\
{
int i=1;
struct sNode *cp=*HL;
struct sNode *ap=NULL;
struct sNode *hp=*HL;
if(cp==NULL||x<=0)
{
printf("单链表为空或x值不正确,退出运行!\n");
exit(1);
}
while(1)
{
if(i==x) break;\当i=要删除的节点,跳出\
else
{
i++;
ap=cp; \ap指向当前节点\
cp=cp->next; \cp指向下一个节点\
}
}
if(x==1) \当要删除的是第一个节点时\
{
*HL=(*HL)->next; \令头指针指向第二个节点\
while(hp->next!=*HL)
hp=hp->next;
hp->next=*HL; \另最后一个节点指向新的第一个新节点,即第二个节点\
}
else \当要删除的不是第一个结点\
{
ap->next=cp->next;
if(cp==*HL) \当cp循环一次后又到第一个节点,此时ap指向最后一个节点\
*HL=ap->next; \令头结点指向新的第一个节点\
free(cp);
}
}
int main()
{
int i,j,m,n;
struct sNode *L;
while(scanf("%d%d",&n,&m)!=EOF)
{
j=n-1;
Initilist(&L); \初始化循环单链表\
for(i=1;i<=n;i++)
InsertLastlist(&L,i); \将1-n依次插入链表最后\
i=1;
while(j) \按规则删除n-1个节点,留下所求的节点\
{
if(i%m==0)
{
Deleteposlist(&L,i);
j--;i=1;
}
else i++;
}
}
printf("%d\n",L->data); \输出最后剩余的一个节点\
return 0;
}
[ 本帖最后由 S030902508 于 2010-11-9 12:11 编辑 ]