计算机科学导论第第4章讲稿程序设计基础.ppt

第4章程序设计基础 学习目标了解程序设计的基础知识 程序设计风格的重要性 基本的查找和排序方法 掌握结构化程序设计方法和面向对象程序设计方法的思想 几种基本的数据结构 学习计算机首先要学习程序设计 良好的程序设计技能和风格有助于加深对计算机的理解和进一步学习 第4章程序设计基础 4 1程序设计基础 程序设计步骤如下 1 确定要解决的问题 2 分析问题 在着手解决问题之前 应该通过分析 充分理解问题 明确原始数据 解题要求 需要输出的数据及形式等 3 选择计算方法 4 确定数据结构和算法 算法是解题的过程 首先集中精力于算法的总体规划 然后逐层降低问题的抽象性 逐步充实细节 直到最终把抽象的问题具体化成可用程序语句表达的算法 这是一个自上而下 逐步细化的过程 4 1程序设计基础 5 绘制流程图 6 编写程序 利用程序设计语言表示算法 编写代码 7 调试并测试程序 调试程序包括编译和连接等操作 程序员还要对程序执行的结果进行分析 只有能够得到正确结果的程序才是所需的程序 8 整理资料 交付使用 高质量程序设计目标是结构化程度高 可读性好 效率高 可靠性高 便于维护 1 自上而下与自下而上先将一个大问题分解成若干个子问题 把比较复杂的子问题继续分解成更加简单的二级子问题 直至每个子问题都有显而易见的解决办法 然后在实现时采用自下而上的方法 逐一编写解决各个子问题的程序 设计程序时采用自上而下的方法比采用自下而上的方法效率要高得多 4 2 1结构化程序设计方法 采用自上而下解决问题的思路如图 4 2 1结构化程序设计方法 用这种方法逐步分解 直到作者认为可以直接将各小段表达为文字语句为止 这种方法就叫做 自顶向下 逐步细化 2 结构化方法结构化方法有助于在正式编写程序之前充分理解问题的实质和实现方法 并且可以在具体编码过程中提供指导 4 2 1结构化程序设计方法 结构化方法通常遵循以下原则 1 用户参与的原则 2 先分析 再设计 后实现的原则 3 自上而下的原则 4 阶段成果文档化 4 2 1结构化程序设计方法 3 结构化程序设计方法使用顺序 选择 循环3种基本控制结构 4 2 1结构化程序设计方法 顺序结构顺序结构是一种最简单 最基本的结构 在顺序结构内 各块是按照它们出现的先后顺序依次执行 下图表示了一个顺序结构形式 从图中可以看出它有一个入口a点 一个出口b点 在结构内A框和B框都是顺序执行的处理框 已知梯形两底a b和高h 设计一个求梯形面积的算法 并画出流程图 选择结构选择结构中包含一个判断框 根据给定的条件S是否成立而选择执行A框或B框 当条件成立时 执行A 否则执行B 判断框中的两个分支 执行完A或B后都必须汇合在一起 从出口b退出 然后接着执行其后的过程 设计一个算法 输出a b c中的最大值 循环结构 循环结构是指在一定条件下反复执行一个程序块的结构 循环结构也是只有一个入口 一个出口 while循环当给定的条件S成立时 执行A框操作 执行完A操作后 再判断S条件是否成立 如果成立 再次执行A操作 如此重复执行A操作 直到判断p条件不成立才停止循环 此时不执行A操作 而从出口b脱离循环结构 do while循环先执行A框操作 然后判断给定条件S是否成立 如果成立 再次执行A操作 然后再对S进行判断 如此反复 直到给定的S条件不成立为止 此时不再执行A框 从出口b脱离循环 设计一个算法 计算1 2 3 100的值 3 结构化程序设计方法使用顺序 选择 循环3种基本控制结构 4 2 1结构化程序设计方法 4 模块化方法一个复杂的问题可以划分为多个简单问题的组合 在自顶向下 逐步细化的过程中 把复杂问题分解成一个个简单问题的最基本方法就是模块化 模块化便于问题的分析 模块体现了信息隐藏的概念 模块常用子程序加以实现 4 2 1结构化程序设计方法 模块设计的方法 模块化设计的思想实际上是一种 分而治之 的思想 把一个大任务分为若干个子任务 每一个子任务就相对简单了 在拿到一个程序模块以后 根据程序模块的功能将它划分为若干个子模块 如果这些子模块的规模还嫌大 还再可以划分为更小的模块 这个过程采用自顶向下方法来实现 4 2 2面向对象的程序设计方法 1 面向对象的思想OO ObjectOriented 面向对象 的程序设计把客观事物看作具有属性和行为的对象 通过抽象找出同一类对象的共同属性 静态特征 和行为 动态特征 形成类 对象对象 Object 是具有某些特性的具体事物的抽象 对象在现实生活中到处可见 凡是我们要处理的事物都可成为处理的对象 包括可见的事物 如人 汽车 电话等 和非可见的事物 如感情 思想等 例如 一个人是一个对象 一台PC机是一个对象 再将一台PC机拆开看 便有显示器 机箱 硬盘 主板 处理器 鼠标等 这每一个部件又是一个对象 即PC机对象是由多个 子 对象组成的 此时PC机可看作为一个容器对象 4 2 2面向对象的程序设计方法 类类是具有共同属性 共同操作性质的对象的集合在例如 桥梁是抽象的概念 重庆长江大桥 西湖断桥就是具体的 我们把抽象的 桥 看成类 而具体的一座桥 如重庆长江大桥看成是对象 类是对象的抽象描述 对象则是类的实例 类是抽象的 对象是具体的 类可以划分为基类 根类 和子类 派生类 子类以其基类为起点 并可继承基类的特征 如水果是基类 苹果是子类 而红富士 黄元帅等苹果品种又是苹果类的子类 在这里 水果也称为是苹果的父类 苹果也可称为是红富士 黄元帅等的父类 具体的一个红富士苹果就是一个对象 4 2 2面向对象的程序设计方法 消息消息是面向对象系统中实现对象间的通讯和请求任务的操作 消息传递是程序运行的基本处理活动 4 2 2面向对象的程序设计方法 类的特性 1 继承性子类不但具有父类的全部属性和方法 而且允许用户根据需要对已有的属性和方法进行修改 或添加新的属性和方法 这种特性称为类的继承性 2 封装性类的封装性是指类的内部信息对用户是隐蔽的 如同一台电视机的使用者只需了解其外部按钮 用户接口 的功能与用法 而无需知道电视机的内部构造与工作原理一样 3 多态性类的多态性是指一些相关联的类包括同名的方法程序 但方法程序的内容不同 4 2 2面向对象的程序设计方法 4 3基本数据结构 数据结构 DataStructure 是系统设计和程序开发的重要基础 4 3 1基本概念 1 数据 数据类型数据是对客观事物的符号表示 在计算机系统内 数据通常是指能够输入到计算机中并被计算机进行处理的符号的集合 例如 数字 字母 汉字 图形 图像 声音等信息在计算机内部的表示都是数据 可以是数值数据 也可以是非数值数据 数据类型是指具有相同取值范围和可以实施同种操作的数据的集合 例如 在程序设计语言中 通常定义了字符型 整数型 数组等多种数据类型 2 数据元素 数据项 数据对象能够独立并完整地描述客观世界实体的基本数据单元称为数据元素 它是组成数据的基本单位 在不同的应用环境中 数据元素有时可以称为结点 记录等 数据项是组成数据元素的不可分割的最小单位 最简单的数据元素是由一个数据项构成的 同类数据元素的集合称为数据对象 4 3 1基本概念 表中的每一行是一个结点 或记录 即数据元素 它是由学号 姓名 各科成绩及平均成绩等数据项组成 4 3 1基本概念 2 数据元素 数据项 数据对象 3 数据结构数据结构是指数据元素之间的相互关系的集合 包括了数据的逻辑结构 物理结构以及数据的运算 4 3 1基本概念 31 数据结构主要研究 数据集合中数据元素之间所固有的关系 即数据逻辑结构 数据处理时数据在计算机中的存储关系 即数据存储结构 对数据所进行的操作 即算法 4 3 1基本概念 4 3 1基本概念 33 数据逻辑结构数据结构中数据元素之间所固有的关系描述成前后件 前驱与后继 关系 数据之间前后件关系是它们之间的逻辑关系 与它们在计算机中存储位置无关 因此将这种关系称为数据逻辑结构 34 一个数据结构可以表示为 S D R S 数据结构D 数据元素集合R D中数据元素之间前后件关系集合 即数据逻辑结构两个元素之间前后件关系用一个二元组表示 如 a1 a2 35 事实上可能有 如树形结构中的一个元素有多个后件或如网状结构中的一个元素有多个前件因此一般来说 数据之间有4种基本逻辑结构 集合线性树形图形 36 37 非线性结构 有多个开始结点和多个终端结点 每个结点可有多个前件和多个后件 线性结构 有且只有一个开始结点和一个终端结点 并且每个结点最多只有一个前件和一个后件 线性结构也称为线性表 根据前后件关系的复杂程度 数据逻辑结构分为2类 38 数据物理结构定义 数据在计算机存储器中的存储方式称为数据存储结构 或数据物理结构 数据结构中数据元素之间在计算机中的位置关系与逻辑关系不一定相同 在数据存储结构中 不仅要存放各个数据元素信息 还要存放数据元素之间前后件关系信息 数据存储结构是逻辑结构在计算机存储器中的表示 39 数据元素在计算机中通常有四种存储方式 顺序链式索引散列常用顺序存储结构和链式存储结构 数据物理结构 40 顺序存储结构在存储器中开辟一块连续的单元用于存放数据 逻辑上相邻的结点在物理位置上也邻接 结点之间的逻辑关系是由存储单元相邻关系来体现 41 链式存储结构结点由两部分组成 数据域 用于存放数据元素值指针域 用于存放前件或后件的存储地址链式存储结构是通过指针反映数据间的逻辑关系 回顾 程序设计步骤程序设计方法结构化程序设计方法面向对象的程序设计方法数据结构的基本概念 4 3 2几种典型的数据结构 1 线性表 2 栈 3 队列 4 线性表 5 图 定义线性表是一组特征相同数据的有限序列 表示为 L a1 a2 a3 an 有限个同类的数据元素构成的序列 4 3 2几种典型的数据结构 1 线性表 有且仅有一个 第一个 数据元素有且仅有一个 最后一个 数据元素除第一个数据元素外 其它元素有且仅有一个直接前驱除最后一个数据元素外 其它元素有且仅有一个直接后继 4 3 2几种典型的数据结构 1 线性表 例如英文字母表 A B C Z 是线性表 表中的每个字母就是一个数据元素 一副扑克的点数 2 3 4 J Q K A 也是线性表 其中每一张牌的点数是一个数据元素 4 3 2几种典型的数据结构 1 线性表 线性表通常采用顺序和链表两种物理实现 对于经常变化的表 通常采取链表结构 线性表常用的运算主要有 插入 删除 查询和遍历 4 3 2几种典型的数据结构 1 线性表 48 2 栈栈是只能在表的一端进行插入和删除运算的线性表允许插入和删除运算的一端称为栈顶 另一端称为栈底 插入元素操作称为入栈删除元素操作称为出栈 4 3 2几种典型的数据结构 49 a1 a2 an 栈底bottom 栈顶top 入栈 出栈 4 3 2几种典型的数据结构 栈是一种 后进先出 或 先进后出 的数据结构 例如用桶堆积物品 先堆进来的压在底下 随后一件一件往堆 取走时 只能从上面一件一件取 4 3 2几种典型的数据结构 52 3 队列只允许 在一端进行插入运算 而在另一端进行删除运算的线性表 允许删除的一端称为队首 队头 允许插入的一端称为队尾 4 3 2几种典型的数据结构 53 3 队列 4 3 2几种典型的数据结构 4 3 2几种典型的数据结构 4 3 2几种典型的数据结构 4 树在树型结构中 每个数据元素称为一个结点 除了唯一的根结点外 其他每个结点都有且仅有一个父结点 每个元素可以有多个子结点 树结构在客观世界中广泛存在 如人类社会的族谱和各种社会组织机构都可用树形象表示 4 3 2几种典型的数据结构 4 3 2几种典型的数据结构 5 图图形结构是一种比树型结构更复杂的非线性结构 在图形结构中 每个数据元素称为一个顶点 任意两个顶点之间都可能相关 这种相关性用一条边来表示 顶点之间的邻接关系可以是任意的 4 3 2几种典型的数据结构 4 3 2几种典型的数据结构 1 线性表 2 栈 3 队列 4 线性表 5 图 4 3 3查找 查找是指根据给定的某个值 在查找表中确定一个其关键字等于给定值的记录或数据元素 若表中存在这样的一个记录 则称查找是成功的 此时查找的结果为给出整个记录的信息 或指示该记录在查找表中的位置 若表中不存在关键字等于给定值的记录 则称查找失败 此时查找的结果可给出一个 空 记录或 空 指针 1 顺序查找2 二分查找3 分块查找 4 3 3查找 1 顺序查找顺序查找是在一个队列中找出与给定关键字相同数值的具体位置 原理是让关键字与队列中的数从第一个开始逐个比较 直到找出与给定关键字相同的数值为止 4 3 3查找 2 二分查找将表中间位置记录的关键字与查找关键字进行比较 如果两者相等 则查找成功 否则利用中间位置记录将表分成前 后两个子表 如果中间位置记录的关键字小于查找关键字 则进一步查找前一子表 假定队列是从小到大排列 否则进一步查找后一子表 重复以上过程 直至找到满足条件的记录 使查找成功 或直至子表不存在为止 此时查找失败 4 3 3查找 一个有序表中有13个记录 记录的关键字序列为 7 14 18 21 23 29 31 35 38 42 46 49 52 给定值k为14 在表中查找关键字与k相等的记录 3 分块查找分块查找又称索引顺序查找 它是顺序查找的一种改进方法 分块的原则是将n个数据元素 按块有序 划分为m块 m n 每一块中的结点不必有序 但块与块之间必须 按块有序 即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字 而第2块中任一元素又都必须小于第3块中的任一元素等 4 3 3查找 3 分块查找分块查找是首先选取各块中的最大关键字构成一个索引表 然后查找分两个部分 先对索引表进行二分查找或已确定待查记录在哪一块中 最后在已确定的块中用顺序法进行查找 4 3 3查找 1 顺序查找2 二分查找3 分块查找 4 3 3查找 4 3 4排序 排序是计算机程序设计中的一种重要操作 简单地说 排序就是要整理文件中的记录 使之按关键字递增 或递减 次序排列起来 4 3 4排序 如果按排序过程中依据的不同原则对内部排序方法进行分类 则可分为直接插入排序 冒泡排序 快速排序等 1 直接插入排序基本操作是将一个记录插入到已排好序的有序表中 从而得到一个新的 记录数增1的有序表 4 3 4排序 1 直接插入排序 基本思想是 每步将一个待排序的对象 按其关键码大小 插入到前面已经排好序的一组对象的适当位置上 直到对象全部插入为止 简言之 边插入边排序 保证子序列中随时都是排好序的 4 3 4排序 初始关键字序列 13 6 3 31 9 27 5 11第一次排序 6 13 3 31 9 27 5 11第二次排序 3 6 13 31 9 27 5 11第三次排序 3 6 13 31 9 27 5 11第四次排序 3 6 9 13 31 27 5 11第五次排序 3 6 9 13 27 31 5 11第六次排序 3 5 6 9 13 27 31 11第七次排序 3 5 6 9 11 13 27 31 例 关键字序列T 13 6 3 31 9 27 5 11 请写出直接插入排序的中间过程序列 注 方括号 中为已排序记录的关键字 下划横线的关键字表示它对应的记录后移一个位置 2 冒泡排序冒泡排序是通过交换两个元素实现的 它的思想是 设有数组A n 1 n为序列中元素个数 第一趟在序列 A 0 A n 1 中从前往后进行两个元素的比较 如后者小 则交换 比较n 1次 第一趟排序结束 最大元素被交换到A n 1 中 即沉底 下一趟排序只要在子序列 A 0 A n 2 中进行 如果在某一趟排序中未交换元素 说明子序列已经有序 则不再进行下一趟排序 4 3 4排序 2 冒泡排序 基本思路 每趟不断将记录两两比较 并按 前小后大 规则交换 优点 每趟结束时 不仅能挤出一个最大值到最后面位置 还能同时部分理顺其他元素 一旦下趟没有交换发生 还可以提前结束排序 4 3 4排序 例 关键字序列T 21 25 49 25 16 08 请按从小到大的顺序 写出冒泡排序的具体实现过程 初态 第1趟第2趟第3趟第4趟第5趟 21 25 49 25 16 0821 25 25 16 08 4921 25 16 08 25 4921 16 08 25 25 4916 08 21 25 25 4908 16 21 25 25 49 3 快速排序基本思想是 对任意给定的系列中存在元素R 经过一趟排序后 将原序列分割成两个子序列 Rp 0 Rp 1 Rp s 1 和 Rp s 1 Rp s 2 Rp n 1 其中前一个子序列中的所有元素的关键字均小于或等于该元素的关键字值Kp s 后一个子序列中元素的关键字均大于或等于Kp s 称该元素R Rp s 为分割元素 子序列 Rp 0 Rp 1 Rp s 1 为其低端系列 Rp