顺序表各种接口的实现(C)

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

概念

  • 用一段物理地址连续的存储单元
  • 依次存储数据元素的线性结构,一般情况下采用数组存储。
  • 在数组上完成数据的增删查改
    一般可以分为
  1. 静态顺序表:使用定长数组存储元素
#define N 1000
typedef int SLDataType;typedef struct SeqList    //对类型进行重命名,方便后续变换类型
{SLDataType array[N];  //定长数组size_t size;          //有效数据个数
}SL;
  1. 动态顺序表:使用动态开辟的数组存储
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;typedef struct SeqList
{SLDataType* array;  //指向动态开辟的数组size_t size;        //有效数据个数size_t capacity;    //容量空间的大小
}SL;

![[Pasted image 20240810054754.png]]

初始化
  • 每次调用接口,要判断传入的指针是不是空指针
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);if (ps->a == NULL){perror("malloc failed");exit(-1);         //程序直接在这里结束}ps->size = 0;ps->capacity = 0;
}
  • 动态内存,用malloc开辟空间,先开4个
  • 检查malloc出的地址是否为空指针
  • 将size和capacity初始化为0
销毁
void SLDestroy(SL* ps)
{assert(ps);free(ps-> a);ps->a = NULL;ps->capacity = ps->size = 0;
}
  • 直接释放掉malloc的空间,将a指针置为NULL
  • 将size和capacity置为0
打印
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps-> size; i++){printf("%d ", ps->a[i]);}printf("\n");
}
  • 从下标0开始往右遍历,直到最后一个元素,即size-1
扩容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}
}
  • 当size等于capacity时,realloc,重新开辟空间,一般扩2倍容量
尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->size] = x;ps->size++;
}
  • 在下标size处插入值,size++,如果size等于capacity,就扩容
尾删
void SLPopBack(SL* ps)
{assert(ps);//if (ps->size == 0)//	return;assert(ps->size > 0);ps->size--;
}
  • 直接size–,覆盖掉尾部的元素
  • 断言size,size不能减为负数
头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}

需要整体元素往右挪动
而且只能从右往左开始遍历,反过来会覆盖没有处理的元素

end从size-1开始
![[Pasted image 20240810060526.png]]

把当前元素往右移动一格,传给end+1
![[Pasted image 20240810061642.png]]

end–,往前一格
![[Pasted image 20240810060703.png]]

直到end=0
![[Pasted image 20240810060808.png]]

把x传进来,size++
![[Pasted image 20240810060931.png]]

当size=capacity时,就需要扩容

头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}

从左往右,挨个往左移动
begin从下标1开始
![[Pasted image 20240810061444.png]]

把begin的内容覆盖给begin-1
![[Pasted image 20240810062211.png]]

begin++
![[Pasted image 20240810061551.png]]

直到begin=size-1
![[Pasted image 20240810062002.png]]

size–
![[Pasted image 20240810062046.png]]

查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}
  • 依次遍历每个元素,找到以后,返回下标,否则返回-1
插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}
  • 先判断pos是否合法,pos可以等于size,因为可以尾插
    end从size-1开始
    ![[Pasted image 20240810064522.png]]

当end大于等于pos时,end开始循环
将end传给end+1
![[Pasted image 20240810064811.png]]

end–,往左移动
![[Pasted image 20240810064743.png]]

直到end=pos
![[Pasted image 20240810064858.png]]

将x传给pos,size++
![[Pasted image 20240810064941.png]]

当pos直接等于size时,相当于尾插
等于0时,相当于头插

删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}
  • 同样判断pos是否合法
    begin从pos+1开始
    ![[Pasted image 20240810065127.png]]

将begin传给begin-1
![[Pasted image 20240810065200.png]]

begin++
![[Pasted image 20240810065219.png]]

直到begin=size-1
![[Pasted image 20240810065252.png]]

size–
![[Pasted image 20240810065322.png]]

当pos等于size-1时,相当于尾删
等于0时,相等于头删

修改
void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}
  • 判断pos的合法性,直接通过数组下标修改

声明定义分离实现

//管理数据 -- 增删查改
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//查找
int SLFind(SL* ps, SLDataType x);
//插入
void SLInsert(SL* ps, int pos, SLDataType x);
//删除
void SLErase(SL* ps, int pos);
//修改
void SLModify(SL* ps, int pos, SLDataType x);
#include "SeqList.h"void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);if (ps->a == NULL){perror("malloc failed");exit(-1);         //程序直接在这里结束}ps->size = 0;ps->capacity = 0;
}void SLDestroy(SL* ps)
{assert(ps);free(ps-> a);ps->a = NULL;ps->capacity = ps->size = 0;
}void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps-> size; i++){printf("%d ", ps->a[i]);}printf("\n");
}void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}
}void SLPushBack(SL* ps, SLDataType x)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->size] = x;ps->size++;
}void SLPopBack(SL* ps)
{assert(ps);//if (ps->size == 0)//	return;assert(ps->size > 0);ps->size--;
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}

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

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

相关文章

旋转字符串 | LeetCode-796 | 模拟 | KMP | 字符串匹配

&#x1f64b;大家好&#xff01;我是毛毛张! &#x1f308;个人首页&#xff1a; 神马都会亿点点的毛毛张 &#x1f579;️KMP算法练习题 LeetCode链接&#xff1a;796. 旋转字符串 文章目录 1.题目描述&#x1f351;2.题解&#x1fad0;2.1 暴力解法&#x1fad2;2.2 模拟…

c# 排序、强转枚举

List<Tuple<double,int>> mm中doble从小到大排序 mm本身排序 在C#中&#xff0c;如果你有一个List<Tuple<double, int>>类型的集合mm&#xff0c;并且你想要根据Tuple中的double值&#xff08;即第一个元素&#xff09;从小到大进行排序&#xff0c;同…

[Qt][对话框][下]详细讲解

目录 1.Qt内置对话框0.有哪些1.消息对话框 QMessageBox2.颜色对话框 QColorDialog3.⽂件对话框 QFileDialog4.字体对话框 QFontDialog5.输⼊对话框 QInputDialog6.进度条对话框 QProgressDialog 1.Qt内置对话框 0.有哪些 Qt提供了多种可复⽤的对话框类型&#xff0c;即Qt标准…

【启明智显技术分享】工业级HMI芯片Model3C/Model3A开发过程中问题记录笔记二

一、Model3C/Model3A芯片介绍 Model3C/Model3A是启明智显针对工业、行业以及车载产品市场推出的一款高性能、低成本的工业级HMI&#xff08;Human-Machine Interface&#xff0c;人机界面&#xff09;芯片。两颗芯片硬件PIN TO PIN&#xff1b;区别在于内置的PSRAM大小不同。该…

百度地图动态绘制台风轨迹

效果图如下: 台风测试数据获取 关键代码: /*** 动态绘制点和线*/drawMakerByAnimate () {const pointsMap = typhoneData.points;const title = typhoneData.tfid + typhoneData.name;if (!pointsMap || pointsMap.length === 0) {return;}if (this.markers.length > 0 &…

Godot《躲避小兵》实战之设置项目

通过之前的学习我们已经基本了解了godot的界面&#xff0c;知道如何创建项目以及节点。那么&#xff0c;从这一章节我们将进入godot官方给我们提供的一个2D游戏开发的小教程进行入手&#xff0c;这个游戏并不是我自己的作品&#xff0c;而是我通过学习完之后&#xff0c;对其进…

C#如何将自己封装的nuget包引入到项目中

问题 自己封装好了一个nuget包&#xff0c;但是不想上传到外网&#xff0c;想局域网使用&#xff0c;有两种方案 搭建私有nuget仓库放到离线文件夹中直接使用 第一种方式请请参考proget安装 下面主要是第二种方式 准备 新建类库项目 using System;namespace ClassLibrary…

数据结构--图(Graph)

定义 图&#xff08;Graph&#xff09;是由顶点的有穷非空集合和顶点之间边的集合组成的一种非线性表结构&#xff0c;通常表示为&#xff1a;G(V,E)&#xff0c;其中&#xff0c;G表示一个图&#xff0c;V是图G中顶点的集合&#xff0c;E是图G中边的集合。 顶点&#xff08;…

阿里云智能大数据演进

本文根据7月24日飞天发布时刻产品发布会、7月5日DataFunCon2024北京站&#xff1a;大数据大模型.双核时代实录整理而成&#xff0c;演讲信息如下&#xff1a; 演讲人&#xff1a;徐晟 阿里云研究员/计算平台产品负责人 主要内容&#xff1a; Overview - 阿里云大数据 AI 产品…

经典算法题总结:数组常用技巧(双指针,二分查找和位运算)篇

双指针 在处理数组和链表相关问题时&#xff0c;双指针技巧是经常用到的&#xff0c;双指针技巧主要分为两类&#xff1a;左右指针和快慢指针。所谓左右指针&#xff0c;就是两个指针相向而行或者相背而行&#xff1b;而所谓快慢指针&#xff0c;就是两个指针同向而行&#xf…

【YOLO5 项目实战】(3)PCB 缺陷检测

欢迎关注『youcans动手学模型』系列 本专栏内容和资源同步到 GitHub/youcans 【YOLO5 项目实战】(1)YOLO5 环境配置与测试 【YOLO5 项目实战】(2)使用自己的数据集训练目标检测模型 【YOLO5 项目实战】(3)PCB 缺陷检测 【YOLO5 项目实战】(3)PCB 缺陷检测 1. PCB 缺陷检…

vue-cli 中 配置 productionSourceMap 为 false 失效?

背景 最近 发现 vuecli 构建的 项目中配置的 productionSourceMap 为 false 后 &#xff0c;生产代码 还是能够看到 sourceMap 文件 。 原因 生效前提条件 得设置 NODE_ENV 为 production 才会生效&#xff01; 解决 直接修改生产环境的配置 NODE_ENV 为 production 直接覆…

融资3亿美元——月之暗面:AI大模型领域的新星

月之暗面&#xff0c;这个名字在AI领域引起了不小的震动。作为国内大模型创业企业的佼佼者&#xff0c;月之暗面以其独特的技术优势和商业模式&#xff0c;迅速在激烈的市场竞争中崭露头角。同时以其出色的长文本处理能力和创新的商业模式吸引了众多投资者的目光。 优牛企讯-企…

基于DETR模型实现交通标志检测

交通标志检测在自动驾驶和交通监控中是一个重要的问题。目标检测技术极大地促进了这一过程的自动化。本文实现基于DETR目标检测模型识别交通标志。 Tiny LISA交通标志检测数据集 本文数据集使用Kaggle上提供的Tiny LISA交通标志检测数据集(https://www.kaggle.com/datasets/mm…

手把手教你CNVD漏洞挖掘 + 资产收集

0x1 前言 挖掘CNVD漏洞有时候其实比一般的edusrc还好挖&#xff0c;但是一般要挖证书的话&#xff0c;还是需要花时间的&#xff0c;其中信息收集&#xff0c;公司资产确定等操作需要花费一定时间的。下面就记录下我之前跟一个师傅学习的一个垂直越权成功的CNVD漏洞通杀&#…

MySql 5.7.1 分区的实践

在性能优化中&#xff0c;Mysql 进行分区&#xff0c;能有效提高查询效率&#xff0c;因此开始百度了起来。但是结果总不是那么一番风顺的。如今使用 uuid 作为主键的情况已是主流&#xff0c;因此在给表增加分区时&#xff0c;出现了如下错误&#xff1a; 错误&#xff1a; A …

AI在医学领域:联邦学习 (FL) 在肿瘤学的应用综述

关键词&#xff1a;联邦学习 (Federated Learning, FL)、机器学习 (Machine Learning, ML)、肿瘤学 (Oncology)、数据隐私 (Data Privacy)、精准医疗 (Precision Medicine)、多模态 (Multi-modal) 肿瘤学正在经历快速的变革&#xff0c;这得益于机器学习&#xff08;ML&#xf…

奥德彪视频素材去哪里找?视频素材网站分享

今天我们来聊一聊一个非常实用的话题——视频素材网站推荐&#xff0c;尤其是奥德彪视频素材。这个名词可能对你来说有些陌生&#xff0c;但别担心&#xff0c;跟着我一起探索&#xff0c;你会发现这是一个充满创意与乐趣的旅程。 蛙学网 首先要介绍的是蛙学网。这是一个视频素…

【传知代码】医疗AI:轻量级图像分割新突破(论文复现)

在医学图像领域&#xff0c;精准的图像分割技术一直是提高诊断效率和准确性的关键&#xff0c;然而传统的图像分割方法常常受到计算资源和处理速度的限制&#xff0c;尤其在资源紧张的医疗环境中更是如此。随着人工智能技术的飞速发展&#xff0c;我们迎来了一个激动人心的新时…

PAT--1101.B是A的多少倍

题目描述 算法分析 把数字转为字符串处理&#xff0c;会简化问题 完整代码 #include<bits/stdc.h> //万能头文件 //#include<iostream> //#include<string> //#include <iomanip> // 包含 std::fixed 和 std::setprecision using namespace std;…