数据结构与算法—顺序表

目录

一、线性表

二、顺序表概念

 三、实现顺序表

1、声明结构体

2、初始化

3、打印数据 

4、销毁 

5、尾插&头插

尾插

判断是否扩容 

 头插

6、尾删&头删

尾删

头删

7、 指定位置插入元素

8、 删除指定位置元素

9、 查找指定元素位置

10、修改指定位置元素

完整版附上:

Seqlist.h

Seqlist.c

 text.c


一、线性表

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

二、顺序表概念

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

2. 动态顺序表:使用动态开辟的数组存储。  

 三、实现顺序表

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

 我们创建三个文件:

  1. Seqlist.h用于存放头文件、结构体和函数的声明
  2. text.c作为主程序进行运行和测试
  3. Seqlist.c存放函数主体

1、声明结构体

#include <stdio.h>typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int size;int capacity;
}SL;
  • 在头文件中声明结构体struct SeqList,由于名字太长,我们用typedef自定义结构体名称的别名为SL。
  • 将顺序表的数据类型用SLDatatype这个别名代替int,以后程序中使用到元素数据类型时都替换成SLDatatype,方便日后修改顺序表数据类型。
  • 定义size存储当前元素个数,capacity存储顺序表容量。

2、初始化

void SLInit(SL* psl)
{assert(psl);psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);if (psl->a == NULL) {perror("malloc fail");return;}psl->size = 0;psl->capacity = 4;
}
  • 需要改变结构体变量,则将其地址传入函数。
  • assert检测传参顺序表指针是否合法,如果传入参数为空则报错(具体哪行出错)。
  • 然后为结构体成员a分配4个成员类型空间,顺便检查是否分配成功。
  • 对成员size和capacity分别复制为0(当前元素个数)和4(顺序表容量)。

3、打印数据 

void SLPrint(SL* psl)
{assert(psl);for (int i = 0; i < psl->size; i++) {printf("%d ", psl->a[i]);}
}
  • assert检测传参顺序表指针是否合法,然后循环遍历输出。

4、销毁 

void SLDestroy(SL* psl)
{assert(psl);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}
  • assert检测传参顺序表指针是否合法。

  • 释放动态开辟a的空间,同时赋值为空,不置空可能会造成野指针的访问。

  • size和capacity分别赋值为0。

5、尾插&头插

尾插

void SLPushBack(SL* psl, SLDatatype x)
{assert(psl);SLCheckCapacity(psl);psl->a[psl->size] = x;psl->size++;
}
  • assert检测传参顺序表指针是否合法。

  • 判断数组是否已经装满,如果装满则进行扩容,这些操作我们在函数SLCheckCapacity内进行。

  • 将 x 赋值给 psl->a 数组中下一个可用的位置,即 psl->size 索引处。

  • 递增 psl->size,以便记录新元素的加入。

 接下来我们来讲解函数SLCheckCapacity:

判断是否扩容 

void SLCheckCapacity(SL* psl)
{if (psl->size == psl->capacity) {SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);if (tmp == NULL) {perror("realloc fail");return;}psl->a = tmp;psl->capacity *= 2;}
}
  •  判断当前元素个数size与顺序表容量capacity是否相等,相等则对结构体成员指针a进行扩容。

  • 通过realloc函数对a的内存进行扩容,每次增加一倍容量,并将reallocd的返回值新空间的起始地址赋值给SLDatatype类型指针 tmp,这样避免直接对a开辟空间时发生错误丢失数据。

  • 检测是否成功扩容。

  • 最后将存放新空间地址的tmp赋值给a。

  • 顺序表的容量也随之扩大为原来的两倍。

我们还可以优化一下尾插函数,具体如下: 

void SLPushBack(SL* psl, SLDatatype x)//尾插
{SLCheckCapacity(psl);psl->a[psl->size++] = x;
}

 头插

void SLPushFront(SL* psl, SLDatatype x)
{assert(psl);SLCheckCapacity(psl);int end = psl->size - 1;while (end >= 0) {psl->a[end + 1] = psl->a[end];end--;}psl->a[0] = x;psl->size++;
}
  • assert检测传参顺序表指针是否合法。

  • 判断数组是否已经装满,如果装满则进行扩容,这些操作在函数SLCheckCapacity内进行。

  • 定义end表示当前顺序表中最后一个元素的下标。

  • while循环用于从后向前将顺序表中的元素依次向后移动一个位置,为新元素 x 腾出空间

  • 将新元素 x 插入到顺序表的开头

  • 顺序表元素个数 size 增加1

6、尾删&头删

尾删

void SLPopBack(SL* psl)
{assert(psl);//暴力判断assert(psl->size == 0);//常规判断//if (psl->size == 0)//	return;psl->a[psl->size - 1] = 0;psl->size--;
}
  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测顺序表是否为空,为空没有元素则不需要删除,程序报错。

  • 我们还可以通过顺序表元素个数判断,if语句判断size为0时,函数停止运行。

  • 顺序表大小不为空,则对最后一个元素进行删除,赋值为0。

  • 顺序表大小size减1.

头删

void SLPopFront(SL* psl)
{assert(psl);assert(psl->size > 0);int start = 0;while (start < psl->size) {psl->a[start] = psl->a[start + 1];start++;}psl->size--;
}
  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测顺序表是否为空,为空没有元素则不需要删除,程序报错。

  • 定义变量start为首元素下标.

  • 头删不用赋值为0,直接从第一个元素开始后项赋值给前项。

7、指定位置插入元素

void SLInsert(SL* psl, int pos, SLDatatype x)
{assert(psl);assert(0 <= pos && pos <= psl->size);SLCheckCapacity(psl);int end = psl->size - 1;while (end >= pos) {psl->a[end + 1] = psl->a[end];end--;}psl->size++;psl->a[pos] = x;
}
  • 参数pos为要在第几个元素后插入。

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 判断数组是否已经装满,如果装满则进行扩容,这些操作在函数SLCheckCapacity内进行。

  • 定义end表示当前顺序表中最后一个元素的下标。

  • while循环用于从后向前将顺序表中的元素依次向后移动一个位置,为新元素 x 腾出空间

  • 顺序表元素个数 size 增加1。

  • 将新元素 x 插入到顺序表指定元素位置之后。

 SLInsert这个函数可以代替头插尾插函数进行顺序表元素的增加。

8、删除指定位置元素

void SLErase(SL* psl, int pos)
{assert(psl);assert(0 <= pos && pos <= psl->size);int start = pos + 1;while (start < psl->size) {psl->a[start - 1] = psl->a[start];start++;}psl->size--;
}
  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 定义变量start存储pos位置后一项的下标。

  • 将删除元素后一项位置的值开始从pos+1向后依次前移一位,顶替pos位置。

  • 顺序表元素个数减一。

这个函数就可以完全代替头删尾删了。

9、查找指定元素位置

int SLFind(SL* psl, SLDatatype x)
{assert(psl);for (int i = 0; i < psl->size; i++) {if (psl->a[i] == x)return i+1;}return -1;
}
  •  assert检测传参顺序表指针是否合法。

  • 循环遍历顺序表找出于x相等的元素,返回其下标。

  • 找不到返回-1。

10、修改指定位置元素

void SLModify(SL* psl, int pos, SLDatatype x)
{assert(psl);assert(0 <= pos && pos <= psl->size);psl->a[pos] = x;
}
  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 将pos位置的值修改为x。

完整版附上:

Seqlist.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int size;int capacity;
}SL;void SLInit(SL* psl);
void SLDestroy(SL* psl);
void SLPrint(SL* psl);
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl, int pos);
int SLFind(SL* psl, SLDatatype x);
void SLModify(SL* psl, int pos, SLDatatype x);

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"void SLInit(SL* psl)//初始化
{assert(psl);psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);if (psl->a == NULL) {perror("malloc fail");return;}psl->size = 0;psl->capacity = 4;//每次开辟的容量为四个
}void SLPrint(SL* psl)//打印数据
{assert(psl);for (int i = 0; i < psl->size; i++) {printf("%d ", psl->a[i]);}
}void SLDestroy(SL* psl)//结束使用需要销毁
{assert(psl);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}void SLCheckCapacity(SL* psl)
{if (psl->size == psl->capacity) {//增加一倍容量SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);if (tmp == NULL) {perror("realloc fail");return;}psl->a = tmp;psl->capacity *= 2;}}void SLPushBack(SL* psl, SLDatatype x)//尾插
{assert(psl);//psl->a[psl->size] = x;//psl->size++;//插入需要判断a是否已满,已满需要扩容SLCheckCapacity(psl);//或者写成一句psl->a[psl->size++] = x;//后置自增
}void SLPushFront(SL* psl, SLDatatype x)//头插
{assert(psl);SLCheckCapacity(psl);int end = psl->size - 1;while (end >= 0) {psl->a[end + 1] = psl->a[end];end--;}psl->a[0] = x;psl->size++;
}
void SLPopBack(SL* psl)
{assert(psl);//尾删//暴力判断//assert(psl->size == 0);//常规判断if (psl->size == 0)return;psl->a[psl->size - 1] = 0;psl->size--;
}void SLPopFront(SL* psl)//头删
{assert(psl);assert(psl->size > 0);int start = 0;while (start < psl->size) {psl->a[start] = psl->a[start + 1];start++;}psl->size--;
}void SLInsert(SL* psl, int pos, SLDatatype x)//指定位置插入元素,可代替头插尾插
{assert(psl);assert(0 <= pos && pos <= psl->size);//判读插入位置是否合法SLCheckCapacity(psl);int end = psl->size - 1;while (end >= pos) {psl->a[end + 1] = psl->a[end];end--;}psl->size++;psl->a[pos] = x;
}void SLErase(SL* psl, int pos)//删除指定位置元素,代替头删尾删
{assert(psl);assert(0 <= pos && pos <= psl->size);int start = pos + 1;while (start < psl->size) {psl->a[start - 1] = psl->a[start];start++;}psl->size--;
}int SLFind(SL* psl, SLDatatype x)//查找指定元素位置
{assert(psl);for (int i = 0; i < psl->size; i++) {if (psl->a[i] == x)return i+1;}return -1;//找不到返回-1
}void SLModify(SL* psl, int pos, SLDatatype x)//修改指定位置元素
{assert(psl);assert(0 <= pos && pos <= psl->size);psl->a[pos] = x;
}

 text.c

这里大家可以自行发挥!

#define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 5);SLPushBack(&s, 9);SLPushBack(&s, 50);SLPushFront(&s, 1);SLPushFront(&s, 15);SLPushFront(&s, 0);SLPopBack(&s, 50);SLPopFront(&s, 0);SLInsert(&s, 2, 555);SLErase(&s, 4);SLPrint(&s);int a=SLFind(&s, 15);printf("\n%d\n", a);if (a != -1)SLErase(&s, a);SLPrint(&s);SLDestroy(&s);
}int main()
{test1();return 0;
}

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

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

相关文章

angular13 自定义组件全项目都可用 自存

1.定义自定义组件 使用命令创建一个组件 但删除它在你的module里的声明&#xff0c;因为会报错只能引用一次 在本组件中创建一个module文件&#xff0c;引入刚才的组件component.ts import { NgModule } from angular/core; import { CommonModule } from angular/common; im…

简化路径[中等]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个字符串path&#xff0c;表示指向某一文件或目录的Unix风格 绝对路径 &#xff08;以/开头&#xff09;&#xff0c;请你将其转化为更加简洁的规范路径。在Unix风格的文件系统中&#xff0c;一个点.表示当前目录本身&#x…

vue3 自定义组件

在项目中&#xff0c;我们会遇到一些没有现成的组件&#xff0c;那这个时候我们就需要自己去写一个满足我们需求的组件。 比如&#xff0c;我需要一个上下排布&#xff0c;上面显示标题&#xff0c;下面显示内容的组件。封装完成后方便复用。 1、布局组件 我定义一个上下结构的…

2024生日快乐祝福HTML源码

源码介绍 2024生日快乐祝福HTML源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c; 源码截图 源码下载 2024生日快乐祝福HTML源码

Gradio 案例——将 dicom 文件转为 nii文件

文章目录 Gradio 案例——将 dicom 文件转为 nii文件界面截图依赖安装项目目录结构代码 Gradio 案例——将 dicom 文件转为 nii文件 利用 SimpleITK 库&#xff0c;将 dicom 文件转为 nii文件更完整、丰富的示例项目见 GitHub - AlionSSS/dcm2niix-webui: The web UI for dcm2…

一种请求头引起的跨域问题记录(statusCode = 400/CORS)

问题表象 问题描述 当我们需要在接口的headers中添加一个自定义的变量的时候&#xff0c;前端的处理是直接在拦截器或者是接口配置的地方直接进行写&#xff0c;比如下面的这段比较基础的写法&#xff1a; $http({method: "post",url:constants.backend.SERVER_LOGIN…

selenium发展史

Selenium Core 2004 年&#xff0c;Thoughtworks 的工程师 Jason Huggins 正在负责一个 Web 应用的测试工作&#xff0c;由于这个项目需要频繁回归&#xff0c;这导致他不得不每天做着重复且低效的工作。为了解决这个困境&#xff0c;Jason 开发了一个运行在 JavaScript 沙箱中…

React框架-Next 学习-1

创建一个 Next.js 应用,node版本要高&#xff0c;16.5以上 npm淘宝镜像切为https://registry.npmmirror.com npm config set registry https://registry.npmmirror.com npx create-next-applatest//安装后 使用npm run dev 启动 Next.js 是围绕着 页面&#xff08;pages&am…

我21岁玩“撸货”,被骗1000多万

最近&#xff0c;撸货业界内发生了一些颇受瞩目的事件。 在郑州&#xff0c;数码档口下面抢手团长跑路失联&#xff0c;涉及金额几百万&#xff0c;在南京&#xff0c;一家知名的电商平台下的收货站点突然失联&#xff0c;涉及金额高达一千多万&#xff0c;令众多交易者震惊不已…

回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测

回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测 目录 回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 Matlab实现GA-LSSVM遗传算法优化最小…

基于 Spring Boot 博客系统开发(十)

基于 Spring Boot 博客系统开发&#xff08;十&#xff09; 本系统是简易的个人博客系统开发&#xff0c;为了更加熟练地掌握 SprIng Boot 框架及相关技术的使用。&#x1f33f;&#x1f33f;&#x1f33f; 基于 Spring Boot 博客系统开发&#xff08;九&#xff09;&#x1f…

【考研数学】张宇《1000题》强化阶段正确率多少算合格?

张宇1000题真的很练人心态.... 基础不好&#xff0c;建议别碰1000题 基础好&#xff0c;1000题建议在两个月以内刷完 如果自己本身在基础阶段学的比较水&#xff0c;自己的薄弱点刷了一小部分题没有针对性完全解决&#xff0c;转身去刷1000题就会发现&#xff0c;会的题目刷…

算术平均数

算术平均数&#xff08;average&#xff09;是一组数据相加后除以数据的个数而得到的结果&#xff0c;是度量数据水平的常用统计量&#xff0c;在参数估计和假设检验中经常用到。比如&#xff1a;用职工平均工资来衡量职工工资的一般水平&#xff0c;用平均体重来观察某一人群体…

通信指挥类装备(多链路聚合设备)-应急通信指挥解决方案

现场通信指挥系统是一种功能全面的便携式音视频融合指挥通信平台&#xff0c;可实现现场应急救援指挥、多种通信手段融合、现场通信组网等功能&#xff0c;是现场指挥系统的延伸。 多链路聚合设备&#xff0c;是一款通信指挥类装备&#xff0c;具有 4G/5G&#xff0c;专网&…

YOLOv8训练流程-原理解析[目标检测理论篇]

关于YOLOv8的主干网络在YOLOv8网络结构介绍-CSDN博客介绍了&#xff0c;为了更好地学习本章内容&#xff0c;建议先去看预测流程的原理分析YOLOv8原理解析[目标检测理论篇]-CSDN博客&#xff0c;再次把YOLOv8网络结构图放在这里&#xff0c;方便随时查看。 ​ 1.前言 YOLOv8训练…

《ESP8266通信指南》17-结尾篇(完结撒花)

《ESP8266通信指南》16-MQTT收发通信-完整代码-&#xff08;Lua烧录代码的深度思考与串口拦截&#xff09;-CSDN博客 《ESP8266通信指南》系列的第十六篇&#xff0c;专注于MQTT收发通信的完整代码以及深度思考与串口拦截。本小节首先列出了往期内容&#xff0c;然后提出了本节…

哈希表的理解和实现

目录 1. 哈希的概念 (是什么) 2. 实现哈希的两种方式 (哈希函数) 2.1. 直接定址法 2.2. 除留余数法 2.2.1. 哈希冲突 3. 补充知识 3.1. 负载因子 3.2. 线性探测和二次探测 4. 闭散列实现哈希表 (开放定址法) 4.1. 开放定址法的实现框架 4.2. Xq::hash_table::insert…

今天遇到一个GPT解决不了的问题

问题描述 你好&#xff0c;postman的一个post请求&#xff0c;编辑器里面放了一个很长的json数据&#xff0c;报Tokenization is skipped for long lines for performance reasons. This can be configured via editor.maxTokenizationLineLength.&#xff0c;但是同样的数据&a…

家用充电桩远程监控安全管理系统解决方案

家用充电桩远程监控安全管理系统解决方案 在当今电动汽车日益普及的背景下&#xff0c;家用充电桩的安全管理成为了广大车主关注的重点问题。为了实现对充电桩的高效、精准、远程监控&#xff0c;一套完善的家用充电桩远程监控安全管理系统解决方案应运而生。本方案旨在通过先…

AI 绘画神器 Fooocus 图生图:图像放大或变化、图像提示、图像重绘或扩充、反推提示词、生成参数提取、所需模型下载

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里&#xff0c;订阅后可阅读专栏内所有文章。 大家好&#xff0c;我是水滴~~ 本文讲述 Fooocus 的图生图功能&#xff0c;主要内容包括&#xff1a;图像放大或变化、图像提示、图像重绘或扩充、反推…