学习线性表：掌握基本操作和应用

线性表

前言

欢迎来到本博客的线性表部分！😄🎉在这篇博文中，我将带您深入探索数据结构中的线性表，这是计算机科学中最基础也是最重要的数据结构之一。

线性表是一种线性数据结构，它由一组连续的元素组成，这些元素按照一定的顺序排列。在我们日常的编程工作中，线性表几乎无处不在，比如数组和链表就是线性表的两种常见实现形式。

本博客将重点关注线性表的插入和删除操作，以及其他一些基本功能，如按位置获取元素、获取长度和查找指定元素的位置。这些操作在实际编程中频繁使用，因此我们将为它们详细讲解，并提供简单易懂的示例代码，让您快速掌握这些核心功能。

线性表的插入和删除操作是其最为关键的特性之一，我们将详细讨论如何在线性表中高效地插入和删除元素，让您了解它们的内部实现原理和时间复杂度。无论您是初学者还是有一定编程经验的开发者，这里都会有对您有益的知识。📚💡

当然，我们也将不时地穿插一些有趣的表情包来轻松化干涩的知识点，让学习过程更加愉快轻松。😄🌈

希望您在本篇博客中能够找到对线性表有更深入了解的机会，并将这些知识应用到您未来的编程实践中。让我们一起开始探索线性表的奥秘吧！🚀😃💻

准备工作

定义数据类型和结构体

typedef int E;typedef struct List {E *array;       //顺序表int MaxSize;    //顺序表最大长度int length;     //顺序表实际长度
} SqList;

初始化操作

线性表初始化，需要对其开辟空间，这里采用动态分配的方式分配空间。即空间大小不够后，可在后面扩容。

  • 首先开启 10 个对应存储的数据的大小空间。
  • 判断开启空间是否成功，如果开辟失败，直接结束
  • 初始化空间存放数据个数的最大容量为 10。
  • 初始化空间内数据的当前长度，默认 为 0。
_Bool initList(SqList *list) {list->array = malloc(sizeof(E) * 10);if (list->array == NULL) return 0;list->MaxSize = 10;list->length = 0;return 1;
}

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！");} else {printf("顺序表初始化失败！");}
}

image-20230728115101595

插入操作

插入操作的基本步骤：

  • 利用for循环找到插入位置。
  • 元素后移：在找到插入位置后，需要将插入位置及其后面的元素都向后移动一位，以腾出空间给新元素。
  • 插入元素：将新元素插入到腾空的位置。
  • 底层数组的实际长度加一。
/**** @param list 顺序表* @param element 插入的元素* @param index 插入元素的位序*/
void insertList(SqList *list, E element, int index) {for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;
}

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");insertList(&list, 111, 1);printList(&list);insertList(&list, 666, 2);printList(&list);insertList(&list, 888, 2);printList(&list);} else {printf("顺序表初始化失败！\n");}
}

运行结果：image-20230728142319203

乍一看，我们的代码看上去写的还不错，貌似非常合理。但是，我们接下来更换一组测试数据：

//main函数
int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");insertList(&list, 111, 4);printList(&list);insertList(&list, 666, 1);printList(&list);insertList(&list, 888, 2);printList(&list);} else {printf("顺序表初始化失败！\n");}
}

image-20230728144025299在初始化完后，我们第一个插入的数据的位序为 4，即下标为3 的位置，从第四个位置开始插入数据。但是最后输出的结果为0，不应该是111 吗？为什么会是 0 呢？这是因为我们插入数据的时候，位置不正确。因此，我们需要完善代码，保证代码的健壮性。

_Bool insertList(SqList *list, E element, int index) {if (index < 1 || index > list->length + 1) return 0;		//判断插入位置是否合理for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;return 1;
}

image-20230728144146971

这次我们再次运行main函数，发现就不会出现上面的问题了，但是这样就结束了吗？真的结束了吗？

我们目前开辟了 10 个大小的数据空间，但是我们只插入了三个数据，如果我们插入 20 个数据会出现怎么样的情况呢？

for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);
}
printList(&list);

image-20230728145126168

输出的结果貌似是正确实，但是这并不代表这是正确的做法。

解释： malloc 函数在内存中分配一块指定大小的连续空间，并返回其指针。当你请求分配 10 个空间时，malloc 可能会给你返回一个指向 10 个连续字节的指针。但是，当你尝试往这个 10 个字节的空间中插入 20 个数据时，这会导致内存越界。这意味着你正在访问和写入一些你没有分配的内存空间，这个行为是未定义的行为。

最常见的问题就是数据损坏：当你在未分配的内存空间中进行写入操作时，这可能导致其他数据被覆盖，数据结构损坏，或者程序崩溃。

为了避免这种问题，应该始终确保在使用动态内存分配时，只访问你已经分配的内容空间，并确保分配的大小足够容纳存放的数据。当需要插入更多的数据时，应该重新分配更大的内存空间（即扩容）。

_Bool insertList(SqList *list, E element, int index) {if (index < 1 || index > list->length + 1) return 0;        //判断插入位置是否合理if (list->MaxSize == list->length) { //判断是否需要扩容int newMaxSize = list->length + (list->length >> 1);E *newArray = realloc(list->array, newMaxSize * sizeof(E));if (newArray == NULL) return 0;list->array = newArray;list->MaxSize = newMaxSize;}for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;return 1;
}

realloc函数：可以做到控制动态内存开辟的大小，重新申请的内存空间大小就是我们指定的新的大小，并且原有的数据也会放到新申请的空间中，非常方便。

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");printf("底层数组初始值：%d\n", list.MaxSize);for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printList(&list);printf("底层数组扩容到：%d\n", list.MaxSize);} else {printf("顺序表初始化失败！\n");}
}

image-20230728160448121

到目前为止，可能出现的问题已经解决了，以此保障了代码的健壮性。接下来介绍线性表（顺序表）的删除操作。

删除操作

删除操作的基本流程：

  • 判断删除的位置是否合理，不合理直接结束；（基本操作）
  • 利用for循环将位序为index的元素删除，即将index后的值向前移动，后面的值覆盖前面的值。（核心思想）
  • 底层数据的实际长度减一。
//删除某个位置的元素
_Bool deleteList(SqList *list, int index){if (index < 1 || index > list->length) return 0;for (int i = index; i < list->length - 1; ++i) {list->array[i] = list->array[i + 1];}list->length--;return 1;
}

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");printf("底层数组初始值：%d\n", list.MaxSize);for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printf("插入后的元素为：");printList(&list);printf("底层数组扩容到：%d\n", list.MaxSize);printf("删除后的元素为：");deleteList(&list, 20);printList(&list);} else {printf("顺序表初始化失败！\n");}
}

image-20230728170012032

这里删除了位序为 20 的数据，即下标为 19 的数组元素。

其他简单操作

OK，这里的插入和删除操作我们就成功完成了，还有一些比较简单的功能，我们这里也来依次实现一下，首先是获取长度：

int getLengthList(SqList *list) {return list->length;
}

image-20230728174650661

接着是按位置获取元素：

//位置获取元素和查找指定元素的位置
E * getList(SqList *list, int index){if (index < 1 || index > list->length - 1) return 0;return &list->array[index - 1];
}

image-20230728175803683

查找指定元素的位置：

int findList(SqList *list, E element) {for (int i = 0; i < list->length - 1; ++i) {if (list->array[i] == element) return i + 1;}return -1;
}

main函数：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printf("插入后的元素为：");printList(&list);printf("%d", findList(&list, 5));} else {printf("顺序表初始化失败！\n");}
}

总结

注意⚠️⚠️⚠️：

  1. 区分位序和下标的区别，大多数教材或者教程上面是将这两者区分开的，即位序 = 下标 + 1的关系，也有一些是位序 = 下标，这一点要格外的注意。
  2. 在开辟新的空间的时候需要判断开辟空间是否成功，如果成功，继续执行后续代码，反之，结束函数。
  3. 实际长度length比底层数组长度MaxSize重要的多。

重难点：

  1. 扩容操作：了解扩容操作的realloc函数，其作用就是开辟一块新的空间然后将原有的数据存放到新申请的空间中，非常方便。当然，如果因为内存不足之类的原因导致内存空间申请失败，那么就返回NULL，所以不要忘记判断是否为空。
  2. 在执行插入或者删除操作时，不要忘记底层数组的实际长度需要自增或自减。

源码部分

#include <stdio.h>
#include <stdlib.h>typedef int E;typedef struct List {E *array;       //顺序表int MaxSize;    //顺序表最大长度int length;     //顺序表实际长度
} SqList;_Bool initList(SqList *list) {list->array = malloc(sizeof(E) * 10);if (list->array == NULL) return 0;list->MaxSize = 10;list->length = 0;return 1;
}/**** @param list 顺序表* @param element 插入的元素* @param index 插入元素的位序*/
_Bool insertList(SqList *list, E element, int index) {if (index < 1 || index > list->length + 1) return 0;        //判断插入位置是否合理if (list->MaxSize == list->length) { //判断是否需要扩容int newMaxSize = list->length + (list->length >> 1);E *newArray = realloc(list->array, newMaxSize * sizeof(E));if (newArray == NULL) return 0;list->array = newArray;list->MaxSize = newMaxSize;}for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;return 1;
}//删除某个位置的元素
_Bool deleteList(SqList *list, int index) {if (index < 1 || index > list->length) return 0;for (int i = index; i < list->length - 1; ++i) {list->array[i] = list->array[i + 1];}list->length--;return 1;
}//获取长度
int getLengthList(SqList *list) {return list->length;
}//位置获取元素和查找指定元素的位置
E *getList(SqList *list, int index) {if (index < 1 || index > list->length - 1) return 0;return &list->array[index - 1];
}int findList(SqList *list, E element) {for (int i = 0; i < list->length - 1; ++i) {if (list->array[i] == element) return i + 1;}return -1;
}void printList(SqList *list) {for (int i = 0; i < list->length; ++i) {printf("%d\t", list->array[i]);}printf("\n");
}int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printf("插入后的元素为：");printList(&list);printf("%d", findList(&list, 5));} else {printf("顺序表初始化失败！\n");}
}

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

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

相关文章

socket server服务器开发常见的并发模型

socket server服务器开发常见的并发模型

两种高效的事件处理模式 服务器程序通常需要处理三类事件&#xff1a;I/O 事件、信号及定时事件。有两种高效的事件处理模式&#xff1a;Reactor和 Proactor&#xff0c;同步 I/O 模型通常用于实现Reactor 模式&#xff0c;异步 I/O 模型通常用于实现 Proactor 模式。 无论是 …
阅读更多...
Flink开发环境准备: centos-jdk8

Flink开发环境准备: centos-jdk8

linux-jdk8 - Flink开发环境准备 一、基本介绍二、环境准备1.1 JDK环境1.2 开发工具1.3 Maven环境 三、flink下载安装配置3.1 Flink下载3.2 flink本地模式安装 - linux3.3 常用配置3.4 日志的查看和配置 四、单机 Standalone 的方式运行 Flink 一、基本介绍 Flink底层源码是基于…
阅读更多...
python+django+mysql项目实践二（前端及数据库）

python+django+mysql项目实践二（前端及数据库）

python项目实践 环境说明&#xff1a; Pycharm 开发环境 Django 前端 MySQL 数据库 Navicat 数据库管理 前端模板 添加模板 在templates下创建 views文件中添加 创建数据库 连接数据库 在setting文件中进行配置 创建表
阅读更多...
Redis持久化机制

Redis持久化机制

AOF 把对redis的写操作记录下来&#xff0c;先执行命令&#xff0c;再执行写入&#xff0c;优势在于&#xff1a; 当然也有风险&#xff1a;丢失和对下一个命令造成阻塞 丢失的原因是执行写操作和记录日志是两个过程 下一个命令造成阻塞的原因是两个过程是同步的 第二个问…
阅读更多...
python GUI nicegui初识一（登录界面创建）

python GUI nicegui初识一（登录界面创建）

最近尝试了python的nicegui库&#xff0c;虽然可能也有一些不足&#xff0c;但个人感觉对于想要开发不过对ui设计感到很麻烦的人来说是很友好的了&#xff0c;毕竟nicegui可以利用TailwindCSS和Quasar进行ui开发&#xff0c;并且也支持定制自己的css样式。 这里记录一下自己利…
阅读更多...
【在英伟达nvidia的jetson-orin-nx上使用调试can基础收发-硬件连接-开机自启动can-初步调试】

【在英伟达nvidia的jetson-orin-nx上使用调试can基础收发-硬件连接-开机自启动can-初步调试】

【在英伟达nvidia的jetson-orin-nx上使用调试can基础收发-硬件连接-开机自启动can-初步调试】 1、概述2、实验环境3、自我学习4-1、实验过程1、硬件原理图焊接连接模块2、输入命令3、测试过程 4-2、目前遗留问题# 1-1、发送可以发送&#xff0c;但是PC发送数据收不到。# 1-2、接…
阅读更多...
Maven项目中Lifecycle和Plugins下的install的区别

Maven项目中Lifecycle和Plugins下的install的区别

在Maven中&#xff0c;如果你的web和service在不同的模块下&#xff0c;如果直接用用tomcat插件运行web层&#xff0c;那么运行时会报错 Failed to execute goal org.apache.maven.plugins:maven-install-plugin:2.5.2:install (default-cli) on project springboot: The pack…
阅读更多...
ResNet-残差网络二

ResNet-残差网络二

文章目录 残差结构的一般表达形式残差结构中的信息传播clean path propagation前向传播反向传播 h(x)为恒等映射的重要性h(x)的实验证明 激活层的位置 和其他网络的对比 上一篇讲了 ResNet 论文中的第一篇&#xff1a;Deep Residual Learning for Image Recognition&#xff0c…
阅读更多...
每日一题——反转单链表

每日一题——反转单链表

反转单链表 题目链接 下面主要介绍两种方法&#xff1a; 方法一&#xff1a; 利用三个指针变量进行反转 具体过程如图所示&#xff1a; 注意&#xff1a;循环的结束的条件为cur NULL而不是next NULL 实现代码&#xff1a; struct ListNode* reverseList(struct ListNode* …
阅读更多...
【C++】——内存管理

【C++】——内存管理

目录 回忆C语言内存管理C内存管理方式new deleteoperator new与operator delete函数new和delete的实现原理定位new表达式(placement-new)malloc/free和new/delete的区别 回忆C语言内存管理 void Test() {int* p1 (int*)malloc(sizeof(int));free(p1);int* p2 (int*)calloc(4…
阅读更多...
解决Linux下PyCharm无法新建文件

解决Linux下PyCharm无法新建文件

一、问题描述 如图&#xff0c;在Ubuntu Linux系统中使用pycharm管理项目时&#xff0c;提示无法新建.py源文件&#xff1a; 二、问题解决 将问题定性为文件夹&#xff08;目录&#xff09;权限问题&#xff0c;在终端中打开项目文件夹的上级目录&#xff0c;将整个项目目录的…
阅读更多...
mysql按照日期分组统计数据

mysql按照日期分组统计数据

目录 前言按天统计按周统计按月统计按年统计date_format参数 前言 mysql的date_format函数想必大家都使用过吧&#xff0c;一般用于日期时间转化 # 例如 select DATE_FORMAT(2023-01-01 08:30:50,%Y-%m-%d %H:%i:%s) # 可以得出 2023-01-01 08:30:50# 或者是 select DATE_FOR…
阅读更多...
【vue】vue-image-lazy图片懒加载使用与介绍【超详细+npm包源代码】

【vue】vue-image-lazy图片懒加载使用与介绍【超详细+npm包源代码】

简介 当前插件是基于vue3&#xff0c;写的一个图片懒加载&#xff0c;文章最下方是npm包的源码&#xff0c;你可以自己拿去研究和修改&#xff0c;如有更好的想法可以留言&#xff0c;如果对你有帮助&#xff0c;可以点赞收藏和关注&#xff0c;谢谢。 后续会添加图片放大和切…
阅读更多...
98. Python基础教程:try...except...finally语句

98. Python基础教程:try...except...finally语句

【目录】 文章目录 1. try...except...finally语法介绍2. try...except...finally执行顺序3. 捕获特定类型的异常4. 捕获所有类型的异常5. 实操练习-打开txt文件并输出文件内容 【正文】 在今天的课程中&#xff0c;我们将学习Python中的异常处理语句try...except...finally。 …
阅读更多...
Mock.js的基本使用方法

Mock.js的基本使用方法

官网网址&#xff1a;Mock.js (mockjs.com) 当前端工程师需要独立于后端并行开发时&#xff0c;后端接口还没有完成&#xff0c;那么前端怎么获取数据&#xff1f; 这时可以考虑前端搭建web server自己模拟假数据&#xff0c;这里我们选第三方库mockjs用来生成随机数据&#xf…
阅读更多...
IDEA偶尔编译的时候不识别lombok

IDEA偶尔编译的时候不识别lombok

偶尔IDEA启动项目的时候会识别不到lombok,识别不到get()跟set()方法 方案 在settings添加下面代码 -Djps.track.ap.dependenciesfalse
阅读更多...
数据安全治理的关键-数据分类分级工具

数据安全治理的关键-数据分类分级工具

强大的资产发现能力 多种资产发现方式的组合应用&#xff0c;能够最大程度地提高资产发现能力。 灵活的敏感数据分类分级规则 内置丰富的敏感数据分类分级规则&#xff0c;支持正则表达式、关键词组、非结构化指纹、结构化指纹、机器聚类等多种匹配方式&#xff0c;并且规则…
阅读更多...
HDFS的QJM方案

HDFS的QJM方案

Quorum Journal Manager仲裁日志管理器 介绍主备切换&#xff0c;脑裂问题解决---ZKFailoverController&#xff08;zkfc&#xff09;主备切换&#xff0c;脑裂问题解决-- Fencing&#xff08;隔离&#xff09;机制主备数据状态同步问题解决 HA集群搭建集群基础环境准备HA集群规…
阅读更多...
Linux中的firewall-cmd

Linux中的firewall-cmd

2023年8月4日&#xff0c;周五上午 目录 打开端口关闭端口查看某个端口是否打开查看当前防火墙设置firewall-cmd中的服务在防火墙中什么是服务&#xff1f;为什么会有服务&#xff1f;打开或关闭服务查看某个服务是否打开firewall-cmd中的 zones查看所有可用的zones&#xff0…
阅读更多...
面试之多线程案例（四）

面试之多线程案例（四）

1.单例模式 单例模式是指在内存中只会创建且仅创建一次对象的设计模式。在程序中多次使用同一个对象且作用相同时&#xff0c;为了防止频繁地创建对象使得内存飙升&#xff0c;单例模式可以让程序仅在内存中创建一个对象&#xff0c;让所有需要调用的地方都共享这一单例对象。…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023