线性表

1、定义

   《大话数据结构》里面对线程表的定义为：零个或多个数据元素的有限序列。

    用专业的数学语言可表述如下：若将线性表记为(a1,...,ai-1,ai,ai+1,...,an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,...,n-1时，ai有且仅有一个直接后继。当i=2,3,...,n时，ai有且仅有一个直接前驱。

2、线性表的分类

    线性表按存储结构可分为：顺序存储结构和链式存储结构。

    线性表按表现形式可分为：单链表、双链表、循环链表。

    顺序存储结构一般用数组实现；链式存储结构一般用指针实现。还有一种特殊的线程表，用数组实现链式结构，叫做静态链表。

3、线程表的常见操作

    1）创建空线性表；2）判断是否为空；3）清空；4）获取指定位置的元素；5）查找指定的元素；6）插入元素；7）删除元素；8）获取表的长度。

4、特殊的线性表

    根据线性表的定义：栈、队列、字符串都可以看成是特殊的线程表。所以，栈、队列、字符串既可以用顺序存储结构实现，也可以用链式存储结构实现。

4.1 两栈共享空间

    由于顺序存储结构扩展存储空间不方便。为了克服它的缺陷，对于两个同类型栈，会设计成两栈共享空间。如下图所示。(注：top1和top2分别为栈1和栈2的栈顶指针）

    栈空的条件：top1或top2等于-1

    栈满的条件：top1+1==top2

4.2 循环队列

    对于队列，会设计成循环队列。如下图所示。（注：front指针指向队头元素，rear指针指向队尾元素的下一个位置）

    队列空的条件：front==rear

    队列满的条件：front == (rear+1) % QueueSize