线性表简介

什么是线性表？
线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract)，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系，即：（ 1）除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素；（ 2）除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。也就是说，数据元素是一个接一个的排列。因此，可以把线性表想象为一种数据元素序列的数据结构。
线性表就是位置有先后关系，一个接着一个排列的数据结构。

线性表的抽象数据类型定义如下：
ADT 线性表（List）
Data
线性表的数据对象集合为（a1,a2,a3,…,an），每一个元素类型均是DataType其中，除第一个元素a1外，每个元素只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素，数据元素之间的关系是一对一的关系
Operation
InitList( L) : 初始化操作建立一个空的线性表L
IsEmpty() : 若线性表为空，返回true，否则返回false，，，
Clear() : 将线性表清空
LocalElem(L，i) 在L表中查找i，如果查找成功，返回索引，若不存在返回-1
Insert(L ,i,e) 在L表中第i个位置，插入新元素 e
Delete(i) 删除中的第i个元素
Length() 返回线性表的长度
endADT

线性表的顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素
顺序表
在计算机内，保存线性表最简单、最自然的方式，就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储(Sequence Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表(Sequence List)，如图所示。顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻

存储器中没有存储单元都有自己的编号，这个编号称为地址，，，

线性表顺序结构的优缺点：
优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间，可以快速地存取表中任一位置的元素
缺点：插入和删除操作需要移动大量的元素，当线性表的长度变化较大是，难以确定存储空间的容量，造成存储空间的“碎片”

为了表示每个数据元素ai 与其后直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，处理存储其本身的信息之外，还需存储一个指示其后继的信息（即直接后继的存储位置），，我们把存储数据元素信息的域称为数据域，吧存储直接后继位置的域称为指针域，指针域中存储的信息叫指针或者链，这两个部分信息组成数据元素ai的存储映像，称为结点（Node）
链表中第一个节点的存储位置叫头指针

单向链表的存储方式示意图：

循环链表
有些应用不需要链表中有明显的头尾结点。在这种情况下，可能需要方便地从最后一个结点访问到第一个结点。此时，最后一个结点的引用域不是空引用，而是保存的第一个结点的地址（如果该链表带结点，则保存的是头结点的地址），也就是头引用的值。带头结点的循环链表(Circular Linked List)如图所示。

双向链表
双向链表(double linked list) 是在单链表的每个结点中，在设置一个指向其前驱节点的指针域

静态链表
首先让数组的元素都是由两个数据域组成的，data和cur，，也就是说，数组的每个下标都对应一个data和一个cur，数据域data用来存放数据元素，也就是我们通常处理的数据，而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，
我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法

静态链表优缺点：
优点：在插入和删除操作是只需要修改游标，不需要移动元素，从而改进在顺序存储结构中的插入和删除操作需要移动大量的元素移动，，，
缺点：没有解决连续存储分配带来的表长难以确定的问题，失去了属性存储结构随机存取的特性，，，

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78066057