手搓顺序表(C语言)

news/2024/7/20 18:15:10/文章来源:https://blog.csdn.net/m0_62646213/article/details/138135525

目录

SeqList.h 

SeqList.c 

 头插尾插复用任意位置插入

头删尾删复用任意位置删除

SLtest.c 

测试示例

 顺序表优劣分析


SeqList.h 

//SeqList.h#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define IN_CY 3typedef int SLdataType;typedef struct SeqList
{SLdataType* a;int size;int capacity;
}SeqList;//初始化函数
void SeqListInit(SeqList* ps);
//销毁函数
void SeqListDestory(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLdataType x);
//尾删
void SeqListPopBack(SeqList* ps);
//打印函数
void print(SeqList* ps);
//头插
void SeqListPushFront(SeqList* ps, SLdataType x);
//头删
void SeqListPopFront(SeqList* ps);// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLdataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

SeqList.c 

//SeqList.C#include "SeqList.h"//初始化顺序表
void SeqListInit(SeqList* ps)
{assert(ps);ps->size = 0;ps->capacity = 3;ps->a = (SLdataType*)malloc(sizeof(SLdataType) * ps->capacity);//申请空间失败if (ps->a == NULL){perror("SeqListInit");exit(-1);}
}//销毁顺序表
void SeqListDestory(SeqList* ps)
{assert(ps);ps->size = 0;ps->capacity = 0;free(ps->a);ps->a = NULL;
}//容量检查
void SLCheckCapacity(SeqList* ps)
{assert(ps);if (ps->size == ps->capacity){ps->capacity += IN_CY;SLdataType* tmp = (SLdataType*)realloc(ps->a, sizeof(SLdataType) * ps->capacity);//申请空间失败if (tmp == NULL){perror("SLCheckCapacity");exit(-1);}ps->a = tmp;}
}//尾插
void SeqListPushBack(SeqList* ps, SLdataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}//尾删
void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps->size);ps->size--;
}//打印顺序表
void print(SeqList* ps)
{assert(ps);int i;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}//头插
void SeqListPushFront(SeqList* ps, SLdataType x)
{assert(ps);SLCheckCapacity(ps);int end = ps->size;while (end--){ps->a[end + 1] = ps->a[end];}ps->size++;ps->a[0] = x;
}//头删
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps->size);int i;for (i = 0; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLdataType x)
{assert(ps);//下标合法检查assert(pos>= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->size++;ps->a[pos] = x;
}// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);//下标合法检查assert(pos >= 0 && pos < ps->size);int i;for (i = pos; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

 头插尾插复用任意位置插入

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLdataType x)
{assert(ps);//下标合法检查assert(pos>= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->size++;ps->a[pos] = x;
}//头插
void SeqListPushFront(SeqList* ps, SLdataType x)
{SeqListInsert(ps, 0, x);
}//尾插
void SeqListPushBack(SeqList* ps, SLdataType x)
{SeqListInsert(ps, ps->size, x);
}

头删尾删复用任意位置删除

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);//下标合法检查assert(pos >= 0 && pos < ps->size);int i;for (i = pos; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}//头删
void SeqListPopFront(SeqList* ps)
{SeqListErase(ps, 0);
}//尾删
void SeqListPopBack(SeqList* ps)
{SeqListErase(ps, ps->size - 1);
}

SLtest.c 

//SLtest.c#include "SeqList.h"void SLtest1()
{SeqList s1;SeqListInit(&s1);SeqListPushBack(&s1, 1);SeqListPushBack(&s1, 2);SeqListPushBack(&s1, 3);print(&s1);SeqListPushBack(&s1, 4);SeqListPushBack(&s1, 5);print(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);print(&s1);SeqListDestory(&s1);
}void SLtest2()
{SeqList s1;SeqListInit(&s1);SeqListPushFront(&s1, 1);SeqListPushFront(&s1, 2);SeqListPushFront(&s1, 3);print(&s1);SeqListPushFront(&s1, 4);SeqListPushFront(&s1, 5);print(&s1);//SeqListPopFront(&s1);//SeqListPopFront(&s1);SeqListPopFront(&s1);print(&s1);SeqListPopFront(&s1);print(&s1);SeqListPopFront(&s1);print(&s1);SeqListPopFront(&s1);print(&s1);SeqListDestory(&s1);
}void SLtest3()
{SeqList s1;SeqListInit(&s1);SeqListInsert(&s1, 0, 1);SeqListInsert(&s1, 0, 2);SeqListInsert(&s1, 0, 3);print(&s1);SeqListInsert(&s1, s1.size, 4);SeqListInsert(&s1, s1.size, 5);SeqListInsert(&s1, s1.size, 6);print(&s1);SeqListInsert(&s1, 1, 7);print(&s1);SeqListErase(&s1, s1.size - 1);print(&s1);}
int main()
{//测试尾插尾删//SLtest1();//测试头插头删//SLtest2();//测试任意位置插入删除SLtest3();return 0;
}

测试示例

尾插:

尾删:

头插:

头删:

任意位置插入:

任意位置删除:

 顺序表优劣分析

        由于顺序表是一块连续的空间,因此可以直接通过下标访问而无需遍历寻找,所以在需要大量访问的程序中具有优势,对缓存的利用率高。而当空间不够扩容时一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。且对于异地扩容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。

        尾插和尾删的时间复杂度为O(1),因此适用于只需要尾插尾删的场景。而头插头删和任意位置插入删除为了保证数据的顺序性需要一个一个挪动数据,时间复杂度为0(n),因此对于需要大量随机存取的程序来说开销较大。

        因此顺序表通常应用于元素高效存储+频繁访问的场景。

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

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

相关文章

系统管理、磁盘分区

系统管理 业务层面&#xff1a;为了满足一定的需求所做的特定操作。 硬盘是什么&#xff0c;硬盘的作用&#xff1a; **硬盘&#xff1a;**计算机的存储设备&#xff0c;机械硬盘是由一个或者多个磁性的盘组成&#xff0c;可以在盘片上进行数据的读写。 连接方式&#xff1a…

开源VS闭源:谁将引领AI大模型的新时代?

一、引言 随着人工智能技术的飞速发展&#xff0c;AI大模型已成为推动这一浪潮的核心动力。在AI大模型的发展过程中&#xff0c;开源与闭源两种不同的发展路径一直备受关注。本文将深入探讨这两种路径的优劣势&#xff0c;分析它们对AI大模型发展的影响&#xff0c;并预测谁将…

深入了解 CSS 预处理器 Sass

今天我们来深入探讨一下 CSS 预处理器 Sass。我们将学习什么是 Sass,如何使用它,以及它是如何工作的。 什么是 Sass? Sass 是 syntactically awesome style sheets 的缩写,是一种 CSS 预处理器。它是 CSS 的扩展,为基础 CSS 增加了更多的功能和优雅。普通的 CSS 代码很容…

从git上拉取项目进行操作

1.Git的概念 Git是一个开源的分布式版本控制系统&#xff0c;可以有效、高速的处理从很小到非常大的项目版本管理。它实现多人协作的机制是利用clone命令将项目从远程库拉取到本地库&#xff0c;做完相应的操作后再利用push命令从本地库将项目提交至远程库。 2.Git的工作流程…

惯性测量单元M-G370系列广泛用于工业系统各个领域

爱普生现已推出型号为M-G370系列的高稳定性、高精度及极小尺寸封装的惯性测量单元(IMU)&#xff0c;可广泛应用于工业系统的各个领域。 为了节省PCB的面积和产品空间&#xff0c;M-G370系列性测量单元设计精巧&#xff0c;且具有6个自由度:三轴角速率和三轴线性加速度&…

七大获取免费https证书的方式

想要实现https访问最简单有效的的方法就是安装SSL证书。只要证书正常安装上以后&#xff0c;浏览器就不会出现网站不安全提示或者访问被拦截的情况。下面我来教大家怎么去获取免费的SSL证书&#xff0c;又如何安装证书实现https访问。 一、选择免费SSL证书提供商 有多家机构提…

揭秘:如何使用Python统计女友生日还剩几天?

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、引言&#xff1a;为何需要统计生日天数&#xff1f; 二、需求分析与准备 1. 用户输入格…

失落的方舟台服账号怎么注册 失落的方舟台服注册收不到验证码

《失落的方舟》&#xff08;Lost Ark&#xff09;是由韩国Smilegate公司研发的一款大型多人在线角色扮演游戏&#xff08;MMORPG&#xff09;。该游戏以其精美的画面、丰富的剧情、动作类游戏的战斗手感以及广阔的开放世界而著称&#xff0c;自发布以来便吸引了全球众多游戏玩家…

黑马python-面向对象程序设计

1.定义类 class 类名&#xff1a; 代码 ….. 注意&#xff1a;类名要满足标识符命名规则&#xff0c;同时遵循大驼峰命名习惯 2.self&#xff1a; self指调用该函数的对象 3.创建对象 对象名类&#xff08;&#xff09; 4.添加获取对象属性 对象名.属性名值 5._init_()方法&…

享受当下,还是留待未来?一项fMRI与眼动追踪技术的联合研究

摘要 时间贴现(temporal discount)是指个体对奖励的估计会随着时间流逝而下降的心理现象。具体而言&#xff0c;当获得奖励的时间以日期(日期条件&#xff1b;例如&#xff0c;2023年6月8日)而不是延迟(延迟条件&#xff1b;例如&#xff0c;30天)呈现时&#xff0c;贴现率较低…

等了10年,终于迎来RTX5/RTX4全家桶开源,开源,开源! 且免费商用

我们的V4, V5, V6 ,V7开发板都配套了大量的RTX4, RTX5教程和案例&#xff0c;从2015年发布首版RTX4内核教程以来&#xff0c;已经整整10年了。 1、制作这个RTX教程和案例&#xff0c;其实也承受了很大的压力&#xff0c;因为只有RTX内核是免费商用的&#xff0c;中间件并不免费…

水电表远程抄表:智能化时代的能源管理新方式

1.行业背景与界定 水电表远程抄表&#xff0c;是随着物联网技术发展&#xff0c;完成的一种新型的能源计量管理方式。主要是通过无线传输技术&#xff0c;如GPRS、NB-IoT、LoRa等&#xff0c;将水电表的信息实时传输到云服务器&#xff0c;进而取代了传统人工当场抄水表。这种…

第十二课,for循环

一&#xff0c;for循环对字符串&#xff08;序列&#xff09;的基础语法 语法&#xff1a;for i in “hello world”: *小练习&#xff1a;统计字符串中有一个字符&#xff1f;特定的字符有几个&#xff1f; 二&#xff0c;for循环的range语句 ①从a开始到b结束&#xff0c;每…

医学中脑机接口技术的未来

医学中脑机接口技术的未来 李升伟 编译 对非侵入性脑机接口&#xff08;而不是植入物&#xff09;日益增长的兴趣可能会提高患者的易使用性&#xff0c;但分辨率需要提高。 图片来源&#xff1a;Denis Pobytov / DigitalVision Vectors / Getty 全球范围内正在展开一场争夺利用…

AutoDL搭建 ChatGLM3

租用新实例 这里选择的西北 B 区、RTX 409024GB 创建虚拟环境并激活 # 安装虚拟环境至数据盘 conda create --prefix /root/autodl-tmp/envs/chatglm3-demo python3.10# 激活虚拟环境 conda activate /root/autodl-tmp/envs/chatglm3-demo拉取ChatGLM3仓库代码 # 开启学术…

wordpress主题 ACG美化插件v3.4.2支持zibll主题7b2主题美化

独具一格的二次元风格&#xff0c;打造全新的子比美化方向 大部分代码均为CSS、JS做成插件只是为了方便懒人小白站长 后台全功能一览&#xff0c;大部分美化均为网上通用流传&#xff0c;

DreamerV3阅读笔记

DreamerV3 文章希望解决的一个挑战是用固定的hyperparameter来同时处理不同domain的任务。文章发现&#xff0c;通过结合KL balancing 和free bits可以使得world model learn without tuning&#xff08;是指上面这件事&#xff0c;即不需要对不同任务改变hyperparameter&#…

Java学习17

目录 一.System类&#xff1a; 1.System类常见方法 二.BigInteger和BigDecima类&#xff1a; 三.日期类&#xff1a; 1.Date&#xff1a;精确到毫秒&#xff0c;代表特定的瞬间。 2.Calendar: (1)简介&#xff1a; 3.第三代日期类&#xff1a; 1.第三代日期类的常用方…

Java入门基础学习笔记44——String

为什么要学习String的处理呢&#xff1f; 开发中&#xff0c;对字符串的处理是非常常见的。 String是什么&#xff1f;可以做什么&#xff1f; java.lang.String 代表字符串。可以用来创建对象封装字符串数据&#xff0c;并对其进行处理。 1、创建对象 2、封装字符串数据 3…

Linux x86_64 UEFI 启动

文章目录 前言一、UEFI二、Disk device compatibility2.1 GPT 磁盘分区表2.1.1 简介2.1.2 Linux 2.2 ESP&#xff08;EFI&#xff09; 文件系统2.2.1 简介2.2.2 LinuxLinux Kernel EFI Boot Stub 三、UEFI GPT grub23.1 简介3.2 引导方式 3.3 BOOTX64.EFI3.4 shimx64.efi3.5 …