计算机基础课件PPT课件

1、1. 计算机系统的组成计算机系统的组成 计算机是由存储器、运算器、控制器、输入设备和输出设备等五大部件所构成。 输入设备控制器运算器输出设备存储器输入信息输入信息输出信息输出信息请求信号、数据流请求信号、数据流控制信号控制信号冯诺依曼，1945第1页/共90页计算机系统计算机系统硬件系统硬件系统软件系统软件系统主机主机外设外设外存储器外存储器( (硬盘、光驱硬盘、光驱) )输入输入/ /输出设备输出设备系统软件系统软件应用软件应用软件办公处理软件办公处理软件辅助工作软件辅助工作软件实时控制软件实时控制软件操作系统操作系统CPUCPU主板、显卡、声卡主板、显卡、声卡内存内存1. 计算机系统的组成

2、计算机系统的组成第2页/共90页系统软件应用软件计算机的软件系统包括计算机的软件系统包括1. 计算机系统的组成计算机系统的组成第3页/共90页（1）操作系统）操作系统 （2）语言处理程序）语言处理程序 （3）支撑软件）支撑软件 （4）数据库系统）数据库系统 系统软件是指控制和协调计算机及其外部设备，支系统软件是指控制和协调计算机及其外部设备，支持应用软件的开发和运行的软件。其主要的功能是进持应用软件的开发和运行的软件。其主要的功能是进行调度、监控和维护系统等等。系统软件是行调度、监控和维护系统等等。系统软件是用户和裸用户和裸机的接口机的接口。 1. 计算机系统的组成计算机系统的组成第4页/共9

3、0页2. 计算机操作系统计算机操作系统第5页/共90页2. 计算机操作系统计算机操作系统第6页/共90页2. 计算机操作系统计算机操作系统第7页/共90页2. 计算机操作系统计算机操作系统第8页/共90页2. 计算机操作系统计算机操作系统第9页/共90页2. 计算机操作系统计算机操作系统第10页/共90页2. 计算机操作系统计算机操作系统第11页/共90页计算机网络的发展的四个阶段：1.第一阶段：“诞生阶段”以主机为中心的联机终端系统，“计算机终端”系统2.第二阶段：“形成阶段 ”以通信子网为中心的主机互连，“计算机-计算机”网络3.第三阶段：互联互通阶段 体系结构标准化网络层次结构，对每层进

4、行了精确定义4.第四阶段：高速网络技术阶段Internet网时代的到来 3. 计算机网络计算机网络第12页/共90页1.第一阶段：“诞生阶段” 以主机为中心的联机终端系统特征：终端(Terminal)共享主机(Host)的软硬件资源 单台主机：执行计算和通信任务 多台终端：执行用户交互 (终端集中器/终端服务器)连接方式：本地或远程TTTTTHOST通信线路3. 计算机网络计算机网络第13页/共90页2.第二阶段：“形成阶段 ” 通信子网为中心的主机互连 特征 多个终端联机系统互联，形成了多主机互联网络 网络结构从“主机终端” 转变为“主机主机”HOSTHOSTHOSTTTTTTTTTTT通信

5、线路3. 计算机网络计算机网络第14页/共90页 演变阶段1 通信任务从主机中分离，由通信控制处理机（CCP）完成 CCP：处理主机之间通信任务的专用计算机CCPCCPHOSTHOSTTTTTTTCCPHOSTTT3. 计算机网络计算机网络第15页/共90页两层网络概念的出现 由CCP组成的传输网络通信子网，提供信息传输服务 建立在通信子网基础上的主机集合资源子网，提供计算资源CCPCCPHOSTHOSTTTTTTTCCPHOSTTTT通信子网通信子网3. 计算机网络计算机网络第16页/共90页17 演变阶段2 通信子网规模逐渐扩大 私有社会公用 公用数据通信网 PSTN X.25 优点 降低

6、用户系统建设成本 提高通信线路利用率 兼容性好公用数据通信网HOSTHOSTTTTTTTHOSTTTTT3. 计算机网络计算机网络第17页/共90页3.第三阶段：互联互通阶段 体系结构标准化网络 为什么需要标准化？ 不同网络设备之间的兼容性和互操作性是推动网络体系结构的标准化的原动力 而兼容性和互操作性的最终目的仍是资源共享 标准化的时机？ 先制定标准再开发还是先开发再制定标准？ 各厂商、研究机构、大学在网络技术、方法、理论等方面的研究日趋成熟是基础3. 计算机网络计算机网络第18页/共90页4.第四阶段：高速网络技术阶段 因特网的出现标志着网络时代的到来 因特网是全球性的网络 丰富的信息和便

7、利的使用是其规模迅速增长的主要驱动力 截止到2000年, Internet的规模为 网络数达到105数量级, 主机数达到107数量级, 用户数108数量级，主干速率大于2.5Gbit/s3. 计算机网络计算机网络第19页/共90页 计算机网络体系结构的形成 相互通信的两个计算机系统必须高度协调工作才行，而这“协调”是相当复杂的。 “分层”可将庞大而复杂的问题，转化为若干较小的局部问题，而这些较小的局部问题就比较易于研究和处理。 3. 计算机网络计算机网络第20页/共90页OSI 与 TCP/IP 体系结构的比较 应用层传输层网络层表示层会话层数据链路层物理层7654321OSI 的体系结构应用

8、层网络接口层网际层 IP (各种应用层协议如TELNET, FTP, SMTP 等)传输层(TCP 或 UDP)TCP/IP 的体系结构3. 计算机网络计算机网络第21页/共90页分层的好处 1. 各层之间是独立的。 2. 灵活性好。 3. 结构上可分割开。 4. 易于实现和维护。 5. 能促进标准化工作。 若层数太少，就会使每一层的协议太复杂。层数太多又会在描述和综合各层功能的系统工程任务时遇到较多的困难。 3. 计算机网络计算机网络第22页/共90页五层协议的体系结构 ：TCP/IP 是四层的体系结构：应用层、运输层、网际层和网络接口层。最下面的网络接口层并没有具体内容。因此往往采取折中的

9、办法，即综合 OSI 和 TCP/IP的优点，采用一种只有五层协议的体系结构 。 3. 计算机网络计算机网络第23页/共90页计算机 1 向计算机 2 发送数据 5432154321计算机 1AP2AP1计算机 2应 用 程 序 数 据应用层首部H510100110100101 比 特 流 110101110101注意观察加入或剥去首部（尾部）的层次应 用 程 序 数 据H5应 用 程 序 数 据H4H5应 用 程 序 数 据H3H4H5应 用 程 序 数 据H4运输层首部H3网络层首部H2链路层首部T2链路层尾部3. 计算机网络计算机网络第24页/共90页网络接口卡网络接口卡（NIC，简称网

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

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

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

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

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

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

16、数据元素，通常作为整体进行处理。 数据元素还不是组成数据的最小单位。6. 数据结构、算法、程序数据结构、算法、程序第47页/共90页 数据结构（Data Structures):带结构的数据元素的集合。 结构：数据元素之间存在的约束关系 数据元素之间不是孤立的，而是相互之间存在着一种或多种特定的关系6. 数据结构、算法、程序数据结构、算法、程序第48页/共90页一种数据结构包含下面三个方面：逻辑结构：表示数据元素之间的逻辑关系。 Data_Structure=( D, S )物理结构：数据结构在计算机存储器中的映射（或表示）， 又称存储结构，也称存储表示结构的行为特征 作用于数据结构上的运算。

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

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

19、存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。 6. 数据结构、算法、程序数据结构、算法、程序第54页/共90页1536元素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. 数据结构、算法、程序数据结构、算法、程序第55页/共90

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

21、条指令表示一个或多个操作。n算法是指解决问题的一种方法或一个过程。6. 数据结构、算法、程序数据结构、算法、程序第58页/共90页 N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构程序设计：为计算机处理问题编制一组指令集算法：怎样处理问题，解决问题的策略数据结构：要处理的信息如何表示，问题的表示模型6. 数据结构、算法、程序数据结构、算法、程序第59页/共90页 N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据（算法数据结构）。 （2）算法的设计依赖于作为基础的数据结构（数据结构算

22、法）。6. 数据结构、算法、程序数据结构、算法、程序第60页/共90页算法的5个特性 有穷性：算法必须总是在执行有穷步后结束，每一步在有穷时间内完成。 确定性：组成算法的每条指令是清晰，无歧义的。 可行性：算法是可执行的。 输入：有零个或多个外部提供的量作为输入。 输出：算法产生至少一个量作为输出。6. 数据结构、算法、程序数据结构、算法、程序第61页/共90页数据结构的主要内容数学模型解题思路 问题抽象数据结构算法 数据类型程序设计编码运行图 计算机解决问题的一般过程6. 数据结构、算法、程序数据结构、算法、程序第62页/共90页 算法设计的要求 1.正确性：算法应当满足具体问题的需求。正确

23、的含义有4个层次的级别：1、程序不含语法错误；2、程序对于几种输入数据有正确的结果；3、程序对于典型、苛刻、刁难性的数据有正确的结果；4、对于一切合法的输入数据都有正确结果。6. 数据结构、算法、程序数据结构、算法、程序第63页/共90页 算法设计的要求 2.可读性：有助于人对算法的理解。 算法主要是为了人的阅读和交流，晦涩难懂的程序容易隐藏错误，难以调试和修改。6. 数据结构、算法、程序数据结构、算法、程序第64页/共90页 算法设计的要求 3.健壮性：适当处理任何错误输入。 对于输入非法的数据时，算法能够给出反应作出处理，而不会出现莫名奇妙的错误。6. 数据结构、算法、程序数据结构、算法、

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

25、算法本身的优劣。6. 数据结构、算法、程序数据结构、算法、程序第68页/共90页度量算法的执行时间 (2)事前分析估算法 依据的影响因素： 依据的算法选用何种策略； 问题的规模； 书写程序的语言； 编译程序时所产生的机器代码的质量； 机器执行指令的速度。6. 数据结构、算法、程序数据结构、算法、程序第69页/共90页度量算法的执行时间 (2)事前分析估算法 分析方法： 找出算法中最重要的操作基本操作，计算它们的运行次数。 基本操作通常是算法最内层循环中最费时的操作6. 数据结构、算法、程序数据结构、算法、程序第70页/共90页 时间复杂度 一般情况下，算法中基本操作重复执行次数是问题规模n的某

26、个函数f(n),算法的时间量度记作 T(n)=O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。 称做算法的渐近时间复杂度（asymptotic time complexity),简称时间复杂度。 6. 数据结构、算法、程序数据结构、算法、程序第71页/共90页 时间复杂度的意义 反映了随着问题规模的增加，算法消耗时间的增加度。问题规模增加执行时间增长快执行时间增长慢算法效率低算法效率高6. 数据结构、算法、程序数据结构、算法、程序第72页/共90页算法A：int i, sum = 0, n = 100;for(i = 1; i = n; i +) sum =

27、 sum + i;printf ( “%d”, sum);算法B：int sum = 0, n = 100;sum = ( 1+n ) * n/2;printf ( “%d”, sum);哪个算法效率更高？6. 数据结构、算法、程序数据结构、算法、程序第73页/共90页 由于时间复杂度考虑的只是问题规模n的增长率，则在难以精确计算基本操作执行次数的情况下，只需求出它关于n的增长率或阶即可。f(n) = 3n2+n6. 数据结构、算法、程序数据结构、算法、程序第74页/共90页for (i=0; in; i+) S(i);for (i=0; in; i+) for (j=0; jn; j+) S

28、(i,j);f(n)=n，时间复杂度为O(n)f(n)=n2，时间复杂度为O(n2)S(i);f(n)=1，时间复杂度为O(1)6. 数据结构、算法、程序数据结构、算法、程序第75页/共90页例：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. 数据结构、算法、程序数据结构、算法、程序第81页/共90页C语言的发展及其特点语言的发展及其特点 运算符丰富。 有34种运算符 把括号、赋值、强制类型

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