one.cpp

Ex4-22 单射函数问题 &laquo 问题描述： 设函数f将点集S = {0,1,&#61516 , n -1}映射为f (S) = { f (i) | i&Icirc S} &Iacute

#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
template<class T>
class Queue;
class OutOfBounds
{
public:
	OutOfBounds(){}
};
template<class T>
class Node{
	friend Queue<T>;
	private:
		T data;
		Node<T> * next;
};
template<class T>
class Queue{
	public:
		Queue(){front=rear=0;}
		~Queue();
		bool Empty() const
		{
			return ((front)? false :true);
		}
		bool Full() const;
		T Frist() const;
		T Last() const;
		Queue<T>& EnQueue(const T& x);
		Queue<T>& DeQueue(T& x);
	private:
		Node<T> * front;
		Node<T> * rear;
};
template<class T>
Queue<T>:: ~Queue()
{
	Node<T> * next;
	while(front)
	{
		next=front->next;
		delete front;
		front=next;
	}
};
template<class T>
bool Queue<T>:: Full() const
{
	Node<T> *p;
	try{
		p=new Node<T>;
		delete p;
		return false;
	}
	catch(NoMem){return true;}
};
template<class T>
T Queue<T>::Frist() const
{
	if(Empty()) throw OutOfBounds();
	return front->data;
};
template<class T>
T Queue<T>::Last() const
{
	if(Empty()) throw OutOfBounds();
	return rear->data;
};
template<class T>
Queue<T>& Queue<T>::EnQueue(const T& x)
{
	Node<T> *p=new Node<T>;
	p->data=x;
	p->next=0;
	if(front)
		rear->next=p;
	else front=p;
	rear=p;
	return *this;
};
template<class T>
Queue<T>& Queue<T>::DeQueue(T& x)
{
	if(Empty()) throw OutOfBounds();
	x=front->data;
	Node<T> *p=front;
	front=front->next;
	delete p;
	return *this;
}
void main()
{
	int n,count=0;
	ifstream fin("input.txt");
	ofstream fout("output.txt");
	fin>>n;
	int* a=new int[n];
	for(int i=0;i<n;i++)
	{
		fin>>a[i];
	}
	bool* label= new bool[n];//用来标识是否已访问
	bool Find=false;  //用来标识是否找到起始点
	for(int j=0;j<n;j++)
	{
		label[j]=false;
	}
	Queue<int> Q;
	for(int k=0;k<n;k++)
	{
		if(!label[k])
		{
			int current=k,next=a[current];
			Q.EnQueue(current);
			label[current]=true;
			while(!label[next])
			{
				Q.EnQueue(next);
				label[next]=true;
				current=next;
				next=a[current];
			}
			while(!Q.Empty())
			{
				int w;
				Q.DeQueue(w);
				if(w==next)
					Find=true;
				if(Find)
					count++;
			}
			Find=false;
		}
	}
	fout<<count<<endl;
}