list.hpp

实现多项式表达式的运算器利用栈实现表达式计算器的模板类；用表达式计算器类和多项式类实现多项式表达式的计算器

#include<iostream.h>
#include"listnode.hpp"

#ifndef LIST_H
#define LIST_H
//////////////////////////////////////////////////////////////////////////
//有序单链表类定义开始,实现与课本基本一样，不作多余注释
//////////////////////////////////////////////////////////////////////////
template<class Type>
class List
{
public:	
	List();//构造函数
	List(const List<Type>& list);//拷贝构造函数
	~List();      //析构函数
	List<Type> operator =(const List<Type>& list);
	void Clear();//将链表置为空表
	int Length() const;//计算链表中的元素个数
	ListNode<Type>* Find(Type& value);//在单链表中搜索含数据value的结点,搜索成功则返回该节点的地址,否则返回NULL
	ListNode<Type>* Find(int i);//定位函数,函数返回链表中的第i个元素的地址
	bool Insert(Type& value);//将新元素value插入在链表中,链表元素按有小到大的顺序排列
	Type* Remove(int i);//将链表中的第i个元素删去
	Type* Get(int i);//取出链表中第i个元素
private:
	friend class ListNode<Type>;
	friend class ListIterator<Type>;
	ListNode<Type> *first,*last;//链表的表头表尾指针
};
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type>::List()
{
	last=first=new ListNode<Type>();
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type>::List(const List<Type>& list)
{
	first=new ListNode<Type>();
	ListNode<Type> *p=list.first->link;
	while(p!=NULL)
	{
		Insert(p->data);
		p=p->link;
	}
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type>::~List()
{
	Clear();
	delete first;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
List<Type> List<Type>::operator =(const List<Type>&list)
{
	Clear();
	ListNode<Type>* p=list.first->link;
	while(p!=NULL)
	{
		Insert(p->data);
		p=p->link;
	}
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
void List<Type>::Clear()
{
	ListNode<Type>* q;
	while(first->link!=NULL)
	{
		q=first->link;
		first->link=q->link;
		delete q;
	}
	last=first;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
int List<Type>::Length()const
{
	ListNode<Type>* p=first->link;
	int count=0;
	while(p!=NULL)
	{
		p=p->link;
		count++;
	}
	return count;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
ListNode<Type>* List<Type>::Find(Type& value)
{
	ListNode<Type>* p=first->link;
	while(p!=NULL && p->data!=value)
		p=p->link;
	return p;
}
//////////////////////////////////////////////////////////////////////////	
template<class Type>
ListNode<Type>* List<Type>::Find(int i)
{
	if(i<-1)
		return NULL;
	if(i==-1)
		return first;
	ListNode<Type>* p=first->link;
	int j=0;
	while(p!=NULL && j<i)
	{
		p=p->link;
		j++;
	}
	return p;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
bool List<Type>::Insert(Type& value)
{
	if(first->link == NULL)
	{
		first->link =new ListNode<Type>(value,NULL);
		last=first->link;
	}
	else
	{
		ListNode<Type> *previous=first,*current=first->link;
		while(current!=NULL && current->data < value)
		{
			current=current->link;
			previous=previous->link;
		}
		ListNode<Type>* newnode=new ListNode<Type>(value,current);
		if(current==NULL)
			last=newnode;
		previous->link=newnode;
	}
	return true;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
Type* List<Type>::Remove(int i)
{
	ListNode<Type>* p=Find(i-1),*q;
	if(p==NULL || p->link==NULL)
		return NULL;
	q=p->link;
	p->link=q->link;
	Type value=new Type(q->data);
	if(q==last)
		last=p;
	delete q;
	return &value;
}
//////////////////////////////////////////////////////////////////////////
template<class Type>
Type* List<Type>::Get(int i)
{
	ListNode<Type>* p=Find(i);
	if(p==NULL || p==first)//参数不合理或欲取的元素是头节点
		return NULL;
	else 
		return &p->data;
}
//////////////////////////////////////////////////////////////////////////
//有序单链表类定义结束
//////////////////////////////////////////////////////////////////////////
#endif