计算机基础（课堂PPT）

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

2、/ /输出设备输出设备系统软件系统软件应用软件应用软件办公处理软件办公处理软件辅助工作软件辅助工作软件实时控制软件实时控制软件操作系统操作系统CPUCPU主板、显卡、声卡主板、显卡、声卡内存内存1. 计算机系统的组成计算机系统的组成4系系统统软软件件应应用用软软件件1. 计算机系统的组成计算机系统的组成5（1）操作系统）操作系统 （2）语言处理程序）语言处理程序 （3）支撑软件）支撑软件 （4）数据库系统）数据库系统 系统软件是指控制和协调计算机及其外部设备，支系统软件是指控制和协调计算机及其外部设备，支持应用软件的开发和运行的软件。其主要的功能是进持应用软件的开发和运行的软件。其主要的功能是

3、进行调度、监控和维护系统等等。系统软件是行调度、监控和维护系统等等。系统软件是用户和裸用户和裸机的接口机的接口。 1. 计算机系统的组成计算机系统的组成62. 计算机操作系统计算机操作系统72. 计算机操作系统计算机操作系统82. 计算机操作系统计算机操作系统92. 计算机操作系统计算机操作系统102. 计算机操作系统计算机操作系统112. 计算机操作系统计算机操作系统122. 计算机操作系统计算机操作系统13计算机网络的发展的四个阶段：1.第一阶段：第一阶段：“诞生阶段诞生阶段”以主机为中心的联机终端系统，“计算机终端”系统2.第二阶段：第二阶段：“形成阶段形成阶段 ”以通信子网为中心的主机

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

5、主机互连特征 多个终端联机系统互联，形成了多主机互联网络 网络结构从“主机终端” 转变为“主机主机”HOSTHOSTHOSTTTTTTTTTTT通信线路3. 计算机网络计算机网络16演变阶段1 通信任务从主机中分离，由通信控制处理机（CCP）完成 CCP：处理主机之间通信任务的专用计算机CCPCCPHOSTHOSTTTTTTTCCPHOSTTT3. 计算机网络计算机网络17两层网络概念的出现由CCP组成的传输网络通信子网通信子网，提供信息传输服务建立在通信子网基础上的主机集合资源子网资源子网，提供计算资源CCPCCPHOSTHOSTTTTTTTCCPHOSTTTT通信子网通信子网3. 计算机网

6、络计算机网络18演变阶段2 通信子网规模逐渐扩大 私有社会公用 公用数据通信网 PSTN X.25 优点 降低用户系统建设成本 提高通信线路利用率 兼容性好公用数据公用数据通信网通信网HOSTHOSTTTTTTTHOSTTTTT3. 计算机网络计算机网络193.第三阶段：互联互通阶段第三阶段：互联互通阶段 体系结构标准化网络为什么需要标准化？ 不同网络设备之间的兼容性和互操作性是推动网络体系结构的标准化的原动力 而兼容性和互操作性的最终目的仍是资源共享标准化的时机？ 先制定标准再开发还是先开发再制定标准？ 各厂商、研究机构、大学在网络技术、方法、理论等方面的研究日趋成熟是基础3. 计算机网络计

7、算机网络204.第四阶段：高速网络技术阶段第四阶段：高速网络技术阶段 因特网的出现标志着网络时代的到来因特网是全球性的网络丰富的信息和便利的使用是其规模迅速增长的主要驱动力截止到2000年, Internet的规模为 网络数达到105数量级, 主机数达到107数量级, 用户数108数量级，主干速率大于2.5Gbit/s3. 计算机网络计算机网络21 计算机网络体系结构的形成相互通信的两个计算机系统必须高度协调工作才行，而这“协调”是相当复杂的。 “分层”可将庞大而复杂的问题，转化为若干较小的局部问题，而这些较小的局部问题就比较易于研究和处理。 3. 计算机网络计算机网络22OSI 与 TCP/

8、IP 体系结构的比较 应用层传输层网络层表示层会话层数据链路层物理层7654321OSI 的体系结构应用层网络接口层网际层 IP (各种应用层协议如TELNET, FTP, SMTP 等)传输层(TCP 或 UDP)TCP/IP 的体系结构3. 计算机网络计算机网络23分层的好处分层的好处 1. 各层之间是独立的。2. 灵活性好。3. 结构上可分割开。4. 易于实现和维护。5. 能促进标准化工作。 若层数太少，就会使每一层的协议太复杂。层数太多又会在描述和综合各层功能的系统工程任务时遇到较多的困难。 3. 计算机网络计算机网络24五层协议的体系结构 ：TCP/IP 是四层的体系结构：应用层、运

9、输层、网际层和网络接口层。最下面的网络接口层并没有具体内容。因此往往采取折中的办法，即综合 OSI 和 TCP/IP的优点，采用一种只有五层协议的体系结构 。 3. 计算机网络计算机网络25计算机 1 向计算机 2 发送数据 5432154321计算机 1AP2AP1计算机 2应 用 程 序 数 据应用层首部H510100110100101 比 特 流 110101110101注意观察加入或剥去首部（尾部）的层次应 用 程 序 数 据H5应 用 程 序 数 据H4H5应 用 程 序 数 据H3H4H5应 用 程 序 数 据H4运输层首部H3网络层首部H2链路层首部T2链路层尾部3. 计算机网络

10、计算机网络26网络接口卡网络接口卡（NIC，简称网卡）能够使工作站、服务器、打印机或其他节点通过网络介质接收并发送数据。网络接口卡常被称为网络适配器。属于OSI模型的物理层。 3. 计算机网络计算机网络27中继器中继器是一种放大或模拟数字信号的网络连接设备。中继器属于OSI模型中的物理层。它们只是转发信号，但同时也转发了信号的噪声， 3. 计算机网络计算机网络28集线器集线器能与网络中的打印服务器、交换器、文件服务器或其他的设备连接。 集线器属于OSI模型中的物理层。 3. 计算机网络计算机网络29网桥网桥这种设备看上去有点像中继器。它具有单个的输入端口和输出端口，它与中继器的不同之处就在于它

11、能够解析它收发的数据。网桥属于OSI模型的数据链路层 3. 计算机网络计算机网络30交换机交换机属于OSI模型的数据链路层，并且，它还能够解析出MAC地址信息。事实上，它相当于多个网桥。 3. 计算机网络计算机网络31路由器路由器是一种多端口设备，它可以连接不同传输速率并运行于各种环境的局域网和广域网，也可以采用不同的协议。路由器属于OSI模型的网络层设备。3. 计算机网络计算机网络32数据库系统的产生与发展数据库基本概念数据库基本概念1）数据）数据(Data)数据是描述事物的符号记录。2）信息）信息(Information) 通常被认为是具有一定含义的、经过加工的、对决策有价值的数据。3）数

12、据库）数据库(Database, DB) 数据库是指长期存储在计算机内，有组织的、可共享的数据集合。4. 数据库数据库33l 数据结构数据结构 是所研究的对象类型的集合。用于描述数据的静态特征。包括：数据的类型、内容和性质的对象（事物）；数据之间联系的对象（联系）。l 数据操作数据操作 是对数据库中各种对象的实例允许执行的操作的集合。用于描述数据的动态特征。l 完整性约束完整性约束 完整性规则的集合。如性别只能有男和女之分，年龄不能为0等。数据模型概述数据模型概述4. 数据库数据库34最常用的数据模型最常用的数据模型1层次模型 层次模型（Hierarchical Model）是一种以记录某一事

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

14、性的取值范围分量：元组中的一个属性值关系模式：对关系的描述4. 数据库数据库38关系的性质1)关系中每一数据项不可再分，是最基本的单位。2)每一列数据项是同属性的。列数根据需要而设，且各列的顺序是任意的。3)每一行记录由一个事物的诸多属性项构成。记录的顺序可以是任意的。4)一个关系是一张二维表，不允许有相同的字段名，也不允许有相同的记录行。5)每个关系都有称之为关键字的属性集唯一标识各元组。4. 数据库数据库395. 软件工程软件工程405. 软件工程软件工程软件开发V模型415. 软件工程软件工程425. 软件工程软件工程435. 软件工程软件工程445. 软件工程软件工程455. 软件工程

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

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

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

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

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

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

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

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

23、 （1）数据上的算法决定如何构造和组织数据）数据上的算法决定如何构造和组织数据（算法（算法数据结构）数据结构）。 （2）算法的设计依赖于作为基础的数据结构）算法的设计依赖于作为基础的数据结构（数据结构（数据结构算法）算法）。6. 数据结构、算法、程序数据结构、算法、程序62算法的算法的5个特性个特性有穷性有穷性：算法必须总是在执行有穷步后结束，：算法必须总是在执行有穷步后结束，每一步在有穷时间内完成。每一步在有穷时间内完成。确定性确定性：组成算法的每条指令是清晰，无歧义：组成算法的每条指令是清晰，无歧义的。的。可行性可行性：算法是可执行的。：算法是可执行的。输入输入：有零个或多个外部提供的量作

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

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

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

27、序70度量算法的执行时间度量算法的执行时间(2)事前分析估算法事前分析估算法依据的影响因素：依据的影响因素： 依据的算法选用何种策略；依据的算法选用何种策略； 问题的规模；问题的规模； 书写程序的语言；书写程序的语言； 编译程序时所产生的机器代码的质量；编译程序时所产生的机器代码的质量； 机器执行指令的速度。机器执行指令的速度。6. 数据结构、算法、程序数据结构、算法、程序71度量算法的执行时间度量算法的执行时间(2)事前分析估算法事前分析估算法分析方法：分析方法： 找出算法中最重要的操作找出算法中最重要的操作基本操作基本操作，计，计算它们的算它们的运行次数运行次数。 基本操作通常是算法基本操

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

29、加执行时间增长快执行时间增长慢算法效率低算法效率高6. 数据结构、算法、程序数据结构、算法、程序74算法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. 数据结构、算法、程序数据结构、算法、程序75由于时间复杂度考虑的只是问题规模由于时间复杂度考虑的只是问题规模n的增长的增长率，则在难以精确计算基本操作执行次数的率，则在难以精确

30、计算基本操作执行次数的情况下，只需求出它情况下，只需求出它关于关于n的增长率或阶的增长率或阶即即可。可。f(n) = 3n2+n6. 数据结构、算法、程序数据结构、算法、程序76for (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. 数据结构、算法、程序数据结构、算法、程序77例：NXN矩阵相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k10 i=

31、i+1 else i=i-1 endif（2） 语言处理程序语言处理程序6. 数据结构、算法、程序数据结构、算法、程序83C语言的发展及其特点运算符丰富。有有34种运算符种运算符把括号、赋值、强制类型转换等都作为运算符处理把括号、赋值、强制类型转换等都作为运算符处理表达式类型多样化表达式类型多样化6. 数据结构、算法、程序数据结构、算法、程序84C语言的发展及其特点数据类型丰富。包括包括:整型、浮点型、字符型、数组类型、指针类型、结整型、浮点型、字符型、数组类型、指针类型、结构体类型、共用体类型；构体类型、共用体类型；C99又扩充了复数浮点类型、超长整型又扩充了复数浮点类型、超长整型(long long)、布尔、布尔类型类型(bool)；指针类型数据，能用来实现各种复杂的数据结构指针类型数据，能用来实现各种复杂的数据结构(如链表、如链表、树、栈等树、栈等)的运算。的运算。6. 数据结构、算法、程序数据结构、算法、程序85C语言的发展及其特点具有结构化的控制语句如如ifelse语句、语句、while语句、语句、dowhile语句、语句、switch语句、语句、for语句语句用函数作为程序的模块单位，便于实现程序的模块化用函数作为程序的模块单位，便于实现程序的模块化C语言是完全模块化和结构化的语言语言是完全模块化和结构化的语言6. 数据