【初阶数据结构篇】顺序表的实现(赋源码)
文章目录
- 本篇代码位置
- 顺序表和链表
- 1.线性表
- 2.顺序表
- 2.1 概念与结构
- 2.2分类
- 2.2.1 静态顺序表
- 2.2.2 动态顺序表
- 2.3 动态顺序表的实现
- 2.3.1动态顺序表的初始化和销毁及打印
- 2.3.2动态顺序表的插入
- 动态顺序表的尾插
- 动态顺序表的头插
- 动态顺序表的在指定位置插入数据
- 2.3.3动态顺序表的删除
- 动态顺序表的尾删
- 动态顺序表的头删
- 动态顺序表的在指定位置删除数据
- 2.3.4动态顺序表查找指定数据
本篇代码位置
代码位置
顺序表和链表
1.线性表
线性表(linearlist)是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的 数据结构,常见的线性表:顺序表、链表、栈、队列、字符串······
线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的,线性 表在物理上存储时,通常以数组和链式结构的形式存储。
2.顺序表
2.1 概念与结构
概念:顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构,⼀般情况下采⽤数组存储。
顺序表和数组的区别?
顺序表的底层结构是数组,对数组的封装,实现了常⽤的增删改查等接⼝。可以这么理解,我们使用数组来存储数据,并提供了增删查改数据的接口(函数),这样组织和存储数据的结构我们将它称为顺序表。
2.2分类
2.2.1 静态顺序表
概念:使用定长数组存储元素
- 缺陷:显而易见的,空间一定,给少了不够用,给多了太浪费
2.2.2 动态顺序表
概念:不存储数组,而是存储一个指向一块动态开辟的内存空间的指针
-
优点:按需开辟,可增容
故我们一般都使用动态顺序表
2.3 动态顺序表的实现
2.3.1动态顺序表的初始化和销毁及打印
创建顺序表,并将其中的指针置为NULL,容量和有效数据个数置为0,销毁大致相同,不过如果arr指针非空,不要忘了释放动态申请的空间
SeqList.h(其中方法会一一讲到)
- 定义顺序表结构
- 将存储数据类型重命名(方便之后替换->例如我们要求顺序表内存储char类型数据,只用改一行代码即可)
- 所写的函数的声明,声明的时候参数只需要类型就可以了,名字加不加都一样
#pragma once
#include <stdio.h>
#include<stdlib.h>
#include <assert.h>typedef int sldatatype;
typedef struct Seqlist
{sldatatype* arr;sldatatype size;sldatatype capacity;
} sl;
void slinit(sl*);//初始化
void sldestroy(sl*);//销毁void slprint(sl*);//打印
void checkcapacity(sl*);//判断空间是否足够
void slpushback(sl*, sldatatype);//尾插
void slpushfront(sl*, sldatatype);//头插void slpopfront(sl*);//头删
void slpopback(sl*);//尾删//在指定位置插入和删除数据
void slinsert(sl*, sldatatype, int);
void slfrase(sl*, int);//查找指定数据int slfind(sl*, sldatatype);
test.c
- 用来测试我们写的函数(函数的调用)
- 这一部分就是自己写的时候用的测试用例,随便什么都行
最好是写一个方法测试一次,不然找错误的时候会很痛苦😜
sl s;//要改变s结构体之中的内容,别忘了传地址#define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"
void sltest1()
{sl s;slinit(&s);slpushback(&s, 1);slpushback(&s, 2);slpushback(&s, 6);slpushback(&s, 5);int m=slfind(&s, 7);printf("%d\n", m);//slpushfront(&s, 2);//slpushfront(&s, 3);//slinsert(&s, 1, 0);//slinsert(&s, 2, 6);//slinsert(&s, 1,0 );//slfrase(&s, 1);//slfrase(&s, 0);//slfrase(&s, 1);//slpopback(&s);//slpopback(&s);//slpopback(&s);//slpopback(&s);//slpopback(&s);slpushback(NULL, 6);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);slprint(&s);sldestroy(&s);
}
int main()
{sltest1();return 0;
}
SeqList.c
函数方法的实现,重点重点!!!
在每一个方法的第一排都使用assert宏来判断ps是否为空(避免使用时传入空指针,后续解引用都会报错)
void slinit(sl* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->size = 0;
}void sldestroy(sl*ps)
{assert(ps);if (ps->arr){free(ps->arr);ps->arr = NULL;}ps->capacity = ps->size = 0;
}
考虑到每次测试方法时调试会很麻烦,于是先写一个打印顺序表的方法
void slprint(sl* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}
}
- 遍历就行了,和打印数组一样的
2.3.2动态顺序表的插入
插入数据的时候一定要判断空间是否足够,不足要增容,一般2倍或3倍增容!!!
SeqList.c
养成好习惯,不要用arr直接接收动态开辟空间的地址,否则开辟失败arr变为NULL,连原来的内存块都找不到了,这就造成了内存泄漏!!!
void slcheckcapacity(sl* ps)
{assert(ps);if (ps->capacity == ps->size){//增容//若capacity为0,给个默认值,否则乘以2int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;sldatatype* tmp = (sldatatype*)realloc(ps->arr, newcapacity * sizeof(sldatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}}
动态顺序表的尾插
SeqList.c
void slpushback(sl* ps, sldatatype x)
{assert(ps);slcheckcapacity(ps);ps->arr[ps->size++] = x;
}
- 插入后size++即可了
动态顺序表的头插
SeqList.c
void slpushfront(sl* ps, sldatatype x)
{assert(ps);slcheckcapacity(ps);for(int i=ps->size;i>0;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}
-
先让每个数据往后一位,注意一定要从后往前挪,否则数据会被覆盖
-
记得size++
动态顺序表的在指定位置插入数据
SeqList.c
void slinsert(sl* ps, sldatatype x, int pos)
{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以及之后数据的向后移动,还是从后往前挪动
- size++
2.3.3动态顺序表的删除
动态顺序表的尾删
删除数据的时候一定要判断顺序表是否为空,即size不能为0!!!
SeqList.c
void slpopback(sl* ps)
{assert(ps && ps->size);ps->size--;//ps->arr[ps->size] = 0;多余了,没有必要
}
- 只要让size–即可,不影响后来的插入(数据会被覆盖)
动态顺序表的头删
SeqList.c
void slpopfront(sl* ps)
{assert(ps && ps->size);for (int i = 0; i <ps->size-1 ; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
- 让每一位向前移动一位,从前往后挪,防止数据覆盖
- 记得size–
动态顺序表的在指定位置删除数据
SeqList.c
void slfrase(sl* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//包含了顺序表不为空的限定条件for (int i = pos; i <ps->size-1 ; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
- 类似头删,让pos以及之后的数据向前一位,从前往后挪
- size–
2.3.4动态顺序表查找指定数据
SeqList.c
int slfind(sl* ps, sldatatype x)
{assert(ps);int i = 0;int flag = 0;for (i = 0; i < ps->size; i++){if(ps->arr[i]==x){flag = 1;break;}}if (flag)return 1;else{return -1;}
}
- 遍历就完事了,相信各位已经熟练掌握了(❁´◡`❁)
- 如果找到返回1,没找到就返回-1(使用bool类型也是可以滴)
SeqList.c(完整版)
#include "Seqlist.h"
void slinit(sl* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}void sldestroy(sl*ps)
{assert(ps);if (ps->arr){free(ps->arr);ps->arr = NULL;}ps->capacity = ps->size = 0;
}void slprint(sl* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}
}void slcheckcapacity(sl* ps)
{assert(ps);if (ps->capacity == ps->size){//增容//若capacity为0,给个默认值,否者乘以2int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;sldatatype* tmp = (sldatatype*)realloc(ps->arr, newcapacity * sizeof(sldatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}}void slpushback(sl* ps, sldatatype x)
{assert(ps);slcheckcapacity(ps);ps->arr[ps->size++] = x;
}void slpushfront(sl* ps, sldatatype x)
{assert(ps);slcheckcapacity(ps);for(int i=ps->size;i>0;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}void slpopback(sl* ps)
{assert(ps && ps->size);ps->size--;//ps->arr[ps->size] = 0;多余了,没有必要
}void slpopfront(sl* ps)
{assert(ps && ps->size);for (int i = 0; i <ps->size-1 ; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}void slinsert(sl* ps, sldatatype x, int pos)
{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 slfrase(sl* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//还有更多的限制如顺序表不能为空for (int i = pos; i <ps->size-1 ; i++){ps->arr[i] = ps->arr[i + 1];}}int slfind(sl* ps, sldatatype x)
{assert(ps);int i = 0;int flag = 0;for (i = 0; i < ps->size; i++){if(ps->arr[i]==x){flag = 1;break;}}if (flag)return 1;else{return -1;}
}
以上就是顺序表的实现方法啦,各位大佬有什么问题欢饮在评论区指正,您的支持是我创作的最大动力!❤️
相关文章:

【初阶数据结构篇】顺序表的实现(赋源码)
文章目录 本篇代码位置顺序表和链表1.线性表2.顺序表2.1 概念与结构2.2分类2.2.1 静态顺序表2.2.2 动态顺序表 2.3 动态顺序表的实现2.3.1动态顺序表的初始化和销毁及打印2.3.2动态顺序表的插入动态顺序表的尾插动态顺序表的头插动态顺序表的在指定位置插入数据 2.3.3动态顺序表…...

移动式气象站:便携科技的天气守望者
在科技日新月异的今天,我们身边的许多设备都在向着更加智能化、便携化的方向发展。而在气象观测领域,移动式气象站的出现,不仅改变了传统气象观测的固有模式,更以其灵活性和实时性,在气象监测、灾害预警等领域发挥着越…...

软件测试必备 - 14个接口与自动化测试练习网站
随着互联网和移动应用的快速发展,接口和自动化测试的重要性日益凸显。越来越多的企业开始重视API测试,因为它不仅能提升开发效率,还能确保系统的稳定性和安全性。这些练习网站为测试人员提供了宝贵的资源,帮助他们掌握必要的技能,应对日益复杂的测试需求。 在软件测试的世…...

基于 HTML+ECharts 实现的数据可视化大屏案例(含源码)
数据可视化大屏案例:基于 HTML 和 ECharts 的实现 数据可视化已成为企业决策和业务分析的重要工具。通过直观、动态的图表展示,数据可视化大屏能够帮助用户快速理解复杂的数据关系,发现潜在的业务趋势。本文将介绍如何利用 HTML 和 ECharts 实…...

vardaccico前端私有库
vardacico docker pull verdaccio/verdaccio:4 docker run -it --rm --name verdaccio -p 4873:4873 verdaccio/verdaccio Docker | Verdaccio 拷贝docker中的配置到宿主机 进入docker内部 docker exec -it verdaccio /bin/sh 进入到指定目录 cd /verdaccio 开始拷贝到指定目…...

先用先发!小样本故障诊断新思路!Transformer-SVM组合模型多特征分类预测/故障诊断(Matlab)
先用先发!小样本故障诊断新思路!Transformer-SVM组合模型多特征分类预测/故障诊断(Matlab) 目录 先用先发!小样本故障诊断新思路!Transformer-SVM组合模型多特征分类预测/故障诊断(Matlab&#…...

学习大数据DAY26 简单数据清洗练习和 Shell 脚本中的数据库编程
目录 上机练习 14 mysql 命令 sql 语句实现步骤 shell 脚本导入 csv 格式文件到 mysql 数据库 secure-file-priv 特性 把文件拷贝到 mysql 指定目录下 上机练习 15 mysqldump 命令 上机练习 16 上机练习 14 运用上一节课学的 Shell 工具完成 1. 清洗数据《infotest.t…...

开发业务(3)——swoole和聊天室入门开发
在普通的PHP代码里面,我们不需要考虑性能和异步问题,包括不限于我们想要使用php搭建一个http服务器(在node/python/go里面都有http模块,但是PHP没有这种功能)。而同样的原因,很难实现php游戏的开发…...

Linux系统服务——【web,http协议,apache服务和nginx服务】(sixteen day)
一、web基础以及http协议 1、web基本概念和常识 前端开发一般用uniapp. 1、Web:为用户提供的一种在互联网上浏览信息的服务,Web 服务是动态的、可交互的、跨平台的和图形化的。 2、Web 服务为用户提供各种互联网服务,这些服务包括信息浏览服务…...
100、Python 关于时间日期的一些操作
在Python中,我们用于处理时间和日期相关的类型最常用的模块是datetime模块。该模块提供了很多与时间日期相关的类,对我们处理时间日期变得很方便。 以下是一些常见的关于时间日期的操作。 一、datetime类 1、获取当前日期和时间(年、月、日…...

【精通Redis】Redis命令详解
引言 Redis是一个内存数据库,在学习它的内部原理与实现之前,我们首先要做到的就是学会使用,学会其丰富的命令操作。 一、字符串 Redis的字符串类型之前笔者的一篇入门介绍中曾经说过,不是简单的只存人可以阅读的字符串…...

项目经理的开源工具指南:优化您的选择过程
国内外主流的10款开源项目管理系统对比:PingCode、Worktile、禅道、Teambition、Gogs、码云 Gitee、Jira、Redmine、ProjectLibre、OpenProject。 在选择合适的开源项目管理系统时,很多团队面临诸多挑战:功能是否全面?易用性如何&…...
如何防御IP劫持
摘要 IP劫持是一种网络攻击方式,攻击者通过各种手段获取对某个IP地址的控制权,并将其用于恶意目的。这种攻击可能会导致数据泄露、服务中断等严重后果。本文将介绍IP劫持的基本概念、攻击方式以及防御策略,并提供一些实际的代码示例。 IP劫…...
C++绝对值
在C中,你可以使用标准库中的abs函数来获取一个整数的绝对值。对于浮点数,也有一个类似的函数叫做fabs。下面是如何使用这些函数的示例: 对于整数 对于整数,你可以使用std::abs函数,它存在于<cstdlib>头文件中。…...

C# dataGridView 去掉左边多出来空列
1.问题 在使用winform做界面程序时,dataGridView控件创建好后,左侧会多出一列为空,如何删除呢 2.解决方法 你可以在属性窗口中进行设置 如图: 将RowHeadersVisible 属性设置为False 或者代码设置 this.dataGridView1.RowHea…...
esp32
买了单片机模块,学8266...

IDEA 本地有jar包依赖文件,但是所有引用的jar包全部爆红
前端时间 看源码,下载源码额按钮不见了,折腾了很久,遂打算重新安装idea,但是重新安装后,发现代码全都爆红,按照晚上说的删除idea 文件夹,idea缓存删除,都不好使,但是看到…...

如何在调整节拍时间的过程中保持生产流程的稳定性?
在快节奏的工业生产领域,节拍时间(Takt Time)——即完成一个完整产品所需的标准时间,是维持生产效率和流程稳定性的关键指标。然而,市场需求的波动、技术升级或是生产线的微调,都可能要求我们对节拍时间进行…...
3. Docker的数据管理与持久化
在Docker容器化应用中,数据的持久化和管理是一个关键问题。容器的生命周期短暂,容器的停止和删除会导致数据丢失。因此,了解Docker的数据卷(Volumes)和挂载(Mounts)的管理方式,对保障…...
Logback原理及应用详解(九)
本系列文章简介: 在软件开发的过程中,日志记录是一项至关重要的功能。它不仅帮助开发者在开发阶段追踪代码的执行流程和调试问题,还在生产环境中扮演着监控应用运行状态、记录关键业务信息和排查故障的重要角色。随着软件系统的日益复杂和分布…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...

Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...