5 数据结构、栈、队列、链表、list、dict、迷宫问题

时间:2021-09-28 17:43:01

 1、什么是数据结构

5 数据结构、栈、队列、链表、list、dict、迷宫问题

2、栈:后进先出

1、什么是栈

栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除操作的列表。

5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题    5 数据结构、栈、队列、链表、list、dict、迷宫问题

2、栈的Python实现

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

stack = []
stack.append(1)         # 进栈 
stack.append(2)
print(stack.pop())      # 最后一个,出去
print(stack[-1])        # 最后一个元素,栈顶

3、栈的应用——括号匹配问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

def check_kuohao(s):
    stack = []
    for char in s:
        print(stack)
        if char in {'(', '{', '['}:
            stack.append(char)
        # 判断下一个是: ) } ]
        elif char == ")":
            if stack[-1] == '(' and len(stack) > 0:
                stack.pop()
            else:
                return False
        elif char == "}":
            if stack[-1] == '{' and len(stack) > 0:
                stack.pop()
            else:
                return False
        elif char == "]":
            if stack[-1] == '[' and len(stack) > 0:
                stack.pop()
            else:
                return False
    if len(stack) == 0:
        return True
    else:
        return False


strings = "([{()}])"
if check_kuohao(strings):
    print('匹配')
else:
    print('不匹配')

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

4、栈的应用——迷宫问题:深度优先

5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

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

 

 

1、解决思路:逆向游走算法

在一个迷宫节点(x,y)上,可以进行四个方向的探查:maze[x-1][y], maze[x+1][y], maze[x][y-1], maze[x][y+1]

5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

2、栈实现

5 数据结构、栈、队列、链表、list、dict、迷宫问题

# -*- coding: utf-8 -*-
# @Time    : 2018/08/01 0001 14:17
# @Author  : Venicid
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

# 搜索路径
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)
        ]


def mpath(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        curNode = stack[-1]
        if (curNode[0], curNode[-1]) == (x2, y2):
            # 到达终点
            for p in stack:
                print(p)
            return True
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                # 找到了下一个
                stack.append(nextNode)      # 添加到栈
                maze[nextNode[0]][nextNode[1]] = -1  #标记为已经走过,防止死循环
                break
        else:   # 四个方向都没找到
            maze[curNode[0]][curNode[1]] = -1
            stack.pop()
    print("没有路")
    return False

mpath(2,2,8,8)

 

5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

5、队列:先进先出

队列(Queue)是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除。

  5 数据结构、栈、队列、链表、list、dict、迷宫问题

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

1、队列能否用list实现?

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

费时间,费内存

 5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

2、队列的使用:from collections import deque

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

from collections import deque
queue = deque()             # q = ""
queue.append(1)             # q = "1"
queue.append(2)             # q = "1  2"
print(queue.popleft())      # q = "2"

3、队列的实现原理——环形队列:求余

5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

环形队列:当队尾指针front == Maxsize + 1时,再前进一个位置就自动到0。
实现方式:求余数运算
队首指针前进1:front = (front + 1) % MaxSize
队尾指针前进1:rear = (rear + 1) % MaxSize
队空条件:rear == front
队满条件:(rear + 1) % MaxSize == front

6、队列的应用——迷宫问题:广度优先

  (1)思路

 5 数据结构、栈、队列、链表、list、dict、迷宫问题 

5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

  (2)队列实现

5 数据结构、栈、队列、链表、list、dict、迷宫问题

# -*- coding: utf-8 -*-
# @Time    : 2018/08/01 0001 14:46
# @Author  : Venicid
mg = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

# 搜索路径
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)
        ]

from collections import deque


def print_p(path):
    curNode = path[-1]
    realpath = []
    print('迷宫路径为:')
    while curNode[2] != -1:
        realpath.append(curNode[0:2])
        curNode = path[curNode[2]]
    realpath.append(curNode[0:2])
    realpath.reverse()
    print(realpath)


def mgpath(x1, y1, x2, y2):
    queue = deque()
    path = []
    queue.append((x1,y1,-1))
    while len(queue) > 0:
        curNode = queue.popleft()
        path.append(curNode)
        if (curNode[0], curNode[1]) == (x2, y2):
            # 到达终点
            print_p(path)
            return True
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            if mg[nextNode[0]][nextNode[1]] == 0:   # 找到下一个方块
                queue.append((*nextNode, len(path)-1))
                mg[nextNode[0]][nextNode[1]] = -1       # 标记我已经走过

    else:
        return False

mgpath(2,2,8,8)

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

7、链表

5 数据结构、栈、队列、链表、list、dict、迷宫问题

1、节点

5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

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

head = Node()
a = Node(86)
b = Node(19)
c = Node(4)
a.next = b
b.next = c
print(a.next.next.item)

2、链表的遍历

  5 数据结构、栈、队列、链表、list、dict、迷宫问题

   5 数据结构、栈、队列、链表、list、dict、迷宫问题

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

# 定义一个链表
head = Node()
head.next = Node(20)
head.next.next = Node(30)

# 遍历列表
def traversal(head):
    curNode = head # 临时用指针
    while curNode is not None:
        print(curNode.item)
        curNode = curNode.next

traversal(head)

3、链表节点的插入与删除

插入: O(1)
p.next = curNode.next
curNode.next = p

 5 数据结构、栈、队列、链表、list、dict、迷宫问题   5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题 

删除:O(1)
p = curNode.next
curNode.next = curNode.next.next
del p

 5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题 5 数据结构、栈、队列、链表、list、dict、迷宫问题

4、建立链表

(1)头插法

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

 5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题   5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

(2)尾插法

5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题   5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题  5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

 5、双链表

  双链表中每个节点有两个指针:一个指向后面节点、一个指向前面节点

 5 数据结构、栈、队列、链表、list、dict、迷宫问题 5 数据结构、栈、队列、链表、list、dict、迷宫问题

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题 5 数据结构、栈、队列、链表、list、dict、迷宫问题 5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题 5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

 5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题

 6、链表与列表的对比分析

                          列表   链表

按元素值查找                   O(n)
按下标查找                 O(1)     O(n)
在某元素后插入             O(n)     O(1)
删除某元素                O(n)     O(1) 

8、Python中的集合与字典(了解)

(1)哈希表查找

哈希表(Hash Table,又称为散列表),是一种线性表的存储结构。通过把每个对象的关键字k作为自变量,通过一个哈希函数h(k),将k映射到下标h(k)处,并将该对象存储在这个位置。

例如:数据集合{1,6,7,9},假设存在哈希函数h(x)使得h(1) = 0, h(6) = 2, h(7) = 4, h(9) = 5,那么这个哈希表被存储为[1,None, 6, None, 7, 9]。

当我们查找元素6所在的位置时,通过哈希函数h(x)获得该元素所在的下标(h(6) = 2),因此在2位置即可找到该元素。

5 数据结构、栈、队列、链表、list、dict、迷宫问题

(2)哈希冲突

 哈希函数种类有很多,这里不做深入研究。
哈希冲突:由于哈希表的下标范围是有限的,而元素关键字的值是接近无限的,因此可能会出现h(102) = 56, h(2003) = 56这种情况。此时,两个元素映射到同一个下标处,造成哈希冲突。

5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题

 (3)字典 O(1)

5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

使用哈希表存储字典,通过哈希函数将字典的键映射为下标。假设h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4,则哈希表存储为[None, 18, None, ’Alex’, ‘Man’]

 

5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

(4)列表

 5 数据结构、栈、队列、链表、list、dict、迷宫问题

5 数据结构、栈、队列、链表、list、dict、迷宫问题

  5 数据结构、栈、队列、链表、list、dict、迷宫问题

 

5 数据结构、栈、队列、链表、list、dict、迷宫问题5 数据结构、栈、队列、链表、list、dict、迷宫问题