《大学计算机基础》课件+第3章

1、大学计算机基础,北京航空航天大学 计算机学院,2,课程目录,求解显示，交互 （2学时）,问题的抽象与建模 （4学时）,3,第3章 问题的描述，数据及数据结构,3.4 程序控制结构,3.3 Python的基本构成及操作,3.5 函数、模块及文件,3.6 Python中类的定义,3.7 Python实现典型数据结构,3.2 数据与数据结构,3.1 问题的描述,4,本 章 重 点,了解问题描述的方法 掌握“数据抽象”的方法 掌握使用Python的基础操作，对象、类型、表达式、程序控制结构，如何构建较大规模的程序 掌握如何在Python中定义“类” 掌握典型数据结构的定义，抽象数据类型及实现方法,5,

2、3.1 问题的描述,3.1.1 引例 3.1.2 编程语言 3.1.3 Python,6,3.1.1引例,如何计算平方根？ 从猜想g开始 如果g*g足够接近x，则停止计算，g为x的平方根 否则，创建一个新的猜想，(g+x/g)/2 将新的猜想称为g，并重复整个过程，直到g*g足够接近x,7,如何描述问题,描述解决问题的要素 输入 输出 简单计算过程 控制流,8,3.1.2 编程语言,1936年，Alan Turing描述了理想的计算模型 编程语言要素 一组编程结构原语 Python原语：文字literal以及中缀运算符等 语法 哪些单词串可以构成句子 4.9 + 4.9 & 4.9 4.9 静

3、态语义 定义哪些句子具有含义 4.9 /xyz 语义 定义句子的含义是什么,9,学习编程易犯的错误,语法错误 严谨的编程语言均会进行语法错误检查，如果含有任何语法错误，用户都无法执行程序 静态语义错误 在允许执行程序前需要进行很多静态语义检查。而C和Python，则仅是做少量的静态语义检查 程序的执行并不是创建者的意图 它可能崩溃，也就是停止运行，给出示意 它可能继续运行，持续运行而不停止 它也可能完成运行，产生不正确的结果，甚至有可能是看似正确的结果,10,编程语言分类,低级语言与高级语言 前者采用指令以及机器级别的数据对象进行编程，后者采用语言设计者提供的抽象操作进行编程 通用编程语言与特

4、定领域编程语言 看编程语言的原语操作是广泛可被使用还是面向特定的领域 解释型编程语言与编译型编程语言 前者程序指令序列直接执行，而后者首先转化为机器级原语操作,11,Python语言特点,通用的编程语言，可有效构建绝大多数程序，而无需对计算机硬件进行直接的访问 较弱的静态语义检查功能，对于高可靠性限制要求的程序、由较多人员长期维护和构建的程序而言，它并不是最佳的选择 解释型语言，对于编程新生而言Python提供的实时反馈非常有帮助，同时Python提供大量库以及扩展功能，便于使用,12,3.2 数据与数据结构,3.2.1 数据 3.2.2 数据结构 3.2.3 数据抽象,13,程序的构成,用于

5、描述问题解决方案包含如下两个方面内容 表征问题实例的数据 产生预期结果所必须的一组施加于数据之上的计算过 编程语言需要提供 数据类型 控制结构 允许算法的步骤能够以更为方便的方式进行表达 顺序结构、选择结构以及迭代控制结构,14,3.2.1 数据,计算机所处理的信息在客观世界中并不孤立存在，如何在计算机中存储这些信息 二进制 为了使得这些序列有含义，我们使用数据类型进行刻画 采用何种方法表征数据间的结构关系，从而通过应用相应的办法进行数据的处理加工，以解决实际问题 数据类型提供算法开发时的基石,15,3.2.2 数据结构,问题要素并非独立存在，之间存在着某种联系，这种联系称为“结构”，也称为数

6、据的“逻辑结构”,16,3.2.3 抽象,利用计算机解决实际问题的重要过程之一便是“抽象” 抽象允许我们看待问题以及提出解决方案的角度分为逻辑视图和物理视图 使用计算机撰写文档，收发邮件，上网、玩游戏，听音乐，存储照片 操作系统是如何工作的，网络协议是如何配置的，如何编写代码实现功用 用户无需知道细节，只需要明确接口如何工作；而“接口”便是用户与底层复杂实现进行交互的方法,17,数据抽象,抽象数据类型（abstract data type） 如何看待数据以及允许施加于数据之上操作的逻辑描述 该描述并不关心如何实现这些数据操作 仅关心数据的表示，而不是如何实现数据的操作 通过抽象，进行数据的封装

7、，即将实现的细节进行封装，对于用户隐藏这些细节 数据结构则提供了抽象数据类型的实现，即如何使用程序结构以及元数据类型提供数据的物理视图,18,3.3 Python的基本构成及操作,3.3.1 对象、表达式以及数字类型 3.3.2 对变量进行赋值 3.3.3 Type Str 3.3.4 结构化类型 3.3.5 输入Input 3.3.6 IDLE,19,3.3.1对象、表达式以及数字类型,对象是Python程序操作的核心内容，每个对象具有类型的定义，用于说明程序可用该类型对象完成的工作 类型可以是标量以及非标量 标量对象可以视为是语言的原子 非标量对象，如字符串，有内在的结构,20,标量对象,

8、Python含有四类标量对象： int用于代表整数型，如 16， -5，1024； float用于代表实数，如 16.0，-5.25，1024E3（代表1024*103）； bool类型用于代表布尔值True以及False； None为单一值类型,21,表达式,对象以及操作符可以组合形成表达式 如表达式 4+5指示int型对象9 而表达式4.00+5.00则指示float型对象9.00 操作符=用于比较两个表达式是否相等，操作符 ！=用于比较两个表达式是否不等,22,找出对象的类型,23,操作规则,对于i+j, i-j, i*j 如果i和j的类型均为int，则结果类型同样为int 如果i和j之

9、一为float，则结果为float型 i/j，表示整数除法 9/3为int 3，9/2为int 4.返回商数，忽略小数部分 i/j 如果操作数均为int，则结果同样为int，否则结果为float i%j，为int i被int j除的余数 i*j，i的j次方 如果操作数均为int，则结果同样为int，否则结果为float 比较符, =, , =含义为大于，大于等于，小于，小于等于,24,数学比较符的优先级,x+y*3 首先计算y*3，之后加上3 通过括号可以改变优先顺序 (x+y)*3，将首先计算x+y,结果值再乘以3,25,基于bool类型值的操作符,x and y，仅当x和y均为True时为

10、True x or y，x,y当中至少一个为True时为True not x，仅当x为False时为True,26,3.3.2 对变量进行赋值,变量提供将名(name)与对象(object)关联的方式 pi = 3.14159 radius = 10.5 circumference =2* pi * radius radius = 12.6,27,恰当使用变量名以增强程序可读性,pi = 3.14159 diameter = 10.5 circumference =2* pi * radius x = 3.14159 y = 10.5 z = 2* pi * y,28,注释,# compute

11、 the circumference of circle using radius pi = 3.14159 radius = 10.5 circumference =2* pi * radius,29,赋值语句,30,3.3.3 Type Str,类型Str的对象用于表示字符串 可以使用或者” 如123代表是字符串，而并非数字123,31,易错点,32,字符串的典型操作,字符串的长度可使用len函数 如len(xyz)值为3 索引可以从字符串中提取字符 键入xyz0将会显示字符串x 采用负数对字符串进行索引将由字符串的末端进行 如xyz-1的值为z 字符串可通过切片提取任意长度的子串， ss

12、tart:end代表的子串是起始于start位置，终结于end-1位置的字串 如xyz1:3 = yz start值缺省为0，end值缺省为字符串的长度 也就是说，xyz: = xyz0:len(xyz)。,33,3.3.4 结构化类型,Tuples 元组是元素的序列，它并不要求其中的元素必须为字符，实际上元素的类型可以为任意类型，同时元素可以是不同类型 Lists 列表和元组一样，是值的有序序列，每个值可以由索引识别 Dict(dictionaries) 类似于列表，只是字典中的索引不需要是整型，而是任意不可变类型，入口并没有顺序，并不能通过索引来进行访问，可以将字典视为“键/值”对,34,

13、Tuple示例,和字符串类型一样，元组类型可以进行连接、索引以及提取操作,35,List,List与之前介绍的类型区别在于list为可变 tuple, int, float以及str类型均为不可变类型 列表类型的对象在其被创建后可被修改。,36,List方法,L.append(o)：将对象o添加至L的尾部； L.count(o)：返回列表中对象o出现的次数； L.insert(i,o)：将对象o插入至L的索引i位置； L.extend(L1)：将列表L1中的元素添加至L的末端； L.remove(o)：从列表L中将第一次出现的o删除； L.index(o)：将列表L中第一次出现的o的索引返回；

14、 L.pop(i)：i缺省值为-1，将列表L中的索引i的元素移除并返回； L.sort()：将L中的元素进行排序； L.reverse()：将L中的元素逆序。,37,序列类型的操作,序列类型：str, tuple，以及list。这三类型的序列都可以使用如下操作： seqi：返回序列中第i个元素； len(seq)：返回序列的长度； seq1 + seq2：将两个序列连接； n *seq：将序列重复n次，并返回该序列； seqstart:end：返回序列的部分； e in seq：测试e是否在序列中； for e in seq：迭代序列中的元素。,38,序列类型的区别,39,Dict,由大括号将

15、元素括起，每个元素是“键:值”的形式 字典操作： len(d)：返回d中元素的数量； d.keys()：返回包含d中keys的列表； d.values()：返回d中values的列表； k in d：若k在d中，则返回True； dk：返回d中键为k的值； d.get(k,v：如果k在d中，返回dk，否则返回v； dk = v：将值v与键k关联，即使已有与k关联的值； del dk：从d中将键k移除； for k in d：依据d中keys进行迭代。,40,3.3.5 输入Input,41,3.3.6 IDLE,IDLE提供 文本编辑器，语法高亮，自动完形以及智能缩进 语法高亮的shell 集

16、成调试器 在启动IDLE后，将打开一个shell窗口，可向其中键入Python命令，同时提供文件菜单以及编辑菜单。其中文件菜单包括： 创建新的编辑窗口，以键入Python程序 打开现有Python程序 将当前窗口编辑的内容写入文件，文件后缀为.py,42,3.4 程序控制结构,3.4.1 条件语句 3.4.2 迭代 3.4.3 简单的数字程序,43,程序控制结构,串行程序按序执行语句，当语句执行完毕则停止 算法需要两种重要的控制结构 选择 if 迭代 while for,44,3.4.1 条件语句,分支选择程序更为有趣，最简单的分支语句为条件语句，条件语句包含三个部分： 测试部分，即一个表达式

17、评值为True或者False 一段代码段，如果测试值为True 一个可选的代码段，如果测试值为False,45,Python中条件语句结构,If boolean expression: block of code else: block of code,46,识别奇偶值,47,嵌套,如何判断当前输入整数是否能被2，3整除？,48,复合表达式,如何求输入三个整数值中的最小值？,49,3.4.2 迭代,与条件语句一样，while迭代语句首先进行测试 如果测试结果为True，程序将执行循环体一次，之后再次评估测试 这个过程一直重复，直至测试条件评值为False，此时控制将传递至迭代语句之后的代码,5

18、0,分析代码,51,for语句,for之后的变量绑定至序列中的第一个值，并执行代码块，之后变量被赋值为序列中的第二个值，再次执行代码块 处理过程持续到代码块中执行break语句或者将序列中的所有值执行完毕,52,for语句格式,for variable in sequence: code block,53,range函数,54,3.4.3 简单的数字程序,如何使用Python中的基本结构来编写简单的程序， 一些简单的语言结构和算法技巧,55,穷举法求平方根,56,程序分析,何时终止? 表达式ans*2的值从0开始，每次迭代增加1 当表达式ans*2的值大于x的绝对值时，循环终止 猜想-检测方法

19、的变体，通常称为穷举法 我们枚举所有可能的结果，以找到正确的结果，或者穷尽可能的空间,57,近似解决方案求解平方根,对于2这样的整数，我们只能给出 is not a perfect square的回答 2的平方根不是有理数，这意味着无法用有限的数字字符串精确表示它的值 使用近似的方法找到平方根，这里近似是指结果与实际值之间足够接近，通常二者距离为常量epsilon,58,程序分析,如果x=0.25，上述程序能否找到它的平方根值足够接近0.5？ 尝试用此算法求120000的平方根 改变step = epsilon *3 步长变小之后意味着可以进行查找范围内的数量增多,59,3.5 函数、模块及文

20、件,3.5.1 函数 3.5.2 作用域 3.5.3 递归 3.5.4 模块 3.5.5 文件,60,3.5.1 函数,函数定义需要名字、一组参数以及函数体，函数可能显式返回值。 def functionName(formalParameters): functionBody,61,调用函数,组成实参的表达式被评值，同时，形参绑定至评值结果； 执行点转移到函数体中的第一条语句； 函数体中的代码执行，直到遇到return语句或者执行完函数体中所有的语句 对于前者，将返回return之后的表达式的值 后者则将返回None； 执行点转移会调用点之后的代码,62,3.5.2 作用域,分析如下程序输出,

21、63,程序分析,在顶层，即shell，由一个符号表追踪所有在这个层次定义的名以及它们当前的绑定 当函数被调用，新的符号表（栈帧stack frame）被创建 这个符号表追踪在当前函数中定义的名以及它们当前的绑定 如果在函数体内调用函数，则再创建另一个符号表； 当函数完成时，栈帧也消失,64,3.5.3 递归,在数学与计算机科学中，是指在函数的定义中使用函数自身的方法 递归一词还较常用于描述以自相似方法重复事物的过程 小时候都听过的故事从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？从前有座

22、山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？” 关于某人“祖先”的递归定义： 某人的双亲是他的祖先（基本情况）。 某人祖先的双亲同样是某人的祖先（递归步骤）。,65,递归的定义,一部分是基本情况，指明特定情况的结果 另一部分为递归情况，定义在其他输入情况下的结果,66,阶乘,阶乘的定义： 1!= 1 (n+1)! = (n+1) * n! （n1） 第一个式子定义基本情况 第二个式子定义所有自然数，除基本情况，依据上一个数来计算当前数的阶乘,67,使用while,68,使用递归计算,当传参为1时，将不进行递归调用 当需要进行递归时，使用比参数小1的值作为新的参数进行调用

23、 递归终结于对于factR(1)的调用,69,斐波那契数列,假定一对新生兔子，公兔和母兔，假定兔子成熟需要一个月的时间，同时兔子的妊娠周期为一个月，同时假定这些兔子永远不会死，而母兔兔在它第二月开始每个月会诞下一对新的公母兔。那么在第六个月末时，会有多少怀孕的兔子呢？,70,问题抽象,F0 = 0（初始值） F1 = 0 （初始值） 对所有大于1的整数n： Fn = Fn-1 + Fn-2 （递归定义）,71,解决方案,72,3.5.4 模块,假定完整的程序存储于一个文件当中，这种方法仅适用于小型程序 当程序规模变大，典型的操作方法是将程序的不同部分存储与不同的文件当中 Python modu

24、le提供了这样一种工作方式，使得可以在多个文件中构建程序代码，从而完成较复杂程序的协同,73,import,module是一个.py文件，该文件包含Python定义以及语句 如，我们创建一个circle.py文件包含如下内容,74,3.5.5 文件,计算的结果通常使用文件来存储 Python提供多种便利进行文件创建及访问 每种操作系统有自己相应的文件系统以进行文件的创建和访问 Python通过文件句柄(file handle)访问文件实现操作系统无关性 nameHandle = open(kids.txt, w) 通知操作系统创建一个名为kids.txt的文件，并返回该文件的文件句柄 参数w指

25、明文件可写,75,文件操作,fileHandle.read()，将文件内容以字符串返回； fileHandle.readline()，返回文件中下一行； fileHandle.readlines()，返回list类型，其中每项是文件的一行 fileHandle.writes(s)，将字符串写入文件末端 fileHandle.writeLines(SL)，SL为字符串的序列，将该序列的每个元素写入文件末端,76,3.6 Python中类的定义,3.6.1 类定义 3.6.2 构造方法 3.6.3 重载操作符,77,3.6.1 类定义,面向对象编程语言中最强大的特性之一便是允许编程人员创建新的类（

26、class）用以对数据建模从而解决问题 如何实现抽象数据类型“分数”（Fraction） 分数，包含两个部分，分子及分母，其中分子为任意整数，分母为大于0的整数 对于Fraction类型数据，允许的操作包括：打印输出、加/减/乘/除以及比较大小等,78,定义类,需要定义它的名字以及一组方法，类似于函数的定义,79,3.6.2 构造方法,所有类需要提供的构造方法（constructor），用以创建该类型的数据对象 创建Fraction对象需要提供两部分的数据，即分子、分母 在Python中，构造方法由_init_标识,80,构造方法（续）,注意到形参列表包含三项(self,top,bottom)

27、 其中self为特殊参数，该参数是指向对象自身的引用，必须为形参的第一项，但是在调用时不会有实参对应 构造方法中self.num定义fraction对象含有num作为其状态的部分 self.den创建分母 为了创建Fraction类的实例，我们必须调用构造方法，通过使用类的名字以及为必要的状态传递值,81,3.6.3 重载操作符,在Python中，为所有的类提供一组标准的方法，但是可能并不能恰当的工作 比如_str_，该方法将对象转化为字符串 它的缺省实现便是返回实例的地址字符串 可以通过“重载”(override)，重新定义方法的行为以打印输出分数,82,重载 _str_,83,重载 +,“

28、+”操作符并不支持将Fraction对象实例作为操作数,84,3.7 Python实现典型数据结构,3.7.1 栈（stack） 3.7.2 队列 （queue） 3.7.3 树（tree） 3.7.4 图（graph）,85,基本的结构,集合，线性结构、树形结构以及图结构,86,线性结构的特点,在数据元素的非空有限集合中 存在唯一一个被称作“第一个”的元素 存在唯一一个被称作“最后一个”的元素 除第一个以外，集合中的每一个元素都只有一个前驱 除最后一个以外，集合中的每一个元素都只有一个后继 栈和队列便是典型的线性数据结构 数据项依据添加和移除的情况进行组织，当一个数据项添加后，它的位置取决于

29、在它之前加入和之后加入的元素,87,3.7.1 栈(stack),“栈”是元素的有序集合，在向其中添加或者移除元素均发生在统一端，这一端称为栈顶（top），而另一端则称为栈底（base） 添加、移除规律为“后进先出”（last-in first-out, LIFO）,88,抽象数据类型,栈是有序的元素项目的集合，元素的添加及移除均从栈顶位置开始操作，栈的操作包括： Stack()，创建栈，该操作不需要参数，同时返回空栈。 push(item)，向栈顶添加元素，参数为向栈添加的元素，无返回值。 pop()，将元素从栈顶移除，无需参数，返回栈顶元素，此时栈被修改。 peek()，返回栈顶元素，但并

30、不移除，无需参数，此时栈不被修改。 isEmpty()，测试栈是否为空，无需参数，返回布尔值。 size()，返回栈内元素的数量，无需参数，返回整型值。,89,Python中实现栈,90,使用栈方法进行相应的操作,91,栈的应用：十进制整数转化为二进制,计算机中的信息以二进制串的方式存储 整数是典型的需要存储的信息，用于程序的计算，在数学课上我们通常使用的则是十进制系统（基数为十） 如果采用R个基本符号（例如：0，1，2，R1）表示数值，则称R数制，R称该数制的基数（Radix），而数制中固定的基本符号，称为“数码”。处于不同位置的数码代表的值不同，与它所在位置的“权”值有关。任意一个R进制数D均可展开为,92,R进制对十进制的转换,在我们熟悉的十进制系统中，9658还可以表示成如下的多项式形式： （9658）D = 9103 + 6102 + 5101 +8100 上式中的103，102，101，100是各位数码的权，可以看出，个位、十位、百位和千位上的数字只有乘上它们的权值，才能真正