linkedlist.h

学生信息管理系统：本程序可以实现输入

#ifndef LINKED_LIST_CLASS
#define LINKED_LIST_CLASS

#include <iostream.h>
#include <iomanip.h>
#include <assert.h>

#include "ListNode.h"

enum SortOrder{Ascending, Descending};

template <class Type>
class LinkedList
{
private:
	ListNode<Type> *header, *tail;

	ListNode<Type>* GetNode(const Type& item, 
		ListNode<Type>* next = NULL);

public:
	LinkedList();
	LinkedList(const LinkedList<Type>& list);
	~LinkedList();

	void ClearList();
	void CopyList(const LinkedList<Type>& list);
	LinkedList<Type>& operator = (const LinkedList<Type>& list);
	
	void Print() const;
	bool IsEmpty() const;
	int  Length() const;
	
	ListNode<Type>* Max() const;
	ListNode<Type>* Min() const;
	
	// need !=, return current pointer
	ListNode<Type>* IsMemberOf(const Type& item, 
		                       ListNode<Type>* & prevPtr) const;
	ListNode<Type>* Locate(int pos, 
						   ListNode<Type>* & prevPtr) const;
	
	Type& DataOfNode(int i);
	Type& operator [] (int i);

	void InsertAt(const Type& item, int i);
	void InsertFront(const Type& item);
	void InsertRear(const Type& item);
	void InsertOrder(const Type& item);

	bool DeleteFront(Type& item);
	bool DeleteNode(const Type& item);
	bool DeleteAt(int pos, Type& item);
	bool DeleteMax(Type& item);
	bool DeleteMin(Type& item);

	void Sort(int sortorde = 0);

	friend ostream& operator << (ostream& os, 
		                         const LinkedList<Type>& item);
	friend istream& operator >> (istream& is, 
		                         LinkedList<Type>& item);

	friend ofstream& operator << (ofstream& ofs, 
		                          const LinkedList<Type>& item);
	friend ifstream& operator >> (ifstream& ifs, 
		                          LinkedList<Type>& item);
};


template <class Type>
LinkedList<Type>::LinkedList():header(NULL), tail(NULL)
{}

template <class Type>
LinkedList<Type>::LinkedList(const LinkedList<Type>& list)
{
	if (this != &list) {
		this->header = NULL;
		this->CopyList(list);
	}
}

template <class Type>
LinkedList<Type>::~LinkedList()
{
	ClearList();
}

template <class Type>
ListNode<Type>* LinkedList<Type>::GetNode(const Type& item, 
								   ListNode<Type>* next)
{
	ListNode<Type>* newNode = new ListNode<Type>(item, next);
	assert(newNode != NULL);

	return newNode;
}

template <class Type>
void LinkedList<Type>::CopyList(const LinkedList<Type>& list)
{
	if (this != &list) {
		ListNode<Type> *tempPtr = list.header;
			
		while (tempPtr != NULL) {
			this->InsertRear(tempPtr->data);
			tempPtr = tempPtr->link;
		}
	}
}

// clear the list, set header and tail to NULL
template <class Type>
void LinkedList<Type>::ClearList()
{
	ListNode<Type>* currPtr = this->header;

	while (currPtr != NULL) {
		this->header = currPtr->link;
		delete currPtr;
		currPtr = this->header;
	}
	this->tail = NULL;
}

template <class Type>
LinkedList<Type>& LinkedList<Type>::operator = (const LinkedList<Type>& list)
{
	if (this != &list) {
		this->ClearList();
		this->CopyList(list);
	}	
	return *this;
}

template <class Type>
int LinkedList<Type>::Length() const
{
	ListNode<Type>* tempPtr = header;
	int size = 0;

	while (tempPtr != NULL) {
		size++;
		tempPtr = tempPtr->link;
	}
	return size;
}

template <class Type>
void LinkedList<Type>::Print() const
{
	ListNode<Type>* currPtr = header;

	while (currPtr != NULL) {
		cout << setw(20) << "current node: " << currPtr << endl
		     << setw(20) << "data: " << currPtr->data << endl;
		currPtr = currPtr->link;
		cout << setw(20) << "next node: " << currPtr << endl;
		cout << endl;
	}
	cout << endl;
}

template <class Type>
bool LinkedList<Type>::IsEmpty() const
{
	return header == NULL;
}

/**********************************************************
 * 1. currPtr == NULL, prevPtr == NULL:
 *     an empty list!
 *
 * 2. currPtr != NULL, prevPtr == NULL:
 *     at the head of the list!
 *
 * 3. currPtr == NULL, prevPtr != NULL:
 *     not in the list!
 *
 * 4. currPtr != NULL, prevPtr != NULL:
 *     at a normal position(at rear or at middle)!
 *
 *********************************************************/
template <class Type>
ListNode<Type>* LinkedList<Type>::IsMemberOf(const Type& item,
								ListNode<Type>* & prevPtr) const
{
	ListNode<Type> *currPtr = this->header;
	prevPtr = NULL;
	while (currPtr != NULL && currPtr->data != item) {
		prevPtr = currPtr;
		currPtr = currPtr->link;
	}
	return currPtr;
}

/**********************************************************
 * 1. currPtr == NULL, prevPtr == NULL:
 *     an empty list!
 *
 * 2. currPtr != NULL, prevPtr == NULL:
 *     at the head of the list!
 *
 * 3. currPtr == NULL, prevPtr != NULL:
 *     pos too big!
 *
 * 4. currPtr != NULL, prevPtr != NULL:
 *     at a normal position(at rear or at middle)!
 *
 *********************************************************/
template <class Type>
ListNode<Type>* LinkedList<Type>::Locate(int pos, 
							ListNode<Type>* &prevPtr) const
{	
	int j = 0;
	ListNode<Type>* currPtr = this->header;
	prevPtr = NULL;

	while (currPtr != NULL && j < pos) {
		j++;
		prevPtr = currPtr;
		currPtr = currPtr->link;
	}
	return currPtr;
}

template <class Type>
void LinkedList<Type>::InsertRear(const Type& item)
{
	ListNode<Type>* newNode = this->GetNode(item);
	
	if (this->IsEmpty()) // empty list
		this->header = this->tail = newNode;
	else {// at rear
		tail->link = newNode;
		tail = newNode;
	}
}

template <class Type>
void LinkedList<Type>::InsertFront(const Type& item)
{	
	ListNode<Type>* newNode = this->GetNode(item);

	if (this->IsEmpty())
		this->header = this->tail = newNode;
	else {
		newNode->link = this->header;
		this->header = newNode;
	}	
}

template <class Type>
void LinkedList<Type>::InsertAt(const Type& item, int pos)
{
	ListNode<Type> *newNode = this->GetNode(item);

	ListNode<Type> *currPtr, *prevPtr;
	currPtr = this->Locate(pos, prevPtr);
	
	if (prevPtr == NULL && currPtr == NULL)
		this->header = this->tail = newNode;
	else if (prevPtr == NULL && currPtr != NULL) {// at head
		newNode->link = this->header;
		this->header = newNode;
	}
	else if (prevPtr != NULL && currPtr != NULL) {// at middle
		prevPtr->link = newNode;
		newNode->link = currPtr;
	}
	else {// prevPtr != NULL && currPtr == NULL // at rear
		prevPtr->link = newNode;
		this->tail = newNode;
	}
}

template <class Type>
void LinkedList<Type>::InsertOrder(const Type& item)
{
	ListNode<Type>* newNode = this->GetNode(item);

	if (this->IsEmpty()) {
		this->header = this->tail = newNode;
		return;
	}

	ListNode<Type> *currPtr = this->header, *prevPtr = NULL;
	while (currPtr != NULL && currPtr->data < item) {
		prevPtr = currPtr;
		currPtr = currPtr->link;
	}

	if (prevPtr == NULL) { // insert at head
		newNode->link = this->header;
		this->header = newNode;
	}
	else if (currPtr == NULL) { // insert at rear;
		prevPtr->link = newNode;
		tail = newNode;
	}
	else { // insert at middle;
		prevPtr->link = newNode;
		newNode->link = currPtr;
	}
}

/**********************************************************
 * retvalue: false if an empty list
 *
 *********************************************************/
template <class Type>
bool LinkedList<Type>::DeleteFront(Type& item)
{
	ListNode<Type>* tempPtr = this->header;
	
	if (tempPtr == NULL)
		return false;
	
	this->header = tempPtr->link;
	if (this->header == NULL) // the only node deleted.
		this->tail = NULL;

	item = tempPtr->data;
	delete tempPtr;

	return true;
}

template <class Type>
bool LinkedList<Type>::DeleteNode(const Type& item)
{
	if (this->IsEmpty())
		return false;

	ListNode<Type> *currPtr, *prevPtr;
	currPtr = this->IsMemberOf(item, prevPtr);
	
	if (currPtr == NULL) // not in
		return false;	
	else if (prevPtr == NULL) { // at header
		this->header = currPtr->link;
		if (this->header == NULL) // the only node deleted.
			this->tail = NULL;
	}
	else { // at middle or at rear
		prevPtr->link = currPtr->link;
		if (prevPtr->link == NULL)
			tail = prevPtr;
	}
	delete currPtr;
	return true;
}

template <class Type>
bool LinkedList<Type>::DeleteAt(int pos, Type& item)
{
	if (this->IsEmpty())		
		return false;

	int i = 0;
	ListNode<Type> *currPtr = this->header, *prevPtr = NULL;
	while (currPtr != NULL && i < pos) {
		i++;
		prevPtr = currPtr;
		currPtr = currPtr->link;
	}

	currPtr = Locate(pos, prevPtr);

	if (currPtr == NULL) // pos too big		
		return false;
	else if (prevPtr == NULL) {	// at head
		this->header = currPtr->link;
		if (this->header == NULL) // the only node been deleted.
			this->tail = NULL;
	}
	else { // at pos
		prevPtr->link = currPtr->link;
		if (prevPtr->link == NULL)
			tail = prevPtr;
	}
	item = currPtr->data;
	delete currPtr;
	return true;
}

template <class Type>
bool LinkedList<Type>::DeleteMax(Type& item)
{
	ListNode<Type>* tempPtr = this->Max();
	if (tempPtr == NULL)
		return false;

	item = tempPtr->data;
	return this->DeleteNode(item);
}

template <class Type>
bool LinkedList<Type>::DeleteMin(Type& item)
{
	ListNode<Type>* tempPtr = this->Min();
	if (tempPtr == NULL)
		return false;

	item = tempPtr->data;
	return this->DeleteNode(item);
}

template <class Type>
Type& LinkedList<Type>::DataOfNode(int pos)
{
	assert (pos >= 0 && pos < this->Length());

	ListNode<Type> *currPtr = NULL, *prevPtr = NULL;
	assert ((currPtr = Locate(pos, prevPtr)) != NULL);

	return currPtr->data;
}

template <class Type>
Type& LinkedList<Type>::operator [] (int i)
{
	return DataOfNode(i);
}

template <class Type>
ListNode<Type>* LinkedList<Type>::Max() const
{
	if (this->IsEmpty())
		return NULL;

	ListNode<Type> *currPtr = header->link,
		*maxPtr = header;
	while (currPtr != NULL) {
		if (maxPtr->data < currPtr->data)
			maxPtr = currPtr;
		currPtr = currPtr->link;
	}
	return maxPtr;
}

template <class Type>
ListNode<Type>* LinkedList<Type>::Min() const
{
	if (this->IsEmpty())
		return NULL;

	ListNode<Type> *currPtr = header->link,
		*minPtr = header;
	while (currPtr != NULL) {
		if (minPtr->data > currPtr->data)
			minPtr = currPtr;
		currPtr = currPtr->link;
	}
	return minPtr;
}

template <class Type>
void LinkedList<Type>::Sort(int sortorder)
{
	ListNode<Type>* pivot = this->header;
	while (pivot != NULL) {
		ListNode<Type>* currPtr = pivot->link;
		while (currPtr != NULL) {
			if (sortorder == 0) {
				if (pivot->data > currPtr->data) {
					Type item = pivot->data;
					pivot->data = currPtr->data;
					currPtr->data = item;
				}
			}

			if (sortorder == 1) {
				if (pivot->data < currPtr->data) {
					Type item = pivot->data;
					pivot->data = currPtr->data;
					currPtr->data = item;
				}
			}

			currPtr = currPtr->link;
		}
		pivot = pivot->link;
	}
}

template <class Type>
istream& operator >> (istream& is, LinkedList<Type>& list)
{
	list.ClearList();

	Type item;
	while (!is.eof()) {
		is >> item;
		is.ignore(80, '\n');
		list.InsertRear(item);
	}
	return is;
}

template <class Type>
ifstream& operator >> (ifstream& ifs, LinkedList<Type>& list)
{
	list.ClearList();

	int n;
	ifs >> n;
	ifs.ignore(80, '\n');

	Type item;
	while (n--) {
		ifs >> item;
		ifs.ignore(80, '\n');
		list.InsertRear(item);
	}
	return ifs;
}

template <class Type>
ostream& operator << (ostream& os, const LinkedList<Type>& list)
{
	ListNode<Type>* tempPtr = list.header;
	while (tempPtr != NULL) {
		
		os << setw(20) << "current node: " << tempPtr << endl
		   << setw(20) << "data: " << tempPtr->data	<< endl
		   << setw(20) << "next node: " << tempPtr->link << endl;

		os << endl;

		tempPtr = tempPtr->link;		
	}
	return os;
}

template <class Type>
ofstream& operator << (ofstream& ofs, const LinkedList<Type>& list)
{
    ofs<<"************************************"<<endl;
	ofs << list.Length() << endl;
    
	ListNode<Type>* tempPtr = list.header;
	while (tempPtr != NULL) {
		ofs << *tempPtr << endl;
		tempPtr = tempPtr->link;
	}
	return ofs;
}

#endif // LINKED_LIST_CLASS