北大C语言讲义.pdf

1 第一部分 计算机基础计算机基础 第一部分内容第一部分内容 1 计算机的历史与发展 计算机的历史与发展 2 计算机的基本原理 计算机结构 计算机的基本原理 计算机结构 3 计算机的抽象模型和基本问题 计算机的抽象模型和基本问题 引言引言 我们生活的环境越来越信息化 我们生活的环境越来越信息化 工作工作 生活对人处理信息的能力提出更高要求 运用 各种通信交流手段 通过媒体收集发送有用信息 运用计算机等信息处理工具挑选有价值的材料并将 其改造成适用的形式等 生活对人处理信息的能力提出更高要求 运用 各种通信交流手段 通过媒体收集发送有用信息 运用计算机等信息处理工具挑选有价值的材料并将 其改造成适用的形式等 从事任何工作 都会感到信息社会的挑战 看到计 算机的巨大作用 计算机正在越来越深入地渗透到 日常生活的每一个角落 从事任何工作 都会感到信息社会的挑战 看到计 算机的巨大作用 计算机正在越来越深入地渗透到 日常生活的每一个角落 学习掌握计算机和信息技术 理解其原理和工作方 式 对每个大学生都是最基本的 学习掌握计算机和信息技术 理解其原理和工作方 式 对每个大学生都是最基本的 计算机 发展简史 计算机 发展简史 现代计算机的历史始于 20世纪40年代后期 一 般认为第一台真正意义 下的计算机是1946年在 美国宾夕法尼亚大学诞 生的名为 ENIAC Electronic Numerical Integrator and Computer 读为 爱尼亚 克 的计算机 计算机 诞生并不是一个孤立事 件 它是人类文明史的 必然产物 是长期客观 需求和技术准备的产 物 史前时代史前时代 计算机是一种机器 是人发明的一种工具 计算机是一种机器 是人发明的一种工具 与人类发明创造的其他工具有根本性差别 与人类发明创造的其他工具有根本性差别 工具大多可以看作是手脚的延伸 完成的是人们原 本需要耗费体力去完成的事情 工具大多可以看作是手脚的延伸 完成的是人们原 本需要耗费体力去完成的事情 而计算机则可以看作是人头脑的延伸 能帮人做原 本需要耗费人的脑力完成的事情 计算机的诞生 从历史上可以找到多方面的原因和前 期准备工作 主要包括几个方面 而计算机则可以看作是人头脑的延伸 能帮人做原 本需要耗费人的脑力完成的事情 计算机的诞生 从历史上可以找到多方面的原因和前 期准备工作 主要包括几个方面 一 人类对计算工具的需求和早期开发 一 人类对计算工具的需求和早期开发 人类文明发展早期就遇到了计算问题 在古人类生活过的岩 洞里刻痕说明他们在计数和计算 人类文明发展早期就遇到了计算问题 在古人类生活过的岩 洞里刻痕说明他们在计数和计算 人手是大自然赋予人类最方便的计算工具 这也是人使用十 进制数的最根本原因 石子 小木棒是手在这个方面的延 伸 人手是大自然赋予人类最方便的计算工具 这也是人使用十 进制数的最根本原因 石子 小木棒是手在这个方面的延 伸 随着文明发展 人发明了 各种专用计算工具 中国 古代的算筹 最早在两河 流域出现 在中国得到了 真正发展和广泛使用的算 盘 都是古代人类寻求计 算工具的辉煌成就 随着文明发展 人发明了 各种专用计算工具 中国 古代的算筹 最早在两河 流域出现 在中国得到了 真正发展和广泛使用的算 盘 都是古代人类寻求计 算工具的辉煌成就 2 工业革命开始后 人发明了各种机械设备 设计制造这些设 备的一个基本问题就是计算 需要解决的计算问题越来越 多 越来越复杂 因此 当时的科学家也进行了计算工具的 研究 工业革命开始后 人发明了各种机械设备 设计制造这些设 备的一个基本问题就是计算 需要解决的计算问题越来越 多 越来越复杂 因此 当时的科学家也进行了计算工具的 研究 1642年法国物理学家帕斯卡发明了机械性的齿轮式加减法 器 年法国物理学家帕斯卡发明了机械性的齿轮式加减法 器 1673年德国数学家莱布尼兹发明了乘除器 从而导致能 够进行四则运算的机械式计算器的诞生 商品机械计算器在 年德国数学家莱布尼兹发明了乘除器 从而导致能 够进行四则运算的机械式计算器的诞生 商品机械计算器在 1820真正出现 真正出现 这方面最卓越的工作是英国发明家查里斯这方面最卓越的工作是英国发明家查里斯 巴贝齐在巴贝齐在19世纪世纪30 40年代设计的差分机和分析机 巴贝齐企图用机械方式实现 一般意义下的计算过程 他设计的分析机已经有了今天计算 机的基本框架 但是由于技术限制 用机械方式实现如此复 杂的过程几乎是不可能的 巴贝齐的计算机器都没有完成 年代设计的差分机和分析机 巴贝齐企图用机械方式实现 一般意义下的计算过程 他设计的分析机已经有了今天计算 机的基本框架 但是由于技术限制 用机械方式实现如此复 杂的过程几乎是不可能的 巴贝齐的计算机器都没有完成 二 人类对自动机械的需求和早期开发 二 人类对自动机械的需求和早期开发 利用地磁场的指南针 中国古代的指南车 广泛应用的风车 水车都可看作这方面的早期成果 利用地磁场的指南针 中国古代的指南车 广泛应用的风车 水车都可看作这方面的早期成果 自动设备发展史上一个里程碑是钟表的发明 文艺复兴后进 入鼎盛时期 有些钟表能定时地完成许多活动 能工巧匠还 利用机械原理制造了许多自动化的小玩意 随着大工业发 展 人们发明了许多自动机械 从蒸汽机到各种织机 特别 是提花织机 自动设备发展史上一个里程碑是钟表的发明 文艺复兴后进 入鼎盛时期 有些钟表能定时地完成许多活动 能工巧匠还 利用机械原理制造了许多自动化的小玩意 随着大工业发 展 人们发明了许多自动机械 从蒸汽机到各种织机 特别 是提花织机 人们也考虑计算过程的自动化 用自动过程代替人工 借助 于计算器械 实施的复杂计算 巴贝齐的计算机器就是在追 求自动化与计算的结合 人们也考虑计算过程的自动化 用自动过程代替人工 借助 于计算器械 实施的复杂计算 巴贝齐的计算机器就是在追 求自动化与计算的结合 1884年美国人荷年美国人荷 豪利瑞斯用穿孔卡片表示数据 发明制表机 获得专利并成功用于美国 豪利瑞斯用穿孔卡片表示数据 发明制表机 获得专利并成功用于美国1890人口普查 人口普查 三 算法和程序性操作的研究及其理论发展 三 算法和程序性操作的研究及其理论发展 机械式按规定步骤行事 通过一系列简单计算完成复杂计算的 过程 称为 机械式按规定步骤行事 通过一系列简单计算完成复杂计算的 过程 称为 算法过程算法过程 程序性过程 程序性过程 最早算法记录在两河流域发现 公元前两三千年的黏土板 一 个典型例子是计算利息何时能等于本金 最早算法记录在两河流域发现 公元前两三千年的黏土板 一 个典型例子是计算利息何时能等于本金 早期发展的最重要成是古希腊的欧几里德提出的计算最大公约 数的辗转相除法 又称欧几里德算法 早期发展的最重要成是古希腊的欧几里德提出的计算最大公约 数的辗转相除法 又称欧几里德算法 中国古代数学研究中有许多有关算法的成果 中国古代数学研究中有许多有关算法的成果 文艺复兴以后随着近代数学的开拓和发展 算法研究也有了许 多成果 人们研究了许多数学问题的计算过程 提出了许多算 法 但若没有自动化计算工具 根本无法完成复杂的计算问 题 文艺复兴以后随着近代数学的开拓和发展 算法研究也有了许 多成果 人们研究了许多数学问题的计算过程 提出了许多算 法 但若没有自动化计算工具 根本无法完成复杂的计算问 题 不必造加法机 乘法 机 最大公约数机 只 要造出 不必造加法机 乘法 机 最大公约数机 只 要造出 通用图灵机通用图灵机 功 能等价的机器 就能解 决所有计算问题 功 能等价的机器 就能解 决所有计算问题 图灵的工作非常重要 计算机领域世界最重要 的奖项就被用命名为 图灵奖 图灵的工作非常重要 计算机领域世界最重要 的奖项就被用命名为 图灵奖 算法的理论基础研究在算法的理论基础研究在20世纪世纪30 40年代取得了突破性进 展 出现了几个有普遍意义的计算模型 年代取得了突破性进 展 出现了几个有普遍意义的计算模型 英国数学家艾兰英国数学家艾兰 图灵图灵40年代提出一种自动计算机器模型 年代提出一种自动计算机器模型 图灵机图灵机 并提出图灵原理 一切可能的机械式计算过程 都能由图灵机实现 还指出 存在 并提出图灵原理 一切可能的机械式计算过程 都能由图灵机实现 还指出 存在 通用通用 图灵机 它可实 现所有图灵机的功能 图灵机 它可实 现所有图灵机的功能 3 四 电技术与电子技术的发展 四 电技术与电子技术的发展 自动计算机器需要技术基础 巴贝齐达到机械方式的最高水 平 由于计算工作的复杂性 该工作未成功 自动计算机器需要技术基础 巴贝齐达到机械方式的最高水 平 由于计算工作的复杂性 该工作未成功 随着十九到二十世纪电学和电子学的发展 人们看到了另一条 实现自动计算过程的途径 随着十九到二十世纪电学和电子学的发展 人们看到了另一条 实现自动计算过程的途径 德国发明家康拉 德 德国发明家康拉 德 祖思在二战期间 用机电方式制造了计 算机 祖思在二战期间 用机电方式制造了计 算机Z 1到到Z 3 美国科学家霍华 德 美国科学家霍华 德 邓肯也提出用机 电方式实现自动计算 机器 邓肯也提出用机 电方式实现自动计算 机器 1944年造出年造出 MARK I计算机 计算机 祖思和 Z 2 推动计算机器开发的最重要因素是需求 现代社会发展和科学技术进步都对新计算工具提出了强烈的需 求 此外 军事和战争的需要也是一个重要因素 研究开发 推动计算机器开发的最重要因素是需求 现代社会发展和科学技术进步都对新计算工具提出了强烈的需 求 此外 军事和战争的需要也是一个重要因素 研究开发 ENIAC计算机的目的是为军事服务 主要是为了计算弹道和 火力表 随着 计算机的目的是为军事服务 主要是为了计算弹道和 火力表 随着ENIAC的诞生 人类历史上计算工具的一个新 时代开始了 的诞生 人类历史上计算工具的一个新 时代开始了 蹒跚学步蹒跚学步 ENIAC是第一台电子计算机 但还不是现代意义的计算机 是第一台电子计算机 但还不是现代意义的计算机 ENIAC能做许多基本计算 如四则运算 平方立方 能做许多基本计算 如四则运算 平方立方 sin和和 cos等 但其计算需要人大量参与 每次计算前技术人员需要 插拔许多导线 极麻烦 等 但其计算需要人大量参与 每次计算前技术人员需要 插拔许多导线 极麻烦 46年美国数学家冯年美国数学家冯 诺依曼提出计算机的基本原理 程序存储诺依曼提出计算机的基本原理 程序存储 原理原理 据此造出的新计算机 据此造出的新计算机 EDSAC Electronic Delay Storage Automatic Calculator 爱达赛克 和 爱达赛克 和 EDVAC Electronic Discrete Variable Automatic Computer 爱达瓦 克 于 爱达瓦 克 于1949和和1952年在英国剑桥大学和美国宾州大学运行 年在英国剑桥大学和美国宾州大学运行 EDSAC是世界第一台存储程序计算机 又称冯是世界第一台存储程序计算机 又称冯 诺依曼计算 机 是所有现代计算机的原型 诺依曼计算 机 是所有现代计算机的原型 范本 范本 EDVAC是最先开始 研究的存储程序计算机 它用了 是最先开始 研究的存储程序计算机 它用了10000只晶体管 只晶体管 1952年才完 成 年才完 成 1952年年IBM公司开发出世界最早的成功的商品计算机公司开发出世界最早的成功的商品计算机 IBM701 这是信息产业的开始 当时人们完全没有意识到计 算机的潜在用途和发展 这是信息产业的开始 当时人们完全没有意识到计 算机的潜在用途和发展 IBM公司总裁当时认为公司总裁当时认为 全世界只需 要五台计算机 全世界只需 要五台计算机 就足够了 就足够了 随着军用和民用的发展 工业化国家的一批公司企业投入到计 算机研究开发生产领域中 随着军用和民用的发展 工业化国家的一批公司企业投入到计 算机研究开发生产领域中 虽然计算机具有通用性 但计算机硬件只提供解决计算问题的物 质基础 要用计算机解决任何问题 都必须编写有关的程序或软 件 早期计算机极难使用 要用二进制编码形式写程序 既耗费 时又容易出错 大大限制了计算机的广泛应用 五十年代前期计 算机领域的先驱者们就开始认识到这个问题的重要性 虽然计算机具有通用性 但计算机硬件只提供解决计算问题的物 质基础 要用计算机解决任何问题 都必须编写有关的程序或软 件 早期计算机极难使用 要用二进制编码形式写程序 既耗费 时又容易出错 大大限制了计算机的广泛应用 五十年代前期计 算机领域的先驱者们就开始认识到这个问题的重要性 1954年约翰年约翰 巴克斯领导的小组 开发出第一个后来广泛使用的 程序语言 巴克斯领导的小组 开发出第一个后来广泛使用的 程序语言Fortran 大大提高了 程序开发效率 大大提高了 程序开发效率 Fortran推动推动 IBM的新机器的新机器704走向世界 成 为当时最成功的计算机 也使 走向世界 成 为当时最成功的计算机 也使 IBM成为计算机产业的老大 由此可见软件的重要性 成为计算机产业的老大 由此可见软件的重要性 随着计算机应用的发展 许多新型计算机被开发出来 计算 机的功能越来越强 速度越来越快 随着计算机应用的发展 许多新型计算机被开发出来 计算 机的功能越来越强 速度越来越快 与此同时 计算机科学理论的研究和计算机技术的研究开发 也取得了丰硕的成果 人们开始进一步研究计算过程的本 质 程序设计的规律 计算机系统的硬件结构和软件结构 与此同时 计算机科学理论的研究和计算机技术的研究开发 也取得了丰硕的成果 人们开始进一步研究计算过程的本 质 程序设计的规律 计算机系统的硬件结构和软件结构 一些新的程序设计语言 如一些新的程序设计语言 如Algol60 COBOL LISP等被开 发出来 等被开 发出来 军用和民用科学计算仍然是计算机应用的主要领域 计算机 也开始在商务数据处理领域崭露头角 军用和民用科学计算仍然是计算机应用的主要领域 计算机 也开始在商务数据处理领域崭露头角 一些新的研究和应用领域 如人工智能 计算机图形图像处 理等露出了萌芽 一些新的研究和应用领域 如人工智能 计算机图形图像处 理等露出了萌芽 4 60年代中操作系统 高级程序设计语言编译系统等基 本软件初步成型 形成当时计算机系统的基本框架 年代中操作系统 高级程序设计语言编译系统等基 本软件初步成型 形成当时计算机系统的基本框架 1965年年IBM推出了推出了360系列计算机 开始了计算机作 为商品发展史的新阶段 系列计算机 开始了计算机作 为商品发展史的新阶段 360计算机采用半导体集成电路技术 第一次提出系 列计算机的概念 不同型号机器在指令层次互相兼 容 并配备较完备的软件 计算机采用半导体集成电路技术 第一次提出系 列计算机的概念 不同型号机器在指令层次互相兼 容 并配备较完备的软件 360及随后的及随后的370系列计算 机取得了极大的成功 系列计算 机取得了极大的成功 七十年代美日的一些公司开始生产与七十年代美日的一些公司开始生产与IBM兼容的大型 计算机 推动了计算机价格竞争和技术进步 兼容的大型 计算机 推动了计算机价格竞争和技术进步 稳步发展稳步发展 DEC 数据设备公司 等开发了小型 低价格 高性能的计 算机 称为小型计算机 数据设备公司 等开发了小型 低价格 高性能的计 算机 称为小型计算机 主要用于教育科研部门和一般企 业 做科学计算和数据处理工作 主要用于教育科研部门和一般企 业 做科学计算和数据处理工作 为解决巨型科学与工程计算问题人们开发了巨型计算机为解决巨型科学与工程计算问题人们开发了巨型计算机 它 们通常装置多个数据处理部件 它 们通常装置多个数据处理部件 CPU 这些部件可同时工 作 大大提高了处理能力 这些部件可同时工 作 大大提高了处理能力 另一类常见计算机被称为工作站另一类常见计算机被称为工作站 在企业或科研部门中由个 人使用 主要用于图形图像处理 计算机辅助设计 软件开 发等专门领域 在企业或科研部门中由个 人使用 主要用于图形图像处理 计算机辅助设计 软件开 发等专门领域 随着半导体技术发展 随着半导体技术发展 60年代末在集成电路片上能制造出的 电子元件数突破 年代末在集成电路片上能制造出的 电子元件数突破1000的量级 在一个芯片上做出一个简单计 算机成为可能 的量级 在一个芯片上做出一个简单计 算机成为可能 1971年年Intel公司的第一个微处理器芯片公司的第一个微处理器芯片4004 诞生 预示着计算机发展的一个新阶段的到来 诞生 预示着计算机发展的一个新阶段的到来 1976年苹果公司成立 年苹果公司成立 1977年推出的年推出的APPLE II计算机是早期 最成功的微型计算机 计算机是早期 最成功的微型计算机 它性能好 价格低 时价相当于一台 高档家电 这使计算机第一次可能走入小企业 商店 普通 学校 走入家庭成为个人生活用品 计算机所扮演的角色从 此发生根本性变化 从科学研究和大企业应用的象牙塔中走 了出来 逐渐成为普通百姓身边的普通用品 它性能好 价格低 时价相当于一台 高档家电 这使计算机第一次可能走入小企业 商店 普通 学校 走入家庭成为个人生活用品 计算机所扮演的角色从 此发生根本性变化 从科学研究和大企业应用的象牙塔中走 了出来 逐渐成为普通百姓身边的普通用品 当时一项有重大意义的发展是图形技术和图形用户界面技术 计算机原来字符行式的命令形式和信息显示形式 复杂而不直 观的人机交互方式 使大众很难接受和使用 面向普通百姓的 计算机需要一种新表现形式 当时一项有重大意义的发展是图形技术和图形用户界面技术 计算机原来字符行式的命令形式和信息显示形式 复杂而不直 观的人机交互方式 使大众很难接受和使用 面向普通百姓的 计算机需要一种新表现形式 Xerox的的Polo Alto研究中心 研究中心 PARC 70年代末开发了基于窗口菜单按钮和鼠标器控制的 图形界面技术 使计算机操作能以较直观易理解的方式进行 年代末开发了基于窗口菜单按钮和鼠标器控制的 图形界面技术 使计算机操作能以较直观易理解的方式进行 Apple仿照仿照PARC的技术开发了其的技术开发了其Macintosh个人计算机 个人计算机 1984 采用图形用户界面取得巨大成功 这和 采用图形用户界面取得巨大成功 这和1981年年IBM 推出的推出的PC XT计算机一起 推动了微型计算机蓬勃发展的大 潮 计算机一起 推动了微型计算机蓬勃发展的大 潮 另一项影响深远的研究也是从七十年代中开始的 这就是计算 机网络技术的研究 另一项影响深远的研究也是从七十年代中开始的 这就是计算 机网络技术的研究 技术进步使计算机性能飞速提高 价格大幅 度下降 技术进步使计算机