大话数据结构 第三章 线性表 简介
线性表的定义
线性表（List）：零个或多个数据元素的有限序列。
①首先它是一个序列。元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
②线性表强调是有限的。
若将线性表记为（
文章图片
,...,
文章图片
,
文章图片
,
文章图片
,...,
文章图片
），则表中
文章图片
领先于
文章图片
，
文章图片
领先于
文章图片
，称
文章图片
是
文章图片
的直接前驱元素，
文章图片
是
文章图片
的直接后继元素。当 i = 1,2,...,n-1时，
文章图片
有且仅有一个直接后继，当 i = 2,3,...,n 时，
文章图片
有且仅有一个直接前驱。
线性表元素的个数 n （n >= 0）定义为线性表的长度，当n=0时，称为空表。
在较复杂的线性表中，一个数据元素可以由若干个数据项组成。
线性表的顺序存储结构
顺序存储定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
所以可以用一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
顺序存储结构需要三个属性：
①存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
②线性表的最大存储容量：数组长度MaxSize。
③线性表的当前长度：length。
数据长度与线性表长度区别
“数组的长度”和“线性表的长度”需要区分一下。
数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。（一般高级语言，可以用编程手段实现动态分配数组，不过这会带来性能上的损耗。）
线性表的长度线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
所以，在任意时刻，线性表的长度应该小于等于数组的长度。
地址计算方法
存储器中的每个存储单元都有自己的编号，这个编号称为地址。
假设每个数据元素占用c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素存储位置满足下列关系（LOC表示获得存储位置的函数）。
LOC(
文章图片
)=LOC(
文章图片
)+c
所以：
LOC(
文章图片
)=LOC(
文章图片
)+(i-1)*c
通过这个公式，可以随时算出线性表中任意的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。
顺序存储结构的插入与删除
获得元素操作
我们将线性表中的第index个位置元素值返回，只要index数值在数组下标范围内。
文章图片
插入操作。
插入算法的思路：
①如果插入位置不合理，抛出异常。
②如果线性表长度大于等于数组长度，则抛出 异常或动态增加容量。
③从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
【大话数据结构 第三章 线性表 简介】④将要插入元素 填入位置i处。
⑤表长加1。
以list的insert为例：
文章图片
删除操作：
删除算法思路：
①如果删除位置不合理，抛出异常。
②取出删除元素。
③从删除元素位置开始遍历到最后一个元素，分别将它们都向前移动一个位置。
④表长减1。
文章图片
线性表顺序存储结构的优缺点
优点：
①无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
②可以快速地存取表中任意位置的元素。
缺点：
①插入和删除操作需要移动大量元素。
②当线性表长度变化较大时，难以确定存储空间的容量。
③造成存储空间的“碎片”。
推荐阅读
- 《数据结构与算法之美》——队列
- 第三章你如果不能出众就可能出局（下）感悟
- 第三章|第三章 进校园重拾旧梦 登讲台初为人师第一节 接乱班面临考验 ，遇高师指点入门
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 一家三口齐穿越——第三章|一家三口齐穿越——第三章 竟然穿越了
- 2018-12-10《天生非此》第三章（你不是生来如此）
- Java深入了解数据结构之栈与队列的详解
- Java集合框架|Java集合框架 数据结构
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式