linkedlist.h

光盘出租管理系统

#ifndef H_linkedList
#define H_linkedList
#include<iostream.h>
template<class Type>
struct nodeType
{
	Type info;
	nodeType<Type>* link;
};

template<class Type>
class linkedListType
{
public:
	const linkedListType<Type>& operator = (const linkedListType<Type>&);
	void initializeList();                             //初始化成空链表
	bool isEmptyList();                                //检查链表是否为空
	bool isFullList();                                 //“没用的”！！
	void print();                                      //打印整个链表的内容
	void print(ostream& object);
	int length();                                      //得到链表中的节点数
	void destroyList();                                //销毁链表
	void retrieveFirst(Type& firstElement);            //获取第一个指针的数据
	void search(const Type& searchItem);               //搜索一个节点
	void insertFirst(const Type& newItem);             //插入一个节点到表头
	void insertLast(const Type& newItem);              //插入一个节点到表末
	void deleteNode(const Type& deleteItem);           //删除一个节点
	linkedListType();
	linkedListType(const linkedListType<Type>& otherList);
	nodeType<Type>* getfirstnode();
	~linkedListType();
protected:
	nodeType<Type>* first;
	nodeType<Type>* last;
};


template<class Type>                                   //
bool linkedListType<Type>::isEmptyList()
{
	return(first==NULL);
}

template<class Type>
bool linkedListType<Type>::isFullList()                //可以不要的，没作用
{                                                      //
	return false;                                      //
}													   //

template<class Type>
linkedListType<Type>::linkedListType()                 //默认构造函数
{
	first=NULL;
	last=NULL;
}

template<class Type>                                   //拷贝构造函数
linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList)
{
	nodeType<Type>* newNode;
	nodeType<Type>* current;
	if(otherList.first ==NULL)                         //预防空的对象
	{
		first = NULL;
		last = NULL;
	}
	else
	{
		current = otherList.first;
		first = new nodeType<Type>;
		first->info = current->info;
		first->link = NULL;

		last = first;
		current = current->link;
		
		while(current!=NULL)
		{
			newNode = new nodeType<Type>;
			newnode->info = current->info;
			newNode->link = NULL;
			
			last->link = newNode;
			last = newNode;

			current = current->link;
		}
	}
}



template<class Type>                                   //销毁链表
void linkedListType<Type>::destroyList()
{
	nodeType<Type>* temp;
	while(first!=NULL)
	{
		temp=first;
		first=first->link;
		delete temp;
	}
	last=NULL;
}

template<class Type>
void linkedListType<Type>::initializeList()
{
	destoryList();                                     //实际上是重新使链表为空状态
}

template<class Type>
void linkedListType<Type>::print()                     //打印所以节点
{
	nodeType<Type>* current;                           //建立一个遍历链表的指针
	current=first;
	while(current!=NULL)
	{
		cout<<current->info<<" ";
		current=current->link;
	}
}


template<class Type>
void linkedListType<Type>::print(ostream& object)                     //重载
{
	nodeType<Type>* current;                           
	current=first;
	while(current!=NULL)
	{
		object<<current->info<<" ";
		current=current->link;
	}
}


 
template<class Type>                                   //链表长度
int linkedListType<Type>::length()
{
	int count=0;
	nodeType<Type>* current;
	current=first;
	while (current!=NULL)
	{
		count++;
		current=current->link;
	}
	return count;
}


template<class Type>                                   //获取第一个指针的数据     
void linkedListType<Type>::retrieveFirst(Type& firstElement)
{
	firstElement=first->info;
}

template<class Type>                                   //搜索链表
void linkedListType<Type>::search(const Type& item)
{
	nodeType<Type>* current;
	bool found;
	
	if(first==NULL)
		cout<<"Cannot search an empty list."<<endl;
	else
	{
		current=first;
		while(!found && current != NULL)
			if(current->info ==item)
				found = ture;
			else
				current = current->link;

			if(found)
				cout<<"Item is found in the list."<<endl;
			else
				cout<<"Item is not in the list."<<endl;
	}
}

template<class Type>                                   //插入节点到链表头
void linkedListType<Type>::insertFirst(const Type& newItem)
{
	nodeType<Type>* newNode;
	
	newNode = new nodeType<Type>;
	newNode->info = newItem;
	newNode->link = first;
	first = newNode;

	if(last == NULL)
		last = newNode;
	//delete newNode  是否要添加 删除呢？？？
}

template<class Type>                                  //插入节点到链表末尾              
void linkedListType<Type>::insertLast(const Type& newItem)
{
	nodeType<Type>* newNode;
	
	newNode = new nodeType<Type>;
	newNode->info = newItem;
	newNode->link = NULL;
	
	if(first == NULL)
	{
		first = newNode;
		last = newNode;
	}
	else
	{
		last->link =newNode;
		last=newNode;
	}
}


template<class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)   //删除一个节点
{
	nodeType<Type>* current;                           //指向当前节点的指针    
	nodeType<Type>* trailCurrent;                      //指向当前节点的前一个指针
	bool found;

	if(first == NULL)
		cout<<"Cannot delete from an empty list.\n";
	else
	{
		if(first->info ==deleteItem)
		{
			current = first;
			first = first->link;
			if(first ==NULL)
				last = NULL;
			delete current;
		}
		else
		{
			found = false;
			trailCurrent = first;
			current = first->link;
			while((!found) && (current !=NULL))
			{
				if(current->info !=deleteItem)
				{
					trailCurrent = current;
					current = current->link;
				}
				else
					found = true;
			}
			if(found)
			{
				trailCurrent->link = current->link;
				if(last == current)                    //last->info = deleteItem
					last = trailCurrent;
				delete current;
				cout<<"已经成功删除!"<<endl;
			}
			else
				cout<<"Item to be deleted is not in the list."<<endl;
		}                                              //end else
	}                                                  //end else
}

template<class Type>                                   //析构函数
linkedListType<Type>::~linkedListType()
{
	nodeType<Type>* temp;
	while(first !=NULL)
	{
		temp =first;
		first = first->link;
		delete temp;
	}
	last = NULL;
}

template<class Type>                                   
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
{
	nodeType<Type>* newNode;
	nodeType<Type>* current;
	if(this != &otherList)                           //预防自己拷贝自己
	{
		if(otherList.first != NULL)
			destroyList();

		if(otherList.first == NULL)                  //拷贝对象为空
		{
			first = NULL;
			last = NULL;
		}
		else                                         //拷贝对象不为空
		{
			current = otherList.first;               
			first = new nodeType<Type>;
			first->info = current->info;
			first->link = NULL;
			
			last = first;
			current = current->link;

			while(current != NULL)
			{
				newNode = new nodeType<Type>;
				newNode->info = current->info;
				newNode->link = NULL;
			
			    last->link = newNode;
				last = newNode;

			    current = current->link;
			}
		}
	}

	return *this;
}

template<class Type> 
nodeType<Type>* linkedListType<Type>::getfirstnode()
{
	return first;
}
#endif