文章目录
推荐两本口碑爆棚的Python算法&数据结构书。第一章：导论1.3 计算机科学1.3.1编程1.3.2为何学习数据结构及抽象数据类型1.3.3 为何学习算法1.4 python基础1.4.1 数据1.4.2 输入与输出1.4.3 控制结构1.4.4 异常处理1.4.5定义函数1.4.6python面向对象编程：定义类推荐两本口碑爆棚的Python算法&数据结构书。
1. 算法图解
2.Problem Solving with Algorithms and Data Structures Using Python SECOND EDITION
3.python数据结构与算法分析
🕸上面书籍的2和3时同一本书
开始学习，小伙伴们！😄
第一章：背景知识的准备
第二章：算法分析的内在思想
第三——七章：全面的介绍在经典计算机科学问题中出现的数据结构与算法
第八章：选学内容
第一章：导论
objective
复习计算机科学、编程以及解决问题方面的知识理解抽象这一概念及在解决问题过程中所发挥的作用理解并建立抽象数据类型的概念复习python
jupyter来记代码
md来整理知识点
1.3 计算机科学
计算机科学的研究对象是问题、解决问题的过程，以及通过该过程得到的解决方案。给定一个问题，计算机科学家的目标是开发一个能够逐步解决该问题的算法。算法是具有有限步骤的过程，依照这个过程便能解决问题。算法就是解决方案。
作者给出的定义:研究问题及其解决方案，以及研究目前无解的问题的学科。
1.3.1编程
编程是指通过编程语言将算法编码以使其能被计算机执行的过程。
1.3.2为何学习数据结构及抽象数据类型
这个地方我不知道作者在说什么
1.3.3 为何学习算法
问题通常有很多方案，选择一个解决方案并且确定其为最优秀的方案。
1.4 python基础
1.4.1 数据
python支持面向对象编程范式。
类都是idui数据的构成（状态）以及数据能做什么（行为）的描述。由于类的使用者只能看到数据项的状态和行为，因此类与抽象数据类型是相似的。
在面对对象编程范式中，数据项被称作对象，一个对象就是类的一个实例。
1.内建原子数据类型 数据类型：int float bool。数值类和布尔类数学运算符逻辑运算符
神奇的东西出来了：变量存的是指向数据的引用，而不是数据本身。（动态特性）
2.内建集合数据类型
列表、字符串以及元组 彼此有差异的有序集合 集（set）和字典 无序集合
列表：零个或多个指向python数据对象的引用的有序集合，通过在方括号内以逗号分隔的一系列值来表达。空列表[]。列表是异构的，意味着其指向的数据对象不需要都是同一个类，可以被赋值给一个变量。
列表有序，支持一系列序列运算。下表所示（很多东西适用于其他数据类型、字典、集、元组）
page9中小例子在python3.6中不适用
python列表提供的常用方法。下表所示
list和range组合，会经常碰到。
字符串：零个或多个字母、数字和其他符号的有序集合。里面的字母、数字和其他字符称为字符。
之前所有序列运算符都能用于字符串
此外，字符串还提供一些特有的方法。如下表所示
🕸split在处理数据非常有用，split接受一个字符串，返回一个由分隔符作为分割点的字符串列表，因此split方法也可以是制表符、换行符和空格等空白字符。
🕸列表和字符串的主要区别在于，列表能够被修改，字符串则不能。列表的这一特性被称为可修改性。
元组（tuple）
元组和列表都是异构数据序列，元组和列表非常相似，但不同的是不可修改（字符串）。元组通常写成由括号包含并且以逗号分隔的一系列值。
元组允许支持一系列序列运算，和列表一样。
集（set）是由零个或多个不可修改的python数据对象组成的无序集合。set无重复元素。表示方法：set()tip：类似于数学中的集合来理解，轻松搞定
python中集支持的运算
python提供的方法
字典：无序结构，元素对构成，键值对（键：值）。
tip：通过键访问其对应的值，也可以向字典中添加新的键值对。
其实，访问字典的语法与访问序列的语法相似。是通过键来访问，而不是通过下标。
键的位置是由散列来决定的。len函数对字典的功能对其他集合的功能相同。
字典既有运算符，又有方法。
python字典支持的运算
python字典提供的方法
1.4.2 输入与输出
用户交互。提示字符串input()
格式化字符串可用的类型
格式化修改符
1.4.3 控制结构
控制结构：迭代和分支
🕸attention：列表解析式
#列表解析式sqlist=[x*x for x in range(5)]sqlist
1.4.4 异常处理
语法错误File "<ipython-input-12-b3415ab79254>", line 2for i in range(10)^SyntaxError: invalid syntax
逻辑错误
异常发生时，程序抛出异常。用try语句来处理异常。
anumber=int(input("please enter an integer "))#learn english (math domain)#不会写啊import mathtry:print(math.sqrt(anumber))except:print('bad value for square root')print("using absolute value instead")print(math.sqrt(abs(anumber)))
except会捕捉到sqrt抛出的异常并打印提示信息。意味着程序并不会终止，而是继续执行后续语句。
也可以使用raise语句来触发运行时异常，下面的例子是创建新的RuntimeError异常的结果
#异常处理anumber=int(input("please enter an integer "))if anumber < 0:raise RuntimeError("you can't use a negative number")else:print(math.sqrt(anumber))
1.4.5定义函数
#通过牛顿迭代法求解平方根，搞不懂。功力尚浅def squareroot(n):root=n/2for k in range(20):root = (1/2)*(root+(n/root))return rootsquareroot(9)
1.4.6python面向对象编程：定义类
1.定义类
面向对象编程语言最强大的一项特性是允许程序员创建全新的类对求解问题所需的数据进行建模。
python中定义新类的做法是，提供一个类名以及一整套与函数定义语法类似的方法定义。
class Fraction:#方法定义
所有类首先都先提供构造方法。创建一个Fraction对象，提供分子分母两部分数据。在python中，构造方法总是命名__init__，如下所示。
class Fraction:def __init__(self,top ,bottom):# 构造方法self.num=topself.den=bottomdef show(self):print(self.num,"/",self.den)def __str__(self):return str(self.num)+"/"+str(self.den)def __add__(self,otherfraction):newnum=self.num * otherfraction.den +self.den*otherfraction.numnewden=self.den * otherfraction.den#欧几里得算法寻找最大公约数common=gcd(newnum,newden)return Fraction (newnum//common,newden//common)def __eq__(self,other):firstnum=self.num*other.densecondnum=self.den*other.numreturn firstnum== secondnum#__________________________________________________________________def gcd(m,n): #find num and den's greatest common divisor(最大公约数)函数while m%n != 0:oldm=moldn=nm=oldnn=oldm%oldnreturn nmyfraction=Fraction(3,5)myfraction.show()print(myfraction)f1=Fraction(1,4)f2=Fraction(3,4)f3=f1+f2print(f3)f4=Fraction(2,8)print(f1==f4)print(f1.__eq__(f4))
🕸self是一个总是指向对象本身的特殊函数。他必须是第一个形式参数。
🕸类通过方法创建了对象。
🕸__add__方法实现
🕸欧几里得算法寻找最大公因数
对于整数m和n，如果m能被n整除，那么他们的最大公因数就是n。如果m不能被n整除，那么结果是n与m除以n的余数的最大公因数。上述gcd为迭代实现。
🕸深浅相等
有两个Fraction对象，只有他们是同一个对象的引用时。f1==f2才为True，浅相等。下图实现不同引用但值相同的深相同。__eq__
2.继承：逻辑门与电路
继承使一个类与另一个类相关联，类似于孩子从父母那里继承了特征。
python中的子类可以从父类继承特征数据和行为。父类称为超类。
下图表示python中集合类的继承层次结构（有序和无序的区别：无序是指数据存入的顺序跟取出的顺序不一致）
#set为无序的,输入数据后会重新排列a=set(['lsi',3,5,2,238,1])#dict也是无序的，通过键值对来找adict={'name':'hd ' ,'age':12,'hobby': 'basketball'}print(adict)#有序的：列表、元组、字符串astr='hefhkakd'print(astr[2])atuple=(1,'4r','33r',3,4)print(atuple[1])alist=[1,2,'daad',5,6,7]print(alist[2])
下面介绍逻辑门的继承层次结构
class LogicGate:def __init__(self,n):self.label=nself.output=Nonedef getLabel(self):return self.label def getOutput(self):self.output=self.performGateLogic()return self.outputclass BinaryGate(LogicGate):def __init__(self,n):super().__init__(n)self.pinA=Noneself.pinB=Nonedef getPinA(self):return int(input('enter pin a input for gate'+\self.getLabel()+'-->'))def getPinB(self):return int(input('enter pin b input for gate'+\self.getLabel()+'-->'))class UnaryGate(LogicGate):def __init__(self,n):super().__init__(n)self.pin=Nonedef getPin(self):return int(input('enter pin input for gate'+\self.getLabel()+'-->'))class AndGate(BinaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):a=self.getPinA()b=self.getPinB()if a==1 and b==1:return 1else:return 0#或门的验证class OrGate(BinaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):a=self.getPinA()b=self.getPinB()if a==1 or b==1:return 1else:return 0#非门的验证class NotGate(UnaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):a=self.getPin()if a==1:return 0else:return 1g3=NotGate('G3')g3.getOutput()
HAS-A关系 （HAS-A意即“有一个”）
连接器
# 超类LogicGateclass LogicGate:def __init__(self,n):self.label = nself.output = Nonedef getLabel(self):return self.labeldef getOutput(self):self.output = self.performGateLogic()return self.output# 二引脚逻辑门class BinaryGate(LogicGate):def __init__(self,n):super().__init__(n)self.pinA = Noneself.pinB = Nonedef getPinA(self):if self.pinA == None:return int(input("Enter Pin A for gate" + self.getLabel() + "-->"))else:return self.pinA.getFrom().getOutput()def getPinB(self):if self.pinB == None:return int(input("Enter Pin B for gate" + self.getLabel() + "-->"))else:return self.pinB.getFrom().getOutput()def setNextPin(self,source):if self.pinA == None:self.pinA = sourceelse:if self.pinB == None:self.pinB = sourceelse:raise RuntimeError("Error: NO EMPTY PINS")# 单引脚逻辑门class UnaryGate(LogicGate):def __init__(self,n):super().__init__(n)self.pin = Nonedef getPin(self):if self.pin == None:return int(input("Enter Pin for gate" + self.getLabel() + "-->")) else:return self.pin.getFrom().getOutput()def setNextPin(self,source):if self.pin == None:self.pin = sourceelse:print("Cannot Connect: NO EMPTY PINS on this gate")# 与门class AndGate(BinaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):self.pinA = self.getPinA()self.pinB = self.getPinB()if self.pinA == 1 and self.pinB == 1:return 1else:return 0# 与非门class NandGate(BinaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):self.pinA = self.getPinA()self.pinB = self.getPinB()if self.pinA == 1 and self.pinB == 1:return 0else:return 1# 或非门class NorGate(BinaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):self.pinA = self.getPinA()self.pinB = self.getPinB()if self.pinA == 0 and self.pinB == 0:return 1else:return 0# 或门class OrGate(BinaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):self.pinA = self.getPinA()self.pinB = self.getPinB()if self.pinA == 1 or self.pinB == 1:# pinA = self.getPinA()# pinB = self.getPinB()# if pinA == 1 or pinB == 1:return 1else:return 0 # 异或门class NorGate(BinaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):self.pinA = self.getPinA()self.pinB = self.getPinB()if self.pinA == self.pinB:return 0else:return 1# 非门class NotGate(UnaryGate):def __init__(self,n):super().__init__(n)def performGateLogic(self):self.pin = self.getPin()if self.pin==1:return 0else:return 1class Connector():def __init__(self,fgate,tgate):self.fromgate = fgateself.togate = tgatetgate.setNextPin(self)def getFrom(self):return self.fromgatedef getTo(self):return self.togateif __name__=="__main__":g1 = AndGate("G1")g2 = AndGate("G2")g3 = OrGate("G3")g4 = NotGate("G4")c1 = Connector(g1,g3)c2 = Connector(g2,g3)c3 = Connector(g3,g4)print(g4.getOutput())
