数据结构知识点总结-线性表（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)。

下一篇文章介绍顺序表的链式表示