三. Basic Data Structures

Posted on Edited on In 
1
对应本书第三章。

3. Basic Data Structures

笔记

本章主要介绍一些抽象数据类型（ADT）：栈stack/队列Queue/双向队列Deque/无序链表Unsordered List/有序链表Sordered List。

栈stack

用内置的list实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:
    def __init__(self):
        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)

典型应用：

  • 括号平衡检查 Parentheses Balance Checker
  • 数字进制转换 Converting Decimal Numbers to Binary Numbers
  • 中缀，前缀，后缀表达式 Infix, Prefix and Postfix Expressions

队列Queue

用内置的list实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)

典型应用：

  • 击鼓传花 Hot Potato Simulation
  • 打印机任务模拟 Printing Tasks Simulation

双向队列Deque

用内置的list实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)

典型应用：

  • 回文检查 Palindrome-Checker

无序链表Unsordered List

用内置的list实现：

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

    def __str__(self):
        return str(self.data)
    
    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 = 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())

有序链表Sordered List

用内置的list实现：

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
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)

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

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

        return count

作业

题目地址

q1

修改infix-to-postfix算法使其可以处理异常情况。

分析：异常情况可能是括号不平衡，也可能是缺少操作符或者缺少操作数。
括号不平衡可以方便地在中缀转后缀的函数中添加，但是操作符和操作数的检查可以留到计算的步骤再去检查，这步留在q2实现。

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
# q1
def infixToPostfix(infixexpr):
    """将表达式从中缀形式转化成后缀形式"""
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    # 存储操作符的栈
    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()
    # 栈中剩余的左括号的个数
    left_p_remain = 0
    
    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
            left_p_remain += 1
        elif token == ')':
            left_p_remain -= 1
            if left_p_remain < 0:
                raise Exception("parenthesis are not balance, please check!")
            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)
    if left_p_remain != 0:
        raise Exception("parenthesis are not balance, please check!")
            
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return " ".join(postfixList)

print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
print(infixToPostfix("( A + B ) * C - ( D - E ) ) * ( F + G)"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A B * C D * +
A B + C * D E - F G + * -
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-6-63343863e9e7> in <module>()
     43 print(infixToPostfix("A * B + C * D"))
     44 print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
---> 45 print(infixToPostfix("( A + B ) * C - ( D - E ) ) * ( F + G)"))

<ipython-input-6-63343863e9e7> in infixToPostfix(infixexpr)
     24             left_p_remain -= 1
     25             if left_p_remain < 0:
---> 26                 raise Exception("parenthesis are not balance, please check!")
     27             topToken = opStack.pop()
     28             while topToken != '(':

Exception: parenthesis are not balance, please check!

q2

实现后缀表达式求值函数中对操作符和操作数的检查

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
def postfixEval(postfixExpr):
    operandStack = Stack()
    tokenList = postfixExpr.split()

    for token in tokenList:
        if token in "0123456789":
            operandStack.push(int(token))
        else:
            # token是个操作符，需要出栈两个操作数，提前检查操作数够不够
            if operandStack.size() < 2:
                raise Exception("not enough operand, please check!")
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token,operand1,operand2)
            operandStack.push(result)
    # 如果遍历完以后，栈中还剩操作数，则操作数过多
    if operandStack.size() != 1:
        raise Exception("too much operand, please check!")
    return operandStack.pop()

def doMath(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

print(postfixEval('7 8 + 3 2 + /'))
print(postfixEval('7 8 + 3 2 + / -'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3.0
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-7-88e05ae7bebb> in <module>()
     30 
     31 print(postfixEval('7 8 + 3 2 + /'))
---> 32 print(postfixEval('7 8 + 3 2 + / -'))

<ipython-input-7-88e05ae7bebb> in postfixEval(postfixExpr)
      9             # token是个操作符，需要出栈两个操作数，提前检查操作数够不够
     10             if operandStack.size() < 2:
---> 11                 raise Exception("not enough operand, please check!")
     12             operand2 = operandStack.pop()
     13             operand1 = operandStack.pop()

Exception: not enough operand, please check!
1
print(postfixEval('7 8 + 3 2 + / 1'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-8-23319fcf89d3> in <module>()
----> 1 print(postfixEval('7 8 + 3 2 + / 1'))

<ipython-input-7-88e05ae7bebb> in postfixEval(postfixExpr)
     16     # 如果遍历完以后，栈中还剩操作数，则操作数过多
     17     if operandStack.size() != 1:
---> 18         raise Exception("too much operand, please check!")
     19     return operandStack.pop()
     20 

Exception: too much operand, please check!

q3/q4

将q1和q2合并，写一个直接根据中序表达式的函数，q4要求把q3改成一个计算器。个人以为q3和q4相似，直接写成一处。

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
# q3/q4

class Calculator(object):
    """支持0-9的加减乘除的简单计算器。"""
    
    def __init__(self):
        pass
        
    def calc(self, infix):
        postfix = self.infixToPostfix(infix)
        return self.postfixEval(postfix)

    def infixToPostfix(self, infixexpr):
        """将表达式从中缀形式转化成后缀形式"""
        prec = {}
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
        # 存储操作符的栈
        opStack = Stack()
        postfixList = []
        tokenList = infixexpr.split()
        # 栈中剩余的左括号的个数
        left_p_remain = 0

        for token in tokenList:
            if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
                postfixList.append(token)
            elif token == '(':
                opStack.push(token)
                left_p_remain += 1
            elif token == ')':
                left_p_remain -= 1
                if left_p_remain < 0:
                    raise Exception("parenthesis are not balance, please check!")
                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)
        if left_p_remain != 0:
            raise Exception("parenthesis are not balance, please check!")

        while not opStack.isEmpty():
            postfixList.append(opStack.pop())

        return " ".join(postfixList)

    def postfixEval(self, postfixExpr):
        operandStack = Stack()
        tokenList = postfixExpr.split()

        for token in tokenList:
            if token in "0123456789":
                operandStack.push(int(token))
            else:
                # token是个操作符，需要出栈两个操作数，提前检查操作数够不够
                if operandStack.size() < 2:
                    raise Exception("not enough operand, please check!")
                operand2 = operandStack.pop()
                operand1 = operandStack.pop()
                result = self.doMath(token,operand1,operand2)
                operandStack.push(result)
        # 如果遍历完以后，栈中还剩操作数，则操作数过多
        if operandStack.size() != 1:
            raise Exception("too much operand, please check!")
        return operandStack.pop()

    def doMath(self, op, op1, op2):
        if op == "*":
            return op1 * op2
        elif op == "/":
            return op1 / op2
        elif op == "+":
            return op1 + op2
        else:
            return op1 - op2
        
cal = Calculator()
print(cal.calc("( 1 + 3 ) / ( ( 3 - 8 ) * 9 ) "))
1
-0.08888888888888889
1
print(cal.calc("( 1 + 3 ) / ( ( 3 - 8 ) * 9 ) 9 "))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-10-968961ac46e3> in <module>()
----> 1 print(cal.calc("( 1 + 3 ) / ( ( 3 - 8 ) * 9 ) 9 "))

<ipython-input-9-507891dfbead> in calc(self, infix)
      9     def calc(self, infix):
     10         postfix = self.infixToPostfix(infix)
---> 11         return self.postfixEval(postfix)
     12 
     13     def infixToPostfix(self, infixexpr):

<ipython-input-9-507891dfbead> in postfixEval(self, postfixExpr)
     69         # 如果遍历完以后，栈中还剩操作数，则操作数过多
     70         if operandStack.size() != 1:
---> 71             raise Exception("too much operand, please check!")
     72         return operandStack.pop()
     73 

Exception: too much operand, please check!

q5

实现Queue，使得队尾是list的末尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Queue2:
    def __init__(self):
        self.items = []

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        head = self.items[0]
        del self.items[0]
        return head

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

q = Queue2()
q.enqueue(1)
q.enqueue(2)
print(q.items[1]) 
q.dequeue()
print(q.items[0])
1
2
2
2

q6

设计实验，对比两种Queue实现的优劣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def queue1_en_test():
    q = Queue()
    for i in range(1000):
        q.enqueue(1)
        
def queue2_en_test():
    q = Queue2()
    for i in range(1000):
        q.enqueue(1)
        
def queue1_en_de_test():
    q = Queue()
    for i in range(1000):
        q.enqueue(1)
    for i in range(1000):
        q.dequeue()
        
def queue2_en_de_test():
    q = Queue2()
    for i in range(1000):
        q.enqueue(1)
    for i in range(1000):
        q.dequeue()
1
2
3
4
5
6
7
8
9
from timeit import Timer
t1 = Timer("queue1_en_test()", "from __main__ import queue1_en_test")
print("queue1_en_test:",t1.timeit(number=1000), "milliseconds")
t2 = Timer("queue2_en_test()", "from __main__ import queue2_en_test")
print("queue2_en_test:",t2.timeit(number=1000), "milliseconds")
t3 = Timer("queue1_en_de_test()", "from __main__ import queue1_en_de_test")
print("queue1_en_de_test:",t3.timeit(number=1000), "milliseconds")
t4 = Timer("queue2_en_de_test()", "from __main__ import queue2_en_de_test")
print("queue2_en_de_test:",t4.timeit(number=1000), "milliseconds")
1
2
3
4
queue1_en_test: 0.49930859899995994 milliseconds
queue2_en_test: 0.20399194199990234 milliseconds
queue1_en_de_test: 0.7333720130000074 milliseconds
queue2_en_de_test: 0.5521609099996567 milliseconds

从理论分析可以知道，如果进队操作设置在list起点，那么入队操作是$O(n)$，出队操作是$O(1)$；
相反，如果进队操作设置在list末端，那么入队操作是$O(1)$，出队操作是$O(n)$。

但是为什么在测试中综合第二种的性能比第一种的好呢？
看一下下面的测试：

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
def list_append_test():
    l = list(range(1000))
    for i in range(1000):
        l.append(i)

def list_pop_test():
    l = list(range(1000))
    for i in range(1000):
        l.pop()
        
def list_del_test():
    l = list(range(1000))
    for i in range(1000):
        del l[0]
        
def list_insert_test():
    l = []
    for i in range(1000):
        l.insert(0, i)
        
t5 = Timer("list_append_test()", "from __main__ import list_append_test")
print("list_append_test:",t5.timeit(number=1000), "milliseconds")
t6 = Timer("list_pop_test()", "from __main__ import list_pop_test")
print("list_pop_test:",t6.timeit(number=1000), "milliseconds")
t7 = Timer("list_del_test()", "from __main__ import list_del_test")
print("list_del_test:",t7.timeit(number=1000), "milliseconds")
t8 = Timer("list_insert_test()", "from __main__ import list_insert_test")
print("list_insert_test:",t8.timeit(number=1000), "milliseconds")
1
2
3
4
list_append_test: 0.09044601999994484 milliseconds
list_pop_test: 0.10493274600003133 milliseconds
list_del_test: 0.14676751699971646 milliseconds
list_insert_test: 0.3609275019998677 milliseconds

也就是说list的append比pop快，虽然都是$O(1)$;而且，del也比insert快，虽然都是$O(n)$。

因此第二种实现更好。

q7

实现是个enqueue和dequeue都是$O(1)$的Queue。
这道题我没有想出来，于是在stackoverflow上找到了一个双栈的实现方法。只有在outbox空的时候，把所有inbox出栈，再入outbox栈，这里的时间复杂度是$O(n)$。正好符合作者的要求。

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
# q7
class Queue3:
    """
    Keep 2 stacks, let's call them inbox and outbox.

    Enqueue:

    Push the new element onto inbox
    Dequeue:

    If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
    Pop and return the top element from outbox
    """
    def __init__(self):
        self.inbox = Stack()
        self.outbox = Stack()

    def enqueue(self, item):
        self.inbox.push(item)

    def dequeue(self):
        if self.outbox.isEmpty():
            while not self.inbox.isEmpty():
                self.outbox.push(self.inbox.pop());
        return self.outbox.pop();

q3 = Queue3()
q3.enqueue(1)
q3.enqueue(2)
q3.enqueue(3)
print(q3.dequeue())
print(q3.dequeue())
print(q3.dequeue())
1
2
3
1
2
3

q8

设计一个现实生活中的使用场景，模拟队列。

这里设计一个理发师和顾客的场景。

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
class Barber():
    
    def __init__(self, wait_seat_num):
        self.wait_seat_num = wait_seat_num
        self.isWorking = False
        self.wait_queue = Queue()
        
    def costomer_come(self, cid):
        if self.isWorking:
            if self.wait_queue.size() < self.wait_seat_num:
                self.wait_queue.enqueue(cid)
            else:
                print("Sorry, the baber shop is full! Come again later!")
        else:
            self.isWorking = True
            self.work(cid)
            
    def work(self, cid):
        # ... ...
        self.work_done(cid)
    
    def work_done(self, cid):
        if self.wait_queue.size() > 0:
            new_cid = self.wait_queue.deque()
            self.work(new_cid)
        else:
            self.isWorking = False

q9

修改hot potato 算法，使每次传递的个数为一个随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import random
def hotPotato(namelist):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    while simqueue.size() > 1:
        num = random.randrange(1,5)
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())

        simqueue.dequeue()

    return simqueue.dequeue()

print(hotPotato(["Bill","David","Susan","Jane","Kent","Brad"]))
print(hotPotato(["Bill","David","Susan","Jane","Kent","Brad"]))
1
2
Susan
Brad

q10

实现一个基数排序器，参考wikipedia的Radix_sort。

wikipedia的example：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
An example[edit]
Original, unsorted list:
170, 45, 75,
90, 802, 2, 24, 66
Sorting by least significant digit (1s place) gives:
170, 90,
802, 2, 24, 45, 75, 66
Notice that we keep 802 before 2, because 802 occurred
before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.
Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90
Notice
that 802 again comes before 2 as 802 comes before 2 in the previous list.
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90,
170, 802

简单的说，就是每比一位排一次序。

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
# q10
def get_max_num_len(nums):
    """获取数组中位数最大的个数的位数"""
    max_len = 0
    for num in nums:
        cur_len = 1 
        while num // 10 != 0:
            num = num // 10
            cur_len += 1
        if cur_len > max_len:
            max_len = cur_len
    return max_len

def get_num_by_order(num, order):
    """例如输入876和2，返回第二位的7；若输入4，则返回0"""
    left = num // (10**(order-1))
    return left % 10


def radix_sorting_machine(nums):
    bins = []
    for i in range(10):
        bins.append(Queue())
    for i in range(get_max_num_len(nums)):
        for num in nums:
            bins[get_num_by_order(num, i+1)].enqueue(num)
        j = 0
        for one_bin in bins:
            while not one_bin.isEmpty():
                nums[j] = one_bin.dequeue()
                j += 1
    return nums

print(get_max_num_len([10, 20, 300]))
print(get_num_by_order(876, 2))
print(get_num_by_order(876, 4))
print(radix_sorting_machine([10, 20, 300]))
print(radix_sorting_machine([20, 1, 3, 677, 98, 25]))
1
2
3
4
5
3
7
0
[10, 20, 300]
[1, 3, 20, 25, 98, 677]

q11

html匹配检测

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

def html_checker(html_str):
    pattern = "<(.+?)>"
    tag_stack = Stack()
    html_pat = re.compile(pattern)
    tags = html_pat.findall(html_str)
    if tags:
        for one in tags:
            one = one.strip()
            if not one.startswith('/'):
                tag_stack.push(one)
            else:
                one = one.replace('/', '')
                if tag_stack.isEmpty():
                    print("html is not balace, check : ", one)
                    return False
                stack_top = tag_stack.pop()
                if stack_top != one:
                    print("html is not balace, check : ", one)
                    return False
        if not tag_stack.isEmpty():
            print("html is not closed, please check !")
            return False
    print("html is balance !")
    return True
            
        
html_str = """
<html>
   <head>
      <title>
         Example
      </title>
   </head>

   <body>
      <h1>Hello, world</h1>
   </body>
</html>
"""
html_checker(html_str)
1
2
html is balance !
True
1
2
html_str += "<a>"
html_checker(html_str)
1
2
html is not closed, please check !
False
1
2
html_str = "<a></b>"
html_checker(html_str)
1
2
html is not balace, check :  b
False

q12

改写回文检测的代码，使得有空格也可以检测（忽略空格）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# q12
def palchecker(aString):
    chardeque = Deque()

    for ch in aString:
        if ch != " ":
            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("lsdkjfskf"))
print(palchecker("radar"))
print(palchecker("I PREFER PI"))
1
2
3
False
True
True

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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
# q13/q14/q15/q16/q17/q18

class UnorderedList:

    def __init__(self):
        # 保存第一个结点
        self.head = None
        self.length = 0
        # 保存最后一个结点
        self.rear = None
    
    # q16/q17    
    def __str__(self):
        datas = []
        current = self.head
        while current:
            datas.append(current.getData())
            current = current.getNext()
        datas = [str(data) for data in datas]
        return "[" + ",".join(datas) + "]"
    
    # q19
    def __getitem__(self, key) :
        if isinstance(key, slice) :
            #Get the start, stop, and step from the slice
            indices = list(range(self.size()))[key.start:key.stop:key.step]
            items = []
            for ind in indices:
                items.append(self.__getitem__(ind))
            return items
        elif isinstance(key, int) :
            if key < 0 : #Handle negative indices
                key += self.size()
            if key < 0 or key >= self.size() :
                raise IndexError("The index (%d) is out of range."%key)

            current = self.head
            cur_ind = 0
            while cur_ind < key:
                current = current.getNext()
                cur_ind += 1
            return current
        else:
            raise TypeError("Invalid argument type.")
        
    def isEmpty(self):
        return self.head == None

    def add(self,item):
        """添加元素到头部"""
        temp = Node(item)
        temp.setNext(self.head)
        if self.head == None:
            self.rear = temp
        self.head = temp
        # q13
        self.length += 1
    
    # q13
    def size(self):
        return self.length

    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 and current:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        # q14
        if found:
            if previous == None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())
            # q13
            self.length -= 1
        else:
            print("item not found in the list!")
    
    # q18        
    def append(self, item):
        """添加元素到尾部"""
        temp = Node(item)
        if self.rear == None:
            self.rear = temp
        else:
            self.rear.setNext(temp)
            self.rear = temp
        if self.head == None:
            self.head = temp
        self.length += 1
        
    def index(self, item):
        ind_list = []
        current = self.head
        cur_ind = 0
        while current:
            if current.getData() == item:
                ind_list.append(cur_ind)
            current = current.getNext()
            cur_ind += 1
        return ind_list
        
    def pop(self, pos=0):
        if pos > self.size()-1:
            print("pos is bigger than list size!")
            return    
        cur_ind = 1
        pre = self.head
        current = pre.getNext()
        if pos == 0:
            self.head = current
            self.length -= 1
            return pre.getData()
        while cur_ind < pos:
            pre = current
            current = pre.getNext()
            cur_ind += 1
#         print(pre.getData())
        pre.setNext(current.getNext())
        self.length -= 1
        return current.getData()
        
    def insert(self, pos, item):
        if pos > self.size():
            print("pos is bigger than list size!")
            return   
        if pos == 0:
            self.add(item)
        elif pos == self.size():
            self.append(item)
        else:
            pre = self.head
            current = pre.getNext()
            cur_ind = 1
            while cur_ind < pos:
                pre = current
                current = pre.getNext()
                cur_ind += 1
            temp = Node(item)
            temp.setNext(current)
            pre.setNext(temp)
            self.length += 1
.input n
1
2
3
4
5
ul = UnorderedList()
ul.add(1)
ul.add(2)
# q13
print(ul.size())
1
2
1
2
# q14
ul.remove(3)
1
item not found in the list!
1
2
3
4
5
# q16/q17
ul.add(3)
print(ul.size())
print(ul.search(2))
print(ul)
1
2
3
3
True
[3,2,1]
1
2
3
4
5
6
# q18
ul.append(3)
ul.append(5)
ul.append(4)
print(ul)
print(ul.size())
1
2
[3,2,1,3,5,4]
6
1
2
# q18
print(ul.index(3))
1
[0, 3]
1
2
3
4
5
6
7
8
# q18
print(ul)
print(ul.size()-1)
ul.pop(2)
print(ul)
print(ul.size()-1)
print(ul.pop(ul.size()-1))
print(ul)
1
2
3
4
5
6
[3,2,1,3,5,4]
5
[3,2,3,5,4]
4
4
[3,2,3,5]
1
2
3
4
5
6
7
ul.insert(0, 3)
print(ul)
ul.insert(3, 3)
print(ul)
ul.insert(5, 3)
print(ul)
ul.insert(8, 3)
1
2
3
4
[3,3,2,3,5]
[3,3,2,3,3,5]
[3,3,2,3,3,3,5]
pos is bigger than list size!
1
print(ul.size())
1
7
1
2
3
for node in ul[0:3]:
    print(node)
print(ul[2])
1
2
3
4
3
3
2
2

q20

完善OrderedList的实现

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
100
101
102
103
104
105
106
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)

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

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

        return count  
    
    def remove(item):
        pre = self.head
        current = pre.getNext()
        if item == pre.getData():
            self.head = current
        found = False
        stop = False
        while current and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    pre = current
                    current = current.getNext()
        if found:
            pre.setNext(current.getNext())
    
    def pop(self, pos=0):
        if pos > self.size()-1:
            print("pos is bigger than list size!")
            return    
        cur_ind = 1
        pre = self.head
        current = pre.getNext()
        if pos == 0:
            self.head = current
            return pre.getData()
        while cur_ind < pos:
            pre = current
            current = pre.getNext()
            cur_ind += 1
        pre.setNext(current.getNext())
        self.length -= 1
        return current.getData()
    
    def index(self, item):
        current = self.head
        cur_ind = 0
        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()
                    cur_ind += 1
        if found:
            return cur_ind
        else:
            return -1

q21

考虑写一个Unordered list和 Ordered list 的父类，使得二者相同的操作可以在父类中实现。

相同的操作有：

pop size isEmpty

此题代码省略。

q22

用链表实现一个stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack2:
    def __init__(self):
        self.items = UnorderedList()

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop(self.items.size()-1)

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

    def size(self):
        return self.items.size()

q23

用链表实现一个queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Queue2:
    def __init__(self):
        self.items = UnorderedList()

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(self.items.size()-1)

    def size(self):
        return self.items.size()

q24

用链表实现一个deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Deque2:
    def __init__(self):
        self.items = UnorderedList()

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

    def addFront(self, item):
        self.items.add(item)

    def addRear(self, item):
        self.items.append(item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(self.items.size()-1)

    def size(self):
        return self.items.size()

q25

设计实验对比链表和python内置list的性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
def list_test():
    l = []
    for i in range(1000):
        l.append(i)
    for i in range(1000):
        l.pop()
    
def unorded_list_test():
    ul = UnorderedList()
    for i in range(1000):
        ul.add(i)
    for i in range(1000):
        ul.pop()
1
2
3
4
5
from timeit import Timer
t9 = Timer("list_test()", "from __main__ import list_test")
print("list :",t9.timeit(number=100), "milliseconds")
t10 = Timer("unorded_list_test()", "from __main__ import unorded_list_test")
print("unorded list :",t10.timeit(number=100), "milliseconds")
1
2
list : 0.020239962999767158 milliseconds
unorded list : 0.18505007000021578 milliseconds

q26

设计实验对比两种stack和queue的实现的性能。

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
def stack_1_test():
    s = Stack()
    for i in range(1000):
        s.push(i)
    for i in range(1000):
        s.pop()
    
def stack_2_test():
    s = Stack2()
    for i in range(1000):
        s.push(i)
    for i in range(1000):
        s.pop()
    
def queue_1_test():
    q = Queue()
    for i in range(1000):
        q.enqueue(i)
    for i in range(1000):
        q.dequeue()
    
def queue_2_test():
    q = Queue2()
    for i in range(1000):
        q.enqueue(i)
    for i in range(1000):
        q.dequeue()
    
1
2
3
4
5
6
7
8
t11 = Timer("stack_1_test()", "from __main__ import stack_1_test")
print("stack 1:",t11.timeit(number=10), "milliseconds")
t12 = Timer("stack_2_test()", "from __main__ import stack_2_test")
print("stack 2:",t12.timeit(number=10), "milliseconds")
t13 = Timer("queue_1_test()", "from __main__ import queue_1_test")
print("queue 1:",t13.timeit(number=10), "milliseconds")
t14 = Timer("queue_2_test()", "from __main__ import queue_2_test")
print("queue 2:",t14.timeit(number=10), "milliseconds")
1
2
3
4
stack 1: 0.005089294999834237 milliseconds
stack 2: 0.9783772470000258 milliseconds
queue 1: 0.007056649999867659 milliseconds
queue 2: 0.9649373209999794 milliseconds

q27

设计一个双向连接的链表。

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
class Node2:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None
        self.pre = None

    def __str__(self):
        return str(self.data)
    
    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def getPre(self):
        return self.pre
    
    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext
        
    def setPre(self,newpre):
        self.pre = newpre

q28

设计一个入队和出队时间复杂度都是O(1)的queue。

参考q7