当前位置：首页 > news >正文

【数据结构】顺序表和链表——顺序表（包含丰富算法题）

news 2025/7/10 5:18:17

文章目录

1. 线性表
2. 顺序表
- 2.1 概念与结构
- 2.2 分类
- - 2.2.1 静态顺序表
  - 2.2.2 动态顺序表
- 2.3 动态顺序表的实现
- 2.4 顺序表算法题
- - 2.4.1 移除元素
  - 2.4.2 删除有序数组中的重复项
  - 2.4.3 合并两个有序数组
- 2.5 顺序表问题与思考

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表

2.1 概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

在这里插入图片描述

顺序表和数组的区别？

顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

在这里插入图片描述

2.2 分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

在这里插入图片描述

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

2.2.2 动态顺序表

概念：使用动态开辟的连续空间存储元素

在这里插入图片描述

2.3 动态顺序表的实现

SeqList.h

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDataType * a;int size; // 有效数据个数int capacity; // 空间容量
}SL;//初始化和销毁
void SLInit(SL * ps);
void SLDestroy(SL * ps);
void SLPrint(SL * ps);
//扩容
void SLCheckCapacity(SL * ps);//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL * ps, SLDataType x);
void SLPopBack(SL * ps);
void SLPushFront(SL * ps, SLDataType x);
void SLPopFront(SL * ps);//指定位置之前插⼊/删除数据
void SLInsert(SL * ps, int pos, SLDataType x);
void SLErase(SL * ps, int pos);
int SLFind(SL* ps, SLDataType x);