大学计算机 冯博琴 水电大基_第7章_程序设计新

西安交通大学2005年西安交通大学大学计算机2005年冯博琴主编新世纪电子信息与自动化系列课程改革教材中国水利水电出版社2018/1/101第7章程序设计基础O本章主要内容N71程序设计的基本概念N72程序设计思想N73算法和数据结构2018/1/10271程序设计的基本概念O为什么要进行程序设计O包饺子与程序设计N饺子的各种吃法O评估N预期需求N可得到的工具N自身能力O在计算机的各个技术应用中，应清楚自身所处的层次、所需的技能2018/1/103一、程序设计的一般过程O计算机可以做任何事情；只要能把实际问题抽象、制作为计算机可求解的程序。O计算机求解问题的步骤分析抽象模型求解命令编程调试程序实际问题问题模型求解算法编制程序问题实现2018/1/104程序设计的一般过程O问题定义O算法设计O程序编制O调试运行O文档2018/1/1051问题定义需求分析O问题一N给定两个正整数P和Q,求其最大公因数O问题二N统计一个班学生的考试成绩，并选出优秀学生P多少科目的成绩P优秀的定义（总分平均分第一名前五名）P数据如何录入如何输出P问题定义确定了未来程序的输入、处理、输出IPO,即INPUT,PROCESS,OUTPUT2018/1/1062算法设计O1算法ALGORITHM是对解决问题步骤的描述O2算法不能被计算机理解、执行O3算法的表示方法N1自然语言描述N2伪代码（PSEUDOCODE）P130例N3流程图FLOWCHAT2018/1/107算法自然语言描述示例一O步骤1输入全部学生姓名、学号、英语成绩、计算机基础成绩；O步骤2对各个学生成绩求合计；O步骤3按合计对学生进行排序；O步骤4取排序的学生列表中第一个学生O步骤5该学生有不及格吗没有则打印姓名并结束；O有不及格，则取下一个学生并重复步骤52018/1/108算法自然语言描述示例二O步骤1输入一个学生的姓名、学号、英语成绩、计算机基础成绩；O步骤2该学生有不及格吗有则转步骤1O步骤3该合计大于以前学生的合计吗大于则记录姓名、学号、合计成绩；O步骤4重复步骤1直到输入全部学生成绩O步骤5打印姓名、学号、合计成绩2018/1/109算法的流程图表示2018/1/10103程序编制O1程序语言的基本语法O1不同语言语法格式上的区别NSUMSUMMATH这是PASCAL的语句NSUMSUMMATH这是C的语句O2不同语言语义上的区别N例如C中的指针,PROLOG的谓词2018/1/10113程序编制O2程序的执行起始点N不同语言处理方式有所不同O3子程序（模块）N将一个大程序分成若干小程序块（子程序）N每一个子程序完成相对单一的功能N一个程序可以调用别的子程序N不同语言的处理也不同,如C中对应函数O4程序的执行顺序N图552018/1/1012程序编制O要点N如何用语句表达思想（算法）P（初级）了解语句、语法P（高级）熟悉语言提供的功能N不同语言提供的功能、性能有较大差距N如何组织程序代码P开始点P执行过程（子程序拆分、调用）P结束点2018/1/10134调试运行O1IDE集成开发环境O2程序错误类型N语法错误N逻辑错误2018/1/1014二、程序设计语言O1语言的分类N机器语言N汇编语言N高级语言O2常见的高级语言NPROLOG/LISPNC,C,C,JAVA,DELPHI,VBNSCRIPT语言脚本语言2018/1/1015二、程序设计语言O3语言的执行方式O1编译N将源程序经过编译程序翻译形成目标程序的过程O2解释N将源程序逐条翻译成机器指令并执行的过程2018/1/101672程序设计思想O一、结构化程序设计O二、面向对象程序设计2018/1/1017一、结构化程序设计O“软件危机”结构化程序设计O基本观点N程序设计方法应以能设计出结构清晰、可读性强、易于分工合作编写和调试的程序。O结构化设计方法是以模块化设计为中心2018/1/10181模块化程序结构O1模块化N把程序划分为若干个部分，每个部分独立存放、完成一个特定的功能。N一个模块可以是一条语句、一段程序、一个函数等O2目的N降低程序的复杂度，使程序便于阅读、调试和维护。O3基本特征N每个模块仅有一个入口和一个出口2018/1/10192三种基本程序结构O任何复杂的算法都可以通过由程序模块组成的三种基本程序结构实现O1顺序结构N按程序语句或模块在执行流中的顺序逐个执行O2选择结构N按设定的条件实现程序执行流的多路分支O3循环结构N按给定的条件重复执行指定的程序段或模块2018/1/10201顺序结构O顺序结构语句包括N说明语句N赋值语句NI/O语句N子函数调用语句、返回语句2018/1/10212选择结构之一O一路分支格式IF（表达式）语句序列语句序列可以是一个语句，也可以是复合语句结构。条件成立不成立语句序列O两路分支格式IF（表达式）语句序列ELSE语句序列条件语句序列1成立不成立语句序列22018/1/10223选择结构之二O多路选择语句格式NSWITCH（整数表达式）NCASE数值1N语句序列1；NNCASE数值NN语句序列N；NDEFAULTN语句序列N1；N语句序列1语句序列N计算整型表达式值语句序列22018/1/10232018/1/10244循环结构O当型循环格式NWHILE表达式N语句序列/循环体/NO直到型循环格式DO语句序列WHILE表达式条件语句序列成立不成立语句序列不成立成立条件2018/1/10252018/1/1026C或C语言的控制结构O顺序O选择（分支）NIFELSENSWITCHCASEDEFAULTO循环NWHILENFORNDOWHILEO出口NBREAKCONTINUE2018/1/10273结构化程序设计思想O基本思想“自顶向下,逐步求精”O1自顶向下N将复杂的问题划分为小问题，找出问题的关键、重点所在，然后用精确的思维定性、定量地描述问题。O2逐步求精N复杂问题经抽象化处理变为相对比较简单的问题。经若干步抽象（精化）处理，最后到求解域中只是比较简单的编程问题。2018/1/1028例题验证“哥德巴赫猜想”O问题表述N任何一个大于等于4的偶数均N可以表示为两个素数之和。N如422835O求解O第一步提出问题N验证哥德巴赫猜想验证哥德巴赫猜想X4XX/2处理哥德巴赫猜想不成立的情况打印出X的分解情况是否2018/1/1032验证哥德巴赫猜想O第四步生成下一个素数。N1）当前素数P加1N2）判别P是否是素数；N3）若是素数，返回P；N4）否则，P加1，继续执行2）PP1是素数PP1否返回素数P2018/1/1033验证哥德巴赫猜想O经过四步分解精化，将“验证哥德巴赫猜想”这个命题已经分解为计算机可以求解的数学模型了。O剩下的问题就是编程求解了。如何编程是程序设计课程要解决的问题。2018/1/1034显示素数源程序PROG1COIS_PRIMEINTNOINTIOFORI2I4/NFORI4INI,INFORJ2JI/2JNIFIS_PRIMEJ12018/1/1036猜想源程序PROG3C一组结果NIS_PRIMEINTNNINTIFORI2INIIFNI0RETURN0NRETURN1NMAINNINTI,J,NSCANF“D“,NFORI4INI,INFORJ2JI/2JNIFIS_PRIMEJ1NBREAK2018/1/1037二、面向对象的程序设计OOPO类与对象O基本过程O主要特点2018/1/10381类与对象P1对象OBJECTN1组成客观世界的各种各样的实体N2每个对象有各自的内部属性和操作方法N3每个对象以功能为中心,采用函数来描述N4复合对象包含其他对象作为其组成部分的对象2018/1/10391类与对象O2类CLASSO1概念N类是具有相同的属性和操作方法，并遵守相同规则的对象的集合。O2类与对象的关系N类是对象集合的抽象，规定了这些对象的公共属性即数据结构和方法（即操作数据的函数）；N对象是类的一个实例。N例如，学生是一个类，而某个班的某个具体学生则是一个对象。2018/1/10401类与对象O3消息MESSAGEN消息是向某对象请求服务的一种表达方式N对象之间的交互通过发送消息来实现。N消息包括目标对象,请求的方法,参数O在OOP中,整个程序由一系列相互作用的对象构成2018/1/10412OOP的基本过程O分析现实世界问题域O建立模型（类属性/方法的确定及类之间关系的确定）O编程建立类数据类型（属性、方法）O用类声明对象，通过对象间传递消息（方法调用）完成预定功能。2018/1/10423OOP的基本特征O1抽象类N数据抽象定义对象的属性和状态N代码抽象定义某类对象的共同行为特征或具有的共同功能O2封装N将数据和过程封藏起来,保证类具有独立性2018/1/10433OOP的基本特征O3继承N类与类之间的层次关系N类继承从现在类派生新类的过程N基类（父类）原有的类N派生类（子类）自动继承父类的属性和操作2018/1/10443OOP的基本特征O4多态性N允许不同类的对象对同一消息作出响应N目的基类和派生类中使用同样的函数名来定义不同的操作O对于简单的任务，面向对象会显得比较麻烦；而对于大的任务及构造开发平台，这种封装及其他优势为软件重用提供了绝好的手段。2018/1/104573算法和数据结构O一、数据和数据结构O1概念N数据、数据类型、数据元素、结点O2数据结构N研究数据及数据元素之间的关系,内容N1逻辑结构元素之间的逻辑关系N2存储结构数据及关系在计算机中的表示N3数据的运算定义在逻辑结构上的操作2018/1/10461数据的逻辑结构O1线性结构N数据元素之间存在线性关系一对一，最多只有一个前趋和后继元素；O3树形结构N数据元素之间呈层次关系，即最多有一个前趋和多个后继元素一对多；O4图状结构N数据元素之间的关系为多对多的关系2018/1/10472数据的存储结构O1顺序存储结构N按某种顺序存放在连续存储单元中O2链式存储结构N每个元素用数据域和指针域两部分表示,数据间通过指针链接数据域指针域数据域指针域数据域指针域2018/1/10482数据的存储结构O3索引存储结构N利用索引表确定数据的存储位置O4散列存储结构N元素和存储位置之间通过映象关系F对应2018/1/10493数据的运算N插入向数据结构中添加新的结点N删除把指定的结点从数据结构中去掉N查找查找满足一定条件的结点N排序递增、递减N遍历不重复也不遗露地访问每个结点2018/1/1050二、算法及其复杂度评价O1算法N指为解决特定问题而采取的有限操作步骤。O2特性N有穷性算法是有限的操作序列N确定性每个操作有确定的含义,无二义性N可执行性每个操作都是可以执行的N输入一个算法应该有0个或多个输入。N输出一个算法应该有1个或多个输出。2018/1/1051二、算法及其复杂度评价O3时间复杂度N程序在计算机上运行时所消耗的时间。O4空间复杂度N程序在计算机中所占的存储空间大小。O5复杂度的表示N按数量级增序排列，常见的有NO1，OLOGN，ON，