经典约瑟夫环问题,编的程序不知错在哪?请高手相助
简述:编号为1—n的n个人按顺时针围坐一圈。每人有一个密码(正整数)。开始选一个报数上限值m,从第一个人开始顺时针顺序报数,报到m停止。报m的人出列,他的密码作为新的m值,从他在顺时针方向上的下一个人开始从1报数。如此下去,直至所有人都出列。例如:m=20,n=7,密码依次为3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。用单向循环链表模拟此过程,输出出列顺序。
感觉应该是deleandpri(Linklist L,Node *q,int *n)这个函数或主函数中while循环条件的问题,看不出错在哪。谢谢各位了!
- C/C++ code
#include<stdio.h>#include<malloc.h>typedef struct Node//节点定义,包含序号num及密码code{ int num,code; struct Node *next;}Node,*Linklist;Linklist initCycList()//初始化单循环链表(带头结点){ Linklist L;//L是头指针,指向头结点 L=(Linklist)malloc(sizeof(Node)); L->next=L;//L->next指向第一个成员节点 return L;}void CreatFromTail(Linklist L)//尾插构造链表{ Node *r,*s;//r是尾指针,s指向新申请的节点 int flag=1,i=1; r=L; while(flag) { char c=getchar(); if(c!='\n') { s=(Node *)malloc(sizeof(Node)); s->code=c;//c值赋给code s->num=i;//序号为i r->next=s; r=s;//尾指针指向s i++; } else { flag=0; r->next=L->next;//最后一个节点指向第一个节点,不是头节点 } }}void deleandpri(Linklist L,Node *q,int *n)//出列并打印序号函数{ int j=1; Node *t; while((++j)<(*n))//将q指向要出列的元素的前驱 q=q->next; if(q==L->next)//表示链表只剩下一个节点 { t=q; q=NULL; } else { t=q->next;//将q的后继保存到t中,t即为出列元素 q->next=t->next;//把q的后继赋为t的后继 } q=q->next;//q指向t的下一个节点 printf("%d ",t->num);//打印出列序号 *n=t->code;//将出列者的密码作为下次处理的上限 free(t);//释放出列元素}void main(){ Linklist L0; L0=initCycList(); printf("请按顺序输入各成员的密码:\n"); CreatFromTail(L0); int m; printf("请输入第一个m的值: \n"); scanf("%d",&m); Node *p; p=L0->next;//p指向第一个成员元素 while(p!=NULL)//这个条件可能有问题 deleandpri(L0,p,&m); printf("\n");}
[解决办法]
传指针不是万能的。。。
deleandpri(L0,p,&m); 这里你只传了p的值进去,p是指针,但是你只能修改*p的值,任何对p的赋值是带不回来的
你要修改p本身的值,必须用p的指针或者引用,涉及到二级指针的概念