如何分析python数据结构

这期内容当中小编将会给大家带来有关如何分析python数据结构，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

创新互联-专业网站定制、快速模板网站建设、高性价比白银区网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式白银区网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖白银区地区。费用合理售后完善，十年实体公司更值得信赖。

数据结构就是设计数据以何种方式组织并存储在计算机中。
比如：列表、集合、字典等都是一种数据结构。

程序 = 数据结构 + 算法

栈

栈（Stack）是一个数据集合，只能在一端进行插入或删除操作的列表
栈的特点：后进先出（last-in, first-out）
栈的基本操作：

• 进栈（压栈）：push

• 出栈：pop

• 取栈顶：gettop，只是看一下，不把元素移除

栈在python中的实现，直接用列表即可：

• 进栈：append(obj)

• 出栈：pop()，不带参数就是出最后一个

• 取栈顶：list[-1]，查看列表最后一个元素

以上栈的操作的时间复杂度都是O(1)。
不过列表本身没有栈的限制，依然可以使用列表支持的其他方法。比如 insert(index, obj) 和 pop(index) 可以插入或取出列表任意位置的元素。但是这些操作不是栈的操作，时间复杂度是O(n)。

队列

队列（Queue）是一个数据集合，仅允许在列表的一段进行插入，另一端进行删除。
队列的性质：先进先出（First-in, First-out）
还有一种双向队列，队列的两端都允许进行进队和出队的操作。

队列不能用列表来实现。如果用列表实现，入队可以是append操作。但是出队是pop(0)，这个操作是把最前面的元素弹出，然后列表前面空了一个位置，所有元素都要往前移动。这样一次操作的时间复杂度是O(n)。

使用下面的模块可以实现队列：

from collections import deque

这个队列是支持双向的，两端都允许进队和出队。操作方法：

• 创建队列：queue = deque()，建一个空队列

• queue = deque(li)，通过一个列表来创建队列

• 进队：append

• 出队：popleft

• 队首进队：appendleft

• 队尾出队：pop

链表

每一个元素都是一个对象，每个对象称为一个节点，包含有数据域item和指向下一个节点的指针next。通过各个节点之间的相互连接，最终串联成一个链表。
节点的定义：

class Node(object):
    def __init__(self, item=None):
        self.item = item
        self.next = None

节点的插入和删除：

# cur_node 是当前节点
# 插入，在当前节点后插入节点p
p.next = cur_node.next
cur_node.naxt = p
# 删除，把当前节点后的节点p删除
p = cur_node.next
cur_node.nxet = cur_node.next.next
del p

节点的插入和删除操作，在链表里的时间复杂度都是O(1)。但是在列表是是O(n)。这个就是链表存在的意义。

建立链表
头插法，每个新加入的元素都插入到头部元素的后面：

def create_link_list_first(li):
    head = Node()
    for item in li:
        p = Node(item)
        p.next = head.next
        head.next = p
    return head

尾插法，每个新加入的元素都放在链表的最后：

def create_link_list_right(li):
    head = Node()
    r = head
    for item in li:
        p = Node(item)
        r.next = p
        r = p
    return head

双链表

双链表是每个节点都有2个指针：一个指向后面的节点，一个指向前面的节点。
单链表中，头部节点没有数据域，值是None，尾部节点的next是None
双链表中，每个节点都有数据局，头部和尾部节点的其中一个指针是None
插入、删除、建立链表就不展开了

列表和链表

下面是两种数据结构的各种基本操作的时间复杂度比较：

• 按元素查找：都是O(n)

• 按下标查找：列表是O(1)，链表是O(n)

• 插入元素：列表是O(n)，链表是O(1)

• 删除元素：列表是O(n)，链表是O(1)

集合与字典

哈希表查找

哈希表（Hash Table，又称为散列表），是一种线性表的存储结构。通过把每个对象的关联字key作为自变量，同个一个哈希函数h(key)，将key映射到下标h(key)处，并将该对象存储在这个位置。
关于这个哈希函数h(k)，就不用深究了。就是给一个表里key，经过计算可以获得一个确定的数（下标）。
例如：数据集合{1, 6, 7, 9}，假设存在哈希函数：h(1) = 0, h(6) = 2, h(7) = 4, h(9) = 5，那么这个哈希表就被存储为[1, None, 6, None, 7, 9]。
这样，当需要查找元素6所在的位置时，通过哈希函数h(6)就可以获得该元素所在的下标（h(6)=2），因此，不需要做遍历，直接去2的位置确认是否有改元素。这就是一个O(1)的时间复杂度。
哈希冲突：由于哈希表的下标范围有限，但是元素key的值是接近无限的。因此可能会出现两个关键字通过哈希函数运算后得到的是同样的值。两个元素映射到通一个下标，这就造成了哈希冲突。
解决哈希冲突的办法：

• 拉链法：将所有冲突的元素在下标处再用链表连接起来

• 开放寻址法：再搞个哈希冲突函数，通过哈希冲突函数，得到新的地址。

python中的集合，就是把元素通过哈希函数得的下标后，去下标位置确认，是否存在值，不存在，则不在集合中。如果存在值，看一下是否一样（可能有华西冲突），如果在该下标处或者是链表里，那么该元素就在集合中。

python中的字典

使用哈希表存储字典，通过哈希函数将字典的key映射为下标。然后可value存储在key对应的下标里。
字典的键值对数量不多的情况下，几乎不会发生哈希冲突。此时查找一个元素的时间复杂度为O(1)。

迷宫问题

可以用一个二维列表表示迷宫。列表中的每个元素都是迷宫中的一格，可能是通路（可以用0表示），也可能是墙（比如用1表示）。每个节点都有4个方向。给出一个算法，给出一条从起点到终点的路径。

maze = [
    [1,1,1,1,1,1,1],
    [1,0,0,0,0,0,1],
    [1,1,0,1,1,0,1],
    [1,0,0,0,0,1,1],
    [1,0,0,1,0,0,1],
    [1,1,1,1,1,1,1]
]

栈实现

在一个迷宫的节点(x, y)上，可以进行4个方向的探查。遍历下面的这个列表，依次完成4个方向的探查：

dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y + 1),
    lambda x, y: (x, y - 1)
]

思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向能走的点。
方法：创建一个空栈，首先将入口节点进栈。当栈不为空是，循环。获取栈顶元素，寻找下一个可走的节点，如果找不到可走的节点，说明当前位置是死胡同，进行回溯（就是当前位置出栈，看前面的点是否还有别的节点可以走）。之前走过的节点可以标记为-1，防止再走上去。

队列实现

思路：从一个节点开始，寻找所有下面能继续走的点。然后继续寻找，直到找到出口。好比很多人一起探索迷宫，遇到岔路了，就把队伍拆分了，继续往每个岔路进行探索。
方法：创建一个空队列，将起点位置进队。在队列不为空时，循环。出队一次，看出队的节点。如果是出口，那么就找到出口了。否则找出出队节点的4个相邻的方块中可走的方块，这些节点全部进队。重复上面的步骤。
按照上面的方法，最终能够找到终点。但是没有输出从起点到终点的路径。每次进队的元素，必须关联到它前一个让他入队的元素。这样就可以倒推出一条从终点到起点的路径了。
这段是我想的，这个路径可以用链表存。链表头最终就是终点位置，链表尾是起点。每个进队列的元素，同时也用头插法插入链表，这样就关联好上一个元素了。貌似不用担心岔路的问题，从
终点到起点的方向是没有分叉的。

深度优先和广度优先

有两种搜索的方法：深度优先和广度优先。
栈的实现就是深度优先方法。
队列的实现就是广度优先方法。
一般，深度优先的实现就是和栈有关。广度优先的实现和队列有关。

上述就是小编为大家分享的如何分析python数据结构了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注创新互联行业资讯频道。