seqlist.h

回顾基础

//顺序表类
#include <iostream.h>

template <class T>
class SeqList                                    //顺序表类，T指定元素类型
{
  private:
    T *element;                                  //动态数组存储顺序表的数据元素
    int size;                                    //顺序表的数组容量
    int len;                                     //顺序表长度

  public:
    SeqList(int size=64);                        //构造指定（默认）容量的空表
    SeqList(T value[], int n);                   //构造由指定数组提供元素的顺序表
    ~SeqList();                                  //析构函数 

    bool isEmpty();                              //判断顺序表是否为空
    int length();                                //返回顺序表长度    
    T get(int i);                                //返回第i（i≥0）个元素
    bool set(int i, T x);                        //设置第i个元素为x
    void insert(int i, T x);                     //插入x作为第i个元素
    void insert(T x);                            //在顺序表最后插入x
    bool remove(int i, T& old);                  //删除第i个元素，原值存放在old变量中 
    void clear();                                //清空顺序表
    friend ostream& operator<<(ostream& out, SeqList<T> &list);    //输出顺序表所有元素

    //8.2.1 顺序查找
    int index(T value);                          //顺序查找指定元素
    bool contain(T value);                       //判断线性表是否包含指定元素


};

template <class T>
SeqList<T>::SeqList(int size)                    //构造指定容量的空表
{
    this->size = size<64 ? 64 : size;
    this->element = new T[this->size];
    this->len = 0;
}

template <class T>
SeqList<T>::SeqList(T value[], int n)            //构造由value数组提供元素的顺序表
{                                                //n指定数组元素个数
    if (n>0) 
    {
        this->element = new T[2*n];
        this->size = 2*n;
        for (int i=0; i<n; i++)
            this->element[i] = value[i];
        this->len = n;
    }
}

template <class T>
SeqList<T>::~SeqList()                           //析构函数
{
    delete []this->element;
}

template <class T>
bool SeqList<T>::isEmpty()                       //判断顺序表是否为空
{
    return len==0;
}

template <class T>
int SeqList<T>::length()                         //返回顺序表长度
{
    return len;
}

template <class T>
T SeqList<T>::get(int i)                         //返回第i（i≥0）个元素
{                                                //若i指定元素序号无效则抛出异常
    if (i>=0 && i<len)
        return element[i];
    throw "参数i指定元素序号无效";
}

template <class T>
bool SeqList<T>::set(int i, T x)                 //设置第i个元素为x
{                                                //操作成功返回true，若i指定序号无效返回false
    if (i>=0 && i<len) 
    {
        element[i] = x;
        return true;
    }
    return false;
}

template <class T>
ostream& operator<<(ostream& out, SeqList<T> &list)   //输出顺序表所有元素
{
    out<<"(";
    if (list.len>0)
    {
        out<<list.element[0];
        for (int i=1; i<list.len; i++)
             out<<", "<<list.element[i];
    }
    out<<")\n";
    return out;
}

template <class T>
void SeqList<T>::insert(int i, T x)              //插入x作为第i个元素
{
    if (len==size)                               //若数组满，则扩充顺序表容量
    {
        T *temp = element;  
        element = new T[size*2];                 //重新申请一个容量更大的数组
        for (int i=0; i<size; i++)               //复制数组元素
            element[i] = temp[i];
        size *=2;
    }
    if (i<0)    i=0;                             //序号容错
    if (i>len)  i=len;

    for (int j=len-1; j>=i; j--)                 //元素后移，平均移动len/2
        element[j+1] = element[j];
    element[i] = x;
    len++;
}

template <class T>
void SeqList<T>::insert(T x)                     //在顺序表最后插入x元素，函数重载
{
    insert(len, x); 
}

template <class T>
bool SeqList<T>::remove(int i, T& old)           //删除第i个元素，原值存放在old变量中
{
    if (len>0 && i>=0 && i<len)
    {
        old = element[i];
        for (int j=i; j<len; j++)                //元素前移，平均移动len/2
            element[j] = element[j+1];
        len--;
        return true;                             //若操作成功，则原值存放在old变量中
    }
    return false;                                //未找到待删除元素，操作不成功
}

template <class T>
void SeqList<T>::clear()                         //清空顺序表，未释放数组空间
{
    len=0;
}

//以上是第2章内容


//第2章习题

/*
int SeqList<T>::search(int k)              //查找，返回k值首次出现的位置
{                                       //未找到时，返回0
    int i=1;
    while(i<=length() && get(i)!=k)
        i++;
    if(i<=length())
        return i;
    else
        return 0;
}
bool SeqList<T>::remove(int k)             //删除k值首次出现的数据元素
{
    if (!isEmpty())
    {
        int i=search(k);                //第i个结点
        for(int j=i;j<length();j++)     //向前移动数据元素
            set(j,get(j+1));            //即element[j]=element[j+1];
        len--;                          //长度减1
        return true;
    }
    else
    {
        cout<<"顺序表为空，无法删除值！\n";
        return false;
    }
}
*/

//以下第8章 8.2.1 顺序查找

template <class T>
int SeqList<T>::index(T value)                   //顺序查找指定元素
{                                                //若查找成功返回首次出现位置，否则返回-1
    for (int i=0; i<len; i++)
        if (element[i]==value)
            return i;
    return -1;
}

template <class T>
bool SeqList<T>::contain(T value)                //以查找结果判断线性表是否包含指定元素
{                                                //若包含返回true，否则返回false
    return index(value)>=0;
}


/*
//以下是第8章 8.2.1 顺序查找习题
    public int lastIndexOf(E value)           //返回obj对象最后出现位置，若未找到返回-1
    {
        if (obj!=null)
            for (int i=this.n-1; i>=0; i--)
                if (obj.equals(this.element[i]))
                    return i;
        return -1;
    }

    public boolean remove(E value)            //移去首次出现的obj对象，若操作成功返回true
    {
        if (this.n!=0 && obj!=null)
            return this.remove(this.indexOf(obj))!=null;
        return false;
    }
    
    public boolean removeAll(E value)         //移去线性表中所有obj对象
    {
        boolean done=false;
        if (this.n!=0 && obj!=null)
        {
            int i=0;
            while (i<this.n)
                if (obj.equals(this.element[i]))
                {
                    this.remove(i);
                    done = true;
                }
                else
                    i++;
        }
        return done;
    }

    public boolean replace(Object obj, E value)//将首次出现的obj对象替换为value对象
    {                                            //若操作成功返回true，O(n/2)
        if (obj!=null && value!=null)
        {
            int i = this.indexOf(obj);           //查找obj对象首次出现位置
            if (i!=-1)
            {
                this.element[i] = value;
                return true;
            }
        }
        return false;
    }

    public boolean replaceAll(Object obj, E value)   //将线性表中所有obj对象替换为value对象
    {
        boolean done=false;
        if (obj!=null && value!=null)
            for (int i=0; i<this.n; i++)
                if (obj.equals(this.element[i]))
                {
                    this.element[i] = value;
                    done = true;
                }
        return done;
    }


}

/*
可行，效率同上
    public String toString()                     //返回显示线性表所有元素值的字符串，形式为[,] 
    {
        String str="[";
        if (this.n()!=0)
        {
            for(int i=0; i<this.n()-1; i++)
                str += this.get(i).toString()+", ";
            str += this.get(this.n()-1).toString();
        }
        return str+"]";
    }

    public boolean equals(Object obj)            //比较两个顺序表对象是否相等
    {                                            //O(n)
        if (this==obj)
            return true;
        
        if (obj instanceof SeqList<T>)
        {
            SeqList<T> list = (SeqList<T>)obj;
            for (int i=0; i<this.length(); i++)
                if (!(this.get(i).equals(list.get(i))))
                    return false; 
            return true;
        }
        return false;
    }


*/