数据结构

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

程序 = 数据结构 + 算法

栈(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个相邻的方块中可走的方块,这些节点全部进队。重复上面的步骤。
按照上面的方法,最终能够找到终点。但是没有输出从起点到终点的路径。每次进队的元素,必须关联到它前一个让他入队的元素。这样就可以倒推出一条从终点到起点的路径了。
这段是我想的,这个路径可以用链表存。链表头最终就是终点位置,链表尾是起点。每个进队列的元素,同时也用头插法插入链表,这样就关联好上一个元素了。貌似不用担心岔路的问题,从
终点到起点的方向是没有分叉的。

深度优先和广度优先

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

相关文章
相关标签/搜索