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

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。

相关文章

Java中switch-case结构的使用方法举例详解

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》：本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者
阅读更多...
结构体和联合体的区别及说明

结构体和联合体的区别及说明

《结构体和联合体的区别及说明》文章主要介绍了C语言中的结构体和联合体,结构体是一种自定义的复合数据类型,可以包含多个成员,每个成员可以是不同的数据类型,联合体是一种特殊的数据结构,可以在内存中共享同一... 目录结构体和联合体的区别1. 结构体(Struct)2. 联合体(Union)3. 联合体与结构体的
阅读更多...
PostgreSQL如何查询表结构和索引信息

PostgreSQL如何查询表结构和索引信息

《PostgreSQL如何查询表结构和索引信息》文章介绍了在PostgreSQL中查询表结构和索引信息的几种方法,包括使用`d`元命令、系统数据字典查询以及使用可视化工具DBeaver... 目录前言使用\d元命令查看表字段信息和索引信息通过系统数据字典查询表结构通过系统数据字典查询索引信息查询所有的表名可
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2