约瑟夫环程序C++循环单链表实现。///当中的new和delete采用了重载函数。//也采用了可利用空间表提高了系统分配和回收的速度。// 题目：// 编号为1，2，3。。。。N的N个人按顺时针方向坐成一圈。每个人有一个密码，一开始任选一个// 整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数。报到M时停止报数，报M// 的人出列，将他的密码作为下一次报数的新值M，从他的顺时针方向上的下一个人开始重新从1// 开始报数。如此下去直到所有人都出列为止。
#include <iostream>using namespace std;//每个人的号码和密码。struct people{ int NO; int pass;}node;template <class Elem>class Link{private: static Link<Elem>* freelist;//静态数据成员的头接点。public: struct people element; Link* next; Link(people elemval,Link* nextval=NULL) { element.NO=elemval.NO; element.pass=elemval.pass; next=nextval; } Link(Link* nextval=NULL) { next=nextval; } void* operator new(size_t);// 重载new 函数。 void operator delete(void*);//重载delete函数。};
template <class Elem>class LList{private: Link<Elem> *head; Link<Elem> *tail; Link<Elem> *fence; void init() { head=tail=fence=new Link<Elem>; tail->next=head->next; //生成链表是要把它的头接点和尾接点连接起来构成循环链表。 //因为有一个空的头接点。所以要把他的尾接点接到头接点的下一个指针。 } void removeall() { while(head!=NULL) { fence=head; fence=fence->next; delete fence; } }public: LList() { init(); } ~LList() { removeall(); } bool insert(const people& T); bool remove(Elem&); void getOut(int&,int&); void prev(); bool append(const people& T);
};
template <class Elem>Link<Elem>* Link<Elem>::freelist=NULL;//静态数据成员的初始化。//重载的实现。template <class Elem>void* Link<Elem>::operator new(size_t){ if(freelist==NULL) return ::new Link; Link<Elem>* temp=freelist; freelist=freelist->next; return temp;}//重载的实现template <class Elem>void Link<Elem>::operator delete(void* ptr){ ((Link<Elem>*)ptr)->next=freelist; freelist=(Link<Elem>*)ptr;}
//插入函数。此程序并没有用到次函数。template <class Elem>bool LList<Elem>::insert(const people& T){ fence->next=new Link<Elem>(T,fence->next);//通过调用构造函数的初始化。 if(tail==fence) { tail=fence->next; tail->next=head->next; } return true;}//从链表的尾插入。template <class Elem>bool LList<Elem>::append(const people& T){ tail=tail->next=new Link<Elem>(T,head->next);//通过调用构造函数的初始化。 return true;}template <class Elem>bool LList<Elem>::remove(Elem& it){ if(tail==head) return false; if(fence->next==NULL) { it=fence->element.pass; cout<<fence->element.NO<<"-- "; return true; } it=fence->next->element.pass; cout<<fence->next->element.NO<<"-- "; Link<Elem>* temp=fence->next; fence->next=temp->next; if(temp==tail) { tail=fence;//当是尾接点的时候要把他的尾指针指向标记指针 } delete temp; return true;}//找下一个接点。template <class Elem>void LList<Elem>::prev(){ if(fence->next!=head) fence=fence->next; else { fence->next=head->next; fence=fence->next; } }//程序的主题//template <class Elem>void LList<Elem>::getOut(int &it,int& sum){ int sign,n=1; fence=tail;//因为是从报到数的上一个人开始找到的删除点。所以要记得从head的上一个接点tail开始。 cout<<"Enter you want to first get out:"; cin>>sign;//报数值。 while(sum>0) { if(sign>sum&&sign>1) //为避免多次的循环找数通过取模可以节省时间。 sign=sign%sum;
if(sign==n||sum==1) { remove(it); sign=it; sum--; n=0;//重新做标记从下一个人1开始。 } else prev();//找下个接点。 n++; }
} int main(){ LList<int> A; struct people T; int item,it,sum; cout<<"Enter you want to people:"; cin>>sum; for(int i=1;i<=sum;i++) { cout<<"enter the--"<<i<<"--pass:"; cin>>item; T.NO=i; T.pass=item; A.append(T);//我这里是从尾插入的。 cout<<endl; } A.getOut(it,sum); return 0;} 这是我学习数据结构和算法写的程序.我平时还可以看看自己写的程序.到以后自己有进步了.我在来看看自己的程序
是否是正确.合理的.
