线性表（2）——顺序表的动态实现

				
					#include <iostream>
#include <cstdlib>
using namespace std;

template <typename Data>
class list{
private:
	Data *head;
	int length;
	int size;
public:
	//1.create destroy and clear
	list(int n){
		head=(Data *)malloc(n*sizeof(Data));
		if(head==nullptr)
		{
		    cout<<"初始化分配内存出错啦！"<<endl;
			return;
		}
		size=n;
		length=0;
	}
	//bool InitList(list &l); 由构造函数替代其功能
	bool DestroyList()
	{
		if(head!=nullptr)
		{
			free(head);
			length=0;
			size=0;
		}
		return true;
	}
	bool ClearList()
	{
		length=0;
		return true;
	}
	
	//2.各种访问型操作
	void ListTraverse()
	{
		for(int i=0;i<length;i++)
		{
			cout<<head[i]<<' ';
		}
		cout<<endl;
	}
	bool ListEmpty(){
		return length==0;
	}
	
	int ListLength()
	{
		return length;
	}
	
	Data GetElem(int i)
	{
		if(i<0||i>length)
		{
			cout<<"访问不合法"<<endl;
			exit(0);
		}
		return head[i];
	}

	int LocateElem(Data e)
	{
		for(int i=0;i<length;i++)
		{
			if(e==head[i])
				return i;
		}
		return -1;
	}
	Data PriorElem(Data cur)
	{
		for(int i=1;i<length;i++)
		{
			if(cur==head[i])
				return head[i-1];
		}
		cout<<"fail in PriorElem"<<endl;
	}
	Data NextElem(Data cur)
	{
		for(int i=0;i<length-1;i++)
		{
			if(cur==head[i])
				return head[i+1];
		}
		cout<<"fail in NextElem"<<endl;
	}
	
	//3.修改型
	bool SetElem(int pos,Data e)
	{
		if(pos<0||pos>length)
		{
			cout<<"fail in SetElem"<<endl;
			return false;
		}
		head[pos]=e;
		return true;
	}
	
	bool InsertElem(int pos,Data e)
	{
		if(pos<0||pos>length)
		{
			cout<<"invalid"<<endl;
			return false;
		}
		if(length+1>=size)
		{
			Data *newbase=(Data *)realloc(head,2*size*sizeof(Data));//默认双倍扩容
			if(newbase==nullptr)
			{
				cout<<"failed to reverse"<<endl;
				return false;
			}
			head=newbase;
			size*=2;
		}
		for(int j=length;j>=pos;j--)
		{
			head[j+1]=head[j];//向后拷贝，节约时间
		}
		head[pos]=e;
		++length;
		return true;
	}
	Data DeleteElem(int pos)//删除指定位置上的元素并返回
	{
		if(pos<0||pos>length)
		{
			cout<<"invalid"<<endl;
			exit(0);
		}
		Data tmp=head[pos];
		for(int j=pos+1;j<length;j++)
		{
			head[j-1]=head[j];
		}
		--length;
		return tmp;
	}
};