Ethan's Blog

记录和思考

常用数据结构及其在 Python 中的实现

发表于: 分类: Tech 热度:

常用的数据结构：

  • 数组
  • 堆栈
  • 队列
  • 链表
  • 树
  • 图
  • 字典树（Tries，这是一种高效的树，有必要单独列出来）
  • 哈希表

本文记录常用的数据结构和在 Python 中的体现和使用。

数组

数组是最简单和广泛使用的数据结构，基本的构成是索引 - 值，数组中的每个元素会分配到一个整数值，这个值对应元素在数组中的位置。大部分编程语言索引都是从 0 开始。Python 的初始索引也是 0。数组分为一维数组和多维数组。

数组的基本操作

  • Insert —— 在给定索引位置插入一个元素 array.insert(index, val)
  • Get —— 返回给定索引位置的元素 array[index]
  • Delete —— 删除给定索引位置的元素 array.pop(index)
  • Size —— 获取数组内所有元素的总数 len(array)

在 Python 中的实现

主要体现在列表（list）这一数据类型。

堆栈

可以把堆栈看成一堆垂直排列的书籍，为了获取中间的书本，需要拿到其上方的所有书籍。因此，堆栈是 “先进后出，后进先出，LIFO” 的原则。

堆栈

堆栈的基本操作

  • Push —— 在顶部插入元素
  • Pop —— 从堆栈中删除后返回顶部元素
  • isEmpty —— 如果堆栈为空，则返回 true
  • Top —— 返回顶部元素，但不从堆栈中删除

在 Python 中的实现

class Stack:
    """ Stack ADT, using a python list
    Stack()
    isEmpty()
    length()
    pop(): assert not empty
    top(): assert not empty, return top of non-empty stack without removing it
    push(item)
    """
    def __init__(self):
        self._items = list()

    def isEmpty(self):
        return len(self) == 0

    def __len__(self):
        return len(self._items)

    def top(self):
        assert not self.isEmpty()
        return self._items[-1]

    def pop(self):
        assert not self.isEmpty()
        return self._items.pop()

    def push(self, item):
        self._items.append(item)

队列

队列也是一种线性数据结构，以顺序方式存储元素。队列和堆栈的最大区别是队列是 “先进先出，First in First Out，FIFO” 原则。队列可以理解为一个排队买票的队伍，先来的先买到票，后来的站到队尾。

堆栈

队列的基本操作

  • Enqueue() —— 向队列末尾插入元素
  • Dequeue() —— 从队列头部移除元素
  • isEmpty() —— 如果队列为空，则返回 true
  • Top() —— 返回队列的第一个元素

在 Python 中的实现

class Queue:
    """ Queue ADT, use list。list实现，简单但是push和pop效率最差是O(n)
    Queue()
    isEmpty()
    length()
    enqueue(item)
    dequeue()
    """
    def __init__(self):
        self._qList = list()

    def isEmpty(self):
        return len(self) == 0

    def __len__(self):
        return len(self._qList)

    def enquue(self, item):
        self._qList.append(item)

    def dequeue(self):
        assert not self.isEmpty()
        return self._qList.pop(0)

链表

链表是一个重要的线性数据结构，像一个节点链，每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，指向链表的第一个元素，如果链表为空，则指向 null 或者不指向任何内容。链表包括单链表、双链表、复杂链表等。

链表

链表的基本操作

  • InsertAtEnd —— 在链表末尾插入指定元素
  • InsertAtHead —— 在链表头部插入指定元素
  • Delete —— 从链表中删除指定元素
  • DeleteAtHead —— 删除链表的第一个元素
  • Search —— 返回链表中的指定元素
  • isEmpty —— 如果链表为空，返回 true

在Python中的实现

# 单链表实现
class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

树

树是一种层级数据结构，包含了连接它们的顶点（节点）和边。树和图很相似，但二者有个很大的不同点，即树中没有循环。

树

几种类型的数

  • N 叉树
  • 平衡树
  • 二叉树
  • 二叉搜索树
  • 平衡二叉树
  • 红黑树
  • 2-3 树

其中，二叉树和二叉搜索树是最常用的树。

图

图就是一组节点，以网络的形式互相连接。节点也被称为顶点（vertices）。一对（x,y）就叫做一个边，表示顶点 x 和顶点 y 相连。一个边可能包含权重 / 成本，显示从顶点 x 到 y 所需的成本。

图的类型：无向图、有向图。在编程语言中，图可以表示为两种形式：邻接矩阵、邻接列表。

图

字典树（比较特殊，单列出来）

字典树，也叫 “前缀树”，是一种树形结构，在解决字符串相关问题中非常高效。其提供非常快速的检索功能，常用于搜索字典中的单词，为搜索引擎提供自动搜索建议，甚至能用于 IP 路由选择。

下面展示了 “top”“thus” 和 “their” 这三个词是如何存储在字典树中的：

字典树

哈希表

散列是一个用于唯一标识对象并在一些预先计算的唯一索引（称为 “密钥”）存储每个对象的过程。因此，对象以 “键值” 对的形式存储，这些项的集合被称为 “字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构，但最常用的数据结构是哈希表。

哈希表通常使用数组实现。哈希数据结构的性能取决于以下三个因素：哈希函数、哈希表的大小、碰撞处理方法。

哈希表

参考资料：
https://www.zhihu.com/question/28580777
https://python-web-guide.readthedocs.io/zh/latest/algorithms/algorithms.html#advanced-linked-lists

相关文章：