C++ in circular linked lists and Joseph rings

Circular linked lists and Joseph rings

Implementation of circular linked lists

A single linked list has only backward nodes. When the tail list of a single linked list does not point to NULL, but to the head node, a ring is formed and it becomes a single cycle linked list, referred to as a cycle linked list. When it is an empty table, the backward node only thinks of itself, which is the main difference between it and a single linked list. Judge node- > Is next equal to head?

The code implementation is divided into four parts:

Initialize the insert delete Positioning for

Code implementation:

void ListInit(Node *pNode){
  int item;
  Node *temp,*target;
  cout<<" The input 0 Complete initialization "<<endl;
  
  while(1){
    cin>>item;
    if(!item)
      return ;
    if(!(pNode)){ // When the watch is empty, head==NULL 
      pNode = new Node ;
      if(!(pNode))
        exit(0);// Unsuccessful application  
      pNode->data = item;
      pNode->next = pNode;
    }
    else{
      //
      for(target = pNode;target->next!=pNode;target = target->next)
        ;
      temp = new Node;
      if(!(temp))
        exit(0);
      temp->data = item;
      temp->next = pNode;
      target->next = temp;
    }
  }
} 
void ListInsert(Node *pNode,int i){ // The parameters are the first node and the insertion position  
  Node *temp;
  Node *target;
  int item;
  cout<<" Enter the value you want to insert :"<<endl;
  cin>>item;
  if(i==1){
    temp = new Node;
    if(!temp)
      exit(0);
    temp->data = item;
    for(target=pNode;target->next != pNode;target = target->next)
    ;
    temp->next = pNode;
    target->next = temp;
    pNode = temp;
  }
  else{
    target = pNode;
    for (int j=1;j<i-1;++j)
      target = target->next;
    temp = new Node;
    if(!temp)
      exit(0);
    temp->data = item;
    temp->next = target->next;
    target->next = temp;
  }
}
void ListDelete(Node *pNode,int i){
  Node *target,*temp;
  if(i==1){
    for(target=pNode;target->next!=pNode;target=target->next)
    ;
    temp = pNode;// save 1 Next is the first node to delete  ,1 It's easy to release  
    pNode = pNode->next;
    target->next = pNode;
    delete temp; 
  }
  else{
    target = pNode;
    for(int j=1;j<i-1;++j)
      target = target->next;
    temp = target->next;// To release the node
    target->next = target->next->next;
    delete temp; 
  }
}
int ListSearch(Node *pNode,int elem){ // Query and return the location of the node  
  Node *target;
  int i=1;
  for(target = pNode;target->data!=elem && target->next!= pNode;++i)
    target = target->next;
  if(target->next == pNode && target->data!=elem)
    return 0;
  else return i;
}

Joseph problem

Joseph ring (Joseph problem) is a mathematical application problem: known n individuals (with Numbers 1,2,3... Sit around a round table. Count from the person numbered k, and the person who counts to m is listed; His next person counts again from 1, and the person who counts to m goes out again; Repeat this pattern until everyone around the round table is out of line. This kind of problem can be solved with the idea of circular lists.

Note: when writing code, note the special case when reporting m = 1

#include<iostream>
#include<cstdio>
using namespace std;
typedef struct Node{
  int data;
  Node *next;
};

Node *Create(int n){
  Node *p = NULL, *head;
  head = new Node;
  if (!head)
    exit(0);
  p = head; // p Is the current pointer  
  int item=1;
  if(n){
    int i=1;
    Node *temp;
    while(i<=n){
      temp = new Node;
      if(!temp)
        exit(0);
      temp->data = i++;
      p->next = temp;
      p = temp; 
    }
    p->next = head->next;
  }
  delete head;
  return p->next;
}
void Joseph(int n,int m){
  //n Is the total number of people, m One to the first m A withdrawal 
  m = n%m;
  
  Node *start = Create(n);
  
  if(m){// If you take the remainder m!=0 ,  m!=1 
    while(start->next!=start){
      Node *temp = new Node;
      if(!temp)
        exit(0);
      for(int i=0;i<m-1;i++) // m = 3%2 = 1
        start = start->next;
      temp = start->next;
      start->next = start->next->next;
      start = start->next;
      cout<<temp->data<<" ";
      delete temp;
    }
  }
  else{
    for(int i=0;i<n-1;i++){
      Node *temp = new Node;
      if(!temp)
        exit(0);  
      cout<<start->data<<" ";
      temp = start;
      start = start->next;
      delete temp;
    }
  }
  cout<<endl;
  cout<<"The last person is:"<<start->data<<endl;
}
int main(){
  Joseph(3,1);
  Joseph(3,2);
  return 0;
}

Thank you for reading, I hope to help you, thank you for your support of this site!