程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++ 中循環鏈表和約瑟夫環

C++ 中循環鏈表和約瑟夫環

編輯:關於C++

C++ 中循環鏈表和約瑟夫環。本站提示廣大學習愛好者:(C++ 中循環鏈表和約瑟夫環)文章只能為提供參考,不一定能成為您想要的結果。以下是C++ 中循環鏈表和約瑟夫環正文


C++ 中循環鏈表和約瑟夫環

投稿:lqh

這篇文章主要介紹了C++ 中循環鏈表和約瑟夫環的相關資料,需要的朋友可以參考下

循環鏈表和約瑟夫環

循環鏈表的實現

單鏈表只有向後結點,當單鏈表的尾鏈表不指向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;
}

感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved