数据结构——线性表

好记性不如一个赖笔头，上小学那会老师经常教育我们～也确实是这个道理，不总结写一遍总感觉缺点啥，最近在学习数据结构，为了加深记忆特意整理，不仅是便于日后自己查阅，也是分享给大家一块学习～后续会有树，栈和队列等一系列博客的更新。

线性表的定义：

由零个或多个数据元素组成的有限序列。1.它是一个序列，也就是说元素之间是有个先来后到的。2.若元素存在多个，则第一个元素无前驱，而最后一个无猴后继，其他元素都有且只有一个前驱和后继。3.另外线性表强调是有限的，事实上无论计算机发展到多强大，它所处理的元素都是有限的。

了解了定义之后，我们要学习线性表的抽象数据类型，先理解一个概念，抽象数据类型（Abstract Data Type，ADT），是指一个数学模型及定义在该模型上的一组操作。

抽象数据类型的标准格式：

ADT 抽象数据类型名

Data

数据元素之间逻辑关系的定义

Operation

操作

endADT；

接下来总结下线性表的抽象数据类型定义：

ADT 线性表（List）

Data

线性表的数据集合{a1，a2...}

Operation

InltList(*L):初始化操作，建议一个空线性表。

ListEmpty(L):判断线性表是否为空表，为空返回true，否则返回false。

GetElem（L,i,*e）:将线性表L中的第i个位置元素值返回给e。

ListInsert（*L,i,e）:在线性表L中第i个位置插入新元素e。

下面还有很多，删除等等操作。

线性表的顺序存储结构

两种物理存储结构：顺序存储结构和链式存储结构。

线性表的顺序存储结构指定的是用一段地址连续的存储单元一次存储线性表的数据元素。

接下来看一下线性表的顺序存储的结构代码

#define MAXSIZE 20

typedf int ElemType

typedf struct

{

ElemType data[MAXSIZE]

int length;//线性表的当前长度

}SqlList;

大家看到了，这里我们封装了一个结构，事实上就是对数组进行封装，增加了当前长度罢了。

地址计算方法

假设ElemType 占用的是C个存储单元（字节），那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是（表示获得存储位置的函数）：Loc（ai+1） = Loc（ai）+C.

线性表的顺序存储结构具有随机存储结构的特点，时间复杂度为O（1）

获得元素操作

实现GetElem的具体操作，既将线性表L中的第i个元素值返回。就程序而言非常简单，我们只需要把数组第i-1下表的值的返回即可。

插入元素操作

思路：如果插入位置不合理，抛出异常.如果线性表长度大于等于数组的长度，则抛出异常或者动态增加数组容量。从最后一个元素开始向前便利到底i个位置，分别将他们都向后移动一个位置。将要插入元素填入位置i处。线性表长+1。

插入操作

思路：

1.如果插入位置不合理，抛出异常。

2.如果线性表长度大于等于数组长度，则抛出异常或动态增加

删除元素

思路：

1.如果删除位置不合理，抛出异常。

2.取出删除元素。

3.从删除元素位置开始遍历到最后一个元素位置，别将它们都向前移动一个位置。

4.表厂-1。

现在我们分析一下插入和删除的时间复杂度，毕竟是研究算法吗嘛~

最好的情况：插入和删除操作刚好要求在最后一个位置操作，以为不需要移动任何元素，所以此时的时间复杂度为O（！）。

最坏的情况：如果要插入和删除的位置是第一个元素，那就以为这要移动所有的元素向后或者向前，所以这个时间复杂度为O（n）。

至于平均情况，由于元素插入到第i个位置，或删除第i个元素，需要移动n-i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就是说位置靠前，移动元素多，移动靠后，移动元素少。最终平均移动次数和最中间的那个元素移动次数相等，为（n-1）/2.

线性表的顺序存储结构，在存，读数据时，不管是哪个位置，时间复杂度都是O（1）。而在插入或删除时，时间复杂度都是O（n）。这就说明，它比较适合元素比较稳定，不经常插入和删除元素，而更多的操作是存储数据的应用。

线性表顺序存储结构的优缺点：

优点：

1.无须为表示表中的元素之间的逻辑关系而增加额外的存储空间。

2.可以快速的存取表中任意位置的元素。

缺点：

1.插入和删除操作需要移动大量元素。

2当线性表长度变化较大时，难以确定存储空间的容量。

3.容易造成存储空间的碎片。

线性表的链式存储结构

线性表的链式存储结构的特点使用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。

比起顺序存储结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（地址）。

也就是说除了存储其本身的信息外，还需要存储一个指示其直接后继的存储位置的信息。

我们把存储数据元素信息的域成为数据域，把存储直接后继位置的域成为指针域。指针域中存储的信息成为指针或链。这两部分信息组成数据元素成为存储印象，称为结点。因此此链表的每个结点中值包含一个指针域，所以叫做单链表。如下图：

对于线性表说，总得有个头有个尾，链表也不例外。我们把链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空（NULL）。