#include"LsList.h"

#include<iterator>
#include<list>
#include<vector>
using  namespace std;
#pragma once
template<class T>
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<T> & ls)//赋值构造函数
	{
		size = 0;
		head.next = 0;
		pr = & head;
		for(LsList<T>::Iter iter  = ls.begin();iter != ls.end();iter++)
		{
		 push_back( *iter);
		}
	}
	//赋值操作符重载
	LsList & operator = ( LsList<T> & tl)
	{
	  clear();
	  size = 0;
	  head.next = 0;
	  pr = & head;
	  for(LsList<T>::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;i<n-1;i++)
		{   pl->data = 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(i<n)
		{
		 i++;
		 p = p->next;
		}
	    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(i<n)
		{
		 i++;
		 p = p->next;
		}
	    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(i<n)
		{
		 i++;
		 p = p->next;
		}
		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<iostream>
#include<list>
#include<vector>
#include"LsList.h"
using namespace std;
int main()
{
	LsList<int> li;//建立一个空的线性表
	cout<<li.GetSize()<<endl;

	int a[3] = {1,2,3};
	LsList<int> mlist(a,3);//用数组初始化一个线性表
	cout<<"数组初始化方式！"<<endl;
	cout<<mlist[0]<<" ";
	cout<<mlist[1]<<" ";
	cout<<mlist[2]<<" ";
	cout<<endl;
	cout<<"list的元素个数为："<<mlist.GetSize()<<endl;

	LsList<int> la;
	la = mlist ;//使用赋值操作符函数
	LsList<int> lb(la) ;//使用复制构造函数初始化
	cout<<"赋值操作符函数"<<endl;
	cout<<la[0]<<" ";
	cout<<la[1]<<" ";
	cout<<la[2]<<" ";
	cout<<endl;
	cout<<"复制构造函数初始化"<<endl;
	cout<<lb[0]<<" ";
	cout<<lb[1]<<" ";
	cout<<lb[2]<<" ";
	cout<<endl;

	cout<<"获取线性表的第一个元素："<<endl;
	cout<<mlist.front()<<endl;//获取线性表的首位元素
	cout<<"获取线性表的最后一个元素："<<endl;
	cout<<mlist.back()<<endl;

	mlist.push_back(4);//向表首段添加元素
	mlist.push_front(-1);//向表尾段添加元素
	cout<<"在表首添加元素4，在表尾添加元素-1"<<endl;
	for(int i=0;i<(int)mlist.GetSize();i++)
	{
		cout<<mlist[i]<<" ";
	}
	cout<<endl;
	cout<<"迭代器高效遍历:"<<endl;
	LsList<int>::Iter it = mlist.begin();//自定义的迭代器高效遍历工具
	for(;it!=mlist.end();it++)
	{
	  cout<<*it<<" ";
	}
	cout<<endl;

	cout<<"在第2个元素之前插入元素7:"<<endl;//插入元素
	mlist.insert(7,2);
	LsList<int>::Iter itr = mlist.begin();
	for(;itr!=mlist.end();itr++)
	{
	  cout<<*itr<<" ";
	}
	cout<<endl;

	cout<<"删除第二个元素:"<<endl;//删除元素
	int ia;
	mlist.dele(ia,2);
	itr = mlist.begin();
	for(;itr!=mlist.end();itr++)
	{
	  cout<<*itr<<" ";
	}
	cout<<endl;







	cout<<"清空整个线性表:"<<endl;//清空整个线性表
	mlist.clear();
	cout<<"list的元素个数为："<<mlist.GetSize()<<endl;
}

线性表链式存储C++实现,布布扣,bubuko.com

线性表链式存储C++实现