鍊隊列約瑟夫環c++代碼_C++ 中循環連結清單和約瑟夫環

循環連結清單和約瑟夫環

循環連結清單的實作

單連結清單隻有向後結點，當單連結清單的尾連結清單不指向NULL，而是指向頭結點時候，形成了一個環，成為單循環連結清單，簡稱循環連結清單。當它是空表，向後結點就隻想了自己，這也是它與單連結清單的主要差異，判斷node->next是否等于head。

代碼實作分為四部分：

初始化

插入

删除

定位尋找

代碼實作：

void ListInit(Node *pNode){

int item;

Node *temp,*target;

cout<

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<

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

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

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

#include

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

start = start->next;

temp = start->next;

start->next = start->next->next;

start = start->next;

cout<data<

delete temp;

}

}

else{

for(int i=0;i

Node *temp = new Node;

if(!temp)

exit(0);

cout<data<

temp = start;

start = start->next;

delete temp;

}

}

cout<

cout<data<

}

int main(){

Joseph(3,1);

Joseph(3,2);

return 0;

}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支援！