1 | 对应本书第三章。 |
3. Basic Data Structures
笔记
本章主要介绍一些抽象数据类型(ADT):栈stack/队列Queue/双向队列Deque/无序链表Unsordered List/有序链表Sordered List。
栈stack
用内置的list实现:
1 | class Stack: |
典型应用:
- 括号平衡检查 Parentheses Balance Checker
- 数字进制转换 Converting Decimal Numbers to Binary Numbers
- 中缀,前缀,后缀表达式 Infix, Prefix and Postfix Expressions
队列Queue
用内置的list实现:
1 | class Queue: |
典型应用:
- 击鼓传花 Hot Potato Simulation
- 打印机任务模拟 Printing Tasks Simulation
双向队列Deque
用内置的list实现:
1 | class Deque: |
典型应用:
- 回文检查 Palindrome-Checker
无序链表Unsordered List
用内置的list实现:
1 | class Node: |
有序链表Sordered List
用内置的list实现:
1 | class OrderedList: |
作业
q1
修改infix-to-postfix算法使其可以处理异常情况。
分析:异常情况可能是括号不平衡,也可能是缺少操作符或者缺少操作数。
括号不平衡可以方便地在中缀转后缀的函数中添加,但是操作符和操作数的检查可以留到计算的步骤再去检查,这步留在q2实现。
1 | # q1 |
1 | A B * C D * + |
q2
实现后缀表达式求值函数中对操作符和操作数的检查
1 | def postfixEval(postfixExpr): |
1 | 3.0 |
1 | print(postfixEval('7 8 + 3 2 + / 1')) |
1 | --------------------------------------------------------------------------- |
q3/q4
将q1和q2合并,写一个直接根据中序表达式的函数,q4要求把q3改成一个计算器。个人以为q3和q4相似,直接写成一处。
1 | # q3/q4 |
1 | -0.08888888888888889 |
1 | print(cal.calc("( 1 + 3 ) / ( ( 3 - 8 ) * 9 ) 9 ")) |
1 | --------------------------------------------------------------------------- |
q5
实现Queue,使得队尾是list的末尾
1 | class Queue2: |
1 | 2 |
q6
设计实验,对比两种Queue实现的优劣
1 | def queue1_en_test(): |
1 | from timeit import Timer |
1 | queue1_en_test: 0.49930859899995994 milliseconds |
从理论分析可以知道,如果进队操作设置在list起点,那么入队操作是$O(n)$,出队操作是$O(1)$;
相反,如果进队操作设置在list末端,那么入队操作是$O(1)$,出队操作是$O(n)$。
但是为什么在测试中综合第二种的性能比第一种的好呢?
看一下下面的测试:
1 | def list_append_test(): |
1 | list_append_test: 0.09044601999994484 milliseconds |
也就是说list的append比pop快,虽然都是$O(1)$;而且,del也比insert快,虽然都是$O(n)$。
因此第二种实现更好。
q7
实现是个enqueue和dequeue都是$O(1)$的Queue。
这道题我没有想出来,于是在stackoverflow上找到了一个双栈的实现方法。只有在outbox空的时候,把所有inbox出栈,再入outbox栈,这里的时间复杂度是$O(n)$。正好符合作者的要求。
1 | # q7 |
1 | 1 |
q8
设计一个现实生活中的使用场景,模拟队列。
这里设计一个理发师和顾客的场景。
1 | class Barber(): |
q9
修改hot potato 算法,使每次传递的个数为一个随机数
1 | import random |
1 | Susan |
q10
实现一个基数排序器,参考wikipedia的Radix_sort。
wikipedia的example:
1 | An example[edit] |
简单的说,就是每比一位排一次序。
1 | # q10 |
1 | 3 |
q11
html匹配检测
1 | import re |
1 | html is balance ! |
1 | html_str += "<a>" |
1 | html is not closed, please check ! |
1 | html_str = "<a></b>" |
1 | html is not balace, check : b |
q12
改写回文检测的代码,使得有空格也可以检测(忽略空格)。
1 | # q12 |
1 | False |
q13/q14/q15/q16/q17/q18/q19
- q13 修改UnorderedList类,增加一个变量保存链表的长度,获取长度的时候不用再遍历。
- q14 修改remove方法,使得元素不存在时的情况也能处理。
- q15 允许UnorderedList中存在重复的元素。代码无修改,会影响后面的index方法。
- q16/q17 实现str方法。
- q18 实现UnorderedList的append, index, pop, insert方法。
- q19 实现UnorderedList的切片。
1 | # q13/q14/q15/q16/q17/q18 |
1 | ul = UnorderedList() |
1 | 2 |
1 | # q14 |
1 | item not found in the list! |
1 | # q16/q17 |
1 | 3 |
1 | # q18 |
1 | [3,2,1,3,5,4] |
1 | # q18 |
1 | [0, 3] |
1 | # q18 |
1 | [3,2,1,3,5,4] |
1 | ul.insert(0, 3) |
1 | [3,3,2,3,5] |
1 | print(ul.size()) |
1 | 7 |
1 | for node in ul[0:3]: |
1 | 3 |
q20
完善OrderedList的实现
1 | class OrderedList: |
q21
考虑写一个Unordered list和 Ordered list 的父类,使得二者相同的操作可以在父类中实现。
相同的操作有:
pop size isEmpty
此题代码省略。
q22
用链表实现一个stack
1 | class Stack2: |
q23
用链表实现一个queue
1 | class Queue2: |
q24
用链表实现一个deque
1 | class Deque2: |
q25
设计实验对比链表和python内置list的性能。
1 | def list_test(): |
1 | from timeit import Timer |
1 | list : 0.020239962999767158 milliseconds |
q26
设计实验对比两种stack和queue的实现的性能。
1 | def stack_1_test(): |
1 | t11 = Timer("stack_1_test()", "from __main__ import stack_1_test") |
1 | stack 1: 0.005089294999834237 milliseconds |
q27
设计一个双向连接的链表。
1 | class Node2: |
q28
设计一个入队和出队时间复杂度都是O(1)的queue。
参考q7