Question

数据结构 线性表

Answer 1

本文主要内容：线性表的逻辑结构和存储结构以及相应 算法 ；

由N（N>=0）个数据特性相同的元素构成的有限序列称为线性表。N为线性表长度，当N为0时就是空表。

非空线性表或是线性结构，其的 特点 是：

线性表的顺序表示和实现
线性表的顺序表：指的是用一组 地址连续 的存储单元依次存储线性表的数据元素。（这种表示又叫线性表的顺序存储结构或顺序映像）Sequential List

逻辑上相邻的元素，物理上也相邻 ；

公式：Loc（ai）=Loc(a0）+（i-1）x L
所以只要确定了一个元素的位置，表中任意元素都可以 随机存取 ，因此线性表是一种随机存取的存储结构。
存取的时间复杂度为O(1).

缺点： 插入和删除费时，需要移动大量的元素，长度固定。

线性表的链式存储结构的特点：
用一组任意的存储单元（可连续可不连续）存储线性表的数据元素，存储时需要额外的存储单元存储后继元素的信息。

每个存储的元素称为 节点 （Node），它由两部分组成：

由n个节点链结成一个链表，即为链式的线性表。

根据链表所含的指针个数，指针指向，指针连接方式，将链表分为：

其中单链表、循环链表、双向链表用于实现线性表的链式存储结构，其他链表多用于实现树和图等非线性结构。

4.1 单链表
单链表的存取必须从 头指针 开始进行，头指针指示链表的第一个节点，最后一个元素的指针为空NULL。
特点：

一般为了处理方便，会在单链表的第一个节点之前设置一个 头结点 ，该头结点的数据域可以不存储任何信息，也可以存储线性表的长度信息或其它附加信息，头结点的指针域存储指向第一个节点的指针。

示例：
指针头: H –>31，如果H指向null表示为空表；

要取得第i个数据元素必须从头指针出发顺链进行寻找,所以单链表是顺序存取的存取结构。

查找算法 ：

插入算法 ：
将值为e的节点插入到第一个节点的位置上即ai-1和ai之间 - 找到ai-1节点，并有指针p指向该节点；

删除算法 ： 时间复杂度为O（n），主要时间在查找ai-1

单链表的创建：
链表从一个空表开始，动态的不断插入数据，形成链表；

4.2 循环链表
另一种链式存储，特点是表中的最后一个节点的指针，指向头节点，整个链表的形式形成一个环。从表中任意节点出发都可以找到其他节点。
合并两个循环链表时，只需要表1的尾->表2的第一个节点（释放表2的头节点），表2的尾指针->表1的头节点。

4.3 双向链表
修改节点的结构，之前的节点只有后继指针，现在给节点添加上前驱指针
双向链表的节点结构：

双向链表也有循环链表叫双向循环链表

两个线性表La和Lb: La长度为m,Lb 的长度为n；

假设GetElem和ListInsert与表长无关，LocateElem执行的时间与表长成正比，则时间复杂度为O（m*n）

调用

结果

时间复杂度O(m n）；
需要开辟新的辅助空间，所以空间复杂度也为O（m n）；