第1章 程序设计概述

程序设计基础 C 导言1 程序设计语言概述 计算机 指令 程序 程序设计语言 C语言 导言2 C语言概述C语言是国际流行的 很有发展前途的计算机高级语言 既可用于编写系统软件 又可用于编写应用软件 既有高级语言特性 又有低级语言特性 应用领域 系统 网络 单片机 手机 游戏 导言3 C语言的学科地位C语言是计算机专业基础课 它为以后的面向对象技术的学习以及C可视化软件的学习奠定了基础 同时C语言也是数据结构和操作系统等计算机专业主干课程的上机工具 要求学生充分重视 导言4 如何学好C语言 仅供参考 勤学 课内 课外 中文 英文 多练 实践是检验真知的唯一标准好问 不 知 下问善于思考 学而不思则罔 教学要求 通过课堂授课与上机实验相结合的方式 使学生能够深刻理解结构化程序设计的思想与方法掌握C语言的基础知识能够在计算机上熟练使用C语言的编辑环境来编写 调试 运行程序具有一定实践体会和相关的编程能力 能编写超过1000行的C语言应用程序 主要参考书目 谭浩强 C语言程序设计 清华大学出版社 1999 全国计算机等级考试二级C教材 C语言教学网站 集思广益 考核办法 出勤 作业 上机 20 30 考试成绩 70 80 1 0计算机简介 一 计算机的组成 1 中央处理器 CPU 运算器控制器寄存器组 对数据进行运算 控制计算机各部分协调工作 存放指令和数据等 1 0计算机简介 2 存储器 内存 存放程序代码及数据 3 外部设备输入设备 输入程序和数据 如键盘 鼠标 输出设备 输出计算结果 如显示器 打印机 外部存贮器 外存 储存各种数据 如硬盘 软盘 U盘 二 计算机基本结构 外部设备 中央处理器 CPU 存储器 输入 输出接口电路 数据总线 控制总线 地址总线 1 0计算机简介 操作系统 OperatingSystem OS是各种软件的核心与基础功能 cpu管理 存储管理 文件管理设备管理 作业管理等常用的OS MS DOS Windows Unix Linux 用户源程序 裸机 由计算机的各种硬件组成CPU 主板 内存 硬盘 声卡 显卡 网卡 光驱 电源 机箱 显示器 键盘 鼠标 音响等 裸机 编译系统和高级语言环境 用户源程序 1 0计算机简介 1 1 1程序设计语言 一 程序的概念 二 计算机软件 程序是计算任务的处理对象和处理规则的描述 计算机软件 程序 文档 1 计算机处理的任务都是计算任务 2 处理对象是数据 3 处理规则是指处理的动作和步骤 三 软件语言 软件语言是书写计算机软件的语言 1 1 1程序设计语言 四 程序设计语言 程序设计语言是用于书写计算机程序的语言 基本成分 1 数据成分 描述程序所涉及的数据 2 运算成分 描述程序所包含的运算 3 控制成分 表达程序的控制构造 4 传输成分 表达程序的数据传输 判断 程序设计语言 软件语言 1 1 1程序设计语言 五 程序设计语言的发展 机器语言二进制代码表示的计算机能直接识别和执行的一种机器指令集合 执行速度快 但较难掌握 不同型号的计算机语言不同 根据语言与硬件的关联程度 程序设计语言分为 低级语言和高级语言 发展过程是从低级到高级 1 1 1程序设计语言 2 汇编语言用助记符号描述的指令系统 如 ADDa b机器不能直接执行 必须翻译成机器码 较难掌握 汇编语言 机器语言 不能直接执行 较为简单 一一对应替换 1 1 2程序设计 3 高级语言接近于自然语言的计算机程序设计语言 不能直接运行 需要转换为机器语言 通常有解释和编译两种 使用较普遍的高级语言 FORTRAIN ALGOL BASIC PASCAL C C JAVA Delphi等 高级语言 机器语言 类似于自然语言 需要专门的编译器 解释器 过程较为复杂 1 1 2程序设计 三种语言的比较 高级语言 汇编语言 机器语言 1 1 2程序设计 六 程序设计的具体步骤 方案确定 建立问题的数学模型算法描述 描述处理规则数据描述 描述处理对象编写程序 编码 转换为程序语言程序测试 检测程序的正确性 注 编写程序只是程序设计的一个步骤 不等于程序设计 1 1 3数据结构 数据结构 DataStructure 计算机存储 组织数据的方式 数据结构一般包括三个方面的内容 数据之间的逻辑关系 也称数据的逻辑结构 LogicalStructure 数据元素及其关系在计算机存储器内的表示 称为数据的存储结构 StorageStructure 数据的运算 即对数据施加的操作 数据结构 逻辑结构 存储结构 运算 1 1 4算法概述 一 算法的概念及特性 1 算法的概念广义上讲 算法就是为解决一个问题而采取的方法和步骤 对同一个问题可能有不同的解决方法和步骤 即不同的算法为了快速有效的解决问题 在保证算法正确的基础上 还要考虑算法的质量 选择较优的算法 方法简单 运算步骤少 运算快 内存开销小的算法 数据结构 算法 程序 对数据的描述 对操作的描述 2 计算机算法的分类 1 数值运算算法 用于求数值解 如求解一个多元方程 2 非数值运算算法 多用于管理领域 如图书管理 著名计算机科学家沃思提出的一个公式 1 1 4算法概述 有穷性 空间有穷 一个算法包含有限的操作步骤 时间有穷 算法可以在合理的时间内运行完 确切性 算法中的每一个步骤是确定的 含义是唯一的可行性 算法中每一个步骤是可行的 有零个或多个输入有一个或多个输出 3 算法的五大特性 1 1 4算法概述 例1 1 对于给定的有序数列 3 5 11 17 21 23 28 30 32 50 如何查找30这个数据元素 1 1 4算法概述 算法一 将30按顺序与给定数列逐一比较直到找到为止 这种算法在最坏的情况可能需要比较整个序列 算法二 查找过程中采用跳跃式方式查找 即先以有序数列的中点位置为比较对象 如果要找的元素值小于该中点元素 则将待查序列缩小为左半部分 否则为右半部分 通过一次比较 将查找区间缩小一半 递推法递归法穷举搜索法贪婪法分治法动态规划法迭代法 4 算法设计与分析常用的方法 1 1 4算法概述 一 算法的表示方法 常用的算法表示方法 自然语言 流程图 N S图 伪代码 程序语言等 1 自然语言表示法用自然语言描述的算法 例1 2 用自然语言表示求两个数的和 如2 3 1 2算法表示方法 Step1 将输入的第一个数2存入xStep2 将输入的第二个数3存入yStep3 将x和y相加的结果存入zStep4 输出结果z 通俗易懂 比较冗余 容易出现歧义 2 流程图表示法用图框表示各种操作 用箭头表示算法流程 1 2算法表示方法 2 流程图表示法用图框表示各种操作 用箭头表示算法流程 用流程图表示求两个数的和 1 2算法表示方法 直观形象 易于理解 流程线没有严格限制 C语言是一种结构化程序设计语言 结构化程序设计主要采用自上而下 逐步细化的方法 结构化程序有三种基本结构 顺序结构 选择结构 循环结构 当型 循环 直到型 循环 1 2 2流程图表示法 传统的程序流程图例图 结束 输入a b c a b b c a c 输出c 输出b 输出c 输出a 开始 Y N Y Y N N 即结构化程序设计流程图 提供了描述三种基本逻辑结构的图形工具 与传统的程序流程图对照描述如下 1 顺序结构 1 2 3N S图表示法 b N S图表示 a 流程图表示 2 选择结构 分支结构 1 2 3N S图表示法 b N S图表示 a 流程图表示 由分支结构派生出来的多分支结构 1 2 3N S图表示法 b N S图表示 a 流程图表示 3 循环结构 a 当型循环结构 先判断循环条件是否满足 当条件满足 执行一遍循环体 再判断循环条件 仍满足再执行一遍循环体 直到不满足条件 则退出循环 执行循环体后的下一语句 若第一次判断条件就不满足 则一次也不执行循环体 1 2 3N S图表示法 b N S图表示 a 流程图表示 b N S图表示 b 直到型循环结构 先执行一遍循环体 再判断循环条件是否满足 如不满足再执行一遍循环体 直到条件满足 则退出循环 执行循环体后的下一语句 这种循环结构至少要执行一遍循环体 1 2 3N S图表示法 a 流程图表示 2 N S流程图表示法 顺序结构 选择结构 循环结构 当型 循环 直到型 循环 1 2 3N S图表示法 例描述求n 的值的算法 1 2 3N S图表示法 F 1 i 1 开始 输入n i n F F i 输出F 结束 i i 1 1 3程序设计方法 一 结构化程序设计 SP方法 程序的基本单元是函数 SP方法主张使用顺序 选择 循环三种基本结构来嵌套连结成具有复杂层次的 结构化程序 严格控制GOTO语句 无条件转移 的使用 自顶而下 逐步求精 的设计思想 独立功能 单出 入口 的模块仅用3种 顺序 分支 循环 基本控制结构的编码原则 C语言就是结构化设计语言 程序结构图 1 3程序设