当前位置：首页 > news >正文

数据结构与算法之Python实现——线性表（一）

news 来源：原创 2024/5/7 5:49:56

🐳 前言

数据结构与算法的一刷是在前几个月的时候用C语言区实现的，那时候也刚开始接触C语言，只知道个C语言的大概，然后却不怎么会应用。

之后在网上买了一本数据结构的书后就开始用C语言去学习。在用C语言去学习的过程中，是十分痛苦的，很多概念都十分抽象，也只有自己想方设法地去理解。但收获也是颇丰，用了几个月硬生生把它啃下来后，也的的确确发现自己对C语言的理解和应用更上一层楼。

但在后面接触python后，我又发现自己对数据结构与算法的学习仅仅停留在C语言的基础上。在我想用python写代码时，常常无从下手，去翻阅别人的博客后，也只能理解个大概，从写代码上来说还是不太行。

于是一直指导我的一位大佬建议我再用python去刷一遍数据结构，告诉我数据结构与算法不是只局限在某个语言之上，它锻炼的是我们的底层思维逻辑和用代码解决实际问题的能力。

数据结构与算法的出现，是针对于解决某些具体的问题，而通过问题寻找解答方法的这种思路正是我们要学习的。

对于一个具体的问题，我们知道怎么解决是一回事，如何用代码去解决又是另一回事。所以这就要求对计算机语言有较高的熟悉度和基于计算机语言的逻辑思维。（说个题外话，因为大二有一门概率论与数理统计的课程，所以之前指导我的那个大佬叫我用C语言去实现这门课的一些试题，大家有兴趣的话可以看一看C语言实现概率论与数理统计）

在此，我会用博客来记录用python实现数据结构与算法的学习过程，希望大家多多支持

🐳 理解线性表

什么是线性表？或者说什么是线性？

线性可以理解为“线”的性质，也就是说线性就类似于“一条线”的性质。通过这条线，将一个一个数据连接起来，每个数据与数据之间的关系一定是前后关系，意思是一个数据只能在另一个数据的前面或者后面，不能在其它位置，此即线性表。

线性表又可以进一步细分为两种——顺序表和链表。请看下图区别👇：

在这里插入图片描述
顺序表是一体式结构，就是说将数据一起存放在一个大的“整体”中。

链表就是通过某种方式将数据链接起来，这里的有向线段是为了突出它们的前后关系。

下面先对顺序表作具体说明（关于链表的类型和操作较多，所以在下一条博客中整理出来）👇：

🐳 顺序表

在Python中我们用list数据类型来作为“线性表”，为什么？

list类型中数据间只有前后关系
list可变，可对其中的数据进行增删改等操作

像元组（它不支持改变其每部状态的任何操作）就不满足上述第二个条件，所以元组不能用作为线性表。

🐋 顺序表的一些主要操作

🐬 初始化
🐬 载入数据
🐬 添加元素
🐬 删除元素
🐬 判断表中位置是否已满
🐬 查找某个数据在表中的位置
🐬 扩大表空间

先看总代码👇

class SqList:
    # 初始化
    def __init__(self,MaxSize):                 # MaxSize为表的最大空间
        self.MaxSize = MaxSize
        self.size = 0                           # 当前表的数据量
        self.data = [None] * self.MaxSize       # 存储表中的数据

    # 加载数据
    def load(self,Elem):                        # 传入一个list，Elem是传入list的名
        if len(Elem) > self.MaxSize:            # 判断list的长度是否超过表长
            return -1
        for i in range(len(Elem)):              # 开始载入
            self.data[self.size] = Elem[i]
            self.size += 1

    # 在指定位置添加数据
    def add(self,pos,e):                        # pos为指定位置，e为数据的值
        if self.size == self.MaxSize:
            return -1
        i = self.size
        while i > pos:
            self.data[i] = self.data[i - 1]
            i -= 1
        self.data[pos] = e
        self.size += 1

    # 删除指定位置的数据                           # pos为指定位置
    def delete(self,pos):
        if self.size == 0:
            return -1
        for i in range(pos,self.size - 1):
            self.data[i] = self.data[i + 1]
        self.data[self.size - 1] = None
        self.size -= 1

    # 判断顺序表的空间是否还有剩余
    def judge(self):
        if self.size == self.MaxSize:
            print('The list is full!')		# 这个表已满
        elif self.size == 0:
            print('The list is empty!')		# 这个表是空的
        else:
            vac = self.MaxSize - self.size
            print('There are only %d vacancies left!' % vac) # 这个表还剩下vac个位置
    # 查找
    def search(self,e):
        for i in range(len(self.data)):
            if self.data[i] == e:
                print("The position of the data you are searching is:%d" % i) # 你要查找的数据的位置是i
                break
    # 添加空间
    def allocate(self,new_size):
        self.data += [None] * new_size
        self.MaxSize += new_size

a = [1,2,3,4,5]
sqlist = SqList(6)
print('The list you have created:')                 # 你创建的表
print(sqlist.data)
sqlist.load(a)              # 载入数据
print('The list after you put datas in:')           # 输入数据后的表
print(sqlist.data)
sqlist.add(5,6)             # 添加数据
print('Add the data 6 on position 5:')              # 在5号位置上添加数据6
print(sqlist.data)
sqlist.delete(0)            # 删除数据
print('Delete the data on position 0:')             # 删除0号位置的数据
print(sqlist.data)
print('Search the position of data 6------------------------')  # 查找数据值为6在表种的位置
sqlist.search(6)            # 查找数据在表中的位置
print('Judge the rest places of the list-------------------------') # 判断表种剩余的空间
sqlist.judge()              # 判断表中剩余空间的情况
sqlist.allocate(3)          # 增加表空间
print('The rest places of the list after allocating new places---------------------')  # 重新分配空间后表种剩余的空间
sqlist.judge()              # 判断表中剩余空间的情况