关于循环链表解决约瑟夫环

Question

大家帮忙看一下，为什么我这个只要选第一个死就会出错误，选别的死就没事

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct _node{
 int data;
 struct _node *next;
}Node;
void tailcreate(Node *L,int n)
{
 Node *p,*r;
 r=L;
 for(int i=1;i<=n;i++)
 {
  p=(Node *)malloc(sizeof(Node));
  p->data=i;
  
  r->next=p;
  r=p;
 }
 r->next=L->next;
 } 
 Node * Delete(Node *L,int num)
 {
  Node *p,*q;
 p=L;
  for(int i=1;;i++)
  {
   
   q=p;
   p=p->next;
   if(i==num)
   {
   if(p==L->next)  
    L->next=p->next;
    q->next=p->next;
    delete(p);
    break;
   }
   
  }
  return q;
}
void print(Node *head)
{
 
 Node *p;
 p=head;
    do
    {
     
     cout<<p->data<<' ';
     p=p->next;
    }while(p->next!=head->next);
}

  int main()
  {
   Node *head,*p;
   int n,num,m;
   cout<<"一共有几个人：";
   cin>>n; 
   m=n;
   head=(Node *)malloc(sizeof(Node));
   tailcreate(head,n);
   cout<<"第几个人死：";
   cin>>num;
   
  while(m--,m!=0)
  {
   p=Delete(head,num);head=p;
   print(head);
   cout<<endl;
   
   
    }  
    cout<<"存活编号";
    print(head);
    
     } 
  
 

Answer 1

主要是你这个是有头结点的循环链表，当第一个节点删除时，你没有将最后一个节点的next指向第一个节点，导致print时你的while条件成立不了

 
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct _node{
    int data;
    struct _node *next;
}Node;
void tailcreate(Node *L,int n)
{
    Node *p,*r;
    r=L;
    for(int i=1;i<=n;i++)
    {
        p=(Node *)malloc(sizeof(Node));
        p->data=i;

        r->next=p;
        r=p;
    }
    r->next=L->next;
} 
Node * Delete(Node *L,int num)
{
    Node *p,*q;
    q =L;
    p =L->next;
    if(num==1)
    {
        do
        {
            q=q->next;
        }while(q->next!=L->next);
        q->next = p->next;
        q = p->next;
        delete(p);
    }
    else
    {
        for(int i=1;;i++)
        {

            q=p;
            p=p->next;
            if(i==num)
            {
                if(p==L->next)  
                    L->next=p->next;
                q->next=p->next;
                delete(p);
                break;
            }
        }
    }
    return q;
}
void print(Node *head)
{

    Node *p;
    p=head;
    do
    {

        cout<<p->data<<' ';
        p=p->next;
    }while(p->next!=head->next);
}

int main()
{
    Node *head,*p;
    int n,num,m;
    cout<<"一共有几个人：";
    cin>>n; 
    m=n;
    head=(Node *)malloc(sizeof(Node));
    tailcreate(head,n);
    cout<<"第几个人死：";
    cin>>num;

    while(m--,m!=0)
    {
        p=Delete(head,num);head=p;
        print(head);
        cout<<endl;


    }  
    cout<<"存活编号";
    print(head);
}