数据结构之顺序表(C语言)

1 线性表

线性表是n个具有相同特性的数据元素的有限序列,是一种在实际中广泛应用的数据结构,常见的线性表有:顺序表、链表、栈、队列、字符串等。

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

2 顺序表的分类

2.1 顺序表与数组的区别

顺序表是线性表的一种,顺序表的特性是:逻辑结构连续,物理结构也是连续的。顺序表的最底层结构是数组,但顺序表在数组的基础上实现了对数组的封装及增删查改等接口。我们可以把数组看成路边小摊,而顺序表就是米其林餐厅,二者虽然结构类似,但发挥的功能却不一样,档次也就自然有所差别。

2.2 静态顺序表

静态顺序表也就表示顺序表存储空间是提前给定的,无法改变。即使用定长数组来进行数据的存储。如下:

struct SeqList//用结构体来完成顺序表的操作
{int arr[100];//定长数组int size;//顺序表中有效的数据个数
};

如果使用静态顺序表就要面临两个严峻的问题:

一、数组空间开辟小了,空间不够用

二、数组空间开辟大了,空间浪费

基于这种情况我们选择使用动态内存开辟,即使用动态顺序表。

2.3 动态顺序表

动态顺序表需要使用到动态内存开辟,所以在结构体内我们对数组要使用指针进行定义,同时需要增加一个申请的空间大小的变量capacity。

Struct SeqList//定义结构体
{int* arr;//定义数组int size;//顺序表中有效的数据个数int capacity;//空间大小
};

当代码量非常庞大,我们若想将部分 int 类型替换为 char 类型时,使用上面的定义方式就会引来麻烦。所以在这里我们将 涉及到顺序表的 int 类型重命名一下,如此一来就方便了我们去对源程序进行查找替换等操作。(同时我们也可以对结构体类型进行重命名)

typedef int SLDataTypetypedef struct SeqList//定义结构体
{SLDataType* arr;//定义数组SLDataType size;//顺序表中有效的数据个数SLDataType capacity;//空间大小
}SL;

3 顺序表的初始化、打印与销毁

在结构体中,为了使每部分功能都独立存在,我们只是对顺序表中的内容进行了定义,而并未进行初始化。故此时我们定义一个初始化函数来完成这部分功能。

void SLInit(SL* ps)//将结构体变量作为参数传到形参
{ps -> arr = Null;//初始化置为空ps -> size = ps -> capacity = 0;//初始化置为0
}

在我们初始化并插入数据后,我们可以自定义一个打印函数对该顺序表内数据进行打印。

在一系列操作完毕后需要销毁顺序表来释放对应的内存空间,故我们再来定义一个销毁函数来完成这部分功能。

void Destroy(SL* ps)
{if(ps -> arr)//等价于 (ps->arr != NULL){free(ps->arr);}ps -> arr = NULL;//将释放的空间置为空,避免野指针造成错误访问ps -> size = ps -> capacity = 0;
}

在上面的销毁操作中,最值得注意的就是在释放了顺序表内的空间后,原有空间部分的首地址指针要置为空,避免生成野指针造成错误访问。

通过上面两个自定义函数我们可以观察到,我们在传参部分使用的是传址调用而不是传值调用。若使用传值调用,函数内操作的部分是原数据的一份临时拷贝,出栈帧即会销毁。实参部分不会得到真实改变,所以在此处传参我们要使用指针来接收要操作部分的地址,实现传址调用来改变实参部分。

4 顺序表的尾插法与头插法

4.1 空间检查函数

在操作数据前我们应首先考虑申请空间的大小,即一次申请多大的空间,使用哪一个内存函数。我们知道C语言中内存函数有 malloc 、calloc 、realloc。

  • malloc 只负责分配指定字节数的内存块,不对其进行初始化。
  • calloc 在分配内存块的同时,将其初始化为零。
  • realloc 用于重新分配内存块的大小,并尝试保留原始内存块中的数据。

由于我们是需要对数组进行扩容,所以我们选择 realloc。原因如下:

  • 避免频繁地分配和释放内存: 如果每次增加大小就用 malloc 分配新的内存,然后丢弃旧的,会频繁引起内存碎片,并可能导致大量小块内存无法再利用,效率低下。realloc 可以合并相邻的小内存块,减少碎片。
  • 连续存储realloc 能够保持原有数据的连续性,这对于性能优化特别重要,特别是对于需要快速访问元素的数据结构(如链表和数组)。
  • 节省时间realloc 在现有内存基础上进行扩展,相比于多次 malloc 和 free 操作,它减少了系统调用次数,提高了程序响应速度。

确定使用的内存函数后,每次扩容应扩大多少?扩容通常来说是成倍数的增加,一般来说是2倍或3倍(由数学推理得出的最佳值)

void SLcheckcapacity(SL* ps)
{if (ps->capacity == ps->size){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目表达式SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//我们之所以用newcapacity和tmp来过渡是为了保证即使扩容失败原有数据也不会丢失if (tmp == NULL)//之所以在此判断是为了确定扩容成功{perror("扩容失败");exit(1);}ps->capacity = newcapacity;//扩容成功,将过渡变量的值赋值给arr和capacityps->arr = tmp;}
}

4.2 尾插函数

void SLPushBack(SL* ps, SLDataType x)
{//判断ps是否为空//温柔的解决方式/*if (ps == NULL){return;}*///暴力判断ps是否为空assert(ps);//等价于assert(ps != NULL)//对空间大小判断SLcheckcapacity(ps);ps->arr[ps->size] = x;++ps->size;//更加巧妙地尾插代码//ps->arr[ps->size++] = x; 使用后置++使得数据插入后size才会发生++操作
}

对数组进行尾插操作就找到数组已有数据后面一位再插入数据,由此我们需要将结构体的地址和要插入的数据传递给尾插函数。

4.3 头插函数

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++;//顺序表内元素个数加一(下标)
}

头插操作中最关键的一步就是对已有数据的挪动,一定是从最后往后移,否则会造成原有数据丢失。

5 顺序表的尾删和头删

5.1 尾删函数

void SLPopBack(SL* ps, SLDataType x)
{assert(ps);assert(ps->size);//上面判断顺序表不为空--ps->size;//我们将顺序表有效数值个数减一后,最后一位元素就无法访问了,即被我们从顺序表中删除
}

尾删的关键在于把顺序表中数组的最后一位下标减一,如此最后一位元素就无法访问了,即被我们删除。

5.2 头删函数

void SLPopfront(SL* ps, SLDataType x)
{assert(ps);SLcheckcapacity(ps);//顺序表判空并同时检查空间//数据整体往前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;//顺序表中有效数据个数减一
}

头删操作和头插操作逻辑类似,关键都在于对于数据的挪动,只是头删时我们需要把数据整体往前挪动一位。

6 指定位置的插入与删除

6.1 指定位置插入数据

如上图所示,顺序表中原有的有效数据个数对应到顺序表元素下标时,其会在最后一个元素后面一位(即留有一处可操作的为空的空间),我们想要在指定位置(此处指定位置我们定义为pos)插入元素时,便需要将pos之后的元素全部后移一位,而 arr[size] 这一块空间就为我们移动数据做了准备。

同时,我们还要考虑一个问题就是指定的位置pos是否在顺序表有效的空间之内,pos能否等于0 , -1 , 10000呢?要解决上面问题j就需要我们对pos的大小进行判断。第一,pos最小是多少?显而易见,pos最小时为0,也就是头插。第二,pos最大是多少?由上类推可知pos最大是pos == size的时候,也就是尾插。

void SLInsert(SL* ps, int pos, SLDataType x)
{//判断传过来的结构体地址不为空assert(ps);//判断指定的位置pos是否在现有情况之下assert(pos >= 0 && pos <= ps->size);//判断空间大小够不够SLcheckcapacity(ps);//将pos及其之后的数据统一往后移动一位for (int i = ps->size; i > pos; i--)//既然是后移,循环的初始化部分就是顺序表中可操作空间的最后,即i == size//循环判断部分可以使用极限情况推导得出,见下面注释{ps->arr[i] = ps->arr[i - 1];//最后一次循环情况 arr[pos+1] = arr[pos]}ps->arr[pos] = x;++ps->size;//顺序表中有效数据个数+1
}

6.2 指定位置删除数据

如上图所示,在指定位置删除数据需要将pos后面的数据整体向前移动一位,从而让pos+1处的数据将pos处的数据覆盖以实现删除效果。

void SLErase(SL* ps, int pos)
{//判断传来的结构体地址不为空assert(ps);//判断指定的位置pos是否合理assert(pos >= 0 && pos <= ps->size);for (int i = pos; i < ps->size - 1; i++)//因为是要在指定位置删除数据,故  i == pos//循环判断部分可以使用极限情况推导得出,见下面注释{ps->arr[i] = ps->arr[i + 1];//最后一次循环时情况 arr[size-2] = arr[size-1]}--ps->size;//删除数据后,顺序表中有效数据个数 -1
}

7 顺序表数据查找

void SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("找到啦");return i;}else{printf("没有找到");return -1;}}
}

8 顺序表全程序及演示结果

8.1 SeqList.h 文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;void SLInit(SL* ps);void SLDestroy(SL* ps);void SLPrint(SL s);void SLcheckcapacity(SL* ps);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);void SLFind(SL* ps, SLDataType x);

8.2 SeqList.c 文件

#include"SeqList.h"void SLInit(SL* ps)
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}void SLDestroy(SL* ps)
{free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLPrint(SL s)
{int i = 0;for (i = 0; i < s.size; i++){printf("%d", s.arr[i]);}printf("\n");
}void SLcheckcapacity(SL* ps)
{if (ps->capacity == ps->size){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//我们之所以用newcapacity和tmp来过渡是为了保证即使扩容失败原有数据也不会丢失if (tmp == NULL)//之所以在此判断是为了确定扩容成功{perror("扩容失败");exit(1);}ps->capacity = newcapacity;//扩容成功,将过渡变量的值赋值给arr和capacityps->arr = tmp;}
}void SLPushBack(SL* ps, SLDataType x)
{//判断ps是否为空//温柔的解决方式/*if (ps == NULL){return;}*///暴力判断ps是否为空assert(ps);//等价于assert(ps != NULL)//对空间大小判断SLcheckcapacity(ps);ps->arr[ps->size] = x;++ps->size;//更加巧妙地尾插插入//ps->arr[ps->size++] = x; 使用后置++使得数据插入后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 SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//上面判断顺序表不为空--ps->size;//我们将顺序表有效数值个数减一后,最后一位元素就无法访问了,即被我们从顺序表中删除
}void SLPopfront(SL* ps)
{assert(ps);SLcheckcapacity(ps);//顺序表判空并同时检查空间//数据整体往前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;//顺序表中有效数据个数减一
}//在指定位置pos插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{//判断传过来的结构体地址不为空assert(ps);//判断指定的位置pos是否合理assert(pos >= 0 && pos <= ps->size);//判断空间大小够不够SLcheckcapacity(ps);//将pos及其之后的数据统一往后移动一位for (int i = ps->size; i > pos; i--)//既然是后移,循环的初始化部分就是顺序表中可操作空间的最后,即i == size//循环判断部分可以使用极限情况推导得出,见下面注释{ps->arr[i] = ps->arr[i - 1];//最后一次循环情况 arr[pos+1] = arr[pos]}ps->arr[pos] = x;++ps->size;//顺序表中有效数据个数+1
}//在指定位置删除数据
void SLErase(SL* ps, int pos)
{//判断传来的结构体地址不为空assert(ps);//判断指定的位置pos是否合理assert(pos >= 0 && pos <= ps->size);for (int i = pos; i < ps->size - 1; i++)//因为是要在指定位置删除数据,故  i == pos//循环判断部分可以使用极限情况推导得出,见下面注释{ps->arr[i] = ps->arr[i + 1];//最后一次循环时情况 arr[size-2] = arr[size-1]}--ps->size;//删除数据后,顺序表中有效数据个数 -1
}//查找
void SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("找到啦");return i;}else{printf("没有找到");return -1;}}
}

8.3 SeqList_test.c 测试文件

#include"SeqList.h"void SLtest_1()
{SL sl;SLInit(&sl);//增删查改操作//测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);//1 2 3 4//SLPushFront(&sl, 5);//SLPushFront(&sl, 6);//测试尾删SLPopBack(&sl);SLPrint(sl);//1 2 3 SLPopBack(&sl);SLPrint(sl);//1 2SLPopBack(&sl);SLPrint(sl);//1//SLPopBack(&sl);//SLPrint(sl);//空//...........SLDestroy(&sl);
}int main()
{SLtest_1();return 0;
}

运行结果:

写作不易,不知各位老板能否给个一键三连或是一个免费的赞呢(*^▽^*)(*^▽^*),这将是对我最大的肯定与支持!!!谢谢!!!(*^▽^*)(*^▽^*)

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

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

相关文章

#【YashanDB认证】#YCA的学习过程总结-之崖山数据库初体验

概述 前段时间崖山数据库做推广活动&#xff0c;参加了yca的考试&#xff0c;为啥参加这个数据库厂商的学习呢&#xff0c;因为目前这个数据库最像Oracle&#xff0c;又听公司的前辈说呢&#xff0c;这个公司的前身是华为人出来做的数据库&#xff0c;华为人的精神呢&#xff0…

一些硬件知识【2024/11/3】

MLCC电容的ESR比较小&#xff0c;但是他的缺点是容量通常比较低&#xff1b;电解电容的容量比较大&#xff0c;但是他的ESR比较大&#xff1b;而钽电容介于两者之间&#xff0c;是MLCC找不到合适的容值比较大的时候&#xff0c;找钽电容&#xff1a; LC谐振电路&#xff1a; 五…

2024版红娘金媒10.3婚恋相亲系统源码小程序(亲测)

1. 红娘服务 红娘服务模块是该系统的一大特色。专业红娘会通过分析用户的个人资料和偏好&#xff0c; 为用户提供精准的配对建议和个性化服务。用户可以预约红娘服务&#xff0c;通过红娘的介入&#xff0c;提升配对成功率。 2. 相亲活动 相亲活动模块用于组织和管理线下或线…

自扶正救生艇,保障水上救援的安全卫士_鼎跃安全

在应急事件中&#xff0c;自扶正救生艇能够发挥关键的救援和保障作用&#xff0c;确保救援人员和被困人员的生命安全&#xff0c;尤其在极端天气或突发水上事故中展现出明显优势。 在救援过程中如果遭遇翻船&#xff0c;救生艇能够迅速恢复正常姿态&#xff0c;确保救援人员不会…

鸿蒙网络编程系列42-仓颉版域名解析示例

1. 域名解析简介 域名解析是网络开发中经常使用的功能之一&#xff0c;特别是对于当前版本的鸿蒙API&#xff0c;使用TCP或者UDP等网络协议通讯时&#xff0c;只能使用确定的IP地址进行绑定或者发送消息&#xff0c;还不支持直接使用域名&#xff0c;所以&#xff0c;通过域名…

6.0、静态路由

路由器最主要的功能就是转发数据包。路由器转发数据包时需要查找路由表&#xff08;你可以理解为地图&#xff09;&#xff0c;管理员可以直接手动配置路由表&#xff0c;这就是静态路由。 1.什么是路由&#xff1f; 在网络世界中&#xff0c;路由是指数据包在网络中的传输路…

玩转HF/魔搭/魔乐社区(作业)

任务描述时间模型下载使用Hugging Face平台、魔搭社区平台&#xff08;可选&#xff09;和魔乐社区平台&#xff08;可选&#xff09;下载文档中提到的模型&#xff08;至少需要下载config.json文件、model.safetensors.index.json文件&#xff09;&#xff0c;请在必要的步骤以…

QT——记事本项目

目录 1.给pushButton按键添加图片 1.1 首先复制存放图片的文件夹&#xff0c;打开Qt回到编辑页面&#xff0c;右键单击pro文件选择在Explorer中显示&#xff0c;将图片文件夹粘贴进去你的代码同目录即可 1.2 创建一个新的文件夹 1.3 点击Add Files&#xff0c;将所有图片添加…

Redis-“自动分片、一定程度的高可用性”(sharding水平拆分、failover故障转移)特性(Sentinel、Cluster)

文章目录 零、写在前面一、水平拆分(sharding/分片)、故障转移(failover)机制介绍水平拆分&#xff08;Sharding&#xff09;故障转移机制 二、Redis的水平拆分的机制有关的配置1. 环境准备2. 配置文件配置3. 启动所有Redis实例4. 创建集群5. 测试集群读/写6. 集群管理 三、Red…

OpenCV视觉分析之目标跟踪(7)目标跟踪器类TrackerVit的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 VIT 跟踪器由于特殊的模型结构而变得更快且极其轻量级&#xff0c;模型文件大约为 767KB。模型下载链接&#xff1a;https://github.com/opencv/…

yolov8训练及测试(ubuntu18.04、tensorrt、ros)

1 数据集制作 1.1标注数据 Linux/Ubuntu/Mac 至少需要 Python 2.6 &#xff08;推荐使用 Python 3 或更高版本 及 PyQt5&#xff09; Ubuntu Linux (Python 3 Qt5) git clone https://gitcode.com/gh_mirrors/la/labelImg.git sudo apt-get install pyqt5-dev-tools cd lab…

海睿思产品体系二次开发能力介绍

海睿思产品体系支持用户通过编写开发代码&#xff08;含低代码&#xff09;&#xff0c;提供定制化功能&#xff0c;解决数据治理和共享场景的个性化需求。 1、数据集成 应用场景&#xff1a;自定义数据集成能力 开发语言&#xff1a;JAVA 使用效果&#xff1a; 1&#xff…

SpringMVC笔记 一万字

此笔记来自于B站尚硅谷 文章目录 一、SpringMVC 简介1、什么是MVC2、什么是SpringMVC3、SpringMVC的特点 二、HelloWorld1、开发环境2、创建maven工程a>添加web模块b>打包方式&#xff1a;warc>引入依赖 3、配置web.xmla>默认配置方式b>扩展配置方式 4、创建请求…

Maven随笔

文章目录 1、什么是MAVEN2、Maven模型3、Maven仓库4、项目集成1_Idea集成Maven设置2_创建Maven项目3_POM配置详解4_maven 坐标详情5_Maven工程类型6_导入Maven项目 5、依赖管理1_依赖配置2_依赖传递3_可选依赖4_排除依赖4_可选依赖和排除依赖的区别5_依赖范围6_继承与聚合7_版本…

看门狗有什么用?

看门狗(WATCH-DOG Timer)全称看门狗定时器 用途&#xff1a;防止程序死机&#xff08;主要用途&#xff09; 或 单纯用来计时 直接上代码&#xff1a; 只要程序可以正常运行&#xff0c;看门狗就会清零&#xff0c;如果崩了&#xff0c;看门狗就会复位程序

云原生开源开发者沙龙丨AI 应用工程化专场杭州站邀您参会

云原生开源开发者沙龙 AI 原生应用架构专场&#xff0c;邀您一起交流&#xff0c;探索 AI 原生应用的工程化落地&#xff01; 活动简介 AI 驱动的应用程序开发、部署和运维&#xff0c;给应用带来了新的生命力和想象空间。但大部分开发者对 AI 应用的编程框架、可观测体系、网…

UFO:Windows操作系统的具象智能代理

近年来&#xff0c;随着AI技术的发展&#xff0c;智能代理在各种应用中扮演着越来越重要的角色。微软推出的UFO&#xff08;User-Focused Operator&#xff09;正是这样一个出色的多代理框架&#xff0c;旨在通过无缝导航和操作&#xff0c;满足用户在Windows操作系统中跨多个应…

基于人工智能的搜索和推荐系统

互联网上的搜索历史分析和用户活动是个性化推荐的基础&#xff0c;这些推荐已成为电子商务行业和在线业务的强大营销工具。随着人工智能的使用&#xff0c;在线搜索也在改进&#xff0c;因为它会根据用户的视觉偏好提出建议&#xff0c;而不是根据每个客户的需求和偏好量身定制…

使用ffmpeg和mediamtx模拟多通道rtsp相机

首先下载ffmpeg&#xff0c;在windows系统上直接下载可执行文件&#xff0c;并配置环境变量即可在命令行当中调用执行。 下载地址&#xff1a; https://ffmpeg.org/再在github上下载mediamtx搭建rtsp服务器&#xff0c;使用ffmpeg将码流推流到rtsp服务器。 下载地址&#xff1…

Spring Boot框架:校园社团信息管理的现代化解决方案

3系统分析 3.1可行性分析 通过对本校园社团信息管理系统实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本校园社团信息管理系统采用SSM框架&#xff0c;JAVA作…