16_顺序存储结构的抽象实现

关键词： SeqList抽象实现

1. 课程目标

完成顺序存储结构的抽象实现

2. SeqList设计要点

• 抽象类模板，存储空间的位置和大小由子类完成
• 试下顺序存储结构线性表的关键操作（增，删，查等）
• 提供数组操作符，方便快速获取元素

3. SeqList的实现

SeqList.h

#ifndef SEQLIST_H
#define SEQLIST_H

#include "List.h"
#include "Exception.h"

namespace DTLib
{

template <typename T>
class SeqList : public List<T>
{
protected:
    T* m_array;     // 顺序存储空间，具体实现由子类实现
    int m_length;   // 当前线性表长度
public:
    bool insert(int i, const T& e)
    {
        bool ret = ((0 <= i ) && ( i <= m_length ));  // 注意：i<= m_length

        ret = ret && ((m_length + 1) <= capacity());  // capacity()为数组的存储量

        if(ret)
        {
            for(int p=m_length-1; p>=i; p--)
            {
                m_array[p + 1] = m_array[p];
            }

            m_array[i] = e;
            m_length++;
        }

        return ret;
    }

    bool remove(int i)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if(ret)
        {
            for(int p=i; p<m_length-1; p++)
            {
                m_array[p] = m_array[p+1];
            }

            m_length--;
        }

        return ret;
    }

    bool set(int i, const T& e)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if(ret)
        {
            m_array[i] = e;
        }

        return ret;
    }

    bool get(int i, T& e) const
    {
        bool ret = ((0 <= i) && (i < m_length));

        if(ret)
        {
            e = m_array[i];
        }

        return ret;
    }

    int length() const
    {
        return m_length;
    }

    void clear()
    {
        m_length = 0;
    }

    T& operator[] (int i)              // [] 操作符重载
    {
        if((0 <= i) && (i < m_length))
        {
            return m_array[i];
        }
        else
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid...");
        }
    }

    T operator[](int i) const
    {
        return (const_cast<SeqList<T>&>(*this))[i];
    }

    virtual int capacity() const = 0;   // 顺序存储空间的容量
};

}

#endif // SEQLIST_H

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4