数据结构--线性表（顺序结构）

1.线性表的定义和基本操作

1.1线性表以及基本逻辑

1.1.1线性表

（1）n(>=0)个数据元素的有限序列，记作（a1,a2,...an），其中ai是线性表中的数据元素，n是表的长度。

（2）ai是线性表中“第i个”元素在线性表中的位序。

注意：数组下标从0（a[0]）开始，位序从1开始.

 1.1.2逻辑特征（n>0）

存在唯一的一个被称为“第一个”的数据元素。

存在唯一的一个被称为“最后一个”的数据元素。

除了第一个元素以外，其他元素均只有一个直接前驱。

除了最后一个元素外，其他元素均只有一个直接后继。

1.2线性表的基本操作

InitList(&L)              //创建一个新的线性表L

ListEmpty(L)           //判断L是否为空

ListLength(L)          //求L的长度

GetElem(L,i,&e)     //取i位置数据元素的值

ClearList(&L)          //将L置为空表

ListInsert(&L,i,e)     //在i位置插入值为e的数据元素

ListDelete(&L,i,&e) //删除i位置的元素e

1.ListInsert(&L,i,e)  ，传值

2.ListDelete(&L,i,&e)，传引用

3.ListDelete(&L,i,*e)，传指针

1.形参改变->不会影响实参

2.3.形参改变->会影响实参（传引用，传指针）

 下面用一张图来介绍形参和实参的区别：（by 通义千问）

传引用（&）适用场景：

1.需要函数修改原始数据。

2.对于大型数组或对象，为了节省内存开销和提升运算效率，使用引用传递。

一句话：对参数的修改结果要“带回来”。 

2.线性表的顺序表示

2.1线性表和顺序表的定义

（1）线性表：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。

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

2.2静态分配和动态分配

2.2.1静态分配

#define MAX 10
int arr[MAX];
int n;         //数据元素个数小于n个

结构体进行封装：

#define MAX 100
typedef struct
{ElemType elem[MAX];int n;
}Sqlist;

2.2.2动态存储

（1）动态申请和释放内存空间

（2）C语言--malloc,free函数

L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize)
//malloc函数返回一个指针，需要用“(ElemType *)”强制类型转化为自己定义的数据元素类型指针

2.2.3顺序表基本操作实现

1.初始化顺序表InitList_Sq(&L)

操作结果：构造一个空的顺序表L.

Status InitList_Sq(SqList&L)       // 定义一个函数名为 InitList_Sq 的函数，参数是对 SqList 类型的引用 L，返回类型为 Status（这里 Status 可能是一个自定义的表示状态的类型）
{L.elem=(ElemType*)malloc(initial_size*sizeof(ElemType));  // 为 L 的 elem 属性分配一块内存空间，大小为 initial_size 个 ElemType 类型元素所需的空间，并将其地址转换为 ElemType*类型赋给 L.elemif(!L.elem)                    // 如果分配内存失败（L.elem 为假，即内存分配不成功得到的是 null 指针等情况）exit(OVERFLOW);            // 退出程序并表示存储空间分配失败（OVERFLOW 可能是一个表示溢出或错误的常量）L.length=0;                    // 将顺序表 L 的当前长度设置为 0L.listsize=initial_size;       // 将顺序表 L 的初始容量设置为 initial_sizereturn 0;                      // 返回一个状态值（这里可能表示成功初始化）
}

下面是对顺序表中长度和容量的解释： 

在顺序表（Sequential List）中：

 

一、长度（length）

 

指的是顺序表中当前实际存储的元素个数。

 

例如，如果有一个顺序表存储了 5 个整数，那么这个顺序表的长度就是 5。随着向顺序表中添加或删除元素，长度会相应地发生变化。

 

二、容量（listsize）

 

指的是顺序表预先分配的能够存储元素的最大空间大小。

 

例如，一开始创建顺序表时可能分配了一块可以存储 10 个整数的连续内存空间，那么此时这个顺序表的容量就是 10。当顺序表中的元素个数达到容量时，如果要继续添加元素，通常需要进行扩容操作（重新分配更大的连续内存空间）。而如果顺序表中的元素个数远小于容量，那么就存在一部分未被使用的内存空间。

2.销毁顺序表DestroyList_Sq(&L):

释放L所占用的内存空间

void DestroyList_Sq(SqList &L)
{free(L.elem); // 释放顺序表 L 的存储数据的内存空间。free 函数用于释放由 malloc、calloc 或 realloc 等函数分配的动态内存。L.elem = NULL; // 将 L 的 elem 指针设置为 NULL，避免出现悬空指针。L.length = 0; // 将顺序表的长度设置为 0，表示表中没有元素。L.listsize = 0; // 将顺序表的容量设置为 0。
}

3.判定是否为空表 ListEmpty_Sq(L):

若L为空表，返回1，否则返回0；

int ListEmpty_Sq(SqList L)
{if (L.length==0)return 1;else return 0;

4.输出顺序表 DispList_Sq(L):

操作结果：当L不为空时，顺序显示L中各个元素的值。

Status DispList_Sq(SqList L)
{if (ListEmpty_Sq(L))return ERROR;// 如果顺序表为空（通过调用 ListEmpty_Sq 函数判断），则返回 ERROR（可能是一个表示错误的状态码）。for(i=0;i<=L-1;i++){print(L.elem[i]);}// 如果顺序表不为空，遍历顺序表，从第一个元素（下标为 0）开始，直到最后一个元素（下标为 L-1），逐个打印顺序表中的元素。return OK;// 遍历完成后，返回 OK（可能是一个表示成功的状态码）。
}

5.插入数据元素  ListInsert_Sq(&L,i,e):

操作结果：在顺序表L的第i个位置前插入新元素e. 

ListInsert_Sq(SqList &L, int i, ElemType e) 
{if (i < 1 || i > L.length + 1) {return ERROR;}// 判断插入位置 i 是否合法，i 应该在 1 到（当前顺序表长度 + 1）之间，否则返回错误状态码 ERROR。if (L.length >= L.listsize) {newbase = (ElemType*)malloc(L.elem,(L.listsize + ElemNumber)*sizeof(ElemType));L.elem = newbase;L.listsize += ElemNumber;}// 如果当前顺序表中已存储的元素个数（L.length）等于或超过了顺序表的容量（L.listsize），则进行扩容操作。// 分配一块新的内存空间，大小为原来的容量加上 ElemNumber 个 ElemType 类型元素所需的空间，然后将新分配的内存地址赋给 L.elem，并更新顺序表的容量 L.listsize。for (j = L.length; j >= i; j--) {L.elem[j] = L.elem[j - 1];}// 将插入位置 i 及之后的元素向后移动一位。L.elem[i - 1] = e;// 在插入位置 i 处放入新元素 e。++L.length;// 顺序表长度加一。return 1;// 返回一个表示成功的状态码（这里是 1）。
}

时间复杂度：

-最好情况：新元素插到表尾，不需要移动元素i=n+1,循环0次，T(n)=O(1);

-最坏情况：新元素插到表头，需要将原有的n个元素全部向后移动i=1,循环n次，T(n)=O(n);

-平均情况：,新元素插入到任意一个位置概率相同，需要的时间是n/2，考虑到时间复杂度量级，T(n)=O(n).  

6.删除数据元素 ListDelete_Sq(&L,i,&e):

操作结果：删除顺序表L中的第i个元素，用引用变量e返回删除的元素。

ListInsert_Sq(SqList &L, int i, ElemType &e) 
{if (i < 1 || i > L.length) {return ERROR;}// 判断插入位置 i 是否合法。i 应该在 1 到顺序表的当前长度之间，如果不合法则返回错误状态码 ERROR。e = L.elem[i - 1];// 将顺序表中位置 i 处的元素赋值给参数 e。for (j = i; j < L.length; j++) {L.elem[j - 1] = L.elem[j];}// 从位置 i 开始，将后面的元素依次向前移动一位。--L.length;// 顺序表的长度减一，表示删除了一个元素。return 1;// 返回一个表示成功的状态码（这里是 1）。
}

时间复杂度：

-最好情况：T(n)=O(1);

-最坏情况：T(n)=O(n);

-平均情况：T(n)=O(n).  

 7.按位查找操作 GetElem(L,i):

操作结果：获取表L中的第i个位置元素的值。

ElemType GetElem(SeqList L,int i)
{return L.data[i-1];
}

 时间复杂度：O（1）

 8.按值查找操作 LocateElem(L,e):

操作结果：在表L中查找具有给定关键字值的元素（第一个）。

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ElemType e)
{for(int i=0;i<=L.length-1;i++){if(L.data[i]==e){return i+1;}}return 0;
}

时间复杂度：

-最好情况：目标元素子啊表头，循环1次，T(n)=O(1);

-最坏情况：目标元素在表尾，循环n次，T(n)=O(n);

-平均情况：目标元素出现在任何一个位置的概率相同，T(n)=O(n).  

 下面是链表，敬请期待...

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

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

相关文章

4个顶级的大模型推理引擎

4个顶级的大模型推理引擎

LLM 在文本生成应用中表现出色&#xff0c;例如具有高理解度和流畅度的聊天和代码完成模型。然而&#xff0c;它们的庞大规模也给推理带来了挑战。基本推理速度很慢&#xff0c;因为 LLM 会逐个生成文本标记&#xff0c;需要对每个下一个标记进行重复调用。随着输入序列的增长&…
阅读更多...
ElasticSearch 备考 -- 备份和恢复

ElasticSearch 备考 -- 备份和恢复

一、题目 备份集群下的索引 task&#xff0c;存储快照名称为 snapshot_1 二、思考 这个涉及的是集群的备份&#xff0c;主要是通过创建快照&#xff0c;涉及到以下2步骤 Setp1&#xff1a;注册一个备份 snapshot repository Setp2&#xff1a;创建 snapshot 可以通过两种方…
阅读更多...
MindSearch 部署到Github Codespace 和 Hugging Face Space

MindSearch 部署到Github Codespace 和 Hugging Face Space

conda init后需要重开终端&#xff0c;不然一键复制会导致后续pip install会安装错环境 还是报错 ImportError: cannot import name AutoRegister from class_registry (/opt/conda/envs/mindsearch/lib/python3.10/site-packages/class_registry/__init__.py)pip install --…
阅读更多...
【技术分析】嘉楠科技SoC芯片K230

【技术分析】嘉楠科技SoC芯片K230

概述 K230是嘉楠科技Kendryte系列AIoT芯片中的最新一代SoC芯片&#xff0c;该芯片采用全新的多异构单元加速计算架构&#xff0c;集成的玄铁C908具有2个高能效RISCV计算核心&#xff0c;内置新一代KPU&#xff08;Knowledge Process Unit&#xff09;智能计算单元&#xff0c;…
阅读更多...
Unity初识+面板介绍

Unity初识+面板介绍

Unity版本使用 小版本号高&#xff0c;出现bug可能性更小&#xff1b;一台电脑可以安装多个版本的Unity&#xff0c;但是需要安装在不同路径&#xff1b;安装Unity时不能有中文路径&#xff1b;Unity项目路径也不要有中文。 Scene面板 相当于拍电影的片场&#xff0c;Unity程…
阅读更多...
Go基础学习11-测试工具gomock和monkey的使用

Go基础学习11-测试工具gomock和monkey的使用

文章目录 基础回顾MockMock是什么安装gomockMock使用1. 创建user.go源文件2. 使用mockgen生成对应的Mock文件3. 使用mockgen命令生成后在对应包mock下可以查看生成的mock文件4. 编写测试代码5. 运行代码并查看输出 GomonkeyGomonkey优势安装使用对函数进行monkey对结构体中方法…
阅读更多...
Chat登录时出现SSO信息出错的解决方法

Chat登录时出现SSO信息出错的解决方法

目录 1. 问题所示2. 问题所示3. 解决方法 1. 问题所示 此贴主要是总结回顾&#xff0c;对此放置在运维专栏 出现如下问题&#xff0c;很懵&#xff0c;以为是节点挂了还是网址蹦了 一直刷新&#xff0c;登录之后就出现这个问题 2. 问题所示 对于SSO&#xff0c;也就是单点登…
阅读更多...
深度学习项目----用LSTM模型预测股价(包含LSTM网络简介，代码数据均可下载)

深度学习项目----用LSTM模型预测股价(包含LSTM网络简介，代码数据均可下载)

前言 前几天在看论文&#xff0c;打算复现&#xff0c;论文用到了LSTM&#xff0c;故这一篇文章是小编学LSTM模型的学习笔记&#xff1b;LSTM感觉很复杂&#xff0c;但是结合代码构建神经网络&#xff0c;又感觉还行&#xff1b;本次学习的案例数据来源于GitHub&#xff0c;在…
阅读更多...
4.4章节python中循环结构得互相嵌套：常用于属于图形（长方形、三角形、菱形）

4.4章节python中循环结构得互相嵌套：常用于属于图形（长方形、三角形、菱形）

一、定义和注意事项 在Python中&#xff0c;循环结构&#xff08;如for循环和while循环&#xff09;可以互相嵌套。嵌套循环意味着一个循环内部包含另一个循环。这在处理多维数据或需要执行多次迭代的任务时非常有用。 注意&#xff1a; 1.缩进&#xff1a;在Python中&…
阅读更多...
实施威胁暴露管理、降低网络风险暴露的最佳实践

实施威胁暴露管理、降低网络风险暴露的最佳实践

随着传统漏洞管理的发展&#xff0c;TEM 解决了因攻击面扩大和安全工具分散而产生的巨大风险。 主动式 TEM 方法优先考虑风险并与现有安全工具无缝集成&#xff0c;使组织能够在威胁被有效利用之前缓解威胁。 为什么威胁暴露管理 (TEM) 在现代网络安全策略中变得至关重要&…
阅读更多...
商家营销工具架构升级总结

商家营销工具架构升级总结

今年以来&#xff0c;商家营销工具业务需求井喷&#xff0c;需求数量多且耗时都比较长&#xff0c;技术侧面临很大的压力。因此这篇文章主要讨论营销工具前端要如何应对这样大规模的业务需求。 问题拆解 我们核心面对的问题主要如下&#xff1a; 1. 人力有限 我们除了要支撑存量…
阅读更多...
C语言 | Leetcode C语言题解之题451题根据字符出现频率排序

C语言 | Leetcode C语言题解之题451题根据字符出现频率排序

题目&#xff1a; 题解&#xff1a; #define HASH_FIND_CHAR(head, findint, out) HASH_FIND(hh, head, findint, sizeof(char), out) #define HASH_ADD_CHAR(head, intfield, add) HASH_ADD(hh, head, intfield, sizeof(char), add)struct HashTable {char key;int val;UT_ha…
阅读更多...
《数据密集型应用系统设计》笔记——第二部分 分布式数据系统（ch5-9）

《数据密集型应用系统设计》笔记——第二部分 分布式数据系统（ch5-9）

第5章 数据复制 目的&#xff1a; 地理位置更近&#xff0c;降低延迟故障冗余提高读吞吐量 主节点与从节点&#xff08;主从复制&#xff09; 主从复制&#xff1a; 写请求发送给主节点&#xff0c;主节点将新数据写入本地存储&#xff1b;主节点将数据更改作为复制的日志发送…
阅读更多...
SAP学习笔记 - Basis01 - 创建Client ，拷贝Client

SAP学习笔记 - Basis01 - 创建Client ，拷贝Client

最近工作当中用到了Client间数据移送的内容&#xff0c;想把自己的虚机给弄两个Client。 最后也没完全弄成&#xff0c;先把过程整理一下&#xff0c;以后有空接着弄。 目录 1&#xff0c;SALE - 新建逻辑系统 2&#xff0c;SCC4 - 分配Client到集团 3&#xff0c;RZ10 - 取…
阅读更多...
python-FILIP/字符串p形编码/数字三角形

python-FILIP/字符串p形编码/数字三角形

一&#xff1a;FILIP 题目描述 给你两个十进制正整数 a,b​&#xff0c;输出将这两个数翻转后的较大数。 「翻转」在本题中的定义详见「说明 / 提示」部分。输入 第一行&#xff0c;两个十进制正整数 a,b。输出 第一行&#xff0c;a 和 b 翻转后的较大数。样例输入1 734 893 样…
阅读更多...
Microsoft Edge 五个好用的插件

Microsoft Edge 五个好用的插件

&#x1f423;个人主页 可惜已不在 &#x1f424;这篇在这个专栏 插件_可惜已不在的博客-CSDN博客 &#x1f425;有用的话就留下一个三连吧&#x1f63c; 目录 Microsoft Edge 一.安装游览器 ​编辑 二.找到插件商店 1.打开游览器后&#xff0c;点击右上角的设置&#…
阅读更多...
【深度学习基础模型】深度残差网络（Deep Residual Networks, DRN）详细理解并附实现代码。

【深度学习基础模型】深度残差网络（Deep Residual Networks, DRN）详细理解并附实现代码。

【深度学习基础模型】深度残差网络&#xff08;Deep Residual Networks, DRN&#xff09;详细理解并附实现代码。 【深度学习基础模型】深度残差网络&#xff08;Deep Residual Networks, DRN&#xff09;详细理解并附实现代码。 文章目录 【深度学习基础模型】深度残差网络&a…
阅读更多...
Python小示例——质地不均匀的硬币概率统计

Python小示例——质地不均匀的硬币概率统计

在概率论和统计学中&#xff0c;随机事件的行为可以通过大量实验来研究。在日常生活中&#xff0c;我们经常用硬币进行抽样&#xff0c;比如抛硬币来决定某个结果。然而&#xff0c;当我们处理的是“质地不均匀”的硬币时&#xff0c;事情就变得复杂了。质地不均匀的硬币意味着…
阅读更多...
Spring Boot中线程池使用

Spring Boot中线程池使用

说明&#xff1a;在一些场景&#xff0c;如导入数据&#xff0c;批量插入数据库&#xff0c;使用常规方法&#xff0c;需要等待较长时间&#xff0c;而使用线程池可以提高效率。本文介绍如何在Spring Boot中使用线程池来批量插入数据。 搭建环境 首先&#xff0c;创建一个Spr…
阅读更多...
每日学习一个数据结构-树

每日学习一个数据结构-树

文章目录 树的相关概念一、树的定义二、树的基本术语三、树的分类四、特殊类型的树五、树的遍历六、树的应用场景 树的遍历一、前序遍历二、中序遍历三、后序遍历使用java代码实现遍历总结 树的相关概念 树是一种重要的非线性数据结构&#xff0c;在计算机科学中有着广泛的应用…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023