数据结构第二章便讲了线性表，其实我们常说线性表一般为数组和链表，熟不知线性表其实是一种逻辑结构，而链表和数组分别是两种存储结构（非顺序和顺序映像）。

先说线性结构，线性结构是在数据元素的非空有限集中：

1.存在唯一的一个被称作“第一个”的数据元素；

2.存在惟一的一个被称作“最后一个”的数据元素；

3.除了第一个之外，集合中的每一个数据元素均只有一个前驱；

4.除了最后一个之外，集合中每个数据元素均只有一个后继。

其实以上四条便是线性表的特征，这四句罗利啰嗦的话就是描述了一条线性的，有前驱后继的数据结构。

线性表是n个数据元素的有限序列，在稍复制的线性表中，一个数据元素（一个结点）可以由多个数据项组成。

线性表中元素的个数n（n>=0）定义为线性表的长度，n=0时称为空表。在非空表中的每一个数据元素都有一个确定的位置（只有这样才方便查找）。

线性表是一种非常灵活的数据结构，它的长度可以根据需要而变化，对线性表的数据元素，不仅可以询问、修改，还可以插入和删除（如果这几个功能线性表都不能完成，还学它何用？）。其实对于线性表，或者说包括其他各种数据结构，建立和访问是基础，不会建立和访问可以说对这种数据结构完全不懂，加上会修改可以说能用这种数据结构，再加上会删除才可以说会用这种数据结构，再加上能抽象出自己的应用模型、活用才能说掌握了这一种数据结构。

线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素（就像数组）。

第i+1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC（ai）之间满足：

LOC（ai+1）=LOC（ai）+ l；

一般来说，线性表的第i个数据元素ai的存储位置为

LOC（ai）=LOC（a1）+ l*（i-1）；

（l为每个元素的需占的存储单元，LOC（a1）为线性表的第一个元素的存储位置，通常被称作相性表的起始位置（废话）和基地址）。

线性表的这种机内表示称作线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表，其特点是为表中相邻的元素ai和ai+1赋以相邻的存储位置LOC(ai)LOC(ai+1)。（其实就是通过元素在计算机内物理位置相邻来表示线性表中的数据元素之间的逻辑关系）。

数据结构一半是怎么存储，一半是怎么运用（算法），线性表的基本操作包括插入，删除。插入就是把元素x插入i位置后，其i到n的元素向后移动1个单位；删除：把第i个元素x删除后，第i+1到n元素向前移动1个单位。

当顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间消耗主要在移动元素上（换句话说，移动元素的操作为估计算法时间复杂度的基本操作），而移动元素的次数取决于插入或者删除元素的位置。

线性表的顺序存储结构可以方便的存取任一元素，但也造成了做插入删除操作时需要移动大量元素的缺点。

而链式存储结构，由于不要求逻辑上相邻的元素也在物理位置也相邻，没有顺序存储结构如上所具有的弱点，但同时也失去了快速的、直接访问的优点。

每个结点包括数据域，存储后继存储元素位置的域称之为指针域。

因为每个结点只包括一个指针与，故又称线性链表或单链表。

在研究链表的时候，我们只关心其逻辑顺序而不管实际机内位置。

关于链表的操作，插入：只需要修改第i-1个元素结点的指向地址和要插入的数据元素x的指向地址；删除，只需要修改第i-1个元素的指向地址，然后释放结点。

操作有点泛泛而谈，其实链表有很多活用的地方，甚至连建立链表也有头插法（逆向建链表）和尾插法（正向建链表）之分。

如果不用指针，可以使用游标来代替指针指示结点在数组中的相对位置，但这种存储结构需要分配出一个足够大的内存空间，为了和指针型链表相区别，我们给这种用数组来描述的链表起名叫做静态链表（前向星便是基于静态链表）。

对于静态链表，如果在删除操作之后，需要辨明数组中那些分量未被使用，解决的办法是将所有未使用的以及删除的用游链表或者一个备用链表每当进行插入时便可以从备用链表上取得第一个结点作为待插入的新结点。（类似专用来记录未被使用的元素下标的栈）。

尾巴指向头的链表为循环链表，当然静态链表也可以用去模来实现循环链表。

因为单链表有着只能从头到尾的单向性，在某些情况，会造成不便，因此，双向链表诞生了。其只不过是多了一个指向前一个结点的指针，操作比单向链表多了一点操作。

一元多项式的表示和相加（线性表的一个应用）

在数学上，一个余元多项式Pn（x）可按升幂写成：

Pn（x） = p0+p1x+p2x^2+.....+pn*n^n;

它可由n+1个系数来唯一确定。因此，在计算机里，它可用一个线性表p表示：p = （p0,p1,...,pn）;

不失一般性，多项式的相加减便可以用一对线性表来表示计算

但这样计算也有弊端，比如计算

S（x） = 1 + 3 * x^10000 + 2 * 3 * x^20000时，将浪费大量的内存（p1-p9999都是0）。这时，如果采用每个数据元素有系数和指数两个数据，那么将节省大量内存，当然，也会浪费查找带来的时间。

当然，这只是提供了一个思路，也算相性表的一个应用，线性表是一种十分灵活的数据结构，至于怎么用，全靠编程者个人，这也是为什么可以说数据结构可以成为使用者的艺术。