网站系统建设需要什么资质,灵感来源网站,国外浏览器app,交互网站模板线性表
定义 线性表是具有相同数据类型的N#xff08;N0#xff09;个元素的有限序列#xff0c;其中N为表长#xff0c;当N0时线性表是一张空表。 线性表的逻辑特征#xff1a;每个非空的线性表都有一个表头元素和表尾元素#xff0c;中间的每个元素有且仅有一个直…
线性表
定义 线性表是具有相同数据类型的NN0个元素的有限序列其中N为表长当N0时线性表是一张空表。 线性表的逻辑特征每个非空的线性表都有一个表头元素和表尾元素中间的每个元素有且仅有一个直接前驱有且仅有一个直接后继。 线性表是一种逻辑结构表示元素之间一对一相邻的关系。顺序表数组和链表是指存储结构两者属于不同的层面。
线性表的基本操作 基本操作的实现取决于采用哪种存储结构存储结构不同算法实现也不同比如底层采用数据实现和链表实现对应的代码不一样但在上层实现算法逻辑时不关心底层具体实现上述方法名可以直接作为伪代码使用。
线性表的顺序表示
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)。
下一篇文章介绍顺序表的链式表示
