线性表(上):Seqlist 顺序表

  • 基本了解
    • 线性表
    • 顺序表
    • 静态顺序表
    • 动态顺序表
  • 编写动态顺序表
    • 项目结构
    • 基础结构
    • 初始化
    • 尾插
    • 头插
    • 尾删
    • 头删
    • 查找
    • 指定位置pos之前插入数据
    • 删除指定位置pos的数据
    • 销毁
    • 完整代码
      • SeqLIst.h
      • SeqLIst.c
      • test.c
  • 算法题
    • 移除元素
    • 删除有序数组中的重复项

基本了解

线性表

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

顺序表

概念:顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构,⼀般情况下采⽤数组存储。顺序表一般分为静态顺序表和动态顺序表。
在这里插入图片描述

静态顺序表

优点:一次性开辟空间
缺点:不可改动,当数据量变化时,空间给大了会造成浪费,空间给小了容易导致数据丢失等问题。

typedef int SLDataType;
#define N 7
typedef struct SeqList {SLDataType arr[N];//定长数组int size;		//有效数据个数int capacity;	//空间大小
}SL;

动态顺序表

优点:灵活可改动,随时可扩容

typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//动态顺序表,定义动态数组int size;		//有效数据个数int capacity;	//空间大小
}SL;

增容的一般逻辑:
在这里插入图片描述

编写动态顺序表

项目结构

SeqList
├── SeqList.h	# 头文件:定义结构、声明
函数
├── SeqList.c	# 实现文件:函数具体实现└── test.c		# 测试文件:每写一个功能以后都要测试一下

在这里插入图片描述

基础结构

SeqLIst.h 中

typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//动态顺序表,定义动态数组int size;		//有效数据个数int capacity;	//空间大小
}SL;

初始化

这里有一个易错点提醒:函数传参时一定要思考是要传值还是传址,只有传址,函数改动的才是传过去的变量本身!
比如如果初始化函数这么写

void SLInit(SL s) {s.arr = NULL;s.size = s.capacity = 0;
}

测试

void test01() {SL sl;SLInit(sl);
}int main() {test01();return 0;
}

在这里插入图片描述
此时就会报这样的错误,为什么呢?
因为传值传参,函数中形参是实参的拷贝,但sl是未初始化的变量,所以这个值拷贝无法完成,自然就会报错了

所以注意此处进行传址调用

void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}
void test01() {SL sl;SLInit(&sl); //注意这里要传地址
}int main() {test01();return 0;
}

尾插

在这里插入图片描述

注释中标明了易错的步骤和知识重点

void SLPushBack(SL* ps, SLDataType x) {//尾插前先判断顺序表是否仍有位置插入if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一开始capacity==0,做乘法以后仍为0出现问题SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) *ps->capacity*2);//用临时指针接收realloc的返回值,防止扩容失败返回NULL,导致影响顺序表的存储//注意realloc第二个参数单位是字节,扩容至原capacity的两倍时,别忘了要乘上SLDataType的字节大小//realloc扩容逻辑:能就地扩就就地扩;不能就另找一块(malloc新的内存块)、拷贝(memcpy)、释放旧块(free)if (tmp == NULL) {perror("realloc fail!");//会在输出里变成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}//尾插操作,可以画图思考,发现size大小实时对应尾插的位置,不需要额外遍历//记得自增size!ps->arr[ps->size++] = x;
}

测试

//测试尾插
void test02() {SL sl;SLInit(&sl);SLPushBack(&sl,1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);
}
int main() {test02();return 0;
}

时间复杂度为O(n)

头插

判满——将数据向右挪动(从右往左依次挪!)——把新数据放到头部
在这里插入图片描述

判满操作是在多个功能中都需要使用到的,所以这里我们把它单独分出来

//判满扩容操作
void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一开始capacity==0,做乘法以后仍为0出现问题SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//用临时指针接收realloc的返回值,防止扩容失败返回NULL,导致影响顺序表的存储//注意realloc第二个参数单位是字节,扩容至原capacity的两倍时,别忘了要乘上SLDataType的字节大小//realloc扩容逻辑:能就地扩就就地扩;不能就另找一块(malloc新的内存块)、拷贝(memcpy)、释放旧块(free)if (tmp == NULL) {perror("realloc fail!");//会在输出里变成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}
}
void SLPushHead(SL* ps, SLDataType x) {//检查一下ps,如果传入了空指针会导致程序直接报错////比较温和的方法//if (ps == NULL)//	return;//比较粗暴的方法:使用断言语句assert(ps);//等价于assert(ps!=NULL)SLCheckCapacity(ps);for (int i = ps->size - 1;i >= 0;i--) {ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;
}

时间复杂度为O(n)

尾删

特殊条件:顺序表不能为空
操作:有效数据个数size–,原来的数据不做处理也没有关系

void SLPopBack(SL* ps) {assert(ps && ps->size);ps->size--;
}

时间复杂度O(1)

头删

特殊条件:顺序表不能为空
操作:

  1. 让数组从左到右往左移一位(覆盖)
  2. 有效数据个数size–,原来的数据不做处理也没有关系
void SLPopHead(SL* ps) {assert(ps && ps->size);for (int i = 1;i < ps->size;i++) {ps->arr[i - 1] = ps->arr[i];}ps->size--;
}

时间复杂度O(n)

查找

设定找到了返回下标,未找到返回-1

int SLFind(SL ps, SLDataType x) {for (int i = 0;i < ps.size;i++) {if (ps.arr[i] == x)return i;//找到了就返回位置}//会运行到这一定是没有找到return -1;
}

指定位置pos之前插入数据

在指定位置pos之前插入数据,实际上新数据就放在pos位置
特殊条件:插入都要判断空间够不够,删除都要判空
且pos有限制范围pos>=0&&pos<=size
核心操作:pos之后的数据向右挪动一位(从右往左挪)

//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//插入都要判断一下!for (int i = ps->size;i > pos;i--) {ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

删除指定位置pos的数据

特殊条件:删除都要判空,且pos有限制范围pos>=0&&pos<=size
核心操作:pos之后的数据向左挪动一位(从左往右往左挪)

//指定位置删除数据
void SLErase(SL* ps, int pos) {assert(ps&&ps->size);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size-1;i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

销毁

//销毁
void SLDesTroy(SL* ps) {if (ps->arr) {//即arr非空free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

完整代码

SeqLIst.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//动态顺序表,定义动态数组int size;		//有效数据个数int capacity;	//空间大小
}SL;//初始化
void SLInit(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//头插
void SLPushHead(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);//头删
void SLPopHead(SL* ps);//查找
int SLFind(SL ps, SLDataType x);//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x);//指定位置删除
void SLErase(SL* ps, int pos);//销毁
void SLDesTroy(SL* ps);

SeqLIst.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//初始化
void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}//判满扩容操作
void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一开始capacity==0,做乘法以后仍为0出现问题SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//用临时指针接收realloc的返回值,防止扩容失败返回NULL,导致影响顺序表的存储//注意realloc第二个参数单位是字节,扩容至原capacity的两倍时,别忘了要乘上SLDataType的字节大小//realloc扩容逻辑:能就地扩就就地扩;不能就另找一块(malloc新的内存块)、拷贝(memcpy)、释放旧块(free)if (tmp == NULL) {perror("realloc fail!");//会在输出里变成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}
}
//尾插
void SLPushBack(SL* ps, SLDataType x) {SLCheckCapacity(ps);//尾插操作,可以画图思考,发现size大小实时对应尾插的位置,不需要额外遍历//记得自增size!ps->arr[ps->size++] = x;
}//头插
void SLPushHead(SL* ps, SLDataType x) {//检查一下ps,如果传入了空指针会导致程序直接报错////比较温和的方法//if (ps == NULL)//	return;//比较粗暴的方法:使用断言语句assert(ps);//等价于assert(ps!=NULL)SLCheckCapacity(ps);for (int i = ps->size - 1;i >= 0;i--) {ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;//记得自增size!ps->size++;
}//尾删
void SLPopBack(SL* ps) {assert(ps && ps->size);ps->size--;
}//头删
void SLPopHead(SL* ps) {assert(ps && ps->size);for (int i = 1;i < ps->size;i++) {ps->arr[i - 1] = ps->arr[i];}ps->size--;
}//查找
int SLFind(SL ps, SLDataType x) {for (int i = 0;i < ps.size;i++) {if (ps.arr[i] == x)return i;//找到了就返回位置}//会运行到这一定是没有找到return -1;
}//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//插入都要判断一下!for (int i = ps->size;i > pos;i--) {ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//指定位置删除数据
void SLErase(SL* ps, int pos) {assert(ps&&ps->size);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size-1;i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//销毁
void SLDesTroy(SL* ps) {if (ps->arr) {//即arr非空free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//测试初始化
void test01() {SL sl;SLInit(&sl);
}void test02() {SL sl;SLInit(&sl);//SLPushBack(&sl, 1);//SLPushBack(&sl, 2);//SLPushBack(&sl, 3);//SLPushBack(&sl, 4);//SLPushBack(&sl, 5);SLPushHead(&sl, 1);SLPushHead(&sl, 2);SLPushHead(&sl, 3);SLPushHead(&sl, 4);SLPushHead(&sl, 5);/*for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLPopHead(&sl);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLPopBack(&sl);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");*///测试findSLErase(&sl, 2);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLInsert(&sl, 2, 7);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");
}int main() {test02();return 0;
}

算法题

移除元素

在这里插入图片描述
本题首先要审题,弄明白评测需要什么

  1. 返回非val的值的个数
  2. 修改nums,使它的前k个数必须是非val的值(顺序不变),后面的数不管。
    在这里插入图片描述
    新数组法:创建一个与nums长度相同的新数组,只选取不等于val的值存储进去,同时进行计数。再将新数组遍历赋回给nums。(之前也说过,这个方法是以空间换时间的方法)
    双“指针”法
    简述思路:记录两个下标,一个负责探路,一个负责存储和计数,一次遍历中两个下标同时发挥其作用。
    在这里插入图片描述
int removeElement(int* nums, int numsSize, int val) {int src=0,dst=0;while(src<numsSize){if(nums[src]!=val){nums[dst]=nums[src];dst++;}src++;}return dst;
}

删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
在这里插入图片描述
注意题目强调有序数组,这意味着重复项都在一起,要利用好这个特性。
新数组法
创建一个与nums长度相同的新数组,只选取符合条件的数字进去,再将新数组遍历赋回给nums。
双"指针"法
画图思考让思路更清晰!
依然是src负责读取数据,dst负责录入数据和返回数据数量
想象src在数组上面走,dst在数组下面走。
在这里插入图片描述

int removeDuplicates(int* nums, int numsSize) {int src=1,dst=0;//因为第一个元素一定算数,所以src可以从1开始走while(src<numsSize){if(nums[src]!=nums[dst]){nums[++dst]=nums[src];}src++;}return dst+1;
}

这个代码还可以做进一步优化,减少没必要的赋值操作:
当nums[src]!=nums[dst]时,如果src只比dst小1, nums[++dst]=nums[src];就相当于这个值自己给自己赋了,所以我们可以据此对代码进一步优化。

int removeDuplicates(int* nums, int numsSize) {int src=1,dst=0;//因为第一个元素一定算数,所以src可以从1开始走while(src<numsSize){if(nums[src]!=nums[dst]&&++dst!=src){nums[dst]=nums[src];}src++;}return dst+1;
}

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

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

相关文章

WebStorm vs VSCode:前端圈的「豆腐脑甜咸之争」

目录 一、初识两位主角&#xff1a;老司机与新势力 二、开箱体验&#xff1a;是「拎包入住」还是「毛坯房改造」 三、智能提示&#xff1a;是「知心秘书」还是「百度搜索」 四、调试功能&#xff1a;是「CT 扫描仪」还是「听诊器」 五、性能表现&#xff1a;是「重型坦克」…

C#将类属性保存到Ini文件方法(利用拓展方法,反射方式获取到分组名和属性名称属性值)

前言&#xff1a;最近学习C#高级课程&#xff0c;里面学到了利用反射和可以得到属性的特性、属性名、属性值&#xff0c;还有拓展方法&#xff0c;一直想将学到的东西利用起来&#xff0c;刚好今天在研究PropertyGrid控件时&#xff0c;想方便一点保存属性值到配置文件&#xf…

kafka 单机部署指南(KRaft 版本)

目录环境准备JDK安装下载jdkjdk安装kafka 部署kafka 下载kafka 版本号结构解析kafka 安装下载和解压安装包配置 KRaft 模式格式化存储目录启动kafkaKafka 配置为 systemd 服务注意事项调整 JVM 内存参数Kafka KRaft 版本&#xff08;即 Kafka 3.0 及更高版本&#xff09;使用 K…

websocket案例 599足球比分

目标地址:aHR0cHM6Ly93d3cuNTk5LmNvbS9saXZlLw接口:打开控制台 点websocket 刷新页面 显示分析:不写理论了关于websocket 几乎发包位置都是下方图片 不管抖音还是快手 等平台这里在进行 new WebSocket 后 是要必须走一步的 也就是 new WebSocket().onopen() 也就是onopen 进行向…

【后端】Linux系统发布.NetCore项目

目录 1.设置全球化不变模式 1.发布到文件 3. 配置为服务 3.1.添加服务 3.2.添加执行权限 3.3.启动服务 4.访问 1.设置全球化不变模式 双击所需项目&#xff0c;设置全球化不变模式 <!-- 设置全球化不变模式 --><RuntimeHostConfigurationOption>System.Globa…

CMU-15445(2024fall)——PROJECT#0

题目介绍 这是题目原文。 注意&#xff1a;在拉取项目的时候需要注意拉取2024fall的Tag&#xff0c;本人血泪教训&#xff01; 本题是关于HyperLogLog的具体实现&#xff0c;其介绍可以看这个视频进行了解。简单来说HyperLogLog可以在一个非常小的固定内存下&#xff08;一般…

使用微信免费的图像处理接口,来开发图片智能裁剪和二维码/条码识别功能,爽歪歪

大家好&#xff0c;我是小悟。 1、图片智能裁剪 我们先来了解一下图片智能裁剪。图片智能裁剪聚焦于数字图像的智能化处理。AI技术的引入彻底改变了传统依赖人工框选的裁剪模式。 通过深度学习模型自动识别图像主体&#xff08;人物、商品等&#xff09;&#xff0c;能在极短时…

【代码随想录】+ leetcode hot100:栈与队列算法专题总结、单调栈

大家好&#xff0c;我是此林。 今天分享的是【代码随想录】栈与队列算法专题总结&#xff0c;分享刷算法的心得体会。 1. 用栈实现队列、用队列实现栈 232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 225. 用队列实现栈 - 力扣&#xff08;LeetCode&#xff09;…

《5分钟开发订单微服务!飞算JavaAI实战:IDEA插件安装→空指针修复→K8s部署全流程》

目录 40倍提升开发效能的秘密武器 一、为什么选择飞算JavaAI&#xff1f;​编辑 二、IDEA插件安装三步曲&#xff08;极简版&#xff09; 步骤1&#xff1a;安装插件&#xff08;30秒完成&#xff09; 步骤2&#xff1a;账号登录&#xff08;2种方式任选&#xff09; 方式…

SQL注入基础尝试

进入网址&#xff0c;测试正常回显和出错画面http://1bcf75af-6e69-4f78-ac71-849fb8cde1b5.node5.buuoj.cn/Less-2/? id1用特殊符号判断注入点判断其类型类型为数字型&#xff0c;order by判断列数当数字为4时候报错而3不报错&#xff0c;由此推断列数为3&#xff0c;接着测试…

[Dify] -进阶4-在 Dify 中实现 PDF 文档问答功能全流程

随着业务需求增加,AI 应用常遇到让模型“读懂”PDF并回答问题的场景。借助 Dify 的 RAG(Retrieval‑Augmented Generation)能力,我们可以构建一个“ChatPDF”式的互动问答机器人。本文详细讲解从环境搭建、PDF 上传、文本抽取、向量检索到问答部署的完整流程。 一、技术栈与…

【EPLAN 2.9】许可证xx成功却显示红色叉,无法启动

问题现象&#xff1a; 无法启动。 原因&#xff1a;通过mstsc远程桌面连接会占用显卡&#xff0c;导致调用显卡的软件无法成功。参考&#xff1a;Windows自带远程桌面(mstsc)在远程时无法启动&#xff08;打开&#xff09;某些应用&#xff08;软件&#xff09;的解决办法 编写…

Oracle ADG 一键自动化搭建脚本

前言在 Oracle 数据库高可用架构中&#xff0c;Active Data Guard (ADG) 是保障数据安全和业务连续性的核心方案。然而传统 ADG 搭建涉及数十项复杂配置&#xff08;监听、TNSNAMES、参数文件、密码文件、日志传输、应用服务等&#xff09;&#xff0c;步骤繁琐且易错&#xff…

某邮生活旋转验证码识别

注意,本文只提供学习的思路,严禁违反法律以及破坏信息系统等行为,本文只提供思路 如有侵犯,请联系作者下架 本文识别已同步上线至OCR识别网站: http://yxlocr.nat300.top/ocr/other/30 旋转验证码数据集如下: 看起来很像顶象的,都有着绿边干扰,那其实思路也能简单了,…

基于Android的景点旅游信息系统App

项目介绍用户分为普通用户和管理员两种角色。 1.管理员有用户管理、景点管理、评论管理功能。 2.用户管理包括查看已注册用户列表、删除用户&#xff1b; 3.景点管理包括增加景点信息、修改景点信息、删除景点信息、将景点设为推荐&#xff1b; 4.评论管理包括查看评论内容、删…

Python----NLP自然语言处理(词向量与词嵌入)

一、词向量与词嵌入将文本语料分词后&#xff0c;接下来就可以让计算机学习这些词&#xff0c;理解这些词的含义。我们可以直接将文本数据输入到计算机中让计算机学习吗&#xff1f;不可以&#xff0c;计算机只能看懂数字&#xff0c;看不懂文字。所以我们需要将词语转成一串数…

八、DMSP/OLS、NPP/VIIRS等夜间灯光数据能源碳排放空间化——碳排放空间分级、空间自相关

一、前言 前面已经将反演后能源碳排放提取、增长率、Slope趋势法分析做了介绍,本节就是给大家介绍如何制作碳排放空间分级和空间自相关的一些具体操作步骤,其实网上也有比较多的各类学习资源,但是质量就层次不齐。这里就给大家详细从头到尾说明白解释清楚如何获取下图这些成…

【电脑】鼠标的基础知识

下面是一些关于鼠标的详细知识&#xff1a;鼠标的基本结构外壳&#xff1a;通常由塑料或金属制成&#xff0c;提供手握的地方。滚轮&#xff1a;位于中央&#xff0c;用于滚动页面。有些高端型号的滚轮可以自定义功能。按键&#xff1a;最常见的是左键、右键和中键&#xff08;…

A33-vstar笔记及资料分享:搭建交叉编译环境

前言 本篇主要是介绍博主在构建A33-vstar开发板镜像时的步骤&#xff0c;也踩了一些坑&#xff0c;才整理出来&#xff0c;如果有错误&#xff0c;还请指正。 A33-vstar开发板的资料&#xff1a; 通过网盘分享的文件&#xff1a;A33-Vstar开发板资料合集 链接: https://pan.bai…

基于51单片机智能家居监控系统设计

摘 要 智能家居是以住宅为平台&#xff0c;利用综合布线技术、网络通信技术、安全防范技术、自动控制技术、音视频技术将家居生活有关的设施集成&#xff0c;构建高效的住宅设施与家庭日程事务的管理系统&#xff0c;提升家居安全性、便利性、舒适性、艺术性&#xff0c;并实现…