网站建设的总结/制作自己的网站
线性表
定义
线性表是具有相同数据类型的N(N>=0)个元素的有限序列,其中N为表长,当N=0时线性表是一张空表。
线性表的逻辑特征:每个非空的线性表都有一个表头元素和表尾元素,中间的每个元素有且仅有一个直接前驱,有且仅有一个直接后继。
线性表是一种逻辑结构,表示元素之间一对一相邻的关系。顺序表(数组)和链表是指存储结构,两者属于不同的层面。
线性表的基本操作
基本操作的实现取决于采用哪种存储结构,存储结构不同,算法实现也不同,比如底层采用数据实现和链表实现,对应的代码不一样,但在上层实现算法逻辑时不关心底层具体实现,上述方法名可以直接作为伪代码使用。
线性表的顺序表示
(1)顺序表定义
# define MaxSize 50 // 定义线性表的最大长度typedef int ElemType;typedef struct{ElemType data[MaxSize] ; // 顺序表的元素int length ; // 顺序表的当前长度} SqList; // 别名
线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元,依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表可以是静态分配的数组,也可以是动态分配的数组。如果采用动态分配,就是在使用时按照实际大小申请空间。
#define InitSize 100typedef struct {ElemType *data ; // 指示动态分配数组的指针int MaxSize , length ; // 数组的最大容量和当前个数}SeqList; // 动态分配数组顺序表的类型定义C语言初始化:L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);C++初始化: L.data = new ElemType[InitSize] ;
注意:动态分配并不是链式存储,同样还是属于顺序存储结构,其物理结构没有变化,依然是随机存取方式,只是分配的空间大小可以在运行时决定。
(2)顺序表的特点
顺序表最主要的特点是:随机访问,即通过首地址和元素序号可以在O(1)时间内找到指定的元素
顺序表的存储密度高,每个结点只存储数据元素,相对于链表来说没有指针域。
顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动元素。
顺序表基本操作
有效性校验、边界检查:
如下面代码的“判断 i 的范围是否有效”。在函数体前面,主代码运行之前,对数据的有效性进行检查,比如是否为空、是否越界等。体现代码的健壮性,完整性,在考试时如果能多这一步并加上注释,是加分项。
(1)顺序表的插入代码实现
// 本算法实现将元素 e 插入到顺序表 L 中第 i 个位置
bool ListInsert( SqList &L , int i , ElemType e){if ( i < 1 || i > L.length +1 ){ // 判断 i 的范围是否有效return false; }if ( L.length >= MaxSize ){ // 当前存储空间已满,不能插入return false;}//有效性检查for( int j = L.length ; j >= i : j--){ //将 第 i 个元素及之后的元素后移L.data[ j ] = L.data[ j-1 ] ;}L.data[ i -1 ] = e; // 在位置 i 处放入 eL.length++; // 线性表的长度 加 1return true;
}
插入算法的平均时间复杂度为O(N)。
最好情况:在表尾插入(即 i = n + 1 ),元素移动语句将不执行,时间复杂度为 O(1) 。
最坏情况:在表头插入(即 i = 1 ),元素移动语句将执行 n 次,时间复杂度为 O( n ) 。
(2)顺序表的删除操作代码
// 本算法实现删除顺序表 L 中第 i 个位置的元素
bool ListDelete( SqList &L , int i , int &e ) {if( i < 1 || i > L.length ){ // 判断 i 的范围是否有效return false ;}e = L.data[ i -1 ] ; // 将被删除的元素赋值给 efor( int j = i ; j < L.length ; j++ ){ // 将第 i 个位置之后的元素前移L.data[ j -1 ] = L.data[ j ]}L.length--; // 线性表的长度减 1return true;
}
最好情况:删除表尾元素(即 i = n),无须移动元素,时间复杂度为 O(1)。
最坏情况:删除表头元素(即 i = 1),需要移动一个元素外的所有元素,时间复杂度为 O(n) 。
同理删除操作的平均时间复杂度也是O(N)
(3)按值查找,返回位序。
//本算法实现查找顺序表中值为 e 的元素,如果查找成功,返回元素位序,否则返回 0
int LocateElem( SqList L , ElemType e){
int i ;
for( i = 0 ; i < L.length ; i++){if( L.data[ i ] == e){return i +1 ; // 下标为 i 的元素值等于 e ,返回其位序 i + 1}return 0; //退出循环,说明查找失败
}
最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为 O(1) 。
最坏情况:查找的元素在表尾(或不存在)时,需要比较 n 次,时间复杂度为 O(n)。
因此,线性表按值查找算法的平均时间复杂度为 O(n) 。
(4)按下标查找、随机访问。
给定下标之后(或给定取第几个元素)可以直接通过下标访问l.data[i],l.data[i-1];因此随机访问的时间复杂度为O(1)。
下一篇文章介绍顺序表的链式表示
相关文章:

数据结构知识点总结-线性表(1)-线性表的定义、基本操作、顺序表表示
线性表 定义 线性表是具有相同数据类型的N(N>0)个元素的有限序列,其中N为表长,当N0时线性表是一张空表。 线性表的逻辑特征:每个非空的线性表都有一个表头元素和表尾元素,中间的每个元素有且仅有一个直…...

Spring Boot 手写starter!!!
原因:为什么要手写starter??? 原因:简化功能。 实例:以分页为例:写一个starter。 1.首先定义一个PageX注解。 Target({ElementType.METHOD}) Retention(RetentionPolicy.RUNTIME) Documented p…...

移动端自动化常用的元素定位工具 介绍
在移动端自动化测试和开发中,元素定位是非常关键的一步。以下是一些常用的工具和技术来帮助开发者或测试工程师在移动设备上定位元素: 1. **UiAutomator**: - **UiAutomator** 是 Android 官方提供的自动化测试框架。它可以用来编写测试脚本&…...

问题:Spark SQL 读不到 Flink 写入 Hudi 表的新数据,打开新 Session 才可见
博主历时三年精心创作的《大数据平台架构与原型实现:数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行,点击《重磅推荐:建大数据平台太难了!给我发个工程原型吧!》了解图书详情,…...

数学建模资料分享
1. 往年各赛题的优秀论文 可以用来参考一下论文是怎么写的。参考论文的结构,格式,思路等等。 链接:https://pan.baidu.com/s/1WG2t4-x9MjtaSgkq4ue5AQ?pwdnlzx 提取码:nlzx --来自百度网盘超级会员V4的分享 2.论文模板 链接&a…...

应用配置管理
一、Pod 配置管理 可变配置用 ConfigMap; 敏感信息用 Secret; 身份认证用 ServiceAccount 这几个独立的资源来实现的; 资源配置用 Resources; 安全管控用 SecurityContext; 前置校验用 InitContainers 这几个在 …...

This dependency was not found解决方法
问题如上(前端代码),我是引用js文件出的问题,无法找到api/userManage模块。 解决:没感觉哪有问题,把后面加了个/,就解决了,代表src目录,应该是目录和目录之间应该有/作为分割:...

基于SpringBoot的停车场管理系统
基于SpringBootVue的停车场管理系统的设计与实现~ 开发语言:Java数据库:MySQL技术:SpringBootMyBatis工具:IDEA/Ecilpse、Navicat、Maven 系统展示 前台首页 停车位 个人中心 管理员界面 摘要 摘要:随着城市化进程的…...

SQL库操作
1、创建数据库 概念 创建数据库:根据项目需求创建一个存储数据的仓库 使用create database 数据库名字创建 数据库层面可以指定字符集:charset/character set 数据库层面可以指定校对集:collate 创建数据库会在磁盘指定存放处产生一个文件夹 创建语法 create …...

物麒平台根据入耳出耳状态使能或禁止触摸按键实现方法
是否需要申请加入数字音频系统研究开发交流答疑群(课题组)?可加我微信hezkz17, 本群提供音频技术答疑服务,+群赠送语音信号处理降噪算法,蓝牙耳机音频,DSP音频项目核心开发资 料, 1 消息发送 2 消息处理 3 宏开关 4 代码 #include "app_main.h" #include &q…...

CAS5.3使用JPA实现动态注册服务
cas同时支持cas协议和OAuth2协议,官方默认是通过扫描json文件的形式注册客户端服务,但是此种方式需要重启服务才能生效,此次我们将使用JPA来完美实现动态注册服务,如果不知道cas如何部署,可以擦看之前的文章 cas-client基于CAS协议客户端搭建-CSDN博客 cas-server5.3自定义密…...

unity ui界面优化
优化一个比较复杂的界面,里面有多个rt和组件。 在初次打开这个界面的时候会发生1s多的卡顿,还是非常严重的。 分析 通过profiler分析 1.打开界面时卡顿。 分析:除了update和dotween相关逻辑,主要在于打开时的lua function调用…...

mysql-MVCC
一、基础概念 1. MVCC的含义 MVCC (Multiversion Concurrency Control),即多版本并发控制技术,它是通过读取某个时间点的快照数据, 来降低并发事务冲突而引起的锁等待, 从而提高并发性能的一种机制. MVCC 的实现,是通过保存数据…...

Sqli-labs靶场第9关详解[Sqli-labs-less-9]
Sqli-labs-Less-9 前言: SQL注入的三个条件: ①参数可控;(从参数输入就知道参数可控) ②参数过滤不彻底导致恶意代码被执行;(需要在测试过程中判断) ③参数带入数据库执行。&#…...

第3.5章:StarRocks数据导入——Broker Load
注:本篇文章阐述的是StarRocks-3.2版本的Broker Load导入机制 一、概述 Broker Load导入方式支持从HDFS类的外部存储系统(例如:HDFS、阿里OSS、腾讯COS、华为云OBS等),支持Parquet、ORC、CSV、及 JSON 四种文件格式&a…...

Linux之ACL权限chmod命令
一. chmod命令 chmod命令来自英文词组change mode的缩写,其功能是改变文件或目录权限的命令。默认只有文件的所有者和管理员可以设置文件权限,普通用户只能管理自己文件的权限属性。 设置权限时可以使用数字法,亦可使用字母表达式࿰…...

HBuilderX的特点
轻巧 仅10余M的绿色发行包(不含插件)极速 不管是启动速度、大文档打开速度、编码提示,都极速响应 C的架构性能远超Java或Electron架构vue开发强化 HBuilderX对vue做了大量优化投入,开发体验远超其他开发工具 详见小程序支持 国外开发工具没有对中国的小程…...

CrossOver虚拟机软件2024有哪些功能?最新版本支持哪些游戏?
CrossOver由codewaver公司开发的类虚拟机软件,目的是使linux和Mac OS X操作系统和window系统兼容。CrossOver不像Parallels或VMware的模拟器,而是实实在在Mac OS X系统上运行的一个软件。CrossOvers能够直接在Mac上运行Windows软件与游戏,而不…...

Android LinearLayout 如何让子元素靠下居中对齐 center bottom
Android LinearLayout 如何让子元素靠下居中对齐 center bottom 首先你需要知道两个知识点: android:layout_gravity 指定的是当前元素在父元素中的位置android:gravity 指定的是当前元素子元素的排布位置 比如: 有这么一个布局,我需要让…...

物体检测-系列教程16:YOLOV5 源码解析6(马赛克数据增强函数load_mosaic)
😎😎😎物体检测-系列教程 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 点我下载源码 9、load_mosaic函数 Mosaic(马赛克)数据增强:将四张不…...

星河做市基金会全球DAO社区启动,为数字货币市场注入新活力
2024年的数字货币市场即将迎来一次重要的历史性时刻 — 比特币减半,这四年一次的事件将成为全球数字资产市场的焦点,预示着新一轮的牛市浪潮即将到来。在这个关键时刻,星河做市基金会展现出其作为区块链行业领先市值管理公司的独特魅力。 GA…...

QT Widget自定义菜单
此文以设置QListWidget的自定义菜单为例,其他继承于QWidget的类也都可以按类似的方法去实现。 1、ui文件设置contextMenuPolicy属性为CustomContextMenu 2、添加槽函数 /*** brief onCustomContextMenuRequested 右键弹出菜单* param pos 右键的坐标*/void onCusto…...

UnityWebGL 设置全屏
这是Unity导出Web默认打开的页面尺寸 修改后效果 修改 index.html 文件 1.div元素的id属性值为"unity-container",宽度和高度都设置为100%,意味着该div元素将占据整个父容器的空间。canvas元素的id属性值为"unity-canvas"ÿ…...

100224. 分割数组
说在前面 🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。 题目描述 给你一个长度为 偶数 的整数数组 nums 。你需要将这个数组分割成 nums1 和 nums2 两部分&am…...

WSL2配置Linux、Docker、VS Code、zsh、oh my zsh(附Docker开机自启设置)
0. 写在前面 本篇笔记来自于UP主麦兜搞IT的合集视频Windows10开发环境搭建中的部分内容 1. 安装WSL2 按照微软官方文档进行操作,当然也可以直接wsl --install 也可以按照 旧版手动安装的步骤 来进行操作 选择安装的是Ubuntu 20.04 LTS 注:WSL默认安装…...

深度学习基础(四)医疗影像分析实战
之前的章节我们初步介绍了卷积神经网络(CNN)和循环神经网络(RNN): 深度学习基础(三)循环神经网络(RNN)-CSDN博客文章浏览阅读1.2k次,点赞17次,收…...

ChatGPT调教指南 | 咒语指南 | Prompts提示词教程(一)
在我们开始探索人工智能的世界时,了解如何与之有效沉浸交流是至关重要的。想象一下,你手中有一把钥匙,可以解锁与OpenAI的GPT模型沟通的无限可能。这把钥匙就是——正确的提示词(prompts)。无论你是AI领域的新手,还是希望优化与大型语言模型交流的老手,掌握如何精确使用…...

LeetCode | 两数相加 C语言
Problem: 2. 两数相加 文章目录 思路解题方法Code一些感想 思路 主要是一一相加和逆序的方式存储 先说逆序储存,看下图 我们先声明出指针p和指针q,还有指针head(主要用于return上而已),然后进行一系列操作,…...

【Spring MVC】处理器映射器:AbstractHandlerMethodMapping源码分析
目录 一、继承体系 二、HandlerMapping 三、AbstractHandlerMapping 四、AbstractHandlerMethodMapping 4.1 成员属性 4.1.1 MappingRegistry内部类 4.2 AbstractHandlerMethodMapping的初始化 4.3 getHandlerInternal()方法:根据当前的请求url,…...

网络编程知识整理
目录 1.1 引言 1.2 分层 1.3 TCP/IP的分层 1.4 互联网的地址 1.5 域名服务 1.6 封装 1.7 分用 1.8 端口号 1.1 引言 很多不同的厂家生产各种型号的计算机,它们运行完全不同的操作系统,但 T C P / I P协议族允许它们互相进行通信。这一点很让人感…...