### 【数据结构】线性表--顺序表(二)

文章目录

        • 1、什么是线性表
        • 2、线性表的基本操作
        • 3、顺序表
          • 3.1、顺序表的定义
          • 3.2、顺序表的实现方式:静态分配
          • 3.3、顺序表的实现方式:动态分配
          • 3.4、顺序表的特点
          • 3.5、顺序表的初始化与插入操作
          • 3.6、顺序表的删除与查询

1、什么是线性表

​ 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表,若用L命名线性表,则其一般表示为

​ L = (a1,a2,…,ai,ai+1,…,an

如图所示:

image-20240506222820628

每个数据类型都相同,也意味着每个数据元素所占空间一样大

重要概念:

  1. ai是线性表中的“第i个”元素线性表中的位序
  2. a1是表头元素;an是表尾元素
  3. 除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继
2、线性表的基本操作

常用操作:

  • InitList(&L):初始化表。构造一个空的线性表L,分配内存空间
  • DestroyList(&L):销毁操作。销毁线性表,并释放线性表L所占用的内存空间。
  • ListInsert(&Li,e):插入操作。在表L中的第i个位置上插入指定元素e。
  • ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
  • LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素
  • GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作:

  • Length(L):求表长。返回线性表L的长度,即L中数据元素的个数
  • PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
  • Empty(L):判空操作。若L为空表,则返回true,否则返回false。

Tips:

  1. 数据元素的位序是从1开始,而程序数组下标是0开始
  2. 在实际开发中,可根据实际需求定义其他的基本操作
3、顺序表
3.1、顺序表的定义

​ 顺序表指的是用顺序存储的方式来实现线性表的顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。

image-20240507105149070

3.2、顺序表的实现方式:静态分配
#define MaxSize 10		//定义最长长度
typedef struct{ElemType data[MaxSize];	//用静态的数组存放数据int length;				//顺序表当前长度
}SqList;		//顺序表的类型定义(静态分配方式)

**问题:**如果数组数组存满了呢?

  • 直接放弃治疗,顺序表的表长刚开始就确定后,无法更改(存储空间是静态的)

**思考:**如果刚开始就声明一个很大的内存空间呢?存在什么问题?

  • 过于浪费
3.3、顺序表的实现方式:动态分配
#define InitSize 10		//顺序表的初始长度
typedef struct{ElemType *data;	//指示动态分配数组的指针int MaxSize;	//顺序表的最大容量int length;		//顺序表的当前长度
}SeqList;		//顺序表的类型定义(动态分配方式)
3.4、顺序表的特点
  1. 随机访问,即可以在o(1)时间内找到第i个元素
  2. 存储密度高,每个节点只存储数据元素
  3. 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
3.5、顺序表的初始化与插入操作

初始化顺序表

#define MaxSize 50
typedef int ElemType; //让顺序表存储其他类型元素时,可以快速改变代码
//静态分配
typedef struct {ElemType data[MaxSize];int length; //顺序表长度
}SqList;

顺序表插入

//顺序表插入,因为L会改变,所以要引用
bool ListInsert(SqList &L,int pos,ElemType elemType){//判断pos是否合法if(pos <= 1 || pos >= L.length + 1){return false;}//如果顺序表满了,也不能进行插入if(L.length == MaxSize){return false;}//将元素依次往后面移动for (int i = L.length; i >= pos; i--) {L.data[i] = L.data[i-1];}L.data[pos-1] = elemType; //存入数据L.length++;       //顺序表长度+1return true;}

打印顺序表

//打印顺序表
void PrintList(SqList L){for (int i = 0; i < L.length; ++i) {printf("%3d",L.data[i]);}
}

在主函数中调用

//顺序表的初始化与插入
int main() {SqList L;  //定义一个顺序表bool result;L.data[0] = 1;  //放置元素L.data[1] = 2;L.data[2] = 3;L.length = 3; //设置顺序表元素为3result = ListInsert(L,2,2);if(true == result){printf("success");} else{printf("error");}PrintList(L);return 0;
}
3.6、顺序表的删除与查询

删除元素

//删除顺序表中的元素
bool ListDelete(SqList &L,int pos,ElemType &del){//判断删除元素位置是否合法if(pos < 1 || pos > L.length ){return false;}del = L.data[pos-1];  //保存删除元素的值//从当前下标开始,往前移动for (int i = pos;  i < L.length; i++) {L.data[i - 1] = L.data[i];}L.length--;return true;
}

查询元素

//查询元素位置
int LocateElem(SqList L,ElemType elemType){//遍历顺序表for (int i = 0; i < L.length; ++i) {if(L.data[i] == elemType){  //如果元素相同return i+1; //返回下标+1}}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Selenium web 网页测试自动化需要哪些技术?

引言&#xff1a; 在当今互联网时代&#xff0c;网页测试自动化成为了确保软件质量和提高效率的重要手段之一。Selenium是一种功能强大且广泛应用的工具&#xff0c;可用于实现网页测试自动化。本文将带您了解Selenium Web网页测试自动化所需的技术和步骤&#xff0c;以便您从…

生成式AI+跨境电商有哪些新玩法?店匠科技与亚马逊云科技已经在路上

导读 跨境电商一直是生成式AI最热门的应用领域之一。 生成式AI在跨境电商行业的核心应用场景有哪些&#xff1f;AI跨境电商又有哪些新玩法&#xff1f; 根据海关数据&#xff0c;2023年我国跨境电商进出口总额达2.38万亿元&#xff0c;增长15.6%。我国跨境电商主体已超10万家…

Set接口

Set接口的介绍 Set接口基本介绍 无序&#xff08;添加和取出的顺序不一致&#xff09;&#xff0c;没有索引不允许重复元素&#xff0c;所以最多包含一个nullJDK API中Set接口的实现类&#xff1a;主要有HashSet&#xff1b;TreeSet Set接口的常用方法 和List 接口一样&am…

【Linux】从零开始认识动静态库 - 静态库

送给大家一句话: 永不言弃&#xff0c;就是我的魔法&#xff01; ——阿斯塔《黑色四叶草》 ଘ(੭ˊ꒳​ˋ)੭✧ଘ(੭ˊ꒳​ˋ)੭✧ଘ(੭ˊ꒳​ˋ)੭✧ ଘ(੭ˊ꒳​ˋ)੭✧ଘ(੭ˊ꒳​ˋ)੭✧ଘ(੭ˊ꒳​ˋ)੭✧ ଘ(੭ˊ꒳​ˋ)੭✧ଘ(੭ˊ꒳​ˋ)੭✧ଘ(੭ˊ꒳​ˋ)੭✧ 从零…

案例研究|硬之城借助DataEase以数据驱动供应链精细化管理

深圳硬之城信息技术有限公司&#xff08;以下简称为“硬之城”&#xff09;成立于2015年&#xff0c;专注电子元件供应链领域&#xff0c;定位于电子产业供应链与智造平台。硬之城通过名为“Allchips”的集成式服务平台&#xff0c;为客户提供一站式的电子元件采购和供应链管理…

走进C++:C到C++的过渡

目录 什么是C呢&#xff1f; C的发展史 多了一些吃前来很香的“语法糖”。 语法糖一&#xff1a;命名空间 命名空间有个强大的功能 如何使用 语法糖二&#xff1a;缺省参数 语法糖三&#xff1a;函数重载 语法糖四&#xff1a;引用 引用传参 引用返回 引用和…

自托管站点监控工具 Uptime Kuma 搭建与使用

本文首发于只抄博客&#xff0c;欢迎点击原文链接了解更多内容。 前言 Uptime Kuma 是一个类似 Uptime Robot 的站点监控工具&#xff0c;它可以自托管在自己的 Nas 或者 VPS 上&#xff0c;用来监控各类站点、数据库等 监控类型&#xff1a;支持监控 HTTP(s) / TCP / HTTP(s…

服务丢在tomcat中启动war包,需要在tomcat中配置Java环境吗?

一般来说&#xff0c;部署在 Tomcat 上的 WAR 包启动时不需要在 Tomcat 中单独配置 Java 环境&#xff0c;因为 Tomcat 启动本身就需要依赖 Java 环境。以下是确保 Tomcat 正常运行与部署 WAR 包的基本步骤&#xff1a; 安装 Java 环境&#xff1a; 首先&#xff0c;确保你的系…

springboot增删改查

我的记录 RestController RequestMapping("/user") public class UserController {Autowiredprivate UserService userService;GetMapping("/list")public List<User> list(){return userService.list();}//新增PostMapping("/save")publi…

stm32 FOC系列 直流无刷6步换向控制原理

1、直流无刷电机的简介 直流无刷电机 (Brushless Direct Current Motor&#xff0c;简称 BLDCM) &#xff0c; 其最大的特点就是取消 了传统有刷电机中的电刷和换向器等结构。 因此线圈绕组不参与旋转&#xff0c;而是作为定子&#xff0c;永磁 体作为转子&#xff0c;所以需要…

vue3 antd-vue 超简单方式实现a-table跨页勾选

一、效果如下&#xff1a; 第一页勾选了2&#xff0c; 3&#xff0c; 4 翻到第三页勾选24&#xff0c; 25 回显&#xff0c;如比返回第一页的时候触发分页改变&#xff0c; 在映射中的第一页的数据给到a-table绑定的state.selectedRowKeys即可&#xff0c;如下方法 二、勾选思路…

luceda ipkiss教程 69:导出器件或者线路的三维模型

ipkiss 3.12版加入write_obj函数&#xff0c;可以直接输出器件的三维模型。 如&#xff0c;输出自定义的mmi的三维模型&#xff1a; 代码如下&#xff1a; from si_fab import all as pdk from ipkiss3 import all as i3class MMI1x2(i3.PCell):"""MMI with …

给网络镜像模式下的 WSL2 使用 127.0.0.1代理的方法

网络镜像模式下的WSL2虽然复制了宿主机windows的ip&#xff0c;但是仍然无法访问127.0.0.1的代理。经过调查&#xff0c;发现因为WSL2从应用商店下载而来&#xff0c;所以可能是UWP应用&#xff0c;所以需要用工具解除环回代理限制。

【吃透Java手写】4-Tomcat-简易版

【吃透Java手写】Tomcat-简易版-源码解析 1 准备工作1.1 引入依赖1.2 创建一个Tomcat的启动类 2 线程池技术回顾2.1 线程池的使用流程2.2 线程池的参数2.2.1 任务队列&#xff08;workQueue&#xff09;2.2.2 线程工厂&#xff08;threadFactory&#xff09;2.2.3 拒绝策略&…

idea运行SpringBoot项目爆红提示出现:Java HotSpot(TM) 64-Bit Server VM warning...让我来看看~

在运行SpringBoot项目的时候&#xff0c;发现总有这个警告提示出现&#xff0c;有点强迫症真的每次运行项目都很难受啊&#xff01;那么今天便来解决这个问题&#xff01; 先来看一下提示内容&#xff1a;Java HotSpot(TM) 64-Bit Server VM warning: Options -Xverify:none an…

智慧公厕:让厕所管理变得更智慧、高效、舒适!

公共厕所是城市的重要组成部分&#xff0c;但常常被忽视。它们的管理和养护往往面临着许多问题&#xff0c;例如卫生状况不佳、环境畏畏缩缩、设施老旧等。为了解决这些问题&#xff0c;智慧公厕应运而生。智慧公厕是一种全方位的应用解决方案&#xff0c;将科技与公共厕所管理…

centos安装mysql-client

直接安装&#xff1a; yum install mysql-community-client报了错误No package mysql-community-client available. 原因&#xff1a;CentOS/RHEL系统默认的软件源中并不包含MySQL软件包&#xff0c;需要通过添加第三方存储库来获取MySQL相关软件 添加源 安装MySQL官方的Yum…

Box86源码解读记录

1. 背景说明 Github地址&#xff1a;https://github.com/ptitSeb/box86 官方推荐的视频教程&#xff1a;Box86/Box64视频教程网盘 2. 程序执行主体图 Box86版本: Box86 with Dynarec v0.3.4 主函数会执行一大堆的初始化工作&#xff0c;包括但不限于&#xff1a;BOX上下文 …

docker端口映射成功,docker端口不生效的问题解决,外界无法访问docker映射端口

docker端口映射不生效的问题解决 问题 使用docker run -p 88848:8848后&#xff0c;显示容器启动正常&#xff0c;并且使用docker logs –f xxx能够看到容器可以正常启用&#xff0c;docker ps 可以看到容器启动成功&#xff0c;并且端口已经映射,但是在浏览器访问相关地址&am…

05-树9 Huffman Codes

05-树9 Huffman Codes &#xff08;30分&#xff09; 题目描述 In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”, and hence printed his name in the history of computer science. As a professor who gives…