数据结构与算法复习（一）

1. 数据结构

1.1 堆栈(Stack)

后进先出(LIFO, Last In First Out)

class Stack():
    """
    栈的实现
    如果使用 python 模块提供的数据结构
        from pythonds.basic.stack import Stack
    """
    def __init__(self): # 初始化
        self.stack = []

    def isEmpty(self): # 判空
        return self.statck == []

    def push(self, item): # 进栈
        self.stack.append(item)

    def pop(self): # 出栈
        self.stack.pop()

    def peek(self): # 返回栈顶项目
        if not self.isEmpty():
            return self.stack[-1]
                

1.2 队列、双端队列(Queue)

先进先出(FIFO, First In First Out), 通常使用链表或者数组来实现。

class Queue():
    """
    队列的实现
    如果使用 python 模块提供的数据结构
        from pythonds.basic.queue import Queue
    """
    def __init__(self): # 初始化
        self.queue = []

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

    def enqueue(self): # 入队
        self.queue.insert(0, item)

    def dequeue(self): # 出队
        self.queue.pop()

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


class Deque():
    """
    双端队列的实现
    如果使用 python 模块提供的数据结构
    from pythonds.basic.deque import Deque
    """
    def __init__(self):
        self.deque = []

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

    def add_front(self, item):
        self.deque.append(item)

    def remove_front(self):
        self.deque.pop()

    def add_rear(self):
        self.deque.insert(0, item)

    def remove_rear(self):
        self.deque.remove(self.deque[0])

1.3 链表(Linked List)

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表实现的基本构造块是节点(Node)。

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 UnorderedList:
    """
    无序列表的 python 实现
    """
    def ___init__():
        self.head = None

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

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

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = 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())

有序列表

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

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

        def add(self, item):
            current = self.head # 从头结点开始查询
            previous = None # 记录前一个节点，头节点的前一个节点为 None
            stop = False
            while current != None and not stop: # 查找到可以插入的位置，跳出循环
                if current.getData() > item:
                    stop = True
                else:
                    previous = current # 更新前一个节点
                    current = current.getNext() # 查找下一个节点
            
            temp = Node(item) # 创建新节点
            if previous == None: # 插入在头结点位置
                temp.setNext(self.head)
                self.head = temp
            else: # 插入在中间或者尾部
                temp.setNext(current)
                previous.setNext(temp)

        def search(self, item):
            # 包含查询、传入值，返回该值在链表中是否存在
            current = self.head
            found = False
            stop = False
            while current != None and not found and not stop:
                if current.getData() == item:
                    found = True
                else:
                    if current.getData() > item:
                        stop = True
                    else:
                        current = current.getNext()
            
            return found
        
        def remove(self, item):
            current = self.head
            previous = None

            while current != None:
                if current.getData() == data:
                    break
                previous = current.getNext()
            
            if previous == None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())