数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。

数据结构按照其逻辑结构可分为线性结构、树结构、图结构

线性结构：数据结构中的元素存在一对一的相互关系
树结构：数据结构中的元素存在一对多的相互关系
图结构：数据结构中的元素存在多对多的相互关系

列表(数组)

在其他语言中数组是定长的,包含相同元素的一种数据结构,他的变量指向数组的首地址,取值时根据元素类型向后推n个元素所占内存大小,这也是为什么索引是从0开始,而不是从1开始的.

为什么python中的列表可以存储不同类型的值,且是可变长的:

python中列表存的是元素的内存地址
当列表中元素超过所开辟的内存时,会重新开辟一块更大的内存,将原内容复制过去

栈

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

栈的特点:后进先出

用栈来匹配括号:

def check_kuohao(s):
    stack = []
    for char in s:
        if char in {'(', '[', '{'}:
            stack.append(char)
        elif char == ')':
            if len(stack) > 0 and stack[-1] == '(':
                stack.pop()
            else:
                return False
        elif char == ']':
            if len(stack) > 0 and stack[-1] == '[':
                stack.pop()
            else:
                return False
        elif char == '}':
            if len(stack) > 0 and stack[-1] == '{':
                stack.pop()
            else:
                return False
    if len(stack) == 0:
        return True
    else:
        return False

队列

队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
进行插入的一端称为队尾(rear)，插入动作称为进队或入队
进行删除的一端称为队头(front)，删除动作称为出队
队列的性质：先进先出(First-in, First-out)

简单的队列:列表+两个变量

创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。
进队操作：元素写到li[rear]的位置，rear自增1。
出队操作：返回li[front]的元素，front自减1。

缺点:空间的浪费

环形队列

环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0。
实现方式：求余数运算(保证了两个指针的范围都在0-MaxSize之间)
队首指针前进1：front = (front + 1) % MaxSize
队尾指针前进1：rear = (rear + 1) % MaxSize
队空条件：rear == front
队满条件：(rear + 1) % MaxSize == front

链表

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

节点定义

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

建立链表

头插法

def createLinkListF(li):
    l = Node() # 建立一个头
    for num in li:
        s = Node(num) # 数据对象
        s.next = l.next # 新对象的下个节点指向头的节点
        l.next = s # 头的节点指向新对象
    return l

尾插法

def createLinkListF(li):
    l = Node() # 建立一个头
    s = l
    for num in li:
        s.next = Node(num) # s.next 指向新对象
        s = s.next() # 重定义s
    return l

节点的插入与删除

# 插入:
p.next=corNode.next
corNode.next=p

# 删除:
corNode.next = corNode.next.next
del p

双链表

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

节点定义:

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

　　双端列表的插入与删除

# 插入：
p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p
# 删除：
p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p

直接寻址表

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都是取自全域U={0, 1, …, m - 1}中的一个关键字，这里m不是一个很大的数。别外，假设没有两个元素具有相同的关键字。

为表示动态集合，我们用一个数组，或称为直接寻址表(direct-address table)，记为T[0..m-1]。其中每个位置，或称为槽(slot)，对应全域U中的一个关键字。槽
k指向集合中一个关键字为k的元素。如果该集合中没有关键字为k的元素，则T[k] = NIL。

直接寻址技术缺点：

当域U很大时，需要消耗大量内存，很不实际
如果域U很大而实际出现的key很少，则大量空间被浪费
无法处理关键字不是数字的情况

哈希表

哈希表（Hash Table，又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。

简单哈希函数：

除法哈希：h(k) = k mod m
乘法哈希：h(k) = floor(m(kA mod 1)) 0<A<1

哈希冲突:

由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况叫做哈希冲突。
比如：h(k)=k mod 7, h(0)=h(7)=h(14)=...

解决哈希冲突

开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。

线性探查：如果位置i被占用，则探查i+1, i+2,……
二次探查：如果位置i被占用，则探查i+12,i-12,i+22,i-22,……
二度哈希：有n个哈希函数，当使用第1个哈希函数h1发生冲突时，则尝试使用h2,h3,……

拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。

队列和栈解决迷宫问题

给一个二维列表，表示迷宫（0表示通道，1表示围墙）。给出算法，求一条走出迷宫的路径。

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]
]

栈

在一个迷宫节点(x,y)上，可以进行四个方向的探查：maze[x-1][y], maze[x+1][y], maze[x][y-1], maze[x][y+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 mgpath(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:  # 栈不空时循环
        curNode = stack[-1]  # 查看栈顶元素
        if curNode[0] == x2 and curNode[1] == y2:
            # 到达终点
            for p in stack:
                print(p) # 打印路过信息
            break
        for dir in dirs:
            nextNode = dir(*curNode)
            if mg[nextNode[0]][nextNode[1]] == 0:  # 找到了下一个方块
                stack.append(nextNode) # 将可走的添加进栈中
                mg[nextNode[0]][nextNode[1]] = -1  # 标记为已经走过，防止死循环
                break
        else:
            mg[curNode[0]][curNode[1]] = -1  # 死路一条
            stack.pop()
    return False

队列

思路：从一个节点开始，寻找所有下面能继续走的点。继续寻找，直到找到出口。
方法：创建一个空队列，将起点位置进队。在队列不为空时循环：出队一次。如果当前位置为出口，则结束算法；否则找出当前方块的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)]
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] == x2 and curNode[1] == y2:
            #到达终点
            # print(path)
            return path
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            if mg[nextNode[0]][nextNode[1]] == 0:  # 找到下一个方块
                queue.append((*nextNode, len(path) - 1)) # 将所有的可走方块都加入队列,len(path)-1被谁带进来的
                mg[nextNode[0]][nextNode[1]] = -1  # 标记为已经走过
    return False

path = mgpath(1,1,8,8)
index = path[-1][2]
path_ = []
path_.append(path[-1])
while True:
    path_.append(path[index])
    index = path[index][2]
    if index<0:
        break
print(path_)