代码写的一定程度上，要再次提升的时候，是该好好的看一下数据结构和算法了。趁着最近有时间，好好的复习一下，今天主要是线性表和线性表的顺序存储。
线性表的概念
1、 线性表是一种最基本、最简单的的数据结构，是一种线性结构。
2、 线性表中数据元素之间的关系是一对一，是n个数据元素的有限序列。
3、 若将线性表记为(a1, ……, ai-1, ai,ai+1, ……,an),则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当丨=1, 2, ……, n-1时，ai有且仅有一个直接后继，当i=2, 3, ……, n时，ai有且仅有一个直接前驱。
所以线性表元素的个数n (n>0)定义为线性表的长度，当n=0时，称为空表
image.png
线性表抽象数据类型定义如下
image.png
线性表的顺序存储结构
线性表的顺序存储结构是最简单最常用的数据结构，用一段连续地址依次存储表中的数据元素。下面我们用代码来实现：
image.png
image.png
运行结果如下：
image.png
线性表顺序存储的时间复杂度：
1、最好的情况，如果元素要插入到最后一个位置，或者删除最后一个元素， 此时时间复杂度为0(1)，因为不需要移动元素的。
2、最坏的情况，如果元素要插入到第一个位置或者删除第一个元素，那就意味着要移动所有的元素向后或者向前，函数要对线性表循环一遍操作，所以这个时间复杂度为 0(n)。
3、平均的情况，由于元素插入到第i个位置，或删除第i个元素，需要移动n—i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为(n-1)/2。因此时间复杂度为0(n)。
线性表顺序存储的优缺点：
优点：查询速度快，简单、运算方便，更适合小线性表或者固定长度的线性表。
缺点：删除和插入效率较低；存储空间容易出现上溢；容易出现空间浪费。
网友评论