郑州自助建站软件,自建论坛要多少钱,项目实施方案,企业的网站建设前期工作总结文章目录
1.概念及结构
2.接口实现
3.数组相关oj题
4.顺序表的问题及思考 文章内容
1.概念及结构
线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构#xff0c;常见的线性表#xff1a;顺序…文章目录
1.概念及结构
2.接口实现
3.数组相关oj题
4.顺序表的问题及思考 文章内容
1.概念及结构
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表一般可以分为 1. 静态顺序表使用定长数组存储元素。 2.动态顺序表使用动态开辟的数组存储。 2.接口实现
动态顺序表主要接口如下
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间如果满了进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);
2.1创建顺序表
对结构体和类型重定义 2.2 顺序表使用前的基本准备 2.3尾插尾删 数组元素个数 与数组下标对应的关系是减一
2.4头插头删 方法二 头删 2.4查找、插入、消除、改 2.5测试
接口全部实现我们来测试一下 3.数组相关oj题
1. 原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)力扣力扣 src负责遍历数组只有src所指向的元素不等于val时src指向的值赋给dest指向的空间这时src 和 dest都若src指向的值等于val则src单独终止条件为src遍历完数组。
代码如下 2. 删除排序数组中的重复项力扣 这是需要两个不同的数组下标一个指向0dest位置一个指向1src位置判断这两个元素是否相等如果相等src dest不动 直到找到src所指向的元素与当前dest元素指向的元素不同时此时dest先指向下一个位置再把src指向的值赋给dest指向的位置终止条件为src遍历完数组。
3. 合并两个有序数组力扣 这题我们应该换种思路前面两题都是从前向后这一道题应该从后向前比较end1 和 end2 的大小谁大谁放在nums1size 的位置上去。当end2为0 时说明所有元素都放进去了不用管end1 是否为0。end2 0 也是程序结束的标志。
代码如下 4.顺序表的问题及思考
问题 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
思考如何解决以上问题呢请看下一篇文章链表。
