3.2 线性表的定义
线性表，从名字上你就能感觉到，是具有像线一样的性质的表。
零个或多个数据元素的有限序列。
这里需要强调几个关键的地方。
首先它是一个序列，也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
线性表强调是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学概念中。
线性表元素的个数
n(n>=0)定义为线性表的长度，当n=0时，称为空表。
在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。
在较复杂的线性表中，一个数据元素可以由若干个数据项组成。
3.4 线性表的顺序存储结构代码
3.4.1 顺序存储定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
3.4.2 顺序存储方式
线性表的顺序存储结构，就是在内存中找了块地，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
为了建立一个线性表，要在内存中找一块地，于是这块地的第一个位置就非常关键，他是存储空间的起始位置。
这里，我们就发现描述顺序存储结构需要三个属性：
- 存储空间的起始位置：数组
data，它的存储位置就是存储空间的存储位置。- 线性表的最大存储容量：数组长度
MaxSize。- 线性表的当前长度：
length.
3.4.3 数据长度与线性表长度区别
数组长度就是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。
3.4.4 地址计算方法
线性表的起始也是1，可C语言中的数组却是从0开始第一个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组元素下标之间存在对应关系
用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。
其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。存储器中的每个存储单元都有自己的编号，这个编号称为地址。当我们占位后，占座的第一个位置确定后，后面的位置都是可以计算的。
由于每个数据元素，不管它是整型，实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)。
LOC(ai+1) = LOC(ai) + c
所以对于第i个数据元素ai的存储位置可以由a1推算得出：
LOC(ai) = LOC(ai) + (i - 1) * c
通过这个公式，你可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或则取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存储结构。
3.5 顺序存储结构的插入语删除
3.5.1 获得元素操作
对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。
3.5.2 插入操作
如果我们要实现ListInsert(*L,i,e),即在线性表L中的第i个位置插入新元素e。
插入算法的思路：
- 如果插入位置不合理，抛出异常。
- 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量。
- 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
- 将要插入元素填入位置i处
- 表长加1
3.5.2 删除操作
如果我们要实现ListInsert(*L,i,e),即在线性表L中的第i个位置插入新元素e。
删除算法的思路：
- 如果删除位置不合理，抛出异常
- 取出删除元素。
- 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。
-
表长减1
现在我们来分析一下，插入和删除的时间复杂度。
先来看最好的情况，如果元素要插入到最后一个位置，或者删除最后一个元素，此时，时间复杂度为O(1),因为不需要移动元素的。
最坏的情况，如果元素要插入到第一个位置或者删除第一个元素，那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为O(n)。
至于平均的情况，由于元素插入到第i个位置，或删除第i个元素，需要移动n-i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为(n-1)/2。
可以得出，平均时间复杂度还是O(n)。
线性表的顺序存储结构，在存，读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入和删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存储数据的应用。
3.5.4 线性表顺序存储结构的优缺点
- 优点
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速的存取表中任一位置的元素
- 缺点
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
*造成存储空间的碎片
3.6 线性表的链式存储结构
3.6.1 顺序存储结构不足的解决办法
顺序存储结构最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。
考虑一下导致这个问题的原因：
就在于相邻两元素的存储位置也具有邻居关系。它们编号是1,2,3，.....，n,它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。
3.6.2 线性表链式存储结构定义
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。
为了表示每个数据元素ai与其直接后继数据元素ai + 1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。
n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2,a3,.....，an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。
我们把链表中第一个结点的存储位置叫做头指针。
线性链表的最后一个节点指针为“空”(通常用NULL来表示)。
有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个节点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。
3.6.3 头结点与头指针的异同
- 头指针
- 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
- 头指针具有标识作用，所以常用头指针冠以链表的名字
- 无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
- 头结点
- 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义。
- 有了头结点，対在第一元素结点前插入结点和删除第一节点，其操作与其他结点的操作就统一了。
- 头结点不一定是链表必须要素。
3.6.4 线性表链式存储结构代码描述
若线性表为空表，则头结点的指针域为"空"。
