circhain.h

常用算法与数据结构原代码

// file CirChain.h

#ifndef CirChain_
#define CirChain_

#include <iostream.h>
#include "cnode.h"
#include "xcept.h"

template <class T> class CirChainIterator;

template<class T>
class CirChain 
{
	friend CirChainIterator<T>;
	friend ostream& operator<<(ostream& out,const CirChain<T>& x);
public:
	CirChain() 
	{
		first=new CirChainNode<T>; 
		first->link=first; 
		last=first;
	}
	CirChain(const CirChain<T>& C);
	~CirChain()
	{ 
		Erase(); 
		delete first;
	}
	bool IsEmpty() const 
	{
		return first==first->link;
	}
	void Erase();
	void Zero() 
	{
		first->link=first;
	}
	int Length() const; 
	bool Find(int k, T& x) const; 
	int Search(const T& x) const; 
	CirChain<T>& Delete(int k, T& x); 
	CirChain<T>& Insert(int k, const T& x);
	CirChain<T>& Append(const T& x);
	CirChain<T>& Reverse();
	void Output(ostream& out) const;
private:
	CirChainNode<T> *first;  // pointer to first node
	CirChainNode<T> *last;
};

template<class T>
class CirChainIterator 
{
public:
	T* Initialize(const CirChain<T>& c)
	{
		location = c.first->link;
		if (location!=c.first) 
			return &location->data;
		return 0;
	}
	T* Next(const CirChain<T>& c)
	{
		if (location==c.first) 
			return 0;
		location = location->link;
		if (location!=c.first) 
			return &location->data;
		return 0;
	}
private:
	CirChainNode<T> *location;
};

template <class T>
CirChain<T>::CirChain(const CirChain<T>& C)
{
	CirChainNode<T> *p,*q;
	first=new CirChainNode<T>;
	q=first;
	p=C.first->link;
	while (p!=C.first)
	{
		CirChainNode<T> *s=new CirChainNode<T>;
		s->data=p->data;
		q->link=s;
		q=s;
		p=p->link;
	}
	q->link=first;
	last=q;
}  

template<class T>
void CirChain<T>::Erase()
{// CirChain destructor. Delete all nodes in CirChain.
	CirChainNode<T> *next=first->link;  // next node
	while (next!=first) 
	{
		first->link=next->link;
		delete next;
		next=first->link;
	}
	last=first;
}

template<class T>
int CirChain<T>::Length() const
{// Return the number of elements in the CirChain.
	CirChainNode<T> *current = first->link;
	int len = 0;
	while (current!=first) 
	{
		len++;
		current = current->link;
	}
	return len;
}

template<class T>
bool CirChain<T>::Find(int k, T& x) const
{// Set x to the k'th element in the CirChain.
	// Return false if no k'th; return true otherwise.
	if (k < 1) 
		return false;
	CirChainNode<T> *current = first->link;
	int index = 1;  // index of current
	while (index < k && current!=first) 
	{
		current = current->link;
		index++;
	}
	if (current!=first) 
	{
		x = current->data;
		return true;
	}
	return false; // no k'th element
}

template<class T>
int CirChain<T>::Search(const T& x) const
{// Locate x.  Return position of x if found.
	// Return 0 if x not in the CirChain.
	CirChainNode<T> *current = first->link;
	int index = 1;  // index of current
	while (current->data != x) 
	{
		current = current->link;
		index++;
	}
	return ((current==first) ? 0:index);
}

template<class T>
CirChain<T>& CirChain<T>::Delete(int k, T& x)
{// Set x to the k'th element and delete it.
	// Throw OutOfBounds exception if no k'th element.
	if (k < 1 || first==first->link)
		throw OutOfBounds(); // no k'th
	
	// p will eventually point to k'th node
	CirChainNode<T> *p = first->link;
	
	// move p to k'th & remove from CirChain
	if (k == 1) // p already at k'th
		first->link = p->link; // remove
	else 
	{ // use q to get to k-1'st
		CirChainNode<T> *q = first->link;
		for (int index = 1; index < k - 1 && q!=first; index++)
			q = q->link;
		if (q==first)
			throw OutOfBounds(); // no k'th
		p = q->link; // k'th
		if (p==last) last=q;
		q->link = p->link;
	} // remove from CirChain
	
	// save k'th element and free node p
	x = p->data;
	delete p;
	return *this;
}

template<class T>
CirChain<T>& CirChain<T>::Insert(int k, const T& x)
{// Insert x after the k'th element.
	// Throw OutOfBounds exception if no k'th element.
	// Pass NoMem exception if inadequate space.
	if (k < 0) 
		throw OutOfBounds();
	
	// p will eventually point to k'th node
	CirChainNode<T> *p = first->link;
	for (int index = 1; index < k && p!=first; index++)  // move p to k'th
		p = p->link;
	if (k > 0 && p==first) 
		throw OutOfBounds(); // no k'th
	
	// insert
	CirChainNode<T> *y = new CirChainNode<T>;
	y->data = x;
	if (k) 
	{// insert after p
		y->link = p->link;
		p->link = y;
	}
	else 
	{// insert as first element
		y->link = first->link ;
		first->link = y;
	}
	if (y->link==first) 
		last=y;
	return *this;
}

template <class T>
CirChain<T>& CirChain<T>::Append(const T& x)
{
	CirChainNode<T> *y;
	y=new CirChainNode<T>;
	y->data=x;
	y->link=first;
	if (first!=first->link)
    {
		last->link=y;
		last=y;
    }
	else
		first->link=last=y;
	return *this;
}

template <class T>
CirChain<T>& CirChain<T>::Reverse()
{
	CirChainNode<T> *p,*q,*r;
	p=first;
	q=p->link;
	last=q;
	while (q!=first)
	{
		r=q->link;
		q->link=p;
		p=q;
		q=r;
	}
	first->link=p;
	return *this;
}


template <class T>
ostream& operator<<(ostream& out,const CirChain<T>& x)
{
	CirChainNode<T> *current;
	for (current=x.first->link;current!=x.first;current=current->link)
		out<<current->data<<" ";
	out<<endl;
	return out;
}

template<class T>
void CirChain<T>::Output(ostream& out) const
{// Insert the CirChain elements into the stream out.
	CirChainNode<T> *current;
	for (current = first->link; current!=x.first; current = current->link)
		out << current->data << "  ";
	out<<endl;
}

#endif