【线性表】（List）

本文围绕以下三个部分展开：

一、线性表（List）
二、顺序存储结构
三、链式存储结构






一、线性表（List）

        1. 概念

        线性表：0个或多个数据元素的有限序列。（像线一样性质的表）

            线性表的每个数据元素的类型都是相同的。

            A. 是一个序列。（元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。）

            B. 元素个数是有限的。

            类比：幼儿园小朋友按次序排队。


        2. 线性表的抽象数据类型

        （1）基本操作：

        抽象数据类型定义如下：

        （2）复杂的个性化操作

        例题：union操作（实现两个线性表集合A和B的并集操作）

        思想：把存在在集合B中但不存在在A中的数据元素插入到A中即可。即：循环集合B中的每个元素，判断当前元素是否存在A中。若不存在，则插入到A中即可。

二、顺序存储结构

        1. 顺序存储

        指用一段地址连续的存储单元依次存储线性表的数据元素。

        2. 顺序存储方式

        在内存中找了块地儿，通过占位符的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。

        使用一维数组来实现顺序存储结构。即：把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。


        3. 顺序存储结构代码和三个属性

        4. 地址计算方法

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

        （1）数据元素的序号和存放它的数组下标之间的对应关系：

        （2）假设一个数据元素占c个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置的关系：

        第i个数据元素的存储位置和第1个数据元素的存储位置的关系：

        （3）随机存取结构：可以随时算出线性表中任意位置的地址，存取时间复杂度均为O(1)，具有这样特点的存取结构称为随机存取结构。


        5. 获得元素的操作（GetElem）：将线性表L中第i个位置元素值返回。

        6. 插入某个数据元素

        7. 删除某个数据元素

        8. 优缺点

三、链式存储结构

        1. 特点：

        用一组任意的存储单元存储线性表的数据元素。这组存储单元可以连续，也可以不连续。意味着，这些数据元素可以存放在内存中未被占用的任意位置。


        2. 数据域、指针域、指针/链、结点

        3. 头结点、头指针

        （1）头指针：链表中第一个结点的存储位置。

        链表最后一个结点的指针为空（NULL/"^"）

        （2）头结点：为了更方便地对链表进行操作，在单链表的第一个结点前附设的一个结点。

        数据域可以不存储任何信息，也可以存储如线性表长度等附加信息。

        指针域存储指向第一个结点的指针。

        （3）二者的异同

        4. 分类

        链式存储结构又有不同形式，分为：单链表、静态链表、循环链表和双向链表。






整理时重点参考：《大话数据结构》程杰著