Freedom_ATX's Blog
0%

常见数据结构及算法（python实现）

发表于 更新于 分类于 ，

1 线性结构

特点：内存连续，可根据下标访问

1.1 链表

1.1.1 单链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

img

  • 表元素域elem用来存放具体的数据。
  • 链接域next用来存放下一个节点的位置（python中的标识）
  • 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

综上所述，单链表的实现主要包含两个部分：1. 单链表的实现 2. 单链表中每一个节点的实现

节点实现

class SingleNode(object):
    """单链表的结点"""
    def __init__(self, item):
        # _item存放数据元素
        self.item = item
        # _next是下一个节点的标识
        self.next = None

单链表的操作

  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历整个链表
  • add(item) 链表头部添加元素
  • append(item) 链表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 删除节点
  • search(item) 查找节点是否存在

链表的实现

class SingleLinkList(object):

    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        """链表是否为空"""
        return self.__head is None

    def length(self):
        """链表长度"""
        cur = self.__head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        while cur is not None:
            print(cur.item, end=" ")
            cur = cur.next

    def append(self, item):
        """尾部插入节点"""
        node = SingleNode(item)
        if self.is_empty():
            self.__head = node  # 如果是空链表，那么直接把头指针只向node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

1.2 栈

简介

栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

img

栈的操作

  • Stack() 创建一个新的空栈
  • push(item) 添加一个新的元素item到栈顶
  • pop() 弹出栈顶元素
  • peek() 返回栈顶元素
  • is_empty() 判断栈是否为空
  • size() 返回栈的元素个数

代码实现

#!/usr/bin/env python
# -*-coding:utf8-*-


class Stack(object):

    def __init__(self):
        self.__list = []

    def push(self, item):
        """添加一个新的元素item到栈顶"""
        self.__list.append(item)
        # 使用顺序表的时候从尾部操作，
        # 因为顺序表对尾部操作的时间复杂度为o(1), 对头部操作的时间
        # 复杂度为o(n)

    def pop(self):
        """弹出栈顶元素"""
        return self.__list.pop()

    def peek(self):
        """返回栈顶元素"""
        if self.__list:
            return self.__list[-1]
        else:
            return None

    def is_empty(self):
        """判断栈是否为空"""
        return not self.__list

    def size(self):
        """返回栈的元素的个数"""
        return len(self.__list)


if __name__ == '__main__':
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

1.3 队列

简介

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

img

队列操作

  • Queue() 创建一个空的队列
  • enqueue(item) 往队列中添加一个item元素
  • dequeue() 从队列头部删除一个元素
  • is_empty() 判断一个队列是否为空
  • size() 返回队列的大小

代码实现

#!/usr/bin/env python
# -*-coding:utf8-*-


class Queue(object):
    """队列"""

    def __init__(self):
        self.__list = []

    def enqueue(self, item):
        """往队列中添加一个item元素"""
        self.__list.append(item)

    def dequeue(self):
        """从队列头部删除元素"""
        return self.__list.pop(0)

    def is_empty(self):
        """判断是否为空"""
        return not self.__list

    def size(self):
        """返回队列的大小"""
        return len(self.__list)


if __name__ == '__main__':
    s = Queue()
    s.enqueue(1)
    s.enqueue(2)
    s.enqueue(3)
    s.enqueue(4)
    print(s.dequeue())
    print(s.dequeue())
    print(s.dequeue())
    print(s.dequeue())

1.4 双端队列

介绍

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

img

操作

  • Deque() 创建一个空的双端队列
  • add_front(item) 从队头加入一个item元素
  • add_rear(item) 从队尾加入一个item元素
  • remove_front() 从队头删除一个item元素
  • remove_rear() 从队尾删除一个item元素
  • is_empty() 判断双端队列是否为空
  • size() 返回队列的大小

代码

#!/usr/bin/env python
# -*-coding:utf8-*-


class Dequeue(object):
    def __init__(self):
        self.__list = []

    def add_front(self, item):
        """从头部往队列中添加元素"""
        self.__list.insert(0, item)

    def add_end(self, item):
        """从尾部往队列中添加元素"""
        return self.__list.append(item)

    def pop_front(self):
        """从头部取元素"""
        return self.__list.pop(0)

    def pop_end(self):
        """从尾部取元素"""
        return self.__list.pop()

    def is_empty(self):
        """判断是否为空"""
        return not self.__list

    def size(self):
        """返回队列的大小"""
        return len(self.__list)

2. 常见排序算法

2.1 冒泡排序

def bubble_sort(array):
    for i in range(len(array) - 1):
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

2.2 选择排序

def select_sort(array):
    for i in range(len(array) - 1):
        min_index = i
        for j in range(i + 1, len(array)):
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]
    return array

2.3 插入排序

def insert_sort(array):
    if len(array) < 2:
        return array
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j+1] = array[j]
            j -= 1
        array[j + 1] = key
    return array

2.4 归并排序

def merge_sort(array):
    if len(array) < 2:
        return array
    mid = len(array) // 2
    left_li = merge_sort(array[:mid])
    right_li = merge_sort(array[mid:])

    l_pointer, r_pointer = 0, 0
    result = []
    while l_pointer < len(left_li) and r_pointer < len(right_li):
        if left_li[l_pointer] < right_li[r_pointer]:
            result.append(left_li[l_pointer])
            l_pointer += 1
        else:
            result.append(right_li[r_pointer])
            r_pointer += 1
    result += left_li[l_pointer:]
    result += right_li[r_pointer:]
    return result

2.5 快速排序

def quick_sort(array):
    if len(array) < 2:
        return array
    mid = array[0]
    left, right = list(), list()
    array.pop(0)
    for item in array:
        if item < mid:
            left.append(item)
        else:
            right.append(item)
    return quick_sort(left) + [mid] + quick_sort(right)

2.6 排序算法复杂度比较

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 o(n^2) o(n) o(n^2) o(l) 稳定
选择排序 o(n^2) o(n^2) o(n^2) o(l) 不稳定
插入排序 o(n^2) o(n) o(n^2) o(l) 稳定
希尔排序 o(nlogn) ~ o(n^2) o(n^1.3) o(n^2) o(l) 不稳定
堆排序 o(nlogn) o(nlogn) o(nlogn) o(l) 不稳定
归并排序 o(nlogn) o(nlogn) o(nlog) o(n) 稳定
快速排序 o(nlogn) o(nlogn) o(n^2) o(logn) ~ o(n) 不稳定

欢迎关注我的其它发布渠道