【数据结构】1-2 约瑟夫环问题
程序员文章站
2023-08-18 09:19:15
这里放出两种不同的代码,一个是老师给的(较为复杂),还有一个是自己写的。 自己写的: 测试代码: 其实原理很简单,就是通过循环链表不断循环然后删除就OK 标准代码: 测试代码 ......
这里放出两种不同的代码,一个是老师给的(较为复杂),还有一个是自己写的。
自己写的:
#include<iostream> using namespace std; struct node { int data; //数据单元 node *link; //指向下一个结点 }; class josephus { private: node *head, *current; //head是头结点,current指向当前结点 int sum;//存储链表中元素的个数 public: josephus(); //无参构造函数,全部初始化为空 josephus(int snumber, int strnumber);//有参构造函数,snumber为总数,strnumber为开始序号 ~josephus();//析构函数 void del(node *&p); void select(int num);//num为间隔数 void print(); }; josephus::josephus() { current = null; head = null; sum = 0; } josephus::josephus(int snumber, int strnumber) { sum = snumber; head = new node; head->data = strnumber; current = head; int dt = strnumber + 1; for (int i = 1; i < snumber; i++) { node *p; p = new node; p->data = dt; current->link = p; current = p; dt++; } current->link = head; } void josephus::del(node *&p) { node *d = p->link; p->link = p->link->link; delete d; } void josephus::select(int num) { int sont = 1; node *p = head; while (sum!= 1) { if (sont % (num-1) == 0) { del(p); sum--; head = p; } sont++; p = p->link; } } void josephus::print() { cout << "剩下的序号有:" << endl; node *p = head; for (int i = 0; i < sum; i++) { cout << p->data << " "; p = p->link; } cout << endl; } josephus::~josephus() { /*node *p = head->link; while (p!=head) { node *de = p; p = p->link; delete de; }*/ head = null; current = null; }
测试代码:
#include"linklist.h" int main() { int snum, stnum,num; cout << "请输入总数以及开始序号:"; cin >> snum >> stnum; josephus a(snum, stnum); a.print(); cout << "请输入间隔数:"; cin >> num; a.select(num); a.print(); system("pause"); return 0; }
其实原理很简单,就是通过循环链表不断循环然后删除就ok
标准代码:
//circle.h #include<iostream> using namespace std; template<class t> struct node //结点结构 { t data; //结点数据 node*link; node() { link = null; } node(t e, node*next = null) { data = e; link = next; } }; template<class t> class circlelinklist { //不带表头结点的循环链表类 private: node<t> *current, *front; //current指向某结点,front指向current前驱 public: circlelinklist() :current(null), front(null) {} //构建空循环链表 circlelinklist(t *d, int msize); //利用d数组元素构建循环链表 ~circlelinklist(); //析构函数 bool insertafter(const t&x); //在current所指结点之后插入x bool removecurrent(t&x); //删除current所指结点 void movenext(int n = 1); //current后移n次 t getcurrentdata() { return current->data; } bool tolocatioin(t &t);//让current指向t结点,若没有则current不移动 void output() const; //输出循环链表 }; 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(); //输出约瑟夫环 }; template<class t> circlelinklist<t>::circlelinklist(t *d, int msize) { //构造函数,将d数组中的msize个元素创建循环链表 //采用前插法创建。 int i; node<t> *p; current = new node<t>; current->data = d[msize - 1]; front = current; for (i = msize - 2; i >= 0; i--) { p = new node<t>(d[i], current); current = p; } front->link = current; } template<class t> circlelinklist<t>::~circlelinklist() //析构函数 { while (current != front)//销毁循环链表 { node<t> *r = current; current = current->link; delete r; } delete current; } template<class t> bool circlelinklist<t>::insertafter(const t&x) //在current所指结点之后插入x,current指向x结点 { node<t> *s = new node<t>(x); if (!s)return false; if (!current) //原循环链表为空 current = front = s->link = s; else //原循环链表非空 { s->link = current->link; current->link = s; front = current; current = s; } return true; } template<class t> bool circlelinklist<t>::removecurrent(t&x) //删除current所指结点 { if (!current)//循环链表为空 return false; x = current->data; if (current == front)//链表中只有一个元素 { delete current; current = front = null; } else { front->link = current->link;//修改链表指针 delete current; current = front->link; } return true; } template<class t> void circlelinklist<t>::output() const //输出循环链表 { if (!current)//循环链表为空 return; node<t> *p = current; do { cout << p->data << " "; p = p->link; } while (p != current); cout << endl; } template<class t> void circlelinklist<t>::movenext(int k) //current后移k次 { for (int i = 1; i <= k; i++) { front = current; // front后移 current = current->link; //current后移 } } template<class t> bool circlelinklist<t>::tolocatioin(t &t) //将current指向元素为t的结点,若没有则current不移动 { if (!current)//循环链表为空 return false; node<t> *current1 = current, *front1 = front; while (current1->data != t) //寻找元素t { front1 = current1; current1 = current1->link; if (current1 == current)// 已寻找一圈没有元素为t的结点 return false; } current = current1; //current指向元素为t的结点 front = front1; return true; } int joseph::getwinner()//获得最终优胜者 { circlelinklist<int> boys; for (int i = 0; i < numofboy; i++)//创建循环链表,编号依次为1~numofboy { int temp = i + 1; boys.insertafter(temp); } boys.tolocatioin(startposition); //找到报数起点 cout << endl << "依次出列的小孩是:" << endl; for (int i = 1; i < numofboy; i++) //numofboy-1个小孩出圈 { int x; boys.movenext(interval - 1); //报数 boys.removecurrent(x); //出圈 cout << x << " "; //输出出圈编号 } return boys.getcurrentdata(); //返回优胜者编号 } void joseph::print() //输出约瑟夫环 { cout << "圈中人数:" << numofboy << endl; cout << "报数起始点:" << startposition << endl; cout << "报数间隔:" << interval << endl; }
测试代码
//测试代码.cpp #include"circle.h" int main() { int total, interv, startboy; cout << "请分别输入人数,起始号码和间隔数"<<endl; cin >> total >> startboy >> interv; joseph jose(total, startboy, interv); jose.print(); cout << "优胜者编号为: " << jose.getwinner() << endl; system("pause"); return 0; }