【数据结构与算法】：手搓顺序表（Python篇）

devtools/2024/11/15 8:29:55/

文章目录

      • 一、顺序表的概念
      • 二、顺序表的实现
        • 1. 顺序表的创建
          • 1.1 扩容
          • 1.2 整体建立顺序表
        • 2. 顺序表的基本运算算法
          • 2.1 顺序表的添加（尾插）
          • 2.2 指定位置插入
          • 2.3 指定位置删除
          • 2.4 顺序表的查找
          • 2.5 顺序表元素的索引访问
          • 2.6 顺序表元素的修改
          • 2.7 顺序表长度
          • 2.8 顺序表的输出
      • 三、完整代码
      • 四、代码验证

一、顺序表的概念

顺序表是一种线性的数据结构，其中数据元素按照特定的顺序依次存储在连续的内存空间中。它由一系列元素组成，每个元素都与唯一的索引（或者叫下标）相关联，索引从 0 开始递增。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
下面这张图中，最下面那行数字0~9代表的是元素的索引，天蓝色的柱子中的数字代表的是顺序表中的元素，顺序表中的元素必须是同一数据类型的，数据类型可以是整数、浮点数、字符串等等。
在这里插入图片描述

二、顺序表的实现

设计顺序表类为SqList，主要包含存放元素的data列表和表示实际元素个数的size属性。因为Python属于弱类型语言，没必要专门设计像C++或则Java中的泛型类，在应用SqList时可以指定其元素为任意合法数据类型。

创建顺序表类：

python"># 顺序表类
class SqList:# 初始化def __init__(self):self.initcapacity = 5  # 初始容量设置为5self.capacity = self.initcapacity  # 容量设置为初始容量self.data = [None] * self.capacity  # 设置顺序表的空间self.size = 0  # 长度设为0
1. 顺序表的创建
1.1 扩容

顺序表在实现各种基本运算如插入和删除时会涉及到容量的更新，所以要设计一个方法将data列表的容量改变为newcapacity。

python"># 扩容
def resize(self, newcapacity):  # 改变顺序表的容量为newcapacityassert newcapacity >= 0oldata = self.dataself.data = [None] * newcapacityself.capacity = newcapacityfor i in range(self.size):self.data[i] = oldata[i]

这里就是先让olddata指向data，为data重新分配一个容量为newcapacity的空间，再将olddata中的所有元素复制到data中，复制中所有的元素的序号和长度size不变。原data空间会被系统自动释放掉。

1.2 整体建立顺序表

该方法就是从空顺序表开始，由含若干个元素的列表a的全部元素整体创建顺序表，即依次将a中的元素添加到data列表的末尾，当出现上溢出时按实际元素个数size的两倍扩大容量。

python"># 整体创建顺序表
def CreateList(self, a):  # 有数组a中的元素整体建立顺序表for i in range(0, len(a)):if self.size == self.capacity:  # 出现上溢出时self.resize(2 * self.size)  # 扩容self.data[self.size] = a[i]self.size += 1  # 添加后元素增加1

时间复杂度为O（n）， n表示顺序表中的元素个数。

2. 顺序表的基本运算算法
2.1 顺序表的添加（尾插）

将元素e添加到顺序表的末尾：Add（e）
在data列表的尾部插入元素e，在插入中出现上溢出时按实际元素个数size的两倍扩大容量。

python"># 顺序表的添加（尾插）
def Add(self, e):  # 在线性表的末尾添加一个元素if self.size == self.capacity:self.resize(2 * self.size)  # 顺序表空间满时倍增容量self.data[self.size] = e  # 添加元素eself.size += 1  # 长度加1

该算法中调用一次resize（）方法的时间复杂度为O（n），但n次Add操作仅需要扩大一次data空间，所以平均时间复杂度仍然为O（1）。

2.2 指定位置插入

在顺序表中插入e作为第i个元素：Insert（i，e）
在顺序表中序号i的位置上插入一个新元素e。若参数i合法（0<= i <= n），先将data[i…n-1]的每个元素均后移一个位置（从data[n - 1]元素开始移动），腾出一个空位置data[i]插入新元素e，最后将长度size增1。在插入元素时若出现上溢出，则按两倍size扩大容量。
在这里插入图片描述

python"># 指定位置插入
def Insert(self, i, e):  # 在线性表中序号为i的位置插入元素assert 0 <= i <= self.sizeif self.size == self.capacity:  # 满时扩容self.resize(2 * self.size)for j in range(self.size, i - 1, -1):  # 疆data[i]及后面的元素后移一位self.data[j] = self.data[j - 1]self.data[i] = e  # 插入元素eself.size += 1  # 长度加1

该算法的时间主要花在元素的移动上，元素移动的次数不仅与表长n有关，而且与插入位置i有关。有效插入位置i的取值是0~n，共有n + 1个位置可以插入元素：

  1. 当i = 0时，移动次数为n，达到最大值。
  2. 当i = n时，移动次数为0，达到最小值。
  3. 其他情况，需要移动data[i…n - 1]的元素，移动次数为（n - 1）- i + 1 = n - i。

时间复杂度为O（n）。

2.3 指定位置删除

顺序表中删除第i个数据元素：Delete（i）
该算法删除顺序表中序号i的元素。若参数i合法（0<= i < n），删除操作是将data[i + 1 … n - 1]的元素均向前移动一个位置（从data[i + 1]元素开始移动），这样覆盖了元素data[i]，从而达到删除该元素的目的，最后将顺序表的长度减一。若当前容量大于初始容量并且实际长度仅为当前容量的1/4（缩容条件），则将当前容量减半。
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

python">def Delete(self, i):  # 在线性表中删除序号为i的元素assert 0 <= i <= self.size - 1for j in range(i, self.size - 1):self.data[j] = self.data[j + 1]  # 将data[j]之后的元素前移一位self.size -= 1  # 长度减一if self.capacity > self.initcapacity and self.size <= self.capacity / 4:self.resize(self.capacity // 2)  # 满足要求容量减半

该算法的时间主要花在元素的移动上，元素移动的次数不仅与表长n有关，而且与删除位置i有关。有效删除位置i的取值是0~n - 1，共有n个位置可以插入元素：

  1. 当i = 0时，移动次数为n - 1，达到最大值。
  2. 当i = n - 1时，移动次数为0，达到最小值。
  3. 其他情况，需要移动data[i +1 … n - 1]的元素，移动次数为（n - 1）- （i + 1）+ 1 = n - i - 1。

时间复杂度为O（n）。

2.4 顺序表的查找

求顺序表中第一个值为e的元素的序号：GetNo（e）
在data列表中从前向后顺序查找第一个值与e相等的元素的序号，若不存在这样的元素，则返回-1。
在这里插入图片描述

python">def GetNo(self, e):  # 查找第一个为e的元素的下标i = 0while i < self.size and self.data[i] != e:  # 查找元素ei += 1if i >= self.size:return -1else:return i

该算法的时间复杂度为O（n），其中n表示顺序表中的元素个数。

2.5 顺序表元素的索引访问

求顺序表中序号i的元素值：GetElem（i）
当序号i合法时（0<= i < size）返回data[i]。
在这里插入图片描述

python">def __getitem__(self, i):  # 求序号为i的元素assert 0 <= i < self.sizereturn self.data[i]

对于顺序表对象L，可以通过L[i]调用上述运算获取序号i的元素值。时间复杂度为O（1）。

2.6 顺序表元素的修改

设置顺序表中序号i的元素值：SetElem（i，e）
在这里插入图片描述

python">def __setitem__(self, i, value):  # 设置序号为i的元素assert 0 <= i < self.sizeself.data[i] = value

对于顺序表对象L，可以通过L[i] = e调用上述运算将序号i的元素值设置为e。该算法的时间复杂度为O（1）

2.7 顺序表长度

求顺序表的长度：getsize（）
返回顺序表的长度（实际元素个数size）。

python">def getsize(self):  # 返回长度return self.size

时间复杂度为O（1）

2.8 顺序表的输出

输出顺序表的所有元素：display（）
依次输出顺序表中的所有元素值。

python">def display(self):  # 输出顺序表for i in range(0, self.size):print(self.data[i], end=' ')print()  # 换行

时间复杂度为O（n），n表示顺序表中的元素个数。

三、完整代码

python"># 顺序表类
class SqList:# 初始化def __init__(self):self.initcapacity = 5  # 初始容量设置为5self.capacity = self.initcapacity  # 容量设置为初始容量self.data = [None] * self.capacity  # 设置顺序表的空间self.size = 0  # 长度设为0# 扩容def resize(self, newcapacity):  # 改变顺序表的容量为newcapacityassert newcapacity >= 0oldata = self.dataself.data = [None] * newcapacityself.capacity = newcapacityfor i in range(self.size):self.data[i] = oldata[i]# 整体创建顺序表def CreateList(self, a):  # 有数组a中的元素整体建立顺序表for i in range(0, len(a)):if self.size == self.capacity:  # 出现上溢出时self.resize(2 * self.size)  # 扩容self.data[self.size] = a[i]self.size += 1  # 添加后元素增加1def Add(self, e):  # 在线性表的末尾添加一个元素if self.size == self.capacity:self.resize(2 * self.size)  # 顺序表空间满时倍增容量self.data[self.size] = e  # 添加元素eself.size += 1  # 长度加1def getsize(self):  # 返回长度return self.sizedef __getitem__(self, i):  # 求序号为i的元素assert 0 <= i < self.sizereturn self.data[i]def __setitem__(self, i, value):  # 设置序号为i的元素assert 0 <= i < self.sizeself.data[i] = valuedef GetNo(self, e):  # 查找第一个为e的元素的下标i = 0while i < self.size and self.data[i] != e:  # 查找元素ei += 1if i >= self.size:return -1else:return i# 指定位置插入def Insert(self, i, e):  # 在线性表中序号为i的位置插入元素assert 0 <= i <= self.sizeif self.size == self.capacity:  # 满时扩容self.resize(2 * self.size)for j in range(self.size, i - 1, -1):  # 疆data[i]及后面的元素后移一位self.data[j] = self.data[j - 1]self.data[i] = e  # 插入元素eself.size += 1  # 长度加1def Delete(self, i):  # 在线性表中删除序号为i的元素assert 0 <= i <= self.size - 1for j in range(i, self.size - 1):self.data[j] = self.data[j + 1]  # 将data[j]之后的元素前移一位self.size -= 1  # 长度减一if self.capacity > self.initcapacity and self.size <= self.capacity / 4:self.resize(self.capacity // 2)  # 满足要求容量减半def display(self):  # 输出顺序表for i in range(0, self.size):print(self.data[i], end=' ')print()  # 换行

四、代码验证

python">if __name__ == '__main__':L = SqList()  # 实例化print('建立空顺序表L, 其容量为 %d' % (L.capacity))a = [1, 2, 3, 4, 5]print('1~6创建L')L.CreateList(a)print('L[容量 = %d, 长度 = %d]:' % (L.capacity, L.getsize()), end=' '), L.display()print('插入6~10')for i in range(6, 11):L.Add(i)print('L[容量 = %d, 长度 = %d]:' % (L.capacity, L.getsize()), end=' '), L.display()print('序号为2的元素 = %d' % (L[2]))print('设置序号为2的元素为20')L[2] = 20print('L[容量 = %d, 长度 = %d]:' % (L.capacity, L.getsize()), end=' '), L.display()x = 6print('第一个值为%d的元素序号 = %d' % (x, L.GetNo(x)))n = L.getsize()for i in range(n - 2):print('删除首元素')L.Delete(0)print('L[容量 = %d, 长度 = %d]:' % (L.capacity, L.getsize()), end=' '), L.display()

在这里插入图片描述


http://www.ppmy.cn/devtools/19850.html

相关文章

Three CSS2D 渲染器 月球绕地球旋转

Three CSS2D 渲染器 月球绕地球旋转

CSS2DRenderer(CSS 2D渲染器) CSS2DRenderer&#xff08;CSS 2D渲染器&#xff09;可以把HTML元素作为标签标注到三维场景中&#xff0c;CSS2DRenderer是CSS3DRenderer&#xff08;CSS 3D渲染器&#xff09;的简化版本&#xff0c;它唯一支持的变换是位移。通过CSS2DRenderer我…
阅读更多...
ubuntu20 中设置桌面背景任务

ubuntu20 中设置桌面背景任务

1. 下载conky 使用 Conky 在 Ubuntu 中显示信息&#xff0c;例如你的阅读计划&#xff0c;可以分几个步骤来完成。Conky 是一款灵活的轻量级系统监视器&#xff0c;能够在桌面上显示各种信息。以下是基本的设置步骤&#xff1a; 安装 Conky 首先&#xff0c;你需要在 Ubuntu…
阅读更多...
传感器在机械自动化中的应用有哪些？

传感器在机械自动化中的应用有哪些？

传感器在机械自动化领域扮演了非常关键的角色&#xff0c;它们是实现高效和精准控制的基础。传感器可以检测和测量机械系统中的各种物理量&#xff0c;如位置、速度、温度、压力等&#xff0c;并将这些物理量转换成电信号&#xff0c;以便控制系统能够进行分析和响应。以下是一…
阅读更多...
如何通过安全数据传输平台，保护核心数据的安全传输？

如何通过安全数据传输平台，保护核心数据的安全传输？

在数字化的浪潮中&#xff0c;企业的数据安全传输显得尤为关键。随着网络攻击手段的日益复杂&#xff0c;传统的数据传输方式已不再安全&#xff0c;这就需要我们重视并采取有效的措施&#xff0c;通过安全数据传输平台来保护核心数据。 传统的数据传输面临的主要问题包括&…
阅读更多...
机器人自动驾驶时间同步进阶

机器人自动驾驶时间同步进阶

0. 简介 之前时间同步也写过一篇文章介绍机器人&自动驾驶中的时间同步。在最近的学习中发现一些额外需要阐述学习的内容&#xff0c;这里就再次写一些之前没写到的内容。 1. NTP NTP 是网络时间协议&#xff0c;用来同步网络中各计算机时间的协议&#xff0c;把计算机的时…
阅读更多...
【bugfix】error in chunk.js from uglifyjs

【bugfix】error in chunk.js from uglifyjs

检查是否是因为新安装的包不支持es5&#xff0c;通过babel 或者 fork 打包输出 es5以兼容老项目。
阅读更多...
shell并行工具parallel

shell并行工具parallel

简介&#xff1a;GNU parallel是一种shell工具&#xff0c;用于使用一台或多台计算机并行执行作业。作业可以是单个命令&#xff0c;也可以是必须为其运行的小脚本输入中的每一行。典型的输入是文件列表、主机列表、用户列表、URL列表或表列表。工作也可以从管道中读取的命令。…
阅读更多...
Linux基础——Linux开发工具(make/makefile，git)

Linux基础——Linux开发工具(make/makefile，git)

前言&#xff1a;在经过前面两篇学习&#xff0c;大家对Linux开发工具都有一定的了解&#xff0c;而在此之前最重要的两个工具就是vim&#xff0c;gcc。 如果对这两个工具不太了解&#xff0c;可以先阅读这两篇文章&#xff1a; Linux开发工具 (vim) Linux开发工具 (gcc/g) 首先…
阅读更多...
最新文章

Copyright @ 2022~2023