0
0

探索数据结构：深入了解顺序表的奥秘


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，它与数组非常类似，但是相比于数组顺序表有一个非常明显的优点——可以动态内存增长空间大小

2. 顺序表的功能

顺序表可以大致包含以下几个功能：

  1. 初始化顺序表中的数据。
  2. 打印顺序表中的数据。
  3. 对顺序表进行尾插(末尾插入数据)。
  4. 对顺序表进行尾删(末尾删除数据)。
  5. 对顺序表进行头插(开头插入数据)。
  6. 对顺序表进行头删(开头删除数据)。
  7. 对顺序表就像查找数据。
  8. 对顺序表数据进行修改。
  9. 任意位置的删除和插入数据。
  10. 销毁顺序表。

3. 顺序表的定义

定义顺序表我们首先需要一个动态内存开辟的空间，当前数据的**个数(size)，以及方便扩容的容量大小(capacity)**。

typedefint SLDataType;//类型重命名，方便后续修改类型#defineN4//初始化空间大小typedefstructSeqList{
    SLDataType* a;//指向动态开辟的数组size_t size;//有效数据个数size_t capacity;//容量大小}SeqList;

4. 功能的具体实现

4.1 初始化顺序表

(1) 代码实现

初始化顺序表时我们可以先开辟四个空间，之后不够再进行扩容。

voidSeqListInit(SeqList* p){assert(p);//断言
    p->a =(SLDataType*)malloc(N*sizeof(SLDataType));//初始顺序表为四个空间if(p->a==NULL){perror("malloc fail:");return;}
    p->size =0;//初始数据个数为0
    p->capacity =4;//初始空间容量为4}
(2) 复杂度分析
  • 时间复杂度：由于没有其他未知数的引入，所以所需时间是个常数，也就是O(1)。
  • 空间复杂度：动态开辟N个空间，所以空间复杂度为O(N)。

4.2 打印数据

(1) 代码实现

打印数据只用循环打印就可以了。

voidSeqListPrint(const SeqList* p){assert(p);//断言if(p->size ==0)//判断顺序表是否为空{printf("顺序表为空\n");return;}int i =0;for(i =0; i < p->size; i++)//打印顺序表{printf("%d ", p->a[i]);}printf("\n");}
(2) 复杂度分析
  • 时间复杂度：因为会打印顺序表中的所有数据，所以时间复杂度为O(N)。
  • 空间复杂度：打印顺序表并不需要开辟格外的空间，所以空间复杂度为O(1)。

4.3 尾插数据

尾插数据，顾名思义就是在顺序表末尾插入数据，在插入数据之前我们应该检查顺序表是否为满。

(1) 检查是否已满
voidCheckCapacity(SeqList* p){assert(p);//断言if(p->size == p->capacity)//检查容量，满了则增容{size_t newcapacity =2* p->capacity;//，扩容为原来的2倍
        SLDataType* prt =(SLDataType*)realloc(p->a, newcapacity *sizeof(SLDataType));//扩容if(prt ==NULL){perror("realloc fail:");return;}
        p->a = prt;// prt不为空，开辟成功
        p->capacity = newcapacity;//更新容量}}
(2) 插入数据
voidSeqListPushBack(SeqList* p, SLDataType x){assert(p);//断言CheckCapacity(p);//检查顺序表容量是否已满
    p->a[p->size]= x;//尾插数据
    p->size++;//有效数据个数+1}
(3) 复杂度分析
  • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
  • 空间复杂度：以最坏的情况考虑，会进行扩容，空间复杂度为O(N)。

4.4 尾删数据

同理，尾删数据就是删除顺序表中最后一个元素，我们只需将size–。注意：删除之前要保证顺序表中有数据。

(1) 代码实现
voidSeqListPopBack(SeqList* p){assert(p);//断言assert(p->size >0);//顺序表不能为空
    p->size--;//有效数据个数-1}
(2) 复杂度分析
  • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
  • 空间复杂度：没有变量影响空间，空间复杂度为O(1)。

4.5 头插数据

头部插入数据就是在第一个元素位置插入一个元素。

(1) 代码实现
voidSeqListPushFront(SeqList* p, SLDataType x){assert(p);//断言CheckCapacity(p);//检查顺序表容量是否已满int i =0;for(i = p->size -1; i >=0; i--)//顺序表中[0,size-1]的元素依次向后挪动一位{
        p->a[i +1]= p->a[i];}
    p->a[0]= x;//头插数据
    p->size++;//有效数据个数+1}
(2) 复杂度分析
  • 时间复杂度：因为从头部插入数据，后续数据需要依次覆盖，所以时间复杂度为O(N)。
  • 空间复杂度：因为可能会进行扩容，按最坏的情况来算，空间复杂度为O(N)。

4.5 头删数据

从头部删除数据，与尾部删除数据不同，需要依次往前覆盖。

(1) 代码实现
voidSeqListPopFront(SeqList* p){assert(p);//断言assert(p->size >0);//顺序表不能为空int i =0;for(i =1; i < p->size; i++)//顺序表中[1,size-1]的元素依次向前挪动一位{
        p->a[i -1]= p->a[i];}
    p->size--;//有效数据个数-1}
(2) 复杂度分析
  • 时间复杂度：因为需要往前覆盖数据，所以时间复杂度自然为O(N)。
  • 空间复杂度：因为并没有开辟其他空间，所以空间复杂度为O(1)。

4.6 查找指定值

根据输入参数，在顺序表中查找指定的值并返回其下标，若未找到则返回-1。

(1) 代码实现
intSeqListFind(const SeqList* p, SLDataType x){assert(p);//断言int i =0;for(i =0; i < p->size; i++){if(p->a[i]== x){return i;//查找到，返回该值在数组中的下标}}return-1;//没有查找到}
(2) 复杂度分析
  • 时间复杂度：以最坏的情况分析，时间复杂度为O(N)。
  • 空间复杂度：并没有格外的空间消耗，空间复杂度为O(1)。

4.7 指定位置修改

我们可以通过指定下标或者查找指定值的下标来修改任意位置的值。

(1) 代码实现
voidSeqListModify(SeqList* p,int pos, SLDataType x){assert(p);//断言assert(p->size >0);//顺序表不能为空assert(pos >=0&& pos < p->size);//检查pos下标的合法性
    p->a[pos]= x;//修改pos下标处对应的数据}
(2) 复杂度分析
  • 时间复杂度：因为是通过指定下标修改，所以时间复杂度为O(1)。
  • 空间复杂度：没有开辟额外的空间，所以空间复杂度为O(1)。

4.8 指定位置插入

和前面其他插入一样，指定位置插入也需要判断是否扩容。

(1) 代码实现
voidSeqListInsert(SeqList* p,int pos, SLDataType x){assert(p);//断言assert(pos <= p->size);//检查pos下标的合法性SeqListCheck(p);//扩容int cur = p->size;while(cur > pos){
        p->a[cur]= p->a[cur -1];//覆盖--cur;}
    p->a[pos]= x;
    p->size++;}
(2) 复杂度分析
  • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
  • 空间复杂度：可能需要扩容，空间复杂度为O(N)。

4.9 指定位置删除

和前面的删除差不多，但是指定删除可能会依次覆盖。

(1) 代码实现
voidSeqListErase(SeqList* p,int pos){assert(p);//断言assert(p->size >0);//顺序表不能为空assert(pos >=0&& pos < p->size);//检查pos下标的合法性int i =0;for(i = pos +1; i < p->size; i++)//将pos位置后面的数据依次向前挪动一位{
        p->a[i -1]= p->a[i];}
    p->size--;//有效数据个数-1}
(2) 复杂度分析
  • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.10 回收空间

在结束操作之后，需要释放开辟的空间，以防止内存泄漏。

(1) 代码实现
voidSeqListDestory(SeqList* p){assert(p);//断言free(p->a);//释放动态开辟的空间
    p->a =NULL;//置空
    p->size =0;//数据个数置0
    p->capacity =0;//空间容量大小置0}
(2) 复杂度分析
  • 时间复杂度：没有额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

5. 完整代码

5.1 SeqList.h

#include<stdio.h>#include<stdlib.h>#include<assert.h>#defineN4//初始化空间大小typedefint SLDataType;//类型重命名，方便后续修改类型typedefstructSeqList{
    SLDataType* a;//指向动态开辟的数组size_t size;//有效数据个数size_t capacity;//容量大小}SeqList;voidSeqListInit(SeqList* p);//初始化顺序表voidSeqListPrint(const SeqList* p);//打印顺序表voidSeqListPushBack(SeqList* p, SLDataType x);//尾插voidSeqListPopBack(SeqList* p);//尾删voidSeqListPushFront(SeqList* p, SLDataType x);//头插voidSeqListPopFront(SeqList* p);//头删intSeqListFind(const SeqList* p, SLDataType x);//查找数据voidSeqListModify(SeqList* p,int pos, SLDataType x);//修改数据voidSeqListInsert(SeqList* p,int pos, SLDataType x);//指定插入voidSeqListErase(SeqList* p,int pos);//指定删除voidSeqListDestory(SeqList* p);//释放空间

5.2 SeqList.c

#define_CRT_SECURE_NO_WARNINGS1#include"SeqList.h"voidSeqListInit(SeqList* p){assert(p);//断言
    p->a =(SLDataType*)malloc(N*sizeof(SLDataType));//初始顺序表为四个空间if(p->a ==NULL){perror("malloc fail:");return;}
    p->size =0;//初始数据个数为0
    p->capacity =4;//初始空间容量为4}voidCheckCapacity(SeqList* p){assert(p);//断言if(p->size == p->capacity)//检查容量，满了则增容{size_t newcapacity =2* p->capacity;//，扩容为原来的2倍
        SLDataType* prt =(SLDataType*)realloc(p->a, newcapacity *sizeof(SLDataType));//扩容if(prt ==NULL){perror("realloc");return;}
        p->a = prt;// prt不为空，开辟成功
        p->capacity = newcapacity;//更新容量}}voidSeqListPushBack(SeqList* p, SLDataType x){assert(p);//断言CheckCapacity(p);//检查顺序表容量是否已满
    p->a[p->size]= x;//尾插数据
    p->size++;//有效数据个数+1}voidSeqListPrint(const SeqList* p){assert(p);//断言if(p->size ==0)//判断顺序表是否为空{printf("顺序表为空\n");return;}int i =0;for(i =0; i < p->size; i++)//打印顺序表{printf("%d ", p->a[i]);}printf("\n");}voidSeqListPopBack(SeqList* p){assert(p);//断言assert(p->size >0);//顺序表不能为空
    p->size--;//有效数据个数-1}voidSeqListPushFront(SeqList* p, SLDataType x){assert(p);//断言CheckCapacity(p);//检查顺序表容量是否已满int i =0;for(i = p->size -1; i >=0; i--)//顺序表中[0,size-1]的元素依次向后挪动一位{
        p->a[i +1]= p->a[i];}
    p->a[0]= x;//头插数据
    p->size++;//有效数据个数+1}voidSeqListPopFront(SeqList* p){assert(p);//断言assert(p->size >0);//顺序表不能为空int i =0;for(i =1; i < p->size; i++)//顺序表中[1,size-1]的元素依次向前挪动一位{
        p->a[i -1]= p->a[i];}
    p->size--;//有效数据个数-1}intSeqListFind(const SeqList* p, SLDataType x){assert(p);//断言int i =0;for(i =0; i < p->size; i++){if(p->a[i]== x){return i;//查找到，返回该值在数组中的下标}}return-1;//没有查找到}voidSeqListModify(SeqList* p,int pos, SLDataType x){assert(p);//断言assert(p->size >0);//顺序表不能为空assert(pos >=0&& pos < p->size);//检查pos下标的合法性
    p->a[pos]= x;//修改pos下标处对应的数据}voidSeqListInsert(SeqList* p,int pos, SLDataType x){assert(p);//断言assert(pos <= p->size);//检查pos下标的合法性SeqListCheck(p);//扩容int cur = p->size;while(cur > pos){
        p->a[cur]= p->a[cur -1];//覆盖--cur;}
    p->a[pos]= x;
    p->size++;}voidSeqListErase(SeqList* p,int pos){assert(p);//断言assert(p->size >0);//顺序表不能为空assert(pos >=0&& pos < p->size);//检查pos下标的合法性int i =0;for(i = pos +1; i < p->size; i++)//将pos位置后面的数据依次向前挪动一位{
        p->a[i -1]= p->a[i];}
    p->size--;//有效数据个数-1}voidSeqListDestory(SeqList* p){assert(p);//断言free(p->a);//释放动态开辟的空间
    p->a =NULL;//置空
    p->size =0;//数据个数置0
    p->capacity =0;//空间容量大小置0}
标签： 数据结构 c语言 动态内存
本文转载自: https://blog.csdn.net/Bettysweetyaaa/article/details/136419374
版权归原作者 Betty’s Sweet 所有， 如有侵权，请联系我们删除。
登录后发布评论

“探索数据结构：深入了解顺序表的奥秘”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航