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

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。

相关文章

利用Python快速搭建Markdown笔记发布系统

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言：为什么要自建知识博客一、技术选型：极简主义开发栈二、系统架构设计三、核心代码实现（分步解析
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
使用Java实现通用树形结构构建工具类

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子
阅读更多...
利用Python开发Markdown表格结构转换为Excel工具

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark
阅读更多...
Java进阶学习之如何开启远程调式

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,：本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx
阅读更多...
mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据

mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据

《mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据》文章主要介绍了如何从.frm和.ibd文件恢复MySQLInnoDB表结构和数据,需要的朋友可以参... 目录一、恢复表结构二、恢复表数据补充方法一、恢复表结构（从 .frm 文件）方法 1：使用 mysq
阅读更多...
Python中顺序结构和循环结构示例代码

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
Java深度学习库DJL实现Python的NumPy方式

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
使用Navicat工具比对两个数据库所有表结构的差异案例详解

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》：本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较：二、开始比较总结概要公司存在多
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2