【啃书】Python数据结构与算法分析(第二版)—基本数据结构

文章目录

引子

接下学习的栈、队列、双端队列、列表都是有序的数据集合，其元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来了，他的前后元素的相对位置将保持不变。这样的数据集合也被称之为线性数据结构

栈LIFO(last-in first-out)

定义

栈是一个有序集合，添加与移除操作都放在同一端，即顶端。栈中的元素离底部越近，代表其在栈中时间越长，因此栈的底部具有非常重要的意义。由于其先进后出的反转特性，在一些特定的场景有着应用，例如游览器的返回按钮。

用Python实现栈

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

    def isEmpty(self):
        return self.item == []

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

    def pop(self):
        return self.item.pop()

    def peek(self):
        """获取栈顶端的数，但是不删除"""
        return self.item[len(self.item) - 1]

    def size(self):
        return len(self.item)

匹配括号

from pythonds.basic import Stack


def func(str_data):
    s = Stack()
    balanced = True
    for i in str_data:
        if i == "(":
            s.push(i)
        else:
            if s.isEmpty():
                balanced = False
                return balanced
            else:
                s.pop()
    if not s.isEmpty():
        balanced = False
    return balanced


print(func("()()()()()"))  # True
print(func("())()()()"))  # False

将十进制数转化为任意进制

from pythonds.basic import Stack


def func(int_data, base):
    digits = "0123456789ABCDEF"
    obj = Stack()
    while int_data > 0:
        rem = int_data % base
        obj.push(rem)
        int_data //= base
    new_str = ""
    while not obj.isEmpty():
        new_str += digits[obj.pop()]
    return new_str


print(func(8, 2))  # 1000
print(func(45, 16))  # 2D=2*16+13

队列FIFO(first-in first-out)

队列是有序集合，添加操作发生在尾部，移除操作作用在头部。

用Python来实现队列

class Queue:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def enqueue(self, item):
        self.item.insert(0, item)

    def dequeue(self):
        return self.item.pop()

    def size(self):
        return len(self.item)

双端队列

双端队列与队列相似，不同的是双端队列在哪一端增添数据、移除数据没有加限制。某种角度上来说是栈与队列的结合。

用Python实现双端队列

class Deque:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def addFront(self, item):
        self.item.append(item)

    def addRear(self, item):
        self.item.insert(0, item)

    def removeFront(self):
        return self.item.pop()

    def removeRear(self):
        return self.item.pop(0)

    def size(self):
        return len(self.item)

回文检测——-就是一个字符串是否相互颠倒，例如：toot

from pythonds.basic import Deque


def func(astring):
    obj = Deque()
    for ch in astring:
        obj.addRear(ch)
    stillEqual = True
    while obj.size() > 1 and stillEqual:
        first = obj.removeFront()
        last = obj.removeRear()
        if first != last:
            stillEqual = False
            break
    return stillEqual


print(func("roor"))  # True
print(func("roo0r"))  # False
print(func("ro0or"))  # True

列表

无序列表

列表是元素的集合，其中每个元素都有一个相对其他元素相对的位置。例如：[22, 13, 44, 11, 77, 43]

通过链表实现无序列表

第一个元素很重要，每个元素都需要知道数据变量、下一个节点的引用，最后一个元素需要知道自己没有下一个元素。

列表类本真并不包含任何节点对象，而只是指向整个链表结构中第一个节点的引用。

class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None  # 最后一个元素末尾即终止

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newdata):
        self.data = newdata

    def setNext(self, newnext):
        self.next = newnext


class UnordefdList:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def length(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count

    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())