计算机文化基础-第7章程序设计基础与基本数据结构讲述.pptx

计算机基础 南京信息工程大学滨江学院 计算机系 计算机基础课程组 第7章 程序设计基础与基本数据结构 南京信息工程大学滨江学院 计算机系 程序设计方法学 教 学 目 标 1 结构化程序设计方法和面向对象程序设计方法 2 程序的本质 3 简单数据结构-线性表、树 4 查找与排序 5 3 通过学习能初步具备程序设计相关的理论知识和目前主流的程序方法；理解程序的本质“算法+数据结构”，初步掌握简单基本的线性和非线性数据结构，以及在查找和排序上的简单应用。 教学重点和难点 算法的描述—流程图 1 2 二叉树的表示及遍历 3 简单查找与二分法查找 4 基本排序算法与堆排序 5 4 栈和队列的操作及简单应用 5 章节安排 7.1 程序设计基础 7.1.1 程序设计方法学与风格 7.1.2 结构化程序设计 7.1.3 面向对象的程序设计 7.2 基本数据结构 7.2.1 算法与数据结构 7.2.2 基本线性数据结构 7.2.3 基本非线性数据结构 7.2.4 基本数据结构的应用 7.3 小结 7.4 习题 7.1 程序设计基础 7 2017-4-7 7.1.1. 程序设计方法学与风格 程序是用来控制计算机操作的一系列代码。而程序设计目的是利用计算机对现实问题进行求解。 计算机科学家、图灵奖获得者尼克劳斯·威茨教授对程序进行了经典定义： 程序=算法+数据结构 随着软件产业的迅猛发展和软件开发的工程化日趋完善，程序与软件开发环境的关系越来越紧密，开发工具的选择对程序的开发效率有着非常大的影响，有时会起到事半功倍的效果。对程序的定义进行了扩充： 程序=算法+数据结构+开发环境 8 2017-4-7 1. 程序设计方法学与风格 程序设计方法学是探讨程序设计的理论和方法的学科。用以指导程序设计各阶段工作的原理和原则，以及依此提出的设计技术。 程序设计方法学的目标是能设计出可靠、高效、易读而且代价合理的程序。更通俗地说，什么样的程序是一个“优秀”的程序，怎样才能设计出“优秀”的程序。 程序设计的一般过程应包括：分析实际问题并抽象，利用数学建模技术构建问题的数学模型，借助计算方法和数据模型构造合适数据结构，进而设计算法，最后借助计算机语言实现算法形成程序。 2. 源程序编写的一般规范 良好的程序设计风格可以使程序结构清晰合理，使程序代码易于测试和维护。 程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体而言应该强调简单和清晰。 9 2017-4-7 2. 源程序编写的一般规范 1）标识符命名及书写规则 （1）规范的基本要求 （2）特殊约定 （3）源代码文件标识符命名规则 2）注释及格式要求 3）缩进规则 4）代码的排版布局 10 2017-4-7 7.1.2 结构化程序设计 迪克斯特拉（E. W. Dijkstra）在1969年提出了结构化程序设计方法，是以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模块，这样使每一个模块的完成变得简单且明确，为设计一些较大的软件打下了良好的基础。 程序的顺序、选择和循环三种控制流程，这就是结构化程序设计方法强调使用的三种基本结构。 结构化程序设计的基本思想是采用“自顶向下，逐步求精”的程序设计方法和“单入口单出口”的控制结构。 11 2017-4-7 结构化程序设计具有以下优点：①整体思路清楚，目标明确。②设计工作中阶段性非常强，有利于系统开发的总体管理和控制。③在系统分析时可诊断出原系统中存在的问题和结构上的缺陷。 程序设计步骤： （1）分析问题。（2）建立数学模型。 （3）选择算法。（4）编写程序。 （5）调试运行。（6）分析结果。 （7）写出程序的文档。 【例7-1】输出2到N之间的素数（质数）。 12 2017-4-7 7.1.3 面向对象的程序设计 面向对象就是基于对象概念，以对象为中心，以类和继承为构造机制，来认识、理解、刻画客观世界和设计、构建相应的软件系统。 对象（Object）是一个现实实体的抽象。一个对象可被认为是一个将数据（属性）和程序（方法）封装在一起的实体，程序用来刻画该对象的动作或对它接收到的外界信号的反应，这些对象操作有时称为方法。 13 2017-4-7 类是构成面向对象程序设计的基础，它把数据和函数封装在一起，是具有相同操作功能和相同数据格式（属性）的对象抽象，它可以被看作抽象数据类型的具体实现。 类与对象的关系：类是用户自定义的数据类型，是用来描述只有相同属性和方法的对象集合，它定义了该集合中每个对象所共有的属性和方法，对象是类的实例。例如，苹果是一个类，而放在桌上的那个苹果则是一个对象。 14 2017-4-7 面向对象的基本特征 （1）对象唯一性 （2