算法_数据结构基础

左手的ㄟ右手 2023-02-10 03:36 8阅读 0赞

# 数据结构基础 #

## 数组 ##

### 数组（array） ###

*  有限个相同类型的变量所组成的有序集合
 *  读取、更新元素的时间复杂度都是O(1)
 *  插入、删除元素的时间复杂度都是O(n)

### 链表（linked list） ###

*  在物理上非连续、非顺序的数据结构，由若干个节点组成
 *  单向链表：每个节点包含两部分，一部分是放数据的变量data，另一部分是指向下一个节点的指针next
 *  双向链表：每一个节点除了拥有data和next指针，还拥有前置节点的prev指针
 *  更新、插入、删除元素的时间复杂度都是O(1)
 *  读取的时间复杂度都是O(n)

### 跳表（skip list） ###

*  只能用于元素有序的情况
 *  跳表对标的是平衡树（AVL Tree）和二分查找，是一种 插入/删除/搜索 都是O(n log n)的数据结构
 *  空间复杂度O(n)

如何给有序的链表加速：一维的数据结构要加速通常采用的方式就是升维就是说变成二维

![../\_images/skiplist.png][.._images_skiplist.png]

*  表头（head）：负责维护跳跃表的节点指针。
 *  跳跃表节点：保存着元素值，以及多个层。
 *  层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
 *  表尾：全部由 `NULL` 组成，表示跳跃表的末尾。

### 练习 ###

[删除排序数组中的重复项][Link 1]

[盛最多水的容器][Link 2]

## 线性结构 ##

线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继

### 栈（Stack） ###

栈是一种有次序的数据项集合，在栈中，数据项的加入和移除都仅发生在同一端，一段叫栈“顶top”，另一端叫栈底“底base。距离栈底越近的数据项，留在栈中的时间就越长。次序安排的原则：”后进先出LIFO“ Last in First out，栈的反转类型

> 日常生活中栈的应用：盘子、托盘、书堆等

> 栈的应用：
> 
> 1.  将中缀表达式转换为后缀表达式，并且计算后缀表达式
> 2.  回溯算法
> 3.  管理计算机内存以支持函数和方法调用
> 4.  支持文本编辑器、字处理程序、电子表格程序、绘图程序或类似的应用程序中的撤销功能
> 5.  维护Web浏览器所访问过的连接的历史记录

#### 栈的相关操作 ####

![栈的相关操作][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center]

栈的实现：可以使用列表来模拟基于数组的栈

class Stack:
        def __init__(self):
            self.items = []
        def isEmpty(self):
            return self.items == []
        # O(1) 栈顶尾端
        def push(self, item):
            self.items.append(item)
        def pop(self):
            return self.items.pop()
        # O(n) 栈顶首端
        # def push(self, item):
        # self.items.insert(0, item)
        # def pop(self):
        # return self.items.pop(0)
        def peek(self):
            return self.items[len(self.items)-1]
        def size(self):
            return len(self.items)

#### 通用括号匹配算法 ####

def parChecker(symbolString):
        s = Stack()
        balanced = True
        index = 0
        while index < len(symbolString) and balanced:
            symbol = symbolString[index]
            if symbol in '([{':
                s.push(symbol)
            # 取右括号判断栈是否为空：为空，说明右括号多了，不为空，从栈顶移除
            elif symbol in ')]}':
                if s.isEmpty():
                    balanced = False
                else:
                    top = s.pop()
                    if not matches(top, symbol):
                        balanced = False
            index += 1
        if balanced and s.isEmpty():
            return True
        else:
            return False
    
    def matches(open, close):
        opens = '([{'
        closers = ')]}'
        return opens.index(open) == closers.index(close)
    
    print(parChecker('{ {[]()}}'))

#### 十进制转换为二进制 ####

“除以二”的过程，得到的余数是从低到高的次序，而输出则是从高到底，所以需要一个栈来反转次序  
![十进制转换二进制][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center 1]

def baseConverter(decNumber, base):
        digits = '0123456789ABCDEF'
        remstack = Stack()
        while decNumber > 0:
            rem = decNumber % base
            remstack.push(rem)
            decNumber = decNumber // base
        newString = ""
        while not remstack.isEmpty():
            newString = newString + digits[remstack.pop()]
        return newString
    print(baseConverter(25,2))

#### 表达式转换 ####

*  中缀表达式 A+B
 *  前缀表达式 +AB
 *  后缀表达式 AB+

中缀表达式转换后缀形式的处理过程中，操作符比操作数要晚输出，而这些暂存的操作符，由于优先级的规则，还有可能要反转次序输出，这种反转特性，使得我们考虑用栈来保存暂时未处理的操作符

> **中缀表达式转后缀算法流程：**
> 
>  *  首先，创建空栈opstack用于暂存操作符（\*-+/()）
>  *  空表postfixList用于保存后缀表达式
>  *  将中缀表达式转换为单词（tocken）列表
>  *  从左到右扫描中缀表达式单词列表
>  *  中缀表达式单词列表扫描结束后，把opstack栈中的所有剩余操作符依次弹出，添加到输出列表末尾
>  *  把输出列表再用join方法合并成后缀表达式字符串

![从左到右扫描][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center 2]

1.  如果单词是操作数，则直接天骄到后缀表达式列表的末尾
2.  如果单词是左括号“（”，则压入opstack栈顶
3.  如果单词是右括号“）”，则反复弹出opstack栈顶操作符，加入到输出列表末尾，直到碰到左括号
4.  如果单词是操作符“±\*/”，则压入opstack栈顶
    
     *  但在压入之前，要比较其与栈顶操作符的优先级
     *  如果栈顶的高于或等于它，就要反复弹出栈顶操作符，加入到输出列表末尾
     *  直到栈顶的操作符优先级低于它

def infixToPostfix(infixexpr):
        prec = { }
        prec['*'] = 3
        prec['/'] = 3
        prec['+'] = 2
        prec['-'] = 2
        prec['('] = 1
        opStack = Stack()
        postfixList = []
        tokenList = infixexpr.split()
        for token in tokenList:
            if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':
                postfixList.append(token)
            elif token == '(':
                opStack.push(token)
            elif token == ')':
                topToken = opStack.pop()
                while topToken != '(':
                    postfixList.append(topToken)
                    topToken = opStack.pop()
            else:
                while (not opStack.isEmpty()) and (prec[opStack.peek()]) >= prec[token]:
                    postfixList.append(opStack.pop())
                opStack.push(token)
        while not opStack.isEmpty():
            postfixList.append(opStack.pop())
        return ' '.join(postfixList)
    print(infixToPostfix('1 * 3 + 2 * 4')) # 1 3 * 2 4 * +

> 后缀表达式求值流程：
> 
> 1.  创建空栈operandStack用于暂存操作数
> 2.  将后缀表达式用split方法解析为单词（token）的列表
> 3.  从左到右扫描单词列表
>     
>      *  如果单词是一个操作数，将单词转换为整数int，压入operandStack栈顶
>      *  如果单词是一个操作符（\*/±），就开始求值，从栈顶弹出2个操作数，先弹出的s是右操作数，后弹出的是左操作数，计算后将值重新压入栈顶
> 4.  单词列表扫描结束后，表达式的值就在栈顶
> 5.  弹出栈顶的值，返回

def postfixEval(postfixExpr):
        operandStack = Stack()
        tokenList = postfixExpr.split()
        for token in tokenList:
            if token in '0123456789':
                operandStack.push(int(token))
            else:
                operand2 = operandStack.pop()
                operand1 = operandStack.pop()
                result = doMath(token,operand1,operand2)
                operandStack.push(result)
        return operandStack.pop()
    
    def doMath(op, op1, op2):
        if op == "*":
            return op1 * op2
        elif op == "/":
            return op1 / op2
        elif op == "+":
            return op1 + op2
        elif op == "-":
            return op1 - op2
    print(postfixEval('1 3 * 2 4 * +')) # 11

### 队列（Queue） ###

队列是一种有序的数据集合，当数据项加入队列，首先出现在队尾，随后队首数据项的移除，它逐渐接近队首。新加入的数据项必须在数据集末尾等待，而等待时间最长的数据则是队首。次序安排的原则：“先进先出FIFO”First in First out

> 日常生活中队列的应用：排队
> 
> 队列的应用：
> 
> 1.  打印队列
> 2.  进程调度（调度原则综合了“先到先服务”及“资源充分利用”）
> 3.  键盘缓冲

#### 队列的相关操作 ####

![队列操作][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center 3]

> enqueue 的复杂度是 O(n)，而 dequeue 的复杂度是 O(1)

队列的实现：可以使用列表来模拟基于数组的队列

class Queue:
        def __init__(self):
            self.items = []
        def isEmpty(self):
            return self.items == []
        def enqueue(self, item):
            self.items.insert(0, item)
        def dequeue(self):
            return self.items.pop()
        def size(self):
            return len(self.items)

#### 热土豆 ####

def hotPotato(namelist, num):
        simqueue = Queue()
        # 把namelist添加到队列中去 ps：从下标是0的位置开始添加，整个插入完成以后序列就反过来了
        for name in namelist:
            simqueue.enqueue(name)
        while simqueue.size() > 1:
            for i in range(num):
                # 从列表的末尾减去什么就把什么添加到列表开头
                simqueue.enqueue(simqueue.dequeue())
            # 哪个排最后哪个就是热土豆，直接出局
            simqueue.dequeue()
        return simqueue.dequeue()
    print(hotPotato(['Bill','David','Susan','Bili','Dell','Kin','Loken'], 7))

#### 打印任务 ####

对象

*  打印任务的属性：提交时间、打印页数
 *  打印队列的属性：具有FIFO性质的打印任务队列
 *  打印机的属性：打印速度、是否忙

> 流程：
> 
> 1.  确定**生成概率**：实例为每个小时会有10个学生提交20份作业，这样，概率是每180秒会有1个作业生成并提交，概率为**每秒1/180**
> 2.  确定**打印页数**：实例时120页，那么就是120页之间概率相同
> 3.  当前的打印作业：正在打印的作业；打印结束倒计时：新作业开始打印时倒计时，回0表示打印完成，可以处理下一个作业
> 4.  统一的时间框架：以最小单位（秒）均匀流逝的时间，设定结束时间
> 5.  同步所有的流程，在**一个时间单位**里，对**生成打印任务**和**实施打印**两个过程各处理一次
> 
> 按照概率生成打印作业，加入打印队列
> 
> 如果打印机空闲，且队列不空，则取出队首作业打印，记录次作业等待时间
> 
> 如果打印机忙，则按照打印速度进行1秒打印
> 
> 如果当前作业打印完成，则打印机进入空闲
> 
> 生成作业时，记录生成的时间戳
> 
> 开始打印时，当前时间减去生成时间即可
> 
> 生成作业时，记录作业的页数
> 
> 开始打印时，页数除以打印速度即可

import random
    
    class Printer:
        def __init__(self, ppm):
            # 打印速度
            self.pageRate = ppm
            # 打印任务
            self.currentTask = None
            # 任务倒计时
            self.timeRemaining = 0
    
        # 打印 1 秒
        def tick(self):
            if self.currentTask != None:
                self.timeRemaining -= 1
                if self.timeRemaining <= 0:
                    self.currentTask = None
    
        # 打印忙？
        def busy(self):
            if self.currentTask != None:
                return True
            else:
                return False
    
        # 打印新作业
        def startNext(self, newtask):
            self.currentTask = newtask
            self.timeRemaining = newtask.getPages() * 60 / self.pageRate
    
    class Task:
        def __init__(self, time):
            # 生成时间戳
            self.timestamp = time
            # 打印页数
            self.pages = random.randrange(1, 21)
    
        def getStamp(self):
            return self.timestamp
    
        def getPages(self):
            return self.pages
    
        def waitTime(self, currenttime):
            return currenttime - self.timestamp
    
    def newPrintTask():
        # 1/180 概率生成作业
        num = random.randrange(1, 181)
        if num == 180:
            return True
        else:
            return False
    
    def simulation(numSeconds,  pagesPerMinute):
        labprinter = Printer(pagesPerMinute)
        printQueue = Queue()
        waittingtimes = []
    
        for currentSecond in range(numSeconds):
            if newPrintTask():
                task = Task(currentSecond)
                printQueue.enqueue(task)
    
            if not labprinter.busy() and not printQueue.isEmpty():
                nexttask = printQueue.dequeue()
                waittingtimes.append(nexttask.waitTime(currentSecond))
                labprinter.startNext(nexttask)
    
            labprinter.tick()
    
        averageWait = sum(waittingtimes) / len(waittingtimes)
        print(f"Average Wait {averageWait:6.2f} secs {printQueue.size():3d} tasks remaining.")
    
    for i in range(10):
        simulation(3600, 5)

### 双端队列（Deque） ###

双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作 “首” “尾” 端。但Deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。某种意义上说，双端队列集成了栈和队列的能力

> 从头头添加或删除项目是O(1)，而从尾部添加或删除是O(n)

双端队列的实现

class Deque:
      def __init__(self):
        self.items = []
      def isEmpty(self):
        return self.items == []
      def addFront(self, item):
        self.items.append(item)
      def addRear(self, item):
        self.items.insert(0, item)
      def removeFront(self):
        return self.items.pop()
      def removeRear(self):
        return self.items.pop(0)
      def size(self):
        return len(self.items)

#### “回文词”判定 ####

“回文词”：正读和反读都一样的词

def palchecker(aString):
      chardeque = Deque()
      for ch in aString:
        chardeque.addRear(ch)
      stillEqual = True
      while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
          stillEqual = False
      return stillEqual
    
    print(palchecker('radar'))

### 列表（List） ###

一个数据项按照相对位置存放的数据集

*  采用链表 实现无序列表
 *  链表的基本模块是节点。节点类对象包含本身的项目数据和对下一个节点的引用

#### 无序列表 ####

链表实现：节点Node

> n个节点的链表，isEmpty方法复杂度是O(1)，只需检查链表的头指针是否为None
> 
> 除了遍历整个链表以外，没办法知道链表的节点数，size方法复杂度是O(n)
> 
> 无序列表add方法的复杂度是O(1)
> 
> search、remove、和有序列表的add，需要遍历，尽管在平均情况下，它们只需要遍历一半的节点，但复杂度都是O(n)

class Node:
      def __init__(self):
        self.data = data
        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

链表实现：无序表UnorderedList

*  链表结构只为我们提供了一个入口，即列表的头，所有其他节点只能通过访问第一个节点，然后通过下一个引用链接到那里
 *  遍历：有序地访问每一个节点，为了做到这点，我们可以使用一个外部引用，它最开始指向列表的第一个节点。每当我们访问一个节点时，我们通过“侧向移动”到下一个引用的方式，将外部引用移动到下一个节点

class UnorderedList:
      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 append(self, item):
        temp = Node(item)
        if self.isEmpty():
          self.head = temp
        else:
          current = self.head
          while current.getNext() != None:
            current = current.getNext()
          current.setNext(temp)
      # 求元素个数
      def size(self):
        current = self.head
        count = 0
        while current != None:
          count += 1
          current = current.getNext()
        return count
      # 索引元素在链表中的位置
      def index(self, item):
        current = self.head
        count = 0
        while current != None:
          if current.getData() == item:
            return count
          else:
            current = current.getNext()
          count += 1
        return False
      # 检索元素是否在链表中
      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())
      # 链表中插入元素
      def insert(self, index, item):
        if index <= 1:
          self.add(item)
        elif index > self.size():
          self.append(item)
        else:
          temp = Node(item)
          current = self.head
          count = 0
          while count < index:
            count += 1
            previous = current
            current = current.getNext()
          previous.setNext(temp)
          temp.setNext(current)

#### 有序列表 ####

isEmpty和size方法的实现和无序列表相同，因为它们只处理列表中的数量而不考虑节点实际的值。同样，remove方法也不需要改动，因为我们仍然需要找到某个节点然后删除它。剩下两个方法：search和add需要一些修改

为了在一个无序列表中搜索某个节点，我们需要遍历节点直到找到它或者遍历完 整个列表（None），当要搜索的元素在列表中时，可以在有序列表中使用与无序列表中相同的方法，但当我们要找的元素不在列表中时，我们可以利用有序列表的顺序尽快结束搜索

链表实现：序表OrderedList

class OrderedList:
        def __init__(self):
            self.head=None
        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 add(self,item):
            current=self.head
            previous=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)

## 参考链接 ##

*  [Java 源码分析（ArrayList）][Java _ArrayList]
 *  [Linked List 的标准实现代码][Linked List]
 *  \[Linked List 示例代码\](http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/code/LinkedList.java)
 *  [Java 源码分析（LinkedList）][Java _LinkedList]
 *  LRU Cache - Linked list：[ LRU 缓存机制][LRU]
 *  Redis - Skip List：[跳跃表][Link 3]、[为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？][Redis _Skip List_ Red-Black]

##  ##

[.._images_skiplist.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yZWRpc2Jvb2sucmVhZHRoZWRvY3MuaW8vZW4vbGF0ZXN0L19pbWFnZXMvc2tpcGxpc3QucG5n?x-oss-process=image/format,png
[Link 1]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[Link 2]: https://leetcode-cn.com/problems/container-with-most-water/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200519101627611.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200519183742410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200519185651397.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200520002458202.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70#pic_center
[Java _ArrayList]: http://developer.classpath.org/doc/java/util/ArrayList-source.html
[Linked List]: http://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/
[Java _LinkedList]: http://developer.classpath.org/doc/java/util/LinkedList-source.html
[LRU]: http://leetcode-cn.com/problems/lru-cache
[Link 3]: http://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
[Redis _Skip List_ Red-Black]: http://www.zhihu.com/question/20202931