linklist.h

数据结构的一些教程....比较适于初学者

//在此定义单链表类LinkList,可作为其它线性链表类的基类,它不带头结点
#ifndef LINKLIST_H
#define LINKLIST_H
#include "Node.h"

template<class T> class LinkList;  //向前引用声明

template<class T>
class ListNode:public Node<T>//定义链表结点类(模板)
{ 
	friend class LinkList<T>;   //声明友元类
protected:
    ListNode<T>* next;
public:
	ListNode( ListNode<T> *ptrNext=NULL); //用于构造头结点
    ListNode(const T& item, ListNode<T> *ptrNext=NULL); //用于构造非头结点
	~ListNode()	{ };
};

template<class T>
ListNode<T>::ListNode( ListNode<T> *ptrNext):Node<T>()
{
	next=ptrNext;
}

template<class T>
ListNode<T>::ListNode( const T& item,ListNode<T> *ptrNext)
:Node<T>(item)
{
	next=ptrNext;
}
	
  

//链表类LinkList的定义的定义与实现
template<class T> class LinkList 
{
protected:
	ListNode<T> *head, *tail;//指向头结点、尾结点和当前结点
	int size;     //表的长度：包含的元素个数
public:
	LinkList()           //构造一个空链表
	{
		head=NULL; tail=NULL;
		size=0;
	}

	~LinkList();
	LinkList(const LinkList<T> &linkedList);   //拷贝构造函数
	LinkList& operator=(const LinkList<T> &linkedList);//赋值操作符重载

	ListNode<T> const* Head() const
	{  return head;  }
    ListNode<T> const* Tail() const
	{  return tail;   }
	int ListSize() const
	{  return size;  }

	bool ListEmpty() const
	{  return size==0;  }
	T GetData(int pos)const;        //读第pos元素的data值
	T const& First() const;    //读第一个元素的data值
    T const& Last() const;     //读最后一个元素的data值

	void Prepend(T const&);  //在第一个元素前插入一新元素
	void Append(T const&);   //在最后一个元素后插入一新元素
	T Delete(T const&);   //删除一个指定元素
	void ClearList();         //清空链表
	void Insert(const T& item, int pos);  //在第pos个元素前插入新元素
	void InsertAfter(const T& item, int pos);//在第pos个元素后插入新元素
};
//LinkList类成员函数的实现
template<class T>
LinkList<T>::LinkList(const LinkList<T> &linkedList)
{//拷贝构造函数
	head=0; tail=0;
	ListNode<T> *p;
    //把linkedList的元素逐个拷贝到本对象
	for(p=linkedList.head; p!=0; p=p->next)
		Append(p->data);
}

template<class T>
LinkList<T>::~LinkList()
{
	ListNode<T> *p=head,*q=0;
	while(size!=0)
	{ //从头到尾逐个删除各个元素
		q=p;
		p=p->next;
		delete q;
		size--;
	}
	head=0; 
	tail=0;
}

template<class T>
LinkList<T>& LinkList<T>::operator=(const LinkList<T> &linkedList)
{//赋值操作符'='重载
	ClearList();        //清空本对象(被赋值对象)
    ListNode<T> *p;
	for(p=linkedList.head; p!=0; p=p->next)
		Append(p->data);
	return *this;
}

template<class T>
T LinkList<T>::GetData(int pos) const
{   //读第pos个元素的data值
    if(size==0)	
	{
		cerr<<"表是空的!"<<endl;
		exit(1);
	}
	ListNode<T>* p=head;
	for(int i=0; i<pos; i++)p=p->next;
	return p->data;
}

template<class T>
T const& LinkList<T>::First() const
{//读第一个元素的data值
	if(size==0)	
	{
		cerr<<"表是空的!"<<endl;
		exit(1);
	}
	return head->data;
}

template<class T>
T const& LinkList<T>::Last() const
{//读最后一个元素的data值
   	if(size==0)	
	{
        cerr<<"表是空的!"<<endl;
		exit(1);
	}
	return tail->data;
}

template<class T>
void LinkList<T>::Append(T const& item)
{//从表尾添加一个元素
	ListNode<T>* const temp=new ListNode<T>(item,0);
	if(head==0) head=temp;
	else tail->next=temp;
	tail=temp;
	size++;
}

template<class T>
void LinkList<T>::Prepend(T const& item)
{//从表头添加一个元素
	ListNode<T>* const temp=new ListNode<T>(item,head);
	if(head==0) tail=temp;
	head=temp;
	size++;
}

template<class T>
T LinkList<T>::Delete(const T& item)
{//删除指定元素
	ListNode<T>* p=head,*q=0;

	while(p!=0 && p->data!=item)
	{	q=p; p=p->next;  }
	if(p==0)
	{
		cerr<<"表是空的或表中无此元素!"<<endl;
		exit(1);
	}
	T data=p->data;
	if(p==head) head=p->next;
	else q->next=p->next;
	if(p==tail) tail=q;
	delete p;
	size--;
	return data;
}

template<class T>
void LinkList<T>::ClearList()
{//清空表
	
	while(size!=0)
	{
        ListNode<T>* temp=head;
		head=head->next;
		delete temp;
		size--;
	}
	head=0;  tail=0;
}

template<class T>
void LinkList<T>::Insert(const T& item, int pos)
{//在指定位置pos前插入一个新元素item
	if(pos<0||pos>size)
	{
		cerr<<"参数pos错!"<<endl;
		exit(1);
	}
	ListNode<T> *p=head,q=0;
	for(int i=0; i<pos; i++) 
	{ q=p; p=p->next;  }
	if(p==head)	Prepend(item);
	else 
	{
		ListNode<T>* temp=new ListNode<T>(item,p);
		q->next=temp;
	}
	size++;
}

template<class T>
void LinkList<T>::InsertAfter(const T& item,int pos)
{//在指定位置pos之后插入一个新元素item
	if(pos<0||pos>size)
	{
		cerr<<"参数pos错!"<<endl;
		exit(1);
	}
	ListNode<T> *p=head,q=0;
	for(int i=0; i<pos; i++) p=p->next; 
    ListNode<T>* temp=new ListNode<T>(item,p->next);
	p->next=temp;
	size++;
}
#endif