数据结构（Python）

1.数据结构介绍

1.定义
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
比如：列表、集合与字典等都是一种数据结构。
2.数据结构的分类
数据结构按照其逻辑结构可分为线性结构、树结构、图结构。
线性结构：数据结构中的元素存在一对一的相互关系（比如列表中的数据是一个挨着一个）
树结构：数据结构中的元素存在一对多的相互关系（比如在堆排序中的二叉树，一个父节点可以对应一个或者多个子节点）
图结构：数据结构中的元素存在多对多的相互关系（可以想象成地图中，各个地点之间可以有多条道路相互连接）

2.列表

1.列表/数组
①列表（其他语言称数组）是一种基本数据类型。
②关于列表的问题：
Q：列表中的元素是如何存储的？
A：顺序存储
Q：列表的基本操作：按下标查找、插入元素、删除元素……这些操作的时间复杂度是多少？
A：分别是O(1)、O(n)、O(n)

3.栈的介绍

1.定义
栈(Stack)是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。（可以想象为下面的这堆书，只能对书顶进行增加一本书或者拿走一本书的操作）

'''栈的实现：创建一个栈的类'''
class Stack:
    def __init__(self):
        self.stack = []

    # 进栈：li.append
    def push(self,element):
        self.stack.append(element)

    # 出栈：li.pop
    def pop(self):
        return self.stack.pop()

    # 取栈顶：li[-1]
    def get_top(self):
        if len(self.stack)>0:
            return self.stack[-1]
        else:
            return None
stack = Stack()
stack.push("aaa")
stack.push("bbb")
stack.push("666")
print(stack.pop())
print(stack.get_top())

# 输出：
# 666
# bbb

4.栈的应用：括号匹配问题

class Stack:
    def __init__(self):
        self.stack = []

    # 进栈：li.append
    def push(self,element):
        self.stack.append(element)

    # 出栈：li.pop
    def pop(self):
        return self.stack.pop()

    # 取栈顶：li[-1]
    def get_top(self):
        if len(self.stack)>0:
            return self.stack[-1]
        else:
            return None

    # 判断栈是否为空
    def is_empty(self):
        return len(self.stack) == 0

def brace_match(s):
    match = {'}':'{',']':'[',')':'('}
    stack = Stack()
    for ch in s:
        if ch in {'(','[','{'}:
            stack.push(ch) # 如果是左括号就进栈
        else: # ch isnot {'(','[','{'}
            if stack.is_empty(): # 如果栈里面是空的，又进栈一个右括号，肯定是False
                return False
            elif stack.get_top() == match[ch]: # 如果栈顶的左括号 == 即将进栈的右括号，则将栈顶出栈
                stack.pop()
            else: # stack.get_top() != match[ch] # 如果是其他的非括号字符，则报错
                return False
    # 全部字符进栈后，若字符串为空，则表示括号全部匹配消掉了，返回True，否则返回False
    if stack.is_empty():
        return True
    else:
        return False

print(brace_match('{[[{}]]()[()]}'))
print(brace_match('[{()}(){()}[]({}){}]'))
print(brace_match('[])}'))

# 输出：
# True
# True
# False

5.队列的介绍

1.定义

6.队列的实现

'''创建一个队列的类'''
class Queue:
    def __init__(self,size=100):
        self.queue = [0 for i in range(size)] # 创建一个size大小的队列
        self.size = size # 队列的大小
        self.rear = 0 # 队尾指针
        self.front = 0 # 队首指针

    # 入队
    def push(self,element):
        if not self.is_filled():
            self.rear = (self.rear+1) % self.size
            self.queue[self.rear] = element
        else:
            raise IndexError("Queue is filled!")

    # 出队
    def pop(self):
        if not self.is_empty():
            self.front = (self.front+1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError("Queue is empty!")

    # 判断是否队空
    def is_empty(self):
        return self.rear == self.front

    # 判断是否队满
    def is_filled(self):
        return (self.rear+1) % self.size == self.front

q = Queue(10)
for i in range(9):
    q.push(i)
print(q.pop())
q.push(6)
print(q.pop())

7.队列的内置模块

1.双向队列

使用方法：from collections import deque
创建队列：queue = deque()
进队：append()
出队：popleft()
双向队列队首进队：appendleft()
双向队列队尾出队：pop()

举例：

from collections import deque

q = deque([1,2,3,4,5],5) # 5表示队列的大小，若超过这个容量，则队首自动出队
q.append(6) # 队尾进队
print(q.popleft()) # 队首出队

# 用于双向队列
q.appendleft(1) # 队首进队
q.pop() # 队尾出队

# 输出：2

3.队列的应用：读取文件最后指定的部分（Linux tail指令）
比如一个txt文件如下，想要读取该文件中的最后五个字符串，通过队列的特点（若超过设定队列的大小容量，队首自动出队），程序如下：

def tail(n):
    with open("testfile.txt",'r') as f:
        q = deque(f,n)
        return q
print(tail(5))
# 输出：deque(['wfewf\n', '873\n', '99292\n', 'wfwefc\n', 'ijiotngbbgr'], maxlen=5)
for line in tail(5):
    print(line,end='')
# 输出：wfewf
# 873
# 99292
# wfwefc
# ijiotngbbgr

8.栈和队列的应用：迷宫问题

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

# 迷宫地图，0表示通道，1表示围墙；以左上角为原点，横向为y轴，纵向为x轴，因为数组[行][列],第x行y列
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]
]
nodeSequence = [
    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 maze_path(x1,y1,x2,y2):
    # 参数：(x1,y1)-起点  (x2,y2)-终点
    stack = []
    stack.append((x1,y1))
    while(len(stack) > 0):
        currentNode = stack[-1]  # 栈顶，即当前点的位置，x和y坐标
        if currentNode[0] == x2 and currentNode[1] == y2: # 表示已到终点
            print("\n走过的路径如下：")
            for path in stack:
                print(path)
            return True

        maze[x1][y1] = 2 # 先将起点设置为2，是走过的点
        for sp in nodeSequence:
            nextNode = sp(currentNode[0],currentNode[1])
            # 如果下一个点能走，maze[1][1]表示起点，maze[8][8]表示终点
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode) # 下一点入栈
                maze[nextNode[0]][nextNode[1]] = 2 # 将走过的点设置为2
                break
        else:
            maze[nextNode[0]][nextNode[1]] = 2 # 将该点设置为2，同时出栈，退到上一个点
            stack.pop()
    else:
        print("从起点到终点没有路通！")
        return False
maze_path(1,1,8,8)

# 输出：
# 走过的路径如下：
# (1, 1)
# (2, 1)
# (3, 1)
# (4, 1)
# (5, 1)
# (5, 2)
# (5, 3)
# (6, 3)
# (6, 4)
# (6, 5)
# (7, 5)
# (8, 5)
# (8, 6)
# (8, 7)
# (8, 8)

3.方法二：队列——广度优先搜索

思路：从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口。
使用队列存储当前正在考虑的节点。

关于这里的思路讲解：

PS：原视频中的关于队列的广度优先搜索程序是错误的，运行的脚本还是栈的深度优先搜索。

9.链表介绍

1.定义
链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表。

# 举例介绍链表的定义
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c

print(a.next.item)
print(a.next.next.item)

# 输出：
# 2
# 2

10.链表创建和遍历

1.头插法

比如一组数据1，2，3，先插入1，然后从头部head插入2，再接着插入3，这样插入的数据打印出来是倒序的。

# 头插法举例
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None

def creat_linklist_head(li):
    head = Node(li[0]) # 链表头部是列表第一个元素
    for element in li[1:]:
        node = Node(element)
        node.next = head
        head = node
    return head

def print_linklist(lk):
    while lk:
        print(lk.item,end=',')
        lk = lk.next

lk = creat_linklist_head([1,2,3])
print_linklist(lk)

# 输出：
# 3,2,1,

2.尾插法

# 尾插法举例
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None

def creat_linklist_tail(li):
    head = Node(li[0])
    tail = head # 对于第一个元素，tail和head指向同一个元素
    for element in li[1:]:
        node = Node(element)
        tail.next = node
        tail = node
    return head

def print_linklist(lk):
    while lk:
        print(lk.item,end=',')
        lk = lk.next

lk = creat_linklist_tail([1,2,1,3,8])
print_linklist(lk)

# 输出：
# 1,2,1,3,8,

11.链表的插入和删除

1.链表节点的插入

假设原链表是1，2，3，将新元素4插入到1和2之间，
第一步先把4和2链接起来，p.next = curNode.next
第二步再把1和4链接起来，curNode.next = p

2.链表节点的删除

假设原链表是1，4，2，3，删除元素4
第一步先表示要删除的是元素4，即p = curNode.next
第二步再把1和2链接起来，curNode.next = curNode.next.next
第三步，删除元素4

12.双链表

1.定义

双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点。

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

2.双链表节点的插入

在原链表1，3中插入元素2
①第一步，元素2和3正向链接，即 p.next = curNode.next
②第二步，元素2和3反向链接，即 curNode.next.prior = p
③第三步，元素2和1反向链接，即 p.prior = curNode
④第四步，元素2和1正向链接，即 curNode.next = p

3.双链表节点的删除

在原链表1，2，3中，删除元素2
①第一步，表示要删除的元素是2，即 p = curNode.next
②第二步，将元素1和3进行正向链接，即 curNode.next = p.next
③第三步，将元素1和3进行反向链接，即 p.next.prior = curNode
④第四步，删除元素2，即 del p

4.链表与顺序表
链表在插入和删除的操作上明显快于顺序表，链表的内存可以更灵活的分配。

13.哈希表

哈希表定义的讲解：

1.定义
哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
insert(key, value)：插入键值对(key,value)
get(key)：如果存在键为key的键值对则返回其value，否则返回空值
delete(key)：删除键为key的键值对。
2.直接寻址表

假设key值包括2，3，5，8，建立一个全域U：0~9，将对应的key值放在全域对应的位置中，这样访问时可以通过下标很快的定位到所需要的key值。可以发现，当关键字的全域U比较小时，直接寻址是一种简单而有效的方法。
直接寻址技术缺点：
①当域U很大时，需要消耗大量内存，很不实际
②如果域U很大而实际出现的key很少，则大量空间被浪费
③无法处理关键字不是数字的情况
3.哈希
直接寻址表：key为k的元素放到k位置上
改进直接寻址表：哈希（Hashing）
构建大小为m的寻址表T
key为k的元素放到h(k)位置上
h(k)是一个函数，其将域U映射到表T[0,1,…,m-1]
4.哈希表
哈希表（Hash Table，又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。
假设有一个长度为7的哈希表，哈希函数h(k)=k%7。元素集合{14,22,3,5}的存储方式如下图。

5.哈希冲突
由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况叫做哈希冲突。
比如h(k)=k%7, h(0)=h(7)=h(14)=…
6.解决哈希冲突——开放寻址法
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。
线性探查：如果位置i被占用，则探查i+1, i+2,……
二次探查：如果位置i被占用，则探查i+12,i-12,i+22,i-22,……
二度哈希：有n个哈希函数，当使用第1个哈希函数h1发生冲突时，则尝试使用h2,h3,……
7.解决哈希冲突——拉链法

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

9.哈希表的应用——集合与字典