单向循环链表实现约瑟夫环（c++）（数据结构）

一、问题重述：  

        n 个人围成一个圆圈，首先第 1 个人从 1 开始，一个人一个人顺时针报数,  报到第 m 个人，令其出列。然后再从下一 个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去,  直到圆圈中只剩一个人为止。此人即为优胜者，请输出优胜者。

二、实现思路：

        将结点的数据域存储元素的序号，通过链表的遍历、元素的查询（search）、元素的删除（remove）等方法便可以较容易实现。

三、下面是具体代码实现思路：

        首先是单向循环链表的实现：

enum InsMod {INF, INR};//头插还是尾插
template class CirclinkNode{
public:
	T data;
	CirclinkNode *link;
	CirclinkNode(CirclinkNode *ptr = NULL){//建立空结点
		link = ptr;
	}
	CirclinkNode(const T &item, CirclinkNode *ptr = NULL){//建立非空结点
		data = item;
		link = ptr;
	}
};

template class CircList{
public:
	CircList()
	{
	    this->first = new CirclinkNode();
	    first->link=first;

        last=first;
	}
	CircList(CircList &L)//复制一个环链表
	{
	    CirclinkNode* p = L.first->link;
	    CirclinkNode*q = this->first->link;
	    while(p!=first)
        {
            q= new CirclinkNode(p->data);
            q=q->link;
            p=p->link;
        }
        last = q;
	}
	~CircList()
	{
	    this->makeEmpty();
	    delete this->first;
	}
	void makeEmpty()
	{
	    CirclinkNode*p = this->first->link;
	    CirclinkNode*q = p->link;
	    while(p!=first)
        {
            delete p;
            p = q;
            q=q->link;
        }
	}
	int Length()const
	{
	    int num =1;
	    CirclinkNode* p = first->link;

	    while(p!=first)
        {
            ++num;
            p=p->link;
        }
        return num;
	}
	CirclinkNode *Search(T& x,int &n)
	{
	    CirclinkNode* p = first->link;
         n=1;
	    while(p->data!=x)
        {
            ++n;
            p=p->link;
            if(p==first)
                exit(1);
        }
        return p;
	}
	CirclinkNode *Locate(int i)
	{
	    if(i<1||i>Length())
        {
            exit(1);
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
                return p;
            p=p->link;
        }
        return p;
	}

	bool getData(int i,T&x)const
	{
	    if(i<1||i>Length())
        {
            return false;
        }
        int num=1;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
                x = p->data;
            p=p->link;
        }
        return true;
	}
	void setData(int i, T &x)
	{
	    if(i<1||i>Length())
        {
            return;
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
            p->data=x;
            p=p->link;
        }
	}
	bool Insert(int i, T &x)
	{
        if(i<1||i>Length()+1)
        {
            return false;
        }
        CirclinkNode* p =NULL;
        if(i==1)
            p = first;
        else
	     p = Locate(i-1);

	    CirclinkNode* q = p->link;

	    CirclinkNode *newNode = new CirclinkNode(x);

	    p->link = newNode;

	    newNode->link = q;
        if(i==Length()+1)
        {
        last = newNode;
        }
	    return true;

	}
	bool Remove(int i, T &x)
	{
        if(i<=0||i>Length())
        {
            return false;
        }
        int j=0;
        CirclinkNode* p = first;
        for(j=1; jlink;
        }
        CirclinkNode *q = p->link->link;
        x = p->link->data;
        if(i==Length())
            last = p;
        delete p->link;
        p->link = q;
        return true;
	}
	bool IsEmpty()const
	{
	    return first->link==last;
	}
	bool IsFull()const
	{
	    return (new CirclinkNode() )==NULL;
	}
	void Sort()
	{
        CirclinkNode * p =first->link;
        CirclinkNode *q=NULL;
        if(NULL==p)
            return ;

        int num = this->Length();
        int maxIndex=1;

        int Max =p->data;
        for(int i=1; idata)
               {
                   maxIndex = j;
                   Max = p->data;
               }
               q=p;
                p=p->link;
            }

            setData(maxIndex,q->data);
            setData(num,Max);
        }
	}
	void Inverse()//不要返回
	{
        int num = this->Length();
        for(int i=1; i * p = Locate(i);
            CirclinkNode* q = Locate(j);

            T temp = p->data;
            p->data = q->data;
            q->data = temp;
        }
	}
	void input(T endTag, InsMod im = INR)
	{
	    if(im==INR)
        {
        Insert(Length()+1,endTag);
        }
        else{
        Insert(1,endTag);
        }
	}
	void output()
	{
	    CirclinkNode* p =first->link;

	    while(p!=first)
        {
          cout<data<<" ";

          p=p->link;
        }
        cout< &operator = (CircList &L)
	{
	    this->makeEmpty();

    CirclinkNode* q =  L.first->link;
    while(q!=L.first)
    {
        input(q->data,INR);
        q=q->link;
    }

	}
 CirclinkNode* travel(int x,CirclinkNode*temp)
	{
	    CirclinkNode* pre = temp;
	    for(int i=1;ilink;
        }
        if(pre==first)
            pre=pre->link;
        return pre;
	}
	int getNum(CirclinkNode* temp)
	{
	    CirclinkNode*pre = first->link;
	    int num=1;
	    while(pre!=temp)
        {
            if(pre!=first)
            ++num;
            pre=pre->link;
        }
        return num;
	}
	friend ostream& operator << (ostream &out, CircList &L){
		CirclinkNode *current = L.first->link;
		while (current != L.first){
			out << current->data <<'t';
			current = current->link;
		}
		out<> (istream &in, CircList &L){//重新输入数据，向后生成
		T val;
		L.makeEmpty();//先清空
		while (!in.eof()){
			in >> val;
			L.last->link = new CirclinkNode(val);
			assert(L.last->link);
			L.last = L.last->link;
		}
		L.last->link = L.first;
		in.clear();//当以ctrl_Z结束，流关闭，必须重新打开
		return in;
	}
	CirclinkNode* getFirst()
	{
	    return first;
	}
protected:
	CirclinkNode *first, *last;
	void inputFront(T endTag);
	void inputRear(T endTag);
};

        根据约瑟夫环的要求，在链表类内加入travel（）方法返回每次遍历要出列的人。由于笔者采用的是带头结点的链表，在遍历时必然会遇到空头节点，此时让迭代次数减一以保证遍历的正确。

 CirclinkNode* travel(int x,CirclinkNode*temp)
{
	    CirclinkNode* pre = temp;
	    for(int i=1;ilink;
        }
        if(pre==first)
            pre=pre->link;
        return pre;
}

        在链表类内加入getNum（）实现每次循环后，得到要查询结点此时在链表里的相对序号。

	int getNum(CirclinkNode* temp)
	{
	    CirclinkNode*pre = first->link;
	    int num=1;
	    while(pre!=temp)
        {
            if(pre!=first)
            ++num;
            pre=pre->link;
        }
        return num;
	}

在main函数里具体实现如下：

int main(){
	CircList List;
	int x=0;
 for(int i=0;i<10;i++)//假设约瑟夫环最初有十人，序号为从1到10
 {
     x=i+1;
     List.Insert(i+1,x);
 }

CirclinkNode* pre = List.getFirst()->link;//初始从序号为1的人开始循环
CirclinkNode*  prev =pre;//中间指针，便于pre结点删除后能够赋值给pre继续循环
while(List.Length()!=1)
{

   pre= List.travel(3,pre);//循环设为3
   prev = pre;
   pre=pre->link;
   List.Remove(List.getNum(prev),x);
   cout<<"出列的人为："<