list.h

银行家算法

#ifndef List_H
#define List_H
#ifndef TURE
#define TURE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
typedef int BOOL;
#include "Node.h"
template <class Type> class List //单链表定义
{
//基本上无参数的成员函数操作的都是当前节点，即current指的节点
//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点
public:
	List() 
	{ 
		first=current=last=new Node<Type>; 
		prior=NULL; 
	}
	~List() 
	{
		MakeEmpty(); 
		delete first; 
	}
	void MakeEmpty() //置空表
	{
		Node<Type> *q;
		while (first->link != NULL)
		{
			q = first->link;
			first->link = q->link;
			delete q;
		}
		Initialize();
	}
	BOOL IsEmpty()
	{
		if (first->link == NULL)
		{
			Initialize();
			return TURE;
		}
		else return FALSE;
	}
	int Length() const //计算带表头节点的单链表长度
	{
		Node<Type> *p = first->link;
		int count = 0;
		while (p != NULL)
		{
			p = p->link;
			count++;
		}
		return count;
	}
	Type *Get()//返回当前节点的数据域的地址
	{
		if (current != NULL) 
			return &current->data;
		else return NULL;
	}
	BOOL Put(Type const &value)//改变当前节点的data，使其为value
	{
		if (current != NULL)
		{
			current->data = value;
			return TURE;
		}
		else return FALSE;
	}
	Type *GetNext()//返回当前节点的下一个节点的数据域的地址，不改变current
	{
		if (current->link != NULL) return &current->link->data;
		else return NULL;
	}
	Type *Next()//移动current到下一个节点，返回节点数据域的地址
	{
		if (current != NULL && current->link != NULL)
		{
			prior=current;
			current=current->link;
            return &current->data;
		}
		else
		{
			return NULL;
		}
	}
	void Insert(const Type &value)//在当前节点的后面插入节点，不改变current
	{
		Node<Type> *p = new Node<Type>(value, current->link);
		current->link = p;
	}
	BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior
	{
		Node<Type> *p = new Node<Type>(value);
		if (prior != NULL)
		{
			p->link = current;
			prior->link = p;
			prior = p;
            return TURE;
		}
		else return FALSE;
	}
	BOOL Locate(int i)//移动current到第i个节点
	{
		if (i <= -1) return FALSE;
		current = first->link;
		for (int j = 0; current != NULL && j < i; j++, current = current->link)
			prior = current;
		if (current != NULL) 
			return TURE;
		else return FALSE;
	}
	void First()//移动current到表头
	{
		current = first;
		prior = NULL;
	}
	void End()//移动current到表尾
	{
		if (last->link != NULL)
		{
			for ( ;current->link != NULL; current = current->link)
				prior = current;
			last = current;
		}
		current = last;
	}
	BOOL Find(const Type &value)//移动current到数据等于value的节点
	{
		if (IsEmpty()) return FALSE;
		for (current = first->link, prior = first; current != NULL && current->data != value;
		current = current->link)
			prior = current;
		if (current != NULL) return TURE;
		else return FALSE;
	}
	BOOL Remove()
		//删除当前节点，current指向下一个节点，如果current在表尾，执行后current = NULL
	{
		if (current != NULL && prior != NULL)
		{
			Node<Type> *p = current;
			prior->link = p->link;
			current = p->link;
			delete p;
			return TURE;
		}
		else return FALSE;
	}
	BOOL RemoveAfter()//删除当前节点的下一个节点，不改变current
	{
		if (current->link != NULL && current != NULL)
		{
			Node<Type> *p = current->link;
			current->link = p->link;
			delete p;
			return TURE;
		}
		else return FALSE;
	}
	friend ostream & operator << (ostream & strm, List<Type> &l)
	{
		l.First();
		while (l.current->link != NULL) strm << *l.Next() << " " ;
		strm << endl;
		l.First();
		return strm;
	}
protected:
	/*主要是为了高效的入队算法所添加的。因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些，否则不正确。但是last除了在队列中非常有用外，其他的时候很少用到，没有必要为了这个用途而降低Insert()，Remove()的效率所以把这部分放到protected，实际上主要是为了给队列继承*/ 
	void LastInsert(const Type &value)
	{
		Node<Type> *p = new Node<Type>(value, last->link);
		last->link = p;
		last = p;
	}
	void Initialize()//当表为空表时使指针复位
	{
		current = last = first;
		prior = NULL;
	}
	//这部分函数返回类型为Node<Type>指针,是扩展List功能的接口
	Node<Type> *pGet()
	{
		return current;
	}
	Node<Type> *pNext()
	{
		prior = current;
		current = current->link;
		return current;
	}
	Node<Type> *pGetNext()
	{
		return current->link;
	}
	Node<Type> *pGetFirst()
	{
		return first;
	}
	Node<Type> *pGetLast()
	{
		return last;
	}
	Node<Type> *pGetPrior()
	{
		return prior;
	}
	void PutLast(Node<Type> *p)
	{
		last = p;
	}
	//这部分插入删除函数不建立或删除节点，是原位操作的接口
	void Insert(Node<Type> *p)
	{
		p->link = current->link;
		current->link = p;
	}
	void InsertBefore(Node<Type> *p)
	{
		p->link = current;
		prior->link = p;
		prior = p;
	}
	void LastInsert(Node<Type> *p)
	{
		p->link = NULL;
		last->link = p;
		last = p;
	}
	Node<Type> *pRemove()
	{
		if (current != NULL && prior != NULL)
		{
			Node<Type> *p = current;
			prior->link = current->link;
			current = current->link;
			return p;
		}
		else return NULL;
	}
	Node<Type> *pRemoveAfter()
	{
		if (current->link != NULL && current != NULL)
		{
			Node<Type> *p = current->link;
			current->link = current->link->link;
			return p;
		}
		else return NULL;
	}
private:
	List(const List<Type> &l);
	Node<Type> *first, *current, *prior, *last;
	//尽量不要使用last，如果非要使用先用End()使指针last正确
};
#endif 
//　　【说明】我将原书的游标类Iterator的功能放在了链表类中，屏蔽掉了返回值为Node以及Node*类型的接口，这样的链表简单、实用，扩充性能也很好。

//　　在完成书后作业的时候，我发现了原书做法的好处，也就是我的做法的不足。如果使用原书的定义，在完成一个功能时，只需要写出对应的函数实现。而在我的定义中，必须先派生一个类，然后把这个功能作为成员或者友元。但是这种比较并不说明书上的定义比我的要合理。首先，使用到原位操作的情况并不多，书后作业只是一种特殊情况；换句话说，书上的定义只是对完成书后作业更实用些。其次，在使用到链表的时候，通常只会用到插入、删除、取数据、搜索等很少的几个功能，我的定义足够用了。而在完成一个软件时，对链表的扩充功能在设计阶段就很清晰了，这时可以派生一个新类在整个软件中使用，对整体的规划更为有利。而对于单个链表的操作，把它作为成员函数更好理解一些。也就是说我的定义灵活性不差。

//单链表应用

//　　有人曾经建议最好把链表和链表位置这两个分开，C++标准库是这么做的；但对于初学者来说，一个类总比两个类好操作。我不清楚在书中这部分的程序究竟调没调试，但这种语句我是绝对看不懂的：

//ListNode<Term> *pa, *pb, *pc, *p;
//ListIterator<Term> Aiter(ah.poly);
//ListIterator<Term> Biter(ah.poly);
//pa = pc = Aiter.First(); pb = p = Biter.First();
//………………………..
//pa->coef = pa->coef + pb->coef;
//p = pb; pb = Biter.Next(); delete p;