第3章节计算机软件课件1章节(3405KB).pptVIP

* * * * * * * * * * * * * * C语言和C++语言 C语言是1972～1973年间由AT＆T公司Bell实验室开发而成，兼有高级语言的优点和汇编语言的效率 C++语言以C语言为基础发展而成，既有数据抽象和面向对象能力，运行性能高，又能与C语言兼容，因而C++语言迅速流行，成为当前面向对象程序设计的主流语言 * 3.4 算法和数据结构概述 * 本节要点 ◆ 算法 ◆数据结构 3.4.1 算法 1.算法的概念 瑞士计算机科学家尼?沃思（N.Wirth）在20世纪70年代曾经提出过一个著名公式： 数据结构+算法 = 程序 * 算法是解决问题的方法与步骤 例：求出a、b、c中的最大数,并放入max 分析： 方法明确而有序 按提供的条件进行操作 任何人均可仿照进行(共享智能) * 开始 输入a,b,c Ab? Max=b Max=a Maxc? 输出max 结束 Max=c no yes no yes 算法的表示方法 文字说明 流程图表示 用N-S盒图表示算法 用PAD图描述算法 伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具） * 2. 算法的特征 必须满足的性质： ① 确定性：算法中每一步操作的含义必须清楚明确，无二义性 ② 可行性： 即必须在计算机的能力范围之内，且在有限时间内能够完成 ③ 有穷性： 算法在执行了有限步操作后必须结束 ④ 输入/输出:必须有零个或多个输入,算法结束后至少产生一个输出（包括参量或状态的变化） * 3. 算法分析的基本内容 正确性：经过有限时间的计算，产生正确的输出结果 简单性 算法是否容易理解和验证，程序是否容易调试 保证一定效率的前提下力求算法简单 时间复杂度(Time Complexity) ： 指算法的时间耗费。当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 空间复杂度(Space Complexity) ： 指算法的空间耗费，记在执行时所占存储空间大小的数量级 * * 3.4.2 数据结构p63 数据结构是相互间存在一种或多种特定关系的数据元素的集合 通俗地说，数据结构是带有结构的数据元素的集合，例如学生登记表 数据元素 指计算机操作对象的个体，数据的基本单位； 具有广泛的含义，一般来说现实世界中客观存在的一切个体都可以是数据元素。例如学生登记表的中的一条记录 如：描述一年四季的季节名：春、夏、秋、冬 表示作为数值的各个数：18、19、20、21 表示家庭成员的各成员：父亲、儿子、女儿 你能发现这些数据元素之间的联系吗？ 前驱、后继 在实际问题中数据元素不是孤立的 数据 计算机中对事实、概念或指令等信息的描述。是计算机加工处理的对象，例如… 树形 数据结构的内容p60 1 数据的逻辑结构，即数据结构中包括哪些元素，相互之间有什么关系等。有四种： * 2 数据的物理(存储)结构，即数据的抽象结构如何在实际的存储器中予以实现，数据元素如何表示，相互关系如何表示等 3运算： 定义在数据结构上的一组操作及其实现方法 线性结构 网状结构 树形结构 集合结构 数据的存储结构举例 顺序存储结构： 借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 链接表存储结构： 利用地址指针来表示元素之间的逻辑关系 * a1 a2 低地址 高地址 a2是a1的后继元素 a1 a2 a2是a1的后继元素 4.数据的运算 每一种逻辑结构都有与之对应的各种运算，各不相同 ★ 计算机软件 ★ 操作系统 ★ 程序设计语言 ★ 算法 ★ 数据结构 * 本 章 小 结 * * * * * * * * 其中： 文字处理软件能帮助你方便地阅读数字作品和写作各种类型的文档 电子邮件和网络聊天等提供你方便而便宜的通信工具 多媒体播放软件、游戏软件为你提供了娱乐的新途径 检索软件、门户网站让你在因特网上找到所需要的信息和资料 BBS和Blog提供你在因特网上向公众发表观点的机会 演示文稿制作软件PowerPoint能帮助你把演说或报告做得更加生动精彩 个人信息管理软件能帮助你管理好自己的重要数据、安排好自己的日程 * * 1 共享软件是一种“买前免费试用”的具有版权的软件，它通常带有一个允许试用一段时间的许可证，允许用户进行拷贝和散发（但不可修改后散发），过了试用期若还想继续使用，就得交一笔注册费，成为注册用户。这是一种为了节约广告费用的有效的软件营销策略。 2 自由软件的创始人是理查德·斯塔尔曼（Richard Stallman），他于1984年启动了开发类UNIX系统的自由软件工程（名为GNU），创建了自由软件基金会