计算机基础课件

1、计算机基础知识计算机基础知识 计算机组成计算机组成 计算机操作系统计算机操作系统 计算机网络计算机网络 数据库数据库 软件工程软件工程 数据结构、算法、程序数据结构、算法、程序 陈 海 新 2017.04.27 1. 计算机系统的组成计算机系统的组成 计算机是由存储器、运算器、控制器、输 入设备和输出设备等五大部件所构成。 输入设备输入设备 控制器控制器 运算器运算器 输出设备输出设备存储器存储器 输入信息输入信息输出信息输出信息 请求信号、数据流请求信号、数据流控制信号控制信号 冯诺依曼，1945 计算机系统计算机系统 硬件系统硬件系统 软件系统软件系统 主机主机 外设外设 外存储器外存储器

2、( (硬盘、光驱硬盘、光驱) ) 输入输入/ /输出设备输出设备 系统软件系统软件 应用软件应用软件 办公处理软件办公处理软件 辅助工作软件辅助工作软件 实时控制软件实时控制软件 操作系统操作系统 CPUCPU 主板、显卡、声卡主板、显卡、声卡 内存内存 1. 计算机系统的组成计算机系统的组成 系系 统统 软软 件件 应应 用用 软软 件件 1. 计算机系统的组成计算机系统的组成 （1）操作系统）操作系统 （2）语言处理程序）语言处理程序 （3）支撑软件）支撑软件 （4）数据库系统）数据库系统 系统软件是指控制和协调计算机及其外部设备，支系统软件是指控制和协调计算机及其外部设备，支 持应用软件

3、的开发和运行的软件。其主要的功能是进持应用软件的开发和运行的软件。其主要的功能是进 行调度、监控和维护系统等等。系统软件是行调度、监控和维护系统等等。系统软件是用户和裸用户和裸 机的接口机的接口。 1. 计算机系统的组成计算机系统的组成 2. 计算机操作系统计算机操作系统 2. 计算机操作系统计算机操作系统 2. 计算机操作系统计算机操作系统 2. 计算机操作系统计算机操作系统 2. 计算机操作系统计算机操作系统 2. 计算机操作系统计算机操作系统 2. 计算机操作系统计算机操作系统 计算机网络的发展的四个阶段： 1.第一阶段：第一阶段：“诞生阶段诞生阶段” 以主机为中心的联机终端系统，“计算

4、机终端”系统 2.第二阶段：第二阶段：“形成阶段形成阶段 ” 以通信子网为中心的主机互连，“计算机-计算机”网 络 3.第三阶段：互联互通阶段第三阶段：互联互通阶段 体系结构标准化网络层次结构，对每层进行了精确定义 4.第四阶段：高速网络技术阶段第四阶段：高速网络技术阶段 Internet网时代的到来 3. 计算机网络计算机网络 1.第一阶段：第一阶段：“诞生阶段诞生阶段” 以主机为中心的联机终端系统 特征：终端(Terminal)共享主机(Host)的软硬件资源 单台主机：执行计算和通信任务 多台终端：执行用户交互 (终端集中器/终端服务器) 连接方式：本地或远程 T T T T T HOS

5、T 通信线通信线 路路 3. 计算机网络计算机网络 2.第二阶段：第二阶段：“形成阶段形成阶段 ” 通信子网为中心的主机互连 特征 多个终端联机系统互联，形成了多主机互联 网络 网络结构从“主机终端” 转变为“主机 主机” HOST HOSTHOST T T T T T T T T T T 通信线路 3. 计算机网络计算机网络 演变阶段1 通信任务从主机中 分离，由通信控制 处理机（CCP）完 成 CCP：处理主机之 间通信任务的专用 计算机 CCP CCP HOST HOST T T TT T T CCP HOST TT 3. 计算机网络计算机网络 两层网络概念的出现 由CCP组成的传输网络

6、通信子网通信子网，提供信息 传输服务 建立在通信子网基础上的主机集合资源子网资源子网 ，提供计算资源 CCP CCP HOST HOST T T TT T T CCP HOST TT T 通信子网通信子网 3. 计算机网络计算机网络 18 演变阶段2 通信子网规模逐渐扩大 私有社会公用 公用数据通信网 PSTN X.25 优点 降低用户系统建设成本 提高通信线路利用率 兼容性好 公用数据公用数据 通信网通信网 HOST HOST T T TT T T HOST TT T T 3. 计算机网络计算机网络 3.第三阶段：互联互通阶段第三阶段：互联互通阶段 体系结构标准化网络 为什么需要标准化？ 不

7、同网络设备之间的兼容性和互操作性是推 动网络体系结构的标准化的原动力 而兼容性和互操作性的最终目的仍是资源共 享 标准化的时机？ 先制定标准再开发还是先开发再制定标准？ 各厂商、研究机构、大学在网络技术、方法、 理论等方面的研究日趋成熟是基础 3. 计算机网络计算机网络 4.第四阶段：高速网络技术阶段第四阶段：高速网络技术阶段 因特网的出现标志着网络时代的到来 因特网是全球性的网络 丰富的信息和便利的使用是其规模迅速增长 的主要驱动力 截止到2000年, Internet的规模为 网络数达到105数量级, 主机数达到107数量级, 用户 数108数量级，主干速率大于2.5Gbit/s 3. 计

8、算机网络计算机网络 计算机网络体系结构的形成 相互通信的两个计算机系统必须高度协调工作 才行，而这“协调”是相当复杂的。 “分层”可将庞大而复杂的问题，转化为若干 较小的局部问题，而这些较小的局部问题就 比较易于研究和处理。 3. 计算机网络计算机网络 OSI 与 TCP/IP 体系结构的比较 应用层 传输层 网络层 表示层 会话层 数据链路层 物理层 7 6 5 4 3 2 1 OSI 的体系结构 应用层 网络接口层 网际层 IP (各种应用层协议如 TELNET, FTP, SMTP 等) 传输层(TCP 或 UDP) TCP/IP 的体系结构 3. 计算机网络计算机网络 分层的好处分层的

9、好处 1. 各层之间是独立的。 2. 灵活性好。 3. 结构上可分割开。 4. 易于实现和维护。 5. 能促进标准化工作。 若层数太少，就会使每一层的协议太复杂。 层数太多又会在描述和综合各层功能的系统工程任务时遇到较多的困难。 3. 计算机网络计算机网络 五层协议的体系结构 ： TCP/IP 是四层的体系结构：应用层、运输层、网 际层和网络接口层。 最下面的网络接口层并没有具体内容。 因此往往采取折中的办法，即综合 OSI 和 TCP/IP 的优点，采用一种只有五层协议的体系结构 。 3. 计算机网络计算机网络 计算机 1 向计算机 2 发送数据 5 4 3 2 1 5 4 3 2 1 计算

10、机 1 AP2 AP1 计算机 2 应 用 程 序 数 据 应用层首部 H5 10100110100101 比 特 流 110101110101 注意观察加入或剥去首部（尾部）的层次 应 用 程 序 数 据 H5应 用 程 序 数 据 H4H5应 用 程 序 数 据 H3H4H5应 用 程 序 数 据 H4 运输层首部 H3 网络层首部 H2 链路层 首部 T2 链路层 尾部 3. 计算机网络计算机网络 网络接口卡 网络接口卡（NIC，简 称网卡）能够使工作站、 服务器、打印机或其他 节点通过网络介质接收 并发送数据。网络接口 卡常被称为网络适配器。 属于OSI模型的物理层。 3. 计算机网络

11、计算机网络 中继器 中继器是一种放大或模 拟数字信号的网络连接 设备。 中继器属于OSI模型中 的物理层。它们只是转 发信号，但同时也转发 了信号的噪声， 3. 计算机网络计算机网络 集线器 集线器能与网络中的打 印服务器、交换器、文 件服务器或其他的设备 连接。 集线器属于OSI模型中 的物理层。 3. 计算机网络计算机网络 网桥 网桥这种设备看上去有 点像中继器。它具有单 个的输入端口和输出端 口，它与中继器的不同 之处就在于它能够解析 它收发的数据。 网桥属于OSI模型的数 据链路层 3. 计算机网络计算机网络 交换机 交换机属于OSI模型的 数据链路层，并且，它 还能够解析出MAC地

12、址信息。事实上，它相 当于多个网桥。 3. 计算机网络计算机网络 路由器 路由器是一种多端口设备，它可以连接不 同传输速率并运行于各种环境的局域网 和广域网，也可以采用不同的协议。路 由器属于OSI模型的网络层设备。 3. 计算机网络计算机网络 数据库系统的产生与发展 数据库基本概念数据库基本概念 1）数据）数据(Data) 数据是描述事物的符号记录。 2）信息）信息(Information) 通常被认为是具有一定含义的、经过 加工的、对决策有价值的数据。 3）数据库）数据库(Database, DB) 数据库是指长期存储在计算机内，有 组织的、可共享的数据集合。 4. 数据库数据库 l 数据

13、结构数据结构 是所研究的对象类型的集合。用于描述数据的静态特征。 包括：数据的类型、内容和性质的对象（事物）；数据之 间联系的对象（联系）。 l 数据操作数据操作 是对数据库中各种对象的实例允许执行的操作的集合。用 于描述数据的动态特征。 l 完整性约束完整性约束 完整性规则的集合。如性别只能有男和女之分，年龄不能 为0等。 数据模型概述数据模型概述 4. 数据库数据库 最常用的数据模型最常用的数据模型 1层次模型 层次模型（Hierarchical Model）是一种以记录某一事物的类型为根节点 的有向树。 4. 数据库数据库 2网状模型 最常用的数据模型最常用的数据模型 网状模型是层次模型

14、的扩展，表示多个从属关系的层次结构，呈现一种 交叉关系的网状结构。 4. 数据库数据库 关系模型（Relational Model）是指虽具有相关性而非从属性的平行的数据 之间按照某种序列排列的集合关系。关系模型是由若干个关系模式组成的集合， 关系模式的实例称为关系，而每个关系实际上就是一张二维表格。 4. 数据库数据库 最常用的数据模型最常用的数据模型 3关系模型 基本概念 关系：一个关系对应一张表 元组：表中的一行 属性：表中的一列 主码：表中的某个属性或属性组，它可以唯一确定一个元组 域：属性的取值范围 分量：元组中的一个属性值 关系模式：对关系的描述 4. 数据库数据库 关系的性质 1

15、)关系中每一数据项不可再分，是最基本的单位。 2)每一列数据项是同属性的。列数根据需要而设，且各列 的顺序是任意的。 3)每一行记录由一个事物的诸多属性项构成。记录的顺序 可以是任意的。 4)一个关系是一张二维表，不允许有相同的字段名，也不 允许有相同的记录行。 5)每个关系都有称之为关键字的属性集唯一标识各元组。 4. 数据库数据库 5. 软件工程软件工程 5. 软件工程软件工程 软件开发V模型 5. 软件工程软件工程 5. 软件工程软件工程 5. 软件工程软件工程 5. 软件工程软件工程 5. 软件工程软件工程 5. 软件工程软件工程 数据数据(Data)：在计算机科学中是所有能输：在计算

16、机科学中是所有能输 入到计算机中并能被计算机程序处理的入到计算机中并能被计算机程序处理的 符号符号的总称。的总称。 数据包含的内容随着计算机的发展而扩大数据包含的内容随着计算机的发展而扩大 例如：数字、字母、汉字、图形、图像、声例如：数字、字母、汉字、图形、图像、声 音都称为数据。音都称为数据。 注意：专业术语中，数据已经不是注意：专业术语中，数据已经不是“数值数值”。 6. 数据结构、算法、程序数据结构、算法、程序 数据元素数据元素(Data Element)：数据的基本单位，：数据的基本单位， 在计算机程序中通常作为一个整体进行考在计算机程序中通常作为一个整体进行考 虑和处理。虑和处理。

17、人是一个数据元素，通常作为整体进行处理。人是一个数据元素，通常作为整体进行处理。 数据元素还不是组成数据的最小单位。数据元素还不是组成数据的最小单位。 6. 数据结构、算法、程序数据结构、算法、程序 数据结构（数据结构（Data Structures):带结构的数据带结构的数据 元素的集合。元素的集合。 结构：数据元素之间存在的约束关系结构：数据元素之间存在的约束关系 数据元素之间不是孤立的，而是相互之间存数据元素之间不是孤立的，而是相互之间存 在着一种或多种特定的关系在着一种或多种特定的关系 6. 数据结构、算法、程序数据结构、算法、程序 一种数据结构包含下面三个方面：一种数据结构包含下面三

18、个方面： 逻辑结构逻辑结构：表示数据元素之间的逻辑关系。：表示数据元素之间的逻辑关系。 Data_Structure=( D, S ) 物理结构物理结构：数据结构在计算机存储器中的映射：数据结构在计算机存储器中的映射 （或表示），（或表示）， 又称存储结构，也称存储表示又称存储结构，也称存储表示 结构的行为特征结构的行为特征 作用于数据结构上的运算。例如：检索，作用于数据结构上的运算。例如：检索， 插入，删除等。插入，删除等。 6. 数据结构、算法、程序数据结构、算法、程序 逻辑结构逻辑结构 根据数据元素间关系的基本特性，有四种基本数据根据数据元素间关系的基本特性，有四种基本数据 结构结构 集

19、合集合数据元素间除数据元素间除“同属于一个集合同属于一个集合”外，无外，无 其它关系其它关系 线性结构线性结构一个对一个，如线性表、栈、队列一个对一个，如线性表、栈、队列 树形结构树形结构一个对多个，如树一个对多个，如树 图形结构图形结构多个对多个，如图多个对多个，如图 6. 数据结构、算法、程序数据结构、算法、程序 （1）顺序存储（向量存储） 以存储位置的相对位置来表示数据元素 之间的逻辑关系。 存储结构(storage structure)：数据结构在 计算机中的表示。 要在计算机中实现数据结构的操作，如何在计 算机中实现对各种数据及其关系的表示？ 6. 数据结构、算法、程序数据结构、算法

20、、程序 顺序存储 存储地址存储地址 存储内容存储内容 1345 1345 元素元素1 1 1346 1346 元素元素2 2 1347 1347 元素元素3 3 1348 1348 元素元素4 4 1349 1349 元素元素5 5 6. 数据结构、算法、程序数据结构、算法、程序 元素n . 元素i . 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 6. 数据结构、算法、程序数据结构、算法、程序 ( 2 ) 链式存储 以附加信息（指针）表示数据元素间 的逻辑关系 所有元素存放在可以不连续的存储单

21、元中，但元素之间的关系可以通过地址 确定，逻辑上相邻的元素存放到计算机 内存后不一定是相邻的。 6. 数据结构、算法、程序数据结构、算法、程序 1536元素21400元素11346元素3 元素4 1345 h 存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 链式存储 h 6. 数据结构、算法、程序数据结构、算法、程序 (3)索引存储 使用该方法存放元素的同时，

22、还建立 附加的索引表，索引表中的每一项称为 索引项，索引项的一般形式是：（关键 字，地址），其中的关键字是能唯一标 识一个结点的那些数据项。 (4)散列存储 通过构造散列函数，用函数的值来确 定元素存放的地址。 6. 数据结构、算法、程序数据结构、算法、程序 数据的逻辑结构 数据的存储结构 数据的运算 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列 树形结构 图形结构 数据结构的三个方面： ：检索、排序、插入、删除、修改等 6. 数据结构、算法、程序数据结构、算法、程序 算法 是对特定问题求解步骤的一种描述，它是 指令的有限序列，其中每一条指令表示一个或 多个操作。 n算法是指解决

23、问题的一种方法或一个过程。 6. 数据结构、算法、程序数据结构、算法、程序 N.沃思（沃思（Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+数据结构数据结构 程序设计程序设计：为计算机处理问题编制一组指令集：为计算机处理问题编制一组指令集 算法算法：怎样处理问题，解决问题的策略：怎样处理问题，解决问题的策略 数据结构数据结构：要处理的信息如何表示，问题的表：要处理的信息如何表示，问题的表 示模型示模型 6. 数据结构、算法、程序数据结构、算法、程序 N.沃思（沃思（Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+数据结构数据结构 以上公式说明了如下两

24、个问题：以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据）数据上的算法决定如何构造和组织数据 （算法（算法数据结构）数据结构）。 （2）算法的设计依赖于作为基础的数据结构）算法的设计依赖于作为基础的数据结构 （数据结构（数据结构算法）算法）。 6. 数据结构、算法、程序数据结构、算法、程序 算法的算法的5个特性个特性 有穷性有穷性：算法必须总是在执行有穷步后结束，：算法必须总是在执行有穷步后结束， 每一步在有穷时间内完成。每一步在有穷时间内完成。 确定性确定性：组成算法的每条指令是清晰，无歧义：组成算法的每条指令是清晰，无歧义 的。的。 可行性可行性：算法是可执行的。：算

25、法是可执行的。 输入输入：有零个或多个外部提供的量作为输入。：有零个或多个外部提供的量作为输入。 输出输出：算法产生至少一个量作为输出。：算法产生至少一个量作为输出。 6. 数据结构、算法、程序数据结构、算法、程序 数据结构的主要内容数据结构的主要内容 数学模型 解题思路 问 题 抽象 数据结构 算法 数据类型 程序 设计 编码 运行 图 计算机解决问题的一般过程 6. 数据结构、算法、程序数据结构、算法、程序 算法设计的要求 1.正确性：算法应当满足具体问题的需求。 正确的含义有4个层次的级别： 1、程序不含语法错误； 2、程序对于几种输入数据有正确的结果； 3、程序对于典型、苛刻、刁难性的

26、数据有正确 的结果； 4、对于一切合法的输入数据都有正确结果。 6. 数据结构、算法、程序数据结构、算法、程序 算法设计的要求 2.可读性：有助于人对算法的理解。 算法主要是为了人的阅读和交流，晦涩难懂 的程序容易隐藏错误，难以调试和修改。 6. 数据结构、算法、程序数据结构、算法、程序 算法设计的要求 3.健壮性：适当处理任何错误输入。 对于输入非法的数据时，算法能够给出反 应作出处理，而不会出现莫名奇妙的错误。 6. 数据结构、算法、程序数据结构、算法、程序 算法设计的要求 4.效率和低存储量需求。 效率是指算法执行的时间，执行时间短的 算法效率高。 存储量需求是指算法执行过程中所需要的

27、最大存储空间，显然是越低越好。 6. 数据结构、算法、程序数据结构、算法、程序 算法效率的度量 算法的时间代价(或称时间复杂度) 执行时间越短，算法效率越高。 6. 数据结构、算法、程序数据结构、算法、程序 度量算法的执行时间度量算法的执行时间 (1)事后统计法：运行程序后通过若干统计事后统计法：运行程序后通过若干统计 数据来分辨优劣。数据来分辨优劣。 缺陷：缺陷： 必须先运行依算法编制的程序，一些大型算必须先运行依算法编制的程序，一些大型算 法要运行则比较费时费力；法要运行则比较费时费力； 所得时间的统计量依赖于计算机的硬件、软所得时间的统计量依赖于计算机的硬件、软 件等环境因素，容易掩盖算

28、法本身的优劣。件等环境因素，容易掩盖算法本身的优劣。 6. 数据结构、算法、程序数据结构、算法、程序 度量算法的执行时间度量算法的执行时间 (2)事前分析估算法事前分析估算法 依据的影响因素：依据的影响因素： 依据的算法选用何种策略；依据的算法选用何种策略； 问题的规模；问题的规模； 书写程序的语言；书写程序的语言； 编译程序时所产生的机器代码的质量；编译程序时所产生的机器代码的质量； 机器执行指令的速度。机器执行指令的速度。 6. 数据结构、算法、程序数据结构、算法、程序 度量算法的执行时间度量算法的执行时间 (2)事前分析估算法事前分析估算法 分析方法：分析方法： 找出算法中最重要的操作找

29、出算法中最重要的操作基本操作基本操作，计，计 算它们的算它们的运行次数运行次数。 基本操作通常是算法基本操作通常是算法最内层循环中最费时的操作最内层循环中最费时的操作 6. 数据结构、算法、程序数据结构、算法、程序 时间复杂度 一般情况下，算法中基本操作重复执行次数是问 题规模n的某个函数f(n),算法的时间量度记作 T(n)=O(f(n) 它表示随问题规模n的增大，算法执行时间的增 长率和f(n)的增长率相同。 称做算法的渐近时间复杂度（asymptotic time complexity),简称时间复杂度。 6. 数据结构、算法、程序数据结构、算法、程序 时间复杂度的意义时间复杂度的意义

30、反映了随着问题规模的增加，算法消耗时间的反映了随着问题规模的增加，算法消耗时间的 增加度。增加度。 问题规模增加 执行时间增长快 执行时间增长慢 算法效率低 算法效率高 6. 数据结构、算法、程序数据结构、算法、程序 算法A： int i, sum = 0, n = 100; for(i = 1; i = n; i +) sum = sum + i; printf ( “%d”, sum); 算法B： int sum = 0, n = 100; sum = ( 1+n ) * n/2; printf ( “%d”, sum); 哪个算法效率更高？ 6. 数据结构、算法、程序数据结构、算法、程序

31、 由于时间复杂度考虑的只是问题规模由于时间复杂度考虑的只是问题规模n的增长的增长 率，则在难以精确计算基本操作执行次数的率，则在难以精确计算基本操作执行次数的 情况下，只需求出它情况下，只需求出它关于关于n的增长率或阶的增长率或阶即即 可。可。 f(n) = 3n2+n 6. 数据结构、算法、程序数据结构、算法、程序 for (i=0; in; i+) S(i); for (i=0; in; i+) for (j=0; jn; j+) S(i,j); f(n)=n， 时间复杂度为O(n) f(n)=n2， 时间复杂度为O(n2) S(i); f(n)=1， 时间复杂度为O(1) 6. 数据结构

32、、算法、程序数据结构、算法、程序 例：NXN矩阵相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k10 i=i+1 else i=i-1 endif （2） 语言处理程序语言处理程序 6. 数据结构、算法、程序数据结构、算法、程序 C语言的发展及其特点 运算符丰富。 有有34种运算符种运算符 把括号、赋值、强制类型转换等都作为运算符处理把括号、赋值、强制类型转换等都作为运算符处理 表达式类型多样化表达式类型多样化 6. 数据结构、算法、程序数据结构、算法、程序 C语言的发展及其特点 数据类型丰富。 包括包括:整型、浮点型、字符型、数组类型、指

33、针类型、结整型、浮点型、字符型、数组类型、指针类型、结 构体类型、共用体类型；构体类型、共用体类型； C99又扩充了复数浮点类型、超长整型又扩充了复数浮点类型、超长整型(long long)、布尔、布尔 类型类型(bool)； 指针类型数据，能用来实现各种复杂的数据结构指针类型数据，能用来实现各种复杂的数据结构(如链表、如链表、 树、栈等树、栈等)的运算。的运算。 6. 数据结构、算法、程序数据结构、算法、程序 C语言的发展及其特点 具有结构化的控制语句 如如ifelse语句、语句、while语句、语句、dowhile语句、语句、switch语句、语句、 for语句语句 用函数作为程序的模块单位，便于实现程序的模块化用函数作为程序的模块单位，便于实现程序的模块化 C语言是完全模块化和结构化的语言语言是完全模块化和结构化