数据结构与算法分析(c++版) #2 初涉线性表

 线性表

        线性表的定义：是由称为元素的数据项组成的一种有限且有序的序列。这个定义中有序是指线性表中的每一个元素都有自己的位置。
       线性表不含任何元素时，我们称之为空表(empty list)。当前储存的元素数目成为线性表的长度(length)。线性表的开始结点成为表头(head)，结尾结点成为表尾(tail)。表中的元素的值与它的位置之间可以有联系，也可以没有联系，因为线性表可以分为有序线性表和无序线性表。有序线性表元素按照值得递增顺序排列，而无序线性表在元素的值与位置之间就没有特殊的联系。

       书中为了定义当前位置的概念，假设线性表由两个分离部分组成，这两部分被一个“栅栏”分开，这个栅栏与当前位置相对应。（本人把它理解为是迭代器指向的地方）。例如，<20, 23 | 12, 15>这个线性表的四个元素被栅栏分成两部分，左边有两个，右边也有两个。

       下面是线性表的ADT。

template <class Elem> class List
{
public:
//
清空线性表
virtual void clear() = 0 ;
//
在线性表的右边部分的表头插入元素，如果线性表满了就返回false，否则返回true
virtual bool insert(const Elem &) = 0;
//
在线性表的右边部分的表尾拼接元素，如果线性表满了就返回false，否则返回true
virtual bool append(const Elem &) = 0;
//
删除线性表的右边部分的表头元素，如果右表为空返回false，否则返回true,并把表头元素的值返回到参数中
virtual bool remove(Elem &) = 0；
//
把栅栏的位置放在线性表表头，使左边部分为空
virtual void setStart() = 0;
//
把栅栏的位置放在线性表尾，使右边部分为空
virtual void setEnd() = 0;
//
把栅栏的位置向左移动一个单位，如果栅栏已经是表头就不移动
virtual void prev() = 0;
//
把栅栏的位置向右移动一个单位，如果栅栏已经是表尾就不移动
virtual void next() = 0;
//
返回左边部分线性表的长度
virtual int leftLength() const = 0;
//
返回右边部分线性表的长度
virtual int rightLength() const = 0;
//
设置栅栏的位置，如果设置的值小于等于线性表元素的个数，则返回true，否则超范围返回false
virtual bool setPos(int pos) = 0;
//
获取右边线性表第一个元素的值，并返回到参数中，获取成功返回true，否则返回false
virtual bool getValue(Elem &) const = 0;
//
打印线性表,可有可无
virtual void print() const = 0;
};

       线性表的实现由两种标准方法——顺序表和链表。接下来就学习一些顺序表和链表的实现，并对比两者的时间和空间效率。

最后

以上就是单纯音响为你收集整理的数据结构与算法分析(c++版) #2 初涉线性表的全部内容，希望文章能够帮你解决数据结构与算法分析(c++版) #2 初涉线性表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。