C语言数据结构之线性表-顺序表篇

星光不负赶路人

江河眷顾奋楫者

🎥烟雨长虹，孤鹜齐飞的个人主页

🔥个人专栏

期待小伙伴们的支持与关注！！！

线性表的简介#

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

目录

线性表的简介#

顺序表的概念与结构

概念#

结构#

 顺序表的接口实现

定义顺序表的结构体#

初始化和动态内存的开辟#

顺序表的头插尾插 

顺序表的尾插#

顺序表的头插#

顺序表的头删尾删 

 顺序表的尾删#

顺序表的头删#

顺序表的指定插入删除 

顺序表的指定插入#

顺序表的指定删除#

顺序表在解题中的运用 

移除元素

顺序表的概念与结构

概念#

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构

一般情况下采用数组存储，在数组上完成数据的增删查改

日常生活中我们的手机通讯录、聊天软件界面就是通过顺序表实现的

结构#

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

静态顺序表一旦空间不够用了还需要手动调节，很不方便

<2>动态顺序表：使用动态开辟的数组存储元素

动态顺序表可以通过realloc来调节空间的大小，无需手动

静态顺序表和动态顺序表的优劣：

静态顺序表#

给定数组的长度

优点：

<1>创建空间时为静态开辟，不用malloc函数，代码相对简单

缺点：

<1>若空间小了，会导致后续的数据存储失败

<2>若空间大了，会导致空间的大量浪费

动态顺序表#

动态开辟的数组存储元素

优点：

<1>动态开辟空间，使用相对灵活，相比于静态开辟空间也可以减少空间浪费

缺点：

<1>因为要用到malloc开辟内存，代码相对复杂

由于静态顺序表实用价值极低，实现思路上不如动态顺序表

且会实现动态顺序表的话实现静态顺序表也没有太大的问题

因此在这里只给大家详细讲解一下动态顺序表的实现

 顺序表的接口实现

今天我将带领大家去学习顺序表的动态实现：

<1>从头部插入数据

<2>从尾部插入数据

<3>从头部删除数据

<4>从尾部删除数据

<5>从指定位置插入数据

<6>从指定位置删除数据

现在到了我们写代码的环节啦

我们依然是像这种代码量多的项目最好分模块写代码

定义顺序表的结构体#

#include<stdio.h> //标准的输入输出
#include<stdlib.h>//开辟动态空间的
#include<assert.h>//断言

typedef int SLDataType; //对变量类型的重命名

typedef struct SeqList
{
	SLDataType* str;   //指向开辟的动态空间
	int capacity;      //记录当前顺序表的空间大小
	int size;          //记录当前顺序表的元素个数
}SL;                   //对结构体的重命名

我们使用 typedef 的好处就是减少类型需求的变化带来修改上的麻烦

初始化和动态内存的开辟#

void SLInit(SL* h);         //初始化
void SLCheckCapacity(SL* h);//动态内存开辟
void SLInit(SL* h)
{
	h->str = NULL;
	h->capacity = h->size = 0;
}

void SLCheckCapacity(SL* h)
{
	if (h->size == h->capacity)
	{
		//三目运算符判断顺序表的扩容
		//如果空间大小为0就开4个SLDataType类型的空间
		//若不够则扩大原来的二倍
		int newCapacity = h->capacity = 0 ? 4 : 2 * h->capacity;
		SLDataType* tmp = (SLDataType*)malloc(h->str, newCapacity * sizeof(SLDataType));
		//断言防止开辟失败
		assert(tmp);
		h->str = tmp;
		h->capacity = newCapacity;
	}
}

可能有小伙伴不理解为啥 void SLInit(SL* h) 传的是指针

我们来看

因为现在是传值调用：形参是实参的拷贝，出了函数就会被销毁

而我们为了修改实参的数据应该选用传址调用-指针

顺序表的头插尾插 

顺序表的尾插#

对于表尾插入元素，需要先判断表是否已满，如果未满，则将元素插入表尾

void SLPushBack(SL* h, SLDataType x)
{
	//判断是否扩容
	SLCheckCapacity(h);
	//空间足够，直接插入
	h->str[h->size++] = x;
}

在用我们的SLPrint()函数将尾插结果测试一下

void SLPrint(SL* h)
{
    //遍历顺序表
	for (int i = 0; i < h->size; i++)
	{
		printf("%d ", h->str[i]);
	}
	printf("\n");
}

这样我们的尾插就完成啦

顺序表的头插#

对于头插入元素，需要先将首位置及其之后的元素后移，然后再将要插入的元素放入头部

void SLPushFront(SL* h,SLDataType x)
{
	//判断是否扩容
	SLCheckCapacity(h);
	//原顺序表中的元素全部往后挪动
	for (int i = h->size; i > 0; i--)
	{
		h->str[i] = h->str[i - 1];
	}
	//将待插入元素放在首位
	h->str[0] = x;
	//元素个数加一
	h->size++;
}

这样我们的头插也就完成啦

顺序表的头删尾删 

 顺序表的尾删#

对于删除表尾元素，直接将表中的元素个数减一即可

void PopBack(SL* h)
{
	//判断顺序表是否为空
	assert(h);
	assert(h->size);
	//顺序表不为空
	//减掉元素个数
	h->size--;
}

我们发现末尾的三个元素被删除了，这样我们的尾删接口也就完成啦

顺序表的头删#

对于删除表中首元素，需要将首位置之后的元素前移，最后将表中的元素个数减一

void PopFront(SL* h)
{
	assert(h);
	assert(h->size);
	//用后面的元素覆盖前一个元素
	for (int i = 0; i < h->size - 1; i++)
	{
		h->str[i] = h->str[i + 1];
	}
	h->size--;
}

这样我们的头删也就完成啦！！！是不是难不倒你呢？

顺序表的指定插入删除 

顺序表的指定插入#

以下是将元素6插入指定位置3的图片模拟

对于在表中任意位置插入元素，需要先将插入位置及其之后的元素后移，然后再将要插入的元素放入合适的位置

void SLInsert(SL* h, int pos, SLDataType x)
{
	//判断动态内存是否开辟成功
	assert(h);
	//规定pos的范围区间
	assert(pos>=0&&pos<=h->size);
	SLCheckCapacity(h);
	//pos之后的数据全部往后挪动一位，pos空出来
	for (int i = h->size; i > pos; i--)
	{
		h->str[i] = h->str[i - 1];
	}
	h->str[pos] = x;
	h->size++;
}

我们发现7和0以及10已经插入了我们指定的位置啦

顺序表的指定删除#

以下是删除指定位置3的图片模拟

对于删除表中任意元素，需要先找到要删除的元素的位置，然后将该位置之后的元素前移，最后将表中的元素个数减一

void PopErase(SL* h, int pos)
{
	//判断动态内存是否开辟成功
	assert(h);
	assert(pos >= 0 && pos <= h->size);
	//pos后面的数从后往前移动
	for (int i = pos; i < h->size-1; i++)
	{
		h->str[i] = h->str[i + 1];
	}
	h->size--;
}

我们发现0和1以及2已经在我们指定的位置删除啦

顺序表的动态内存销毁 

void SeqListFree(SL* h)
{
	free(h->str); //释放动态申请的内存空间
	h->str = NULL;//置空指针
	h->size = 0;
	h->capacity = 0;
}

为了避免发生程序的内存泄露问题，在不使用空间的时候记得释放哦

 以下是全部代码的实现：

#include<stdio.h> 
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* str;   
	int capacity;      
	int size;          
}SL;                  

void SLInit(SL* h);         
void SLCheckCapacity(SL* h);
void SLPrint(SL* h);
void SLPushBack(SL* h, SLDataType x);
void SLPushFront(SL* h, SLDataType x);
void PopBack(SL* h);
void PopFront(SL* h);
void SLInsert(SL* h, int pos, SLDataType x);
void PopErase(SL* h, int pos);
void SeqListFree(SL* h);

void SLInit(SL* h)
{
	h->str = NULL;
	h->capacity = h->size = 0;
}

void SLCheckCapacity(SL* h)
{
	if (h->size == h->capacity)
	{
		int newCapacity = h->capacity = 0 ? 4 : 2 * h->capacity;
		SLDataType* tmp = (SLDataType*)malloc(h->str, newCapacity * sizeof(SLDataType));
		assert(tmp);
		h->str = tmp;
		h->capacity = newCapacity;
	}
}

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

void SLPushBack(SL* h, SLDataType x)
{
	SLCheckCapacity(h);
	h->str[h->size++] = x;
}

void SLPushFront(SL* h,SLDataType x)
{
	SLCheckCapacity(h);
	for (int i = h->size; i > 0; i--)
	{
		h->str[i] = h->str[i - 1];
	}
	h->str[0] = x;
	h->size++;
}

void PopBack(SL* h)
{
	assert(h);
	assert(h->size);
	h->size--;
}

void PopFront(SL* h)
{
	assert(h);
	assert(h->size);
	for (int i = 0; i < h->size - 1; i++)
	{
		h->str[i] = h->str[i + 1];
	}
	h->size--;
}

void SLInsert(SL* h, int pos, SLDataType x)
{
	assert(h);
	assert(pos>=0&&pos<=h->size);
	SLCheckCapacity(h);
	for (int i = h->size; i > pos; i--)
	{
		h->str[i] = h->str[i - 1];
	}
	h->str[pos] = x;
	h->size++;
}

void PopErase(SL* h, int pos)
{
	assert(h);
	assert(pos >= 0 && pos <= h->size);
	for (int i = pos; i < h->size-1; i++)
	{
		h->str[i] = h->str[i + 1];
	}
	h->size--;
}


void SeqListFree(SL* h)
{
	free(h->str); 
	h->str = NULL;
	h->size = 0;
	h->capacity = 0;
}

void CeShi()
{
	SL s1;
	SLInit(&s1);
}

int main(void)
{
	CeShi();
	system("pause");
}

顺序表在解题中的运用 

移除元素

题目链接：移除元素

题目描述#

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明#

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5并且 nums 中的前五个元素为 0 1 3 0 4注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

思路：

<1>定义两个快慢指针，都指向开头

<2>如果没有遇到val两个指针就一起走，并且left将当前的值给right指针

<3>遇到val时，left先去寻找共同的目标(不是val的数)并把它给right

<4>这样返回right就是移除后的新长度

class Solution 
{
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int left = 0;
        int right = 0;
        int n = nums.size();//计算数组大小
        while(left<n)
        {
            if(nums[left] !=  val)
            {
              nums[right++] = nums[left++];
            }
            else
            {
                left++;
            }
        }
        return right;
    }
};

总结： 

<1>编写代码量大的项目，要学会分模块写

<2>动态内存在不适使用的情况下，记得销毁，避免内存泄露

<3>顺序表的本质就是数组，只不过增加了增删查改的功能

<4>在静态分配时，由于数组的大小和空间是固定的，一旦空间占满，就无法再新增数据，否则会导致数据溢出

<5>在动态分配时，存储数组的空间在程序执行过程中会动态调整大小，当空间占满时，可以另行开辟更大的存储空间来储存数据

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Vue3前端开发，computed计算属性的基础练习

Vue3前端开发，computed计算属性的基础练习

Vue3前端开发&#xff0c;computed计算属性的基础练习&#xff01; 在新版里面&#xff0c;和传统的vue2一样&#xff0c;计算属性&#xff0c;都是对一些数据运算进行了封装操作。返回结果是一个实时监控的效果。区别在于&#xff0c;写法不同。效果是一样。 下面给大家展示…
阅读更多...
【萤火虫系列教程】3/5-Adobe Firefly 创意填充

【萤火虫系列教程】3/5-Adobe Firefly 创意填充

003-Adobe Firefly 创意填充 创意填充 登录账号后&#xff0c;在主页点击创意填充的【生成】按钮&#xff0c;进入到创意填充页面 我们可以上传自己的图像 一键抠图 点击【背景】就可以把主图抠出来 点击【反转】就可以把背景抠出来 点击【清除】就可以恢复到图片原来…
阅读更多...
一文详解Linux文本处理三剑客

一文详解Linux文本处理三剑客

1.正则表达式 目录 1.正则表达式 1.什么是正则表达式 &#xff1f; 2.正则表达式的使用场景 3.正则表达式字符表示 4.它们之间的区别 2.grep命令 作用&#xff1a; 语法&#xff1a; 说明&#xff1a; 选项&#xff1a;options 重点 实例 3.后面的下次再更新。 …
阅读更多...
【征服redis7】谈谈Redis的RDB持久化方式

【征服redis7】谈谈Redis的RDB持久化方式

从现在开始&#xff0c;我们来探讨redis的一个非常重要的问题——集群&#xff0c;要讨论集群&#xff0c;我们需要先理解redis持久化数据的方法&#xff0c;因为集群本质上就是将一个集群的数据同步到其他机器上。 Redis 6的持久化机制主要有两种&#xff1a;RDB&#xff08;…
阅读更多...
【CUDA】GPU 算力与 CUDA 版本对应关系

【CUDA】GPU 算力与 CUDA 版本对应关系

1. 查询 GPU 算力&#xff08;Compute Capability&#xff09; 官方算力表&#xff1a;https://developer.nvidia.com/cuda-gpus#compute 2. GPU 算力与 CUDA 版本对应关系 2.1. 信息来源 1 https://docs.nvidia.com/datacenter/tesla/drivers/index.html#cuda-arch-matri…
阅读更多...
Kafka-消费者-KafkaConsumer分析-SubscriptionState

Kafka-消费者-KafkaConsumer分析-SubscriptionState

KafkaConsumer从Kafka拉取消息时发送的请求是FetchRequest(具体格式后面介绍),在其中需要指定消费者希望拉取的起始消息的offset。 为了消费者快速获取这个值&#xff0c;KafkaConsumer使用SubscriptionState来追踪TopicPartition与offset对应关系。 图展示了SubscriptionSta…
阅读更多...
el-dialog嵌套使用，只显示遮罩层的问题

el-dialog嵌套使用，只显示遮罩层的问题

直接上解决方法 <!-- 错误写法 --><el-dialog><el-dialog></el-dialog></el-dialog><!-- 正确写法 --><el-dialog></el-dialog><el-dialog></el-dialog>我是不建议嵌套使用的&#xff0c;平级也能调用&#xff0c…
阅读更多...
LaWGPT安装和使用教程的复现版本【细节满满】

LaWGPT安装和使用教程的复现版本【细节满满】

文章目录 前言一、下载和部署1.1 下载1.2 环境安装1.3 模型推理 总结 前言 LaWGPT 是一系列基于中文法律知识的开源大语言模型。该系列模型在通用中文基座模型&#xff08;如 Chinese-LLaMA、ChatGLM等&#xff09;的基础上扩充法律领域专有词表、大规模中文法律语料预训练&am…
阅读更多...
Qt 状态机框架:The State Machine Framework (二)

Qt 状态机框架:The State Machine Framework (二)

传送门: Qt 状态机框架:The State Machine Framework (一) Qt 状态机框架:The State Machine Framework (二) 1、利用并行态避免态的组合爆炸 假设您想在单个状态机中对汽车的一组互斥属性进行建模。假设我们感兴趣的属性是干净与肮脏&#xff0c;以及移动与不移动。需要四个…
阅读更多...
【教3妹学编程-算法题】检查按位或是否存在尾随零

【教3妹学编程-算法题】检查按位或是否存在尾随零

3妹&#xff1a;呜呜&#xff0c;烦死了&#xff0c; 脸上长了一个痘 2哥 : 不要在意这些细节嘛&#xff0c;不用管它&#xff0c;过两天自然不就好了。 3妹&#xff1a;切&#xff0c;你不懂&#xff0c;影响这两天的心情哇。 2哥 : 我看你是不急着找工作了啊&#xff0c; 工作…
阅读更多...
Golang通过Gorm操作Mysql时遇到的datetime时区问题

Golang通过Gorm操作Mysql时遇到的datetime时区问题

情景描述 golang使用Gorm操作MySQL&#xff0c;MySQL中数据类型是datetime&#xff0c;Golang中用的是time.now。 但是会导致存储的时间与北京时间有8h误差&#xff0c; 显然是没有初始化时区导致。 问题修复 初始化设置时区 参考我自己之前写过的一篇总结——Mysql中多种日…
阅读更多...
QT上位机开发（不同场景下界面的设计模板）

QT上位机开发（不同场景下界面的设计模板）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 qt由于其优秀的跨平台属性&#xff0c;几乎成了嵌入式开发界面开发的标配。同时呢&#xff0c;由于它在windows平台开发出来的效果也是非常的好&am…
阅读更多...
Python开发环境安装:梦的起点

Python开发环境安装:梦的起点

Python解释器安装 前言 解释器&#xff08;Interpreter&#xff09;&#xff0c;又译为直译器&#xff0c;是一种电脑程序能够把高级编程语言一行一行直接转译运行。解释器不会一次把整个程序转译出来&#xff0c;只像一位“中间人”&#xff0c;每次运行程序时都要先转成另一…
阅读更多...
dubbo入门案例！！！

dubbo入门案例！！！

入门案例之前我们先介绍一下&#xff1a;zookeeper。 Zookeeper是Apacahe Hadoop的子项目&#xff0c;可以为分布式应用程序协调服务&#xff0c;适合作为Dubbo服务的注册中心&#xff0c;负责服务地址的注册与查找&#xff0c;相当于目录服务&#xff0c;服务提供者和消费者只…
阅读更多...
rust跟我学七:获取外网IP地址

rust跟我学七:获取外网IP地址

图为RUST吉祥物 大家好，我是get_local_info作者带剑书生，这里用一篇文章讲解get_local_info是怎么获取到本机的外网IP地址。 首先，先要了解get_local_info是什么？ get_local_info是一个获取linux系统信息的rust三方库，并提供一些常用功能，目前版本0.2.4。详细介绍地址：[…
阅读更多...
测试驱动开发：基于Jenkins+GoTest+HTML的持续化集成

测试驱动开发：基于Jenkins+GoTest+HTML的持续化集成

目录 前言 一、项目框架 1.项目迭代 2.项目时序图 3.项目测试执行 二、项目具体实现 1.创建流水线 2.拉取代码 3.执行测试代码 4.生成测试报告 5.报告内容解读 6.数据统计 7.邮件通知 8.企业微信通知 三、项目遇到的问题 1.go test -args 2.go test生…
阅读更多...
MyBatisPlus学习笔记四-扩展功能

MyBatisPlus学习笔记四-扩展功能

1、代码生成器 1.1、官方的1 1.3、官方的2-idea插件 1.3、非官方的-idea插件 2、静态工具 先查询&#xff0c;再分组 3、逻辑删除 4、枚举处理器 5、JSON处理器
阅读更多...
二、ArcGIS Pro SDK 开发环境配置踩坑

二、ArcGIS Pro SDK 开发环境配置踩坑

上篇写了如何配置开发环境&#xff0c;也确实是配置好了&#xff0c;激动的就睡觉去了&#xff0c;万万没想到&#xff0c;今天当要创建工程的时候&#xff0c;结果发现创建不了&#xff0c;弹出了如下错误&#xff1a; 很郁闷&#xff0c;于是有查找了资料发现&#xff1a; 是…
阅读更多...
2024年华数杯国际赛B题超详细解题思路

2024年华数杯国际赛B题超详细解题思路

ICM B题&#xff1a;光伏发电 该题目出题的难度与方向都与美赛ICM的题型高度相似&#xff0c;将本次竞赛当做美赛的练手赛&#xff0c;个人认为是非常合适的一种选择。同时28号就可以出成绩&#xff0c;也可以在美赛前实现查漏补缺&#xff0c;提前预祝大家比赛顺利&#xff0…
阅读更多...
如何用WhatsApp做外贸？

如何用WhatsApp做外贸？

WhatsApp 可帮助企业和客户快速建立个性化的联系&#xff0c;进行产品和服务类营销推广&#xff0c;并在购物过程中及时回应和解决客户的问题。 WhatsApp Business还可以帮助大中型企业提供客户服务支持&#xff0c;并向客户发出消息通知。 如果是中小企业&#xff0c;可以使用…
阅读更多...
最新文章

Copyright @ 2022~2023