chain.h

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

// file chain.h


#ifndef Chain_
#define Chain_

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

template <class T> class ChainIterator;

template<class T>
class Chain 
{
	friend ChainIterator<T>;
	friend ostream& operator<<(ostream& out,const Chain<T>& x);
public:
	Chain() 
	{
		first = 0;
	}
	Chain(const Chain<T>& C);
	~Chain()
	{ 
		Erase();
	}
	bool IsEmpty() const 
	{
		return first == 0;
	}
	void Erase();
	void Zero() 
	{
		first=0;
	}
	int Length() const; 
	bool Find(int k, T& x) const; 
	int Search(const T& x) const; 
	void BinSort(int range);
	Chain<T>& BubbleSort();
	Chain<T>& SelectionSort();
	Chain<T>& RankSort();
	Chain<T>& Delete(int k, T& x); 
	Chain<T>& Delete(T& x);
	Chain<T>& Insert(int k, const T& x);
	Chain<T>& Append(const T& x);
	Chain<T>& Reverse();
	Chain<T>& FromList(LinearList<T>& L); 
    Chain<T>& ToList(LinearList<T>& L);
	Chain<T>& Alternate(const Chain<T>& A, const Chain<T>& B);
	Chain<T>& Merge(const Chain<T>& A, const Chain<T>& B);
	Chain<T>& Split(Chain<T>& A, Chain<T>& B);
	void Output(ostream& out) const;
private:
	ChainNode<T> *first;  // pointer to first node
	ChainNode<T> *last;
};

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

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

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

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

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

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

template<class T>
Chain<T>& Chain<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)
		throw OutOfBounds(); // no k'th
	
	// p will eventually point to k'th node
	ChainNode<T> *p = first;
	
	// move p to k'th & remove from chain
	if (k == 1) // p already at k'th
		first = first->link; // remove
	else 
	{ // use q to get to k-1'st
		ChainNode<T> *q = first;
		for (int index = 1; index < k - 1 && q;	index++)
			q = q->link;
		if (!q || !q->link)
			throw OutOfBounds(); // no k'th
		p = q->link; // k'th
		if (p==last) 
			last=q;
		q->link = p->link;
	} // remove from chain
	
	// save k'th element and free node p
	x = p->data;
	delete p;
	return *this;
}

template<class T>
Chain<T>& Chain<T>::Delete(T& x)
{// Delete element matching x.
	// Throw BadInput exception if no match.
	ChainNode<T> *current = first,
		*trail = 0; // one behind current
	
	// search for match
	while (current && current->data != x) 
	{
		trail = current;
		current = current->link;
	}
	if (!current) 
		throw BadInput(); // no match
	
	// match found in node current
	x = current->data; // save matching element
	
	// remove current from chain
	if (trail) 
		trail->link = current->link;
	else 
		first = current->link; // current is first node
	
	delete current;  // free node
	return *this;
}

template<class T>
Chain<T>& Chain<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
	ChainNode<T> *p = first;
	for (int index = 1; index < k && p;	index++)  // move p to k'th
		p = p->link;
	if (k > 0 && !p) 
		throw OutOfBounds(); // no k'th
	
	// insert
	ChainNode<T> *y = new ChainNode<T>;
	y->data = x;
	if (k) 
	{// insert after p
		y->link = p->link;
		p->link = y;
	}
	else 
	{// insert as first element
		y->link = first;
		first = y;
	}
	if (!y->link) 
		last=y;
	return *this;
}

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

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

template <class T>
void Chain<T>::BinSort(int range)
{
	int b;
	ChainNode<T> **bottom,**top;
	bottom=new ChainNode<T>* [range+1];
	top=new ChainNode<T>* [range+1];
	for (b=0;b<=range;b++)
		bottom[b]=0;
	for (;first;first=first->link)
	{
		b=first->data;
		if (bottom[b])
		{
			top[b]->link=first;
			top[b]=first;
		}
		else 
			bottom[b]=top[b]=first;
	}
	ChainNode<T> *y=0;
	for (b=0;b<=range;b++)
		if (bottom[b])
		{
			if (y)
				y->link=bottom[b];
			else
				first=bottom[b];
			y=top[b];
		}
		if (y) 
			y->link=0;
		last=y;
		delete []bottom;
		delete []top;
}

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

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

template<class T>
Chain<T>& Chain<T>::FromList(LinearList<T>& L)
{// Construct a chain from L.
	// first make *this empty
	Erase();
	
	// copy elements from L
	for (int i = 1; i <= L.Length(); i++)
	{
		T x;
		L.Find(i,x);
		Append(x);
	}
	
	return *this;
}

template<class T>
Chain<T>& Chain<T>::ToList(LinearList<T>& L)
{
	int len = L.Length();
	for (int i = len; i > 0; i--) {
		T x;
		L.Delete(i,x);
	}
	
	// copy from *this
	ChainNode<T> *current = first;
	i = 1; // index of current element
	while (current) 
	{// copy current element
		L.Insert(i-1, current->data);
		current = current->link;  // move to next node
		i++;
	}
	
	return *this;
}

template<class T>
Chain<T>& Chain<T>::Alternate(const Chain<T>& A, const Chain<T>& B)
{
	// Meld alternately from A and B.
	Erase(); // empty out *this
	
	ChainNode<T> *ca = A.first;  // pointer to current node in A
	ChainNode<T> *cb = B.first;  // pointer to current node in B
	
	while (ca && cb) 
	{
		Append(ca->data);
		ca = ca->link;
		Append(cb->data);
		cb = cb->link;
	}
	
	while(ca)
	{
		Append(ca->data);
		ca = ca->link;
	}
	
	while(cb)
	{
		Append(cb->data);
		cb = cb->link;
	}
	return *this;
}


template<class T>
Chain<T>& Chain<T>::Merge(const Chain<T>& A, const Chain<T>& B)
{
	// Merge the sorted chains A and B.
	Erase(); // empty out *this
	
	ChainNode<T> *ca = A.first;  // pointer to current node in A
	ChainNode<T> *cb = B.first;  // pointer to current node in B
	
	// merge from A and B until one is empty
	while (ca && cb) 
	{
		if (ca->data <= cb->data) 
		{	// A element goes first
			Append(ca->data);
			ca = ca->link;
		}
		else 
		{	// B element is smaller
			Append(cb->data);
			cb = cb->link;
		}
	}
	
	// append the rest
	// at most one of A and B is nonempty now
	if (ca) 
	{
		while(ca)
		{
			Append(ca->data);
			ca = ca->link;
		}
	}
	else 
	{
		while(cb)
		{
			Append(cb->data);
			cb = cb->link;
		}
	}
	return *this;
}

template<class T>
Chain<T>& Chain<T>::Split(Chain<T>& A, Chain<T>& B)
{
	// Split A into two chains B and C.
	// first free all nodes in B and C
	A.Erase();
	B.Erase();
	
	ChainNode<T> *ts = first;  // pointer to current node in this
	
	while (ts) 
	{
		// first give B an element
		A.Append(ts->data);
		ts = ts->link;
		if (!ts) 
			break;
		// now give C an element
		B.Append(ts->data);
		ts = ts->link;
	}
	return *this;
}

template<class T>
Chain<T>& Chain<T>::BubbleSort()
{// Sort *this using the bubble sort method.
	if (!first) 
		return *this;       // empty list
	
	// define cursors
	ChainNode<T> *AfterLast = 0,    // node after last one
		*current,          // curent node
		*next,             // node right of current
		*previous;         // node left of current
	
	// bubble sort
	while (first->link != AfterLast) 
	{
		// more than one element remains
		// do a bubbling pass
		current = first;
		next = first->link;
		previous = 0;
		while (next != AfterLast)
		{
			// compare current and next and
			// swap nodes if necessary
			if (current->data > next->data)
			{
				// swap the nodes
				if (previous) 
					previous->link = next;
				else 
					first = next;
				current->link = next->link;
				next->link = current;
				previous = next;
				next = current->link;
            }
			else 
			{// move cursors forward one node
				previous = current;
				current = next;
				next = next->link;
			}
		}
		//  need to go only as far as previous
		AfterLast = current;
	}
	
	return *this;
}

template<class T>
Chain<T>& Chain<T>::SelectionSort()
{// Sort *this using the selection sort method.
	if (!first) 
		return *this;       // empty list
	
	// define cursors
	ChainNode<T> *AfterLast = 0,    // node after last one
		*MaxNode,          // node with max element
		*PreMax,           // node left of MaxNode
		*current,          // curent node
		*previous;         // node left of current
	
	// selection sort
	while (first->link != AfterLast) 
	{
		// more than one element remains
		// do a selection pass
		MaxNode = first;
		PreMax = 0;
		current = first->link;
		previous = first;
		while (current->link != AfterLast) 
		{
			// compare current and MaxNode
			// update MaxNode if necessary
			if (current->data > MaxNode->data) 
			{
				// update PreMax and MaxNode
				PreMax = previous;
				MaxNode = current;
            }
			// move cursors forward one node
			previous = current;
			current = current->link;
		}
		if (current->data > MaxNode->data)
			// no node is to be moved
			// set for next pass
			AfterLast = current;
		else 
		{
			// must bring MaxNode to right of current
			// first delete MaxNode from present location
			if (PreMax)
				// MaxNode is not the first node on the chain
				PreMax->link = MaxNode->link;
			else
				// MaxNode is the first node
				first = MaxNode->link;
			// now insert MaxNode after current
			MaxNode->link = current->link;
			current->link = MaxNode;
			// set for next pass
			AfterLast = MaxNode;
		}
	}
	
	return *this;
}

template<class T>
Chain<T>& Chain<T>::RankSort()
{// Sort *this using the rank sort method.
	
	if (!first) 
		return *this;  // empty chain
	
	int n = Length();
	
	// r[i] will be rank of element i+1
	int *r = new int[n];
	for (int i = 0; i < n; i++)
		r[i] = 0;  // initialize
	
	// compute ranks
	// compare all pairs of elements
	ChainNode<T> *c = first;
	for (i = 0; i < n; i++) 
	{
		// c->data is element i+1
		ChainNode<T> *d = first;
		for (int j = 0; j < i; j++) 
		{
			// d->data is element j+1
			if (d->data <= c->data) 
				r[i]++;
			else 
				r[j]++;
			d = d->link;
		}
		c = c->link;
	}
	
	// distribute to bins by rank
	ChainNode<T> **bin = new ChainNode<T> * [n];
	c = first;
	for (i = 0; i < n; i++) 
	{
		bin[r[i]] = c;
		c = c->link;
	}
	
	// collect from bins
	first = bin[0];
	ChainNode<T> *last = first;  // last node on chain
	for (i = 1; i < n; i++)
		last = last->link = bin[i];
	last->link = 0;
	
	delete [] r;
	delete [] bin;
	
	return *this;
}

#endif