摘要：线性表的基本运算置空表，构造一个空的线性表。三线性表的链式存储结构单链表线性链表链式存储结构除了存储本身的信息之外，还需要一个存储指示其后继元素存储位置的指针，由这两个部分组成元素的存储映像通常称为结点。用这种方法存储的线性表称为链表。
目录
今天我们来学习数据结构的第2章——线性表。线性表是最简单和最常用的一种数据结构，所以这一章是数据结构当中的重点内容，小伙伴们一定要熟练掌握！本文主要介绍基本概念，算法和代码实现不过多赘述。
1）线性表的定义
线性表是由 个数据元素（结点） 组成的有限序列。其中，数据元素的个数 为表的长度。当 为零时称为空表。
2）线性表的逻辑特征
对于一个非空的线性表：
① 有且仅有一个称为开始元素的 ，它没有前趋，仅有一个直接后继 ；
② 有且仅有一个称为终端元素的 ，它没有后继，仅有一个直接前趋；
③ 其余元素 称为内部元素，它们都有且仅有一个直接前趋 和一个直接后继 。
（1）置空表 InitList(L)，构造一个空的线性表 L。
（2）求表长 ListLength(L)，返回线性表 L 中元素个数，即表长。
（3）取表中第 个元素 GetNode(L，i)，若1ListLength(L)，则返回第 个元素 。
（4）按值查找 LocateNode(L，x)，在表 L 中查找第一个值为 的元素，并返回该元素在表 L 中的位置，若表中没有元素的值为 ，则返回 0 值。
（5）插入InsertList(L，i，x)，在表 L 的第 个元素之前插入一个值为 的新元素，表 L 的长度加1。
（6）删除DeleteList(L，i)，删除表 L 的第 个元素，表 L 的长度减1。
线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。顺序表是一种随机存取结构。
1）插入运算
线性表的插入运算是指在线性表的第 -1 个元素和第 个元素之间插入一个新元素 ，使长度为 的线性表：
()
变为长度为 +1 的线性表：
()
！插入是向后移动元素。
2）删除运算
线性表的删除运算是指将表中第 个元素删除，使长度为 的线性表
()
变为长度为 -1 的线性表：
()
！删除是向前移动元素。
链式存储结构除了存储 本身的信息之外，还需要一个存储指示其后继元素 存储位置的指针，由这两个部分组成元素 的存储映像通常称为结点。它包括两个域：存储数据元素的域称为数据域，存储直接后继存储地址的域称为指针域。用这种方法存储的线性表称为链表。
个结点链成一个链表，即为线性表（）的链式存储结构。由于这种链表的每个结点只包含一个指针域，因此又称为单链表。
1）建立单链表
建立单链表的常用方法有两种：头插法和尾插法。
① 头插法建表
头插法建表是从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。
② 尾插法建表
尾插法是将新结点插入在当前链表的表尾上，因此需要增设一个尾指针 rear，使其始终指向链表的尾结点。
2）查找运算（带头结点）
① 按结点序号查找
在单链表中要查找第 个结点，就必须从链表的第1个结点（开始结点，序号为1）开始，序号为 0 的是头结点，p 指向当前结点，j 为计数器，其初始值为1，当 p 扫描下一个结点时，计数器加1。当 j= 时，指针 p 所指向的结点就是要找的结点。
② 按结点值查找
在单链表中按值查找结点，就是从链表的开始结点出发，顺链逐个将结点的值和给定值 k 进行比较，若遇到相等的值，则返回该结点的存储位置，否则返回 NULL。
3）插入运算
链表插入时不需要移动结点，但需要用移动指针来进行位置查找。
4）删除运算
链表删除和插入同理，不需要移动结点，但需要移动指针。
循环链表的特点是单链表中最后一个结点（终端结点）的指针域不为空，而是指向链表的头结点，使整个链表构成一个环。
双向链表的特点是在单链表的结点类型中增加一个指向其直接前趋的指针域。这样形成的链表中就有两条不同方向的链。因此称之为双向链表。
顺序表可以随机存取表中任一元素，插入和删除操作时需移动大量元素。链表插入和删除不用大量移动元素，但失去了随机访问的特点。
顺序表查询快，增删慢；链表查询慢，增删快。
在实际问题中，若经常对线性表进行查找操作，则以顺序表存储为宜。若经常对线性表进行插入和删除操作，则以链表存储为宜。
顺序表的存储空间是静态分配的，设置过大将产生空间浪费，设置过小会使空间溢出，因此顺序存储结构适合对数据量大小能事先知道的应用问题。
而链表的存储空间是动态分配的，只要内存有空闲空间，就不会产生溢出，因此链式存储结构适合数据量变化较大的动态问题。
ps：博主创作不易，如果喜欢就点个赞吧！ღ( ´･ᴗ･` )比心
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/122177.html
新编html网页设计从入门到精通共分为21章，全面系统地讲解了html的发展历史及4.0版的新特性、基本概念、设计原则、文件结构、文件属性标记、用格式标记进行页面排版、使用图像装饰页面、超链接的使用、使用表格组织页面、使用多媒体美化页面、创建多框架页面、动态网页的制作、使用层叠样式表(css)美化页面、javascript语言、数组和字符串以及表达式与程序的流程控制等内容。 本书适合作为培训学校的...
摘要：贡献者飞龙版本最近总是有人问我，把这些资料看完一遍要用多长时间，如果你一本书一本书看的话，的确要用很长时间。为了方便大家，我就把每本书的章节拆开，再按照知识点合并，手动整理了这个知识树。 Special Sponsors showImg(https://segmentfault.com/img/remote/1460000018907426?w=1760&h=200); 贡献者：飞龙版...
摘要：主成分分析就是降维，通过线性组合，把多个原始变量合并成若干个主成分，这样每个主成分都变成原始变量的线性组合。相关系数系数为为为。从结果看，这个数据可能不太适合用来分析，因为降到维后的代笔性不足。 这两天用学了主成分分析，用的是PCA。主成分分析就是降维，通过线性组合，把多个原始变量合并成若干个主成分，这样每个主成分都变成原始变量的线性组合。所以你想看具体哪个特征对结果的影响大，通过PC...
摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...
阅读 1086·2021-11-18 13:23
阅读 801·2021-11-08 13:16
阅读 933·2021-10-11 10:58
阅读 3552·2021-09-22 15:26
阅读 1792·2021-09-08 10:42
阅读 1875·2021-09-04 16:45
阅读 1783·2019-08-30 15:54
阅读 2610·2019-08-30 13:45
