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

数据结构---顺序表

news 2025/8/22 19:31:38

专栏：数据结构
个人主页：HaiFan.
专栏简介：从零开始，数据结构！！

顺序表

  • 前言
  • 接口实现
  • SListInit初始化和SListDestory销毁
  • SListPrint打印表中的元素
  • SListCheckCapacity检查表中空间
  • SListPushBack尾插和SListPopBack尾删
  • SListPushFront头插和SListPopFront头删
  • SListFind查找元素
  • SListInset插入元素
  • SListErase删除元素
  • 完整代码

前言

在这里插入图片描述

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。
顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储元素。
  2. 动态顺序表：使用动态开辟的数组存储。

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef int SLDataType;typedef struct SeqList
{SLDataType* val;int cnt;int capacity;
}SL;void SListInit(SL* ps);//对顺序表进行初始化
void SListDestory(SL* ps);//使用动态分配函数开辟的空间需要free掉
void SListPrint(SL* ps);//打印出顺序表中的内容void SListCheckCapacity(SL* ps);//检查顺序表中的空间是否够用void SListPushBack(SL* ps,SLDataType x);//顺序表尾部插入
void SListPopBack(SL* ps);//尾部删除void SListPushFront(SL* ps, SLDataType x);//头部插入
void SListPopFront(SL* ps);//头部删除int SListFind(SL* ps,SLDataType x);//查找元素void SListInsert(SL* ps, int pos, SLDataType x);//在任意位置插入元素void SListErase(SL* ps, int pos);//删除任意位置的元素

要说明的是，这里为什么要把int重命名成SLDataType，因为元素的类型是可以变化的，想改变元素的类型，只需要在typedef这里改一下即可，就不需要在更改其他的数据了。

cnt是用来记录顺序表中的元素有多少个

capacity是用来检查顺序表中的空间是否够用

SListInit初始化和SListDestory销毁

顺序表初始化要把结构体中的val开辟一点空间。

void SListInit(SL* ps)
{ps->val = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->val == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->cnt = 0;
}

在程序结束的时候，要把动态开辟的空间给销毁，用了多少空间，还给系统多少空间。

void SListDestory(SL* ps)
{free(ps->val);ps->val = NULL;ps->capacity = ps->cnt = 0;
}

SListPrint打印表中的元素

打印表中的元素，要实现这个只需要一个for循环就能解决。

void SListPrint(SL* ps)
{for (int i = 0; i < ps->cnt; i++){cout << ps->val[i] << ' ';}puts("");
}

cnt是用来记录表中的元素个数的，

SListCheckCapacity检查表中空间

在进行增加元素的时候，要先对表中的空间进行一个检查，判断空间的大小是否足够在容纳一个元素。

void SListCheckCapacity(SL* ps)
{if (ps->capacity == ps->cnt){SLDataType* tmp = (SLDataType*)realloc(ps->val, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->val = tmp;ps->capacity *= 2;}
}

如果val是NULL，先通过malloc开辟一段空间，如果val不是NULL，就让cnt和capacity进行是否相等判断，如果相等，就使用realloc函数对val进行扩容，扩容的时候，用一个临时的指针接收，然后在把临时的指针赋值给val。

当然，空间扩容了，capacity也别忘记扩大了。

SListPushBack尾插和SListPopBack尾删

尾插很简单，cnt不但可以用来记录元素的个数的，也可以当作要插入的元素的下标。

元素值：1 2 3

下标： 0 1 2

cnt的值：3

此时在下标为cnt(3)的地方插入一个值即可。

void SListPushBack(SL* ps, SLDataType x)
{SListCheckCapacity(ps);ps->val[ps->cnt] = x;ps->cnt++;
}

当然，在插入元素之前，要先检查表的空间。

删除元素也很简单，只需要cnt–即可。

void SListPopBack(SL* ps)
{assert(ps->cnt);ps->cnt--;
}

这里要添加一个断言，避免没有元素了还执行删除操作。

SListPushFront头插和SListPopFront头删

头插的话，需要先把每个元素都往后移动一位，把第一个元素的位置给腾出来，才能把x给插入。

void SListPushFront(SL* ps, SLDataType x)
{SListCheckCapacity(ps);for (int i = ps->cnt; i > 0; i--){ps->val[i] = ps->val[i - 1];}ps->val[0] = x;ps->cnt++;
}

当然，要先检查表中空间是否够用

头删的话，只需要把第一个元素等于第二个元素就行，即：下一个元素把上一个元素给覆盖了。

void SListPopFront(SL* ps)
{assert(ps->cnt);for (int i = 0; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;
}

SListFind查找元素

查找元素的话，只需要遍历一遍表中元素即可，找到相同的值，返回下标

int SListFind(SL* ps, SLDataType x)
{assert(ps->cnt);for (int i = 0; i < ps->cnt; i++){if (ps->val[i] == x){return i;break;}}return -1;
}

SListInset插入元素

插入元素分为两种情况，当要插入的位置等于cnt时，就是尾插。

否则，就要让pos之后的元素依次往后移动一位，把pos位置空出来，在进行插入操作。

void SListInsert(SL* ps, int pos, SLDataType x)
{SListCheckCapacity(ps);if (pos > ps->cnt){return;}else if (pos == ps->cnt){SListPushBack(ps, x);}else{for (int i = ps->cnt; i > pos; i--){ps->val[i] = ps->val[i - 1];}ps->val[pos] = x;ps->cnt++;}}

SListErase删除元素

删除元素也分为两种情况，当pos等于cnt-1的时候，就是尾删。

否则，就要让pos后的元素，依次往前移动一位，把pos给覆盖即可。

void SListErase(SL* ps, int pos)
{
assert(ps);

if (pos == ps->cnt - 1)
{SListPopBack(ps);
}
else if (pos > ps->cnt)
{exit(-1);
}
else
{for (int i = pos; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;
}

完整代码

.h文件

#pragma once#include <iostream>
#include <stdlib.h>
#include <assert.h>using namespace std;typedef int SLDataType;typedef struct SeqList
{SLDataType* val;int cnt;int capacity;
}SL;void SListInit(SL* ps);//对顺序表进行初始化
void SListDestory(SL* ps);//使用动态分配函数开辟的空间需要free掉
void SListPrint(SL* ps);//打印出顺序表中的内容void SListCheckCapacity(SL* ps);//检查顺序表中的空间是否够用void SListPushBack(SL* ps,SLDataType x);//顺序表尾部插入
void SListPopBack(SL* ps);//尾部删除void SListPushFront(SL* ps, SLDataType x);//头部插入
void SListPopFront(SL* ps);//头部删除int SListFind(SL* ps,SLDataType x);//查找元素void SListInsert(SL* ps, int pos, SLDataType x);//在任意位置插入元素void SListErase(SL* ps, int pos);//删除任意位置的元素

.cpp文件

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void SListPrint(SL* ps)
{for (int i = 0; i < ps->cnt; i++){cout << ps->val[i] << ' ';}puts("");
}void SListInit(SL* ps)
{ps->val = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->val == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->cnt = 0;
}void SListDestory(SL* ps)
{free(ps->val);ps->val = NULL;ps->capacity = ps->cnt = 0;
}void SListCheckCapacity(SL* ps)
{if (ps->capacity == ps->cnt){SLDataType* tmp = (SLDataType*)realloc(ps->val, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->val = tmp;ps->capacity *= 2;}
}void SListPushBack(SL* ps, SLDataType x)
{SListCheckCapacity(ps);ps->val[ps->cnt] = x;ps->cnt++;
}void SListPopBack(SL* ps)
{assert(ps->cnt);ps->cnt--;
}void SListPushFront(SL* ps, SLDataType x)
{SListCheckCapacity(ps);for (int i = ps->cnt; i > 0; i--){ps->val[i] = ps->val[i - 1];}ps->val[0] = x;ps->cnt++;
}void SListPopFront(SL* ps)
{assert(ps->cnt);for (int i = 0; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;
}int SListFind(SL* ps, SLDataType x)
{assert(ps->cnt);for (int i = 0; i < ps->cnt; i++){if (ps->val[i] == x){return i;break;}}return -1;
}void SListInsert(SL* ps, int pos, SLDataType x)
{SListCheckCapacity(ps);if (pos > ps->cnt){return;}else if (pos == ps->cnt){SListPushBack(ps, x);}else{for (int i = ps->cnt; i > pos; i--){ps->val[i] = ps->val[i - 1];}ps->val[pos] = x;ps->cnt++;}}void SListErase(SL* ps, int pos)
{assert(ps);if (pos == ps->cnt - 1){SListPopBack(ps);}else if (pos > ps->cnt){exit(-1);}else{for (int i = pos; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;}}

test.cpp文件

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void TestSeqList()
{SL s;SListInit(&s);SListPushBack(&s, 1);SListPushBack(&s, 2);SListPushBack(&s, 3);SListPushBack(&s, 4);SListPushBack(&s, 5);SListPrint(&s);SListPopBack(&s);SListPrint(&s);SListPushFront(&s, -1);SListPushFront(&s, -2);SListPushFront(&s, -3);SListPushFront(&s, -4);SListPushFront(&s, -5);SListPrint(&s);SListPopFront(&s);SListPrint(&s);int ret  = SListFind(&s, 4);cout << ret << endl;SListInsert(&s, 3, 100000);SListPrint(&s);SListErase(&s, 3);SListPrint(&s);SListDestory(&s);
}int main()
{TestSeqList();return 0;
}

在这里插入图片描述

http://www.lryc.cn/news/17207.html

相关文章：

  • springboot基础
  • 华为OD机试真题Python实现【 时间格式化】真题+解题思路+代码（20222023）
  • android kotlin 协程(五) suspend与continuation
  • JavaScript事件循环
  • 华为OD机试真题Python实现【最少停车数】真题+解题思路+代码（20222023）
  • Python每日一练(20230223)
  • Flask----------第一个flask项目，debug、host、port的配置
  • 容器技术概述
  • 「SAP」ABAP模块学习需要了解什么？快收下这份ABAP技术栈指南【附技能树】
  • 【python 基础篇 九】python的常用数据类型操作-------时间日历
  • 华为OD机试真题Python实现【相同字符连续出现的最大次数】真题+解题思路+代码（20222023）
  • 【Unity3D】空间和变换
  • 脑洞｜ChatGPT加持下，ChatOps将如何革新团队协作与运维管理？
  • 华为OD机试真题Python实现【找数字】真题+解题思路+代码（20222023）
  • 【Database-01】达梦数据库Docker版下载安装
  • Allegro如何打开格点显示效果操作指导
  • 电子技术——反馈放大器的分析方法总结
  • 微服务系统启动，环境从0开始的搭建过程
  • 手工测试1年经验面试，张口要13K，我真是服了····
  • 【保姆级】手把手捋动态代理流程（JDK+Cglib超详细源码分析）
  • Appium自动化测试 Inspector定位Webview/H5页面元素
  • 数组求和方法总结，学点干货
  • 斗地主洗牌发牌-课后程序(JAVA基础案例教程-黑马程序员编著-第六章-课后作业)
  • 基于antd封装的二次业务筛选组件-table-filter
  • 逆向-还原代码之max 再画堆栈图 (Interl 64)
  • GitHub标星30K+的Java面试八股文长啥样？
  • CVE-2022-39197 POC(CobaltStrike XSS ＜=4.7)漏洞复现
  • 我们来说说蹿红的AIGC到底是什么？ChatGPT又是什么？
  • 新手如何从零开始搭建配置Windows云服务器？
  • 百趣代谢组学-抑郁症居然“男女有别”，脑膜淋巴管起关键作用！