chpater3_answer

一、讨论题二、编程练习1.修改从中序到后序的转换算法，使其能处理异常情况。2.修改计算后序表达式的算法，使其能处理异常情况。3.结合从中序到后序的转换算法以及计算后序表达式的算法，实现直接的中序计算。在计算时，应该使用两个栈从左往右处理中序表达式标记。一个栈用于保存运算符，另一个用于保存操作数。4.将在练习3中实现的算法做成一个计算器。5.使用列表实现队列抽象数据类型，将列表的后端作为队列的尾部。6.设计和实现一个实验，对比两种队列实现的性能。能从该实验学到什么？7.实现一个队列，使其添加操作和移除操作的平均时间复杂度为O(111)。这意味着在大多数情况下，两个操作的时间复杂度都是O(111)，仅在一种特殊情况下，移除操作为O(nnn)。8.考虑现实生活中的一个情景。完整地定义问题，并且设计一个模拟来解决它。9. 修改传土豆模拟程序，允许随机计数，从而使每一轮的结果都不可预测。10.实现一个基数排序器。11.HTML 中也存在括号匹配问题。标签有开始和结束两种形式，并且需要互相匹配才能正确描述网页内容。写一个程序来检查HTML文档中的标签是否正确匹配。12.扩展代码清单3-15 中的回文检测器，使其可以处理包含空格的回文。如果忽略其中的空格，那么I PREFER PI 就是回文。13. 本章通过计算列表中节点的个数来实现length 方法。另一种做法是将节点个数作为额外的信息保存在列表头中。请修改UnorderedList 类的实现，使其包含节点个数信息，并且重新实现length 方法。14. 实现remove 方法，使其能正确处理待移除元素不在列表中的情况。15. 修改列表类，使其能支持重复元素。这一改动会影响到哪些方法？16. 实现UnorderedList类的__str__方法。列表适合用什么样的字符串表示？17. 实现__str__方法，使列表按照Python 的方式来显示（使用方括号）。18. 实现无序列表抽象数据类型剩余的方法：append、index、pop 和insert。19. 实现UnorderedList 类的slice 方法。该方法接受start和stop两个参数， 并且返回一个从start位置开始，到stop位置结束的新列表（但不包含stop位置上的元素）。20. 实现有序列表抽象数据类型剩余的方法。21. 思考有序列表和无序列表的关系。能否利用继承关系来构建更高效的实现？试着实现这个继承结构。22. 使用链表实现栈。23.使用链表实现队列。24. 使用链表实现双端队列。25. 设计和实现一个实验，比较用链表实现的列表与Python列表的性能。26. 设计和实现一个实验，比较基于python列表的栈和队列与相应链表实现的性能。27. 由于每个节点都只有一个引用指向其后的节点，因此本章给出的链表实现成为单向链表。另一种实现成为双向链表。在这种实现中，每一个节点都有指向后一个节点的引用（通常称为next）和指向前一个节点的引用（通常称为back）。头引用同样也有两个引用，一个指向链表中的第一个节点，另一个指向最后一个节点。请用Python实现双向链表。28. 为队列创建一个实现，使得添加操作和移除操作的平均时间复杂度是O(1)O(1)O(1)。三、总结

参考链接：

/p/130436689 link

一、讨论题

略略略

二、编程练习

1.修改从中序到后序的转换算法，使其能处理异常情况。

from chapter3.stack import Stackimport stringdef infixToPostfix(infixexpr):prec = {}prec["("] = 1prec["+"] = 2prec["-"] = 2prec["*"] = 3prec["/"] = 3opstack = Stack()postfixList = []count = 0tokenList = infixexpr.split()lenth = len(tokenList)for i in range(lenth):if tokenList[i] in string.ascii_uppercase and (tokenList[i+1] in string.ascii_uppercase or tokenList[i-1] == ")" or tokenList[i+1] == "("):return "Input Error"if tokenList[i] in "+-*/" and (tokenList[i+1] in "+-*/)" or tokenList[i-1] in "+-*/(" ):return "Input Error"if i+1 < lenth and tokenList[i] == ')' and tokenList[i+1] == "(":return "Input Error"for token in tokenList:if token in string.ascii_uppercase:postfixList.append(token)elif token == '(':count += 1opstack.push(token)elif token == ')':count -= 1topToken = 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 count != 0:return "Input Error"while not opstack.isEmpty():postfixList.append(opstack.pop())return " ".join(postfixList)if __name__ == '__main__':print(infixToPostfix("( A + - V )"))print(infixToPostfix("( A + B )"))

2.修改计算后序表达式的算法，使其能处理异常情况。

from chapter3.stack import Stackdef postfixEval(postfixExpr):numstack = Stack()tokenList = postfixExpr.split()try:for token in tokenList:if token in "0123456789":numstack.push(int(token))else:num1 = numstack.pop()num2 = numstack.pop()result = doMath(token, num1, num2)numstack.push(result)if numstack.size() == 1:return numstack.pop()else:return "Input Error"except:return "Input Error"def doMath(op, n1, n2):if op == "*":return n1 * n2elif op == "/":return n1 / n2elif op == "+":return n1 + n2else:return n1 - n2if __name__ == '__main__':print(postfixEval("4 * 6"))

3.结合从中序到后序的转换算法以及计算后序表达式的算法，实现直接的中序计算。在计算时，应该使用两个栈从左往右处理中序表达式标记。一个栈用于保存运算符，另一个用于保存操作数。

from chapter3.stack import Stackdef infixEval(infixExpr):opstack = Stack()numstack = Stack()tokenList = infixExpr.split()for token in tokenList:if token in "+-*/()":if token == ")":while opstack.peek() != '(':num2 = numstack.pop()num1 = numstack.pop()op = opstack.pop()res = doMath(op, num1, num2)numstack.push(res)opstack.pop()else:opstack.push(token)else:numstack.push(float(token))return numstack.pop()def doMath(op, n1, n2):if op == "*":return n1 * n2elif op == "/":return n1 / n2elif op == "+":return n1 + n2else:return n1 - n2if __name__ == '__main__':print(infixEval("( 2 + 13.1 )"))

4.将在练习3中实现的算法做成一个计算器。

效果如图：

主要加了俩括号，参考链接：/p/130436689 link

import mathimport tkinterfrom chapter3.stack import Stackroot = tkinter.Tk()root.resizable(width=False, height=False)'''hypeparameter'''# 是否按下了运算符IS_CALC = False# 存储数字STORAGE = []Expression = ''# 显示框最多显示多少个字符MAXSHOWLEN = 18# 当前显示的数字CurrentShow = tkinter.StringVar()CurrentShow.set('0')'''按下小数点'''def pressDP():global IS_CALCif IS_CALC:CurrentShow.set('0')IS_CALC = Falseif len(CurrentShow.get().split('.')) == 1:if len(CurrentShow.get()) < MAXSHOWLEN:CurrentShow.set(CurrentShow.get() + '.')'''清零'''def clearAll():global STORAGEglobal IS_CALCSTORAGE.clear()IS_CALC = FalseCurrentShow.set('0')'''清除当前显示框内所有数字'''def clearCurrent():CurrentShow.set('0')'''删除显示框内最后一个数字'''def delOne():global IS_CALCif IS_CALC:CurrentShow.set('0')IS_CALC = Falseif CurrentShow.get() != '0':if len(CurrentShow.get()) > 1:CurrentShow.set(CurrentShow.get()[:-1])else:CurrentShow.set('0')'''计算答案修正'''def modifyResult(result):result = str(result)if len(result) > MAXSHOWLEN:if len(result.split('.')[0]) > MAXSHOWLEN:result = 'Overflow'else:# 直接舍去不考虑四舍五入问题result = result[:MAXSHOWLEN]return result'''按下运算符'''def pressOperator(operator):global STORAGEglobal IS_CALCif operator == '+/-':if CurrentShow.get().startswith('-'):CurrentShow.set(CurrentShow.get()[1:])else:CurrentShow.set('-'+CurrentShow.get())elif operator == '1/x':try:result = 1 / float(CurrentShow.get())except:result = 'illegal operation'result = modifyResult(result)CurrentShow.set(result)IS_CALC = Trueelif operator == 'sqrt':try:result = math.sqrt(float(CurrentShow.get()))except:result = 'illegal operation'result = modifyResult(result)CurrentShow.set(result)IS_CALC = Trueelif operator == 'MC':STORAGE.clear()elif operator == 'MR':if IS_CALC:CurrentShow.set('0')STORAGE.append(CurrentShow.get())expression = ''.join(STORAGE)try:result = eval(expression)except:result = 'illegal operation'result = modifyResult(result)CurrentShow.set(result)IS_CALC = Trueelif operator == 'MS':STORAGE.clear()STORAGE.append(CurrentShow.get())elif operator == 'M+':STORAGE.append(CurrentShow.get())elif operator == 'M-':if CurrentShow.get().startswith('-'):STORAGE.append(CurrentShow.get())else:STORAGE.append('-' + CurrentShow.get())def pressExpression(operator):global Expressionprint(list)if operator != '=':Expression += operatorelse:expression = ' '.join(Expression)result = infixEval(expression)CurrentShow.set(result)def infixEval(infixExpr):opstack = Stack()numstack = Stack()tokenList = infixExpr.split()for token in tokenList:if token in "+-*/()":if token == ")":while opstack.peek() != '(':num2 = numstack.pop()num1 = numstack.pop()op = opstack.pop()res = doMath(op, num1, num2)numstack.push(res)opstack.pop()else:opstack.push(token)else:numstack.push(float(token))return numstack.pop()def doMath(op, n1, n2):if op == "*":return n1 * n2elif op == "/":return n1 / n2elif op == "+":return n1 + n2else:return n1 - n2'''Demo'''def Demo():root.minsize(320, 420)root.title('Calculator')# 布局# --文本框label = tkinter.Label(root, textvariable=CurrentShow, bg='black', anchor='e', bd=5, fg='white', font=('楷体', 20))label.place(x=20, y=50, width=280, height=50)# --第一行# ----Memory clearbutton1_1 = tkinter.Button(text='MC', bg='#666', bd=2, command=lambda:pressOperator('MC'))button1_1.place(x=20, y=110, width=50, height=35)# ----Memory readbutton1_2 = tkinter.Button(text='MR', bg='#666', bd=2, command=lambda:pressOperator('MR'))button1_2.place(x=77.5, y=110, width=50, height=35)# ----Memory savebutton1_3 = tkinter.Button(text='MS', bg='#666', bd=2, command=lambda:pressOperator('MS'))button1_3.place(x=135, y=110, width=50, height=35)# ----Memory +button1_4 = tkinter.Button(text='M+', bg='#666', bd=2, command=lambda:pressOperator('M+'))button1_4.place(x=192.5, y=110, width=50, height=35)# ----Memory -button1_5 = tkinter.Button(text='M-', bg='#666', bd=2, command=lambda:pressOperator('M-'))button1_5.place(x=250, y=110, width=50, height=35)# --第二行# ----删除单个数字button2_1 = tkinter.Button(text='del', bg='#666', bd=2, command=lambda:delOne())button2_1.place(x=20, y=155, width=50, height=35)# ----清除当前显示框内所有数字button2_2 = tkinter.Button(text='CE', bg='#666', bd=2, command=lambda:clearCurrent())button2_2.place(x=77.5, y=155, width=50, height=35)# ----清零(相当于重启)button2_3 = tkinter.Button(text='C', bg='#666', bd=2, command=lambda:clearAll())button2_3.place(x=135, y=155, width=50, height=35)# ----取反button2_4 = tkinter.Button(text='+/-', bg='#666', bd=2, command=lambda:pressOperator('+/-'))button2_4.place(x=192.5, y=155, width=50, height=35)# ----开根号button2_5 = tkinter.Button(text='sqrt', bg='#666', bd=2, command=lambda:pressOperator('sqrt'))button2_5.place(x=250, y=155, width=50, height=35)# --第三行# ----7button3_1 = tkinter.Button(text='7', bg='#bbbbbb', bd=2, command=lambda:pressExpression('7'))button3_1.place(x=20, y=200, width=50, height=35)# ----8button3_2 = tkinter.Button(text='8', bg='#bbbbbb', bd=2, command=lambda:pressExpression('8'))button3_2.place(x=77.5, y=200, width=50, height=35)# ----9button3_3 = tkinter.Button(text='9', bg='#bbbbbb', bd=2, command=lambda:pressExpression('9'))button3_3.place(x=135, y=200, width=50, height=35)# ----除button3_4 = tkinter.Button(text='/', bg='#708069', bd=2, command=lambda:pressExpression('/'))button3_4.place(x=192.5, y=200, width=50, height=35)# ----取余button3_5 = tkinter.Button(text=')', bg='#708069', bd=2, command=lambda:pressExpression(')'))button3_5.place(x=250, y=200, width=50, height=35)# --第四行# ----4button4_1 = tkinter.Button(text='4', bg='#bbbbbb', bd=2, command=lambda:pressExpression('4'))button4_1.place(x=20, y=245, width=50, height=35)# ----5button4_2 = tkinter.Button(text='5', bg='#bbbbbb', bd=2, command=lambda:pressExpression('5'))button4_2.place(x=77.5, y=245, width=50, height=35)# ----6button4_3 = tkinter.Button(text='6', bg='#bbbbbb', bd=2, command=lambda:pressExpression('6'))button4_3.place(x=135, y=245, width=50, height=35)# ----乘button4_4 = tkinter.Button(text='*', bg='#708069', bd=2, command=lambda:pressExpression('*'))button4_4.place(x=192.5, y=245, width=50, height=35)# ----取导数button4_5 = tkinter.Button(text='(', bg='#708069', bd=2, command=lambda:pressExpression('('))button4_5.place(x=250, y=245, width=50, height=35)# --第五行# ----3button5_1 = tkinter.Button(text='3', bg='#bbbbbb', bd=2, command=lambda:pressExpression('3'))button5_1.place(x=20, y=290, width=50, height=35)# ----2button5_2 = tkinter.Button(text='2', bg='#bbbbbb', bd=2, command=lambda:pressExpression('2'))button5_2.place(x=77.5, y=290, width=50, height=35)# ----1button5_3 = tkinter.Button(text='1', bg='#bbbbbb', bd=2, command=lambda:pressExpression('1'))button5_3.place(x=135, y=290, width=50, height=35)# ----减button5_4 = tkinter.Button(text='-', bg='#708069', bd=2, command=lambda:pressExpression('-'))button5_4.place(x=192.5, y=290, width=50, height=35)# ----等于button5_5 = tkinter.Button(text='=', bg='#708069', bd=2, command=lambda:pressExpression('='))button5_5.place(x=250, y=290, width=50, height=80)# --第六行# ----0button6_1 = tkinter.Button(text='0', bg='#bbbbbb', bd=2, command=lambda:pressExpression('0'))button6_1.place(x=20, y=335, width=107.5, height=35)# ----小数点button6_2 = tkinter.Button(text='.', bg='#bbbbbb', bd=2, command=lambda:pressDP())button6_2.place(x=135, y=335, width=50, height=35)# ----加button6_3 = tkinter.Button(text='+', bg='#708069', bd=2, command=lambda:pressExpression('+'))button6_3.place(x=192.5, y=335, width=50, height=35)root.mainloop()if __name__ == '__main__':Demo()

5.使用列表实现队列抽象数据类型，将列表的后端作为队列的尾部。

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

6.设计和实现一个实验，对比两种队列实现的性能。能从该实验学到什么？

以队列的入队操作为例，第一个队列以列表头部做队头，第二个队列以列表尾部做队头。

import timeitimport matplotlib.pyplot as pltclass Queue1:def __init__(self):self.items = []def isEmpty(self):return self.items == []def enqueue(self, item):self.items.append(item)def dequeue(self):return self.items.pop(0)def size(self):return len(self.items)class Queue2: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)lenx = []q1y = []q2y = []color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']if __name__ == '__main__':Q1 = Queue1()Q2 = Queue2()for i in range(100, 200000, 5000):t1 = timeit.Timer("Q1.enqueue(%d)" % i,"from __main__ import Q1")t2 = timeit.Timer("Q2.enqueue(%d)" % i, "from __main__ import Q2")x = list(range(i))Q1.items = xq1_time = t1.timeit(number=1)x = list(range(i))Q2.items = xq2_time = t2.timeit(number=1)print("%d, %15.8f, %15.8f" % (i, q1_time, q2_time))lenx.append(i)q1y.append(q1_time)q2y.append(q2_time)ax = plt.gca()# 去掉边框ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')# 移位置 设为原点相交ax.xaxis.set_ticks_position('bottom')ax.spines['bottom'].set_position(('data', 0))ax.yaxis.set_ticks_position('left')ax.spines['left'].set_position(('data', 0))plt.ylim(0, 0.0003)q1dot = plt.scatter(lenx, q1y, c=color[3], edgecolors='r', label='Q1')q2dot = plt.scatter(lenx, q2y, c=color[1], edgecolors='b', marker='^', label='Q2')plt.xlabel('lenth(list&dict)')plt.ylabel('time(/s)')plt.title('Q1&Q2_enqueue()_analysis')plt.legend()plt.show()

结果如图：

由实验知：

以列表头部做队头的队列入队操作的时间复杂度为常数阶：O(111)以列表尾部做队头的队列入队操作的时间复杂度为线性阶：O(nnn)

7.实现一个队列，使其添加操作和移除操作的平均时间复杂度为O(111)。这意味着在大多数情况下，两个操作的时间复杂度都是O(111)，仅在一种特殊情况下，移除操作为O(nnn)。

【存疑】

考虑输入受限的双端队列，即允许在一端进行添加和删除，另一端只允许删除。

class Dequeue:def __init__(self):self.items = []def isEmpty(self):return self.items == []def addRear(self, item):self.items.append(item)def removeFront(self):return self.items.pop(0)def removeRear(self):return self.items.pop()def size(self):return len(self.items)if __name__ == '__main__':deq = Dequeue()deq.addRear(2)print(deq.items)

8.考虑现实生活中的一个情景。完整地定义问题，并且设计一个模拟来解决它。

以排队等待洗车——求顾客平均等待时间为例：假设在给定的一小时内，这家洗车店总有十个顾客，并且每人都洗一次车。那么每小时平均有10个洗车任务，相当于每 60/10 = 6分钟（360秒）有一个任务，即在任意一秒，创建一个洗车任务的概率为1/360，通过1~360的随机数模拟每秒内产生洗车任务的概率。若随机数=360，则认为创建洗车任务。

创建三个类：WashingCar、Task、Queue分别模拟洗车店、洗车任务、队列。假设车的类型分三类：小型车、中型车、大型车，并规定若洗车店洗小车的速度为 N mins洗一辆，则洗一辆中型车需 2N mins,大型车 3N mins。车类型通过1~3的随机数来模拟。

import randomfrom chapter3.queue import Queueclass Task:def __init__(self, time):self.timestamp = timeself.carclass = random.randrange(1, 4)def getStamp(self):return self.timestampdef getCarclass(self):return self.carclassdef waitTime(self, currenttime):return currenttime - self.timestampclass WashingCar:def __init__(self, ppm):self.carrate = ppmself.currentTask = Noneself.timeRemaining = 0def tick(self):if self.currentTask != None:self.timeRemaining -= 1if self.timeRemaining <= 0:self.currentTask = Nonedef busy(self):if self.currentTask != None:return Trueelse:return Falsedef startNext(self, newtask):self.currentTask = newtaskself.timeRemaining = newtask.getCarclass()*60*self.carratedef simulation(numseconds, minutesPercar):washing = WashingCar(minutesPercar)carsQueue = Queue()waitingtimes = []for currentSecond in range(numseconds):if newwashingTask():task = Task(currentSecond)carsQueue.enqueue(task)if (not washing.busy()) and (not carsQueue.isEmpty()):nexttask = carsQueue.dequeue()waitingtimes.append(nexttask.waitTime(currentSecond))washing.startNext(nexttask)washing.tick()averageWait = sum(waitingtimes) / len(waitingtimes)print("Average wait %6.2f secs %3d tasks remaining." % (averageWait, carsQueue.size()))def newwashingTask():num = random.randrange(1, 361)if num == 360:return Trueelse:return Falseif __name__ == '__main__':for i in range(10):simulation(3600, 5)

9. 修改传土豆模拟程序，允许随机计数，从而使每一轮的结果都不可预测。

from chapter3.queue import Queueimport randomdef hotPotato(namelist):q = Queue()for name in namelist:q.enqueue(name)while q.size() > 1:num = n = random.randrange(1, 101)for i in range(num):q.enqueue(q.dequeue())q.dequeue()return q.dequeue()if __name__ == '__main__':namelist =['Bill', 'David', 'Susan', 'Jane', 'Kent', 'Brad']for i in range(10):print("第%d次出局人: %s" % (i+1 , hotPotato(namelist)))

10.实现一个基数排序器。

十进制数的基数排序利用1个主桶和10个数位桶。每个桶就像一个队列，并且根据数字到达的先后顺序来维持其中的值。该算法首先将所有的数都放在主桶中，然后按照数值中的每一个数位来考察这些值。第一个值从主桶中移除并且根据在考察的数位将其放到对应的数位桶中。如果考察的是个位，那么534将被放在4号数位桶中，667则放在7号数位桶中。一旦所有的值都被放在了相应的数位桶中，便依次从0号到9号数位桶中将值放回主桶。重复整个过程到数字的十位、百位等。在最后一个数位被处理完之后，主桶里面就是排好序的值。

网上找了一个过程图（已包浆🤣）

参考链接：/double_happiness/article/details/72452243

link

咱们这是用队列来表示题目的桶：

from chapter3.queue import Queuedef cardinalitysorted(alist):result = []masterq = Queue()numslist = []maxnumlen = 0for i in range(10):numslist.append(Queue())for i in range(len(alist)):maxnumlen = max(maxnumlen, len(str(alist[i])))masterq.enqueue(alist[i])for i in range(maxnumlen):while not masterq.isEmpty():cur = masterq.dequeue()radix = int(cur / (10 ** i) % 10)numslist[radix].enqueue(cur)for j in range(10):while not numslist[j].isEmpty():masterq.enqueue(numslist[j].dequeue())for i in range(len(alist)):result.append(masterq.dequeue())return resultif __name__ == '__main__':ml = [54, 678, 3215, 57, 4123, 3, 3535, 90]print(cardinalitysorted(ml))

11.HTML 中也存在括号匹配问题。标签有开始和结束两种形式，并且需要互相匹配才能正确描述网页内容。写一个程序来检查HTML文档中的标签是否正确匹配。

下面是简单的html文档，用于展示标签的匹配和嵌套。

<html><head><title>example</title></head><body><h1>hello world</h1></body></html>

from chapter3.stack import Stackdef parCheckerHtml(symbolString):s = Stack()matched = Trueindex = 0while index < len(symbolString) and matched:str = symbolString[index]if str in ["<html>", "<head>", "<title>", "<body>","<h1>"]:s.push(str)if str in ["</html>", "</head>", "</title>", "</body>","</h1>"]:if s.isEmpty():matched = Falseelse:top = s.pop()if not matches(top, str):matched = Falseindex += 1if matched and s.isEmpty():return Trueelse:return Falsedef matches(left, right):lefts = ["<html>", "<head>", "<title>", "<body>","<h1>"]rights = ["</html>", "</head>", "</title>", "</body>","</h1>"]return lefts.index(left) == rights.index(right)if __name__ == '__main__':file_path = "test.html"string = open(file_path).read().split()print(parCheckerHtml(string))

12.扩展代码清单3-15 中的回文检测器，使其可以处理包含空格的回文。如果忽略其中的空格，那么I PREFER PI 就是回文。

from chapter3.dequeue import Dequeuedef palchecker(aString):chardeque = Dequeue()for ch in aString:if ch == ' ':continuechardeque.addRear(ch)matched = Truewhile matched and chardeque.size() > 1:left = chardeque.removeRear()right = chardeque.removeFront()if left != right:matched = Falsereturn matchedif __name__ == '__main__':str = "I PREFER PI"print(str)print(palchecker(str))

13. 本章通过计算列表中节点的个数来实现length 方法。另一种做法是将节点个数作为额外的信息保存在列表头中。请修改UnorderedList 类的实现，使其包含节点个数信息，并且重新实现length 方法。

&

14. 实现remove 方法，使其能正确处理待移除元素不在列表中的情况。

class unorderList:def __init__(self):self.head = Noneself.lenth = 0def isEmpty(self):return self.head == Nonedef add(self, item):temp = Node(item)temp.setNext(self.head)self.head = tempself.lenth += 1def length(self):return self.lenthdef search(self, item):q = self.headfound = Falsewhile not found and q != None:if q.getData() == item:found = Trueq = q.getNext()return founddef remove(self, item):try:q = self.headpre = Nonefound = Falsewhile not found:if q.getData() == item:found = Trueelse:pre = qq = q.getNext()if pre == None:self.head = q.getNext()else:pre.setNext(q.getNext())self.lenth -= 1except:print("待移除的元素不在列表中")

15. 修改列表类，使其能支持重复元素。这一改动会影响到哪些方法？

&

16. 实现UnorderedList类的__str__方法。列表适合用什么样的字符串表示？

&

17. 实现__str__方法，使列表按照Python 的方式来显示（使用方括号）。

&

18. 实现无序列表抽象数据类型剩余的方法：append、index、pop 和insert。

&

19. 实现UnorderedList 类的slice 方法。该方法接受start和stop两个参数， 并且返回一个从start位置开始，到stop位置结束的新列表（但不包含stop位置上的元素）。

from chapter3.node import Nodeclass unorderList:def __init__(self):self.head = Noneself.lenth = 0def __str__(self):string = ''p = self.headwhile p != None:if p.getNext() != None:string += str(p.getData()) + ','else:string += str(p.getData())p = p.getNext()# return stringreturn '[' +string+ ']'def append(self, alist):p = self.headwhile p.getNext() != None:p = p.getNext()p.setNext(alist.head)def index(self, item):p = self.headidx = 0while p != None:if str(p.getData()) == str(item):breakp = p.getNext()idx += 1return idxdef pop(self):p = self.headpre = Noneif p == None:return "空列表无法pop()"while p.getNext() != None:pre = pp = p.getNext()if pre != None:pre.setNext(None)self.lenth -= 1return p.getData()else:self.head = Noneself.lenth = 0return p.getData()def insert(self, idx, item):try:p = self.headpre = self.headtemp = Node(item)if idx == 0:temp.setNext(self.head)self.head = tempself.lenth += 1return selfelif idx < 0:return "Input Error"else:for i in range(idx):pre = pp = p.getNext()pre.setNext(temp)temp.setNext(p)self.lenth += 1return selfexcept:print("Input Error")def slice(self, start, stop):p = self.headi ,j= 0, starttemplist = unorderList()while i < start:p = p.getNext()i += 1templist.head = ppre = templist.headtemplist.lenth += 1while j < stop and p.getNext()!=None:pre = pp = p.getNext()j += 1pre.setNext(None)return templistdef isEmpty(self):return self.head == Nonedef add(self, item):temp = Node(item)temp.setNext(self.head)self.head = tempself.lenth += 1def length(self):return self.lenthdef search(self, item):q = self.headfound = Falsewhile not found and q != None:if q.getData() == item:found = Trueq = q.getNext()return founddef remove(self, item):try:q = self.headpre = Nonefound = Falsewhile not found:if q.getData() == item:found = Trueelse:pre = qq = q.getNext()if pre == None:self.head = q.getNext()else:pre.setNext(q.getNext())self.lenth -= 1except:print("待移除的元素不在列表中")if __name__ == '__main__':mylist = unorderList()mylist.add(12)mylist.add(12)mylist.add(456)mylist.add(23)mylist.add(157)mylist.add(13)mylist.add(17)list2 = unorderList()list2.add(1)list2.add(2)mylist.append(list2)print(mylist)print(mylist.index('23'))p = mylist.headprint(mylist.pop())print(mylist)mylist1 = mylist.insert(0, 66)print(mylist1)mylist2 = mylist.slice(3,4)

20. 实现有序列表抽象数据类型剩余的方法。

from chapter3.node import Nodeclass orderList:def __init__(self):self.head = Noneself.lenth = 0def __str__(self):string = ''p = self.headwhile p != None:if p.getNext() != None:string += str(p.getData()) + ','else:string += str(p.getData())p = p.getNext()# return stringreturn '[' +string+ ']'def append(self, alist):newlist = selfq = alist.headprint(q.getData())while q != None:p = newlist.headpre = pdata = q.getData()temp = Node(data)if data < p.getData():temp.setNext(p)newlist.head = tempnewlist.lenth += 1q = q.getNext()else:while p != None :if data < p.getData():breakpre = pp = p.getNext()q = q.getNext()pre.setNext(temp)temp.setNext(p)newlist.lenth += 1return newlistdef index(self, item):p = self.headidx = 0while p != None:if str(p.getData()) == str(item):breakp = p.getNext()idx += 1return idxdef pop(self):p = self.headpre = Noneif p == None:return "空列表无法pop()"while p.getNext() != None:pre = pp = p.getNext()if pre != None:pre.setNext(None)self.lenth -= 1return p.getData()else:self.head = Noneself.lenth = 0return p.getData()def insert(self, idx, item):try:p = self.headpre = self.headtemp = Node(item)if idx == 0:temp.setNext(self.head)self.head = tempself.lenth += 1return selfelif idx < 0:return "Input Error"else:for i in range(idx):if item < p.getData():return "Input Error"print("aaaa",i)pre = pp = p.getNext()if item > p.getData():return "Input Error"pre.setNext(temp)temp.setNext(p)self.lenth += 1return selfexcept:print("Input Error")def slice(self, start, stop):p = self.headi ,j= 0, start+1templist = orderList()while i <= start:p = p.getNext()i += 1templist.head = ppre = templist.headtemplist.lenth += 1while j <= stop and p:pre = pp = p.getNext()j += 1pre.setNext(None)return templistdef isEmpty(self):return self.head == Nonedef add(self, item):p = self.headpre = Nonetemp = Node(item)while p != None:if item < p.getData():break;pre = pp = p.getNext()if pre == None:temp.setNext(self.head)self.head = tempelse:temp.setNext(p)pre.setNext(temp)def length(self):count = 0q = self.headwhile q != None:count += 1q = q.getNext()return countdef search(self, item):q = self.headfound = Falsewhile not found and q != None:if q.getData() == item:found = Trueelif q.getData() > item:breakq = q.getNext()return founddef remove(self, item):q = self.headpre = Nonefound = Falsewhile not found:if q.getData() == item:found = Trueelse:pre = qq = q.getNext()if pre == None:self.head = q.getNext()else:pre.setNext(q.getNext())if __name__ == '__main__':mylist = orderList()mylist.add(9)mylist.add(8)mylist.add(7)mylist.add(6)mylist.add(5)mylist.add(2)list2 = orderList()list2.add(4)list2.add(3)list2.add(11)print(mylist)print(list2)mylist.append(list2)print(mylist)print(mylist.index('5'))print(mylist.pop())print(mylist)print(mylist.insert(2,1))

21. 思考有序列表和无序列表的关系。能否利用继承关系来构建更高效的实现？试着实现这个继承结构。

有序列表对于无序列表只是多了一个有序属性，有序可以继承父类无序。

from chapter3_answer.t15_19 import unorderListfrom chapter3.node import Nodeclass orderList(unorderList):def __init__(self):self.head = Noneself.lenth = 0def __str__(self):return super(orderList, self).__str__()def append(self, alist):newlist = selfq = alist.headprint(q.getData())while q != None:p = newlist.headpre = pdata = q.getData()temp = Node(data)if data < p.getData():temp.setNext(p)newlist.head = tempnewlist.lenth += 1q = q.getNext()else:while p != None :if data < p.getData():breakpre = pp = p.getNext()q = q.getNext()pre.setNext(temp)temp.setNext(p)newlist.lenth += 1return newlistdef index(self, item):return super(orderList, self).index(item)def pop(self):print("pop")return super(orderList, self).pop()#def insert(self, idx, item):try:p = self.headpre = self.headtemp = Node(item)if idx == 0:temp.setNext(self.head)self.head = tempself.lenth += 1return selfelif idx < 0:return "Input Error"else:for i in range(idx):if item < p.getData():return "Input Error"pre = pp = p.getNext()if item > p.getData():return "Input Error"pre.setNext(temp)temp.setNext(p)self.lenth += 1return selfexcept:print("Input Error")def slice(self, start, stop):p = self.headi, j = 0, start + 1templist = orderList()while i <= start:p = p.getNext()i += 1templist.head = ppre = templist.headtemplist.lenth += 1while j <= stop and p:pre = pp = p.getNext()j += 1pre.setNext(None)return templistdef isEmpty(self):return super(orderList, self).isEmpty()def add(self, item):p = self.headpre = Nonetemp = Node(item)while p != None:if item < p.getData():break;pre = pp = p.getNext()if pre == None:temp.setNext(self.head)self.head = tempelse:temp.setNext(p)pre.setNext(temp)def length(self):return super(orderList, self).length()def search(self, item):q = self.headfound = Falsewhile not found and q != None:if q.getData() == item:found = Trueelif q.getData() > item:breakq = q.getNext()return founddef remove(self, item):q = self.headpre = Nonefound = Falsewhile not found:if q.getData() > item:return "待移除的元素不在列表中"elif q.getData() == item:found = Trueelse:pre = qq = q.getNext()if pre == None:self.head = q.getNext()else:pre.setNext(q.getNext())if __name__ == '__main__':mylist = orderList()mylist.add(9)mylist.add(8)mylist.add(7)mylist.add(6)mylist.add(5)mylist.add(2)list2 = orderList()list2.add(4)list2.add(3)list2.add(11)print(mylist)print(list2)mylist.append(list2)print(mylist)print(mylist.index('5'))print(mylist.pop())print(mylist)print(mylist.slice(0,3))

22. 使用链表实现栈。

from chapter3_answer.t15_19 import unorderListclass Stack(unorderList):def __init__(self):self.head = Noneself.lenth = 0def isEmpty(self):return super(Stack, self).isEmpty()def push(self, item):return super(Stack, self).add(item)def pop(self):p = self.headif p == None:return "list is null"else:pre = pp = p.getNext()self.head = pself.lenth -= 1return pre.getData()def peek(self):return self.head.getData()def size(self):return self.lenthif __name__ == '__main__':mylist = Stack()mylist.push(12)mylist.push(456)mylist.push(23)mylist.push(157)mylist.push(13)mylist.push(17)print(mylist)print(mylist.lenth)print(mylist.pop())print(mylist.lenth)print(mylist.peek())

23.使用链表实现队列。

from chapter3_answer.t15_19 import unorderListclass Queue(unorderList):def __init__(self):self.head = Noneself.lenth = 0def isEmpty(self):return super(Queue, self).isEmpty()def enqueue(self, item):return super(Queue, self).add(item)def dequeue(self):return super(Queue, self).pop()def size(self):return self.lenthif __name__ == '__main__':q = Queue()q.enqueue(1)q.enqueue(2)q.enqueue(3)print(q)print(q.dequeue())print(q.size())q.dequeue()q.dequeue()print(q.isEmpty())

24. 使用链表实现双端队列。

from chapter3_answer.t15_19 import unorderListfrom chapter3.node import Nodeclass Dequeue(unorderList):def __init__(self):self.head = Noneself.lenth = 0def isEmpty(self):return super(Dequeue, self).isEmpty()def addFront(self, item):p = self.headtemp = Node(item)if p == None:return super(Dequeue, self).add(item)else:while p.getNext() != None:p = p.getNext()p.setNext(temp)self.lenth += 1def addRear(self, item):return super(Dequeue, self).add(item)def removeFront(self):return super(Dequeue, self).pop()def removeRear(self):p = self.headif p == None:return "list is null"else:pre = pp = p.getNext()self.head = pself.lenth -= 1return pre.getData()def size(self):return self.lenthif __name__ == '__main__':deq = Dequeue()deq.addFront(1)deq.addRear(2)deq.addFront(7)deq.addFront(5)print(deq)print(deq.removeFront())print(deq.removeRear())print(deq)

25. 设计和实现一个实验，比较用链表实现的列表与Python列表的性能。

以列表的插入insert为例：

from chapter3_answer.t15_19 import unorderListimport timeitimport matplotlib.pyplot as pltlenx = []insert1y = []insert2y = []color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']if __name__ == '__main__':L = unorderList()for i in range(100, 200000, 5000):t1 = timeit.Timer("x.insert(0, %d)" % i, "from __main__ import random, x")t2 = timeit.Timer("L.insert(0, %d)" % i, "from __main__ import random, L")x = list(range(i))inserttime1 = t1.timeit(number=1)for m in range(i):L.add(m)inserttime2 = t2.timeit(number=1)print("%d, %15.6f，%15.6f" % (i, inserttime1, inserttime2))lenx.append(i)insert1y.append(inserttime1)insert2y.append(inserttime2)ax = plt.gca()# 去掉边框ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')# 移位置 设为原点相交ax.xaxis.set_ticks_position('bottom')ax.spines['bottom'].set_position(('data', 0))ax.yaxis.set_ticks_position('left')ax.spines['left'].set_position(('data', 0))plt.ylim(0, 0.0002)plt.scatter(lenx, insert1y, c=color[3], edgecolors='r', label='List')plt.scatter(lenx, insert2y, c=color[1], edgecolors='b', marker='^', label='Node')plt.xlabel('lenth(list)')plt.ylabel('time(/s)')plt.title('List&Node_insert_analysis')plt.legend()plt.show()

结果如图：

python列表的插入操作是线性阶，链表实现列表的插入操作是常数阶。

26. 设计和实现一个实验，比较基于python列表的栈和队列与相应链表实现的性能。

以队列的入队操作为例：

from chapter3.queue import Queue as Q1from chapter3_answer.t23 import Queue as Q2import timeitimport randomimport numpy as npimport matplotlib.pyplot as pltimport pandas as pdlenx = []enqueue1y = []enqueue2y = []color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']if __name__ == '__main__':q1 = Q1()q2 = Q2()for i in range(100, 200000, 5000):t1 = timeit.Timer("q1.enqueue(%d)" % i, "from __main__ import random, x,q1")t2 = timeit.Timer("q2.enqueue(%d)" % i, "from __main__ import random, q2")x = list(range(i))for j in x:q1.enqueue(j)enqueuetime1 = t1.timeit(number=1)for m in range(i):q2.enqueue(m)enqueuetime2 = t2.timeit(number=1)print("%d, %15.6f，%15.6f" % (i, enqueuetime1, enqueuetime2))lenx.append(i)enqueue1y.append(enqueuetime1)enqueue2y.append(enqueuetime2)ax = plt.gca()# 去掉边框ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')# 移位置 设为原点相交ax.xaxis.set_ticks_position('bottom')ax.spines['bottom'].set_position(('data', 0))ax.yaxis.set_ticks_position('left')ax.spines['left'].set_position(('data', 0))plt.ylim(0, 0.001)plt.scatter(lenx, enqueue1y, c=color[3], edgecolors='r', label='List')plt.scatter(lenx, enqueue2y, c=color[1], edgecolors='b', marker='^', label='Node')plt.xlabel('lenth(list)')plt.ylabel('time(/s)')plt.title('List&Node_Queue.enqueue()_analysis')plt.legend()plt.show()

结果如图：

python列表实现队列的入队操作是线性阶，链表实现队列的入队操作是常数阶。

27. 由于每个节点都只有一个引用指向其后的节点，因此本章给出的链表实现成为单向链表。另一种实现成为双向链表。在这种实现中，每一个节点都有指向后一个节点的引用（通常称为next）和指向前一个节点的引用（通常称为back）。头引用同样也有两个引用，一个指向链表中的第一个节点，另一个指向最后一个节点。请用Python实现双向链表。

from chapter3.node import Nodefrom chapter3_answer.t15_19 import unorderListclass DNode(Node):def __init__(self, initdata):super(DNode, self).__init__(initdata)self.back = Nonedef getBack(self):return self.backdef setBack(self, newback):self.back = newbackclass DList(unorderList):def __init__(self):super(DList, self).__init__()def add(self, item):temp = DNode(item)temp.setNext(self.head)p = self.headif p == None:self.head = tempprint(self.head.getData())self.head.setBack(temp)self.head.setNext(None)self.lenth += 1else:while p.getNext() != None:p = p.getNext()temp.setBack(p)temp.setNext(self.head)self.head.setBack(temp)self.head = tempself.lenth += 1if __name__ == '__main__':list = DList()list.add(1)list.add(2)list.add(3)print(list)print(list.head.getBack().getData())print(list.head.getNext().getData())

28. 为队列创建一个实现，使得添加操作和移除操作的平均时间复杂度是O(1)O(1)O(1)。

考虑循环队列：

class CircularQueue:def __init__(self, maxsize):self.items = [None]*maxsizeself.maxsize = maxsizeself.front = 0self.rear = 0self.length = 0def isEmpty(self):return self.front == self.reardef enqueue(self, item):if (self.rear+1) % self.maxsize == self.front:return "Error: the queue is full and maxsize = %d"%self.maxsizeself.rear = (self.rear+1) % self.maxsizeself.items[self.rear] = itemself.length += 1return selfdef dequeue(self):if self.isEmpty():return "Error: the queue is none"self.front = (self.front + 1) % self.maxsizex = self.items[self.front]self.items[self.front] = Noneself.length -= 1return xdef size(self):return self.lengthif __name__ == '__main__':deq = CircularQueue(100)deq.enqueue(1)deq.enqueue(2)deq.enqueue(3)deq.enqueue(4)deq.enqueue(5)deq.enqueue(6)print(deq.items)print(deq.dequeue())print(deq.items)print(deq.rear)print(deq.front)for i in range(deq.front+1, deq.rear+1):print(deq.items[i])

三、总结

主要学习了栈、队列、链表的构建和应用，以及用随机数模拟概率等。

如：

用栈求解后序表达式队列模拟打印任务，基数排序法双端队列检测回文