数据结构 · 线性表 | 顺序表
啊我摔倒了..有没有人扶我起来学习....
👱个人主页: 《 C G o d 的 个 人 主 页 》 \color{Darkorange}{《CGod的个人主页》} 《CGod的个人主页》交个朋友叭~
💒个人社区: 《 编 程 成 神 技 术 交 流 社 区 》 \color{Darkorange}{《编程成神技术交流社区》} 《编程成神技术交流社区》加入我们,一起高效学习,收割好Offer叭~
🌱刷题链接: 《 L e e t C o d e 》 \color{Darkorange}{《LeetCode》} 《LeetCode》快速成长的渠道哦~
前言
- 线性表(
linear list
)是n
个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… - 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,
线性表在物理上存储时,通常以数组和链式结构的形式存储
顺序表
1.1概念及结构
- 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存
储。在数组上完成数据的增删查改
顺序表一般可以分为:-
静态顺序表:使用定长数组存储元素
-
动态顺序表:使用动态开辟的数组存储
-
1.2 接口实现
- 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空
间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间
大小
- 所以下面我们实现动态顺序表:
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size; // 有效数据个数
size_t capicity; // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
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);
- 具体实现:
//初始化
void SeqListInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->size = psl->capacity = 0;
}
//检查扩容
void CheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
psl->a = tmp;
psl->capacity = newcapacity;
}
}
//尾插
void SeqListPushBack(SL* psl, SLDataType x)
{
SeqListInsert(psl, psl->size, x);
}
//尾删
void SeqListPopBack(SL* psl)
{
SeqListErase(psl, psl->size - 1);
}
//头插
void SeqListPushFront(SL* psl, SLDataType x)
{
SeqListInsert(psl, 0, x);
}
//头删
void SeqListPopFront(SL* psl)
{
SeqListErase(psl, 0);
}
//查找
int SeqListFind(SL* psl, SLDataType x)
{
for (int i = 0; i < psl->size; i )
{
if (psl->a[i] == x)
return i;
}
return -1;
}
//任意位置插入
void SeqListInsert(SL* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos <= psl->size);
//检查扩容
CheckCapacity(psl);
//挪动数据
int end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end - 1];
--end;
}
psl->a[pos] = x;
psl->size;
}
//任意位置删除
void SeqListErase(SL* psl, size_t pos)
{
assert(psl);
assert(pos < psl->size&& pos >= 0);
//挪动数据
while (pos < psl->size - 1)
{
psl->a[pos] = psl->a[pos 1];
pos;
}
--psl->size;
}
//销毁
void SeqListDestroy(SL* psl)
{
assert(psl);
free(psl->a);
psl->size = psl->capacity = 0;
}
//打印
void SeqListPrint(SL* psl)
{
for (int i = 0; i < psl->size; i )
{
printf("%d ", psl->a[i]);
}
}
1.3 顺序表的问题及思考
问题:
- 中间/头部的插入删除,时间复杂度为O(N)
- 增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗。
- 增容一般是呈
2
倍的增长,势必会有一定的空间浪费。例如当前容量为100
,满了以后增容到200
,我们再继续插入了5
个数据,后面没有数据插入了,那么就浪费了95
个数据空间
思考:如何解决以上问题呢?后面文章会给出链表的结构与实现
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfigekg
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01