01数据结构 - 顺序表

这里是只讲干货不讲废话的炽念，这个系列的文章是为了我自己以后复习数据结构而写，所以可能会用一种我自己能够听懂的方式来描述，不会像书本上那么枯燥和无聊，且全系列的代码均是可运行的代码，关键地方会给出注释^_^

全文近8000字

版本：C++17

编译器：Clion 2023.3.24

暂时只给出代码，不会涉及到基础知识的讲解

1.线性表的定义

//定义顺序表的表头结构
typedef struct {Element* data;              // 指向顺序表的数据区域int len;                    // 该区域能够访问的边界条件，目前内容器存储数据的数量int cap;                    // 该区域最大容量，超过这个容量就需要扩容
}SeqList;// len 始终指向待插入位置

2.线性表的实现函数

2.1.表的创建以及删除

// 表的创建以及删除
SeqList *createSeqList(int n);                  // 创造一个表并初始化void releaseSeqList(SeqList *seqList);          // 释放掉表头以及表内的数据

 2.2.扩容函数

// 辅助函数
int enLargerSeq(SeqList *seqList);                  // 扩容函数

2.3.向表中插入元素

// 三种插入方式
int pushBackSeq(SeqList *seqList, Element val);         // 往尾部插入一个元素int headInsertSeq(SeqList *seqList, Element val);       // 往头部插入一个元素int insertSeq(SeqList *seqList, int pos, Element val);  // 按指定值来插入元素

2.4.表的展示以及查找

// 展示以及查找
void showSeqList(SeqList *seqList);                // 遍历并显示数据int findSeq(SeqList *seqList, Element val);        // 按值查找

2.5.删除表中的元素

// 三种方式删除
int deleteSpeSeq(SeqList *seqList, Element val);   // 删除特定值的元素int deleteHeadSeq(SeqList *seqList);               // 删除首元素int deleteTailSeq(SeqList *seqList);               // 删除尾元素

3.实现函数的代码

3.1.createSeqList函数的实现

函数定义：
SeqList *createSeqList(int n);                  // 创造一个表并初始化

函数功能：
该函数用于创建一个长度为n的顺序表，并返回指向该顺序表的指针

实现思路：
a.申请表头空间b.申请表内元素的空间c.初始化 len(length 长度) 和 cap(capacity 容量)d.对申请的空间进行检查，如果申请空间失败，则需要返回NULL

具体实现代码：
SeqList *createSeqList(int n) {SeqList *seqList;seqList = (SeqList *)malloc(sizeof(SeqList));               //申请表头if (seqList == NULL){printf("Malloc seqlist failed\n");return NULL;}seqList->data = (Element *) malloc(sizeof(Element) * n);    //申请空间if (seqList->data == NULL){printf("Malloc data failed");return NULL;}seqList->len = 0;seqList->cap = n;return seqList;
}

测试代码： 
int main() {SeqList *list = createSeqList(10);if (list == NULL) {printf("创建顺序表失败\n");return 1;}printf("顺序表创建成功\n");free(list->data);free(list);return 0;
}

测试结果：

3.2 releaseSeqList函数的实现

函数定义：
void releaseSeqList(SeqList *seqList);          // 释放掉表头以及表内的数据

函数功能： 
该函数用于释放一个顺序表所占用的内存空间，防止内存泄漏

实现思路：
a.先判断表头再判断数据域是否为空b.如果数据域不为空，则释放掉表内的数据域空间c.释放掉表头空间

 具体实现代码：
void releaseSeqList(SeqList *seqList) {if (seqList){if (seqList->data){free(seqList->data);}free(seqList);printf("Release success!\n");}
}

测试代码： 
int main() {SeqList *list = createSeqList(10);if (list == NULL) {printf("创建顺序表失败\n");return 1;}printf("顺序表创建成功\n");releaseSeqList(list);  // 释放顺序表return 0;
}

测试结果：

3.3 enLargerSeq 函数的实现

函数定义：
int enLargerSeq(SeqList *seqList);                  // 扩容函数

函数功能：
该函数用于对顺序表进行扩容，将顺序表的大小扩展为原来的两倍

实现思路：
a.先申请一个新空间 tmp，新空间的大小为原来空间大小(seqList->len / seqList->cap)的两倍
b.将原来空间的值通过 for 循环赋值给新空间
c.释放掉原来表头指向的空间 seqList->data
d.将表头的 seqList->data 指向新申请的空间 tmp
e.将 seqList->cap 大小变为原来的两倍

具体实现代码：
int enLargerSeq(SeqList *seqList) {Element *tmp = (Element *) malloc(sizeof (Element) * 2 * seqList->cap);if (!tmp){printf("Enlarger element failed!\n");return -1;}for (int i = 0; i < seqList->len; i++){tmp[i] = seqList->data[i];}free(seqList->data);    // 这两句是否有先后？seqList->data = tmp;    // 有先后，如果调换顺序就会先指向新的内存空间，然后再释放老的内存空间，此时老的内存空间已经找不到了，会发生内存泄露seqList->cap *= 2;printf("Enlarge success!\n");return 0;
}

测试代码： 
int main(){SeqList *list = createSeqList(5);for (int i = 0; i < 5; i++){pushBackSeq(list, i);}pushBackSeq(list,666);showSeqList(list);printf("%d", list->cap);return 0;
}

测试结果：

3.4 showSeqList && findSeq 函数的实现

函数定义：
void showSeqList(SeqList *seqList);                // 遍历并显示数据int findSeq(SeqList *seqList, Element val);        // 按值查找

函数功能：

1.showSeqList 函数

该函数用于遍历并显示顺序表中的所有数据

2.findSeq 函数 

该函数用于在顺序表中查找指定的值，并返回该值的索引。如果未找到，则返回 -1

实现思路：

1.showSeqList 函数

a.首先判断传入的表是否为空
b.使用 for 循环遍历整个表并打印数据

2.findSeq 函数

a.判断传染的表是否为空且表的长度是否合法(seqList->len > 0)
b.使用for循环遍历表，如果找到了val就直接返回该数的下标
c.如果没找到，打印提示信息，返回-1

具体实现代码：
// showSeqList 函数
void showSeqList(SeqList *seqList) {if (seqList == NULL || seqList->data == NULL){printf("SeqList is null.Show error\n");return;}for (int i = 0; i < seqList->len; i++){printf("%d ", seqList->data[i]);}printf("\n");
}// findSeq 函数
int findSeq(SeqList *seqList, Element val) {if (!seqList || !seqList->data || seqList->len <= 0){printf("SeqList is null!\n");return -1;}for (int i = 0; i < seqList->len; i++){if (seqList->data[i] == val){return i;}}printf("Find value error!\n");return -1;
}

测试代码： 
int main(){SeqList *list = createSeqList(5);for (int i = 0; i < 5; i++){pushBackSeq(list, i);}showSeqList(list);int index1 = findSeq(list, 666);int index2 = findSeq(list,0);printf("%d\n", index1);printf("%d\n", index2);releaseSeqList(list);return 0;
}

测试结果：

3.4 pushBackSeq && headInsertSeq && insertSeq 函数的实现

函数定义：
int pushBackSeq(SeqList *seqList, Element val);         // 往尾部插入一个元素int headInsertSeq(SeqList *seqList, Element val);       // 往头部插入一个元素int insertSeq(SeqList *seqList, int pos, Element val);  // 按指定位置来插入元素

函数功能：
1.pushBackSeq 函数
在顺序表尾部插入一个元素
2.headInsertSeq 函数
在顺序表头部插入一个元素
3.insertSeq 函数
在顺序表指定位置插入一个元素

实现思路：

1.pushBackSeq 函数

a.判断传入的链表以及数据域是否为空b.判断当前元素是否到达空间上限，如果是则需要扩容c.往 seqList->len 的位置放入元素d.seqList->len++

 2.headInsertSeq 函数

a.判断传入的链表以及数据域是否为空b.判断当前元素是否到达空间上限，如果是则需要扩容c.从第 1 个元素开始，依次往后移动元素d.往下标为 0 的位置放入元素e.seqList->len++

3.insertSeq 函数

a.判断传入的链表以及数据域是否为空b.判断当前元素是否到达空间上限，如果是则需要扩容c.从第 seqList->len-1 个元素开始，直到第 pos 个元素(包含)，从后往前移动元素d.往下标为 pos 的位置放入元素e.seqList->len++

具体实现代码：

1.pushBackSeq 函数

// pushBackSeq 函数
int pushBackSeq(SeqList *seqList, Element val) {if (!seqList || !seqList->data){printf("Seqlist is null");return -1;}if (seqList->len >= seqList->cap){printf("Insertion overflow. Consider enlarging the structure!\n");if (enLargerSeq(seqList) == -1){printf("Enlarge failed!\n");return -1;}}seqList->data[seqList->len] = val;seqList->len++;return 0;
}

  2.headInsertSeq 函数

// headInsertSeq 函数
int headInsertSeq(SeqList *seqList, Element val) {if (!seqList || !seqList->data){printf("Seqlist is null");return -1;}if (seqList->len >= seqList->cap){printf("Insertion overflow. Consider enlarging the structure!\n");if (enLargerSeq(seqList) == -1){printf("Enlarge failed!\n");return -1;}}for (int i = seqList->len; i > 0; i--) {        // 核心移动逻辑seqList->data[i] = seqList->data[i-1];}seqList->data[0] = val;seqList->len++;return 0;
}

 3.insertSeq 函数

// insertSeq 函数
int insertSeq(SeqList *seqList, int pos, Element val) {if (!seqList || !seqList->data){printf("Seqlist is null");return -1;}// 为什么是 > seqList->len，而不是 > seqList->cap?// 顺序表是一种线性数据结构，它要求元素在内存中连续存储。这意味着元素之间不能有空隙，必须紧密排列// 使用 len 而不是 cap 来确定插入位置，可以保证顺序表中的元素始终保持连续存储，这是顺序表的核心特征if (pos < 0 || pos > seqList->len){printf("Insert value out of bounds\n");return -1;}if (seqList->len >= seqList->cap){printf("Insertion overflow. Consider enlarging the structure!\n");if (enLargerSeq(seqList) == -1){printf("Enlarge failed!\n");return -1;}}for (int i = seqList->len-1; i >= pos; i--){    // 核心移动逻辑seqList->data[i+1] = seqList->data[i];}seqList->data[pos] = val;seqList->len++;return 0;
}

测试代码： 
int main(){SeqList *list = createSeqList(5);for (int i = 0; i < 5; i++){pushBackSeq(list, i);}showSeqList(list);insertSeq(list, 5, 111);      // 任意位置插入showSeqList(list);insertSeq(list, 0, 222);      // 任意位置插入showSeqList(list);insertSeq(list, 999, 333);    // 任意位置插入showSeqList(list);printf("\n");headInsertSeq(list, 888);     // 头插法showSeqList(list);printf("\n");pushBackSeq(list, 666);       // 尾插法showSeqList(list);releaseSeqList(list);return 0;
}

测试结果：

3.5 deleteSpeSeq && deleteHeadSeq && deleteTailSeq 函数的实现

函数定义：
int deleteSpeSeq(SeqList *seqList, Element val);   // 删除特定值的元素int deleteHeadSeq(SeqList *seqList);               // 删除首元素int deleteTailSeq(SeqList *seqList);               // 删除尾元素

函数功能：

1.deleteSpeSeq 函数

该函数用于在顺序表中删除指定值的元素

2. deleteHeadSeq 函数  

该函数用于删除顺序表中的首元素

 3.deleteTailSeq 函数 

该函数用于删除顺序表中的尾元素

实现思路：

1.deleteSpeSeq 函数

a.判断传入的表是否为空
b.调用 findSeq 函数，判断要查找的值是否在表中
c.如果不在表中，则返回错误标志
d.从 pos+1 的位置开始，从后往前覆盖元素
e.seqList->len--

2. deleteHeadSeq 函数 

a.判断传入的表是否为空
b.判断表内是否有元素
c.从第二个元素(索引为1)开始，从后往前进行覆盖
d.seqList->len--

3.deleteTailSeq 函数 

a.判断传入的表是否为空
b.判断表内是否有元素
d.seqList->len--

具体实现代码：

1.deleteSpeSeq 函数

int deleteSpeSeq(SeqList *seqList, Element val) {if (!seqList || !seqList->data){printf("Seqlist is null. Delete failed!\n");return -1;}int pos = findSeq(seqList, val);if (pos == -1){printf("Delete value error!\n");return -1;}for (int i = pos + 1; i < seqList->len; i++){seqList->data[i - 1] = seqList->data[i];}/*for (int i = pos; i < seqList->len; i++){ // 第二种写法可能会有溢出的风险seqList->data[i] = seqList->data[i + 1];}*/seqList->len--;return 0;
}

2. deleteHeadSeq 函数

int deleteHeadSeq(SeqList *seqList) {if (!seqList || !seqList->data){printf("Seqlist is null. Delete failed!\n");return -1;}if (seqList->len <= 0){printf("Delete head value failed!");return -1;}for (int i = 1; i < seqList->len; i++){seqList->data[i-1] = seqList->data[i];}seqList->len--;return 0;
}

3.deleteTailSeq 函数

int deleteTailSeq(SeqList *seqList) {if (!seqList || !seqList->data){printf("Seqlist is null. Delete failed!\n");return -1;}if (seqList->len <= 0){printf("Delete tail value failed!");return -1;}seqList->len--;return 0;
}

测试代码：
int main(){SeqList *list = createSeqList(5);for (int i = 0; i < 5; i++){pushBackSeq(list, i);}deleteHeadSeq(list);showSeqList(list);deleteTailSeq(list);showSeqList(list);deleteSpeSeq(list,999);showSeqList(list);deleteSpeSeq(list,1);showSeqList(list);releaseSeqList(list);return 0;
}

测试结果：

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

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

相关文章

大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】

大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】

大数据面试SQL题复习思路一网打尽&#xff01;(文档见评论区)_哔哩哔哩_bilibiliHive SQL 大厂必考常用窗口函数及相关面试题 大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】大数据面试SQL题-笔记02【...】 目录 01、力扣网-sql题 1、高频SQL50题&#xff08…
阅读更多...
51单片机STC89C52RC——19.1 SG90舵机（伺服电机）

51单片机STC89C52RC——19.1 SG90舵机（伺服电机）

目的/效果 独立按键K1&#xff0c;K2 实现加舵机减角度增减&#xff0c;LCD1602显示舵机转角度数&#xff08;上电默认90度&#xff09; 一&#xff0c;STC单片机模块 二&#xff0c;SG90舵机 2.1 简介 舵机只是我们通俗的叫法&#xff0c;它的本质是一个伺服电机&#xf…
阅读更多...
VPN以及GRE和MGRE

VPN以及GRE和MGRE

VPN VPN — 是虚拟专用网络 通俗地说&#xff0c;就是通过虚拟的手段&#xff0c;将两个独立的网络&#xff0c;穿越一个公共网络进行连接&#xff0c;实现点到点专线的效果&#xff08;可以理解为&#xff1a;一个分公司通过公网和总公司建立点到点的专线连接&#xff09; 现…
阅读更多...
【MQTT（3）】开发一个客户端，QT-Android安卓手机版本

【MQTT（3）】开发一个客户端，QT-Android安卓手机版本

手机版本更加方便 生成安卓库 参考了这个代码 在编译Mosquitto以支持安卓平台时&#xff0c;主要涉及到使用Android NDK&#xff08;Native Development Kit&#xff09;进行交叉编译。环境的准备参考之前的博客【QT开发&#xff08;17&#xff09;】2023-QT 5.14.2实现Andr…
阅读更多...
单链表算法 - 链表的回文结构

单链表算法 - 链表的回文结构

链表的回文结构_牛客题霸_牛客网对于一个链表&#xff0c;请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法&#xff0c;判断其是否为。题目来自【牛客题霸】https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa思路1: /* struct ListNode {int val;st…
阅读更多...
字节面试：如何让单机下Netty支持百万长连接？

字节面试：如何让单机下Netty支持百万长连接？

最近有同学在面试遇到了一道非常有深度的面试题&#xff1a; 如何让单机下Netty支持百万长连接&#xff1f; 当时在群里问小北&#xff0c;我发现我也没有系统化的梳理过这个问题&#xff0c;所以一时也没有回答的特别好。 痛定思痛的我赶紧去各种搜集资料&#xff0c;系统化的…
阅读更多...
unity渲染人物模型透明度问题

unity渲染人物模型透明度问题

问题1&#xff1a;有独立的手和衣服的模型&#xff0c;但最终只渲染出来半透明衣服 问题2&#xff1a;透明度贴图是正确的但显示却不正确 这上面两个模型的问题都是因为人物模型是一个完整的&#xff0c;为啥有些地方可以正常显示&#xff0c;有些地方透明度却有问题。 其中…
阅读更多...
数据结构小测试：排序算法

数据结构小测试：排序算法

目录 1、请简述数据结构八大排序算法的思路。 2、常用排序算法手写 冒泡排序&#xff1a; 选择排序&#xff1a; 快速排序&#xff1a; 归并排序&#xff1a; 堆排序&#xff1a; 3、额外再加一个二分查找吧 1、请简述数据结构八大排序算法的思路。 冒泡排序&#xff…
阅读更多...
亚信安全发布2024年第24期《勒索家族和勒索事件监控报告》

亚信安全发布2024年第24期《勒索家族和勒索事件监控报告》

本周态势快速感知 本周&#xff0c;勒索软件LockBit涉嫌对美国一家生产乙烯基产品的公司&#xff08;Homeland Vinyl&#xff09;进行攻击。LockBit声称他们已窃取了销售、库存、财务交易数据及其他公司记录&#xff0c;并声明将于2024年7月19日公开这些被盗信息。本周全球共监…
阅读更多...
【iOS】OC类与对象的本质分析

【iOS】OC类与对象的本质分析

目录 前言clang常用命令对象本质探索属性的本质对象的内存大小isa 指针探究 前言 OC 代码的底层实现都是 C/C代码&#xff0c;OC 的对象都是基于 C/C 的数据结构实现的&#xff0c;实际 OC 对象的本质就是结构体&#xff0c;那到底是一个怎样的结构体呢&#xff1f; clang常用…
阅读更多...
AI算法17-贝叶斯岭回归算法Bayesian Ridge Regression | BRR

AI算法17-贝叶斯岭回归算法Bayesian Ridge Regression | BRR

贝叶斯岭回归算法简介 贝叶斯岭回归&#xff08;Bayesian Ridge Regression&#xff09;是一种回归分析方法&#xff0c;它结合了岭回归&#xff08;Ridge Regression&#xff09;的正则化特性和贝叶斯统计的推断能力。这种方法在处理具有大量特征的数据集时特别有用&#xff…
阅读更多...
安全入门day01

安全入门day01

一、常用名词 1、前后端 &#xff08;1&#xff09;前端 前端主要负责用户界面的展示和交互。它通常包括HTML、CSS和JavaScript等技术的使用&#xff0c;也可能使用各种前端框架和库&#xff0c;如React、Vue.js、Angular等&#xff0c;来构建更加复杂和动态的用户界面。前端…
阅读更多...
校验el-table中表单项

校验el-table中表单项

需求&#xff1a; 表格中每一行都有几个必填项&#xff0c;如用户提交时有未填的选项&#xff0c;将该选项标红且给出提示&#xff0c;类似el-form 的那种校验 el-table本身并没有校验的方法&#xff0c;而且每一行的输入框也是通过插槽来实现的&#xff0c;因此我们要自己跟…
阅读更多...
log4js node日志插件

log4js node日志插件

最近不是特别忙在用express搭建后台项目&#xff0c;在开发过程中遇到了需要输入日志的问 本来想直接用node自带的console来实现&#xff0c;后来发现console输出的日志达不到自己希望的 日志格式&#xff0c;后来各种百度发现了log4js插件&#xff0c;本文来记录log4js插件使用…
阅读更多...
一文-深入了解Ansible常见模块、安装和部署

一文-深入了解Ansible常见模块、安装和部署

1 Ansible 介绍 Ansible是一个配置管理系统configuration management system, python 语言是运维人员必须会的语言, ansible 是一个基于python 开发的&#xff08;集合了众多运维工具 puppet、cfengine、chef、func、fabric的优点&#xff09;自动化运维工具, 其功能实现基于ss…
阅读更多...
django实现用户的注册、登录、注销功能

django实现用户的注册、登录、注销功能

创建django项目的步骤&#xff1a;Django项目的创建步骤-CSDN博客 一、前置工作 配置数据库&#xff0c;设置数据库引擎为mysql 1、在settings文件中找到DATABASES, 配置以下内容 DATABASES {"default": {ENGINE: django.db.backends.mysql, # 数据库引擎NAME: dja…
阅读更多...
基于springboot和mybatis的RealWorld后端项目实战二之实现tag接口

基于springboot和mybatis的RealWorld后端项目实战二之实现tag接口

修改pom.xml 新增tag数据表 SET FOREIGN_KEY_CHECKS0;-- ---------------------------- -- Table structure for tags -- ---------------------------- DROP TABLE IF EXISTS tags; CREATE TABLE tags (id bigint(20) NOT NULL AUTO_INCREMENT,name varchar(255) NOT NULL,PR…
阅读更多...
【hadoop大数据集群 2】

【hadoop大数据集群 2】

【hadoop大数据集群 2】 文章目录 【hadoop大数据集群 2】1. 虚拟机克隆2. 时间同步3. 环境变量配置、启动集群、关闭集群 1. 虚拟机克隆 克隆之后一定要重新生成新虚拟机唯一的MAC地址和UUID等&#xff0c;确保新虚拟机与源虚拟机在网络拓扑中不发生冲突。 注意1.生成新的MA…
阅读更多...
IDEA关联数据库

IDEA关联数据库

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …
阅读更多...
Spring Boot2（Spring Boot 的Web开发 springMVC 请求处理 参数绑定 常用注解 数据传递）

Spring Boot2（Spring Boot 的Web开发 springMVC 请求处理 参数绑定 常用注解 数据传递）

目录 一、Spring Boot 的Web开发 1. 静态资源映射规则 2. enjoy模板引擎 二、springMVC 1. springMVC-请求处理 测试&#xff1a; 以post方式请求 限制请求携带的参数 GetMapping 查询 PostMapping 新增 DeleteMapping删除 PutMapping 修改 2. springMVC-参…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023