list.cpp

创建顺序表： 输出顺序表：顺序输出各个元素； 插入顺序表：在指定位置处插入元素； 删除顺序表：根据删除指定位置的元素； 逆转顺序表：按逆序倒置所有的元素； 排序顺序表：按照升序排列所有元素；

// List.cpp: implementation of the List class.
//
//////////////////////////////////////////////////////////////////////

#include "List.h"
#include"LinkNode.h"
#include<stdlib.h>
#include<iostream>
using namespace std;


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
 //复制构造函数
template<class T>
List<T>::List(List<T>&L)
{
	T value;
	LinkNode<T>*srcptr=L.getHead();
	LinkNode<T>*destptr=first=new LinkNode<T>;
	if(first==NULL){cerr<<"存储分配错误"<<endl;exit(1);}
	while(srcptr->link!=NULL)
	{
		value=srcptr->link->data;
		destptr->link=new LinkNode(value);
		if(destptr->link==NULL){cerr<<"存储分配错误"<<endl;exit(1);}
		destptr=destptr->link;
		srcptr=srcptr->link;
	}
	destptr->link=NULL;
}
 //计算链表的长度
template<class T>
int List<T>::Length()const
{
	LinkNode<T>*p=first->link;
	int count=o;
	while(p!=NULL)
	{
		count++;
		p=p->link;
	}
	return count;
}
 //将链表置为空表
template<class T>
void List<T>::makeEmpty()
{
	LinkNode<T>*q;
	while(first->link!=NULL)
	{
		q=first->link;
		first->link=q->link;
		delete q;
	}
}

 //搜索第i个元素地址
template<class T>
LinkNode<T>* List<T>::Search(T x)
{
	LinkNode<T>* current=first->link;
	while(current!=NULL)
	{
		if(current->data==x)return current;
		else current=curent->link;
	}
	return NULL;
}
 //取出第i个元素地址
template<class T>
LinkNode<T>* List<T>::Locate(int i)
{
	if(i<0)return NULL;
	LinkNode<T>* current=first;
	int k=0;
	while(current!=NULL&&k<i)
	{
		current=current->link;
		k++;
	}
	return current;
}
 //用x修改第i个元素的值
template<class T>
void List<T>::setData(int i,T& x)
{
	if(i<0)return;
	LinkNode<T>*curent=locate(i);
	if(current==NULL)return;
	else current->data=x;
}
//取出第i个元素地址

template<class T>
T* List<T>::getData(int i)
{
	if(i<0)return NULL;
	LinkNode<T>* current=Locate(i);
	if(current==NULL)return NULL;
	else return &currrent->data;
}
//在第i个元素后插入x
template<class T>
bool List<T>::Insert(int i,T x)
{
	LinkNode<T>* current=Locate(i);
	if(current==NULL)return false;
	LinkNode<T>* newNode=new LinkNode<T>(x);
	if(newNode==NULL){cerr<<"存储分配错误"<<endl;exit(1);}
	newNode->link=current->link;
	current->link=newNode;
	return true;
}
 //删除第i个元素x返回该元素的值
template<class T>
bool List<T>::Remove(int i,T& x)
{
	LinkNode<T>* current=Locate(i-1);
	if(current==NULL||current->link==NULL)return false;
	LinkNode<T>* del=current->link;
	current->link=del->link;
	x=del->data;
	return true;
}
   //输出链表
template<class T>
void List<T>::output()
{
	LinkNode<T>* current=first->link;
	while(current!=NULL)
	{
		cout<<current->data<<' ';
		current=current->link;
	}
	cout<<endl;
}
//重载函数：赋值
template<class T>
List<T>& List<T>::operator=(List<T>&L)
{
	T value;
	LinkNode<T>*srcptr=L.getHead();
	LinkNode<T>*destptr=first=new LinkNode<T>;
	if(first==NULL){cerr<<"存储分配错误"<<endl;exit(1);}
	while(srcptr->link!=NULL)
	{
		value=srcptr->link->data;
		destptr->link=new LinkNode(value);
		if(destptr->link==NULL){cerr<<"存储分配错误"<<endl;exit(1);}
		destptr=destptr->link;
		srcptr=srcptr->link;
	}
	destptr->link=NULL;
	return *this;
} //后插法建立单链表
template<class T>
void List<T>::inputRear(T endflag)
{
	LinkNode<T>* newNode;
	LinkNode<T>* last;
	T val;
	first=new LinkNode<T>;
	if(first==NULL){cerr<<"存储分配错误！"<<endl;exit(1);}
	last=first;
	cin>>val;
	while(val!=endflag)
	{
		newNode=new LinkNode<T>(val);
		if(newNode==NULL){cerr<<"存储分配错误！"<<endl;exit(1);}
		last->link=newNode;
		last=newNode;
		cin>>val;
	}
	last->link=NULL;

}  //将链表逆序
template<class T>
void List<T>::reverse()
{
		LinkNode<T>* p=new LinkNode<T>;
		LinkNode<T>* t=first->link,	*q=first->link;
		int i=0;
		while(t->link!=NULL)
		{
			t=q->link;
			q->link=p;
			p=q;
			q=t;
		}
		t->link=p;
		first->link=t;
		p=first->link;
		while(p->link!=NULL)
		{
			q=p;
			p=p->link;	
		}
		q->link=NULL;
		delete p;




}