doublechain.h

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

// doubly linked list
// extended to include methods of Exercise 57.

#ifndef DoubleChain_
#define DoubleChain_


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

template<class T>
class DoubleChain 
{
public:
	DoubleChain() 
	{
		LeftEnd = RightEnd = current = 0;
	}
    ~DoubleChain();
    bool IsEmpty() const 
	{
		return LeftEnd == 0;
	}
    int Length() const; 
    bool Find(int k, T& x) const; 
    int Search(const T& x) const; 
    DoubleChain<T>& Delete(int k, T& x); 
    DoubleChain<T>& Insert(int k, const T& x);
    void ResetLeft()
    {
		if (LeftEnd) 
		{// not empty
			current = LeftEnd;
			return;
		}
        // list is empty
        throw OutOfBounds();
    }
    void ResetRight()
	{
		if (LeftEnd) 
		{// not empty
			current = RightEnd;
			return;
		}
		// list is empty
		throw OutOfBounds();
	}
    bool Current(T& x)
    {
		if (current) 
		{// at a node
			x = current->data;
			return true;
		}
		// not at a node
		return false;
    }
    bool End()
    {
		return current == RightEnd;
	}
    bool Front()
    {
		return current == LeftEnd;
	}
	bool Next()
    {
		if (!current) 
			return false;
		// there is a next node, which may be 0
		current = current->right;
		return true;
	}
    bool Previous()
    {
		if (!current) 
			return false;
		// there is a previous node, which may be 0
		current = current->left;
		return true;
	}
	void Output(ostream& out) const;
private:
    DoubleNode<T> *LeftEnd,   // pointer to leftmost node
		*RightEnd,  // pointer to rightmost node
		*current;   // pointer to current node
};

template<class T>
DoubleChain<T>::~DoubleChain()
{// Double destructor. Delete all nodes.
	DoubleNode<T> *curr = LeftEnd,  // current node
				  *next;            // next node
	while (curr) 
	{
		next = curr->right;
		delete curr;
		curr = next;
	}
}

template<class T>
int DoubleChain<T>::Length() const
{// Return the number of elements in the list.
	// count nodes
	DoubleNode<T> *curr = LeftEnd;
	int len = 0;  // number to left of curr
	while (curr) {
		len++;
		curr = curr->right;
	}
	return len;
}

template<class T>
bool DoubleChain<T>::Find(int k, T& x) const
{// Set x to the k'th element in the list.
	// Return false if no k'th; return true otherwise.
	if (k < 1 || !LeftEnd) 
		return false;
	
	DoubleNode<T> *curr = LeftEnd;
	int index = 1;  // index of curr
	while (index < k && curr) 
	{
		// move to next node
		curr = curr->right;
		index++;
	}
	if (index == k) 
	{
		x = curr->data;
		return true;
	}
	return false; // no k'th element
}

template<class T>
int DoubleChain<T>::Search(const T& x) const
{// Locate x.  Return position of x if found.
	// Return 0 if x not in the chain.
	if (!LeftEnd)
		return 0;  // list is empty
	
	// examine nodes
	DoubleNode<T> *curr = LeftEnd;
	int index = 1;  // index of curr
	while (curr && curr->data != x) 
	{
		// move to next node
		curr = curr->right;
		index++;
	}
	if (curr)
		return index;
	return 0;
}

template<class T>
DoubleChain<T>& DoubleChain<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 || !LeftEnd)
		throw OutOfBounds(); // no k'th
	
	// p will eventually point to k'th node
	DoubleNode<T> *p = LeftEnd;
	int index = 1;  // index of p
	
	// move p to k'th
	for (; index < k && p; index++)
		p = p->right;
	
	// make sure p is at the k'th element
	if (index != k) 
		throw OutOfBounds(); // no k'th
	
	// remove p from list
	if (p == LeftEnd) 
	{
		// delete first node
		LeftEnd = LeftEnd->right;
		if (!LeftEnd)  // list is empty
			RightEnd = 0;
		else  // list is not empty
			LeftEnd->left = 0;
	}
	else if (p == RightEnd) 
	{
		// delete last node
		RightEnd = RightEnd->left;
		RightEnd->right = 0;
	}
	else 
	{
		// delete an interior node
		p->right->left = p->left;
		p->left->right = p->right;
	}
	
	// save k'th element, update current, and free node p
	x = p->data;
	if (p == current)  // set current pointer to 0
		current = 0;
	delete p;
	
	return *this;
}

template<class T>
DoubleChain<T>& DoubleChain<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();
	
	if (k) 
	{// locate k'th node
		if (!LeftEnd) 
			throw OutOfBounds();  // empty list
		
		// p will eventually point to k'th node
		DoubleNode<T> *p = LeftEnd;
		int index = 1;
		// move p to k'th
		for (; index < k && p; index++)
			p = p->right;
		if (index != k) 
			throw OutOfBounds(); // no k'th
		
		// insert after p
		DoubleNode<T> *y = new DoubleNode<T>;
		y->data = x;
		y->right = p->right;
		p->right = y;
		y->left = p;
		if (p == RightEnd) // y is now the last node
			RightEnd = y;
		else  // y is not the last node
			y->right->left = y;
	}
	else 
	{// insert as first element
		DoubleNode<T> *y = new DoubleNode<T>;
		y->data = x;
		if (LeftEnd)
		{// insert into nonempty list
            y->right = LeftEnd;
            y->left = 0;
            LeftEnd->left = y;
		}
		else 
		{// insert into an empty list
			LeftEnd = RightEnd = y;
			y->left = y->right = 0;
		}
		LeftEnd = y;
	}
	
	return *this;
}

template<class T>
void DoubleChain<T>::Output(ostream& out) const
{// Insert the chain elements into the stream out.
	for (DoubleNode<T> *curr = LeftEnd;
	curr; curr = curr->right)
		out << curr->data << "  ";
	out << endl;
}

// overload <<
template <class T>
ostream& operator<<(ostream& out, const DoubleChain<T>& x)
{
	x.Output(out); 
	return out;
}

#endif