线性表

mozzie大约 4 分钟

线性表是一种基本且常用的数据结构，它体现了数据元素之间一对一的线性关系。

什么是线性表？

由同类型数据元素构成有序序列的线性结构

表中元素个数称为线性表的长度
线性表没有元素时，成为空表
表起始位置称表头，表结束位置称表尾

类型名称：线性表(List)

数据对象集：线性表是 n(≥0)个元素构成的有序序列(a₁，a₂，......，a_n)

操作集：线性表 L∈List，整数 i 表示位置，元素 X∈ElementType，线性表基本操作主要有：

顺序存储结构

数组

数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。

查询较快，增删较慢，增加每一个元素都要后移，删除每一个元素都要前移。

单链表(LinkList)

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」

元素无需按顺序排列，只要上一个元素指向下一个元素即可

创建链表：每一个链表的空间和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

单链表结构与顺序存储结构的优缺点：

存储分配方式：
- 顺序存储结构用一段连续存储单依次存储线性表的数据元素
- 单链表采用链式存储结构，用一任意的存储单元存放线性表的元素
时间性能：
- 查找
  - 顺序存储结构 O(1)
  - 单链表 O(n)
- 插入和删除
  - 顺序存储结构需要平均移动长一半的元素，时间复杂度为 O(n)
  - 单链表在找出位置的指针后插入和删除时间复杂度仅为 O(1)
空间性能： - 顺序存储结构需要预分配存储间，分大了，浪费；分小了，易发生上溢 - 单链表不需要分配存储空间，只有就可以分配，元素个数不受限制若线性表需要频繁查找，很少进行插入和操作时，宜采用顺序存储结构，反正使用单结构当线性表中的元素个数变化较大或者根本知道有多大时，最好用单链表结构。

静态链表

用数组描述的链表叫做静态链表，数组的每个下标都对应一个 data 和 cur，数据域 data 用来存放数据元素，游标 cur 用来指向该元素的后继(类似单链表中的 next 指针)

静态链表创建

#define MAXSIZE 1000 /* 存储空间的初始分配量 */

/* 线性表的静态链表存储结构 */
typedef struct
{
    Elemtype data;
    int cur;			/* 游标(cursor)，为0表示无指向 */
} Component,StaticLinkList[MAXSIZE];

第一个跟最后一个元素不存数据

第一个 cur 存储空闲空间第一个结点的下标，最后一个 cur 存储第一个元素的下标

第一个 cur 指向备用链表的第一个结点，最后一个 cur 指向第一个数据

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

循环链表

将单链表中终端节点的指针指向头结点，形成一个环，这就是循环链表

双向链表

在单链表的每个节点中在设置一个前驱指针，两个指针一个指向后继节点，一个指向前驱节点