C++ 中循环链表和约瑟夫环

概述循环链表和约瑟夫环循环链表的实现单链表只有向后结点，当单链表的尾链表不指向NULL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。当它是空表，向后结点就只想了自己，这也是它与单链表的主

循环链表和约瑟夫环

循环链表的实现

单链表只有向后结点，当单链表的尾链表不指向NulL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。当它是空表，向后结点就只想了自己，这也是它与单链表的主要差异，判断node->next是否等于head。

代码实现分为四部分：

初始化 插入 删除 定位寻找

代码实现：

voID listinit(Node *pNode){  int item;  Node *temp,*target;  cout<<"输入0完成初始化"<<endl;    while(1){    cin>>item;    if(!item)      return ;    if(!(pNode)){ //当空表的时候，head==NulL       pNode = new Node ;      if(!(pNode))        exit(0);//未成功申请       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){ //参数是首节点和插入位置   Node *temp;  Node *target;  int item;  cout<<"输入您要插入的值:"<<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;//保存一下要删除的首节点,一会便于释放     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;//要释放的node    target->next = target->next->next;    delete temp;   }}int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置   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;}

约瑟夫问题

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。这类问题用循环列表的思想刚好能解决。

注意：编写代码的时候，注意报数为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是当前指针   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为总人数，m为数到第m个的退出  m = n%m;    Node *start = Create(n);    if(m){//如果取余数后的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;}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

总结

以上是内存溢出为你收集整理的C++ 中循环链表和约瑟夫环全部内容，希望文章能够帮你解决C++ 中循环链表和约瑟夫环所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。