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

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。

相关文章

Go学习记录之runtime包深入解析

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,：本文主要介绍Go学习记录之runtime包的... 目录前言：一、runtime包内容学习1、作用：① Goroutine和并发控制：② 垃圾回收：③ 栈和
阅读更多...
Android学习总结之Java和kotlin区别超详细分析

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,：本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1：Kotlin 如何解决 Java 的 NullPointerExceptio
阅读更多...
Python+PyQt5实现文件夹结构映射工具

Python+PyQt5实现文件夹结构映射工具

《Python+PyQt5实现文件夹结构映射工具》在日常工作中,我们经常需要对文件夹结构进行复制和备份,本文将带来一款基于PyQt5开发的文件夹结构映射工具,感兴趣的小伙伴可以跟随小编一起学习一下... 目录概述功能亮点展示效果软件使用步骤代码解析1. 主窗口设计（FolderCopyApp）2. 拖拽路径
阅读更多...
重新对Java的类加载器的学习方式

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》：本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示
阅读更多...
Java学习手册之Filter和Listener使用方法

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》：本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter（过滤器）1. Filter 的工作原理2. Filter 的配置与使用二、Listen
阅读更多...
利用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
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2