【数据结构与算法】:手搓顺序表(Python篇)

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】:手搓顺序表(Python篇)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、顺序表的概念

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

二、顺序表的实现

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

创建顺序表类

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

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

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

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

1.2 整体建立顺序表

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

# 整体创建顺序表
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的两倍扩大容量。

# 顺序表的添加(尾插)
def Add(self, e):  # 在线性表的末尾添加一个元素
    if self.size == self.capacity:
        self.resize(2 * self.size)  # 顺序表空间满时倍增容量
    self.data[self.size] = e  # 添加元素e
    self.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篇),数据结构与算法,python,算法,数据结构,开发语言

# 指定位置插入
def Insert(self, i, e):  # 在线性表中序号为i的位置插入元素
    assert 0 <= i <= self.size
    if 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  # 插入元素e
    self.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篇),数据结构与算法,python,算法,数据结构,开发语言

def Delete(self, i):  # 在线性表中删除序号为i的元素
    assert 0 <= i <= self.size - 1
    for 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篇),数据结构与算法,python,算法,数据结构,开发语言

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

该算法的时间复杂度为O(n),其中n表示顺序表中的元素个数。

2.5 顺序表元素的索引访问

求顺序表中序号i的元素值:GetElem(i)
当序号i合法时(0<= i < size)返回data[i]。
【数据结构与算法】:手搓顺序表(Python篇),数据结构与算法,python,算法,数据结构,开发语言

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

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

2.6 顺序表元素的修改

设置顺序表中序号i的元素值:SetElem(i,e)
【数据结构与算法】:手搓顺序表(Python篇),数据结构与算法,python,算法,数据结构,开发语言

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

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

2.7 顺序表长度

求顺序表的长度:getsize()
返回顺序表的长度(实际元素个数size)。

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

时间复杂度为O(1)

2.8 顺序表的输出

输出顺序表的所有元素:display()
依次输出顺序表中的所有元素值。

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

时间复杂度为O(n),n表示顺序表中的元素个数。

三、完整代码

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

    # 扩容
    def resize(self, newcapacity):  # 改变顺序表的容量为newcapacity
        assert newcapacity >= 0
        oldata = self.data
        self.data = [None] * newcapacity
        self.capacity = newcapacity
        for 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  # 添加后元素增加1

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

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

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

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

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

    # 指定位置插入
    def Insert(self, i, e):  # 在线性表中序号为i的位置插入元素
        assert 0 <= i <= self.size
        if 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  # 插入元素e
        self.size += 1  # 长度加1

    def Delete(self, i):  # 在线性表中删除序号为i的元素
        assert 0 <= i <= self.size - 1
        for 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()  # 换行

四、代码验证

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] = 20
    print('L[容量 = %d, 长度 = %d]:' % (L.capacity, L.getsize()), end=' '), L.display()
    x = 6
    print('第一个值为%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()

【数据结构与算法】:手搓顺序表(Python篇),数据结构与算法,python,算法,数据结构,开发语言文章来源地址https://www.toymoban.com/news/detail-860858.html

到了这里,关于【数据结构与算法】:手搓顺序表(Python篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:两个顺序表合并算法

            将a,b两个有序顺序表进行合并,放在c顺序表当中,并且要保证顺序表c仍然有序。         因为a,b两个顺序表是有序的,所有可以从前往后一起查找a,b当中最小的一个数值,放入到c中。         如果遍历到最后,a遍历完了,b没有遍历完,就把b剩下的放入

    2024年02月08日
    浏览(36)
  • 【数据结构与算法】3.顺序表

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 定义:线性表是 n 个具有相同特性的数据元素的有序序列。线性表是一种在实际中

    2024年01月23日
    浏览(39)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(52)
  • 顺序表(更新版)——“数据结构与算法”

    各位CSDN的uu们你们好呀,今天小雅兰又来更新新专栏啦,其实之前我就已经写过了顺序表的内容,只是之前的内容不是最新版的顺序表,现在,我来更新一下最新版的顺序表,下面,就让我们进入更新版的顺序表的世界吧 顺序表和小雅兰之前写的三子棋、扫雷、通讯录一样,

    2023年04月23日
    浏览(30)
  • 【Python数据结构与算法】线性结构小结

    🌈个人主页: Aileen_0v0 🔥系列专栏:PYTHON学习系列专栏 💫\\\"没有罗马,那就自己创造罗马~\\\"   目录 线性数据结构Linear DS 1.栈Stack 栈的两种实现 1.左为栈顶,时间复杂度为O(n) 2.右为栈顶,时间复杂度O(1)   2.队列Queue 3.双端队列Deque 4.列表List 5.链表 a.无序链表的实现 b.有序链表的实

    2024年02月04日
    浏览(40)
  • python数据结构和算法

    参考 python图解算法 选择/快速排序 哈希表 广度优先搜索算法 迪杰斯特拉算法 贪婪算法 动态规划 K-邻近算法 算法计时 time模块,与算法复杂度 O() [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EIwk2Zdi-1691788469064)(https://facert.gitbooks.io/python-data-str

    2024年02月13日
    浏览(49)
  • Python数据结构与算法

    栈、队列、双端队列和列表都是有序的数据集合, 其元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来,它与前后元素的相对位置将保持不变。这样的数据集合经常被称为线性数据结构。 栈的添加操作和移除操作总发生在同一端。栈中的元素离底端越近,代

    2024年02月02日
    浏览(53)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(52)
  • 【数据结构与算法】之顺序表及其实现!

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(33)
  • 数据结构与算法 --顺序表的创建

    1. 顺序表(Sequence List)是一种线性表的实现方式,通过连续的内存空间存储元素,按照顺序排列。 顺序表的特点包括: 元素在内存中的存储是连续的,通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包