数据结构之线性表

一、线性表概述

1.1 线性表的定义

• 线性表是具有相同数据类型的 n (n>=0) 个数据元素的有限序列。其中 n 表示表长，当 n = 0 时表示该线性表是一个空表。
• 除第一个元素外，每个元素有且仅有一个直接前驱。
• 除最后一个元素外，每个元素有且仅有一个直接后驱。

1.2 线性表的特性

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，在序列各元素排序有其先后次序。
• 表中元素都是数据元素，每个元素都是单元素。
• 表中元素的数据类型都相同，这意味着每一个元素占有相同大小的存储空间。
• 表中元素具有抽样性，即仅讨论元素之间的逻辑关系，不考虑元素究竟表示什么内容。

1.3 线性表的基本操作

• InitList(&L)：初始化表，构造一个空的线性表。
• Length(L)：求表厂，返回线性表L的长度，即L中数据元素的个数。
• LocateElem(L, e)：按值查找，在表 L 中查找具有给定关键字值的元素。
• GetElem(L, i)：按位查找，获取表中第 i 个位置的元素的值。
• ListInsert(&L, i, e)：插入操作，在表 L 中第 i 个位置插入指定元素 e 。
• ListDelete(&L, i, &e)：删除操作，表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
• PrintList(L)：输出操作，按前后顺序输出线性表 L 的所有元素值。
• Empty(L)：判空操作，若 L 为空表，则返回 true ，否则返回 false 。
• DestoryList(&L)：销毁操作，销毁线性表，并释放线性表 L 所占用的内存空间。

二、线性表的顺序表示

2.1 顺序表的定义

• 线性表的顺序存储又称顺序表。
• 它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
• 一维数组可以是静态分配，也可以是动态分配。
• 静态分配需事先固定数组的大小和空间，空间占满时，再加入新的数据将产生溢出，导致程序崩溃。
• 动态分配时，在程序执行过程中通过动态存储分配语句分配存储数组的空间，空间占满时，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而扩充数组空间，而不是一次性地划分所有所需空间。

2.2 顺序表的特点

• 顺序表的最主要特点是随机访问，即通过首地址和元素序号可以在 O(1) 的时间内找到指定的元素。
• 顺序表的存储密度高，每个节点只存储数据元素。
• 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.3 顺序表基本操作

• 插入、删除、按值查找（顺序查找）

三、线性表的链式表示

• 链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻。
• 它是通过链建立数据元素之间的逻辑关系。
• 对线性表的插入、删除不需要移动元素，而只需要移动指针。

3.1 单链表的定义

• 线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。
• 由于单链表的元素是离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接查找表中某个特定的节点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
• 通常用头指针来标识一个单链表，如单链表 L ，头指针为 NULL 时表示一个空表，
• 为了操作上的方便，在单链表的第一个结点之前附加一个结点，称为头节点。

3.2 单链表基本操作

• 采用头插法建立单链表、通过尾插法建立单链表、按序号查找结点值、按值查找结点值、插入节点操作（分为前插操作、后插操作，常用后插操作），删除节点操作、求表厂操作。

3.3 双链表

• 双链表结点中有两个指针 prior 和 next ，分别指向其前驱结点和后驱节点
• 主要操作：双链表的插入操作、双链表的删除操作。

3.4 循环链表

• 循环单链表：循环单链表与单链表的区别在于，表中的最后一个指针不是 NULL，而改为指向头节点，从而使整个链表形成一个环。可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。
• 循环双链表：与循环单链表类似，但头节点的 prior 指针还要指向尾节点。

四、静态链表

• 静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next，这里的指针时结点的相对地址（数组下标），又称为游标。
• 和顺序表一样，静态链表也要预先分配一块连续的内存空间。
• 静态链表以 next = -1 作为其结束的标志。
• 静态链表的插入、删除操作与动态链表相同，只需要修改指针，而不需要移动元素。

五、顺序表和链表的比较

5.1 存取方式

• 顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。

5.2 逻辑结构与物理结构

• 采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相似。
• 链式存储时，逻辑上相邻的元素，其物理位置不一定相邻，其对应的逻辑关系时通过指针链接来表示的。

5.3 查找、插入和删除操作

• 对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为 O(n)，而当顺序表有序时，可采用折半查找，此时时间复杂度为 O(log n)。
• 对于按序号查找，顺序表支持随机访问，时间复杂度为 O(1)，而链表的平均时间复杂度为 O(n)。
• 顺序表的插入、删除操作，平均需要移动半个表厂的元素；链表的插入、删除操作，只需要修改相关结点的指针域即可。
• 由于链表每个结点带有指针域，因而在存储空间上的存储密度较小。

5.4 空间分配

• 顺序存储在静态分配情况下，需要预先分配较大的内存空间。预先分配过大，可能会导致顺序表后面大量闲置；预先分配过小，会造成溢出。
• 顺序表在动态分配情况下，虽然可以扩充存储空间，但需要移动大量元素，操作效率较低，而且内存中没有更大块的连续存储空间将导致分配失败。
• 链式存储的结点空间只需要的时候申请分配，只要内存有空间就可以分配，操作灵活、高效。

六、在实际中怎样选取存储结构

• 通常较稳定的线性表选择顺序存储，而频繁做插入、删除操作的线性表（即动态性较强）宜选择链式存储。

6.1 基于存储的考虑

• 对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度小于1。

6.2 基于运算的考虑

• 经常做按序号访问数据元素时，顺序表优于链表。
• 做插入和删除操作，当数据元素的信息量较大且表较长时，由于顺序表平均移动表中一般的元素，而在链表中主要是比较操作，从这个角度考虑，后者由于前者。

6.3 基于环境的考虑

• 顺序表易于实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单。

易错点

• 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。
• 顺序表和链表是指存储结构，两者属于不同层次的概念，莫要将其混淆。
• 线性表的顺序存储结构是一种随机存取的存储结构。