线性表
线性表的定义：是由称为元素的数据项组成的一种有限且有序的序列。这个定义中有序是指线性表中的每一个元素都有自己的位置。
线性表不含任何元素时，我们称之为空表(empty list)。当前储存的元素数目成为线性表的长度(length)。线性表的开始结点成为表头(head)，结尾结点成为表尾(tail)。表中的元素的值与它的位置之间可以有联系，也可以没有联系，因为线性表可以分为有序线性表和无序线性表。有序线性表元素按照值得递增顺序排列，而无序线性表在元素的值与位置之间就没有特殊的联系。
书中为了定义当前位置的概念，假设线性表由两个分离部分组成，这两部分被一个“栅栏”分开，这个栅栏与当前位置相对应。（本人把它理解为是迭代器指向的地方）。例如，<20, 23 | 12, 15>这个线性表的四个元素被栅栏分成两部分，左边有两个，右边也有两个。
下面是线性表的ADT。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43template <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++版)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复