python 列表实现简单的数据结构

python3列表
python中，列表是一种使用频率很高的数据结构，有点类似于C++的数组,但是功能似乎又比数组更加强大，用法更加灵活，可能是我C++没有学到位吧！在这里就不介绍数组了，因为列表本身就是一个加强版的数组，它除了具备python中序列的基本操作：索引，切片，加，乘，检查成员之外，还有很多灵活便捷的方法操作。
列表常见操作
下面是列表中的方法：
list.append(x) : 将元素x加到元素末尾，即arr[len(arr):]=x
list.extend(L): 将列表L的所有元素加到当前列表末尾，即arr[len(arr):]=L
list.insert(i,x): 在列表索引为 i 的元素前插入 x ，即插入完之后 x 的索引变为 i
list.remove(x): 删除列表第一个值为 x 的元素，若不存在，则返回错误信息
list.clear(): 清空列表即del arr[ : ]
list.index(x): 返回列表中第一个值为 x 的元素索引，若不存在，则返回错误信息
list.pop（i）: 删除列表索引为 i 的元素并返回，i 不存在则报错，注意， list.remove(x) 不返回x ；另外，也可list.pop() 直接返回列表最后一个元素
list.count(x): 返回列表中 x 出现的次数
list.reverse(): 将列表元素倒排
list.sort(): 将列表元素升序排序
在上面的方法之中，有些是有返回值的，但是有些只是单纯地对列表进行操作，没有返回值。其中，list.index(x)、list.pop([i])、list.pop()、list.count(x)是有返回值的，其他的都是没有返回值的。
用列表实现“堆栈”
"栈"是一种线性数据结构，遵循后入先出原则，就像一个桶里依次放东西进去，要想取出下面的东西，就必须先将它上面的东西拿出。
栈的两种基本操作：
入栈：push() 、出栈：pop()
用列表实现的话，list.append()、 list.pop() 就可以实现：

>>> stack_test=[9,-8,-7.5,6,2]
>>> stack_test
[9, -8, -7.5, 6, 2]
>>> stack_test.append(-20)
>>> stack_test.append(33)
>>> stack_test
[9, -8, -7.5, 6, 2, -20, 33]
>>> stack_test.pop()
33
>>> stack_test
[9, -8, -7.5, 6, 2, -20]

4.用列表实现“队列”

“队列”，也是一种线性数据结构，遵循先入先出的原则，因此根据上面“栈”的写法，很容易想到我们也可以直接用列表的方法实现，list,append(x) 实现元素的添加，然后 list.pop(0) 抛出列表最左边的元素,易得如下代码：

>>> queue_test=[9,-8,-7.5,6,2]

>>> queue_test.append(20)
>>> queue_test.append(-30)
>>> queue_test
[9, -8, -7.5, 6, 2, 20, -30]
>>> queue_test.pop(0)
9
>>> queue_test
[-8, -7.5, 6, 2, 20, -30]

但是，用上面的方法并不合适，首部进行插入删除操作时，往往需要移动比较多的元素，python中提供了一种双端队列 collections.deque ,支持从两端进行插入删除操作，deque支持如下操作：
    append(x) :尾部添加元素
    appendleft(x):首部添加元素
    pop() :尾部弹出元素
    popleft() :首部弹出元素
    clear() :清空队列
    reverse() :反转队列

>>> from collections import deque
>>> queue_test=deque(['a','b','c','d'])
>>> queue_test.append('x')
>>> queue_test.appendleft('y')
>>> queue_test
deque(['y', 'a', 'b', 'c', 'd', 'x'])
>>> queue_test.popleft()
'y'
>>> queue_test
deque(['a', 'b', 'c', 'd', 'x'])
>>> queue_test.clear()
>>> queue_test
deque([])
>>> list(queue_test)
[]
>>>

5.用列表实现“二叉树”

二叉树，是一种非线性数据结构，具体概念就不介绍了，涉及基础知识概念比较多，这里主要关注如何用一个列表表示一颗二叉树
python 列表实现简单的数据结构
也就是结点之间的关系，父节点，左子树根结点，右子树根结点，我们用嵌套列表表示，即列表的元素还是列表，不难理解，根结点的子树还是一颗二叉树嘛！下面看到上图，再看代码：

binary_tree=[
        'a',
            ['b',['d',[],[]],['e',[],[]] ],
            ['c',['f',[],[]],[]]
        ]
print("输出二叉树：")
print(binary_tree)
print("输出结点 a 的左子树：")
print(binary_tree[1])
print("输出结点 b 的右子树:")
print(binary_tree[1][2])
print("输出结点 a 的右子树的根节点：")
print(binary_tree[2][0])
print("输出结点 a 的右子树的左子树：")
print(binary_tree[2][1])

python 列表实现简单的数据结构
从代码和结果中我们可以发现，列表 binary_tree 其实就只有 3 个元素 binary_tree[0:3] 分别是根节点，左子树，右子树，每个元素又是一个列表，同样是只有3个元素，根节点，左子树，右子树，比如 binary_tree[1][0] , binary_tree[1][1] , binary_tree[1][2] ,通过嵌套，将下一层子树嵌套进列表元素中，这种表示方法应该是很直观的。

谢谢阅读，如有问题或想法，请随时指出，万分感谢！

python 列表实现简单的数据结构

相关推荐