大话数据结构学习笔记-线性表(二)-顺序存储结构

2024-04-18 20:04
文章标签 学习 数据结构 笔记 结构 线性表 大话 顺序存储

本文主要是介绍大话数据结构学习笔记-线性表(二)-顺序存储结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。一般就是用一维数组来实现。

顺序存储结构定义

描述顺序存储结构的线性表需要以下三个属性
1)存储空间的起始位置:数组data。它的存储位置就是存储空间的存储位置
2)线性表的最大存储容量:数组长度MAX_SIZE
3)线性表的当前长度:length

结构代码如下

public class ArrayList<T>
{/// <summary>/// 存储空间初始分配量/// </summary>public const int MAX_SIZE = 20;/// <summary>/// 数组，存储数据元素/// </summary>private T[] _data;/// <summary>/// 线性表当前长度/// </summary>private int _length;
}

顺序存储结构的基本操作

初始化

工欲善其事必先利其器，如果要进行线性表的各种操作，首要任务肯定是要先创建一个线性表。
对于顺序存储的线性表来说，创建操作主要为以下两步
1)初始化数组，为数组分配MAX_SIZE的内存
2)初始化长度为0
初始化操作代码如下:

/// <summary>
/// 初始化一个线性表
/// </summary>
/// <returns>初始化后的线性表</returns>
public IList<T> Init()
{//1)初始化数组，为数组分配MAX_SIZE的内存_data = new T[MAX_SIZE];//2)初始化长度为0_length = 0;return this;
}

获取元素

对于线性表的顺序存储结构来说,如果我们要实现GetElem操作，其实就是将第i个位置的元素返回即可，对应代码中也就是返回data[i-1]。这里要注意返回之前要先判断位置i有没有超过当前线性表的长度。可分为以下两步:
1)如果获取元素的位置不合适(小于0或者大于当前线性表长度)，抛出异常
2)返回第i个位置的元素
获取元素操作代码如下:

/// <summary>
/// 获取第i个位置的元素
/// </summary>
/// <param name="i">元素的位置</param>
/// <returns>待获取元素</returns>
/// <exception cref="ArgumentException"></exception>
public T GetElem(int i)
{//1)如果获取元素的位置不合适(小于0或者大于当前线性表长度)，抛出异常if(i < 1 || i > _length){throw new ArgumentException("位置必须大于0，且必须小于等于当前线性表的长度");}//2)返回第i个位置的元素return _data[i-1];
}

插入操作

对于顺序存储存储线性表来说，插入操作主要是以下5步
1)如果插入的位置不合适(小于0或者大于当前线性表长度)，抛出异常
2)如果线性表长度大于等于数组长度，则抛出异常，或者动态扩容。
3)从最后一个位置元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
4)将要插入元素填入位置i处。
5)线性表当前长度+1
插入操作代码如下:

/// <summary>
/// 插入元素
/// </summary>
/// <param name="e">待插入元素</param>
/// <param name="i">插入的位置</param>
/// <exception cref="ArgumentException"></exception>
public void Insert(T e, int i)
{//1)如果插入的位置不合适(小于0或者大于当前线性表长度)，抛出异常if (i < 1 || i > _length){throw new ArgumentException("位置必须大于0，且必须小于等于当前线性表的长度");}//2)如果线性表长度大于等于数组长度，则抛出异常，或者动态扩容。if (_length >= _data.Length){T[] newData = new T[_data.Length * 2];for(int j=0;j<_length;j++){newData[j] = _data[j];}_data = newData;}//3)从最后一个位置元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。for (int j=_length-1;j>=i-1;j--){_data[j+1] = _data[j];}//4)将要插入元素填入位置i处。_data[i - 1] = e;//5)线性表当前长度+1_length++;
}

删除操作

顺序存储结构的线性表删除操作可分为以下几步:
1)如果删除的位置不合适(小于0或者大于当前线性表长度)，抛出异常。
2)取出删除元素。
3)从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。
4)线性表当前长度-1
5)返回删除元素
删除操作代码如下:

/// <summary>
/// 删除第i个位置的元素
/// </summary>
/// <param name="i">删除元素的位置</param>
/// <returns>删除的元素</returns>
/// <exception cref="ArgumentException"></exception>
/// <exception cref="Exception"></exception>
public T Delete(int i)
{//1)如果删除的位置不合适(小于0或者大于当前线性表长度)，抛出异常。if (i < 1 || i > _length){throw new ArgumentException("位置必须大于0，且必须小于等于当前线性表的长度");}if (_length == 0){throw new Exception("线性表为空");}//2)取出删除元素。T retEle = _data[i-1];//3)从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。for(int j=i;j<_length;j++){_data[j - 1] = _data[j];}//4)线性表当前长度-1_length--;//5)返回删除元素return retEle;}

定位元素操作

定位元素操作，就是定位要查找的元素在线性表中的位置，可分为以下几步:
1)从第一个元素开始遍历到最后一个元素，如果遍历的元素与要查找元素相等，则返回这个位置
2)如果整个遍历都没有返回，说明线性表中没有这个元素，返回0
查找元素操作代码如下:

/// <summary>
/// 定位元素
/// </summary>
/// <param name="e">要定位的元素</param>
/// <returns>定位元素的位置</returns>
public int LocateElem(T e)
{//1)从第一个元素开始遍历到最后一个元素，如果遍历的元素与要查找元素相等，则返回这个位置for (int i=0;i<_length;i++){if (_data[i].Equals(e)){return i+1;}}//2)如果整个遍历都没有返回，说明线性表中没有这个元素，返回0return 0;
}

其他操作

对于顺序存储的线性表来说，获取长度直接返回length即可;清空线性表就是将length置0;判断线性表是否为空就是判断length是否等于0。
线性表的剩余操作的代码如下:

/// <summary>
/// 清空线性表
/// </summary>
public void Clear()
{_length = 0;
}/// <summary>
/// 判断线性表是否为空
/// </summary>
/// <returns>为空返回true,否则返回false</returns>
public bool Empty()
{return _length == 0;
}/// <summary>
/// 获取线性表的长度
/// </summary>
/// <returns>线性表的长度</returns>
public int Length()
{return _length;
}

完整代码

namespace DataStructLearning.List;public class ArrayList<T> : IList<T>
{/// <summary>/// 存储空间初始分配量/// </summary>public const int MAX_SIZE = 20;/// <summary>/// 数组，存储数据元素/// </summary>private T[] _data;/// <summary>/// 线性表当前长度/// </summary>private int _length;/// <summary>/// 清空线性表/// </summary>public void Clear(){_length = 0;}/// <summary>/// 判断线性表是否为空/// </summary>/// <returns>为空返回true,否则返回false</returns>public bool Empty(){return _length == 0;}/// <summary>/// 获取线性表的长度/// </summary>/// <returns>线性表的长度</returns>public int Length(){return _length;}/// <summary>/// 定位元素/// </summary>/// <param name="e">要定位的元素</param>/// <returns>定位元素的位置</returns>public int LocateElem(T e){//1)从第一个元素开始遍历到最后一个元素，如果遍历的元素与要查找元素相等，则返回这个位置for (int i=0;i<_length;i++){if (_data[i].Equals(e)){return i+1;}}//2)如果整个遍历都没有返回，说明线性表中没有这个元素，返回0return 0;}/// <summary>/// 删除第i个位置的元素/// </summary>/// <param name="i">删除元素的位置</param>/// <returns>删除的元素</returns>/// <exception cref="ArgumentException"></exception>/// <exception cref="Exception"></exception>public T Delete(int i){//1)如果删除的位置不合适(小于0或者大于当前线性表长度)，抛出异常。if (i < 1 || i > _length){throw new ArgumentException("位置必须大于0，且必须小于等于当前线性表的长度");}if (_length == 0){throw new Exception("线性表为空");}//2)取出删除元素。T retEle = _data[i-1];//3)从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。for(int j=i;j<_length;j++){_data[j - 1] = _data[j];}//4)线性表当前长度-1_length--;//5)返回删除元素return retEle;}/// <summary>/// 获取第i个位置的元素/// </summary>/// <param name="i">元素的位置</param>/// <returns>待获取元素</returns>/// <exception cref="ArgumentException"></exception>public T GetElem(int i){//1)如果获取元素的位置不合适(小于0或者大于当前线性表长度)，抛出异常if (i < 1 || i > _length){throw new ArgumentException("位置必须大于0，且必须小于等于当前线性表的长度");}//2)返回第i个位置的元素return _data[i - 1];}/// <summary>/// 初始化一个线性表/// </summary>/// <returns>初始化后的线性表</returns>public IList<T> Init(){//1)初始化数组，为数组分配MAX_SIZE的内存_data = new T[MAX_SIZE];//2)初始化长度为0_length = 0;return this;}/// <summary>/// 插入元素/// </summary>/// <param name="e">待插入元素</param>/// <param name="i">插入的位置</param>/// <exception cref="ArgumentException"></exception>public void Insert(T e, int i){//1)如果插入的位置不合适(小于0或者大于当前线性表长度)，抛出异常if (i < 1 || i > _length){throw new ArgumentException("位置必须大于0，且必须小于等于当前线性表的长度");}//2)如果线性表长度大于等于数组长度，则抛出异常，或者动态扩容。if (_length >= _data.Length){T[] newData = new T[_data.Length * 2];for(int j=0;j<_length;j++){newData[j] = _data[j];}_data = newData;}//3)从最后一个位置元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。for (int j=_length-1;j>=i-1;j--){_data[j+1] = _data[j];}//4)将要插入元素填入位置i处。_data[i - 1] = e;//5)线性表当前长度+1_length++;}
}

顺序存储结构的优缺点

优点

1)无需为表示表中元素之间的逻辑关系而增加额外的存储空间
2)可以快速的存取表中任意位置的元素。

缺点

1)插入和删除操作需要移动大量元素
2)当线性表长度变化较大时，难以确定存储空间的容量
3)造成存储空间的“碎片”

这篇关于大话数据结构学习笔记-线性表(二)-顺序存储结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/915727。

相关文章

Vite 打包目录结构自定义配置小结

Vite 打包目录结构自定义配置小结

《Vite打包目录结构自定义配置小结》在Vite工程开发中,默认打包后的dist目录资源常集中在asset目录下,不利于资源管理,本文基于Rollup配置原理,本文就来介绍一下通过Vite配置自定义... 目录一、实现原理二、具体配置步骤1. 基础配置文件2. 配置说明（1）js 资源分离（2）非 JS 资
阅读更多...
Unity新手入门学习殿堂级知识详细讲解（图文）

Unity新手入门学习殿堂级知识详细讲解（图文）

《Unity新手入门学习殿堂级知识详细讲解（图文）》Unity是一款跨平台游戏引擎,支持2D/3D及VR/AR开发,核心功能模块包括图形、音频、物理等,通过可视化编辑器与脚本扩展实现开发,项目结构含A... 目录入门概述什么是 UnityUnity引擎基础认知编辑器核心操作Unity 编辑器项目模式分类工程
阅读更多...
redis数据结构之String详解

redis数据结构之String详解

《redis数据结构之String详解》Redis以String为基础类型,因C字符串效率低、非二进制安全等问题,采用SDS动态字符串实现高效存储,通过RedisObject封装,支持多种编码方式（如... 目录一、为什么Redis选String作为基础类型？二、SDS底层数据结构三、RedisObject
阅读更多...
Java集合中的链表与结构详解

Java集合中的链表与结构详解

《Java集合中的链表与结构详解》链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序的通过链表中的引用链接次序实现,文章对比ArrayList与LinkedList的结构差异,详细讲解了链表... 目录一、链表概念与结构二、当向单链表的实现2.1 准备工作2.2 初始化链表2.3 打印数据、链表长
阅读更多...
Python学习笔记之getattr和hasattr用法示例详解

Python学习笔记之getattr和hasattr用法示例详解

《Python学习笔记之getattr和hasattr用法示例详解》在Python中,hasattr()、getattr()和setattr()是一组内置函数,用于对对象的属性进行操作和查询,这篇文章... 目录1.getattr用法详解1.1 基本作用1.2 示例1.3 原理2.hasattr用法详解2.
阅读更多...
创建springBoot模块没有目录结构的解决方案

创建springBoot模块没有目录结构的解决方案

《创建springBoot模块没有目录结构的解决方案》2023版IntelliJIDEA创建模块时可能出现目录结构识别错误,导致文件显示异常,解决方法为选择模块后点击确认,重新校准项目结构设置,确保源... 目录创建spChina编程ringBoot模块没有目录结构解决方案总结创建springBoot模块没有目录
阅读更多...
SpringBoot利用树形结构优化查询速度

SpringBoot利用树形结构优化查询速度

《SpringBoot利用树形结构优化查询速度》这篇文章主要为大家详细介绍了SpringBoot利用树形结构优化查询速度,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一个真实的性能灾难传统方案为什么这么慢N+1查询灾难性能测试数据对比核心解决方案：一次查询 + O(n)算法解决
阅读更多...
Oracle查询表结构建表语句索引等方式

Oracle查询表结构建表语句索引等方式

《Oracle查询表结构建表语句索引等方式》使用USER_TAB_COLUMNS查询表结构可避免系统隐藏字段（如LISTUSER的CLOB与VARCHAR2同名字段）,这些字段可能为dbms_lob.... 目录oracle查询表结构建表语句索引1.用“USER_TAB_COLUMNS”查询表结构2.用“a
阅读更多...
MySQL中的索引结构和分类实战案例详解

MySQL中的索引结构和分类实战案例详解

《MySQL中的索引结构和分类实战案例详解》本文详解MySQL索引结构与分类,涵盖B树、B+树、哈希及全文索引,分析其原理与优劣势,并结合实战案例探讨创建、管理及优化技巧,助力提升查询性能,感兴趣的朋... 目录一、索引概述1.1 索引的定义与作用1.2 索引的基本原理二、索引结构详解2.1 B树索引2.2
阅读更多...
如何使用Maven创建web目录结构

如何使用Maven创建web目录结构

《如何使用Maven创建web目录结构》：本文主要介绍如何使用Maven创建web目录结构的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录创建web工程第一步第二步第三步第四步第五步第六步第七步总结创建web工程第一步js通过Maven骨架创pytho
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2