诺小新 | Neuerliu
0%

python数据结构与算法:(二)基本结构

Posted on In

1.线性结构(Linear Structure)

1.1 线性结构的定义

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

  • 第一个没有前驱，最后一个没有后继
  • 新的数据项加入到数据集中，只会加入到原有某个数据项之前或之后

1.2 线性结构的两端

线性结构有两端，称为左端、右端或者前端、后端。两端的称呼并不是关键，不同线性结构的关键区别在于数据项增减的方式。

  • 有的结构只允许数据项从一段添加，而有的结构则允许数据项从两端移除；有的结构允许数据项从中间插入、移除

依据数据项增减方式的不同，可以研究4种结构：

  • 栈(Stack)
  • 队列(Queue)
  • 双端队列(Deque)
  • 列表(List)

2.栈抽象数据类型及Python实现

2.1 栈的定义

栈是一种有次序的数据项集合，在栈中数据项的加入和移除都仅发生在同一端。一般加入/移除数据项的段称为栈顶(top)，另一端称为栈底(base)。

  • 距离栈底越近的数据项，留在栈中的时间越长—>这种次序被称为“**后进先出LIFO(Last in First out)**”

举例：访问网页的后退按钮，一般最先back的是最近的网页；Word中的撤销按钮也是针对最近的操作

2.2 抽象数据类型Stack

栈是一个有次序的数据集，每个数据项仅从栈顶一端加入、移除数据集中，栈具有后进先出的LIFO特性。

栈的定义包括如下方法：

方法 描述
Stack() 创建一个空栈，不包含任何数据项
push(item) 将item加入栈项，无返回值
pop() 从栈顶将数据项移除并返回移除值，栈被修改
peek() 窥视栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
isEmpty() 返回栈是否为空栈
size() 返回栈中有多少个数据项

2.3 用Python实现ADT Stack

ADT(Abstract Data Type, 抽象数据类型)，我们用python的列表类型实现，选用列表的末端(index = -1)作为栈顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Stack:
    def __init__(self):
        '''
        初始化Stack
        '''
        self.items = []
        
    def isEmpty(self):
        '''
        判断是否为空
        '''
        return self.items == []
    
    def push(self, item):
        '''
        添加新元素，无返回值
        '''
        self.items.append(item)
        
    def pop(self):
        '''
        移除元素，返回被移除元素
        '''
        return self.items.pop()
        
    def peek(self):
        '''
        窥视栈顶数据项
        '''
        return self.items[len(self.items) - 1]
    
    def size(self):
        '''
        查看栈的大小
        '''
        return len(self.items)

如果将index=0作为栈顶，同样可以实现上述功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Stack:
    def __init__(self):
        '''
        初始化Stack
        '''
        self.items = []
        
    def isEmpty(self):
        '''
        判断是否为空
        '''
        return self.items == []
    
    def push(self, item):
        '''
        添加新元素，无返回值
        '''
        self.items.insert(0, item)
        
    def pop(self):
        '''
        移除元素，返回被移除元素
        '''
        return self.items.pop(0)
        
    def peek(self):
        '''
        窥视栈顶数据项
        '''
        return self.items[0]
    
    def size(self):
        '''
        查看栈的大小
        '''
        return len(self.items)

2.4 栈的应用：简单括号匹配

  • 括号需要遵循平衡原则，即每个开括号要恰好对应一个闭括号，并且每一对括号要正确闭合。
  • 将其余字符去除，从左到右扫面括号构成的字符串，则最先遇到的左括号应该匹配最后遇到的右括号。这是一种次序反转，可以使用栈来处理。

括号匹配

2.5 进制转换

  • 进制：用多少个字符表示整数
  • 将十进制转化为二进制可以使用除法，不断除以2，通过余数得到各位的表示。最后的书写则需要反转这一过程，可以通过栈来实现。
  • 此外，还可以将十进制转换为十六以下任意进制

3.表达式转换

3.1 中缀表达式

  • 中缀表达式：操作符介于操作数中间的表示法，称为“中缀”表示法，例如：A+B*C
  • 人们通过引入操作符的优先级解决这个问题来消除混淆，通过引入括号来表示强制优先级
  • 计算机处理问题时最好能明确优先级，避免处理复杂的优先规则，引入全括号表达式—>将表达式加入括号，表示优先级

3.2 前缀和后缀表达式

实际上就是改变操作符的位置，以A+B为例：

  • 前缀表达式：将操作符移到前面，变为+AB
  • 后缀表达式：将操作符移到后面，变为AB+

前后缀表达式

在前缀、后缀表达式中，操作符的次序完全决定了运算次序，不再需要括号。

3.3 表达式转换

表达式转换1

表达式转换2

主要步骤如下：

  • 将中缀表达式转换为全括号形式
  • 将所有的操作符移动到子表达式所在的左括号(针对前缀情况)或者右括号处(针对后缀情况)，替代之，在删除所有的括号

3.3.1 中缀转后缀表达式

  • 在中缀表达式转换为后缀表达式的过程中，操作符比操作数要晚输出，因此需要暂存操作符
  • 暂存的操作符可能由于优先级的规则，需要反转次序输出—>考虑用栈存储操作符

通用算法：

  • 约定中缀表达式是由空格隔开的一系列单词(token)构成

    • 操作符单词包括：+-*/()
    • 操作数单词是单字母标识符A、B、C等

  • 创建空栈opstack用于暂存操作符，空表用于保存后缀表达式

  • 从左到右扫描中缀表达式单词列表
    转化为后缀表达式流程1

  • 中缀表达式单词列表扫描结束后，把opstack栈中所有剩余操作符一次弹出，添加到输出列表末尾

  • 把输出列表再用join方法合并成后缀表达式字符串

3.3.2 后缀转中缀表达式

此时操作符在操作数的后面，因此需要暂存操作数，碰到操作符时将栈顶的操作符弹出进行运算

转化为中缀表达式1

3.队列抽象数据类型及Python实现

3.1 队列的定义

队列(Queue)是一种有次序的数据集合，特征是：

  • 新数据项的添加总发生在一端，通常称为尾端(rear)

  • 现存数据项的移除总发生在另一端，通常称为首端(front)

  • 新加入的数据项必须在数据集末尾等待，等待时间最长的数据项则是队首，这种次序被称为先进先出(FIFO, First In First Out)

队列的例子是排队，队列只有一个入口和出口。

3.2 抽象数据类型Queue

抽象数据类型Queue由如下操作定义：

方法 描述
Queue() 创建一个空队列，返回值为Queue对象
enqueue() 将数据项item添加到队尾，无返回值
dequeue() 从队首移除数据项，返回队首数据项
isEmpty() 测试队列是否为空队列，返回值为布尔值
size() 返回队列中数据项个数

3.3 队列问题：热土豆问题

热土豆问题(约瑟夫问题)：传烫手的热土豆，鼓声停的时候，手里有土豆的小孩就要出列。如果去掉鼓，改为传过固定人数，就成了现代版约瑟夫问题。

队列_热土豆问题

3.4 队列应用：打印任务

  • 场景：多人共享一台打印机，采取“先到先服务”的队列策略来执行打印任务

  • 打印模式有两种：草稿模式，质量低，每分钟10页；正常模式，质量高，每分钟5页

  • 问题是如何在大家等待时间不会太久的前提下实现尽可能高质量的打印？—> 决策支持问题

3.4.1 问题建模

  • 对象：打印任务、打印队列、打印机
    • 打印任务属性：提交任务时间、打印页数
    • 打印队列的属性：具有FIFO性质的打印任务队列
    • 打印机属性：打印速度、是否忙
  • 过程
    • 生成和提交打印任务：此时每180s有一个打印任务，打印页数在1~20页之间满足均匀分布，打印速度为5页/s
    • 实施打印：新作业在打印时开始倒计时，回0表示打印完毕，可以处理下一个作业
    • 模拟时间：以s的形式均匀流逝，同时在一个时间单位中对生成打印任务和实施打印两个过程各处理一次

打印机任务流程

  • 作业的等待时间
    • 生成作业时，记录生成的时间戳
    • 开始打印时，当前时间减去生成时间即可
  • 作业打印时间
    • 生成作业时，记录作业的页数
    • 开始打印时，页数除以打印速度即可

4.双端队列抽象数据类型及Python实现

4.1 双端队列的定义

双端队列(deque)两端可以称作首尾，数据项既可以从两端加入，也可以从两端移除。从某种意义上，双端队列同时具有栈、队列的特性。

4.2 抽象数据类型Deque

双端队列包括以下功能：

方法 描述
Deque() 初始化
isEmpty() 判断双端队列是否为空
addRear(item) 尾部添加元素
addFront(item) 首部添加元素
size() 双端队列大小
removeRear() 尾部元素移除
removeFront() 首部元素移除

4.3 双端队列Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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)

应用：判断回文词

5.无序表抽象数据类型和Python实现

5.1 无序表的定义

数据项按照相对位置存放的数据集，称为无序表(unordered list)，实际上就是list。

5.2 采用链表实现无序表

虽然列表数据结构要求保持数据项的前后相对位置，但这种前后位置的保持并不要求数据项一次存放在连续存储空间中。

无序列表1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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:
    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 size(self):
        '''
        链表大小
        '''
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()

        return count

    def search(self, item):
        '''
        寻找指定数据项item
        '''
        current = self.head #当前节点
        found = False #是否找到
        while current != None and not found:
            if current.data == item:
                found = True
            else:
                current = current.getNext()

        return found

    def remove(self, item):
        '''
        删除指定数据项item
        '''    
        current = self.head #当前节点
        previous = None #前一个节点
        found = False #是否找到
        while not found:
            if current.data == item:
                if previous != None:
                    previous.setNext(current.getNext())
                else:
                    self.head = current.getNext()

                found = True
            else:
                previous = current
                current = current.getNext()

6.有序表抽象数据类型及Python实现

6.1 有序表的定义

有序表是一种数据项依照其某科比性质(如整数大小、字母表先后)来决定在列表中的位置

有序表操作

6.2 采用链表实现有序表

  • 实现有序表时，需要记住的是数据项的相对位置取决于它们之间的“大小”比较。我们可以定义__gt__方法，就可以应用>比较自定义的数据类型。
  • 对于isEmpty/size/remove方法，与节点次序无关，实现和之前的无序表一致；search/add需要修改

小结

线性结构是指数据项以某种线性次序组织起来

  • 栈Stack维持了数据项后进先出(LIFO)的次序，基础操作包括：push、pop、isEmpty
  • 队列Queue维持了数据项先进先出(FIFO)的次序，基础操作包括：enqueue、dequeue、isEmpty
  • 双端队列Deque同时具备栈和队列的功能
  • 列表List是数据项能够维持相对位置的数据集
  • 链表的实现可以保持列表维持相对位置的特点，而不需要连续的存储空间

案例总结：

  • 书写表达式的方法有前缀prefix、中缀infix、后缀postfix三种，由于栈结构具有次序反转的特性，所以栈结构适合用于开发表达式求值和转换算法。

  • 模拟系统通过对现实问题进行抽象建模，加入随机数动态运行，为复杂问题的决策提供依据。队列queue可以用来进行模拟系统的开发。

线性表、链表、顺序表

顺序存取vs随机存取

区分两个概念，存储方式和存取方式：存储方式是指数据在内存中的布局，若连续布局则是顺序存储，若布局没有物理结构的相关性，则可能是链式存储。

  • 顺序存储由于物理结构上的相关性，则访问数据时可以随机访问，因此是随机存取；
  • 链式存储由于物理结构上不具备相关性，则访问数据需要从链表头节点开始，因此是顺序存取

多重链表、二叉链表

多重链表_二叉链表

问题解答

  • 判断：栈的pop操作时间复杂度为O(n)

    答：错误。栈的pop操作时间复杂度取决于栈的具体实现，可能是O(n)，也可能是O(1)。

  • 如何打印输出一个类？

    答：可以定义其中的__str__和__repr__特殊方法实现，在执行print(<类名>)实现打印类的自定义信息。