动态顺序表的增删改查（数据结构）

目录

一、顺序表

二、静态顺序表

三、动态顺序表

3.1、动态顺序表的实现

3.2、动态顺序表的实现

3.3.1、结构体创建

3.3.2、初始化

3.3.3、销毁数据

3.3.4、增容空间

3.3.5、尾插数据

3.3.6、头插数据

3.3.7、删除尾数据

3.3.8、打印数据

3.3.9、删除头数据

3.3.10、在指定位置之前插入数据

3.3.11、删除指定位置的数据

3.3.12、查找数据是否存在

四、全部代码

顺序表是数据结构的基础知识，通过学习次内容，可以让我们了解顺序表中数据中是如何进行存储，删除，插入数据的。

一、顺序表

顺序表在逻辑上与物理上是连续存放的，比如我们之前学习的数组，数组中包含许多数，每个数据在内存中存储都是连续的，在我们逻辑思维上存储也是连续的，当然，据我自己所了解，所以数据都需要是具有逻辑存储的，如果不是逻辑存储，那么根本就无法找到此数据。

以下是数组存储的数据：

顺序表与数组的区别：

顺序表的底层结构是数组，对于数组进行封装，实现了增删查改的接口。

使用数组很单一，无法进行修改，而使用顺序表进行存储数据，我们可以任意进行数据的修改。

二、静态顺序表

使用静态顺序表存储数据：

静态顺序表的大小被限制死了，无法进行扩容。

空间给少了不够用，空间给多了浪费。

三、动态顺序表

SLDataType* a;

为什么在这动态顺序表中，数据需要加上“*”,这是因为创建的是一个动态的顺序表，我们可以使用malloc，realloc进行开辟新空间来存储a，如果使用静态数据“a”的话，数据的存储位置就无法变动，当我们在增加数据时候，数据不够了，我们使用realloc开辟新空间，并且空间的其实位置进行改变，那么a就地址就会更改。

3.1、动态顺序表的实现

我们需要创建三个文件，node.h , node.c , test.c

node.h存储头文件与函数的参数

node.c实现函数

test.c为我们的主函数

代码小提示：

在编写代码的时候，我们需要勤测试，在完成一个函数体时，就需要测试，避免写完一大堆函数以后再测试，这样会无从下手。

3.2、动态顺序表的实现

在这部分，我只进行函数的讲解，想要查看全部源码的同学，可以拉到博客的最后进行查看

3.3.1、结构体创建

typedef int SLDatatype;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDatatype* arr;int size;     // 有效数据个数int capacity; // 空间容量
}SL;

我们把int类型的名字改变成了SLDatatype，这样可以方便进行数据类型大小的修改。

3.3.2、初始化

test.cSL s;  //新建结构体
SLInit(&s);  //取地址传给函数进行初始化
//初始化
void SLInit(SL* ps) //进行传址调用，否则堆栈在运行完如何销毁的时候，内容也会消失
{ps->arr = NULL;                 //把数据给置空ps->size = ps->capacity = 0;   //把数据大小与空间也置零
}

因为是顺序表，无需修改首元素的地址，所以我们不需要进行SL* lisk=NULL；把新创建的内容给置为空。我们只要在一个空间进行增删改查。

初始化时我们需要把结构体中的arr置为空，数据大小与空间大小置为0

3.3.3、销毁数据

//销毁
void SLDestroy(SL* ps)
{if (ps->arr)    //相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

当需要销毁数据时，需要把有数据的空间给释放掉，把释放掉空间的地址给置为NULL，避免这个地址变为野指针，影响其他软件的运行，然后我们把size数据大小与capacity 空间大小都置为0。

3.3.4、增容空间

//增容空间
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容//0*2 = 0//若capacity为0，给个默认值，否则×2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}

对于动态顺序表来说，每次增容的大小我们统一规定为：新空间大小 = 2 * 原空间大小。

当原空间大小为0时，我们可以增加一行进行判断，如果原空间等于0那么我们就随机给个默认值，我们这里默认值给的是4个整型。

在扩容完以后，我们将原空间的数据与空间大小都指向为新的地址。

3.3.5、尾插数据

//插入数据
void SLPushBack(SL* ps, SLDatatype x)
{//粗暴的解决方法---断言assert(ps);//等价于assert(ps != NULL)温柔的解决方式//if (ps == NULL)//{//	return;//}SLCheckCapacity(ps);ps->arr[ps->size++] = x;  //每插入一个数据，有效数据大小size就会+1
}

assert（ps）断言是为了判断ps是一个空指针。

当ps->arr[0]=1;进行完这个操作，我们如果想继续插入2，那么我们就要让arr的大小增加1位，此时就变成了ps->arr[1]=2。因此得出代码：ps->arr[ps->size++] = x;

3.3.6、头插数据

void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);//判断空间是否足够SLCheckCapacity(ps);//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来ps->arr[0] = x;ps->size++;
}

这段代码里的注释应该是很清楚的表示了

我们需要把表中数据集体往后移动一位，让新数据放到首元素。

3.3.7、删除尾数据

//删除
void SLPopBack(SL* ps)
{assert(ps);       //判断ps不为空，如果为空，代码没必要运行assert(ps->size); //判断有效数据大小不为空，如果为空，代码没必要运行//ps->arr[ps->size - 1] = -1;  //多余了ps->size--;    //直接将有效数据个数-1就达到我们尾删的效果
}

我们可以直接将有效数据个数-1就达到我们尾删的效果

3.3.8、打印数据

void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}

这个很好理解，不过多阐述了。

3.3.9、删除头数据

void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//数据整体向前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];   //i = size-2}ps->size--;
}

将数据集体往前移动一位。

移动前：

移动后：

3.3.10、在指定位置之前插入数据

//在指定位置之前插入数据(空间足够才能直接插入数据）
void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(ps);   //判断ps是否为空assert(pos >= 0 && pos <= ps->size);    //判断指定位置的数据是否在顺序表中有效SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1]; //pos+1   ->   pos}ps->arr[pos] = x;ps->size++;
}

插入前：

插入后：

3.3.11、删除指定位置的数据

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//还有更多的限制：如顺序表不能为空....//pos之后的数据整体向前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];// size-2 <- size-1}ps->size--;
}

删除前：

删除后：

3.3.12、查找数据是否存在

//查找数据
int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)  //如果arr指向的数据等于x那么就return i{return i;}}//没有找到：返回一个无效的下标return -1;
}
test.cint find = SLFind(&s, 222);
if (find < 0)
{printf("没找到\n");
}
else
{printf("找到了\n");
}

如果return返回的数字小于零，打印没找到，否则就打印找到了

四、全部代码

node.htypedef int SLDatatype;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDatatype* arr;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 SLPushFront(SL* ps, SLDatatype x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//查找指定数据
int SLFind(SL* ps, SLDatatype x);
//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLDatatype x);
//指定位置之前删除数据
void SLErase(SL* ps, int pos);
node.c#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
//销毁
void SLDestroy(SL* ps)
{if (ps->arr)//相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容//0*2 = 0//若capacity为0，给个默认值，否则×2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}
//插入数据
void SLPushBack(SL* ps, SLDatatype x)
{//粗暴的解决方法---断言assert(ps);//等价于assert(ps != NULL)温柔的解决方式//if (ps == NULL)//{//	return;//}SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);//判断空间是否足够SLCheckCapacity(ps);//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来ps->arr[0] = x;ps->size++;
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}//删除
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//ps->arr[ps->size - 1] = -1;//多余了ps->size--;
}
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//数据整体向前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];//i = size-2}ps->size--;
}
//在指定位置之前插入数据(空间足够才能直接插入数据）
void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1]; //pos+1   ->   pos}ps->arr[pos] = x;ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//还有更多的限制：如顺序表不能为空....//pos之后的数据整体向前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];// size-2 <- size-1}ps->size--;}int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}//没有找到：返回一个无效的下标return -1;
}
test.c#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"void SLtest01()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);//SLPushBack(&s, 5);//SLPushBack(&s, 6);//SLPushBack(NULL , 6);////SLPushFront(&s, 1);//SLPushFront(&s, 2);//SLPushFront(&s, 3);//SLPushFront(&s, 4);SLPrint(&s); //1 2 3 4//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);////SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLInsert(&s, 11, 0);//SLPrint(&s);//SLInsert(&s, 22, s.size);//SLPrint(&s);//SLInsert(&s, 33, 1);//SLPrint(&s);//SLErase(&s, 1);//SLPrint(&s); //1 3 4//SLErase(&s,s.size-1);//SLPrint(&s);//2 3int find = SLFind(&s, 222);if (find < 0){printf("没找到\n");}else{printf("找到了\n");}SLDestroy(&s);//SLDestroy(&s);//ctrl+d
}int main()
{SLtest01();return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/434503.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

怎么绕开华为纯净模式安装软件

怎么绕开华为纯净模式安装软件

我是标题 众所周不知&#xff0c;华为鸿蒙系统自带纯净模式&#xff0c;而且 没法关闭 : ) 我反正没找到关闭键 以前或许会有提示&#xff0c;无视风险&#xff0c;“仍要安装”。但我这次遇到的问题是&#xff0c;根本没有这个选项&#xff0c;只有“应用市场”和“取消”&…
阅读更多...
鸿蒙OS开发之动画相关示例分享, 关于弹出倒计时动画的实战案例源码分享

鸿蒙OS开发之动画相关示例分享, 关于弹出倒计时动画的实战案例源码分享

基础动画案例 Entry Component struct Index {StatebtnWidth:number 200 // 按钮的宽度StatebtnHeight:number 100 // 按钮的高度build() {Row(){Column(){Button("测试").width(this.btnWidth).height(this.btnHeight)// 按钮: 用来启动动画Button("动画开始…
阅读更多...
XWF使用指南

XWF使用指南

简介 X-Ways Forensics 是由 Stefan Fleischmann 编写的一个轻量化的应急响应及取证工具&#xff0c;是 WinHex 的法证版本&#xff0c;因此界面逻辑和 WinHex 较为相似。在配置好 mplayer 的情况下&#xff0c;程序总体积在 100MiB 左右&#xff0c;运行时内存占用极低&#…
阅读更多...
c++ 继承 和 组合

c++ 继承 和 组合

目录 一. 继承 1.1 继承的概念 1.2 继承定义 1.3 继承类模板 1.4. 继承中的作用域 二. 派生类&#xff08;子类&#xff09;的默认成员函数 2.1 概念&#xff1a; 2.2 实现⼀个不能被继承的类 2.3 继承与友元 2.4继承与静态成员 三.多继承及其菱形继承问题 3.1继承方…
阅读更多...
市场调研利器 网络问卷的优势及面临的挑战

市场调研利器 网络问卷的优势及面临的挑战

网络问卷作为市场调研工具&#xff0c;高效便捷、成本低廉、数据准确度高且灵活多样。但其低响应率、数据偏差、隐私与安全及技术依赖等挑战也需关注。企业应优化调研方法&#xff0c;应对挑战&#xff0c;以获取全面市场信息。 一、网络问卷的优势 首先&#xff0c;我们来分析…
阅读更多...
sheng的学习笔记-AI-时序差分学习

sheng的学习笔记-AI-时序差分学习

AI目录&#xff1a;sheng的学习笔记-AI目录-CSDN博客 强化学习&#xff1a;sheng的学习笔记-AI-强化学习&#xff08;Reinforcement Learning, RL&#xff09;-CSDN博客 蒙特卡罗强化学习&#xff1a; sheng的学习笔记-AI-蒙特卡罗强化学习-CSDN博客 什么是时序差分学习 时序…
阅读更多...
毕业设计选题：基于ssm+vue+uniapp的校园订餐小程序

毕业设计选题：基于ssm+vue+uniapp的校园订餐小程序

开发语言&#xff1a;Java框架&#xff1a;ssmuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;M…
阅读更多...
北斗三号多模对讲机TD70：公专网融合、数模一体、音视频调度，推动应急通信效能升级

北斗三号多模对讲机TD70：公专网融合、数模一体、音视频调度，推动应急通信效能升级

随着国家对应急通信和精准定位技术的重视程度不断提高&#xff0c;相关技术和设备的研发与应用也得到了迅猛发展。特别是在边防巡逻、林业巡防、海上作业等领域&#xff0c;通信设备的可靠性和功能性直接关系到人员的生命安全和任务的成功完成。 近年来&#xff0c;我国政府高度…
阅读更多...
python 高效读取多个geojson 写入一个sq3(Sqlite) 、效率提高90%+

python 高效读取多个geojson 写入一个sq3(Sqlite) 、效率提高90%+

1.问题缘由&#xff1a; 由于工作需求&#xff0c;需要将多个&#xff08;总量10G&#xff09;geojson文件写入到sq3库&#xff0c;众所周知&#xff0c;sqlite 不支持多线程写入&#xff0c;那该怎么办呢&#xff0c;在网上也查了很多策略&#xff0c;都没有达到立竿见影的效果…
阅读更多...
工控主板在工业控制中扮演什么角色

工控主板在工业控制中扮演什么角色

工控主板在工业控制中扮演着至关重要的角色&#xff0c;它是工业控制系统的核心组件&#xff0c;负责连接、控制和管理各种工业设备&#xff0c;实现自动化生产和智能化管理。具体来说&#xff0c;工控主板在工业控制中的作用可以归纳为以下几个方面&#xff1a; 一、核心控制…
阅读更多...
年龄性别与手势识别系统源码分享

年龄性别与手势识别系统源码分享

年龄性别与手势识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Comput…
阅读更多...
计算机视觉学习路线：从基础到进阶

计算机视觉学习路线：从基础到进阶

计算机视觉学习路线&#xff1a;从基础到进阶 计算机视觉&#xff08;Computer Vision&#xff09;是人工智能和机器学习领域中重要的分支&#xff0c;致力于让计算机能够理解和分析图像、视频等视觉信息。随着深度学习的发展&#xff0c;计算机视觉的应用变得越来越广泛&…
阅读更多...
Python 解析 html

Python 解析 html

一、场景分析 假设有如下 html 文档&#xff1a; 写一段 python 脚本&#xff0c;解析出里面的数据&#xff0c;包括经度维度。 <div classstorelist><ul><li lng"100.111111" lat"10.111111"><h4>联盟店1</h4><p>…
阅读更多...
基于Qt/C++UDP 调试软件功能及用途介绍

基于Qt/C++UDP 调试软件功能及用途介绍

概述 UDP 调试软件是一个基于 Qt 框架的图形化应用程序&#xff0c;旨在提供一个简单易用的界面用于测试和调试 UDP&#xff08;用户数据报协议&#xff09;通信。该软件支持客户端和服务器模式&#xff0c;能够实现数据的发送和接收&#xff0c;方便开发者和网络工程师进行网…
阅读更多...
牛顿迭代法求解x 的平方根

牛顿迭代法求解x 的平方根

牛顿迭代法是一种可以用来快速求解函数零点的方法。 为了叙述方便&#xff0c;我们用 C C C表示待求出平方根的那个整数。显然&#xff0c; C C C的平方根就是函数 f ( x ) x c − C f(x)x^c-C f(x)xc−C 的零点。 牛顿迭代法的本质是借助泰勒级数&#xff0c;从初始值开始快…
阅读更多...
C++ | Leetcode C++题解之第438题找到字符串中所有字母异位词

C++ | Leetcode C++题解之第438题找到字符串中所有字母异位词

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<int> findAnagrams(string s, string p) {int sLen s.size(), pLen p.size();if (sLen < pLen) {return vector<int>();}vector<int> ans;vector<int> count(26);for (int i …
阅读更多...
828华为云征文｜基于华为云Flexus X实例部署Uptime-Kuma服务器监控面板

828华为云征文｜基于华为云Flexus X实例部署Uptime-Kuma服务器监控面板

目录 前言 一、Flexus云服务器X介绍 1.1 Flexus云服务器X实例简介 1.2 Flexus云服务器X实例特点 1.3 Flexus云服务器X实例场景需求 二、Flexus云服务器X购买 2.1 Flexus X实例购买 2.2 重置密码 2.3 登录服务器 三、Flexus X安装uptime-kuma面板 3.1 uptime-kuma介绍 3.2 uptim…
阅读更多...
【频分复用】5G中OFDM和GFDM的比较（频谱效率、误码率、星座图、复杂度）【附MATLAB代码及报告】

【频分复用】5G中OFDM和GFDM的比较（频谱效率、误码率、星座图、复杂度）【附MATLAB代码及报告】

微信公众号&#xff1a;EW Frontier QQ交流群&#xff1a;554073254 背景 5G需要满足低延迟、高数据速率、连接密度和其他应用需求&#xff0c;这些应用需要增强的移动的宽带、超可靠和低延迟连接以及海量机器类型连接[1]。这种通信所需的信道容量受到噪声、衰减、失真和符号间…
阅读更多...
R包：ggheatmap热图

R包：ggheatmap热图

加载R包 # devtools::install_github("XiaoLuo-boy/ggheatmap")library(ggheatmap) library(tidyr)数据 set.seed(123) df <- matrix(runif(225,0,10),ncol 15) colnames(df) <- paste("sample",1:15,sep "") rownames(df) <- sapp…
阅读更多...
TypeScript 设计模式之【策略模式】

TypeScript 设计模式之【策略模式】

文章目录 策略模式&#xff1a;灵活切换算法的导航系统策略模式的奥秘策略模式有什么利与弊?如何使用策略模式来优化你的系统代码实现案例策略模式的主要优点策略模式的主要缺点策略模式的适用场景总结 策略模式&#xff1a;灵活切换算法的导航系统 当你使用导航软件规划路线…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023