線性表鏈式存儲C++實現

#include"LsList.h"

#include
#include
#include
using  namespace std;
#pragma once
template
class LsList
{
public:
	class LNode{
	public:
  	T data;//數據域
	LNode * next;//指針域
	~LNode()
	{
	}
	};
public://定義迭代器類型，用於高效遍歷
	//由於是單向鏈表所以該迭代器類型只能是“前向迭代器”
	class Iter{//迭代器類型
	public :
		Iter(LNode * t)
		{
	      mp = t;
		}
	//重載迭代器++操作符
	Iter & operator++( )//前綴自增操作符重載
	{
	 LNode *  p = mp;
	 mp = mp->next;
	 return *this;
	}
	Iter & operator++(int)//後綴自增操作符重載
	{
	 LNode *  p = mp;
	 mp = mp->next;
	 return *this;
	}

	//重載迭代器*操作符
	T & operator*()
	{
	  return (*mp).data;
	}
	//重載迭代器==操作符
	bool  operator==(Iter & iter)
	{
		return mp==iter.mp;
	}
	//重載迭代器!=操作符
	bool  operator!=(Iter & iter)
	{
		return mp!=iter.mp;
	}

	private :
	LNode *  mp;
	};

public:
	typedef T ElemType;//定義元素類型
	LsList(void)//建立一個空的鏈式線性表
	{
		size = 0;
		head.next = 0;
		pr = & head;
	}
	LsList(LsList & ls)//賦值構造函數
	{
		size = 0;
		head.next = 0;
		pr = & head;
		for(LsList::Iter iter  = ls.begin();iter != ls.end();iter++)
		{
		 push_back( *iter);
		}
	}
	//賦值操作符重載
	LsList & operator = ( LsList & tl)
	{
	  clear();
	  size = 0;
	  head.next = 0;
	  pr = & head;
	  for(LsList::Iter iter  = tl.begin();iter != tl.end();iter++)
	{
		 push_back( *iter);
	}

	  return *this;
	}


	//數組初始化方式
	LsList(T t[],int n)
	{   if(n<=0)
	   {
		   throw underflow_error("underflow_error");
	   }
		size = 0;
		LNode * pl = new LNode();
		head.next = pl;
		pr = pl;
		for(int i=0;idata = t[i];
			LNode *p = new LNode();
			pl->next = p;
			pl = p;
			size++;
		}
		pl->data = t[n-1];
		pr = pl;
		size++;
		pl->next = 0;
	}

	//支持下標操作（不建議這樣寫，效率低！鏈式存儲的數據結構一般不會支持數據的隨機存取）
	T & operator[](size_t n)
	{
		if(n>size-1)
		{
			throw range_error("range_error");
		}
		LNode * p = head.next;
		size_t i = 0;
		while(inext;
		}
	    return p->data;
	}
	//返回線性表的元素個數
	size_t GetSize()
	{
	  return  size;
	}

	//在表首增加元素
	bool push_front(T  t)
	{
	 LNode * p = head.next;
	 LNode * pl = new LNode();
	 pl->data = t;
	 head.next = pl;
	 pl->next = p;
	 if(pr==&head) //先判斷是否為空表
	 {
	  pr = pl;
	 }
	 size++;
	 return true;
	}
	//在表尾增加元素
	bool push_back(T  t)
	{ 
	 LNode * pl = new LNode();
	 pl->data = t;
	 if(pr==&head) //先判斷是否為空表
	 {
	   head.next = pl;
	   pr = pl;
	 }
	 else
	 {
	  pr->next = pl;
	  pl->next = 0;
	  pr = pl;
	 }
	 size++;
	 return true;
	}

	//返回第一個元素
	T & front()
	{
		if(pr==&head)
			throw runtime_error("鏈表為空!");
	    return (head.next)->data;
	}

	//返回最後一個元素
	T & back()
	{
	   if(pr==&head)
	   throw runtime_error("鏈表為空!");
	   return pr->data;
	}

	//在第n個元素前插入一個元素
	bool insert(T  t,size_t n)
	{
	 if(n<=0||n>size)
		{
			throw range_error("range_error");
		}
		LNode * p = &head;
		size_t i = 1;
		while(inext;
		}
	    LNode * pl = new LNode();
	    pl->data = t;
		pl->next = p->next;
		p->next = pl;
		size++;
	    return true;
	}

	//刪除第n個元素
	bool dele(T & t,size_t n)
	{
	    if(n<=0||n>size)
		{
			throw range_error("range_error");
		}
		LNode * p = &head;
		size_t i = 1;
		while(inext;
		}
		LNode * pd = p->next;
		t = pd->data;
		
		p->next = p->next->next;
		if(n==size)
		{
		 pr = p;
		}
		size--;
		delete pd;
		return true;
	}
	//清空整個鏈表
	bool clear()
	{
	 LNode * pl = head.next;
	 while (pl)
	 {
		 /*delete pl;
		 pl = pl->next;*/   //說明：在C語言裡可以用這種寫法，但危險性極大
		  LNode * p2 = pl->next;
		  delete pl;
		  pl=p2;
	 }
	  size = 0;
	  head.next = 0;
	  pr = & head;
	 return true;
	}
	//返回第一個數據節點迭代器，用於調用者遍歷之用
	Iter begin()
	{
	 return Iter(head.next);
	}
	//返回最後一個數據節點迭代器，用於調用者遍歷之用
	Iter end()
	{
	  return Iter(pr->next);
	}
	
	
	~LsList(void)
	{ 
	}
private :
	LNode head;//頭節點
	LNode * pr;//指向表尾的指針
	size_t size;//元素個數
};

#include
#include
#include
#include"LsList.h"
using namespace std;
int main()
{
	LsList li;//建立一個空的線性表
	cout< mlist(a,3);//用數組初始化一個線性表
	cout<<"數組初始化方式！"< la;
	la = mlist ;//使用賦值操作符函數
	LsList lb(la) ;//使用復制構造函數初始化
	cout<<"賦值操作符函數"<::Iter it = mlist.begin();//自定義的迭代器高效遍歷工具
	for(;it!=mlist.end();it++)
	{
	  cout<<*it<<" ";
	}
	cout<::Iter itr = mlist.begin();
	for(;itr!=mlist.end();itr++)
	{
	  cout<<*itr<<" ";
	}
	cout<