【Python】数据结构实战------数组

原创

小馒头学Python

修改于 2024-02-21 20:24:54

16500

代码可运行

修改于 2024-02-21 20:24:54

文章被收录于专栏：小馒头学Python小馒头学Python

运行总次数：0

代码可运行

?数组（Array）

首先我将介绍一下数组的基本原理

线性数据结构，同时它在内存中是一段连续的存储空间
可以通过索引或者下标继续访问元素，从0开始
所有元素的类型相同，内存空间相等

其次介绍一下优缺点

优点：

随机访问，对应时间复杂度就是o（1）
索引计算简单

缺点：

数组的大小如果不做后续处理，是固定的
插入和删除操作效率较低
内存空间较浪费

?数组的基本操作实现

我们定义一个类（MyArrayList），并进行数组的初始化

class MyArrayList:
    def __init__(self, init_capacity=1):
        self.data = [None] * init_capacity
        self.size = 0

接下来我们分别进行不同操作的函数讲解

添加一个元素（位置无要求）

def add(self, index, e):
        self._check_position_index(index)
        cap = len(self.data)
        if self.size == cap:
            self._resize(2 * cap)
        self.data[index+1:self.size+1] = self.data[index:self.size]
        self.data[index] = e
        self.size += 1

添加一个元素（头部）

def add_first(self, e):
        self.add(0, e)

添加一个元素（尾部）

def add_last(self, e):
        cap = len(self.data)
        if self.size == cap:
            self._resize(2 * cap)
        self.data[self.size] = e
        self.size += 1

删除一个元素（位置无要求）

def remove(self, index):
        self._check_element_index(index)
        cap = len(self.data)
        if self.size == cap // 4:
            self._resize(cap // 2)
        deleted_val = self.data[index]
        self.data[index:self.size-1] = self.data[index+1:self.size]
        self.data[self.size - 1] = None
        self.size -= 1
        return deleted_val

删除一个元素（头部）

def remove_first(self):
        return self.remove(0)

删除一个元素（尾部）

def remove_last(self):
        if self.size == 0:
            raise NoSuchElementException()
        cap = len(self.data)
        if self.size == cap // 4:
            self._resize(cap // 2)
        deleted_val = self.data[self.size - 1]
        self.data[self.size - 1] = None
        self.size -= 1
        return deleted_val

通过制定的索引返回元素

def get(self, index):
        self._check_element_index(index)
        return self.data[index]

修改指定位置的元素为element

def set(self, index, element):
        self._check_element_index(index)
        old_val = self.data[index]
        self.data[index] = element
        return old_val

返回列表的大小

def size(self):
        return self.size

判断列表是否为空

def is_empty(self):
        return self.size == 0

检索函数

# 用于检查索引是否在有效范围内。
    def _is_element_index(self, index):
        return 0 <= index < self.size
    def _is_position_index(self, index):
        return 0 <= index <= self.size

    # 用于检查索引是否在有效范围内，如果不在有效范围内，则抛出 IndexError。
    def _check_element_index(self, index):
        if not self._is_element_index(index):
            raise IndexError("Index: " + str(index) + ", Size: " + str(self.size))
    def _check_position_index(self, index):
        if not self._is_position_index(index):
            raise IndexError("Index: " + str(index) + ", Size: " + str(self.size))

感兴趣的小伙伴可以在下面的主函数中自行测试

if __name__ == "__main__":
    arr = MyArrayList(3)
    for i in range(1, 6):
        arr.add_last(i)

    arr.remove(3)
    arr.add(1, 9)
    arr.add_first(100)
    val = arr.remove_last()

    for i in range(arr.size):
        print(arr.get(i))
    print(arr.display())

如果新容量小于当前大小，则不进行调整。

def _resize(self, new_cap):
 if self.size > new_cap:
 return
 temp = [None] * new_cap
    temp[:self.size] = self.data[:self.size]
 self.data = temp

如果想要运行的可以运行下面的主函数代码

 def __iter__(self):
        self.p = 0
        return self

    def __next__(self):
        if self.p == self.size:
            raise StopIteration
        self.p += 1
        return self.data[self.p - 1]
    # 打印
    def display(self):
        print(f"size = {self.size} cap = {len(self.data)}")
        return self.data


if __name__ == "__main__":
    arr = MyArrayList(3)
    for i in range(1, 6):
        arr.add_last(i)

    arr.remove(3)
    arr.add(1, 9)
    arr.add_first(100)
    val = arr.remove_last()

    for i in range(arr.size):
        print(arr.get(i))
    print(arr.display())

运行代码如下