C语言实现顺序表--数据结构

news/2024/5/19 22:27:25/

在这里插入图片描述

  • 魔王的介绍:😶‍🌫️一名双非本科大一小白。
  • 魔王的目标:🤯努力赶上周围卷王的脚步。
  • 魔王的主页:🔥🔥🔥大魔王.🔥🔥🔥
    请添加图片描述
    ❤️‍🔥大魔王与你分享:“提亚马特都有失去主动的一天,更何况是满身破绽的你呢”。

文章目录

  • 一、前言
  • 二、顺序表实现
    • 1、创建结构体
    • 2、初始化
    • 3、销毁
    • 4、检查
    • 5、打印
    • 6、尾插
    • 7、尾删
    • 8、头插
    • 9、头删
    • 10、查找
    • 11、插入
    • 12、删除
    • 13、注意事项
  • 三、总代码
    • SeqList.h
    • SeqList.c
    • Test.c
  • 四、总结

一、前言

顺序表是线性表的一种,它就如同字面意思一般,在内存是按顺序存储的,如果你还不理解,那你想想你一直用的数组,它就是顺序表的原理,在内存中连续存放的,因此地址也是连续的。如图:在这里插入图片描述

二、顺序表实现

1、创建结构体

虽然顺序表只是单纯的一个数组,但是要知道,我们在使用顺序表时,需要增删查改这些操作,那么对于在内存中连续存贮的顺序表,我们怎样快速找到它呢,我们怎样确定这个顺序表有几个元素呢,那就需要定义一个变量来记录这个顺序表的元素。至于为什么让他们俩连起来弄在结构体里,那当然是因为这样可以避免传一堆参数,没弄好自己就蒙了,命名了一堆的变量名,所以我们让他们放在结构体里,方便一起操作。

当然,因为要实现的顺序表是动态的,也就是会自己扩容,避免空间不够或者空间浪费,所以我们在结构体里还需要弄一个新的变量,那就是记录当前顺序表的大小。当元素个数与顺序表的大小相等时,我们就需要扩容了。

代码:

#define InitCapacity 5typedef int SLDateType;typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SL;

2、初始化

创建完这个结构体,我们需要给结构体里的元素初始化,封装成一个函数,在给数组指针初始化时,我们给他一个初始大小,等以后不够再自动扩容。

代码:

void SLInit(SL* pc)
{assert(pc);pc->a = (SLDateType*)malloc(sizeof(SLDateType) * InitCapacity);pc->size = 0;pc->capacity = InitCapacity;
}

3、销毁

因为是动态开辟的,所以内存是再堆区的,当我们用完如果不销毁,那么只能等程序结束才会自动销毁,如果没结束不会自动释放,所以当我们用完后需要手动释放。

代码:

void SLDestroy(SL* pc)
{assert(pc);free(pc->a);pc->size = 0;pc->capacity = 0;pc->a = NULL;
}

4、检查

现在我们来实现刚才一直说的扩容,当顺序表容量满的时候,我们需要扩容,那么怎样检查又怎样扩容呢,请看下面代码实现。

代码:

void SLCheck(SL* pc)
{assert(pc);if (pc->capacity == pc->size){int* str = realloc(pc->a, pc->capacity * sizeof(SLDateType) * 2);if (str == NULL){perror("realloc fail");return;//返回之后的流程是什么:会打印出开辟失败的一行信息,但接下来的步骤还会进行,比如越界什么的,强行执行后面的操作。}else{pc->a = str;str = NULL;}pc->capacity = pc->capacity * 2;}
}

注意在扩容时,需要先用一个临时指针操作,否则如果开辟失败,返回一个空指针,空指针的值赋给了原本的指针,那么这个数组的地址就找不到了,那么损失就大了。所以当开辟成功时,再把这个临时指针的值赋给新指针,并把临时指针置空,防止野指针。

5、打印

为了验证等会下面的增删查改,我们先实现一个打印函数,然后等写好功能后来验证。

代码:

void SLPrint(SL* pc)
{assert(pc);for (int i = 0; i < pc->size; i++){printf("%d ", pc->a[i]);}
}

6、尾插

首先来实现一下尾插,在尾插时,第一步当然是判断顺序表是否满了,如果,满了我们还插入内容,那就越界访问了。这一步弄完,我们直接插入值就行了,插入到下标为元素个数的位置即可,因为数组下标是从0开始的。最后就是让我们结构体里统计个数的那个变量加一就行了。

代码:

void SLPushBack(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);pc->a[pc->size] = x;pc->size++;
}

7、尾删

尾删特别简单,先判断该顺序表是否有内容,如果有,那么直接让个数减一就ok了,其他不用管,因为打印是根据个数打印的。

代码:

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

8、头插

头插比较麻烦,说的麻烦是效率麻烦,因为需要逐个遍历,全部都向后移动一位,然后让size+1。实现并不难,因为顺序表整体都是简单的。

代码:

void SLPushFront(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);for (int end = pc->size - 1; end >= 0; end--){pc->a[end + 1] = pc->a[end];}pc->a[0] = x;pc->size++;
}

9、头删

头删和头插一样,都是需要逐个遍历,这个是都向前移动一位,然后让size-1。

代码:

void SLPopFront(SL* pc)
{assert(pc);assert(pc->size);for (int begin = 1; begin <= pc->size - 1; begin++){pc->a[begin - 1] = pc->a[begin];}pc->size--;
}

10、查找

查找也和简单,就是从第一个元素逐个遍历,然后返回找到的位置下标,如果没有找到,就返回-1。

代码:

int SLFind(SL* pc, SLDateType x)
{assert(pc);assert(pc->size);for (int i = 0; i < pc->size; i++){if (x == pc->a[i]){return i;}}return -1;
}

11、插入

实现了头插尾插, 那如果我们想从内部插入呢,其实原理是一样的,让某个地方之后的都向后移动一位,当然这之前需要判断是否满了。最后size+1。

代码:

void SLInsert(SL* pc, int pos, SLDateType x)
{assert(pc);int end = pc->size - 1;if (pos >= 0 && pos <= pc->size){SLCheck(pc);while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;}
}

12、删除

实现了头删和尾删,如果我们想从内部某个位置删除,就需要再写一个代码了,原理也是一样的,先判断有没有元素,然后让从这个位置之后的都向前进一。最后size-1。

代码:

void SLErase(SL* pc, int pos)
{assert(pc);assert(pc->size);//可有可无int begin = pos + 1;if (pos >= 0 && pos < pc->size){while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;}
}

13、注意事项

  • 我们在进行插入时,挪动元素位置需要先挪后边再挪前边,否则会覆盖原数组的值,移动后所对应的就不是原来的值了。
  • 相同的,在进行删除时,也需要考虑这方面,不过跟插入是相反的,我们需要先挪动前边的,不然会覆盖原数组的值,移动后就不是原来数组的值了。

三、总代码

SeqList.h

SeqList.h

#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>#define InitCapacity 5typedef int SLDateType;typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SL;//初始化
void SLInit(SL* pc);//结束,销毁
void SLDestroy(SL* pc);//检查是否需要扩容
void SLCheck(SL* pc);//打印
void SLPrint(SL* pc);//尾插
void SLPushBack(SL* pc, SLDateType x);//尾删
void SLPopBack(SL* pc);//头插
void SLPushFront(SL* pc, SLDateType x);//头删
void SLPopFront(SL* pc);//查找
int SLFind(SL* pc, SLDateType x);//插入(从0开始,也就是按照的是下标而不是个数)
void SLInsert(SL* pc, int pos, SLDateType x);//删除(从0开始,也就是按照的是下标而不是个数)
void SLErase(SL* pc, int pos);

SeqList.c

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void SLInit(SL* pc)
{assert(pc);pc->a = (SLDateType*)malloc(sizeof(SLDateType) * InitCapacity);pc->size = 0;pc->capacity = InitCapacity;
}void SLDestroy(SL* pc)
{assert(pc);free(pc->a);pc->size = 0;pc->capacity = 0;pc->a = NULL;
}void SLCheck(SL* pc)
{assert(pc);if (pc->capacity == pc->size){int* str = realloc(pc->a, pc->capacity * sizeof(SLDateType) * 2);if (str == NULL){perror("realloc fail");return;//返回之后的流程是什么:会打印出开辟失败的一行信息,但接下来的步骤还会进行,比如越界什么的,强行执行后面的操作。}else{pc->a = str;str = NULL;}pc->capacity = pc->capacity * 2;}
}void SLPrint(SL* pc)
{assert(pc);for (int i = 0; i < pc->size; i++){printf("%d ", pc->a[i]);}
}void SLPushBack(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);pc->a[pc->size] = x;pc->size++;
}void SLPopBack(SL* pc)
{assert(pc);assert(pc->size);pc->size--;
}void SLPushFront(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);for (int end = pc->size - 1; end >= 0; end--){pc->a[end + 1] = pc->a[end];}pc->a[0] = x;pc->size++;
}void SLPopFront(SL* pc)
{assert(pc);assert(pc->size);for (int begin = 1; begin <= pc->size - 1; begin++){pc->a[begin - 1] = pc->a[begin];}pc->size--;
}int SLFind(SL* pc, SLDateType x)
{assert(pc);assert(pc->size);for (int i = 0; i < pc->size; i++){if (x == pc->a[i]){return i;}}return -1;
}void SLInsert(SL* pc, int pos, SLDateType x)
{assert(pc);int end = pc->size - 1;if (pos >= 0 && pos <= pc->size){SLCheck(pc);while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;}
}void SLErase(SL* pc, int pos)
{assert(pc);assert(pc->size);//可有可无int begin = pos + 1;if (pos >= 0 && pos < pc->size){while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;}
}

Test.c

Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 0);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPopBack(&s);SLPushFront(&s, 9);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);int i = 0;i = SLFind(&s, 4);if (i != -1){printf("下标为%d\n", i);}SLPrint(&s);
}
void test2()
{SL s;SLInit(&s);SLPushFront(&s, 3);SLInsert(&s, 0, 0);SLInsert(&s, 0, 1);SLInsert(&s, 0, 5);SLInsert(&s, 0, 6);SLInsert(&s, 0, 7);SLInsert(&s, 2, 8);SLInsert(&s, 0, 9);SLErase(&s, 2);SLPrint(&s);
}void test3()
{SL s;SLInit(&s);SLPushFront(&s, 0);SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPushFront(&s, 5);SLPushFront(&s, 6);SLPrint(&s);
}
int main()
{//test1();//test2();test3();return 0;
}

四、总结

在这里插入图片描述

✨请点击下面进入主页关注大魔王
如果感觉对你有用的话,就点我进入主页关注我吧!


http://www.ppmy.cn/news/46956.html

相关文章

如何使用Tensorflow神经网络模型来完成兰州房价预测分析?

兰州房价预测是一个非常热门的话题,许多人都对如何预测兰州房价感兴趣。在本文中,我将介绍如何使用TensorFlow来预测兰州房价,并提供Python源代码。 首先,我们需要收集兰州的房价数据。我们可以从房地产网站或政府统计数据中获取。在本文中,我们将使用Kaggle上提供的兰州…

收音机知识,调谐(选频/滤波),调制(升频)

参考&#xff1a;https://www.bilibili.com/video/BV1d14y1N7nm/?spm_id_from333.999.0.0&vd_source00bd76f9d6dc090461cddd9f0deb2d51 有关知识提纲 整个信号的传输变化调谐人耳听到声音的频率范围&#xff08;20~20000Hz&#xff09;天线和传送信号的波长关系波长和天线…

RHCE第一次作业at和cront两个任务管理程序的区别

1.at 单一执行的例行性工作&#xff1a;仅处理执行一次就结束了 -m 当任务完成之后&#xff0c;即使没有标准输出&#xff0c;将给用户发送邮件 -l atq的别名&#xff0c;可列出目前系统上面的所有该用户的at调度 -d atrm的别名,可以取消一个在at调度中的工作 -v 使用较明显的…

pandas中df.groupby详解?

df.groupby 是 pandas 库用于实现按照某些列进行拆分&#xff0c;应用函数和组合的一个功能。步骤如下&#xff1a; 1. 按照指定的一列或多列进行分组 (grouping) 2. 对每个分组应用一个聚合函数 (aggregation) 3. 将每个分组的聚合结果合并成一个数据结构 语法&#xff1a; df…

Session详解(重点)

类似于去服务器注册账号&#xff0c;只要服务器不停机&#xff0c;自己注册的账号一直会存在服务器。 什么是Session&#xff1a; 1.服务器会给每一个用户&#xff08;浏览器&#xff09;创建一个对象&#xff1b; 2.一个Session独占一个浏览器&#xff0c;只要浏览器没有关…

***大论文中插入Visio不失真方法:word插入viso图片方法

***大论文中插入Visio不失真方法&#xff1a;word插入viso图片方法 1、可以直接导出emf2、如果利用emf导致字符间距过大&#xff0c;可以选择下面方式 1、可以直接导出emf 导出emf方法&#xff1a; 打开visio --> 另存为 --> 选择emf格式文件 打开word --> 插入图片…

[API]ListList方法集合排序Lambda表达式(四)

List接口&#xff1a; 继承自Collection接口&#xff0c;List集合是可重复集合&#xff0c;并且有序&#xff0c;还提供了一套可以通过下标来操作元素的方法 常见的实现类&#xff1a; ArrayList&#xff1a;内部使用数组实现&#xff0c;查询性能更好(直接下标找到物理地址)、…

开源GPT-4小羊驼(Vicuna)快速上手指南

小羊驼&#xff08;Vicuna)是什么 Vicuna: 一个开源的GPT&#xff0c;宣称实现了GPT-4 90%的功能。 UC伯克利学者联手CMU、斯坦福等&#xff0c;再次推出一个全新模型70亿/130亿参数的Vicuna&#xff0c;俗称「小羊驼」&#xff08;骆马&#xff09;。 并且和其他以往不同的是…

2023红明谷杯部分WP

0x00 签到 一直点就能得到flag 0x01 Dreamer 拿到题感觉有点儿懵 先下发靶机看一眼 梦想家CMS&#xff0c;好嘛&#xff0c;我直接一手查找官网 直接一手演示中心碰运气 哎嘿嘿&#xff0c;运气不错进去了&#xff0c;突然想起之前有位大佬写的关于Dreamer CMS的代码审…

基于ArcGIS、ENVI、InVEST、FRAGSTATS等多技术融合提升环境、生态、水文、土地、土壤、农业、大气等领域的数据分析能力与项目科研水平

【原文链接】&#xff1a;基于ArcGIS、ENVI、InVEST、FRAGSTATS等多技术融合提升环境、生态、水文、土壤、农业、大气等领域的数据分析https://mp.weixin.qq.com/s?__bizMzU5NTkyMzcxNw&mid2247537467&idx4&sn10c4c12897282daf5320efae05caf3a4&chksmfe689551…

​​2021遥感应用组二等奖:基于机器学习回归算法的鄱阳湖水质遥感定量反演及时序变化监测研究

作品介绍 一、作品背景 鄱阳湖是中国第一大淡水湖&#xff0c;也是中国第二大湖&#xff0c;它在调节长江水位、涵养水源、改善当地气候等方面起着重大的作用。但近年来受围垦、环境污染等人类活动影响&#xff0c;鄱阳湖湿地退化严重&#xff0c;同时使鄱阳湖的容量减少&…

Kafka的历史版本对应SpringBoot版本

截至目前&#xff08;2023年&#xff09;&#xff0c;Kafka的最新版本是2.9.0&#xff0c;发布于2022年11月30日。Kafka的历史版本可以在Kafka官方网站的下载页面中找到。Kafka从0.8版本开始发布&#xff0c;经历了多个版本的迭代和升级。以下是一些比较重要的Kafka版本及其发布…

US News退榜风波后,发布最新美国最佳法学院和医学院排名

从2022年11月开始&#xff0c;美国权威排名机构US News不断陷入风波。耶鲁大学法学院率先宣布退出US News法学院排名&#xff0c;先是法学院&#xff0c;后是医学院&#xff0c;包括哈佛大学大学、斯坦福大学、哥伦比亚大学和加州大学伯克利分校等名校也纷纷宣布退出。 这些老…

The 1st Universal Cup Stage 12: ̄Ookayama, April 15-16, 2023 题解

A XOR Tree Path 给一颗树&#xff0c;树上点有黑白两色&#xff0c;每次可以选一个叶子节点&#xff0c;翻转其到根路径上所有点的颜色&#xff0c;问最大黑色点数。 树dp #include<bits/stdc.h> using namespace std; #define MAXN (10000010) #define ll long long…

【社区图书馆】启迪后人——GPT 与读书的奇妙之旅

随着科技的发展和人工智能的不断进步&#xff0c;我们的阅读方式也在逐渐改变。作为一个热爱读书的人&#xff0c;我深感好奇与惊讶地发现&#xff0c;GPT&#xff08;即生成预训练 Transformer&#xff09;正以前所未有的方式拓展我们的阅读视野。在这篇博客中&#xff0c;我将…

RabbitMQ-整合mqtt

用 springboot rabbitmq可以搭建物联网&#xff08;IOT&#xff09;平台&#xff0c;rabbitmq 不是消息队列吗&#xff0c;原来rabbitmq有两种协议&#xff0c;消息队列是用的AMQP协议&#xff0c;而用在智能硬件中的是MQTT协议。 一、rabbitmq是什么&#xff1f; RabbitMQ就…

Windows 自带环境变量

目录 Windows自带环境变量说明Windows自带环境变量总结 所谓 Windows 环境变量&#xff0c;指的是 Windows 指定操作系统工作环境的一些设置选项或属性参数&#xff0c;比方说指定系统文件夹或临时文件夹的位置等。与常量相比&#xff0c;一个环境变量往往由变量名称和变量值组…

MySQL全局锁、表级锁、行级锁介绍演示(详细)

目录 介绍 分类 1、全局锁 1.1介绍 1.2场景 1.3语法 1.4演示 2、表级锁 2.1介绍 2.2分类 2.3语法 2.4演示 3、行级锁 3.1介绍 3.2分类 3.3场景 介绍 锁是计算机协调多个进程或线程并发访问某一资源的机制。在数据库中&#xff0c;除传统的计算资源&#xff08;…

详解语义分割deeplabv3+模型的工业应用流程

来源&#xff1a;投稿 作者&#xff1a;某一个名字 编辑&#xff1a;学姐 导语 在工业视觉应用中&#xff0c;目标检测算法常用于特征的粗定位&#xff0c;而语义分割则在特征的精定位方面有着突出的表现。使用较多的语义分割模型主要有FCN、deeplab系列、unet等&#xff0c;根…

android framework-PackageManagerService(PKMS)包管理服务

一、概述 Android系统启动过程中&#xff0c;会启动一个包管理服务PackageManagerService(PKMS)&#xff0c;这个服务主要负责扫描系统中指定目录&#xff0c;找出里面以apk结尾的文件&#xff0c;通过对这些文件进行解析&#xff0c;得到应用程序的所有信息并完成应用程序的安…