顺序表.cpp

数据结构：顺序表

//定义线性能顺序表存储模板类的实现文件“顺序表.cpp”
#include<iostream.h>
#include<stdlib.h>

#include "顺序表.h"

//构造函数，初始化线性表
template<class ElemType>
LinearList<ElemType>::LinearList(int ms)
{
	if(ms<=0) {cout<<"ms值无效！"<<endl; exit(1);}
	list=new ElemType[ms];
	if(!list){
		cerr<<"动态存储空间分配失败!"<<endl;
		exit(1);
	}
	size=0;
	MaxSize=ms;
}

//拷贝构造函数
template<class ElemType>
LinearList<ElemType>::LinearList(LinearList<ElemType>& a)
{
	list=new ElemType[a.MaxSize];
	if(!list){
		cerr<<"动态存储空间分配失败！"<<endl;
		exit(1);
	}
	for(int i=0; i<=a.size; i++) list[i]=a.list[i];
	size=a.size;
	MaxSize=a.MaxSize;
}

//得到线性表中指定下标位置的元素
template<class ElemType>
ElemType LinearList<ElemType>::GetElemList(int pos)
{
	if(pos<0 || pos>size-1){
		cerr<<"下标越界！"<<endl;
		exit(1);
	}
	return list[pos];
}

//遍历线性表
template<class ElemType>
void LinearList<ElemType>::TraverList()
{
	for(int i=0; i<size; i++) cout<<list[i]<<' ';
	cout<<endl;
}

//向线性表中插入元素
template<class ElemType>
void LinearList<ElemType>::InsertList(const ElemType& item, int mark)
//假定当mark等于1时插入到表头，等于2时插入到表尾
{
	//检查mark的合法性
	if(mark!=1 && mark!=2){
		cout<<"mark值无效！"<<endl;
		exit(1);
	}
	//对动态空间用完的情况进行处理
	if(size==MaxSize){
		ElemType *p=new ElemType[2*MaxSize];  //空间增加一倍
		if(!p){//分配失败退出运行
			cout<<"存储空间用完！"<<endl;
			exit(1);
		}
		for(int i=0; i<size; i++)        //把原空间内容复制到新空间中
			p[i]=list[i];
		delete []list;                  //释放原线性空间
		list=p;                         //使list指向新线性表空间
		MaxSize=2*MaxSize;              //把线性表空间大小修改为新的长度
	}
	//把元素插入到表头
	if(mark==1){
		for(int i=size-1; i>=0; i++)
			list[i+1]=list[i];
		list[0]=item;
	}
	//元素插入到表尾
	else list[size]=item;
	//线性表长度增1
	size++;
	return;
}

//从线性表中删除元素
template<class ElemType>
bool LinearList<ElemType>::DeleteList(ElemType& item, int mark)
//假定当mark等于1时删除表头元素，等于2时删除表尾元素
{
	//线性表为空返回假
	if(size==0) return false;
	//检查mark的合法性
	if(mark!=1 && mark!=2){
		cout<<"mark值无效！"<<endl;
		exit(1);
	}
	//删除表头元素
	if(mark==1){
		item=list[0];
		for(int i=1; i<size; i++)
			list[i-1]=list[i];
	}
	//删除表尾元素
	else item=list[size-1];
	//线性表长度减1
	size--;
	//返回真表示删除成功
	return true;
}