【c++数据结构】顺序表 继承线性表类

#include 
#include
#include"LinearList.h"
using namespace std;
const int defaultSize =30;

template
class LinearList {
public:
	LinearList() {}
	~LinearList() {}
	virtual int Size()const = 0;
	virtual int Length()const = 0;
	virtual int Search(T& x)const = 0;
	virtual int Locate(int i)const = 0;
	virtual T& getDate(int i)const = 0;
	virtual void setData(int i, T& x) = 0;
	virtual bool Insert(int i, T& x) = 0;
	virtual bool Remove(int i, T& x) = 0;
	virtual bool Isempty()const = 0;
	virtual bool Isfull()const = 0;
	virtual void input() = 0;
	virtual void output() = 0;
};

template
class SeqList :public LinearList {
protected:
	T* data;
	int maxSize;
	int last;          
	void reSize(int newSize);
public:
	SeqList(int sz=defaultSize);
	SeqList(SeqList& L);
	~SeqList()                   {delete[]data; }
	int Size()const              { return maxSize; }
	int Length()const            { return last + 1;}
	T& getDate(int i)const       {return data[i-1]; }
	bool Isempty()const          { return (last == -1) ? true : false; }
	bool Isfull() const          { return(last == maxSize - 1) ? true : false; }
	void setData(int i, T& x)    {if (i > 0 && i <= last - 1)data[i] = x;} 
	int Search(T& x)const;
	int Locate(int i)const;
	void quickSort(int left,int right);  //快速排序
	bool Insert(int i, T& x);            //插入
	bool sort_Insert(T x);               //有序插入
	void List_Reverse();                 //逆置
	bool Remove(int i,T& x);             //删除单个元素
	bool List_delete(int i, int k);      //删除多个连续元素
	void input();
	void output();
};

template                          //构造函数
SeqList::SeqList(int sz) {           
	maxSize = sz;
	last = -1;
	data = new T[maxSize];
	if (data == NULL) {
		cout << "存储分配失败" << endl;
		exit(0);
	}
}

template                         //复制构造函数
SeqList::SeqList(SeqList& L) {
	maxSize = L.Size();
	last = L.Length() - 1;
	data = new T[maxSize];
	if (data == NULL) {
		cout << "存储分配失败" << endl;
		exit(0);
	}
	for (int i = 0; i <= last; i++) data[i] = L.getDate(i+1);
}

template                         //扩充链表
void SeqList::reSize(int newSize) {       
	if (newSize <= 0) {
		cout << "无效的数组大小" << endl;
		return;
	}
	if (newSize != maxSize) {
		T* newDate = new T[newSize];
		if (newDate == NULL) {
			cout << "存储分配失败" << endl;
			exit(0);
		}
		for (int i = 0; i <= last - 1;i++) newDate[i] = getDate[i];
		maxSize = newSize;
		data = newDate;
	}
}


template                         //定位
int SeqList::Locate(int i)const {             
	if (i >= 1 && i <= last + 1)return i;
	else return 0;
}


template                          //查找
int SeqList::Search(T& x)const {            
	for (int i = 0; i <= last; i++) {
		if (data[i] == x) return i + 1;
	}
	return 0;
}


template                           //快速排序
void SeqList::quickSort(int left, int right) { //快速排序
	if (left >= right)return;
	int i, j; T base;
	i = left; j = right; base = data[left];
	while (i < j) {
		while (data[j] >= base && i < j)j--;
		if (i < j) data[i++] = data[j];
		while (data[i] < base && i < j)i++;
		if (i < j) data[j--] = data[i];
	}
	data[i] = base;
	quickSort(left, i - 1);
	quickSort(i + 1, right);

}


template                           //插入
bool SeqList::Insert(int i,T& x) {         
	if (last == maxSize - 1) return false;
	if (i<0 || i>last + 1)return false;
	for (int j = last; j >= i; j--)
		data[j + 1] = data[j];
	data[i] = x;
	last++;
	return true;
}


template                           //有序插入
bool SeqList::sort_Insert(T x) {             
	if (last == maxSize - 1)return false;
	quickSort(0, last);
	int loc=0;
	for (int i = 0; i <= last; i++) {
		if (data[i] >= x) {
			loc == i ; break;
		}
		else loc++;
	}
	if (Insert(loc, x)) return true;
	else return false;
}


template                            //逆序排序
void SeqList::List_Reverse() {           
	for (int i = 0; i < last / 2; i++)
		swap(data[i], data[last - i]);
}


template                            //删除单个元素
bool SeqList::Remove(int i,T& x) {            
	if (last == -1 || i<1 || i>last + 1)return false;
	for (int j = i-1; j < last; j++)
		data[j] = data[j + 1];
	last--;
	return true;
}


template                            //删除多个连续元素
bool SeqList::List_delete(int left, int right) {   
	int delete_num = right - left + 1;
	if (left<1 || left>last + 1) return false;
	if (right<1 || right>last + 1) return false;
	if (delete_num<0 || delete_num>last + 1)return false;
	else if (delete_num==0) { Remove(left, data[left]); return true; }
	else {
		int delete_num = right - left + 1;
		for (int i = left-1 ; i <= last - delete_num;i++)
			data[i] = data[i+ delete_num];
		last = last - delete_num;
		return true;
	}
}


template                            //逐个数据输入
void SeqList::input() {
	int num;
	cout << "开始建立顺序表，请输入表中元素个数：";
		while (1) {
			cin >> num;
			if (num <= maxSize - 1)break;
			cout << "表元素个数输入有误，范围不能超过" << maxSize - 1 << ":";
	}
	last = num - 1;
	for (int i = 0; i <= last; i++)
	{
		cout << i + 1 <<":";
		cin >> data[i];
		
	}
}


template                            //打印顺序表
void SeqList::output() {
	cout << "顺序表当前元素最后位置为：" << last << endl;
	for (int i = 0; i <= last; i++)
		cout << "#" << i + 1 << ":" << data[i] << endl;
}

//测试代码
//void test01() {
//	int a, b, c;
//
//	SeqList Seqlist_A(10);
//	if(Seqlist_A.Isempty()) cout<<"该线性表为空"< Seqlist_B(Seqlist_A);
//	cout << "复制构造B，打印Seqlist_B：" << endl;
//	Seqlist_B.output(); cout << endl;
//
//	Seqlist_A.quickSort(0, Seqlist_A.Length()-1);
//	cout << "正序排序：" ;
//	Seqlist_A.output(); cout << endl;
//
//	Seqlist_A.List_Reverse();
//	cout << "翻转Seqlist_A：";
//	Seqlist_A.output(); cout << endl;
//
//	cout << "输入元素有序插入到SeqList_A：";
//	cin >> a;
//	if (Seqlist_A.sort_Insert(a)) cout << "插入成功" << endl; else cout << "插入失败" << endl;
//	Seqlist_A.output(); cout << endl;
//	
//	cout << "输入删除SeqList_A中元素范围 从第__个到第__个：";
//	cin >> b >> c;
//	if (Seqlist_A.List_delete(b, c))cout << "删除成功" << endl; else cout << "删除失败" << endl;
//	Seqlist_A.output();
//}
//int main() {
//	test01();
//}