线性表的逻辑特征#xff1a;每个非空的线性表都有一个表头元素和表尾元素#xff0c;中间的每个元素有且仅有一个直…

线性表

线性表是具有相同数据类型的NN0个元素的有限序列其中N为表长当N0时线性表是一张空表。

线性表的逻辑特征每个非空的线性表都有一个表头元素和表尾元素中间的每个元素有且仅有一个直接前驱有且仅有一个直接后继。

线性表是一种逻辑结构表示元素之间一对一相邻的关系。

顺序表数组和链表是指存储结构两者属于不同的层面。

基本操作的实现取决于采用哪种存储结构存储结构不同算法实现也不同比如底层采用数据实现和链表实现对应的代码不一样但在上层实现算法逻辑时不关心底层具体实现上述方法名可以直接作为伪代码使用。

1顺序表定义

线性表的顺序存储又称为顺序表。

它是用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表可以是静态分配的数组也可以是动态分配的数组。

如果采用动态分配就是在使用时按照实际大小申请空间。

#define

注意动态分配并不是链式存储同样还是属于顺序存储结构其物理结构没有变化依然是随机存取方式只是分配的空间大小可以在运行时决定。

顺序表最主要的特点是随机访问即通过首地址和元素序号可以在O(1)时间内找到指定的元素

顺序表的存储密度高每个结点只存储数据元素相对于链表来说没有指针域。

顺序表逻辑上相邻的元素物理上也相邻所以插入和删除操作需要移动元素。

顺序表基本操作

的范围是否有效”。

在函数体前面主代码运行之前对数据的有效性进行检查比如是否为空、是否越界等。

体现代码的健壮性完整性在考试时如果能多这一步并加上注释是加分项。

本算法实现将元素

给定下标之后或给定取第几个元素可以直接通过下标访问l.data[i]l.data[i-1]因此随机访问的时间复杂度为O(1)。