linklist.cpp

著名的约瑟夫问题编码

//约瑟夫问题：
#include "LinkList.h"
#include<iostream>
using namespace std;
/*
*前置条件：循环链表不存在
*输    入：无
*功    能：构建一个循环链表
*输    出：无
*后置条件：构建一个循环链表
*/
template <class T>
LinkList<T>:: LinkList()
{
	first=new Node<T>; 
	first->next=first;
	
}
/*
*前置条件：循环链表不存在
*输    入：数据信息pa,长度n
*功    能：将pa中元素建为长度为n的循环链表
*输    出：无
*后置条件：构建一个循环链表
*/
 
template <class T>  
LinkList<T>::LinkList(int n)
{
    first=new Node<T>;   //生成头结点
	first->next=first;
	Node<T> *s;
    for(int i=n; i>=1; i--)
	{ 
      s=new Node<T>; s->data=i;  //为每个数组元素建立一个结点
	  s->next=first->next; first->next=s;//插入到终端结点之后
	}
	Length=n;
   
}
/*
*前置条件：循环链表存在
*输    入：无
*功    能：删除循环链表
*输    出：无
*后置条件：循环链表被析构
*/
template <class T>
LinkList<T>:: ~LinkList()
{
	Node<T> *p=first->next,*q;
	while (p!=first) 
	{
		q=p;
		p=p->next;
	    delete q;
	}
	first=NULL;
}
/*
*前置条件：循环链表存在
*输    入：查询元素位置i
*功    能：按位查找位置为i的元素并输出值
*输    出：查询到的元素的值
*后置条件：循环链表不变
*/
template <class T>
T LinkList<T>::Get(int i) 
{   
	Node<T> *p; int j;
	p=first->next;  j=1;  //或p=first;  j=0;
	while (p!=first&&j<i)    
	{
		p=p->next;       //工作指针p后移
		j++;
	}
	if (!p) throw "位置";
	else return p->data;
}
/*
*前置条件：循环链表存在
*输    入：要删除元素位置i
*功    能：删除循环链表中位置为i的元素
*输    出：无
*后置条件：循环链表被删除了位置为i的元素
*/
template <class T>  
void LinkList<T>::Delete(int i)
{ 
	Node<T> *p,*q; int j;
	p=first->next;j=1;  //工作指针p初始化
	if(i==1)
	{  q=first->next;
	   first->next=q->next;
	   delete q;
	   q=NULL;
	}
	else
	{  
		while (p!=first&&j<i-1)  //查找第i-1个结点
		{
		   p=p->next;
		   j++;
		}
	    if (p==first||Length==0) throw "删除位置错误！";  //结点p不存在或结点p的后继结点不存在
        else 
		{
		   Node<T> *q; 
		   q=p->next;   //暂存被删结点
		   p->next=q->next;  //摘链
		   delete q;
		   q=NULL;
		}
	}
    Length--;
}
/*
*前置条件：循环链表存在
*输    入：无
*功    能：循环链表遍历
*输    出：输出所有元素
*后置条件：循环链表不变
*/
template <class T> 
void LinkList<T>::PrintList()
{
	Node<T> *p;
	p=first->next;
	while (p!=first)
	{
		cout<<(p->data)<<endl;
		p=p->next;
	}
	
}
/*
*前置条件：循环链表存在
*输    入：无
*功    能：求解约瑟夫问题
*输    出：约瑟夫问题的解
*后置条件：循环链表的某些节点被删除
*/
template <class T> 
void LinkList<T>::jushua(int m)
{  
   int j=1,counter=1;
   Node<T> *pr=first->next,*p,*q;
   /*j和counter是计数器，j用来计数到m(数人数的间隔),
     是为了找到一个出局者。counter用来计数寻找出局者
	 到first指针的相对位置。只要总人数大于 1 就一直
     执行下去。*/
   while(Length>1&&m>0)
   {   
	   /*****************如果找到一个出局者*******************/
	   if(j==m)//j用来计数到m，是为了找到一个出局者。
	   {   cout<<"第"<<pr->data<<"人出局"<<endl;
		   q=pr->next;
	       p=first->next;counter=1;
		   /*一直循环，从first->next指针位置找到
		    pr指针位置，从而找到出局者相对头指针
			的位置。*/
		   while(p!=pr)
           {  
	          counter++;
			  p=p->next;
		   }
		   pr=q;
		   try
		   {
		     Delete(counter);//删除掉出局者对应的节点。
		   }
		   catch(char ch[100])
		   {
			   cout<<"ch"<<endl;
		   }
		   j=1;//计数器归一
		   counter=1;//计数器归一
	   }
	   /*******************************************************/
	   /*--------------------如果没找到出局者-----------------*/
	   else
	   { 
		 if(pr->next==first)//如果下一个结点是头结点, 则跳过
			 pr=first->next;
		 else if(pr==first)//如果本结点是头结点, 则跳过，同时计数器j减一
		 {  pr=first->next;
		    j--;
		 }
		 else//否则则是最一般的情况，直接后移一人即可
		     pr=pr->next;
		 ++j;
	   }
	   /*-----------------------------------------------------*/
   }
   if(m<=0||Length<=0)
	   cout<<"输入错误！"<<endl;
   else
       cout<<"第"<<first->next->data<<"人留下"<<endl;
}

void main()
{  
   cout<<"约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。"<<endl;
   cout<<"从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1"<<endl;
   cout<<"开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出"<<endl;
   cout<<"列。请问最后一个出列的人的编号。本程序处理约瑟夫问题，请输入n及m"<<endl;
   int m,n;
   cin>>n>>m;
   LinkList<int> a(n);
   a.jushua(m);
}