网站建设公司选哪个好,新闻株洲最新,wordpress打开很卡,办公室工作绩效 网站建设python 数据结构与算法1 python常见数据结构性能1.1 List1.1.1 安索引取值和赋值1.1.2 列表append和__add__()1.1.3 使用timeit模块测试执行时间1.1.4 List基本操作的大O数量级1.2 Dict1.2.1 dict数据类型2 线性结构 Linear Structure2.1 栈Stack2.1.1 抽象数据类型Stack2.1.2 …python 数据结构与算法1 python常见数据结构性能1.1 List1.1.1 安索引取值和赋值1.1.2 列表append和__add__()1.1.3 使用timeit模块测试执行时间1.1.4 List基本操作的大O数量级1.2 Dict1.2.1 dict数据类型2 线性结构 Linear Structure2.1 栈Stack2.1.1 抽象数据类型Stack2.1.2 Stack的操作如下2.1.3 栈的应用1简单括号匹配2.1.3.1 圆括号匹配2.1.3.2 通用括号匹配2.1.4 栈的应用2进制转换2.1.4.1 十进制转换二进制2.1.4.2 十进制转换任意进制2.1.5 栈的应用3表达式转换2.1.5.1 中缀表达式2.1.5.2 全括号中缀表达式2.1.5.3 前缀和后缀表达式2.1.5.4 中缀表达式转换为前缀和后缀形式2.1.5.5 通用的中缀转后缀算法2.1.5.6 后缀表达式求值2.2 队列Queue1 python常见数据结构性能1.1 List1.1.1 安索引取值和赋值list最常用的操作是按索引取值和赋值(va[i]a[i]v)这两个操作执行时间与列表大小无关均为O(1)。1.1.2 列表append和__add__()list.addend(v)执行时间是O(1)。list0 list1 [v]执行时间是O(nk)其中k是被加的列表长度。1.1.3 使用timeit模块测试执行时间使用timeit模块对函数计时1.1.4 List基本操作的大O数量级1.2 Dict1.2.1 dict数据类型字典是根据key找到对应的value最常用的取值get和赋值set其性能都是O(1)。另外一个常用的操作判断字典中是否存在某个key (in)这个性能也是O(1)。2 线性结构 Linear Structure线性结构是一种有序数据项的集合其中每个数据项都有唯一的前驱和后继(除了第一个和最后一个)。2.1 栈Stack栈是一种有次序的数据项集合在栈中数据项的加入和移除都仅发生在同一端这一端叫做“栈顶top”另一端叫做“栈底base”。栈是一种后进先出LIFOLast in First out这是一种基于数据项保存时间的次序时间越短的离栈顶越近而时间越长的离栈底越近。2.1.1 抽象数据类型Stack抽象数据类型“栈”是一个有次序的数据集每个数据项仅从“栈顶”一端加入到数据集中、从数据集中移除栈具有后进先出LIFO的特性。2.1.2 Stack的操作如下stack()创建一个空栈不包含任何数据项。push(item)将item加入栈顶无返回值。pop()将栈顶的数据项移除并返回栈被修改。peek()“窥视”栈顶数据项返回栈顶的数据。isEmpty()返回是否是空栈。size()返回栈中有多少个数据项。class Stack(object):def __init__(self):self.stack []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def peek(self):if not self.is_empty():return self.stack[self.size()-1]def is_empty(self):return len(self.stack) 0def size(self):return len(self.stack)2.1.3 栈的应用1简单括号匹配2.1.3.1 圆括号匹配括号必须遵循“平衡”原则即每个开括号必须有一个比括号对应。从左到右扫描括号最新打开的左括号应该匹配最先遇到的右括号。这样第一个左括号就应该匹配最后一个右括号这种次序反转的识别正好符合栈的特性。流程图如下from data_structure.Stack.stack import Stackdef brackets_valid(expression):stack Stack()for item in expression:if item (:stack.push(item)elif item ):if stack.is_empty():return Falseelse:stack.pop()return stack.is_empty()if __name__ __main__:print(brackets_valid(()()()))print(brackets_valid((()())(()))print(brackets_valid(((56)*(43))((10-9)))2.1.3.2 通用括号匹配实际应用中会遇到更多种括号比如[], {},()。from data_structure.Stack.stack import Stackdef brackets_valid(expression):stack Stack()mapping {): (,]: [,}: {}for item in expression:if item in ([{:stack.push(item)elif item in )]}:if stack.is_empty():return Falseelse:if stack.peek() ! mapping[item]:return Falseelse:stack.pop()return stack.is_empty()if __name__ __main__:print(brackets_valid(()()()))print(brackets_valid((()())(()))print(brackets_valid(((56)*(43))((10-9)))print(brackets_valid({{([][])}()}))print(brackets_valid([[{{(())}}]]))print(brackets_valid([][][](){}))print(brackets_valid(([)}))print(brackets_valid(((()]))))print(brackets_valid([{()]))2.1.4 栈的应用2进制转换进制指用多少字符来表示整数。十进制是0-9十个数字字符二进制是0、1两个字符。例如十进制233对应的二进制是11101001具体算法如下233 2102 3101 310011101001 127 126 125 024 123 022 021 1*202.1.4.1 十进制转换二进制常见的十进制转换二进制采用的是**“除2求余数”的算法。如下35的二进制是100011。在除2求余的过程中得到的余数是从低到高的次序而输出则是从高到低所以需要一个栈来反转次序**。from data_structure.Stack.stack import Stackdef convert(num):if not isinstance(num, int):return Falsestack Stack()while num:num, remainder divmod(num, 2)stack.push(remainder)result while not stack.is_empty():result str(stack.pop())return resultif __name__ __main__:print(f35的二进制数是{convert(35)})2.1.4.2 十进制转换任意进制将“除2求余”改为“除N求余”就可以将上面的算法扩展为任意进制转换。十进制233对应八进制351十六进制是E9。主要区别是二进制0-1十进制0-9八进制0-7十六进制0-9A-Ffrom data_structure.Stack.stack import Stackdef convert(num, unit):if not isinstance(num, int):return Falsedights 0123456789ABCDEFstack Stack()while num:num, remainder divmod(num, unit)stack.push(remainder)result while not stack.is_empty():result str(dights[stack.pop()])return resultif __name__ __main__:print(f35的二进制数是{convert(35, 2)})print(f233的八进制数是{convert(233, 8)})print(f233的十六进制数是{convert(233, 16)})2.1.5 栈的应用3表达式转换2.1.5.1 中缀表达式操作符位于两个操作数之间的表示法称为“中缀”表达式。例如AB。2.1.5.2 全括号中缀表达式计算机处理时最好避免复杂的优先级(乘除优先于加减、括号优先级)规则能明确规定所有的计算顺序是最好的。因此引入全括号表达式 ((AB*C)D)2.1.5.3 前缀和后缀表达式前缀表达式将操作符移到操作数前面即AB。后缀表达式将操作符移到操作数后面即AB。在前缀和后缀表达式中操作符次序完全决定了运算的次序不再混淆。2.1.5.4 中缀表达式转换为前缀和后缀形式2.1.5.5 通用的中缀转后缀算法中缀表达式ABC对应的后缀表达式是 ABC。其中操作数ABC的顺序没有改变操作符的出现顺序在后缀表达式中反转了。由于*的优先级比高所以后缀表达式中操作符的出现顺序与运算次序一致。算法流程import stringfrom data_structure.Stack.stack import Stackdef convert_postfix(expression):result oper_stack Stack()priority {(: 0,: 1,-: 1,*: 2,/: 2}for item in expression:if item in string.ascii_letters or item in string.digits:result itemelif item (:oper_stack.push(item)elif item ):while oper_stack.peek() ! (:result oper_stack.pop()else:oper_stack.pop()elif item in -*/:while oper_stack.peek() and \priority[oper_stack.peek()] priority[item]:result oper_stack.pop()else:oper_stack.push(item)while not oper_stack.is_empty():result oper_stack.pop()return resultif __name__ __main__:print(convert_postfix(AB*C))print(convert_postfix((AB)*C))2.1.5.6 后缀表达式求值对于后缀表达式从左到右扫描由于操作符在操作数后面所以要暂存操作数在遇到操作符的时候再将暂存的两个操作数进行实际的计算。例如 ABC*先扫描到了ABC暂存到栈中扫描到*的时候从栈中弹出2个操作数做乘法做完之后再存入栈中继续扫描到从栈中弹出2个操作数做加法。注意对于-/操作符弹出的两个操作数顺序很重要先弹出的是右操作数后弹出的是左操作数。算法流程import stringfrom data_structure.Stack.stack import Stackfrom data_structure.Stack.infix_to_postfix import convert_postfixdef calculate(expression):stack Stack()for item in expression:if item in string.digits:stack.push(item)elif item in -*/:first stack.pop()second stack.pop()stack.push(str(eval(second item first)))return stack.pop()if __name__ __main__:print(calculate(convert_postfix(12*3)))print(calculate(convert_postfix((12)*3)))2.2 队列Queue
