大家好，我是讯享网，很高兴认识大家。



 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p> 

讯享网

• 一、线性表的定义和特点及案例引入
• • 1.线性表的定义和特点
  • 2.案例引入
  • • (1) 一元多项式的运算
    • (2) 稀疏多项式的运算
    • (3) 图书信息管理系统
• 二、线性表的类型定义
• 三、线性表的顺序表示和实现
• • 1.初始化顺序表
  • 2.顺序表取值
  • 3.顺序表查找
  • 4.顺序表的插入
  • 5.顺序表的删除
  • 6.基本操作补充
  • 7.顺序表的特点
• 四、线性表的链式表示和实现
• • 1.链表介绍及单链表、双链表、循环链表基本定义
  • 2.三个典型问题
  • 3.链表的特点及优缺点
• 五、单链表
• • 1.单链表的定义和实现
  • 2.单链表的存储结构定义
  • 3.初始化单链表
  • 4.基本操作补充
  • 5.单链表的取值
  • 6.单链表的查找
  • 7.单链表的插入
  • 8.单链表的删除
  • 9.链表运算时间效率分析
• 六、循环链表
• • 1.循环链表的基本形态：
  • 2.循环链表特点
  • 3.循环链表的合并
• 七、双向链表
• • 1.双向链表基本形态及特点
  • 2.双向链表的插入
  • 3.双向链表的删除
• 八、顺序表和链表的比较
• 九、线性表的应用
• • 1.线性表的合并
  • 2. 顺序有序表的合并
  • 3.有序链表的合并
• 十、案例实现与分析
• • 1.多项式的创建
  • 2.多项式的相加
• 十一、单链表、循环链表、双向链表的时间效率的比较
• 十二、总结

---

线性表的知识是数据结构中的重点及基础，涉及到的知识会比较多，但对线性表的操作反复进行理解与实践会使你对线性表的理解更加深刻、学的更好。

因此当我们在存储上面两个多项式时，如果仍然使用顺序表进行存储，则缺点有：（1）存储空间分配不灵活。（2）运算的空间复杂度高。我们应该使用链式结构进行存储。

进行上面两个多项式的相加：

分析：首先我们从A的结点开始，往后一位则是指数为0，系数为7的结点，与B进行比较，发现B中没有指数为0的结点，我们不作处理，再对链表A后面的结点进行分析。发现链表A与链表B都有指数为1的结点，则将它们的系数相加放在链表A中。以此类推进行分析。过程与结果如下图：

对于图书信息管理系统，我们经常会有查找、插入、删除、修改、排序、计数等操作，用顺序表或链表存储图书信息的方式如下：

---

小结：
(1) 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
(2) 许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序,过于耗费成本。
(3) 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。

线性表主要分为顺序表与链表，它们的重要基本操作有初始化、取值、查找、插入、删除。顺序表的存储方式为随机存储，链表的存储方式为顺序存储。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻。

顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。

讯享网

图书表的顺序存储结构类型定义：

以下是对顺序表操作的具体步骤，对于简单的代码，在代码后面我注释说明；而相对复杂的代码，我再具体进行解释及说明。

方法1：参数为引用类型：

讯享网

方法2：参数用指针类型：

获取顺序表L中的某个数据元素的内容：

讯享网

这个算法的时间复杂度为O(1)。

在线性表L中查找值为e的数据元素:

要求顺序表查找算法的时间复杂度要先了解一个知识：什么是平均查找长度？（简称ASL），书上对平均查找长度有明确的解释，我这里就简单地解释一下。平均查找长度就是（每个元素**作的概率）乘以（最坏情况下n次到第i个元素的和除以2）。例如查找操作，假设一共有n个元素，因为每一个元素都有被查找的可能，因此概率为n分之1，假设最坏情况是循环第n次才找到该元素，因此时间复杂度就为n分之1乘以i的1到n的和。

在线性表L中第i个数据元素之前插入数据元素e：

讯享网

时间复杂度为O(n)。

将线性表L中第i个数据元素删除：

时间复杂度：O(n)。

销毁线性表L：

讯享网

清空线性表L：

求线性表L的长度：

讯享网

判断线性表L是否为空：

(1) 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致。

(2) 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等。

这种存取元素的方法被称为随机存取法。

优点：
(1) 存储密度大（结点本身所占存储量/结点结构所占存储量）。
(2) 可以随机存取表中任一元素。

缺点：
(1) 在插入、删除某一元素时，需要移动大量元素。
(2) 浪费存储空间。
(3) 属于静态存储形式，数据元素的个数不能自由扩充。

因此，为了克服顺序表的缺点而产生了。

结点：数据元素的存储映像。由数据域和指针域两部分组成。
链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。

链式存储结构定义：
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。

线性表的链式表示又称为非顺序映像或链式映像。

头指针、头结点、首元结点：
头指针是指向链表中第一个结点的指针。
首元结点是指链表中存储第一个数据元素a1的结点。
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息。

链表有两种表现形式：头结点的有无。

链表（链式存储结构）的特点：
(1) 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
(2) 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。

这种存取元素的方法被称为顺序存取法。

优点：
(1) 数据元素的个数可以自由扩充。
(2) 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高。

缺点：
(1) 存储密度小。
(2) 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）。

• 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。
• 若头指针名是L，则把链表称为表L 。
  
  
  

讯享网

• 指针变量p：表示结点地址。
• 结点变量*p：表示一个结点。

单链表的销毁：

讯享网

清空单链表

求单链表表长

讯享网

判断表是否为空

链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。

讯享网

1.返回L中值为e的数据元素的地址，查找失败返回NULL。

2.返回L中值为e的数据元素的位置序号，查找失败返回0。

讯享网

1.任意位置插入：

2.头插法

算法步骤：

讯享网

3.尾插法

讯享网

1.查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。
2.插入和删除: 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
3.但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。

从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到。

对循环链表，有时不给出头指针，而给出尾指针，可以更方便的找到第一个和最后一个结点。

首先设置一个指针指向第一个链表的头结点处，连接各个元素，连接完毕后去掉第二个链表的头结点，即完成循环链表的合并。

讯享网

讯享网

此表不需要记，理解即可。

问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合。

讯享网

总结：顺序有序表的合并与链式有序表的合并的时间复杂度都为O(m+n)。因为顺序有序表合并时需要开辟另一个存储空间，因此合并顺序有序表的空间复杂度为O(m+n)，而合并链式有序表只需将前后地址修改即可，没有开辟新的存储空间，因此空间复杂度为0(1)。

讯享网

• 掌握线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。
• 熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。
• 熟练掌握顺序表的查找、插入和删除算法 。
• 能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合 。

---

原创不易，如果此篇文章对您了解数据结构的线性表有帮助，麻烦点个赞支持一下谢谢。