线性表介绍

将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

线性表具有以下特点

* 有限的序列
* 使用线性表存储的数据必须具有相同的数据类型。即要么全都是整形，要么全都是字符串。一半是整形，一半是字符串的一组数据无法使用线性表存储。
* 可以是有序的也可以是无序的。可以把线性表理解成一队学生，可以让这些学生根据身高从小到大排列，也可以随机排成一列

线性表常用术语

* 某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”；
* 某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”；

存储结构

线性表的存储结构有顺序存储结构和链式存储结构两种，前者称为顺序表，后者称为链表。

1.顺序表

顺序表就是将数据依次存储在连续的整块物理空间中。
顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组。

// 顺序表的结构体定义
typedef struct Table{
    int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length;//记录当前顺序表的长度
    int size;//记录顺序表分配的存储容量
}table;

顺序表的优点

* 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
* 可以快速地存取表中任一位置的元素

顺序表的缺点

* 插入和删除操作需要移动大量元素
* 当线性表长度变化较大时，难以确定存储空间的容量
* 造成存储空间碎片

2.链表

链表就是数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系。

顺序表最大的缺点就是插入和删除某一元素时都需要移动大量的元素，这是很耗费时间的。这是由于相邻两元素的存储位置具有相邻关系，他们在内存中的位置也是挨着的，
中间没有空虚，不能直接进行插入，要想进行插入，需要先把其他元素进行挪动，同理，若删除某个元素以后，就会流出空隙，也是需要移动其他元素进行补齐。
为了改善顺序表的缺点，让元素之间的位置不必相邻，内存中的位置也不必相邻，我们把这种存储结构称为链式存储结构。

链表中每个数据的存储都由以下两部分组成：

1) 数据元素本身，其所在的区域称为数据域；
2) 指向直接后继元素的指针，所在的区域称为指针域；

2.1 单链表

链表的每个结点中只包含一个指针域，所以叫做单链表。

有的链表带有头结点，有的不带头结点，头节点的数据域可以不存储任何信息，可以存储线性表长度等附加信息，头节点的指针域存储指向第一个结点的指针。
当链表是带有头结点的时候，就相当于火车头一样的存在，只是用来表明列车顺序开始的方向，并不乘坐客人。（链表一般都是包含头结点的）

单链表结点定义

typedef struct LNode
{
    int data;              //data中存放结点数据域
    struct LNode *next;    //指向后继结点的指针
}LNode; 

2.2 静态链表
用数组描述的链表，即称为静态链表。
在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。

2.3 循环链表

2.4 双向链表

3. 顺序存储和链式存储比较

链表操作

参考
https://juejin.im/post/5b5130c6f265da0f84561fcd
http://data.biancheng.net/view/157.html

数据结构与算法--线性表

原文：https://www.cnblogs.com/vivian187/p/13368451.html