约瑟夫环的c++实现
//约瑟夫环 #include using namespace std; template struct Node //结点结构 { T data; //结点数据 Node }; template class linklist//循环链表 { Node public: linklist() :current(NULL),front(NULL) {}//无参构造 linklist(T a[],int maxsize)//有参构造 { int i; Node current = new Node current->data = a[maxsize - 1]; front = current; for (i = maxsize - 2; i >= 0; i--)//前移 { p = new Node p->data = a[i]; p->next = current; current = p; } front->next = current; } ~linklist();//析构 bool insert(T &x);//插入 T Delete(T &x);//删除 void Output();//输出元素 bool toLocatioin(T &t);//定位元素 void move(int t);//后移 T GetCurrentData() { return current->data; }//返回 }; template linklist { while (current != front) { Node current = current->next; delete r; } delete current; } template bool linklist { Node s->data = x; if (!s) return false; if (!current) //原循环链表为空 current = front = s->next = s; else //原循环链表非空 { s->next = current->next; current->next = s; front = current; current = s; } return true; } template T linklist { if (!current)//循环链表为空 return false; x = current->data; if (current == front)//链表中只有一个元素 { delete current; current = front = NULL; } else { front->next = current->next;//修改链表指针 delete current; current = front->next; } return true; } template void linklist { if (!current)//循环链表为空 return; Node do { cout << p->data << " "; p = p->link; } while (p != current); cout << endl; } template void linklist { for (int i = 1; i <= t; i++) { front = current; // front后移 current = current->next; //current后移 } } template bool linklist { if (!current)//循环链表为空 return false; Node while (current1->data != t) //寻找元素t { front1 = current1; current1 = current1->next; if (current1 == current)// 已寻找一圈没有元素为t的结点 return false; } current = current1; //current指向元素为t的结点 front = front1; return true; } class Joseph // 约瑟夫环类 { private: int numOfBoy; //圈中人数 int startPosition; //报数起始点 int interval; //报数间隔 public: Joseph(int boys,int start,int m) :numOfBoy(boys),startPosition(start),interval(m) {}//构造函数 void setNumOfBoy(int num) { numOfBoy = num; }//重置圈中人数 void setStartPosition(int start) { startPosition = start; }//重置起始点 void setInterval(int inter) { interval = inter; }//重置报数间隔 int GetWinner();//求得最终优胜者编号 void print(); //输出约瑟夫环 }; int Joseph::GetWinner() { linklist for (int i = 1; i <= numOfBoy; i++)//创建循环链表,编号依次为1~numOfBoy { boys.insert(i); } boys.toLocatioin(startPosition); //找到报数起点 cout << endl << "依次出列的小孩是:" << endl; for (int i = 1; i < numOfBoy; i++) //numOfBoy-1个小孩出圈 { int x; boys.move(interval - 1); //报数 boys.Delete(x); //出圈 cout << x << " "; //输出出圈编号 } return boys.GetCurrentData(); //返回优胜者编号 } void Joseph::print() //输出约瑟夫环 { cout << "圈中人数:" << numOfBoy << endl; cout << "报数起始点:" << startPosition << endl; cout << "报数间隔:" << interval << endl; } int main() { int total,interv,startboy; cout << "请输入初始数据:小孩数,起始小孩号码,间隔数:n"; cin >> total >> startboy >> interv; Joseph jose(total,startboy,interv); jose.print(); cout << "优胜者编号为: " << jose.GetWinner() << endl; system("pause"); return 0; } 测试结果: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |