基本数据结构

发表于 | 更新于 | 分类于 | 评论数：

python内置的数据结构

事实上python内置的两种结构是及其先进且易用的.

list

  • 增加元素

    • append(x) 添加元素
    • extend(l) 将l中所有元素添加入其中
    • insert(i, x) 在i处添加元素x

  • 删除元素

    • remove(x) 删除元素x,若没有该元素会出现ValueError
    • pop([i]) 删除i处元素(默认最后一个),并返回这个元素
    • clear() 删除所有元素

  • 查找元素

    • index(x[, start[, end]]) 寻找x,返回其位置k,其中 $start \leq k < end$.(同样有ValueError错误)
    • count(x) 统计x出现的次数

  • 修改

    • sort() 排序
    • reverse() 倒序

  • 其他

    • copy() 返回一个一样的list

dict

  • 添加元素

    • update(dict2) 将dict2加入其中

  • 删除元素

    • popitem() 随机删除一对,并返回(key, value)
    • pop(key [,default]) 删除key及对应的值,并返回值,若不存在则返回default
    • clear() 删除所有元素

  • 查看键或值

    • keys() 返回所有键的列表
    • values() 返回所有值的列表
    • item() 返回由(key, value)组成的列表
    • has_key(key) 查找是否存在该键
    • dict.get(key, default=None) 返回值,不存在则返回default

  • 其他

    • copy()
    • fromkeys(seq[, value]) 以seq为键,value为值建一个字典,其中value默认为None

线性数据结构

每个元素的前后元素始终保持不变数据结构被称为线性数据结构.

常见的有: 栈,队列,双向队列,列表.

栈(stack)

其特点是后进先出(LIFO, Last In First Out).

栈的抽象数据类型

  • Stack() 创建一个空的新栈,并返回一个空栈.
  • push(x) 将x添加到栈的顶部.
  • pop() 从栈中删除顶部的元素,并返回这个元素.
  • peek() 从栈返回顶部元素，但不会删除它.
  • isEmpty() 返回栈是否为空.
  • size() 返回栈中的元素的数量.

栈的python实现

这里仅为我个人的实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

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

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

    def peek(self):
        return self.stack[self.size() - 1]

    def isEmpty(self):
        return self.size() == 0

栈的实际用处

括号匹配

每次看到栈,就免不了括号匹配这个问题.

对于合法的括号嵌套,总是一层一层的,这意味着栈可以很好的保存它们.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def par_checker(s):
    par = Stack()
    flag = True
    for c in s:
        if c == '(':
            par.push(c)
        else:
            if par.isEmpty():
                flag = False
                break
            else:
                par.pop()

    if not par.isEmpty():
        flag = False

    return flag

print(par_checker("(())"))
print(par_checker("()"))
print(par_checker("(()"))
print(par_checker("(())("))

输出结果:

1
2
3
4
True
True
False
False

符号匹配

比刚刚的难度要大一些,这里需要匹配的还有[]和{}.

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
def par_checker_2(s):
    par = Stack()
    flag = True
    for c in s:
        if c in "([{" :
            par.push(c)
        else:
            if par.isEmpty():
                flag = False
                break
            else:
                top = par.pop()
                match = top + c
                if match not in "()[]{}":
                    flag = False
                    break

    if not par.isEmpty():
        flag = False

    return flag

print(par_checker_2("[](){}"))
print(par_checker_2("([)]"))
print(par_checker_2("({[]}){()}"))
print(par_checker_2("(()[])"))

简单的修改即可,输出结果:

1
2
3
4
True
False
True
True

十进制转二进制

转进制通常使用除法,且每次的余数恰好是从左到右.

用下标表示进制,那么:

$$150_{(10)} = 10010110_{(2)}$$

1
2
3
4
5
6
7
8
9
10
11
12
def base_2_converter(x):
    s = Stack()
    while x != 0:
        re = x % 2 #余数
        s.push(re)
        x //= 2
    s2 = ""
    while not s.isEmpty():
        s2 += str(s.pop())
    return s2

print(base_2_converter(150))

可惜这个程序不能转换0.

如果是其他进制(16以下),可以写一个统一的程序:

1
2
3
4
5
6
7
8
9
10
11
def base_converter(x, base = 2):
    dig = "0123456789ABCDEF"
    s = Stack()
    while x != 0:
        re = x % base #余数
        s.push(re)
        x //= base
    s2 = ""
    while not s.isEmpty():
        s2 += dig[s.pop()]
    return s2

中缀表达式转后缀表达式(前缀表达式)

中缀表达式转后缀表达式

这里有简单的案例,后缀和前缀不需要括号就能表明计算的顺序.

中缀表达式 后缀表达式 前缀表达式
5 + 6 5 6 + + 5 6
5 + 6 * 8 5 6 8 * + + 5 * 6 8
(5 + 6) * 8 5 6 + 8 * * + 5 6 8

可以看到,三种表达式的数字顺序都没有改变,也就是说只有运算符发生了变化.因此,转换时可以直接保存数字,而将运算符全都压入栈中,利用优先级决定弹出的顺序.

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
def infix2postfix (infixStr):
    priority = {"+":1, "-":1, "*":2, "/":2, "(":0, ")":4, "@":0}
    postfixList = []
    num = 0; numFlag = False
    opsta = Stack()
    for c in infixStr:
        # 处理数字
        if c in "0123456789":
            numFlag = True
            num *= 10
            num += int(c)
        elif numFlag and c in "+-*/@)":
            postfixList.append(str(num))
            num = 0; numFlag = False

        # 处理优先级
        if c in "+-*/@":
            while not opsta.isEmpty() and priority[opsta.peek()] >= priority[c]:
                postfixList.append(opsta.pop())
            opsta.push(c)
        elif c == "(":
            opsta.push(c)
        elif c == ")":
            while opsta.peek() != "(":
                postfixList.append(opsta.pop())
            opsta.pop()

    return " ".join(postfixList)

print(infix2postfix("5 + 6 * 8@"))

这里的实例是中缀转后缀,但是在实现过程中务必注意几个问题:

  • 括号的问题,(和)都是需要特殊处理的.
  • 最后栈可能没有清空,所以为了清空,在最后面加上一个@或者=,并且当作一个低优先级符号处理比较方便.(当然最后搞个while把栈弹空也不是不行,但这样就显得代码有些长了.)
  • 数字的问题.如果只用识别"123456789"或者"ABCDEFG"的话,数字比较好处理,但是如果利用符号作为间隔来识别数字,要注意两个符号相连和表达式开头就是(的情况.

####　利用后缀表达式求值

其实方法是完全一样的,只不过需要一个数字栈.在符号弹出之后,直接把两个数字进行计算再压入栈中.

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
from Stack import Stack

def calcu (op, num1, num2):
    if op is "+":
        return num2 + num1
    elif op is "-":
        return num2 - num1
    elif op is "*":
        return num2 * num1
    elif op is "/":
        return num2 / num1

def infix_eval (infixStr):
    priority = {"+":1, "-":1, "*":2, "/":2, "(":0, ")":4, "@":0}
    opsta = Stack()
    numsta = Stack()

    num = 0; numFlag = False
    for c in infixStr:
        # 处理数字
        if c in "0123456789":
            numFlag = True
            num *= 10
            num += int(c)
        elif numFlag and c in "+-*/@)":
            numsta.push(num)
            num = 0; numFlag = False

        # 处理优先级
        if c in "+-*/@":
            while not opsta.isEmpty() and priority[opsta.peek()] >= priority[c]:
                op = opsta.pop()
                numsta.push(calcu(op, numsta.pop(), numsta.pop()))
            opsta.push(c)
        elif c == "(":
            opsta.push(c)
        elif c == ")":
            while opsta.peek() != "(":
                op = opsta.pop()
                numsta.push(calcu(op, numsta.pop(), numsta.pop()))
            opsta.pop()

    return numsta.pop()

print (infix_eval("6 * 8 - 9 / 2@"))

只要运算的式子是正确的,就应该能算出正确结果了.

和转后缀的区别主要在于加入List变为实际的运算.

这里也有几个需要注意的小问题:

  • 注意实际的运算是左结合还是右结合,尤其是 5^6 和 5-6 这样不满足交换律的运算.
  • 最后的结果在栈中,当然也可以用@或=来把结果弹出,如果里面的数字不止一个,那肯定出现了问题.
  • 向上面那样在传参时直接调用pop()是一件极其糟糕的事情,极其不推荐.

队列(queue)

其特点是后进先出(FIFO, First In First Out).

队列的抽象数据类型

  • Queue() 创建一个空的新队列,并返回一个空队列.
  • enqueue(x) 将x添加到队列的尾部.
  • dequeue() 从队列中删除头部的元素,并返回这个元素.
  • isEmpty() 返回队列是否为空.
  • size() 返回队列中的元素的数量.

队列的python实现

这里有个显然的问题,就是队列的开头在哪里.若规定0是开头,那么出队将会是 $\mathcal{O(n)}$,而入队则是$\mathcal{O(1)}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, x):
        self.queue.append(x)

    def dequeue(self):
        return self.queue.pop(0)

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

    def isEmpty(self):
        return self.size() == 0

实际上我只是将栈的实现做了极其简单的改动.

队列的实际用处

约瑟夫问题

一群人围成圈按1~7报数,其中报到7就出局,问最后一个出局的人是谁.

这个问题用队列是个极其简单的方法,不过真实的队列模拟实际上有些浪费.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solve(num, people):
    """
        num: 循环到 num 时出局
        people: 一些人名
    """
    que = Queue()
    for per in people:
        que.enqueue(per)

    while que.size() > 1:
        for i in range(num - 1):
            que.enqueue(que.dequeue())
        que.dequeue()

    return que.dequeue()

打印机

这是一个有些复杂的模拟了.

平均每天大约10名学生在任何给定时间打印两次,这些任务的长度范围从1到20页.每分钟以草稿质量可以处理10页,而高质量则只能每分钟处理5页.选择这两种速率的主要依据是平均等待时间,也就是需要模拟来计算的量.

建模实际有些麻烦.

首先是随机的任务.学生的任务是随机的,随机的时间和随机的页数(1~20),这需要一个额外的程序来生成.

接着是对每一秒进行模拟.

  • 创建打印任务.并将任务的时间戳添加到队列.
  • 分配给打印机任务.
  • 计算这个任务的等待时间,并加入到另一个列表中等待处理.

最后是计算.从生成的等待时间列表中计算平均等待时间.

在这里,则需要几个类来着手解决了.

Printer

成员:

  • rate 打印速率,1代表6秒一张,2代表12秒一张.
  • task 当前任务,没有时设为None.
  • remain 剩余时间.

函数:

  • __init__(pagerate) 初始化三个成员,并设置速度.
  • isBusy() 返回是否繁忙.
  • start(newtask) 开始新任务.
  • tick() 让时间走一秒,并更改相关参数.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Printer:
    def __init__(self, rate):
        self.rate = rate
        self.task = None
        self.remain = 0

    def isBusy(self):
        return self.task != None

    def tick(self):
        if self.isBusy():
            self.remain -= 1

        if self.remain == 0:
            self.task = None

    def start(self, newtask):

这里的start需要等到Task写好再解决.

Task

这个类用来表示单个的任务.

成员:

  • time 任务开始排队的时间.
  • pages 打印的页数.

函数:

  • __init__(time) 初始化成员.
  • waitTime(now) 计算任务的等待时间.
1
2
3
4
5
6
7
8
9
import random

class Task:
    def __init__(self, time):
        self.time = time
        self.pages = random.randrange(1,21)

    def waitTime(self, now):
        return now - self.time

接着就可以补写Printer中的start()了:

1
2
3
def start(self, newtask):
    self.task = newtask
    self.remain = newtask.pages * 6 * self.rate
开始模拟

模拟的过程很简单,按照上面写步骤的即可进行.

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
import random

def sim(total_time, rate):
    tskque = Queue()
    printer = Printer(rate)
    waitList = []

    for now in range(total_time):
        if isStart():
            task = Task(now)
            tskque.enqueue(task)

        if not printer.isBusy() and not tskque.isEmpty():
            task = tskque.dequeue()
            waitList.append(task.waitTime(now))
            printer.start(task)

        printer.tick()

    average = sum(waitList) / len(waitList)

    print("平均等待时间:{0:.2f}秒.剩余{1}个任务.".format(average, tskque.size()))



# 平均180秒一次打印任务,所以遇到0才生成任务.
def isStart ():
    num = random.randrange(180)
    return num == 0

for i in range(10):
    sim(3600, 1)

两种速度的输出大致如下:

高质量:

1
2
3
4
5
6
7
8
9
10
平均等待时间:74.28秒.剩余5个任务.
平均等待时间:177.47秒.剩余0个任务.
平均等待时间:74.71秒.剩余0个任务.
平均等待时间:92.50秒.剩余0个任务.
平均等待时间:76.26秒.剩余0个任务.
平均等待时间:268.80秒.剩余3个任务.
平均等待时间:61.88秒.剩余0个任务.
平均等待时间:735.33秒.剩余4个任务.
平均等待时间:81.36秒.剩余0个任务.
平均等待时间:30.33秒.剩余3个任务.

高速度:

1
2
3
4
5
6
7
8
9
10
平均等待时间:40.71秒.剩余0个任务.
平均等待时间:2.69秒.剩余0个任务.
平均等待时间:15.53秒.剩余0个任务.
平均等待时间:33.12秒.剩余0个任务.
平均等待时间:36.56秒.剩余0个任务.
平均等待时间:15.81秒.剩余0个任务.
平均等待时间:29.33秒.剩余1个任务.
平均等待时间:17.76秒.剩余1个任务.
平均等待时间:11.59秒.剩余0个任务.
平均等待时间:12.90秒.剩余0个任务.