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; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!