devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构(Python版)：线性表_线性表的增删改查 python

作者：小蓝xlanll | 2024-05-07 14:30:26

赞

踩

线性表的增删改查 python

2. 线性表（线性数据结构）

线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继。除了第一个没有前驱，最后一个没有后继，
新的数据项加入到数据集中时，只会加入到原有某个数据项之前或之后，具有这种性质的数据集，就称为线性结构。

顺序表和链表是两种最基本的线性表（数据）结构。顺序表是指采用顺序存储的方式来存储数据元素的线性表，它通常在内存中开辟一段连续的存储空间，将结点依次存放在这组地址连续的存储空间中。因为存储空间连续且每个数据元素占用的空间相同，所以可计算得出每结点元素的存储地址，使元素索引取值（或赋值）的时间复杂度减小至 O(1)。链表是指采用链式结构来存储数据元素的线性表，它通常在每个结点创建时主动向系统申请一个本结点的存储空间，并通过指针来链接各个包含数据元素的结点。链表中元素的逻辑顺序是由指针的链接次序决定的，与存储空间的物理位置无关，因此使用时仅能被顺序存取，其元素索引取值（或赋值）的时间复杂度为 O(n)。

编程开发中，常用的线性结构有栈（Stack）、 队列（Queue）、双端队列（Deque）和列表（List）四种。他们的区别在于数据项增减的方式，且都有基于顺序表或链表的两种不同实现方式，具体对比如下表所示：

2.1 栈（Stack）

栈（Stack）是一个有次序的数据集，每个数据项仅从“栈顶”一端加入到数据集中、从数据集中移除，栈具有后进先出LIFO的特性。
在这里插入图片描述

图3：Dict基本操作的大O数量级

栈（Stack）定义的操作如下：

  1. Stack()：创建一个空栈，不包含任何数据项
  2. push(item)：将item加入栈顶，无返回值
  3. pop()：将栈顶数据项移除，并返回，栈被修改
  4. peek()：“窥视”栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
  5. isEmpty()：返回栈是否为空栈 size()：返回栈中有多少个数据项

代码实现：

# 栈
class Stack(object):
    """
    Stack()：创建一个空栈，不包含任何数据项
    push(item)：将item加入栈顶，无返回值
    pop()：将栈顶数据项移除，并返回，栈被修改
    peek()：“窥视”栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
    isEmpty()：返回栈是否为空栈 size()：返回栈中有多少个数据项
    """
    def __init__(self):
        super().__init__()
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        return self.stack.pop()

    def peek(self):
        return self.stack[-1]

    def isEmpty(self):
        return self.stack==[]

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

2.2 队列（Queue）

队列（Queue）是一个有次序的数据集合，数据项仅添加到“尾rear”端，而且仅从“首front”端移除；Queue具有FIFO的操作次序。

在这里插入图片描述

图3：Dict基本操作的大O数量级

队列（Queue）定义的操作如下：

  1. queue()：创建一个空队列对象，返回值为Queue对象
  2. enqueue(item)：将数据项item添加到队尾，无返回值
  3. dequeue()：从队首移除数据项，返回值为队首数据项，队列被修改
  4. isEmpty()：测试是否空队列，返回值为布尔值
  5. size()：返回队列中数据项的个数

代码实现：

# 队列
class Queue(object):
    """
    queue()：创建一个空队列对象，返回值为Queue对象
    enqueue(item)：将数据项item添加到队尾，无返回值
    dequeue()：从队首移除数据项，返回值为队首数据项，队列被修改
    isEmpty()：测试是否空队列，返回值为布尔值
    size()：返回队列中数据项的个数
    """
    def __init__(self):
        super().__init__()
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        """ 时间复杂度：O(n) """
        return self.queue.pop(0)

    def isEmpty(self):
        return self.queue==[]

    def size(self):
        return len(self.queue)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

2.2.1 优先队列（Priority Queue

优先队列（Priority Queue）是一种特殊的队列结构，其出队规则跟队列一样，都从队首出队；但在优先队列内部，数据项的次序却是由“优先级”来确定，即：高优先级的数据项排在队首，而低优先级的数据项则排在后面。

这样，优先队列的入队操作就比较复杂，需要将数据项根据其优先级尽量挤到队列前方；实现优先队列的经典方案是采用二叉堆数据结构，二叉堆能够将优先队列的入队和出队复杂度都保持在 O(log n)。新数据项入队后，根据优先级“上浮”（二叉堆的新增结点方法中的一步操作）到对应位置；最高优先级数据项出队后，通过“下沉”（二叉堆的移出最值项方法中的一步操作），次高优先级数据项排列到队列首位。

代码实现：



  • 1

2.3 双端队列（Deque）

双端队列（Deque）是一种有次序的数据集，跟队列相似，其两端可以称作“首”“尾”端；但deque中数据项既可以从队首加入，也可以从队尾加入，且数据项也可以从两端移除。

某种意义上说，双端队列集成了栈和队列的能力。但双端队列并不具有内在的LIFO或者FIFO特性，如果用双端队列来模拟栈或队列，需要由使用者自行维护操作的一致性。

在这里插入图片描述

图3：Dict基本操作的大O数量级

双端队列（Deque）定义的操作如下：

  1. Deque()：创建一个空双端队列
  2. addFront(item)：将item加入队首
  3. addRear(item)：将item加入队尾
  4. removeFront()：从队首移除数据项，返回值为移除的数据项
  5. removeRear()：从队尾移除数据项，返回值为移除的数据项
  6. isEmpty()：返回deque是否为空 size()：返回deque中包含数据项的个数

代码实现：

# 双端队列
class Deque(object):
    """"
    Deque()：创建一个空双端队列
    addFront(item)：将item加入队首
    addRear(item)：将item加入队尾
    removeFront()：从队首移除数据项，返回值为移除的数据项
    removeRear()：从队尾移除数据项，返回值为移除的数据项
    isEmpty()：返回deque是否为空 size()：返回deque中包含数据项的个数
    """
    def __init__(self):
        super().__init__()
        self.deque = []

    def addFront(self, item):
        """ 时间复杂度：O(n) """
        self.deque.insert(0, item)

    def addRear(self, item):
        self.deque.append(item)

    def removeFront(self):
        """ 时间复杂度：O(n) """
        return self.deque.pop(0)

    def removeRear(self):
        return self.deque.pop()

    def isEmpty(self):
        return self.deque==[]

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

2.4 列表（List）

列表可分为无序列表和有序列表，无序列表（Unordered List）是一种数据项按照相对位置存放的数据集，其中数据项只按照存放位置来索引，与各项数据间的大小关系无关；有序列表（Ordered List）是一种数据项依照其某可比性质（如整数大小、字母表先后）来决定其在列表中位置的数据集，越“小”的数据项越靠近列表的头（越靠“前”）。

列表一般是无序列表（使用有序列表时，名称前半部分的有序二字不应省略），在Python语言中，内置列表（list）数据类型已很好地实现了基于顺序表的无序列表数据结构，一般我们可直接使用。下文中，我们进一步简述基于（单向）链表实现的无序列表和有序列表数据结构。

无序列表（Unordered List）定义的操作如下：

  1. List()：创建一个空列表
  2. append(item)：添加一个数据项到表末尾
  3. remove(item)：从列表中移除item，列表被修改
  4. search(item)：在列表中查找item，返回布尔类型值
  5. isEmpty()：返回列表是否为空
  6. _size()：返回列表包含了多少数据项
  7. index(item)：返回数据项在表中的位置
  8. insert(pos, item)：将数据项插入到位置pos
  9. pop(pos)：移除位置为pos的数据项，假设原列表存在位置pos

基于链表的无序列表代码实现：

# 链表结点
class SingleNode(object):
    """
    创建单链表的一个结点
    """
    def __init__(self, data, next_node=None):
        super().__init__()
        self.data = data
        self.next_node = next_node

# 列表
class List(object):
    """
     List()：创建一个空列表
     add(item)：从头部添加一个数据项到列表中
     remove(item)：从列表中移除item，列表被修改
     search(item)：在列表中查找item，返回布尔类型值
     isEmpty()：返回列表是否为空
     size()：返回列表包含了多少数据项
     append(item)：添加一个数据项到表末尾
     index(item)：返回数据项在表中的位置
     insert(pos, item)：将数据项插入到位置pos
     pop(pos)：默认从列表开头移除数据项，若给定pos，则移除该位置为的数据项
    """
    def __init__(self, alist=None):
        super().__init__()
        self.head = None
        self.size = 0
        if alist is not None:
            for item in alist:
                self.append(item)


    def append(self, item):
        """添加一个数据项到表末尾，时间复杂度是 O(1)"""
        temp_node = SingleNode(item)
        temp_node.next_node = self.head
        self.head = temp_node
        self.size += 1


    def remove(self, item):
        """从列表中移除item，列表被修改，时间复杂度是 O(n)"""
        #
        if self.isEmpty():
            print('list is Empty')
            return False
        # 列表非空
        pre_node = None
        cur_node = self.head
        while cur_node is not None:
            if cur_node.data == item:
                if pre_node is None:
                    """当先结点是链首结点"""
                    self.head = cur_node.next_node
                else:
                    """当先结点非链首结点"""
                    pre_node.next_node = cur_node.next_node
                self.size -= 1
                return True
            else:
                cur_node = cur_node.next_node
        print("This item is' not in list")


    def search(self, item):
        """
        在列表中查找item，返回布尔类型值；
        仅能实现顺序查找，时间复杂度是 O(n)
        """
        cur_node = self.head
        while cur_node:
            if cur_node.data == item:
                return True
            else:
                cur_node = cur_node.next_node
        return False


    def isEmpty(self):
        """返回列表是否为空"""
        return self.head is None


    def _size(self):
        """
        可顺序遍历每结点后得出，时间复杂度是 O(n)
        或在类中添加一个属性来保存列表大小，时间复杂度是 O(1)
        """
        # cur_node = self.head
        # n = 0
        # while cur_node is not None:
        #     n += 1
        #     cur_node = cur_node.next_node
        # return n
        return self.size


    def index(self, item):
        """返回数据项在表中的位置，时间复杂度是 O(n)"""
        cur_node = self.head
        n = 0
        while cur_node:
            if cur_node.data == item:
                return self.size - 1 - n
            else:
                cur_node = cur_node.next_node
                n += 1
        print("This item is' not in list")


    def insert(self, pos, item):
        """将数据项插入到位置pos，时间复杂度是 O(n)"""
        if pos == self.size:
            """尾插"""
            self.append(item)
            self.size += 1
        elif 0 <= pos < self.size:
            cur_node = self.head.next_node
            for i in range(self.size-1, -1, -1):
                if i == pos:
                    temp = SingleNode(item)
                    temp.next_node = cur_node.next_node
                    cur_node.next_node = temp
                    self.size += 1
                else:
                    cur_node = cur_node.next_node
        else:
            raise IndexError('list index out of range')


    def pop(self, pos=None):
        """
        默认从列表开头移除数据项，时间复杂度是 O(1)；
        若给定pos，则移除该位置为的数据项 ，时间复杂度是 O(n)
        """
        if self.isEmpty():
            print('list is Empty')
            return False
        #
        if pos is None:
            temp = self.head
            self.head = self.head.next_node
            self.size -= 1
            return temp.data
        elif pos == self.size - 1:
            """尾删"""
            temp = self.head
            self.head = temp.next_node
            self.size -= 1
            return temp.data
        elif 0 <= pos < self.size - 1:
            pre_node = self.head
            cur_node = self.head.next_node
            for i in range(self.size-2, -1, -1):
                if i == pos:
                    pre_node.next_node = cur_node.next_node
                    self.size -= 1
                    return cur_node.data
                else:
                    pre_node = cur_node
                    cur_node = cur_node.next_node
        else:
            raise IndexError('list index out of range')


# test
temp = List([1, 4, 5, 6])

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168

有序列表（Ordered List）定义的操作如下：

  1. OrderedList()：创建一个空的有序表
  2. append(item)：在表中添加一个数据项，并保持整体顺序
  3. remove(item)：从有序表中移除一个数据项，有序表被修改
  4. search(item)：在有序表中查找数据项，返回是否存在
  5. isEmpty()：是否空表
  6. size()：返回表中数据项的个数
  7. index(item)：返回数据项在表中的位置
  8. pop()：移除并返回有序表中最后一项，表中应至少存在一项
  9. pop(pos)：移除并返回有序表中指定位置的数据项，此位置应存在

代码实现：

class OrderedList(List):
    """
    append(item)：在表中添加一个数据项，并保持整体顺序
    remove(item)：从有序表中移除一个数据项，此项应存在
    search(item)：在有序表中查找数据项，返回是否存在
    isEmpty()：是否空表
    _size()：返回表中数据项的个数
    index(item)：返回数据项在表中的位置
    pop(pos)：默认从列表开头移除数据项，若给定pos，则移除该位置为的数据项
    """
    def __init__(self, alist=None):
        super().__init__(alist)

    def append(self, item):
        if self.isEmpty():
            """添加一个数据项到表末尾，时间复杂度是 O(1)"""
            temp_node = SingleNode(item)
            temp_node.next_node = self.head
            self.head = temp_node
            self.size += 1
            return True
        elif self.head.data < item:
            temp = SingleNode(item)
            temp.next_node = self.head
            self.head = temp
            self.size += 1
            return True
        else:
            pre_node = self.head
            cur_node = self.head.next_node
            while cur_node is not None:
                if cur_node.data < item:
                    temp = SingleNode(item)
                    temp.next_node = cur_node
                    pre_node.next_node = temp
                    self.size += 1
                    return True
                else:
                    pre_node = cur_node
                    cur_node = cur_node.next_node
        return False

    def insert(self, pos, item):
        print('无效方法')


# test
temp = OrderedList([1, 5, 3, 7, 10, 15])

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/549681
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号