那些年错过的数据结构与算法(四)
本篇文章将结合《算法》第4版、业界大牛的博客和自己的理解，具体描述线性表的一些概念，如有错误，请大佬指出。如有侵权，请联系我删除，谢谢。
线性表
1.基本概念
线性表是最简单也是最常用的一种数据结构。是由n个(n≥0)数据结构元素x1、x2···,xn组成的一个有限序列。除了第一个元素外，其它的元素有且只有一个前驱；除了最后一个元素外，其它元素有且只有一个直接后继。可以将线性表表示为(x1,x2,···,xn)，其中xi(i=1,2,···,n)是线性表的数据元素，也成为线性表的一个结点。线性表中的数据元素必须具有相同的属性，即属于同种数据对象。
例如:
- 字母表(A,B,C,···,Z)就是一个长度为26的线性表，其中每个字母都是一个数据元素。
- 矩阵也可以看做一个比较复杂的线性表，既可以把每一行看做一个数据元素，也可以把每一列看做一个数据元素。其中每一个数据元素(一个行向量或者列向量)实际上又是一个简单的线性表。
2.线性表的顺序存储结构
将线性表中的元素在计算机中一段相邻的存储区域中连续存储，称为线性表的顺序存储。线性表的顺序存储结构具有以下2个基本特点：
- 所有元素所占的存储空间必须是连续的。
- 所有元素在存储空间的位置是按逻辑顺序存放的。
从以上2点可以看出，线性表的元素之间逻辑上的相邻关系即元素在计算机内物理位置上的相邻关系。所以只要确定了首地址，线性表内的所有元素的地址都可以方便地找出来。对线性表的处理主要有插入、删除、查找、排序、分解、合并、复制和逆转等，都建立在线性表的顺序存储结构上。
3.线性表的插入运算
在对线性表进行插入操作时，若在第 i (1 ≤ i ≤ n+1)个元素之前插入一个新元素，则完成插入操作需要以下3个步骤：原来第i个结点至第n个结点依次往后移动一个位置；把新结点放在第i个位置上；线性表的结点数加1。
同理，当在线性表头进行插入运算时，则需在表头位置插入一个新的元素，表内的所有元素往后移动一个位置。
当在线性表尾进行插入运算时，则只需在表的末尾增加一个元素即可，不需要移动表内的元素。
一般来说，线性表会事先开辟一个大于线性表长度的空间，但当多次插入运算后，可能出现存储空间已满的情况下仍继续进行插入运算，此时会产生错误，称为"上溢"。
4.线性表的删除运算
在对线性表进行删除操作时，若在第 i 个元素之前插入一个新元素，则完成插入操作需要以下步骤：把第i个元素之后(不包括第i个元素)的n-i个元素依次往前移动一个位置；线性表的结点数减1。
同理，当在线性表头进行删除运算时，则需移动表内除了第1个的所有元素。
当在线性表尾进行删除运算时，则只需最后一个元素，不需要移动表内的元素。
这一篇讲的是线性表的基本要点，内容不多，也容易理解。下一篇讲栈的一些概念和运算。敬请期待哦<(￣︶￣)>。
