双向链表实现约瑟夫问题小BUG
自己测试了很多遍，但是一直不知道问题出在哪，想请教一下各位鱼油！！！#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *prior;
struct Node *next;
}DListNode,*DLinkList;
void Josephus(DLinkList head,int n,int m,int k)
{
DListNode *p,*q,*r,*s,*t;
int i;
p=head;
for(i=1;i<k;i++) /*从第k个人开始报数*/
{
p=p->next;
}
r=p;
s=p;
while(r->next!=r)
{
for(i=1;i<m;i++) /*数到m的人出列*/
{
q=r;
r=r->next;
t=s;
s=s->prior;
}
q->next=r->next; /*将p指向的结点删除，即报数为m的人出列*/
r->next->prior=q;
t->prior=s->prior;
s->prior->next=t;
if(r->data != s->data)
{
printf("%d-%d,",r->data,s->data);/*输出被删除的结点*/
if(q==s&&r==t)
{
if(q->next==r)
{
r=q->next->next;
s=t->prior->prior;
free(q);
free(t);
}
if(r==s)
{
r->next->prior=r;
r->prior->next=r;
}
}
else
{
if(r==t&&q!=s)
{
free(s);
}
else if(q==s&&r!=t)
{
free(r);
}
else if(q!=s&&r!=t)
{
free(r);
free(s);
}
r=q->next;
s=t->prior;
}
}
else
{
printf("%d,",r->data);
free(r);
//free(s);
r=q->next;
s=t->prior;
}
} /*p指向下一个结点，重新开始报数*/
printf("%d,\n",r->data);
free(r);
}
DLinkList CreateDCList(int n)
/*创建双向循环链表*/
{
DLinkList head=NULL;
DListNode *s,*q;
int i;
for(i=1;i<=n;i++)
{
s=(DListNode*)malloc(sizeof(DListNode));
s->data=i;
s->next=NULL;
/*将新生成的结点插入到双向循环链表*/
if(head==NULL)
{
head=s;
s->prior=head;
s->next=head;
}
else
{
s->next=q->next;
q->next=s;
s->prior=q;
head->prior=s;
}
q=s; /*q始终指向链表得最后一个结点*/
}
return head;
}
int main()
{
DLinkList h;
int n,k,m;
scanf("%d,%d,%d", &n, &k, &m);
if(n<1||m<1||k<1)
{
printf("n,m,k must bigger than 0.\n");
}
else if(k>n)
{
printf("k should not bigger than n.\n");
}
else
{
h=CreateDCList(n);
Josephus(h,n,m,k);
}
return 0;
} 看不懂
页:
[1]