线性表的本质、操作及顺序存储结构（六）

        我们说到线性表，可能好多人还不太理解。那么我们举个例子来说，在幼儿园中，老师们总会让小朋友以同样的派对秩序出行，这个例子的本质就是线性表。

        那么线性表（List）的表现形式是怎样的呢？符合以下几个特征：1、零个或多个数据元素组成的集合；2、数据元素在位置上是有序排列的；3、数据元素的个数是有限的；4、数据元素的类型必须是相同的。那么线性表的抽象定义是怎么定义的呢？线性表是具有相同类型的 n( ≥ 0 ) 个数据元素的有限序列。如下

        下来我们来看看 List 的本质：1、a₀ 为线性表的第一个元素，只有一个后继；2、a_n-1 为线性表的最后一个元素，只有一个前驱；3、除 a₀ 和 a_n-1 外的其他元素 a_i ，既有前驱又有后继；4、直接支持逐项访问和顺序存取。下面我们来看看线性表一些常用操作：a> 将元素插入线性表；b> 将元素从线性表中删除；c> 获取目标位置处元素的值；d> 设置目标位置处元素的值；d> 获取线性表的长度；e> 清空线性表。

        线性表在程序中表现为一种特殊的数据类型。定义如下

#ifndef LIST_H #define LIST_H #include "Object.h" namespace DTLib { template < typename T > class List : public Object { public:     List() {}     virtual bool insert(const T& e) = 0;     virtual bool insert(int i, const T& e) = 0;     virtual bool remove(int i) = 0;     virtual bool set(int i, const T& e) = 0;     virtual bool get(int i, T& e) const = 0;     virtual int length() const = 0;     virtual void clear() = 0; }; } #endif // LIST_H

        下面我们来看看顺序存储的定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表中的数据元素。如下

        那么我们该如何设计呢？可以使用一维数组来实现顺序存储结构，存储空间：T* m_array；当前长度： int m_length；定义如下

template < typename T > class SeqList : public List<T> { protected:     T* m_array;     int m_length;     //// }

        那么顺序存储结构的元素获取操作怎样来实现呢？一是判断目标位置是否合法，二是将目标位置作为数组下标获取元素。定义如下

bool SeqList<T>::get(int i, T& e) const     {     bool ret = ((0 <= i) && (i < m_length));     if( ret )     {         e = m_array[i];     }     return ret; }

        顺序存储结构的元素插入示例如下

bool SeqList<T>::insert(int i, const T& e)     {     bool ret = ((0 <= i)  && (i <= m_length));     ret = ret &&  (m_length < 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; }

        顺序存储结构的元素删除操作：1、判断目标位置是否合法；2、将目标位置后的所有元素前移一个位置；3、线性表长度减一。删除示例如下

bool SeqList<T>::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; }

        我们完成了以上的几个重要操作之后，我们来看看 SeqList 处于一个什么样的位置，如下图所示

        那么这便是一个顺序存储结构线性表的抽象实现了。在 SeqList 设计时，我们要只有以下几点：1、抽象类模板，存储空间的位置和大小由子类完成；2、实现顺序存储结构线性表的关键操作（增、删、查等）；3、提供数组操作符，方便快速获取元素。那么它的抽象定义如下：

template < typename T > class SeqList : public List<T> { protected:     T* m_array;        // 顺序存储空间     int m_length;      // 当前线性表长度 public:     bool insert(int i, const T& e);     bool remove(int i);     bool set(int i, const T& e);     bool get(int i, T& e) const;     int length() const;     void clear();          // 顺序存储线性表的数组访问方式     T& operator[] (int i);     T& operator[] (int i) const;          // 顺序存储空间的容量      virtual int capacity() const = 0; };

        下来我们来看看 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));         ret = ret &&  (m_length < 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 insert(const T& e)     {         return insert(m_length, e);     }     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

main.cpp 源码

#include <iostream> #include "Seqlist.h" using namespace std; using namespace DTLib; int main() {     SeqList<int>* l;     return 0; }

        经过编译，编译时通过的，说明我们已经完成了 SeqList 抽象类的实现了。接下来我们思考下，在前面的 SeqList 的实现中，我们在它的下面还有 StaticList 和 DynamicList 的两个子类，那么我们该如何去实现它们呢？StaticList 和 DynamicList 的差异在哪里？是否可以将 DynamicList 作为 StaticList 的子类实现呢？通过对线性表的学习，总结如下：1、线性表是数据元素的有序并且有限的集合，并且线性表中的数据元素必须是类型相同的；2、线性表可用于描述派对关系的一系列问题；3、线性表在程序中表现为一种特殊的数据类型；4、线性表在 C++ 中表现为一个抽象类。