b.cpp

线性表实验（约瑟夫问题） 数据结构课的实验作业

#include "iostream.h"
struct node
{
 int Num;
 node *next;
};

void CreatList(node *head, node *end, int n);
void DeleteNode(node *head, int s, int d);
PrintList(node *head);

void CreatList(node *head, node *end, int n)
{
 node *temp;
 for(int i=1; i<n; i++)
 {
  temp = new node;
  temp->Num = i+1;
  end->next = temp;
  temp->next =head;
  end = temp;
 }
 end = head->next;
}

void DeleteNode(node *head, int s, int d)
{
 node *temp, *deletenode, *startnode = head;
 while(1)
 {
  if(startnode->Num == s)
   break;
  startnode = startnode->next;
 }
 while(startnode->next != startnode)
 {
  cout<<"Head:";
  PrintList(head);
  temp = startnode;
  for(int i=1; i<d-1; i++)
   temp = temp->next;
  deletenode = temp->next;
  temp->next = deletenode->next;
  if(deletenode == head)
   head = deletenode->next;
  cout<<"Start point is node "<<startnode->Num<<" , delete node "<<deletenode->Num<<endl<<endl;

  delete deletenode;
  startnode = temp->next;
 }
 cout<<"Head:";
  PrintList(head);
 cout<<"Start point is node "<<startnode->Num<<" , delete node "<<startnode->Num<<endl<<endl;
 cout<<"List is empty!";
 delete startnode;
}

 PrintList(node *head)
{
 node *temp;
 if(head)
 {
  temp = head->next;
  cout<<head->Num;
  while(temp != head)
  {
   cout<<"->"<<temp->Num;
   temp = temp->next;
  }
  cout<<"->head"<<endl;
 }
}

int main(int argc, char* argv[])
{
 node *head, *end;
 int n, s, d;
 char flag = 'y';
 while(flag == 'y' || flag == 'Y')
 {
  cout<<"Input number of node: ";
  cin>>n;
  cout<<"Input the start point: ";
  cin>>s;
  cout<<"Input distance: ";
  cin>>d;
  head = new node;
  head->Num = 1;
  head->next = head;
  end = head;
  CreatList(head, end, n);
  cout<<"The original List is ";
  PrintList(head);
  cout<<endl;
  DeleteNode(head, s, d);
  cout<<"\n\nGo on?(y/n)";
  cin>>flag;
 }
 return 0; 
}