详解初阶数据结构之顺序表（SeqList）——单文件文件实现SeqList的增删查改

目录

一、线性表

二、顺序表

2.1概念及结构

2.2接口实现

2.3动态顺序表的创建

2.3动态顺序表的初始化

2.3.1传值初始化

2.3.2传址初始化

2.4动态顺序表的清空

2.5动态顺序表的扩容

2.6动态顺序表内容的打印

三、动态顺序表的使用

3.1尾插尾删

3.1.1尾插

3.1.2尾删

3.2头插头删

3.2.1头插

3.2.2头删

3.3在pos位置插入x

3.4删除pos位置的值

3.5修改某个位置的值

四、完整代码

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

2.1概念及结构

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

顺序表一般分为：

静态顺序表：使用定长数组储存元素。

//静态顺序表
#define N 100
struct SeqList
{int a[N];//定长数组int size;//有效数据的个数
};

 

缺点：不是很灵活

动态顺序表：使用动态开辟的数组储存。

2.2接口实现

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

所谓动态其实指的这个结构体里的指针是动态内存开辟来的，是可变的，用的时候动态开辟，不够的话继续开辟，程序结束的时候释放。

2.3动态顺序表的创建

typedef int SLDatatype;//将int重命名为SLDatatype
typedef struct SeqList
{SLDatatype* a;//指向动态开辟的数组SLDatatype capacity;//容量SLDatatype size;//有效数据的个数}SL;//将结构体SeqList重命名为SL

2.3动态顺序表的初始化

2.3.1传值初始化

//传值初始化
void SLInit(SL s)
{s.a = NULL;s.size = 0;s.capacity = 0;
}

 函数那个章节我们学过形参只是实参的临时拷贝，并没有实际作用，生命周期短，出了函数的作用域就会销毁，我们不考虑这种初始化方式。

2.3.2传址初始化

//传址初始化
void SLInit(SL* ps)
{ps->a = 0;ps->capacity = 0;ps->size = 0;
}
void SLInit(SL* ps)
{ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间if (ps->a == NULL){perror("malloc failed");exit(-1);}ps->capacity = 4;//开辟了空间就要给容量赋值ps->size = 0;
}

上面两种初始化方式都可以给予结构体成员变量赋值，但是我们使用第二种，因为第二种为我们开辟了空间。


2.4动态顺序表的清空

void SLDestr(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;//内存释放，容量清零ps->size = 0;//内存释放，有效数据清零
}

2.5动态顺序表的扩容

void SLCheckcapacity(SL* ps)
{if (ps->size == ps->capacity){SLDatatype* tmp = (SLDatatype*)realloc(ps->a, ps->capacity * 2 *( sizeof(SLDatatype)));//扩容尾原来的倍数if (tmp == NULL)//判断是否扩容失败{perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;//扩容后修改原来的容量}
}

这就是所谓的动态，当我们空间不够时，就需要开辟新的空间，使用realloc函数要注意是否开辟成功，定义一个中间指针，当开辟成功时将这个指针赋值给动态数组中的指针。 

2.6动态顺序表内容的打印

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

size为有效数据个数，使用循环打印其中的有效数据。 

三、动态顺序表的使用

3.1尾插尾删

3.1.1尾插

void SLPushBack(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);//检查空间是否足够插入ps->a[ps->size] = x;//赋值ps->size++;//插入一个有效数据，有效数据个数加一
}

 首先一定要检查规矩是否足够，根据上面开辟的空间，容量为4，有效数据为size为0，所以从第一个空间开始插入数据。

3.1.2尾删

//尾删
void SLPopBack(SL* ps)
{assert(ps->size > 0);//判断是否会造成越界if (ps->size == 0){return;}ps->size--;//删除一个数据，有效数据个数减一
}

插入数据后size的大小也会变化，数组中最后一个数字的下标刚好和size的大小一样我们只需要将size减1就行。 

3.2头插头删

3.2.1头插

void SLPushFront(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);//检查空间是否足够int end = ps->size;while (end > 0){ps->a[end] = ps->a[end - 1];//将前一个数据后移动end--;}ps->a[0] = x;//将x赋给初始位置ps->size++;//加入一个数字，有效数据个数加1
}

 老规矩一定要检查空间是否足够，头部插入数据我们只需要将原来的数据往后移动一格就将第一格的位置空出来，再将数值插入就行，插入一个数据，有效数据加1即可。

3.2.2头删

void SLPopFront(SL* ps)
{assert(ps->size > 0);//防止越界访问if (ps->size==0){return;}int begin = 0;while (begin < ps->size){ps->a[begin] = ps->a[begin+1];//将后一个数据往前移动begin++;}ps->size--;//减少一个数字，有效数据减1
}

这里的删除并不是真正意义上的删除，我们只需要将原来的数据往前移动一位使后一位的数据覆盖在前一位，这就做到了删除，顺便再将有效数据减1就行。 

3.3在pos位置插入x

void SLInsert(SL* ps, int pos, int x)
{assert(pos >= 0 && pos <= ps->size);//防止越界访问SLCheckcapacity(ps);int end = ps->size;while (end >=pos){ps->a[end] = ps->a[end-1];//和头插的思想差不多，将数据后移end--;}ps->a[pos] = x;//将x赋值给pos位置ps->size++;//有效数据加1
}

我们可以这样理解：将pos看成初始位置，是不是就转化为头插了？按照头插的思想就可以完成在pos位置上插入x。 

3.4删除pos位置的值

void SLErase(SL* ps, int pos)
{assert(pos >= 0 && pos <= ps->size);//防止越界访问SLCheckcapacity(ps);int begin = pos;while (begin < ps->size){ps->a[begin] = ps->a[begin + 1];//和头删的思想差不多，将数据前移begin++;}ps->size--;//有效数据减1
}

我们会发现3.4和3.5不仅可以做到某个位置值的插入和删除，也可以做到尾插尾删和头插头删。 

3.5修改某个位置的值

void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{assert(pos >= 0 && pos < ps->size);//防止越界ps->a[pos] = x;
}

 这样修改某个位置的值看起来是挺麻烦，但是是为了安全考虑。

四、完整代码

#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//静态顺序表
//#define N 100
//struct SeqList
//{
//	int a[N];//定长数组
//	int size;//有效数据的个数
//};//动态顺序表//创建
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;//指向动态开辟的数组SLDatatype capacity;//容量SLDatatype size;//有效数据的个数}SL;
//传值初始化
//void SLInit(SL s)
//{
//	s.a = NULL;
//	s.size = 0;
//	s.capacity = 0;
//}
//传址初始化
//void SLInit(SL* ps)
//{
//	ps->a = 0;
//	ps->capacity = 0;
//	ps->size = 0;
//}
void SLInit(SL* ps)
{ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间if (ps->a == NULL){perror("malloc failed");exit(-1);}ps->capacity = 4;ps->size = 0;
}
//清空
void SLDestr(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}
//打印
void SLprint(SL* ps)
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}
//检查容量
void SLCheckcapacity(SL* ps)
{if (ps->size == ps->capacity){SLDatatype* tmp = (SLDatatype*)realloc(ps->a, ps->capacity * 2 *( sizeof(SLDatatype)));//扩容尾原来的倍数if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}
}
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);ps->a[ps->size] = x;ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{assert(ps->size > 0);if (ps->size == 0){return;}ps->size--;
}
//头插
void SLPushFront(SL* ps, SLDatatype x)
{SLCheckcapacity(ps);int end = ps->size;while (end > 0){ps->a[end] = ps->a[end - 1];end--;}ps->a[0] = x;ps->size++;
}
//头删
void SLPopFront(SL* ps)
{assert(ps->size > 0);if (ps->size==0){return;}int begin = 0;while (begin < ps->size){ps->a[begin] = ps->a[begin+1];begin++;}ps->size--;
}
//在pos位置插入x
void SLInsert(SL* ps, int pos, int x)
{assert(pos >= 0 && pos <= ps->size);SLCheckcapacity(ps);int end = ps->size;while (end >=pos){ps->a[end] = ps->a[end-1];end--;}ps->a[pos] = x;ps->size++;
}
//删除pos位置的值
void SLErase(SL* ps, int pos)
{assert(pos >= 0 && pos <= ps->size);SLCheckcapacity(ps);int begin = pos;while (begin < ps->size){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;
}
int SLFind(SL* ps, int x)
{int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}
int main()
{SL s1;//传值初始化//SLInit(s1);//传址初始化SLInit(&s1);//尾插SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushBack(&s1, 5);SLPushBack(&s1, 6);SLPushBack(&s1, 7);//尾插测试printf("尾插:\n");SLprint(&s1);//尾删SLPopBack(&s1);//尾删测试printf("尾删:\n");SLprint(&s1);//头插SLPushFront(&s1,10);//头插测试printf("头插:\n");SLprint(&s1);//头删 SLPopFront(&s1);//头删测试printf("头删:\n");SLprint(&s1);//在pos位置插入xSLInsert(&s1, 0, 100);//pos插入x测试printf("pos位置插入x\n");SLprint(&s1);//删除pos位置的值SLErase(&s1, 0);//测试printf("删除pos位置的值\n");SLprint(&s1);//改SLModify(&s1, 2, 1);printf("修改某个位置上的值:\n");//SLprint(&s1);//清空SLDestr(&s1);return 0;
}

 

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

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

相关文章

软件测试/测试开发丨ChatGPT：带你进入智能对话的新时代

软件测试/测试开发丨ChatGPT：带你进入智能对话的新时代

简介 人工智能时代来临 我们正处于AI的iPhone时刻。——黄仁勋&#xff08;英伟达CEO&#xff09; ChatGPT 好得有点可怕了&#xff0c;我们距离危险的强人工智能不远了。——马斯克&#xff08;Tesla/SpaceX/Twitter CEO&#xff09; 以上的内容说明我们现在正处于一个技术大…
阅读更多...
【uni-app】

【uni-app】

准备工作 1.下载hbuilder&#xff0c;插件使用Vue3的uni-app项目 2.需要安装编译器 3.下载微信开发者工具 4.点击运行->微信开发者工具 5.打开微信开发者工具的服务端口 效果图 page.json&#xff08;添加路由&#xff0c;修改底层导航栏&#xff0c;背景色&#xff09…
阅读更多...
读书笔记：多Transformer的双向编码器表示法(Bert)-1

读书笔记：多Transformer的双向编码器表示法(Bert)-1

多Transformer的双向编码器表示法 Bidirectional Encoder Representations from Transformers&#xff0c;即Bert&#xff1b; 本笔记主要是对谷歌Bert架构的入门学习&#xff1a; 介绍Transformer架构&#xff0c;理解编码器和解码器的工作原理&#xff1b;掌握Bert模型架构…
阅读更多...
2023.9.7 关于 TCP / IP 的基本认知

2023.9.7 关于 TCP / IP 的基本认知

目录 网络协议分层 TCP/IP 五层&#xff08;四层&#xff09;模型 应用层 传输层 网络层&#xff08;互联网层&#xff09; 数据链路层&#xff08;网络接口层&#xff09; 物理层 网络数据传输的基本流程 网络协议分层 为什么需要分层&#xff1f; 分层之后&#xff0c…
阅读更多...
MATLAB实现数据插值

MATLAB实现数据插值

目录 一.理论知识 二.一维插值实例 三.二维插值实例 一.理论知识 所谓插值&#xff0c;顾名思义&#xff0c;插入数值。很多时候&#xff0c;我们仅有离散点上的数据&#xff0c;这时如果我们想要分析变量之间的函数关系&#xff0c;则无法实现。但如果通过插值处理&#xf…
阅读更多...
PCL入门（四）：kdtree简单介绍和使用

PCL入门（四）：kdtree简单介绍和使用

目录 1. kd树的意义2. kd树的使用 参考博客《欧式聚类&#xff08;KD-Tree&#xff09;详解&#xff0c;保姆级教程》和《(三分钟)学会kd-tree 激光SLAM点云搜索常见》 1. kd树的意义 kd树是什么&#xff1f; kd树是一种空间划分的数据结构&#xff0c;对于多个维度的数据&a…
阅读更多...
电商（淘宝1688京东拼多多等）API接口服务：提升商业效率和用户体验的关键

电商（淘宝1688京东拼多多等）API接口服务：提升商业效率和用户体验的关键

电商API接口服务&#xff1a;提升商业效率和用户体验的关键 随着电子商务的飞速发展&#xff0c;电商企业需要不断提升自身的业务能力和服务质量&#xff0c;以应对日益激烈的市场竞争。为了更好地满足商家和消费者的需求&#xff0c;电商API接口服务应运而生。本文将探讨电商…
阅读更多...
计算机毕设 大数据商城人流数据分析与可视化 - python 大数据分析

计算机毕设 大数据商城人流数据分析与可视化 - python 大数据分析

文章目录 0 前言课题背景分析方法与过程初步分析&#xff1a;总体流程&#xff1a;1.数据探索分析2.数据预处理3.构建模型 总结 最后 0 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕设题目缺少创新和亮点&#xff0c;往往达不到…
阅读更多...
jmeter调试错误大全

jmeter调试错误大全

一、前言 在使用jmeter做接口测试的过程中大家是不是经常会遇到很多问题&#xff0c;但是无从下手&#xff0c;不知道从哪里开始找起&#xff0c;对于初学者而言这是一个非常头痛的事情。这里结合笔者的经验&#xff0c;总结出以下方法。 二、通过查看运行日志调试问题 写好…
阅读更多...
【常用代码14】el-input输入框内判断正则，只能输入数字，过滤汉字+字母。

【常用代码14】el-input输入框内判断正则，只能输入数字，过滤汉字+字母。

问题描述&#xff1a; el-input输入框&#xff0c;只能输入数字&#xff0c;但是不能显示输入框最右边的上下箭头&#xff0c; <el-input v-model"input" type"number" placeholder"请输入内容" style"width: 200px;margin: 50px 0;&…
阅读更多...
两种解法解决LCR 008. 长度最小的子数组【C++】

两种解法解决LCR 008. 长度最小的子数组【C++】

文章目录 [LCR 008. 长度最小的子数组](https://leetcode.cn/problems/2VG8Kg/description/)解法暴力解法滑动窗口&#xff08;双指针法&#xff09; LCR 008. 长度最小的子数组 解法 暴力解法 //暴力解法&#xff1a; //使用双for循环依次遍历数组&#xff0c;罗列出所有情况…
阅读更多...
华为云 异构数据迁移

华为云 异构数据迁移

数据库和应用迁移 UGO&#xff08;Database and Application Migration UGO&#xff0c;以下简称为UGO&#xff09;是专注于异构数据库结构迁移的专业服务。可将源数据库中的DDL、DML和DCL一键自动转换为华为云GaussDB/RDS的SQL语法&#xff0c;通过数据库评估、对象迁移两大核…
阅读更多...
计算机竞赛 基于深度学习的植物识别算法 - cnn opencv python

计算机竞赛 基于深度学习的植物识别算法 - cnn opencv python

文章目录 0 前言1 课题背景2 具体实现3 数据收集和处理3 MobileNetV2网络4 损失函数softmax 交叉熵4.1 softmax函数4.2 交叉熵损失函数 5 优化器SGD6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习的植物识别算法 ** …
阅读更多...
Vue3，Typescript中引用组件路径无法找到模块报错

Vue3，Typescript中引用组件路径无法找到模块报错

是这么个事&#xff0c;我在vue3新创建的项目里&#xff0c;写了个组件叫headerIndex.vue&#xff0c;放到app.vue中import就会报错 路径肯定没写错&#xff0c;找到了解决方法&#xff0c;但是也没想明白为什么 解决方法如下 在vite-env.d.ts文件中加入 declare module &qu…
阅读更多...
AJAX学习笔记6 JQuery对AJAX进行封装

AJAX学习笔记6 JQuery对AJAX进行封装

AJAX学习笔记5同步与异步理解_biubiubiu0706的博客-CSDN博客 AJAX请求相关的代码都是类似的&#xff0c;有很多重复的代码&#xff0c;这些重复的代码能不能不写&#xff0c;能不能封装一个工具类。要发送ajax请求的话&#xff0c;就直接调用这个工具类中的相关函数即可。 用J…
阅读更多...
springboot web 增加不存在的url返回200状态码 vue 打包设置

springboot web 增加不存在的url返回200状态码 vue 打包设置

spring boot项目增加 html web页面访问 1. 首先 application.properties 文件中增加配置&#xff0c;指定静态资源目录&#xff08;包括html的存放&#xff09; spring.resources.static-locationsclasspath:/webapp/,classpath:/webapp/static/ 2. 项目目录 3. 如果有实现 …
阅读更多...
Arm 架构 Ubuntu 使用 Docker 安装 Gitlab 并使用

Arm 架构 Ubuntu 使用 Docker 安装 Gitlab 并使用

官方 gitlab 文档 我的系统是 arm 架构的 ubuntu 官网没有提供 arm 架构的 docker 的 gitlab 的安装方式&#xff0c;直接安装的也是后来加的&#xff0c;文档也是随笔带过&#xff0c;&#xff0c;&#xff0c;我用到了&#xff0c;记录一下 默认已经安装了 docker 在 docker …
阅读更多...
爬虫逆向实战(31)-某花顺行情中心(cookie、补环境)

爬虫逆向实战(31)-某花顺行情中心(cookie、补环境)

一、数据接口分析 主页地址&#xff1a;某花顺 1、抓包 通过抓包可以发现数据接口是/page/2/ajax/1/ 2、判断是否有加密参数 请求参数是否加密&#xff1f; 无请求头是否加密&#xff1f; 通过查看“标头”可以发现有一个Hexin-V加密参数&#xff0c;但是这个参数的值与c…
阅读更多...
初学Python记

初学Python记

Python这个编程语言的大名当然听说过了呀&#xff0c;这几年特别火&#xff0c;火的一塌涂地。大家可以回忆一下&#xff1a;朋友圈推荐的广告里经常可以看见python的网课广告。 本学期&#xff0c;学校开设了python课程&#xff0c;这几天学习了一下入了一下门&#xff0c;感…
阅读更多...
SpringMVC笔记

SpringMVC笔记

文章目录 一、SpringMVC简介1、什么是MVC2、什么是SpringMVC3、SpringMVC的特点 二、HelloWorld1、开发环境2、创建maven工程a>添加web模块b>打包方式&#xff1a;warc>引入依赖 3、配置web.xmla>默认配置方式b>扩展配置方式 4、创建请求控制器5、创建springMVC…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023