数据结构知识点总结-线性表（1）-线性表的定义、基本操作、顺序表表示
线性表
定义
线性表是具有相同数据类型的N（N>=0）个元素的有限序列，其中N为表长，当N=0时线性表是一张空表。
线性表的逻辑特征：每个非空的线性表都有一个表头元素和表尾元素，中间的每个元素有且仅有一个直接前驱，有且仅有一个直接后继。
线性表是一种逻辑结构，表示元素之间一对一相邻的关系。顺序表（数组）和链表是指存储结构，两者属于不同的层面。
线性表的基本操作
基本操作的实现取决于采用哪种存储结构，存储结构不同，算法实现也不同，比如底层采用数据实现和链表实现，对应的代码不一样，但在上层实现算法逻辑时不关心底层具体实现，上述方法名可以直接作为伪代码使用。
线性表的顺序表示
（1）顺序表定义
# define MaxSize 50 // 定义线性表的最大长度typedef int ElemType;typedef struct{ElemType data[MaxSize] ; // 顺序表的元素int length ; // 顺序表的当前长度} SqList; // 别名线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表可以是静态分配的数组，也可以是动态分配的数组。如果采用动态分配，就是在使用时按照实际大小申请空间。
#define InitSize 100typedef struct {ElemType *data ; // 指示动态分配数组的指针int MaxSize , length ; // 数组的最大容量和当前个数}SeqList; // 动态分配数组顺序表的类型定义C语言初始化：L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);C++初始化： L.data = new ElemType[InitSize] ;注意：动态分配并不是链式存储，同样还是属于顺序存储结构，其物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。
（2）顺序表的特点
顺序表最主要的特点是：随机访问，即通过首地址和元素序号可以在O(1)时间内找到指定的元素
顺序表的存储密度高，每个结点只存储数据元素，相对于链表来说没有指针域。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动元素。
顺序表基本操作
有效性校验、边界检查：
如下面代码的“判断 i 的范围是否有效”。在函数体前面，主代码运行之前，对数据的有效性进行检查，比如是否为空、是否越界等。体现代码的健壮性，完整性，在考试时如果能多这一步并加上注释，是加分项。
（1）顺序表的插入代码实现
// 本算法实现将元素 e 插入到顺序表 L 中第 i 个位置
bool ListInsert( SqList &L , int i , ElemType e){if ( i < 1 || i > L.length +1 ){ // 判断 i 的范围是否有效return false; }if ( L.length >= MaxSize ){ // 当前存储空间已满，不能插入return false;}//有效性检查for( int j = L.length ; j >= i : j--){ //将 第 i 个元素及之后的元素后移L.data[ j ] = L.data[ j-1 ] ;}L.data[ i -1 ] = e; // 在位置 i 处放入 eL.length++; // 线性表的长度 加 1return true;
}插入算法的平均时间复杂度为O(N)。
最好情况：在表尾插入（即 i = n + 1 ），元素移动语句将不执行，时间复杂度为 O(1) 。
最坏情况：在表头插入（即 i = 1 ），元素移动语句将执行 n 次，时间复杂度为 O( n ) 。
（2）顺序表的删除操作代码
// 本算法实现删除顺序表 L 中第 i 个位置的元素
bool ListDelete( SqList &L , int i , int &e ) {if( i < 1 || i > L.length ){ // 判断 i 的范围是否有效return false ;}e = L.data[ i -1 ] ; // 将被删除的元素赋值给 efor( int j = i ; j < L.length ; j++ ){ // 将第 i 个位置之后的元素前移L.data[ j -1 ] = L.data[ j ]}L.length--; // 线性表的长度减 1return true;
}最好情况：删除表尾元素（即 i = n），无须移动元素，时间复杂度为 O(1)。
最坏情况：删除表头元素（即 i = 1），需要移动一个元素外的所有元素，时间复杂度为 O(n) 。
同理删除操作的平均时间复杂度也是O(N)
（3）按值查找，返回位序。
//本算法实现查找顺序表中值为 e 的元素，如果查找成功，返回元素位序，否则返回 0
int LocateElem( SqList L , ElemType e){
int i ;
for( i = 0 ; i < L.length ; i++){if( L.data[ i ] == e){return i +1 ; // 下标为 i 的元素值等于 e ，返回其位序 i + 1}return 0; //退出循环，说明查找失败
}最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为 O(1) 。
最坏情况：查找的元素在表尾（或不存在）时，需要比较 n 次，时间复杂度为 O(n)。
因此，线性表按值查找算法的平均时间复杂度为 O(n) 。
（4）按下标查找、随机访问。
给定下标之后（或给定取第几个元素）可以直接通过下标访问l.data[i]，l.data[i-1]；因此随机访问的时间复杂度为O(1)。
下一篇文章介绍顺序表的链式表示