算法2——数据结构

数据结构

据结构按照逻辑结构分为线性结构/树结构/图结构 * 线性结构 一对一 * 树结构 一对多 * 图结构 一对多

列表

列表(其他语言也称为数组) 数组和列表有两点不同: 1. 数组元素类型要相同 2. 数组长度固定

数据集合 只能在一端插入或删除操作的列表 栈的特点:后进先出 基本操作: * 进栈 push * 出栈 pop * 取栈顶 gettop

#栈的基本实现
class Stack:
    def __init__(self):
        self.stack = []
    def push(self,element):
        self.stack.append(element)
    def pop(self):
        return self.stack.pop()
    def get_top(self):
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None

栈的应用 括号匹配问题 给一个字符串/其中包含小括号/中括号/大括号,求该字符串中的括号是否匹配.

队列

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

环形队列

  • 当队尾指针front=Maxsize-1时,再前进一个位置就自动到0
  • 队首指针前进1:front=(front+1)%MaxSize
  • 队尾指针前进1:rear=(rear+1)%MaxSize
  • 队空条件:rear == front
  • 队满条件:(rear+1)%MaxSize == front

    # __*__ coding=utf-8 __*__
    
    class Queue:
    def __init__(self,size=100):
        self.queue = [0 for _ in range(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]
    
    def is_empty(self):
        return self.rear == self.front
    
    def is_filled(self):
        return (self.rear + 1) % self.size == self.front
    
    q = Queue(5)
    for i in range(4):
    q.push(i)
    print(q.is_filled())
    
    print(q.pop())
    q.push(4)

栈和队列的应用问题 迷宫问题

深度优先搜索

回溯法 思路:从一个节点开始,任意找到下一个能走的点,当找不到能走的点时,退回上一个点寻找是否有其他方向的点.

广度优先搜索 思路:从一个节点开始,寻找所有接下来能继续走的点,继续不断寻找,直到找到出口.

链表

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

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

创建链表

头插法 尾插法

# __*__ coding=utf-8 __*__

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

def create_linklist(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 = create_linklist([1,2,3])
print_linklist(lk)
print(lk.item)

链表的插入

p.next = curNode.next
curNode.next = p

链表的删除

p = curNode.next
curNode.next = curNode.next.next
del p

双链表

双链表的每个节点有两个指针:一个指向后一个节点,另一个指向前一个节点

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

双链表的插入

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

链表–复杂度分析

顺序表与链表 * 按元素值查找 * 按下标查找 * 在某元素后插入 * 删除某元素

链表的插入和删除的操作明显快于顺序表 链表的内存可以更灵活的分配 链表这种链式存储的数据结构对树和图的结构有很大的启发性

哈希表

哈希表是一个通过哈希函数来计算数据存储位置的数据结构,通常支持操作: * insert(key,value):插入键值对(key,value) * get(key):如果存在键为key的键值对则返回其value,否则返回空值 * delete(key):产出键值为key的键值对

直接寻址表 当关键字的全域U比较小时,直接寻址是一种简单而有效的方法.

直接寻址表 + 哈希 = 哈希表

直接寻址表:key为k的元素放在k位置上 改进直接寻址表:哈希(Hashing) * 构建大小为m的寻址表T * key为k的元素放到h(k)位置上 * h(k)是一个函数,其将域U映射到表T[0,1,…,m-1]

哈希冲突 * 开放寻址法 * 拉链法

字典与集合都是通过哈希表来实现的

树与二叉树

一个基于树的简单文件系统的实现

class Node:
    def __init__(self,name,type='dir'):
        self.name = name
        self.type = type
        self.children = []
        self.parent = None

    def __repr__(self):
        return self.name

class FileSystemTree:
    def __init__(self):
        self.root = Node("/")
        self.now = self.root

    def mkdir(self,name):
        #name 以 / 结尾
        if name[-1] != "/":
            name += "/"
        node = Node(name)
        self.now.children.append(node)
        node.parent = self.now

    def ls(self):
        return self.now.children

    def cd(self,name):
        if name[-1] != "/":
            name += "/"
        for child in self.now.children:
            if child.name == name:
                self.now = child
                return
        raise ValueError("invalid dir.")



tree = FileSystemTree()
tree.mkdir("var/")
tree.mkdir("bin/")
tree.mkdir("usr/")

tree.cd("bin/")
tree.mkdir("python/")

print(tree.ls())

二叉树的实现

class BiTreeNode:
    def __init__(self,data):
        self.data = data
        self.lchild = None
        self.rchild = None

a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")

e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f

root = e
print(root.lchild.rchild.data)

##二叉树的遍历

二叉树的遍历方式: 截屏2021-01-04 下午4.11.47.png

  • 前序遍历:EACBDGF
  • 中序遍历:ABCDEGF
  • 后序遍历:BDCAFGE
  • 层次遍历:EAGCFBD

    #四种遍历方法的实现
    def pre_order(root):
    if root:
        print(root.data,end=",")
        pre_order(root.lchild)
        pre_order(root.rchild)
    #pre_order(root)
    
    def in_order(root):
    if root:
        in_order(root.lchild)
        print(root.data,end=",")
        in_order(root.rchild)
    #in_order(root)
    def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data,end=",")
    #post_order(root)
    
    def level_order(root):
    queue = deque()
    queue.append(root)
    while len(queue) > 0:
        node = queue.popleft()
        print(node.data,end=",")
        if node.lchild:
            queue.append(node.lchild)
        if node.rchild:
            queue.append(node.rchild)
    level_order(root)

二叉树的删除操作

  1. 如果要删除的节点是叶子节点:直接删除.
  2. 如果要删除的节点只有一个孩子,将此节点的父亲与孩子连接,然后删除该节点.
  3. 如果要删除的节点有两个孩子:将其右子树的最小节点(该节点最多有一个右孩子)删除,并替换当前节点.

    def __remove_node_1(self, node):
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:
            node.parent.lchild = None
        else:
            node.parent.rchild = None
    
    def __remove_node_2l(self, node):
        if not node.parent:
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent
        else:
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent
    
    def __remove_node_22(self, node):
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent

二叉搜索树的效率

平均情况下,二叉搜索树进行搜索的时间复杂度为O(lgn) 最坏情况下,二叉搜索树可能非常偏斜 解决方案: * 随机化插入 * AVL树

AVL树

AVL树是一棵自平衡的二叉搜索树 AVL树具有以下性质: * 根的左右子树的高度之差的绝对值不能超过1 * 根的左右子树都是平衡二叉树

  • 插入一个节点可能会破坏AVL树的平衡,可以通过 旋转操作进行修正

AVL插入:

不平衡是由于对K的右孩子的右子树插入导致的 – 左旋

不平衡是由于对K的左孩子的左子树插入导致的 – 右旋

不平衡是由于对K的右孩子的左子树插入导致的: 右旋-左旋

不平衡是由于对K的左孩子的右子树插入导致的: 左旋-右旋

github address:

https://github.com/chenbokaix250/ForSomeForMySelf

点击刷新