《数据结构》课件1第1章基础

主要学习内容Python基础知识12Python面向对象编程3数据结构和算法相关模块Python基础知识Python诞生于1990年支持面向对象的解释型计算机程序设计语言单句代码交互式执行源程序批量运行两个系列，互不兼容：2.x停止更新3.x持续发展查看Python版本python-V概述几种主流程序设计语言对比

PythonJavaCC++C#JavaScript运行效率★★★★★★★★★★★★学习曲线★★★★★★★★★★★代码移植性★★★★★★★★★★★★开发效率★★★★★★★★★★★★适用领域★★★★★★★★★★★★解释型语言VS编译型语言运行环境官网下载解释器/downloads/首先，选择合适的版本，例如：3.9.1然后，根据自己的操作系统选择对应安装程序开始菜单选择Python交互编程界面集成开发环境-IDLEPython解释器自带PycharmJetBrains开发的优秀Python开发环境变量变量需要使用内存变量的三个属性名值地址Python变量无需定义即可直接赋值Python解释器会根据赋值自动推导出变量的类型Python变量的地址在赋值后可能发生变化数值类型四种数值类型：整型(int)浮点型(float)复数型(complex)布尔型(bool)整型最简单且常用的数据类型Python的整型使用时无须担心变量的“溢出”随着整型变量值的大小而动态改变所用内存的大小整型的运算加减乘除乘方求余浮点型浮点型会出现舍入误差计算机表示浮点数“先天不足”下面两个语句结果不等print(0.1*26) #0.1乘以26print(0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1) #26个0.1连加判断两个浮点数相等求二者差的绝对值，判断是否小于一个很小的值复数型复数由实部和虚部组成a+bj其中a表示实部，b表示虚部real属性可以得到复数的实部imag属性可以得到复数的虚部conjugate方法可以得到当前对象的共轭复数复数直接支持加、减、乘、除和乘方数学操作对复数执行复杂的数学运算，需要引入cmath模块布尔型只有两个值TrueFalse布尔型和数字进行数学运算1+True字符串字符串是数值型之外使用最多的数据类型Python的字符串明显的特色多样的书写方式负索引灵活的切片字符串是不可修改的如果需要对字符串进行修改，实质是得到一个新的字符串字符串常量四种方式单引号'hello'双引号"I'mastudent."三个单引号三个双引号转义符反斜杠'\'是转义符在字符串常量前面写一个r抑制转义print("C:\\Users\\Public\\Downloads")print(r"C:\Users\Public\Downloads")转义表示形式描述\\反斜杠符号\'单引号\"双引号\b退格(Backspace)\n换行\v纵向制表符\t横向制表符\r回车字符串索引正向索引从0开始负索引从-1开始字符串切片切片可以非常方便地得到字符串的子串或者子串的变形字符串[起点：终点：步长]切片例子str1="Soochow"print(str1[2:4:1]) #对第2个和第3个字符切片print(str1[2:4:]) #对第2个和第3个字符切片print(str1[::2]) #从头到尾，每隔一个字符切片print(str1[::-1]) #通过切片得到字符串的逆序串字符串常见操作字符串连接print('Soochow'+"University") #字符串连接字符串重复print("dog"*3) #字符串重复3次得到字符内码print(ord('A')) #得到'A'的内码根据内码得到字符print(chr(97)) #得到97作为内码所对应的字符字符串常用方法方法说明string.count()返回字符串指定子串出现的次数string.endswith()检查字符串是否以指定字符串结束string.find()查找子串，如果存在返回开始的索引值，否则返回-1string.index()和find()方法一样，但如果子串不存在将会出现一个异常string.isalnum()如果string所有字符都是字母或数字则返回True，则返回Falsestring.isalpha()如果string所有字符都是字母返回True，否则返回Falsestring.isdecimal()如果string只包含十进制数字返回True，否则返回Falsestring.isdigit()如果string只包含数字则返回True否则返回Falsestring.isnumeric()如果string只包含数字字符，则返回True，否则返回Falsestring.isspace()如果string只包含空格，则返回True，否则返回Falsestring.join()拼接字符串string.lower()转换string所有大写字符为小写string.replace()字符串替换string.rfind()类似于find()方法，但是从右边开始查找string.rindex()类似于index()方法，但是从右边开始查找string.split()拆分字符串string.startswith()检查字符串是否以指定字符串开头string.title()所有单词转换为大写开始，其余字母均为小写string.upper()转换string的小写字母为大写Python内置组合类型四种内置组合类型列表元组字典集合列表列表相当于其他语言中的动态数组可以通过下标便捷地访问列表的元素可以很容易地修改列表、添加和删除元素列表自带了排序、逆序等方法Python中的列表可以是异构的一个列表中每个元素的类型可以不一样列表简单例子lst1=[] #空列表print(lst1)lst2=[1,2,3] #列表初始化print(lst2)lst3=[1,'abc',[3,4]] #元素类型不同的列表print(lst3)lst4=list("hello") #将字符串转换为列表print(lst4)列表常用操作和字符串的操作可以通过+运算符实现两个列表的连接可以用*运算符实现把一个列表重复n次列表常用函数函数说明len()返回列表元素个数list()将其他序列转换为列表max()返回列表元素最大值min()返回列表元素最小值sorted()返回排序的结果通过切片修改列表可以通过切片修改列表元素如下的代码把列表中的元素修改成了0和1交替的数值。lst=[1,2,3,4,5,6,7,8,9]lst[::2]=[0]*len(lst[::2])lst[1::2]=[1]*len(lst[1::2])print(lst)列表常用方法方法说明list.append()在列表末尾添加新的对象list.clear()清空列表list.copy()复制列表list.count()统计某个元素在列表中出现的次数list.extend()在列表末尾扩展某个列表中的所有元素list.index()从列表中找出某个值第一个匹配项的索引位置list.insert()将对象插入列表指定的位置list.pop()删除列表中的一个元素（默认最后一个元素），且返回该元素值list.remove()基于值删除列表中的第一个匹配项list.reverse()逆序列表中元素list.sort()对列表进行排序append和extend辨析append方法lst=[1,3,5]lst.append([2,7])print(lst)结果是：[1,3,5,[2,7]]extend方法lst=[1,3,5]lst.extend([2,7])print(lst)结果是：[1,3,5,2,7]sort方法和sorted函数辨析二者都可以对列表排序sort方法对当前对象排序当前对象会被修改成排序后的结果该方法的返回结果是Nonelst=[1,2,5,3]lst.sort() #lst中的数据被排序sorted函数第一个参数是待排序的数据但是并不会修改它将排序结果以列表形式返回lst=[1,2,5,3]res=sorted(lst) #lst中的数据保持原序，res中是排序的结果列表的浅拷贝和深拷贝Python列表之间赋值默认是浅拷贝lst1=[1,3,5]lst2=lst1lst2[2]=7print(lst1) #此时lst1也已经变成了[1,3,7]列表的深拷贝lst1=[1,3,5]lst2=lst1.copy() #利用copy方法实现lst2和lst1分别是独立的内存lst3=lst1[::] #利用分片实现lst3和lst1分别是独立的内存元组元组可以看成不可修改的列表有些数据是只读数据选用元组将会避免误修改数据导致程序逻辑错误元组定义使用圆括号空的元组就是一对空的圆括号tup1=() #空元组如果元组只包含一个元素，需要在此元素后面添加逗号tup2=(3,) #一个元素的元组从列表得到元组lst=['武汉','孝感','黄冈']tups=tuple(lst) #从列表得到元组元组补充说明元组的元素不可以删除可以用del删除整个元组如果确实需要从元组删除元素通常是生成新的元组集合集合是一个无序的且无重复元素的序列集合中的数据对于Python程序员而言是无序的集合非常适合用于去除重复项可以使用大括号{}或者set()函数创建集合建一个空集合必须用set()而不是用一对空的{}和空字典产生二义性在向集合中添加元素时，如果该元素不存在则添加，否则不进行任何操作集合常用方法方法说明add()为集合添加元素clear()清除集合的所有元素copy()产生集合的一个副本difference()返回多个集合的差集discard()删除集合指定的元素，如果不存在就放弃intersection()返回集合的交集isdisjoint()判断两个集合是否包含相同的元素issubset()判断指定集合是否为该方法参数集合的子集issuperset()判断指定集合是否为该方法参数集合的超集remove()删除指定元素，如果不存在就抛出异常symmetric_difference()返回两个集合不重复的元素集合union()返回两个集合的并集update()给集合添加元素字典列表、元组和字符串都是用整数作为索引从而访问元素字典用关键字作为索引字典用于表示“键:值”对的数据，键就是关键字，具有唯一性在一个字典中一个关键字只能出现一次，不可以重复值可以重复字典中的数据对于Python程序员而言是无序的创建字典显式创建字典的语法如下：字典名={[关键字1:值1[,关键字2:值2,……,关键字n:值n]]}几个创建字典的例子dict1={} #空字典dict2=dict() #空字典dict3={'壹':1,'贰':2,'叄':3} #显式定义字典dict4=dict((['dog','狗'],['cat','猫'])) #基于元组定义字典访问字典的元素两种方法获取指定键的值方括号dict1={'壹':1,'贰':2,'叄':3}print(dict1[‘壹’]) #输出1print(dict1[‘肆’]) #该语句会出错get方法dict1={'壹':1,'贰':2,'叄':3}print(dict1.get([‘壹’],None))

#输出1print(dict1.get([‘肆’],None)) #输出None字典常用方法方法说明clear()删除字典内所有元素copy()返回一个字典的拷贝fromkeys()基于现有的序列创建一个新字典get()返回指定键的值，如果值不在字典中返回指定的默认值items()以列表返回可遍历的(键,值)keys()返回所有的键update()合并指定字典的项到当前字典values()返回所有的值pop()删除字典给指定键所在的项，并返回该项的值has_key()判断指定的键在字典中是否存在字典例子words={"星期一":"monday",

"星期二":"tuesday","星期三":"wendsday","星期四":"thursday","星期五":"friday","星期六":"saturday","星期天":"sunday"}word=input("请输入中文")print(words.get(word,"查无此词"))Python运算符运算符可以对一个或者多个操作数进行计算并返回结果单目运算符（一元运算符）not双目运算符（二元运算符）and常用运算符设num1=3,num2=5运算符类型运算符说明算术运算符+加法，num1+num2的结果是5-减法，num1-num2的结果是-2*乘法，num1*num2的结果是15/除法，num1*num2的结果是0.6%求余，num1%num2的结果是3**乘方，num1**num2的结果是243//整数除，num1//num2的结果是0关系运算符>

大于，num1>num2的结果是False<

小于，num1<num2的结果是True>=大于等于，num1>=nuum2的结果是False<=小于等于，num1<=num2的结果是True==等于，num1==num2的结果是False!=不等于，num1!=num2的结果是True逻辑运算符and逻辑与，num1>1andnum2<6的结果为Trueor逻辑或，num1>=4ornum2<=5的结果为Truenot逻辑非，notnum1的结果为False常用运算符(续)设num1=3,num2=5运算符类型运算符说明简单赋值运算符=赋值运算符，num1=num2的结果是使得num1等于5位运算符&按位与，num1&num2的结果是1|按位或，num|num2的结果是7~按位取反，~num1的结果是-4^按位异或，num1^num2的结果是6<<

左移，num1<<1的结果是6>>

右移，num1>>1的结果是1成员资格运算符in是否存在，num1in[1,3,5]的结果为Truenotin是否不存在，num2notin[2,4,6]的结果为True身份运算符is是否引用同一对象，num1isnum2的结果是Falseisnot是否引用非同一对象，num1isnotnum2的结果是True复合运算符用二元运算符和“=”组合而成+=-=*=/=……例子num1=3num1+=1 #使用复合运算符给num1加1num1=num1+1 #使用简单运算符给num1加1运算符被重载一个运算符在不同上下文有不同含义例如：+3+5 #数值相加[1,2,3]+[4,5,6] #列表拼接“hello”+“world!” #字符串连接(3+5j)+(4+7j) #复数相加==和is运算符辨析==判断两个对象的值是否相等is判断两个对象是否引用了同一个对象例子：lst1=[1,2]lst2=[1,2]print(lst1==lst2) #此行会输出Trueprint(lst1islst2) #此行会输出False运算符的优先级序号运算符说明1**乘方2~按位取反3+、-正、负4*、/、%、//乘、除、求余、整除5+、-加、减6<<、>>移位运算符7&按位与8^按位异或9|按位或10<、<=、>、>=、!=、==关系运算符11is、isnot身份运算符12in、notin成员测试13not逻辑非14and逻辑与15or逻辑或16=赋值（包括复合赋值）圆括号改变优先级在编写程序遇到优先级不太清晰时通过圆括号指明优先顺序可以提高代码的可读性例子：num1>2andnum1<5ornum2>4andnum2<8(num1>2andnum1<5)or(num2>4andnum2<8)#虽然执行结果一样，但前者的可读性就弱于后者函数函数是可重复使用的程序代码段是一个能完成特定功能的代码块。分类：内置函数用户自定义函数优点便于程序架构使得问题被分而治之便于协作代码编写提高代码复用降低代码冗余……函数的定义定义：指定函数名设计函数的形式参数实现函数的功能代码形式：def函数名([形式参数表]):

函数体注意点其中函数名和变量名一样，需要尽量做到顾名思义函数的形式参数可以多个，也可没有，没有参数时圆括号不能省略函数体属于函数定义的内部语句块，必须缩进函数例子defisPrime(num):'''

本函数用于判断一个正整数是不是质数

:paramnum: 待判断的正整数

:return: True-是质数

Fasle-不是质数

None-参数不合法

'''ifisinstance(num,int)==False:

returnNoneifnum<=0:returnNoneifnum==1:returnFalseimportmathmaxNumber=int(math.sqrt(num))foriinrange(2,maxNumber+1):ifnum%i==0:returnFalsereturnTrue函数的返回值函数可以用return语句向调用者传递值Python中函数的返回值非常灵活可以是数值常量、变量、表达式等，甚至是函数如果一个函数没有return语句，那么该函数最终会返回NonePython的函数一定有返回值在执行时一旦遇到return语句，该函数后续代码将不再执行一次返回多个值样例：defcalc(marks):maxVal=max(marks)minVal=min(marks)returnmaxVal,minVal,(sum(marks)-maxVal-minVal)/(len(marks)-2)maxMark,minMark,averMark=calc([88,65,78,99,45,72])print('最高分：',maxMark)print('最低分：',minMark)print('平均分：',averMark)函数调用形式参数定义函数时的参数实际参数调用函数时的参数调用函数时通常需要满足两个条件：（1）实际参数和形式参数的数量相同（2）实际参数的顺序和形式参数一一对应普通对象参数传递普通对象的值传递是单向的defexchange(num1,num2):num1,num2=num2,num1print(num1,num2) #输出交换后的值num1=5num2=7print(num1,num2) #输出调用前的值，是5,7exchange(num1,num2) #试图交换print(num1,num2) #输出调用后的值，还是5

7可变对象参数传递可变对象的值传递是双向的defchange(lst,dict1):lst[0]=2dict1['one']="一"lst=[1,2,3]dict1={'one':1}change(lst,dict1)print(lst)print(dict1)调用函数指定参数名用时允许采用指定形式参数名的方式实现“乱序”调用defexample(num1,num2):print("num1=",num1,"num2=",num2)example(20,10)example(num2=10,num1=20)函数的形式参数指定默认值科学的默认值可以为函数调用者带来便利例如内置排序函数：sorted(iterable,key=None,reverse=False)后面两个参数都提供了默认值常用内置函数函数名说明bin()返回数字转2进制的结果字符串chr()返回内码所对应的字符eval()计算表达式的值help()返回指定模块或者函数的说明文档hex()返回数字转16进制的结果字符串id()返回对象的内存地址isinstance()判断一个对象是否指定类的实例map()返回对指定序列映射后的迭代器ord()返回字符的内码，对于西文而言就是ASCII码range()返回一个可迭代对象type()返回对象的类型输入函数内置input函数input([prompt])其中的prompt是运行时给用户的提示字符串该函数的返回值是字符串样例代码str1=input("请输入一个字符串") #取字符串输入则无须转换print(str1) num=int(input("请输入一个整数")) #可以int强制转换print(num)nums=list(map(int,input("请输入多个整数用空格分开").split())) #获取多个整数到列表print(nums)输出函数print函数用于打印输出，该函数的原型如下：print(*objects,sep='',end='\n',file=sys.stdout,flush=False)objects表示可以一次输出多个对象输出多个对象时，需要用“,”分隔sep用于分隔输出的多个对象，默认值是一个空格end表示print输出完成后的结束符号，默认值是换行符'\n'file表示要重定向的文件对象，默认值sys.stdout为标准输出（显示器）flush表示输出是否被缓存文件文件是存储在外部介质上一组相关信息的集合文件为程序持久存储数据提供保障对文件操作可以抽象成三个步骤：打开文件、进行读写操作关闭文件读操作是指从文件输入数据到内存变量写操作是指从内存输出到文件打开文件打开文件必须用open函数，该函数原型如下：open(file,mode='r',buffering=-1,encoding=None)file参数是一个字符串，用于指定文件的路径可以是相对路径，也可以是绝对路径mode也是一个字符串，用于指定打开文件的模式encoding用于指定文件的编码格式打开文件的方式模式说明b二进制模式r以只读方式打开文本文件。rb以二进制格式打开一个文件用于只读r+打开一个文件用于读写rb+以二进制格式打开一个文件用于读写w打开一个文件只用于写入。如果该文件已存在则打开文件（原有内容会被删除），否则创建新文件wb以二进制格式打开一个文件只用于写入。如果该文件已存在则打开文件（原有内容会被删除），否则创建新文件w+打开一个文件用于读写。如果该文件已存在则打开文件（原有内容会被删除），否则创建新文件wb+以二进制格式打开一个文件用于读写。如果该文件已存在则打开文件（原有内容会被删除），否则创建新文件a打开一个文件用于追加。如果该文件已存在则打开文件并定位文件指针到文件结尾，否则创建新文件ab以二进制格式打开一个文件用于追加。如果该文件已存在则打开文件并定位文件指针到文件结尾，否则创建新文件a+打开一个文件用于读写。如果该文件已存在则打开文件并定位文件指针到文件结尾，否则创建新文件ab+以二进制格式打开一个文件用于追加。如果该文件已存在则打开文件并定位文件指针到文件结尾，否则创建新文件文件常用读写方法方法说明close()关闭文件flush()强制把内部缓冲区的数据立刻写入文件read()从文件读取指定的字节数，如果为空或为负则读取所有readline()读取一行readlines()读取所有行并返回列表seek()移动文件读取指针到指定位置tell()返回文件当前位置。write()将字符串写入文件writelines()向文件写入列表中所有数据实现文本文件复制的例子defcopyFile(src,des):srcFp=open(src,"r")desFp=open(des,"w")ch=srcFp.read(1)whilech!="":desFp.write(ch)ch=srcFp.read(1)srcFp.close()desFp.close()异常处理软件天然的复杂性，运行时可能遇到各种各样的异常：例如网络通信程序可能遇到网络断开、通讯不畅的情况大数据处理程序可能遇到内存不够的情况程序错误可以分为语法错误运行错误逻辑错误一个良好的程序需要处理程序运行时的异常，使得程序在运行遇到异常时做出合理的反应Python与异常异常是一个事件，它发生在程序的运行期在遇到无法正常处理的代码时会引发异常出现异常会影响程序的正常执行，将导致程序的运行过程偏离设计的流程。当Python程序发生异常时，必须捕获并处理它，否则程序将会被终止执行。程序员希望程序的执行过程在掌控之中，不希望因为用户操作不当，或者运行环境变化等缘由导致程序被终止执行。Python对异常的支持Python语言对异常处理提供了完备的支持主要涉及的关键字try监视异常raise抛出异常except捕获异常else不出现异常时执行其语句块finally无论是否出现异常都会执行其语句块异常处理器try:

语句块except异常类型1[as错误描述]： 异常处理语句块1……except异常类型n[as错误描述]： 异常处理语句块nexcept:

默认异常处理语句块else:

未处理异常才执行的语句块finally:

一定被执行的语句块错误与异常处理原则程序遇到错误情况时，如果还能以某种方式执行下去，不要随意终止执行，不轻易崩溃遇到错误时，不出现任意的非预期行为在某个局部发生错误时，尽可能局部处理异常处理机制已经成为现代程序设计处理错误的标准模式使用了异常处理之后会显著增强程序的健壮性模块一个大的程序往往包括多个源文件通常包含用户自定义的变量、函数和类一个源文件可以被称为一个模块若干个功能相关的模块组合在一起称为包包中必须有一个名称为__init__.py的文件包中除了有模块，还可以有包一个包中也可以只有一个模块包和模块两个词汇有时区分的并不明显若干个功能相关的包在一起称为库标准库和第三方库标准库安装Python时附带的库例如：randommath第三方库需要另外安装的库例如：numpywordcloud三种导入模块的方式import语句导入模块，三种方式import模块名1[as别名],[模块名2[as别名]…]importmathprint(math.sqrt(2))from模块名import函数名[as别名],[函数名[as别名]…]frommathimportsqrtprint(sqrt(2))from模块名import*frommathimport*print(sqrt(2))管理第三方包Python附带了包的管理工具：pip提供了对Python包的查找、下载、安装、卸载的功能功能命令显示版本pip--version查看帮助pip--help安装包pipinstall包名安装指定版本的包pipinstall包名==版本号升级包pipinstall–u包名显示包的信息pipshow包名列出已经安装的包piplist查看可以升级的包piplist-o搜索包pipsearch包名卸载包pipuninstall包名面向对象编程面向对象基本概念类：具有相同属性和方法的对象的集合。对象：对象是类的实例，类和对象是抽象和具体的关系，一个类可以产生多个实例。方法：类中的函数被称为方法，方法是类的动态特性，方法也被称为函数成员。属性：类中的变量被称为属性，属性是类的静态特性，属性也被称为数据成员。封装与隐藏：在设计类的时候将抽象出方法和属性的过程叫封装，然后通过设置权限将部分方法和属性不为外界所用的过程叫隐藏。继承与派生：允许在创建类时基于已有的类扩展，已有的类叫基类（父类），新建的类叫派生类（子类）类的定义不仅可以使用系统定义好的类，也支持用户自定义类定义类的语法如下：class类名： 属性的定义

方法的定义方法的self参数类成员函数的第一个参数都是self，self是一个约定俗成的变量名，用于表示当前对象类的成员函数是本类的所有对象共享的每个对象调用成员函数时，自动把自身传递过来通过self可以得到调用成员函数的当前对象类变量和实例变量类变量类变量是定义在类内部但又在类的成员函数之外它是类的所有对象共享的、公用的一个类有一个类变量，该类产生多少个对象，此类变量只有一份实例变量实例变量是每个实例独有的每个对象的实例变量互不影响一个类有一个实例变量，该类产生了n个对象，就有n份此实例变量成员的权限面向对象的隐藏就必须依赖私有和保护权限才能落地实现类中的成员可以有三种权限：公有私有保护如果类的成员称为内部，类的使用者称为外部在类内外部都可以访问公有的成员只有内部可以访问私有的成员内部和子类的成员函数都可以访问保护的成员外部无法访问保护成员__init__方法__init__是类的一个特殊方法，被称为类的构造方法两个下划线开头暗示了它是私有的不可以被类外部直接调用。每当用类产生对象，都会自动调用此方法它非常适合用于初始化数据成员继承与派生类的两个作用是产生对象作为基类进行继承派生继承派生的语法如下：class类名(基类名称1[，基类名称2…])： 属性的定义 方法的定义迭代器迭代器是一个可以遍历而且自己记录遍历位置的对象它的工作模式属于“懒惰模式”在调用迭代器时才会返回下一个元素在处理海量数据时就无须预先产生大量数据或者把大量数据加载到内存迭代器从数据的第一个元素开始访问，直到所有的元素被访问完结束迭代器只能单向往前，不可以后退迭代器内部需要维护自己的状态一个类如果实现了__iter__和__next__方法就属于迭代器类生成器生成器也是可迭代的不用实现__iter__和_