线性表的顺序实现【C语言版的真代码】

news/2024/3/29 23:06:54/文章来源:https://blog.csdn.net/qq_56870066/article/details/128095672

顺序表

    • 线性表
    • 顺序表
      • 顺序表的概念及其结构
      • 顺序表基本操作
      • 顺序表的初始化
      • 顺序表的插入
      • 顺序表的删除
      • 顺序表的查找

线性表

线性表:一个线性表是含n个数据元素的有限序列。

它的逻辑结构要求是线性的,但其存储结构并没有做要求,即逻辑结构类似于如下的表则被称为线性表:
在这里插入图片描述
线性表的每个结点都有且仅有一个前驱(前一个)和一个后继(后一个),但它的第一个结点没有前驱,最后一个结点没有后继。

既然它对存储结构未做要求,那么它的存储结构可以采用顺序存储、也可以采用链式存储。因此一个线性表可以顺序实现、也可以链式实现。
在这里插入图片描述

采用顺序存储的线性表,被称为顺序表,更为详细一点的逻辑关系:
在这里插入图片描述

采用链式存储的线性表,则被称为链表,更为详细一点的逻辑关系:
在这里插入图片描述
线性表的第一个数据元素的存储位置,通常称为线性表的起始地址或者基地址。

顺序表

顺序表的概念及其结构

采用顺序存储的线性表即为顺序表,指的是用一组地址连续的存储单元依次存储线性表的数据元素。通俗地来说,就是这些数据元素存放的“位置是相邻的”。

通常情况下使用数组来描述顺序表(数组的逻辑结构是线性的,物理存储采用顺序存储符合顺序表的特点)

//例如
//定长的数组
int arr[10];
//动态开辟的数组
int* arr;

顺序表可以分为静态顺序表和动态顺序表

  • 静态顺序表:采用定长的数组存储数据元素
  • 动态顺序表:采用动态开辟的数组存储数据元素

【静态顺序表的定义】
现阶段数据元素的类型并不清楚,在C语言中可以使用类型重定义的方式,便于后续修改。

typedef int ELemType;
ElemType arr[100];

同理,究竟需要多大的空间我们也并不确定,因此使用宏定义的方式,便于后续修改

#define MAXSIZE 100
typedef int ELemType;
ElemType arr[MAXSIZE];

仅仅这样无法满足我们需求,线性表不仅要支持存储数据,还要能够对数据进行增删查改。如果顺序表内一个元素都不存在了,还要去删除,又或者说顺序表满了,还要去插入数据元素,这样是不可行的。因此我们还需要一个属性去标记它每个时刻所存放的真实数据元素的个数,当要进行删除的时候,就判断一下个数是不是为0,如果不为0的话再进行删除操作,其他操作根据情况来定:

#define MAXSIZE 100
typedef int ELemType;
struct SeqList
{ELemType arr[MAXSIZE];int size; //记录每个时刻保存的数据元素个数
};

此外,如果直接这样,一个顺序表就需要这样定义struct SeqList name。通常会把这个结构体类型进行类型重定义,达到简写的目的:

#define MAXSIZE 100
typedef int ELemType;
typedef struct SeqList
{ELemType arr[MAXSIZE];int size; //记录每个时刻保存的数据元素个数
}SeqList;

【动态顺序表的定义】

typedef int ELemType;
typedef struct SeqList
{ElemType* arr;int capacity; //记录此时容量大小,以数据元素个数为单位int size; //记录每个时刻保存的数据元素个数
}SeqList;

数组指针arr指向顺序表的基地址。

静态的顺序表因为其存储空间是静态的,如果开一个很大的空间,可能就会造成浪费,如果一开始开比较小的空间,则可能不够用。因此对于更加高阶一些并且基于线性表的数据结构来说,通常采用的都是动态顺序表。

顺序表基本操作

//线性表的初始化
void SeqListInit(SeqList* seq);
//线性表的销毁
void SeqListDestory(SeqList* seq);
//线性表的尾插
void SeqListPushBack(SeqList* seq, ElemType value);
//线性表的尾删
void SeqListPopBack(SeqList* seq);
//线性表的头插
void SeqListPushFront(SeqList* seq, ElemType value);
//线性表的头删
void SeqListPopFront(SeqList* seq);
//线性表的查找
int SeqListFind(SeqList* seq, ElemType value);
//在pos位置(下标)插入value
void SeqListInsert(SeqList* seq, int pos, ElemType value);
//删除pos位置(下标)的值
void SeqListErase(SeqList* seq, int pos);
//打印顺序表
void SeqListPrint(SeqList seq);

下面将只介绍几个十分重要的顺序表基本操作

顺序表的初始化

void SeqListInit(SeqList* seq)
{seq->arr = NULL;seq->size = seq->capacity = 0;
}

顺序表的插入

顺序表的插入有三种情况:

  • 尾插:在顺序表的尾部插入一个数据元素
  • 头插:在顺序表的头部插入一个数据元素
  • 在任意位置(下标)处插入一个数据元素

【尾插的实现】

void SeqListPushBack(SeqList* seq, ElemType value)
{}

按照逻辑,直接将要插入的数据元素放入数组的尾部。
在这里插入图片描述

此时数组尾部的下标就是size的大小,插入之后一定要维护size的值。

void SeqListPushBack(SeqList* seq, SLDataType value)
{seq->arr[seq->size] = value;seq->size++;
}

但还可能会遇到顺序表已满的情况,此时就不能够直接进行插入。若顺序表已满,插入前则应该先扩容,再执行上述的逻辑。
在这里插入图片描述
那么在进行插入之前,应当先判断顺序表内此刻是否有空间,能够容纳要插入的数据元素。当size和capacity相同的时候,就表示顺序表内没有多余的空间。但还要分成两种情况:
(1)size=capacity=0;顺序表一点容量都没有
(2)size=capacity≠0;顺序表没有多余容量存放其他数据元素

void SeqListPushBack(SeqList* seq, SLDataType value)
{if(seq->size == seq->capacity){//如果为空,则新容量为4;否则开辟原来的2倍//策略可以自行定制,但要注意适当int newcapacity = (seq->capacity == 0 ? 4 : seq->capacity * 2);ElemType* tmp = (ElemType*)realloc(seq->arr, sizeof(ElemType) * newcapacity);if(NULL == tmp){printf("扩容失败\n");exit(-1);}seq->arr = tmp;seq->capacity = newcapacity;}seq->arr[seq->size] = value;seq->size++;
}

【头插的实现】
和尾插类似,在进行插入前需要检查是否还有足够的容量,容纳准备插入的数据元素。为了提高代码的复用率,我们可以将检查容量的工作提取出来,封装成一个方法。

void SeqListCheckCapac(SeqList* seq)
{//如果size== capacity说明:数组为空 或者满了;需要扩容if (seq->size == seq->capacity){int newcapacity = seq->capacity == 0 ? 4 : (seq->capacity * 2);ElemType* tmp = (ElemType*)realloc(seq->arr, sizeof(ElemType) * newcapacity);if (tmp == NULL){printf("扩容失败\n");exit(-1);}seq->arr = tmp;seq->capacity = newcapacity;}
}

优化一下尾插的方法:

void SeqListPushBack(SeqList* seq, ElemType value)
{//检查容量SeqListCheckCapac(seq);seq->arr[seq->size] = value;seq->size++;
}

现在正式开始顺序表头插的实现

void SeqListPushFront(SeqList* seq, ElemType value)
{//检查容量SeqListCheckCapac(seq);
}

在这里插入图片描述
在顺序表的头部进行插入,若插入位置有数据元素,则应将数据元素往后面挪。但只将插入位置的一个数据元素挪到后面,会把后面的数据元素覆盖掉。因此要从顺序表的尾部开始,依次将数据元素往后挪一个位置。简而言之,就是要给插入的数据元素“腾位置”。
在这里插入图片描述
然后插入即可。

void SeqListPushFront(SeqList* seq, ElemType value)
{//检查容量SeqListCheckCapac(seq);int end = seq->size - 1;while(end > 0){seq->arr[end + 1] = seq->arr[end]end--;}seq->arr[0] = value;seq->size++;
}

[在任意位置插入]
同样,插入前需要检查容量,并且还需要判断选择插入的位置是否合法,在准许插入的范围之内。

//在pos位置插入value
void SeqListInsert(SeqList* seq, int pos, ElemType value)
{//检查容量SeqListCheckCapac(seq);if(pos < 0 || pos > seq->size){printf("试图插入一个非法的位置\n");return;}
}

在这里插入图片描述
如果不是尾部的插入(当前要插入的位置有数据元素),类似于头插,需要给它“腾位置”,从尾部开始依次往后挪一位。
在这里插入图片描述

//在pos位置插入value
void SeqListInsert(SeqList* seq, int pos, ElemType value)
{//检查容量SeqListCheckCapac(seq);if(pos < 0 || pos > seq->size){printf("试图插入一个非法的位置\n");return;}int end = seq->size - 1;while(end > pos){seq->arr[end + 1] = seq->arr[end]end--;}seq->arr[pos] = value;seq->size++;
}

顺序表的删除

顺序表的删除共有三种删除方式:

  • 尾删:删除顺序表尾部的一个数据元素;
  • 头删:删除顺序表头部的一个数据元素;
  • 删除顺序表任意位置的一个数据元素

【尾删的实现】
尾删的基本做法:将尾部的位置置为初始值,同时size的大小减去1;
但对于我们的角度来说,只要访问不到这个位置,那么就认为这个位置不存在真实的数据元素。根据整个代码的逻辑来看,只需要将描述顺序表内真实数据元素个数的size,减去1即可。

void SeqListPopBack(SeqList* seq)
{seq->size--;
}

设想顺序表内没有数据元素了,却仍然要去执行删除的操作,那么必定不能够删除。因此在执行删除操作之前,还需判断顺序表内是否存在数据元素。此处可采用稍暴力的方式“断言”

void SeqListPopBack(SeqList* seq)
{assert(seq->size > 0);seq->size--;
}

【头删的实现】
同尾删一样,删除前需要检查顺序表内是否存在数据元素。

void SeqListPopFront(SeqList* seq)
{assert(seq->size > 0);
}

在这里插入图片描述
(1)若删除位置后面不存在数据元素,可直接将size的值减去1即可;
(2)若删除位置后面存在数据元素,将后面的值依次挪到前面,将要删除位置的数据元素进行覆盖,再将size的值减去1即可。
在这里插入图片描述

void SeqListPopFront(SeqList* seq)
{assert(seq->size > 0);int end = 0;while (end < seq->size){seq->arr[end] = seq->arr[end + 1];end++;}seq->size--;
}

【任意位置的删除】
类似于头删,若后面存在数据元素,则将删除位置后面的数据元素依次挪动即可,若不存在数据元素就无需挪动,再将顺序表size的值减去1即可。

void SeqListErase(SeqList* seq, int pos)
{assert(seq->size > 0 && pos >=0 && pos < seq->size);int end = pos;while (end < seq->size){seq->arr[end] = seq->arr[end + 1];end++;}seq->size--;
}

顺序表的查找

由于顺序表采用数组实现,那么它就支持随机访问。因此要查找一个数据元素时,只需要依次去比较,如果找到了符合的,返回对应的下标即可。否则返回-1,表示该顺序表内不存在这样的数据元素。

int SeqListFind(SeqList* seq, ElemType value)
{for (int i = 0; i < seq->size; i++){if (value == seq->arr[i]){return i;}}return -1;
}

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

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

相关文章

m基于NSGAII优化算法的微网系统的多目标优化规划matlab仿真

目录 1.算法描述 2.仿真效果预览 3.MATLAB核心程序 4.完整MATLAB 1.算法描述 NSGA-II是基于的非支配排序的方法,在NSGA上进行改进&#xff0c;也是多目标进化优化领域一个里程碑式的一个算法。 NSGA-Ⅱ算法是 Srinivas 和 Deb 于 2000 年在 NSGA 的基础上提出的&#xff0c…

预约陪诊系统开发,跨省就医也能省时省力

就医陪护服务这几年一直受到人们的好评&#xff0c;有了预约陪诊系统开发之后一些无法居家照顾老人的子女可以通过就医陪护为老人预约服务&#xff0c;预约陪诊平台的出现还让陪诊员有了正规的接单平台&#xff0c;不仅方便了人们下单找就医陪诊员还可以对陪诊人员实行正规的管…

解决nginx: [emerg] unknown directive “stream“ in /etc/nginx/nginx.conf问题

文章目录1.未报错时nginx配置&#xff1a;2.报错时nginx配置&#xff1a;3.增加配置报错&#xff1a;4.增加配置位置如下&#xff1a;5.解决办法&#xff1a;6.测试&#xff1a;nginx -t1.未报错时nginx配置&#xff1a; #user nginx; user root; worker_processes auto;er…

群晖外网访问终极解决方法:IPV6+阿里云ddns+ddnsto

写在前面的话 受够了群晖的quickconnet的小水管了&#xff0c;急需一个新的解决方法&#xff0c;这是后发现移动没有公网IP&#xff0c;只有ipv6&#xff08;公网的&#xff09;&#xff0c;时候有小伙伴要问&#xff0c;要是没有ipv6就没办法访问群晖了吗&#xff1f; 不&…

微信截图无法发送,也发不出电脑上的图片

微信截图无法发送&#xff0c;也发不出电脑上的图片 现象 今天微信突然出现这个问题&#xff0c;怎么改设置都调不好&#xff0c;卸载重装都不行&#xff0c;最后发现&#xff0c;微信的消息目录中&#xff0c;一些文件无法删除&#xff0c;提示“文件或目录损坏且无法读取”…

TinyML:是否是FPGA在人工智能方面的最佳应用?

TinyML 也是机器学习的一种&#xff0c;他的特点就是缩小深度学习网络可以在微型硬件中使用&#xff0c;主要应用在智能设备上。超低功耗嵌入式设备正在“入侵”我们的世界&#xff0c;借助新的嵌入式机器学习框架&#xff0c;它们将进一步推动人工智能驱动的物联网设备的普及。…

sipp: bind_local;watchdog timer trip

文章目录作为服务端时&#xff0c;source ip 随机的问题命令示例bind_localwatchdog_minor_maxtriggers作为服务端时&#xff0c;source ip 随机的问题 https://sipp.sourceforge.net/doc/reference.html https://github.com/SIPp/sipp/issues/83 https://github.com/SIPp/sip…

虹科分享 | 网络流量监控 | 使用 ntopng 收件人和端点进行灵活的警报处理

在之前&#xff0c;ntopng引擎对所有警报的配置是单一的&#xff1a;进入偏好页面并指定警报的发送地点。但这是不理想的&#xff0c;原因有很多&#xff1a;包括不可能在不同的渠道向不同的收件人发送警报&#xff0c;或有选择地决定何时发送警报。 出于这个原因&#xff0c;…

北大惠普金融指数-匹配企业绿色创新指数2011-2020年:企业名称、年份、行业分类等多指标数据

1、数据来源&#xff1a;北京大学数字金融中心、国家统计局、国家专利产权局等部门公开数据 2、时间跨度&#xff1a;2011-2020年 3、区域范围&#xff1a;全国 4、指标说明&#xff1a; 中国内地31个省&#xff08;直辖市、自治区&#xff0c;简称“省”&#xff09;、337…

网络安全工程师必备证书有哪些?

网络环境之间的竞争&#xff0c;归根到底优秀人才之间的竞争。 在2022年网络安全周上&#xff0c;《网络安全人才实战能力白皮书》正式公布。资料显示&#xff0c;到2027年&#xff0c;我国网络安全人员缺口将达327万&#xff0c;而高校人才培养经营规模仅是3万/年。 那样&am…

小程序数据请求的方式和注意事项

1.小程序中网络数据请求的限制 出于安全性方面的考虑&#xff0c;小程序官方对数据接口的请求做出了如下两个限制&#xff1a; ① 只能请求HTTPS类型的接口 ② 必须将接口的域名添加到信任列表中 2.配置request合法域名 假设要在自己的微信小程序中&#xff0c;希望请求某…

【JavaScript作用域】

JavaScript作用域1 本节目标2 作用域2.1 作用域概述2.2 全局作用域2.3 局部作用域3 变量的作用域3.1 变量作用域的分类3.2 全局变量3.3 局部变量3.4 从执行效率看全局变量与局部变量3.5 JS没有块级作用域4 作用域链1 本节目标 说出JavaScript的两种作用域区分全局变量和局部变…

关系抽取(二)远程监督方法总结

目录 前言 1. 远程监督关系抽取开山之作 1.1 介绍 1.2 训练过程 1.2.1 数据标注方法 1.2.2 训练方法 1.3 测试过程 1.4 思考 1.5 总结 2. PCNN 2.1 介绍 2.2 模型结构 2.2.1 文本特征表示 2.2.2 卷积 2.2.3 分段最大池化 2.2.4 softmax多分类 2.3 多实例学习的…

React Server Component: 混合式渲染

作者&#xff1a;谢奇璇 React 官方对 Server Comopnent 是这样介绍的: zero-bundle-size React Server Components。 这是一种实验性探索&#xff0c;但相信该探索是个未来 React 发展的方向&#xff0c;与 React Server Component 相关的周边生态正在积极的建设当中。 术语…

Spring Cloud OpenFeign - - - >拦截器

源码地址&#xff1a;https://download.csdn.net/download/weixin_42950079/87209379 SpringMVC拦截器 和 OpenFeign拦截器 的区别 初学者很容易将 Spring MVC 拦截器 和 Spring Cloud OpenFeign 拦截器搞混&#xff0c;误以为OpenFeign拦截器就是SpringMVC拦截器&#xff1a; …

Kotlin高仿微信-第9篇-单聊-文本

Kotlin高仿微信-项目实践58篇详细讲解了各个功能点&#xff0c;包括&#xff1a;注册、登录、主页、单聊(文本、表情、语音、图片、小视频、视频通话、语音通话、红包、转账)、群聊、个人信息、朋友圈、支付服务、扫一扫、搜索好友、添加好友、开通VIP等众多功能。 Kotlin高仿…

Spark系列之Spark的数据倾斜

title: Spark系列 第九章 Spark的数据倾斜 9.1 Spark调优概述 ​ 有的时候&#xff0c;我们可能会遇到大数据计算中一个最棘手的问题——数据倾斜&#xff0c;此时 Spark 作业的性能会比期望差很多。数据倾斜调优&#xff0c;就是使用各种技术方案解决不同类型的数据倾斜问题…

2022腾讯全球数字生态大会【存储专场】它来了|预约有礼

它来了&#xff01;它来了&#xff01; 2022腾讯全球数字生态大会【存储专场】它来了&#xff01; 作为腾讯集团产业互联网规格最高、规模最大、覆盖面最广的年度盛会 今年存储专场与您一起探讨 分布式高性能存储与数据分析处理的科技创新和最新成果 存储会场六大亮点&…

PyQt5可视化编程-事件、信号和对话框

一、概述: 所有的应用都是事件驱动的。事件大部分都是由用户的行为产生的&#xff0c;当然也有其他的事件产生方式&#xff0c;比如网络的连接&#xff0c;窗口管理器或者定时器等。调用应用的exec_()方法时&#xff0c;应用会进入主循环&#xff0c;主循环会监听和分发事件。…

【SpringBoot】对于yaml的详细学习和三种属性赋值的实战详解

一.yaml详细讲解 1.1 什么是yaml&#xff1f; YAML是一种数据序列化语言&#xff0c;通常用于编写配置文件。业界对YAML有不同的看法。有些人会说YAML代表另一种标记语言。其他人认为“YAML不是标记语言”&#xff08;“YAML并非标记语言”&#xff09;。“YAML”只是这句话的…