线性表

数据结构

//头文件
#ifndef LinearList
//enum bool {false,true};
template<class T>
class LinearList{
public:
    LinearList();
    ~LinearList();
    virtual int Size()const=0;
    virtual int Length()const=0;
    virtual int Locate(int i)const=0;
    virtual bool getData(int i,T &x)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 IsFull()const=0;
    virtual void Sort()=0;
    virtual void input()=0;
    virtual void output()=0;
    virtual LinearList<T>operator=(LinearList<T>&L)=0;
}
#endif

//源文件
#include<iostream.h>
#include<stdlib.h>
#include"LinearList.h"
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;}
    int Search(T& x)const;
    int Locate(int i)const;
    bool getData(int i,T &x)const
    {if(i>0&&i<=last+1) {x=data[i-1];return true;} else return false;}
    bool setData(int i,T &x)
    {if(i>0&&i<=last+1)data[i-1]=x;}
    bool IsEmpty(){return (last==-1)?true:false;}
    bool IsFull(){return (last==maxSize-1)?true:false;}
    void input()i
    void output()i
    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)
            {cerr<<"存储分配错误！"<<endl;exit(1);}
    }
}
template<classT>
SeqList<T>::SeqList(SeqList<T>&L){
    maxSize=L.Size();last=L.Length()-1;T value;
    data=new T[maxSize];
    if(data==NULL)
        {cerr<<"存储分配错误！"<<endl;exit(1);}
    for(int i=1;i<=last+1;i++)
        {L.getData(i,value);data[i-1]=value;}
}
template<class T>
void SeqList<T>::reSize(int newSize){
    if(newSize<=0)
        {cerr<<"无效的数组大小"<<endl;return;}
    if(newSize!=maxSize){
        T *newarray=new T[newSize];
        if(newarray==NULL)
            {cerr<<"存储分配错误！"<<endl;exit(1);}
        int n=last+1;
        T *srcptr=data;
        T *destptr=newarray;
        while(n--)*destptr++=*srcptr++;
        delete[]data;
        data=newarray;maxSize=newSize;
    }
}
template<class T>
int SeqList<T>::Search(T &x)const{
    for(int i=0;i<=last;i++)
        if(data[i]==x)return i+1;
    return 0;
}