#pragma once
#include<iostream>
#include <stdlib.h>
#include"LinearList.h"
using namespace std;
const int defaultSize = 100;
template<class T>
class SeqList : public LinearList<T>
{
protected:
T* data;
int maxSize;
int last;
void reSize(int newSize);
public:
SeqList(int sz = defaultSize);
SeqList(SeqList<T>& L);
~SeqList()
{
delete [] data;
}
int Size()const
{
return maxSize;
}
int Length()const
{
return last + 1;
}
bool getData(int i, T& x) const
{
if(i>0 && i<=last+1)
{
x = data[i-1];
return true;
}
else
return false;
}
void setData(int i, T& x)
{
if(i>0 && i<=last+1)
data[i-1] = x;
}
bool IsEmpty() const
{
if(last == -1)
{
cout<<"This is a empty seqlist !"<<endl;
}
else
{
cout<<"This is not a empty seqlist !"<<endl;
}
return (last == -1)?true:false;
}
bool IsFull() const
{
return (last == maxSize - 1)?true:false;
}
int Search(T& x)const;
int Locate(int i)const;
bool Insert(int i, T& x);
bool Remove(int i, T& x);
void input();
void output();
SeqList<T>operator=(SeqList<T>&L);
};
template<class T>
SeqList<T>::SeqList(int sz)
{
if(sz > 0)
{
maxSize = sz;
last = -1;
data = new T[maxSize];
if(data == NULL)
{
cout<<"存储内存失败"<<endl;
exit(1);
}
}
}
template<class T>
SeqList<T>::SeqList(SeqList<T>& L)
//复制构造函数，用参数表中给出的已有顺序表初始化新建的顺序表
{
maxSize = L.Size();
last = L.Length() - 1;
data = new T[maxSize];
if(data == NULL)
{
cout<<"存储分配失败"<<endl;
exit(1);
}
for(int i=1; i<=last+1; i++)
data[i-1] = L.getData(i,L);
}
template<class T>
void SeqList<T>::reSize(int newSize)
//私有函数：扩充顺序表的存储数组空间大小，新数组的元素个数为newSize
{
if(newSize <= 0)
{
cout<<"无效的数组大小"<<endl;
return;
}
if(newSize != maxSize)
{
T* newarray = new T[newSize];
if(newarray == NULL)
{
cout<<"存储分配错误"<<endl;
exit(1);
}
int n = last + 1;
T* scrptr = data;
T* desptr = newarray;
while(n--)
*desptr++ = *scrptr++;
delete []data;
data = newarray;
maxSize = newSize;
}
}
template<class T>
int SeqList<T>::Search(T& x)const
{
cout<<endl;
cout<<"Now we will search the data that you want!"<<endl;
for(int i=0; i<=last; i++)
if(data[i] == x)
{
cout<<"OK,We have fonuded!"<<endl;
return i+1;
}
cout<<"Cannot find the result!"<<endl;
return 0;
}
template<class T>
int SeqList<T>::Locate(int i)const
{
if(i>=1 && i<=last+1)
return i;
else
return 0;
}
template<class T>
bool SeqList<T>::Insert(int i, T& x)
{
if(last == maxSize - 1)
{
cout<<"The seqlist is full, we cann't insert any data!"<<endl;
return false;
}
if(i<0 || i>last+1)
{
cout<<"The location is not valid, please choose a valid location!"<<endl;
return false;
}
for(int j=last; j>=i; j--)
data[j+1] = data[j];
data[i] = x;
last++;
return true;
}
template<class T>
bool SeqList<T>::Remove(int i, T& x)
{
if(last == -1)
return false;
if(i<1 || i>last+1)
return false;
x = data[i-1];
for(int j=i; j<=last; j++)
{
data[j-1] = data[j];
}
last--;
return true;
}
template<class T>
void SeqList<T>::input()
{
cout<<"Begin to create the list, please input elements:"<<endl;
while(1)
{
cin>>last;
cout<<"The lenght of the Seqlist is:"<<last<<endl;
if(last <= maxSize -1)
break;
cout<<"范围不能超过"<<maxSize - 1<<"!"<<endl;
}
for(int i=0; i<=last; i++)
{
cout<<"The "<<i+1<<"data is："<<endl;
cin>>data[i];
}
}
template<class T>
void SeqList<T>::output()
{
cout<<"The last location of the Seqlist is："<<last<<"(The location of the first data is 0)"<<endl;
for(int i=0; i<=last; i++)
cout<<"The "<<i+1<<"data is:"<<data[i]<<endl;
}