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

常用的数据结构:

  • 数组
  • 堆栈
  • 队列
  • 链表
  • 字典树(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

相关文章: