第 1 章计算机科学技术的基础知识本章学习目标本章主要讲解计算机的发展简史,特点,用途,
系统组成,基本结构和工作原理,计算机中数据的表示方法 ——数制与码制,程序设计基础知识等内容 。 通过本章的学习,主要掌握以下内容：
计算机的基本概念,特点,用途及发展
数制及数制间的相互转换方法
计算机中数的表示方法,ASCII码和汉字编码
计算机基本结构和工作原理
程序设计语言,程序设计方法
算法与数据结构第 1章 计算机科学技术的基础知识
1.1 计算机概述
1.2 计算机科学与技术专业的知识结构
1.3 计算机的运算基础
1.4 逻辑代数与逻辑电路基础
1.5 计算机的基本结构和工作原理
1.6 程序设计基础
1.1 计算机概述
1.1.1 计算机的基本概念
1.1.2 计算机系统的组成
1.1.3 计算机的发展
1.1.4 计算机的分类
1.1.5 计算机的特点
1.1.6 计算机的用途 返回
1.1.1 计算机的基本概念
,计算机,顾名思义是一种计算的机器，它是由一系列电子器件组成 —英语名称为 Computer。
计算机可以对 数字、文字、颜色、声音、图形、图像 等各种形式的数据进行加工处理。
计算机具有各种计算的能力。 当用计算机进行数据处理时，首先把要解决的实际问题，用计算机语言编写成计算机程序，然后将待处理的数据和程序输入到计算机中，计算机按程序的要求，一步一步地进行各种运算，
直到存入的整个程序执行完毕为止。
计算机具有各种计算的能力。 在数据处理过程中，
计算机不仅能进行加、减、乘、除等算术运算，而且还能进行逻辑运算并对运算结果进行判断，从而决定以后执行什么操作。
计算机具有信息处理能力 。 在当今的信息社会里,各行各业,随时随处产生大量的信息,人们为了高效地获取,传送,检索信息及从信息中产生各种报表数据,必须将信息在计算机的控制下进行有效的组织和管理 。
综上所述,可以给计算机下一个定义：
计算机是一种能按照事先存储的程序,自动,高速地进行大量数值计算和各种信息处理的现代化智能电子设备 。
返回
1.1.2 计算机系统的组成计算机系统由计算机硬件和计算机软件两大部分组成。
硬件（ Computer hardware)
主要由 CPU,存储器、输入输出控制系统和各种输入输出设备等功能部件组成。
软件（ Computer software)
它包括计算机运行所需的各种程序、
数据及相关文档资料。
裸机脱离软件的计算机硬件称,裸机,。
硬件是软件赖以运行的物质基础，软件是人与硬件之间的界面。
操作员（人）
应用软件支撑软件系 编译程序统 ……..
软件 操作系统计算机硬件计算机软件计算机系统的层次结构返回
1.1.3 计算机的发展自 1946年 美国宾西法尼亚大学研制出世界上第一台电子数字计算机 ENIAC（ 电子数字积分计算机的英文缩写）至今，短短五十多年的时间内，计算机系统和计算机应用得到了飞速发展。元件制作工艺水平的不断提高是计算机发展的物质基础，因此以 计算机元器件 的变革作为标志，计算机的发展已经历了四代，并正在研制第五代 。
1,第一代计算机 —电子管计算机 （ 1946～ 1957年 ）
其主要特征是采用电子管作为主要元器件。 ENIA。
2．第二代计算机 —晶体管计算机（ 1958～ 1964年）
其主要特征是由电子管改为晶体管。
3．第三代计算机 —集成电路计算机（ 1965～ 1971年）
其主要特征是用半导体中小规模集成电路代替分立元件的晶体管。
4,第四代计算机 —大规模与超大规模集成电路计算机
（ 1972年至今 ）
其主要特征是以大规模和超大规模集成电路为计算机的主要功能部件。
5,新一代计算机 —智能计算机新一代计算机正在研制之中,主要特征是人工智能,
它将具有自然语言理解能力,模式识别能力和推理判断能力等,突破冯,诺依曼体系结构的限制,提出非冯,
诺依曼的体系结构,如神经网络计算机 。
6,微型计算机的发展概况微型计算机 （ 简称微机 ） 诞生于 1971年,属于第四代计算机,微型计算机的诞生和迅速普及是计算机发展史中最重大的事件 。 微型计算机具有体积小,重量轻,功耗小,可靠性高,使用环境要求不严格,价格低廉,易于成批生产等特点 。
世界上第一台微机是由美国 Intel公司年轻的工程师马西安,霍夫 （ M.E.Hoff） 于 1971年研制成功的 。
他大胆地提出了一个设想,把计算机的全部电路做在四个芯片上,即一片 4位微处理器 Intel4004,一片 320位的随机存取存储器,一片 256字节的只读存储器和一片 10位的寄存器,它们通过总线连接起来就组成了世界第一台 4位微型计算机 —MCS-4。
微型计算机的核心部件是 微处理器 （ MPU）,根据微处理器集成规模和功能,形成了微型计算机的不同发展阶段 。
1．第一代微型计算机
1972年 Intel公司研制成功 8位微处理器 Intel8008,它主要采用工艺简单、速度较低的 P沟道 MOS电路。由它装备起来的计算机 MCS-8称为第一代微型计算机。
2．第二代微型计算机第二代微处理器是在 1973年研制成功的，主要采用速度较快的 N沟道 MOS技术的 8位微处理器。具有代表性的产品有 Intel公司的 Intel8085,Motorola公司的 M6800,Zilog公司的 Z80等。由它装备起来的计算机称为第二代微型计算机。
3．第三代微型计算机第三代微处理器是在 1978年研制成功的，主要采用 H-MOS新工艺的 16位微处理器。其典型产品是 Intel公司的 Intel8086。 由第三代微处理器装备起来的计算机称为第三代微型计算机。
4．第四代微型计算机从 1985年起采用超大规模集成电路的 32位微处理器，标志着第四代微处理器的诞生。典型产品有 Intel公司的 Intel80386。
由第四代微处理器装备起来的计算机称为第四代微型计算机。 返回
1.1.4 计算机 的分类计算机科学技术的发展日新月异，它已成为一个庞大的家族。
计算机的种类很多，从不同角度对计算机有不同的分类方法。
1．按计算机处理数据的方式分类可以分为数字计算机,模拟计算机和数字模拟混合计算机三类。
2．按计算机的用途分类可分为通用计算机和专用计算机两类。
3．按计算机的规模和处理能力分类规模和处理能力主要是指计算机的体积,字长,运算速度,
存储容量,外设的配置,输入输出能力等主要技术指标,按其分类大体可分为巨型计算机,大 /中型计算机,小型计算机,微型计算机,工作站,服务器以及网络计算机等种类 。
总之,目前微型计算机与工作站,小型计算机乃至中大型计算机之间的界限已经越来越模糊 。 无论按哪一种方法分类,各类计算机之间的主要区别是运算速度,
存储容量及机器体积等 。
返回
1.1.5 计算机 的特点计算机作为一种通用的信息处理工具,它具有极高的处理速度,很强的存储能力,精确的计算能力和逻辑判断能力 。 虽然各类计算机在性能上,用途上,规模结构上有所不同,但它们都具备以下一些特点 。
1,运算速度快由于计算机是采用高速电子器件组成,因此能以极高的速度工作 。
目前的巨型机运算速度已达到每秒几百亿次运算,微机也可达到每秒亿次以上 。
2,计算精度高由于计算机采用二进制表示数据,因此它的精度主要取决于表示数据的位数,即机器字长 。 字长越长,其精度越高 。
3,具有记忆能力存储器是计算机的记忆部件,计算机把大量的数据和程序存入存储器,并把处理或计算的结果保存在存储器中 。 计算机存储器有内存和外存之分,目前,微型计算机的内存容量一般可以达到 512MB且可以进一步扩展,外存 （ 如硬盘 ） 容量可以达到十 GB甚至上百 GB。
4,具有逻辑判断能力计算机不仅具有运算能力,还可以进行各种逻辑判断,并根据判断的结果自动决定下一步应该执行的指令 。
5,具有自动控制能力计算机内可以存储程序,计算机可以在人们事先编制好的程序的控制 下自动地完成各种操作,无需人工干预 。 返回
1.1.6 计算机 的用途计算机在科学技术,国民经济,社会生活等各个方面都得到了广泛的应用 。 按照应用的领域计算机的用途归纳起来可分为以下几个方面 。
1,科学计算科学计算又称为数值计算,是指使用计算机来完成科学研究和工程技术中提出的数学问题计算 。 如人造卫星轨迹的计算 。
2,数据处理数据处理是指用计算机对数据进行输入,分类,加工,统计,排序,
传输,检索,存储,制表等操作,形成有用的信息 。 据统计,全世界计算机用于数据处理的工作量占全部计算机应用的 80%以上 。
3,过程控制过程控制又称为实时控制,自动控制,所谓过程控制是指用计算机及时采集数据,将数据检测,处理后,按最佳值迅速对控制对象进行自动控制或自动调节 。 目前广泛应用于钢铁工业,石油工业,医药工业等 。
4,计算机辅助系统计算机辅助系统主要包括计算机辅助设计,计算机辅助制造,计算机辅助教育等 。
5,人工智能人工智能是用计算机模拟或部分模拟人类的智能,一般是指模拟人脑进行演绎推理和采取决策的思维过程 。
6,电子商务电子商务是指通过计算机和网络进行商务活动 。 返回
1.2 计算机科学与技术专业的知识结构计算机科学技术学科经历半个多世纪的迅猛发展,已成为比较完备的学科体系,衍生了许多相对独立的方向和分支 。 从学科体系的角度,可将计算机科学与技术学科的内容划分为三个层面：
应用层,专业基础层和专业基础的理论基础层 。
1,应用层应用层是与计算机应用领域或用户最接近的层面,它包括人工智能应用与系统,信息,管理与决策系统,计算可视化,科学计算等计算机应用的各个方向 。
2,专业基础层专业基础层为应用层提供理论和方法指导及环境 。 它包括软件开发方法学,计算机网络与通信技术,程序设计科学,计算机体系结构,电子计算机系统基础 。
3,专业基础的理论基础层专业基础的理论基础层是为计算机专业基础提供理论指导或依据的更低层的理论层面,包含了计算机科学的最核心和最基础的理论 。 它主要包括计算理论和高等逻辑等内容 。 返回
1.3 计算机的运算基础基础
1.3.1 数制
1.3.2 码制
1.3.3 定点数与浮点数
1.3.4 信息编码返回
1.3.1 数制关于数，大家并不陌生，数是各种运算的基础。计算机处理的对象就是数据，在计算机中数值，字符、声音、图形、图像等都是数据，那么数据在计算机中是如何表示的？有哪些要求？
1．数制的概念按进位的原则进行计数叫进位计数制，简称 数制 。
人们熟悉十进制数，但除以之外，还有十六进制、十二进制等等。
基数,所谓某数制的基数是指该数制中允许选用的基本数码的个数。如十进制的基数是 10。
位权,一个数码处在数的不同位置时，它所代表的数值是不同的。每个数码所表示的数值等于该数码乘以一个与数码所在位置有关的常数，这个常数叫位权。
位权的大小是以基数为底,数码所在位置的序号为指数的整数次幂 。
例如,十进制数个位数位置上的位权为 100,千位数位置上的位权为 103,小数后第 3位的位权为 10-3。
例如,十进制数 1548.3687可以表示成：
1548.3687 = 1× 103+5× 102+4× 101+8× 100+
3× 10-1+6× 10-2+8× 10-3+7× 10-4
计算机的运算基础是二进制,计算机中采用二进制,
而不采用十进制,这是因为：
（ 1） 二进制的数码 0和 1,用电子器件极易实现 。
（ 2） 二进制数的运算规则简单 。
（ 3） 二进制数只有两个状态,数字的传输和处理不容易出错,计算机工作的可靠性高 。
（ 4） 二进制码的两个符号,0” 和,1” 正好与逻辑命题的两个值,真,和,假,相对应,为计算机实现逻辑运算和程序中逻辑判断提供了便利条件 。
2,常用的数制在计算机科学技术中常用的数制有：
十进制,二进制,八进制和十六进制 。
在计算机内部一切数据的存储,处理和传送均采用 二进制 形式 。
二进制不便于书写,通常用八进制或十六进制来书写,因此计算机学科引入了 八进制和十六进制 。
为了适应人的习惯,数值型数据在输入输出设备上则采用人们十分熟悉的 十进制 。
无论是哪一种数制,采用位权表示法的数制有四个重要的特征：
★ 逢 R进一 （ R为基数 ） 。 如十进制数逢十进一 。
★ 数字的总个数等于基数 。 如十进制数 0—9。
★ 最大的数字比基数小 1。 如十进制中最大数字为 9。
★ 每个数字都要乘以基数的幂次,该幂次由每个数字所在的位置决定 。
一般地,对于 R进制而言,其基数为 R,使用 R个数字表示数值,其中最大的数字为 R-1,任何一个 R进制数 N：
N = an an-1 …,,a1 a0 ·a-1…… a-m
均可表示为如下按权展开式形式：
N = an an-1 …,,a1 a0 ·a-1…… a-m
= an × Rn + an-1 × Rn-1 +… + a1 × R1 +
a0 × R0 + a-1 × R-1 +…… + a-m × R-m
（ 1） 十进制 （ 简记符为 D）
十进制用 0,1,2,3,4,5,6,7,8,9十个数码表示数值,采用,逢十进一,计数原则 。 基数为 10，
位权为 10i。
例如,十进制数 5246.376可表示成：
5246.376 = 5× 103+2× 102+4× 101+6× 100+
3× 10-1+7× 10-2+6× 10-3
（ 2） 二进制 （ 简记符为 B）
二进制用数字 0和 1表示数值,采用,逢二进一,
计数原则 。 基数为 2,位权为 2 i。
例如,二进制数 1011.101可表示成：
1011.101 = 1× 23+0× 22+1× 21+1× 20
+1× 2-1+0× 2-2+1× 2-3
二进制计数方式最本质的东西是每位数计满 2时,
向高一位进一,即,逢二进一,。
对于二进制数,小数点向右移一位,数值就扩大 2
倍,例如,11011.101=10× (1101.1101)；反之,小数点向左移一位,数值就缩小 2倍 。
例如,11011.101=1/10× (110111.01)。
另外,若个位数是 1,则此二进制数就是奇数,如
11,11101,110001等都是奇数,若个位数是 0,则此数就是偶数,如 110,111010,11000等都是偶数 。
二进制数的加法和乘法的运算规则如下：
加法运算规则,乘法运算规则：
0 + 0 = 0 0 × 0 = 0
0 + 1 = 1 0 × 1 = 0
1 + 0 = 1 1 × 0 = 0
1 + 1 = 10 1 × 1 = 1
[例 1.1] （ 1011） 2 + （ 11011） 2 =？
1 0 1 1
+ 1 1 0 1 1
1 0 0 1 1 0
即,1011 + 11011 = 100110
相当于十进制数 11+27=38。
[例 1.2] （ 1001） 2 × （ 110） 2 =？
1 0 0 1
× 1 1 0
1 0 0 1
+ 1 0 0 1
1 1 0 1 1 0
即,（ 1001） 2 × （ 110） 2 =（ 110110） 2
相当于十进制数 9× 6=54。
（ 3） 八进制 （ 简记符为 Q）
八进制用 0,1,2,3,4,5,6,7八个数码表示数值,采用,逢八进一,计数原则 。 基数为 8,位权为 8
i。
例如：
（ 473.25） 8 = 4 × 82 + 7 × 81 + 3 ×
80 + 2 × 8-1 + 5 × 8-2
（ 4） 十六进制 （ 简记符为 H）
十六进制用 0,1,2,3,4,5,6,7,8,9,A，
B,C,D,E,F十六个数码表示数值,采用,逢十六进一,计数原则 。 基数为 16,位权为 16 i。
例如：
（ 4AF8.94B） 16 = 4× 163+A× 162+F× 161+ 8× 160
+9× 16-1 +4× 16-2 +B× 16-3
综上所述可见,各种进位计数制的基本道理是相同的,只是在日常生活中不经常用到二进制,八进制和十六进制,对它们不十分熟悉而已,但它们之间存有内在的联系,它们之间可以相互转换 。
3,各种数制间的相互转换将数由一种数制转换成另一种数制称为数制间的转换 。
（ 1） 非十进制转换成十进制非十进制数转换成十进制数采用,位权法,,即把非十进制数写成各自的按权展开式,然后按十进制运算原则求和,其和值就是转换后对应的十进制数 。
[例 1.3] 将二进制数 1011101.1001转换成十进制数 。
（ 1011101.1001） 2 = 1× 26 + 0× 25 + 1× 24
+ 1× 23 + 1× 22 + 0× 21
+ 1× 20 + 1× 2-1 + 0× 2-2
+ 0× 2-3 + 1× 2-4
= 64+16+8+4+1+0.5+0.0625
=（ 93.5625） 10
[例 1.4] 将八进制数 763.24转换成十进制数 。
（ 763.24） 2 = 7× 82 + 6× 81 + 3× 80 + 2× 8-1
+ 4× 8-2
= 448 + 48 + 3 + 0.25 + 0.0625
= （ 499,3125） 10
[例 1.5] 将十六进制数 B2F转换成十进制数 。
（ B2F） 16 = B× 162 + 2× 161 + F× 160
= 11× 162 + 2× 161 + 15× 160
= 2816 + 32 + 15 = （ 2863） 10
（ 2） 十进制数转换成非十进制数将十进制数转换成二进制,八进制或十六进制等非十进制数的方法是相似的,十进制数转换非十进制数时,整数部分和小数部分分别进行转换,将两个转换结果结合起来就可以得到对应的非十进制数 。
★ 十进制整数转换成非十进制整数将十进制整数转换为非十进制整数采用,除基取余法,。 即,将十进制整数及此期间产生的商逐次除以需转换为数制的基数,直到商为零为止,并记下每一次相除所得到的余数,按从后往前的次序将各余数记作 K n K n -1K n-2…… K 0,从而构成转换后对应的非十进制整数 。
[例 1.6] 将十进制整数 125转换成对应的二进制整数 。
2 125 余数
2 62 1
2 31 0
2 15 1
2 7 1
2 3 1
2 1 1
0 1
则得,（ 125） 10 = （ 1111101） 2
[例 1.7] 将十进制整数 125转换成对应的十六进制整数 。
16 125 余数
16 7 13 （ D）
0 7
则得,（ 125） 10 = （ 7D） 16
[例 1.8] 将十进制整数 125转换成对应的八进制整数 。
8 125 余数
8 15 5
8 1 7
0 1
则得,（ 125） 10 = （ 175） 8
★ 十进制小数转换成非十进制小数将十进制小数转换为非十进制小数采用,乘基取整法,。 即：将十进制小数及此期间产生的积小数部分逐次乘以需转换为数制的基数,直到积的小数部分为零为止或达到一定精度为止,并记下每一次相乘所得到的整数部分,按照从前往后的次序,将各整数部分记作 k–1 k-2…… k-m,从而构成转换后对应的非十进制小数 。
[例 1.9] 将十进制小数 0.625转换成对应的十六进制小数 。
0.625 整数部分
× 16
3750
+ 625
10.000 10 (A)
则得,（ 0,625） 10 =（ 0,A） 16
[例 1.10] 将十进制小数 0.625转换成对应的二进制小数。
0.625 整数部分
× 2
1.250 1
0.25
× 2
0.5 0
× 2
1.0 1
则得：（ 0,625） 10 =（ 0,101） 2
[例 1.11] 将十进制小数 0.625转换成对应的八进制 小数
0.625 整数部分
× 8
5.000 5
则得,（ 0,625） 10 =（ 0,5） 8
[例 1.12] 将十进制小数 0.467转换成对应的二进制数
0.467 整数部分
× 2
0.934 0
× 2
1.868 1
0.868
× 2
1.736 1
0.736
× 2
1.472 1
…………,.
则得,（ 0,467） 10 =（ 0,0111…,） 2
如果一个十进制数既有整数部分，又有小数部分，
则应将整数部分和小数部分分别进行转换，然后把两者相加便得到结果。
[例 1.13] 将十进制数 125.625转换成对应的二进制数因为 （ 125） 10 =（ 1111101） 2
（ 0.625） 10 =（ 0.101） 2
所以 （ 125.625） 10=（ 1111101.101） 2
（ 3）二进制与八进制、十六进制之间的转换由于一位八进制数对应 3位二进制数，一位十六进制数对应 4位二进制数，于是二进制数与八进制数、
十六进制数之间的转换比较简单。
★ 二进制与八进制之间的转换二进制的基数是 2，八进制的基数是 8，由于 8=23，
因此，一位八进制数正好相当于 3位二进制数；反之，
3位二进制数可表示一位八进制数 。
若把二进制数转换为八进制数，只须以小数点为界，将整数部分从右向左每 3位一组，最高一组不足 3
位时，在最左端添 0补足 3位，小数部分从左向右，每
3位一组，最低一组不足 3位时，在最右端添 0补足 3位，
然后，将各组的 3位二进制数转换为对应的一位八进制数即可。反之，若将八进制数转换成二进制数，只要把每位八进制数用对应的 3位二进制数表示即可。
[例 1.14] 将二进制数 1101100111.10011转换成对的八进制数。
0 0 1 1 0 1 1 0 0 1 1 1,1 0 0 1 1 0
1 5 4 7 4 6
则得,（ 1101100111.10011） 2 =（ 1547.46） 8
[例 1.15] 将八进制数 576.32转换成对应的二进制数 。
（ 576.32） 8 = 101 111 110,011 010
则得,(576,32) 8 =（ 101111110,01101） 2
★ 二进制与十六进制之间的转换十六进制的基数是 16，由于 16=24，因此，一位十六进制数可用 4位二进制数表示。
若把二进制数转换为十六进制数,只须以小数点为界,将整数部分从右向左每 4位一组,最高一组不足
4位时,在最左端添 0补足,小数部分从左向右按 4位为一组,最低一组不足 4位时,在最右端添 0补足,然后,
将各组的 4位二进制数转换为对应的一位十六进制数即可 。 反之,若将十六进制数转换成二进制数,只要把每位十六进制数用对应的 4位二进制数表示即可 。
[例 1.16] 将二进制数 1101100111.10111转换成对应的十六进制数 。
0 0 1 1 0 1 1 0 0 1 1 1,1 0 1 1 1 0 0 0
3 6 7 B 8
则得,（ 1101100111,10111） 2 =（ 367,B8） 16
[例 1.17] 将十六进制数 5FD4,A3转换成对应的二进制数 。
（ 5FD4,A3） 8 = 0101 1111 1101 0100,1010 0011
则得,（ 5FD4,A3） 16
=（ 101111111010100,10100011） 2
返回
1.3.2 码制计算机处理的数据分为数值型和非数值型两类。
数值型数据是指数学中的代数值，具有量的含义，且有正负之分、整数和小数之分。 非数值型数据是指输入到计算机中的所有信息，没有量的含义，如英文字母、数字符号 0~9、汉字、声音、图形、
图像等。
在计算机中这些数据是如何表示的呢？由于计算机采用二进制，也就是说计算机只识别 0和 1形式的代码，所以输入到计算机中任何数值型和非数值型数据都必须转换为二进制代码 。
1．机器数与真值在计算机中,数值型数据是用二进制数来表示的,
数值型数据有正,负之分,那么在计算机内部是如何表示正,负号的呢？
在计算机内部数值型数据的最高位用来表示数值的正负,这一位通常称为 符号位 。 规定：用,0” 表示
,+” 号,用,1” 表示,﹣,号 。
在计算机内部数字和正负号都用二进制代码表示,
两者结合在一起构成数值型数据的机内表示 。 我们把这种连同数字与符号组合在一起的二进制数称为 机器数,由机器数所表示的实际值称为 真值 。
如,（ 00110101） 2 =（ +53） 10
即在计算机内部 00110101这一串二进制数代表十进制数 +53。
（ 10110101） 2 =（ ﹣ 53） 10
在计算机内部 10110101这一串二进制数代表十进制数 ﹣53 。
2．原码、反码和补码计算机中机器数可以用不同的码制来表示，常用的码制有原码表示法、反码表示法和补码表示法。
设机器字长为 n位，最高位为符号位，其余 n-1位为数值位。
★ 原码表示法原码：最高位为真值的符号 （ 正为 0,负为 1） 其余 n-1位为数值位且与真值的数值位相同 。 数 X的原码记为 [X]原 。
例如：假设机器字长 8位,二进制数 +1011011和
﹣ 1011011的原码分别表示为 01011011和 11011011。
注意,在原码表示中,零有两种表示形式,
即,[+0]原 =00000000,[﹣ 0]原 =10000000
原码所能表示的数的范围与机器字长有关,设机器字长为八位时,最高位为符号位,整数原码表示的范围为 ﹣ 127 ～ +127。 即最大数是 01111111,最小数是 11111111。 同理,机器字长为十六位时,整数原码的范围为 ﹣ 32767 ～ +32767。
[例 1.19] 假设字长为 8，求十进制数 +56与 ﹣56 的原码。
因为 （ 56） 10 =（ 111000） 2
所以 [+56]原 = 00111000 [﹣ 56]原 =10111000
用原码表示一个数简单,直观,与真值之间转换方便 。
这种表示法,对乘法和除法的符号判别是很方便的,在作乘法或除法时,把数的符号位按位相加后,就得到结果的符号位 。
但这种表示法对加,减法来说运算比较复杂,不能用它直接对两个同号数相减或两个异号数相加 。
例如：十进制数,39” 与,﹣ 56” 的两个原码直接相加 。
因为 [+39]原 = 00100111 [﹣ 56]原 = 10111000
0 0 1 0 0 1 1 1
+ 1 0 1 1 1 0 0 0
1 1 0 1 1 1 1 1
其结果符号位为 1表示是负数,真值为,1011111”,
即等于十进制数,﹣ 95”,这显然是错误的 。
又如，十进制数,+39” 与,+56” 的两个原码直接相减：
0 0 1 0 0 1 1 1
﹣ 0 0 1 1 1 0 0 0
1 1 1 0 1 1 1 1
其机器数为,11101111”,真值为十进制数 ﹣ 111，
这显然也是不对的 。 因此为了计算机中方便进行加,
减法而引入了反码和补码表示法 。
★ 反码表示法反码：正数的反码和原码相同,负数的反码是对该数的原码除符号位外各位取反,即,0” 变,1”,
,1” 变,0” 。 数 X的反码记为 [X]反 。
例如：设机器字长 8位,二进制数 +1011011和
﹣ 1011011的反码分别表示为 01011011和 10100100。
零的反码 表示有两种,即,[ +0]反 = 00000000
[﹣ 0]反 = 11111111
可以验证,任何一个数的反码的反码即是原码本身 。
反码通常作为求补过程的中间形式 。
★ 补码表示法补码：正数的补码和原码相同,负数的补码是对该数的原码除符号位外各位取反,最末位加 1。 即：反码加 1。 数 X的补码记为 [X]补 。
例如：设机器字长 8位,二进制数 +1011011和
﹣ 1011011的补码分别表示为 01011011和 10100101。
零的补码 表示是唯一的 。
即,[+0]补 = [﹣ 0]补 = 00000000。
补码所能表示的数的范围也与二进制数的位数
（ 即机器字长 ） 有关,假设用八位二进制数表示时,
最高位为符号位,整数补码表示的范围为 ﹣ 128 ～
+127。 用十六位二进制数表示整数补码时的范围为
﹣ 32768 ～ +32767。
[例 1.20] 设字长为 8,求十进制数 +56与 ﹣ 56的补码 。
[+56]补 = [+56]原 = 00111000
[﹣ 56]原 = 10111000 [﹣ 56]补 = 11001000
可以验证，任何一个数的补码的补码即是原码本身 。
引入补码后,加减法都可以用加法来实现,即减法变为加法来运算,并且两数的补码之,和,等于两数,和,的补码 。
即,[ X+Y ]补 = [ X ]补 + [ Y ]补
[ X﹣ Y ]补 = [ X+（ ﹣ Y） ]补 = [ X ]补 + [﹣ Y ]补
[例 1.21] 计算十进制数,39” 与,56” 之差
（ 39） 10﹣ （ 56） 10 = [39 ]补 + [﹣ 56 ]补
[39 ]补 = 00100111 [﹣ 56 ]补 = 11001000
0 0 1 0 0 1 1 1
+ 1 1 0 0 1 0 0 0
1 1 1 0 1 1 1 1
其结果 11101111为补码,对它再进行一次求补运算就得到结果的原码表示形式,即,[11101111] 补 = 10010001
则 10010001=﹣ 0010001= （ ﹣ 17） 10,由于 39﹣ 56 =﹣ 17,所以结果正确 。
由此可见,计算机中加减法运算都可以统一化成补码的加法运算,其符号位也参与运算 。 目前计算机中的加减法运算基本上都采用补码进行运算 。 返回
1.3.3 定点数与浮点数在计算机中，参与运算的数据，既有整数，也有小数，那么在计算机内部小数点是如何表示的呢？
在计算机系统中，当处理的数值含有小数部分时，计算机并不是采用某个二进制位来表示小数点，
而是用隐含规定小数点的位置来表示。
按小数点的位置是否固定，一般分为定点数和浮点数，相应地数据具有定点表示和浮点表示两种形式。
1,定点数在机器中,小数点位置固定的数称为 定点数,定点数根据小数点隐含固定位置不同,又分为 定点小数和定点整数 。
（ 1） 定点小数定点小数是指小数点隐含固定在最高数值位的左边,符号位右边,参与运算的数是纯小数 。
记作,X0,X -1 X -2 …… X –m,定点小数在计算机中表示的格式如下：
数值位符号位 隐含小数点位置
X0 X-1 X-2 ··· X-m
在定点小数表示中，机器中运算的数都是绝对值小于 1的纯小数。但实际上，参加运算的数不可能都是这样的纯小数，对于绝对值大于 1的数，若直接使用定点小数格式将产生,溢出,,因此应根据实际需要取一个
,比例因子,,将原数据按比例缩小，以定点小数格式表示，得到结果后再按该比例扩大，得到实际的结果。
例如,有一数为 110.1001将其乘以 2–3，
得,110.1001× 2 –3 = 0.1101001
这样,该数就通过比例因子 2 –3缩小为小于 1的数 。
设机器字长为 n位,其中一位是符号位,其余 （ n-1）
位是有效数值位,那么这种定点小数所能表示的数值范围为,﹣ 0.1111…… 11 ～ 0.1111…… 11
n-1位 n-1位即,﹣ (1-2 ﹣ ( n-1 ) )≤ x ≤ 1-2 ﹣ ( n-1 )
若采用补码运算,由于零的补码唯一,规定用
1.0000…… 00 表示 ﹣ 1,所以 n位字长的定点小数所能表示的数值范围为,﹣ 1≤ x ≤ 1-2 ﹣ ( n-1 ) 。
（ 2） 定点整数定点整数是指小数点隐含固定在整个数值的最右端,符号位右边所有的位数表示的是一个纯整数 。 记作,X n X n -1 X n - 2 …… X 1 X 0,定点整数在计算机中表示的格式如下：
数值位符号位 隐含小数点位置在定点整数表示中,机器中运算的数都是绝对值大于 1的整数,并且都是绝对值在一定范围内的整数,，
对于绝对值超出该范围或参与运算的数是小数,我们就不能直接使用定点整数格式表示,需要根据实际情况适当地选取一个,比例因子,进行调整 。
Xn Xn-1 Xn-2 ··· X0
n位字长（其是一位是符号位）的定点整数（补码）
所能表示的数值范围为：
﹣ 2 n-1 ≤ X ≤ 2 n-1﹣ 1
定点表示法所能表示的数值范围非常有限,计算机做定点运算时,很容易溢出 。 溢出是计算结果超出字长表示范围的现象,它使计算机的运算发生错误 。
无论是定点小数或定点整数，由于小数点都固定在一个位置，所以机器在运算时不必对位，可以直接进行加减运算。实现这种运算方法的电路都比较简单，
但表示数的范围受到限制，缺乏灵活性，且为了防止
,溢出,需要选择合适的,比例因子,,对运算前后的数据按比例因子折算，使用也不方便。
2．浮点数浮点数是指小数点位置不固定,根据需要而浮动的数,它既有整数部分又有小数部分 。
定点数所能表示的范围非常有限,在许多场合下是不够用的,浮点数表示法可以扩大数据的表示范围 。
在计算机中通常把浮点数分成阶码和尾数两部分来表示,其中阶码一般用补码定点整数表示,阶码用于表示该数的小数点位置,尾数一般用补码或原码定点小数表示,尾数用于表示数据的有效位 。
一个数 N用浮点数表示可以写成,N = M× RE
其中 M表示 尾数,E表示 指数,R表示 基数 。 基数一般取 2,8,16。 一旦计算机定义好了基数值,就不能再改变了,因此,基数在浮点数中不用表示出来,是隐含的 。
浮点数的格式多种多样，在设计时，阶码和尾数占用的位数可以灵活地设定，由于阶码确定数的表示范围，而尾数确定数的精度，所以 当字长一定时，分配给阶码的位数越多，则表示数的范围越大，但分配给尾数的位数将减少，从而降低了表示数的精度，反之，分配阶码的位数减少，则数的表示范围将变小，
但尾数的位数增加，从而使精度提高。
例如，某计算机字长为 32位，用 4个字节表示浮点数，阶码部分为 8位补码定点整数，尾数部分为 24位补码定点小数，基数为 2，如下图所示。
31 30 24 23 22 0
阶码部分 尾数部分阶符 阶码 尾符 尾数为了提高精度通常其尾数的最高位必须是非零的有效位,这称为 浮点数的规格化 形式 。
由于其阶码为 8位,由阶码最大值为 2 7﹣ 1 =（ 127） 10,阶码最小值为 ﹣ 2 7 = （ ﹣ 128） 10,这样格式所表示数的范围为：
﹣ 1× 2 127 ～ （ 1﹣ 2﹣ 23 ） × 2 127
由此可见，浮点数的表示范围要比定点数大得多，但也不是无限的，当计算机中参与运算的数超出了浮点数的表示范围时称为 溢出 。如果一个数的阶码大于计算机所能表示的最大阶码，则称为 上溢 ；反之，若小于最小阶码，则称为 下溢 。上溢时计算机将停止运算，转溢出中断处理程序进行溢出处理；下溢时计算机将该数作为机器零来处理，即把该浮点数的阶码和尾数全置成零，但仍能进行运算。
采用浮点表示的数,在运算之前要进行对齐小数点的操作 （ 称为 对阶 ）,才能进行加减运算 。
在计算机中判断两数的小数点是否对齐,只要判断两数的阶码是否相等,若相等,则说明两小数点的位置已对齐 。 所以实现浮点运算操作比较麻烦,设备也比较复杂 。
返回
1.3.4 信息编码信息编码是指对输入到计算机中的各种非数值型数据用二进制数进行编码的方式 。 所谓编码就是用若干位二进制代码,选择一定的组合原则来表示组成信息的各种符号 。 根据不同的用途有各种各样的编码方案,常用的有 ASCII码,BCD码,汉字编码和数据校验码 。
1,ASCII码
ASCII码是美国标准信息交换码,已被国际标准化组织定为国际标准,是目前最普遍使用的字符编码 。 字符是计算机中使用最多的非数值型数据,是人与计算机进行通信,交互的重要媒介 。
ASCII码有 7位码和 8位码两种编码方案,常用的是 7位码方案 。 7位 ASCII码是用七位二进制数进行编码的,可共表示 2 7 =128个字符 。
ASCII码的每个字符用 7位二进制码表示，其排列次序为 b6b5b4 b3b2b1b0 。通过查 ASCII码表可以找到数字、运算符、标点符号以及控制字符等字符与 ASCII码之间的对应关系。
例如：小写字母,g‖的 ASCII码为 1100111；
ASCII码 0110011对应的字符是数字,3” 。
字符 0～ 9十个数字字符的 ASCII码的高 3位编码
（ b6b5b4） 为 011,低 4位为 0000～ 1001。 当去掉高 3位的值时,低 4位正好是 0～ 9的二进制数形式 。 这样编码既满足正常的排序关系,又有利于完成 ASCII码与二进制数之间的转换 。
字母 A～ Z的编码值为 65～ 90（ 1000001～
1011010）,小写英文字母 a～ z的编码值为 97～ 122
（ 1100001～ 1111010）,大,小写字母编码差别仅表现在 b5位的值为 0或 1,对应大,小写英文字母 ASCII码值十进制形式相差 32,因此大,小写英文字母之间的编码转换非常便利 。
为了提高信息传输的可靠性，字符 ASCII码在计算机内实际是用 八位二进制代码 表示的,一个字符占一个字节存储空间,一个字节中的 ASCII码表示如图 1.5
所示。
有效编码位奇偶校验位
ASCII码的最高位 b7作为奇偶校验位 。 所谓 奇偶校验,是指在代码传送过程中用来检验是否出现错误的一种方法,一般分奇校验和偶校验两种 。 例如,奇
（ 偶 ） 校验规则为：若 7位 ASCII码中,1” 的个数为奇
（ 偶 ） 数,则校验位置,0”,否则置,1” 。 注意,
校验位仅在信息传输时有用,在对 ASCII码进行处理时校验位被忽略 。
b7 b6 b5 b4 b3 b2 b1 b0
2,BCD码
BCD码又称 8421码，是一种二 —— 十进制的编码，
它使用 4位二进制数表示一位十进制数。由于 4位二进制数可表示 16种状态，只取前 10种状态 0000～ 1001来表示十进制数码 0～ 9，从左到右每位二进制数的权分别是 8,4,2,1，因此又叫 8421码。这种编码既具有二进制形式，又具有十进制的特点，它是逢,十,进位的。 BCD码十个不同的码分别是,0000,0001,0010、
0011,0100,0101,0110,0111,1000和 1001，这十个码分别代表十进制数码 0,1,2,3,4,5,6,7,8、
9。
BCD码很直观，可以很容易实现与十进制的转换。
对于多位十进制数，可以直接使用一位十进制数用四位二进制数来编码表示。
例如：十进制数 258对应的 BCD码 001001011000；
反之,BCD码 1001 1000 0111 0010 对应的十进制数是 9872。
3．汉字编码计算机在处理汉字信息时需要对汉字进行编码，
由于汉字数量大，字形复杂，同音字多，所以汉字在计算机中的输入、内部处理、存储和输出都使用不同的编码。如 汉字输入码、汉字机内码、汉字交换码、
汉字字形码以及汉字地址码 等汉字信息处理系统在处理汉字时，不同环节使用不同的编码，并根据不同的处理层次和不同的处理要求，要进行一系列的汉字代码转换。从汉字输入到最终的汉字输出的转换过程如下图所示。
汉字 汉字输入设备 输入管理模块 汉字库 输出设备汉字输入码 国标码汉字机内码汉字字形码
（ 1）汉字输入码汉字输入码是为方便人工通过输入设备 (如键盘 )输入汉字而设计的代码。
输入码种类繁多，广泛采用的输入码主要有,
区位码,智能 ABC码,五笔字型码、快速输入码 等。
（ 2）汉字交换码 (又称为国标码）
汉字交换码是用于汉字信息处理系统之间或通信系统之间进行信息交换的汉字代码。
我国的国标 GB2312-80制定了汉字交换码的标准。
该标准规定了信息交换用的 6763个汉字和 682个非汉字图形字符编码。根据汉字使用频率的高低、构词能力强弱、实际用途的大小划分为两级汉字，一级汉字 3755个，
二级汉字 3008个。一级汉字按拼音顺序排列，同音汉字按笔画顺序排列；二级汉字按部首顺序排列。
国标码字符集中的任何一个汉字或图形符号都用两个 7位的二进制数表示，在计算机中用两个字节表示，
每个字节的最高位为 0，剩余 7位为 GB2312-80二进制编码。
（ 3）汉字机内码汉字机内码是供计算机系统内部进行汉字存储、加工处理、传输统一使用的代码。也称汉字内码。
目前国内应用较广的一种为两字节机内码，俗称变形国标码。即：
这种格式的机内码是将国标码的两个字节的最高位分别置 1得到的。其最大优点是机内码表示简单，和交换码之间有明显的对应关系。
即：机内码 =国标码 +8080H
（ 4）汉字字形码汉字字形码是指汉字字库中存储的汉字字形的数字化信息码，它主要用于汉字输出 (打印、显示等 )时产生的汉字字形。
有两种显示字形的方法,矢量字符和点阵字符 。一个汉字系统所允许使用的全部汉字的汉字字形编码称为
,汉字库,,存放于系统的汉字字形库的存储器中。
1 ××××××× 1 ×××××××
在通用汉字系统中，广泛以点阵的方式形成汉字，
这时的汉字字形码是汉字点阵字形的代码，以点阵形式组成的汉字字形码，由于点阵规格的不同，又分为
16× 16,24× 24,32× 32,48× 48，甚至更多点阵的汉字库。
对于 16× 16的点阵字形，字形码为 32个字节
(16× 16÷ 8=32)每个汉字占 32B,那么 16× 16点阵汉字字库（包括一、二级汉字 6763个）共占 230KB左右。
（ 5）汉字地址码是指汉字字形码在汉字字库中存放位置的代码，即字形信息的地址 。
需要向输出设备输出汉字时，必须通过地址码，才能在汉字库中取到所需的字形码，最终在输出设备上形成可见的汉字字形。
由于汉字字形信息都是按一定顺序连续存放在存储器中。因此，汉字地址码一般是连续有序的，并且与汉字机内码间有着简单的换算关系。 返回
1.4 逻辑代数与逻辑电路基础
1.4.1 逻辑代数
1.4.2 逻辑电路和逻辑设计基础返回
1.4.1 逻辑代数计算机之所以具有逻辑处理能力，是由于计算机中使用了实现各种逻辑功能的电路，逻辑代数是进行逻辑电路设计的数学基础。
逻辑代数是 1847英国数学家乔治 ·布尔首先创立的，所以有时又叫 布尔代数 。
逻辑代数与普通代数有本质的区别，逻辑代数表示的不是数量大小之间的关系，而且逻辑关系，
逻辑代数中的 0和 1，不是数量的 0和 1，它只代表所要研究问题的两种可能性或两种稳定的物理状态。
它是分析和设计逻辑电路的基本数学工具。
1．逻辑变量和逻辑函数逻辑电路具有输入和输出间的逻辑关系，为了对输入和输出间的逻辑关系进行数学表达和演算，所以提出了 逻辑变量 和 逻辑函数 两个术语。
一个逻辑电路如下图所示,A,B为输入,F为输出，
输入和输出之间的逻辑关系为 F = f（ A,B）。
A F
B
A,B,F为逻辑变量
F=(A,B)为逻辑函数逻辑变量和逻辑函数的逻辑取值,只取两个值 0
和 1,通常称为逻辑 0和逻辑 1。
F＝ f(A,B)
2．逻辑运算逻辑变量之间的运算，称为逻辑运算。它包括三种基本运算,逻辑与、逻辑或和逻辑非 。通过这三种基本运算，可推导出其它逻辑运算，如 异或运算 等等。
（ 1） 逻辑与运算逻辑与又称为逻辑乘,通常用,·” 表示 。 它的运算规则为：
0 ·0 = 0 读成 0与 0等于 0
0 ·1 = 0 读成 0与 1等于 0
1 ·0 = 0 读成 1与 0等于 0
1 ·1 = 1 读成 1与 1等于 1
即：与运算表示，只有参加运算的逻辑变量都同时取值为 1时，其与运算结果才等于 1。
现在举例说明与运算的物理意义 。 如某学校用电,
只有当学校电源总闸和教学楼分闸同时接通,教室里才有电使用 。
（ 2）逻辑或运算逻辑或又称逻辑加,通常用符号,+” 来表示,或运算的运算规则如下：
0 + 0 = 0 读成 0或 0等于 0
0 + 1 = 1 读成 0或 1等于 1
1 + 0 = 1 读成 1或 0等于 1
1 + 1 = 1 读成 1或 1等于 1
可见,在给定的逻辑量中,只要有一个为 1,逻辑或的结果就为 1。
逻辑或的这种作用,在日常生活中经常可以碰到 。
例如,房间里有一盏电灯,为了使用方便,装了两个开关,这两个开关并联,显然,任何一个开关接通或两个开关同时接通电灯都会亮 。
注意：逻辑加与算术加法的运算规律不完全相同 。 要特别注意,1 + 1 = 1。
（ 3）逻辑非运算逻辑非运算在普通代数中是没有的 。 在逻辑量上方加横线,
,—” 表示非 。 其运算规则为：
0 = 1 读成非 0等于 1； 1 = 0 读成非 1等于 0
例如室内电灯,不是亮就是灭,只有这两种可能 。
(4） 异或运算异或运算通常用符号,,表示,它的运算规则为：
0 0 = 0 读成 0同 0异或,结果为 0
0 1 = 1 读成 0同 1异或,结果为 1
1 0 = 1 读成 1同 0异或,结果为 1
1 1 = 0 读成 1同 1异或,结果为 0
在给定的两个逻辑量中,只要两个逻辑量的值相同,异或运算的结果就为 0；只有相异时,结果才为 1。
注意,当两个多位的逻辑量进行逻辑运算时,只在对应位之间按上述规律进行逻辑运算,不同位之间没有任何关系,当然,也就不存在算术运算中的进位或借位问题 。
例如,1 1 0 1 1 0 0 0
+ 0 1 0 1 1 1 1 0
1 1 0 1 1 1 1 0
+
+
+
+
+
返回
1.4.2 逻辑电路和逻辑设计基础
1,逻辑电路基础能实现逻辑运算的电路称为 逻辑门电路 （简称门电路），常用的门电路有,与,门,,或,门、
,非,门,,与非,门,,或非,门,,异或,门等。由基本门电路可以按逻辑设计组合成计算机硬件的基本功能电路，如：触发器、寄存器、计数器、
译码器、半加器、全加器等等。
（ 1）,与,门实现,与,运算的单元电路叫,与,门。,与,
门的逻辑符号如图所示,A F=AB
B
其逻辑函数表达式为,F = A B。
例如 A=1,B=0,则 F = A B = 1·0 = 0
&
（ 2）,或,门实现,或,运算的单元电路叫,或,门 。,或,门的逻辑符号如图所示,A F=A+B
B
其逻辑函数表达式为,F = A + B。
例如 A=0,B=0,则 F=A+B=0+0=0。
（ 3） ―非,门实现,非,运算的单元电路叫,非,门,或叫反相器 。,非,门的逻辑符号如图所示：
A F=A
其逻辑函数表达式为,F= A。
例如 A=1,则 F = A = 0。
1
≥ 1
（ 4）,与非,门
―与非,门是由,与,门和,非,门两个单元电路组合而成的逻辑电路,用以实现,与非,运算 。 ―与非,
门的逻辑函数表达式为,F = A B,其逻辑结构和逻辑符号如下图所示 。
A AB F=AB A F=AB
B B
例如,若 A=1,B=0,则 F= A B = 1·0 = 1。
（ 3） ―或非,门
―或非,门是由,或,门和,非,门两个单元门电路组合而成,用以实现,或非,运算 。,或非,门逻辑表达式为,F=A+B,其逻辑结构和逻辑符号如下图所示 。
A A+B F=A+B A F=A+B
B B
例如,若 A=1,B=0,则 F= A+B = 1+0 = 0。
1& ≥ 1
1& ≥ 1
（ 5）,异或,门
,异或,门是由,非,门,,与,门和,或,门逻辑组合而成的逻辑电路 。 用以实现,异或,运算 。 具有两个输入端的,异或,门由两个,非,门,两个,与,
门和一个,或,门组合而成 。
其逻辑函数表达式为,F =Ａ Ｂ = A B+ＡＢ,异或门的逻辑符号如下图所示 。
A F＝ A B
B
对于给定的输入 A和 B,可以得出 F=A B。
例如：若 A=1,B=0，
则 F= A B= A B+A B = 1 ·0+ 1 ·0 = 1
+
＝ 1 +
+
+
2,逻辑组合电路的分析与设计逻辑组合电路的分析是指找出组合电路逻辑功能的过程,而设计则是指按照给定的具体逻辑问题,求出简单的逻辑电路的过程 。
（ 1） 逻辑电路分析方法分析逻辑组合电路的目的是找出其逻辑功能,既然逻辑组合电路的输出为一逻辑函数,那么用真值表来表示电路功能就最为直观了 。 由小规模集成电路构成的组合电路的分析,通常先根据给定的逻辑电路,
由输入到输出逐级写出逻辑函数表达式,然后对其进行化简,进而得到最简的逻辑表达式,有时也用真值表来直观表示电路的逻辑功能 。
（ 2）逻辑设计方法与步骤逻辑组合电路的设计是要按照给定的逻辑问题,设计出能实现其逻辑功能的电路 。
逻辑组合电路设计的步骤如下：
① 描述逻辑电路应具备的逻辑功能
② 构造真值表,构造能够实现逻辑电路的逻辑功能的真值表。要列真值表首先得对事件的因果关系进行分析，把事件的起因定为输入变量，把事件的结果作为输出逻辑函数；其次要对逻辑变量赋予输入量各种组合值，用逻辑 0和 1分别表示两种不同状态；再根据给定事件的因果关系给出逻辑函数的值。
③ 写逻辑函数表达式,即根据真值表写出相应的逻辑函数表达式并进行化简。
④ 根据简化的逻辑函数表达式画逻辑图。 返回
1.5 计算机的基本结构和工作原理
1.5.1 计算机硬件的基本结构
1.5.2 计算机的工作原理返回
1.5.1 计算机硬件的基本结构计算机是一种按着程序自动、高速地进行信息处理的系统，它由硬件和软件两大部分组成。计算机硬件的基本功能是接受计算机程序的控制来实现数据输入、运算、数据输出等一系列基本操作。
计算机硬件是计算机系统的重要组成部分，它是由电子的、磁性的、机械的器件按一定结构组成的设备，
是计算机的物质基础。各种类型的计算机硬件虽然有不同的实现形式，但都有其相同的基本结构和特点。
自从 1946年世界上第一台计算机诞生，计算机的体系结构不断地改进完善，其性能成倍地提高。虽然现在的计算机系统从性能指标、运算速度、工作方式、应用领域和价格等方面都有了长足的发展，但基本结构仍一直沿袭冯,诺依曼传统的框架。
美国数学家 冯,诺依曼 研制了 EDVAC计算机,他提出了计算机应由五个基本部分组成,即,运算器,控制器,
存储器,输入设备和输出设备,并描述了五大部分的功能及其相互关系,还提出了,采用二进制,和,存储程序,两个重要基本思想 。,采用二进制,就是计算机中的数据和指令均以二进制形式存储和处理；,存储程序,
就是将程序事先存入存储器中,使计算机在工作时能自动地从存储器中读取指令,分析后执行 。
目前大多数计算机都采用冯,诺依曼体系结构,都属于冯,诺依曼型计算机,其基本结构如下图所示 。
1,运算器 （ Arithmetic Unit）
运算器是计算机对数据进行加工处理的部件,主要包括 算术逻辑单元 （ ALU） 和寄存器 。
主要功能是在控制器的控制下执行程序中的指令,
完成各种 算术运算 和 逻辑运算,实现逻辑判断 。
ALU主要完成加,减,乘,除等四则运算以及与,
或,非,移位等逻辑运算,寄存器用来暂存参加运算的操作数或运算结果 。
运算器的主要技术指标是 运算速度,其单位是
MIPS（ 每秒百万条指令 ） 。
2,控制器 （ Control Unit）
控制器的作用是指挥整个计算机的各个部件按照指令的功能要求有条不紊地协调工作 。
控制器由 程序计数器 （ PC）,指令寄存器 （ IR）,
指令译码器 （ ID）,时序电路和微操作控制电路 组成,
程序计数器 用来对程序中的指令进行计数,其内容存放预将执行的指令在内存储器中的存储地址,使得控制器能依次读取指令 。
指令寄存器 在指令执行期间暂时保存正在执行的指令 。
指令译码器 用来对指令的操作码进行译码,产生的译码信号识别了该指令要进行的操作,并传送给微控制部件,以便产生相应的控制信号 。
时序控制电路 用来生成时序信号,以协调在指令执行周期内部件的工作 。
微操作控制电路 用来产生各种控制操作命令 。
控制器和运算器 合在一起称为 中央处理器,
即 CPU（ Central Processing Unit）,它是计算机的核心 。
3,存储器存储器是计算机的记忆和存储部件,用来存储数据和程序 。 按功能存储器一般可分为 内存储器和外存储器 两大类 。
（ 1） 内存储器 （ 简称内存 ）
内存储器也称为主存储器 （ 简称主存 ）,用来存放当前运行程序的指令和数据 。
目前内存由半导体存储器所组成,它直接与运算器和控制器相连接 。
内存特点,直接与 CPU交换信息,存取速度快,存储容量较小,价格相对外存高等 。
按存取方式内存可分为 随机存取存储器 (简称 RAM）
和只读存储器 （ 简称 ROM） 。 RAM是一种读写存储器,
通常用来存放正在执行的程序及所需的数据 。 RAM存取速度快,但它只是临时存储信息,即加电记忆信息,
一但断电 RAM中的信息立即丢失 。
ROM中的信息只能读出而不能重新写入和修改,
其信息是制作时用专门仪器写入的 。 计算机断电后,
其中的信息不丢失 。 ROM常用来存放一些专用固定的程序,数据和系统配置软件 。 如 磁盘引导程序,
自检程序,I/O驱动程序 等 。
内存由若干存储单元组成,为了区别不同的存储单元,一般从,0” 开始对存储单元进行连续编号,
每个单元都有一个唯一的号码,我们把它称为存储单元的 地址 。 每个存储单元能存放一个二进制数,
或一条由二进制编码表示的指令 。 如下图所示：
每个存储单元由若干位二进制位组成,,位,
（ bit） 是存储器的最小存储单位,一位可存储一位二进制数,8位二进制代码称为一个 字节 （ Byte,简称 B）,
字节是计算机中数据处理和存储容量的基本单位 。
1 K = 1024 B 1 GB= 1024 MB
1 MB= 1024 K 1 TB= 1024 GM
一个存储单元中存入的信息称为一个,字,,一个字所包含的二进制数的位数称为,字长,。
小型机或微型机的字长一般为 16位或 32位,计算机的字长越长,其精确度越高 。
存储器所包含的存储单元的总数称为 存储容量,现在微机内存容量大多在兆字节以上 。
（ 2） 外存储器 （ 简称外存 ）
内存由于技术及价格等原因,容量有限,不可能容纳所有的系统软件及各种用户程序,因此,计算机系统都配置外存 。 外存又称为 辅助存储器,它是内存的扩充外存特点,存储容量大,价格低,但存取速度较慢,
不能与 CPU直接交换信息等 。
一般用来存放需要长期保存的,暂时不用的程序,
数据和结果,需要时可成批地和内存进行信息交换 。
目前常用的外存有 磁盘 （ 软盘,硬盘 ）,光盘,磁带 等 。 外存容量一般用 KB,MB,GB,TB来表示 。
4,输入 /输出设备输入 /输出设备简称 I/O设备,它是外部与计算机交换信息的渠道,用户通过输入设备将程序,数据,操作命令等输入计算机,输出设备将计算机处理的结果显示或打印出来 。
常用的输入设备有,键盘,鼠标器,扫描仪,光笔,
数字化仪和语音输入装置等 。
常用的输出设备有 显示器,打印机,绘图仪和声音播放装置等 。 返回
1.5.2 计算机的工作原理计算机是一种能存储程序和数据，并能自动对各种数字化信息进行处理的机器。
计算机之所以能自动进行信息处理，是因为它能将程序及数据存储在内存中，并能自动执行程序，
我们称之为 存储程序原理 。要使计算机能自动工作，
必须根据要解决的问题编好程序，并将程序转换成由机器语言指令组成的形式存入内存中，然后以存储程序的首地址启动机器执行第一条指令。以后，
计算机便开始自动地 取指令，分析指令，执行指令所规定的操作，周而复始，直到将该程序执行完毕。
以计算 3＋ 5＝ 8为例具体说明计算机工作原理和过程。要想让计算机计算 3＋ 5，首先编写好计算程序，假设用 8086指令系统编写此程序，程序如下：
MOV AL,X
ADD AL,Y
MOV SUM,AL
HLT
说明,X,Y,SUM是变量，其存储情况如下：
系统把这 4条指令组成的程序段存放到存储器中。
当把首地址置入程序计数器 IP中,便可启动计算机执行该程序，其工作过程如下：
1,取第一条指令并执行
（ 1） 取指令并分析指令在取指令机器周期内,取出第一条指令,MOV
AL,X‖的机器码送入指令寄存器 IR中,该指令的操作码部分经指令译码器分析产生传送操作的信号,
,告诉,微操作控制部件本指令将要执行传送操作 。
与此同时,指令寄存器中的寻址方式和形式地址部分经地址形成器,计算出源操作数的物理地址
（ 1FD40H）,目标操作数是内部寄存器 AL。 在取指令机器周期内还更新 IP的内容,为执行下一条指令作好准备 。
（ 2） 执行指令微操作控制部件接收到来自指令译码器的译码信号,取数和传递,,则转入执行,存储器读机器周期,。在该周期内将完成从地址为 1FD40H的单元中取出 X的值是 3，并送入寄存器 AL中，第一条指令执行完毕，转入执行第二条指令。
2,取第二条指令并执行
（ 1） 取指令并分析指令从存储单元中取出第二条指令,ADD AL,Y‖的机器码并送入 IR中,IR中的操作码部分经指令译码器 ） 译码产生,ADD‖的信号有效,同时从寻址方式和形式地址指明的目标操作数是寄存器 AL,源操作数是存储器,由地址形成器计算出操作数的存储单元地址为 1FD41H。 此外为取下一条指令准备 IP地址 。
（ 2） 执行指令微操作控制部件接收到来自 ID的译码信号,相加寄存器操作数和存储器操作数,,在此机器周期内要完成存储器读操作和加法操作。先从 1FD41H存储单元中取出 Y的值 5送到运算器输入端，运算器执行加法运算 3+5，得出和 8送入 AL中。第二条指令执行完毕，故转入执行第三条指令。
第三条指令与第一条指令相似,完成的都是数据传送,但传送的方向不同,完成的是存储器写操作,即将 AL的内容传送 （ 写 ） 到 SUM的存储单元之中
（ 1FD42H号单元 ） 。
第四条指令是停机指令,可在取指令机器周期内完成 。
综上所述,我们对计算机的自动工作原理作如下概括,从计算机程序员的角度看,计算机自动工作过程是执行预先编写好的程序的过程,
而执行程序的过程就是周而复始地完成取指令,分析指令和执行指令的过程 。
返回
1.6 程序设计基础
1.6.1 程序设计的概念
1.6.2 程序设计语言
1.6.3 算法与数据结构返回
1.6.1 程序设计的概念程序设计是软件开发过程中的一个重要环节,程序设计是计算机科学与技术专业学生的基本功,这个专业的学生将来大部分要从事程序设计工作,因此,必须掌握程序设计的基本要领,才能成为优秀的设计人员 。
1,什么是程序设计利用计算机解决问题,首先要按照人们的意愿,
借助计算机语言,将解决问题的方法,公式,步骤等编写成程序,然后将程序输入到计算机中,由计算机执行这个程序,这个设计和书写程序的整个过程就是程序设计 。
程序设计 是根据给出的具体任务,编制一个能正确完成该任务的计算机程序 。
计算机程序 是有序指令的集合或者是具有一定结构的语句的集合 。 它能被计算机执行 。
为了能很好地完成给定的任务,程序设计过程大致需要三步,① 确定算法与数据结构 ；
② 用流程图表示程序的思想 ；
③ 用程序设计语言编制计算机程序 。
2,程序设计方法目前程序设计方法主要有结构化程序设计和面向对象程序设计 。
结构化程序设计 是由荷兰学者 Dijkstra在 20世纪 70年代提出的,其 主要思想是自顶向下,逐步求精,模块编程 。
结构化程序设计采用自顶向下逐步求精的设计方法就是先设计顶层,然后步步深入,逐层细分,
逐步求精,直到整个问题可用程序设计语言明确地描述出来为止 。
结构化程序设计采用单入口单出口的控制结构,
即：程序由 顺序,选择,循环 三种基本控制结构组成 。 任何一个算法都可以用这三种基本结构实现,
任何复杂的程序都可以分解为由三种基本结构组成 。
3种基本结构如下图所示 。
结构化程序设计使得程序结构清晰,可读性好,
在出现问题时,便于查错,易于修改,提高了程序设计的质量 。 但随着软件规模和复杂性的增长,这种方法越来越不能适应庞大,复杂软件的开发,暴露出许多缺点,面向对象程序设计方法正是在这种背景下诞生的 。
面向对象的程序设计 （ Object Oriented
Programming,缩写为 OOP） 是一种先进的程序设计方法,OOP实际上是围绕着各类事物进行程序设计的,
OOP本质是把数据和处理数据的过程 （ 函数 ） 当成一个整体 — 对象 。 一旦在程序中建立了一个对象,
其他程序员可以在其他的程序中使用这个对象,完全不必重新编制繁琐复杂的代码 。 对象的重复使用可以大大地节省开发时间,切实地提高软件的开发效率 。
面向对象具有三个重要特性,即 封装性,继承性和 多态性 。
封装性,把数据结构同操作数据的过程组合在一起,把它们封装在一个类中 。
这种封装性能保护类中的数据与过程的安全,防止外界干扰和误用 。
继承性,这种特性很符合人的思维方式,通过继承,一个对象可以获得另一个对象的属性,并可加入一些属于自己的特性 。
多态性,就是一个接口,多种方式 。
多态性的优点在于通过提供一个相同的接口,可以通过不同的动作来访问,从而降低了问题的复杂度 。
面向对象程序设计并没有摒弃结构化程序设计方法,相反,它是在充分吸收结构化程序设计优点的基础上,引进了对象,类等新的,强有力的概念,从而开创了程序设计工作的新天地 。
2,程序设计风格程序设计时程序应 结构清晰,合理,编写出来的程序不仅可在机器上正确执行,还要便于程序的调试和维护,让别人能看懂 。
学习程序设计过程中,必须养成良好的程序设计风格 。 好的程序设计风格有助于提高程序的正确性,可读性,可维护性,可用性 。
建议从以下方面，逐步形成良好程序设计风格,
（ 1）编码格式和编码约定在整个程序中应保持一致；
（ 2）程序中应给出必要的注释。
（ 3）对变量、标识等的命名，采用,匈牙利命名法,。（ 4）程序书写采用缩进格式，突出程序的层次结构。 （ 5）每一行只写一条语句，使用括号间隔表达式或语句的组成部分。
（ 6）使用结构化、面向对象的编程技术，提高程序可重用性、可扩充性 。
（ 7）提高程序健壮性，预防用户的操作错误返回
1.6.2 程序设计语言编写计算机程序所用的语言即 程序设计语言,是人与计算机之间交换信息的工具 。 程序设计语言的发展从面向过程,到面向对象,进一步发展成为面向组件,经历了非常曲折的发展过程 。 总的来说可以分成 机器语言,
汇编语言,高级语言,面向对象语言 等等 。
1,机器语言机器语言是计算机第一代语言,它由 0,1代码构组的机器指令集合组成 。 是最底层,能直接被机器所接受的语言 。
用机器语言编写程序,计算机硬件可直接识别,执行速度比较快,基本上充分发挥了计算机的速度性能 。
不同的 CPU,其机器语言也不同 。 针对一种计算机所编写的机器语言程序,不能在另一种计算机上运行 。
机器语言不容易记忆,程序编写难度大,调试修改繁琐,且不易移植,但执行速度最快,它是一种面向机器的程序设计语言 。
2,汇编语言汇编语言是第二代程序设计语言 。
汇编语言是用助记符代替操作码,用地址符号代替地址码,使机器语言,符号化,,所以也称汇编语言是符号语言 。
汇编语言与特定类型的机器相对应,也是一种面向机器的语言 。 事实上,每一个计算机厂家都为自己的机器制定了一套机器码的,助记符,,即汇编语言指令系统 。
汇编语言与机器语言是一,一对应的,因此,对于不同的计算机,针对同一问题所编写的汇编语言源程序是互不通用的 。 用汇编语言编写的程序执行效率比较高,但通用性与可移植性仍然比较差 。
总的来说,汇编语言比机器语言前进了一步 。 但是,计算机不能直接识别用汇编语言编写的程序,必须由一种专门翻译程序将汇编语言程序翻译成机器语言程序,计算机才能执行 。
3,高级语言机器语言和汇编语言都是面向机器的语言,称为低级语言 。 它们对机器依赖性很大,用它们开发的程序通用性差,且要求程序员必须熟悉和了解计算机硬件的每一个细节,普通计算机用户很难胜任编程工作 。
随着计算机技术的发展及计算机应用领域的不断扩大,计算机用户的队伍不断壮大,而且这个队伍中绝大部分不是计算机专业人员 。 为此,从 20世纪 50年代中期开始,逐步发展了面向问题的程序设计语言,
称为 高级语言 。 高级语言与具体的计算机硬件无关,
其表达方式接近于被描述的问题,接近于自然语言和数学语言,易被人们接受和掌握 。
高级语言的显著特点是独立于具体的计算机硬件,
通用性和可移植性好 。
目前,计算机高级语言已有上百种之多,得到广泛应用的也有十几种,并且几乎每一种高级语言都有其最适用的领域 。
高级语言发展经历了二个阶段 。
第一阶段高级语言是 过程化 的语言,如,BASIC
语言,C语言,FORTRAN语言,COBOL语言,PASCAL语言,LISP语言等都是过程化的语言 。 过程化语言编程时需要一步一步地安排好机器的执行顺序,要告诉机器怎么做 。
第二个阶段的高级语言是 非过程化 语言 。 非过程化语言只需告诉机器做什么就可以了,由机器自己生成和安排执行的步骤 。 如 FOXBASE,FOXPRO都是非过程化的语言 。
用任一种高级语言编写的源程序都不能被计算机直接执行,在执行之前,必须由编译程序或解释程序翻译成机器能接受的目标代码 。 与低级语言相比,用高级语言编写的程序其执行的时间和空间效率要差 。
取其所长,上述三类语言可用在不同的场合,一般科学计算,数据处理采用高级语言比较合适,而实时控制因为速度要求高,往往采用汇编语言 。
4,面向对象程序设计语言 (OOPL)
OOPL是建立在用对象编程的方法基础上的,是当前程序设计采用最多的一种语言 。
OOPL具有封装性,继承性和多态性 。
OOPL有两大类：一类是纯粹的面向对象语言,在纯粹的面向对象语言中,几乎所有的语言成分都是
,对象,,如,Smalltalk,Java等,这类语强调开发快速原型的能力；另一类是混合型面向对象语言,如：
C++,Object Pascal,这类语言是在传统的过程化语言基础上增加面向对象机制,它所强调的是运行效率 。
成熟的面向对象语言通常都提供丰富的类库和强有力的开发环境 。
5,组件技术所谓组件可理解为自包含的,可编程的,可重用的,与语言无关的代码片段,可以作为整体很容易地插入到应用程序中 。 组件技术是计算机软件发展的最新结果,也是非常有效的软件构造方法 。 返回
1.6.3 算法与数据结构大型软件系统的开发,应运用软件工程的思想和方法进行,而解决较简单的实际问题时,需要遵循以下几个步骤：
★ 分析问题,确定算法将要解决的问题进行分析,提取操作的对象,
并找出操作对象之间的关系 。 在此基础上确定具体解决问题的方法和步骤,设计出一种优化算法 。
★ 选择程序设计语言进行程序设计选择适当的程序设计语言,将算法转换成程序代码 。 人们常把程序定义为：
程序 =算法 +数据结构 +程序设计语言 +工具和环境
★ 程序测试设计一组足够的测试数据,使用这组测试数据来运行程序 。
分析问题,确定算法在整个解决问题过程中是非常重要的一步,决不可忽视 。
1,算法
（ 1） 什么是算法算法是解题的步骤,是一组有穷的规则,它们规定了解决某一特定问题的一系列运算,是对解题方案的准确与完整的描述 。
制定一个算法,一般要经过设计算法,描述算法,
分析算法和验证算法等阶段 。
（ 2） 算法的特性一个算法具有下列五个重要的特性：
确定性,有穷性,可行性,输入和输出 。
（ 3） 算法的描述算法的描述方法可以归纳为以下几种,
① 自然语言 。
② 图形,如 N-S图,流程图,图的描述与算法语言的描述对应 。
③ 算法语言,即：程序设计语言,伪代码 。
（ 4） 衡量算法优劣的方法解决某一个实际问题可能有许多不同的算法,究竟如何来衡量这些算法的优劣？ 并从中选出较好的算法呢？
选用的算法首先应该是,正确的,。 此外,主要考虑如下 3点：
① 执行算法所耗费的时间,即时间特性 。
② 执行算法所耗费的存储空间,即空间特性 。
③ 算法应易于理解,易于编码,易于调试 。
当然,我们希望选用一个所占存储空间小,运算时间短,其它性能也好的算法 。 然而,实际上很难做到十全十美 。 原因是上述要求有时相互抵触,要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间 。 因此我们只能根据具体情况有所侧重 。
2,数据结构计算机发展初期,人们使用计算机主要是处理数值计算问题 。 由于数值计算的特点是数据元素之间的关系简单,但计算复杂,所以程序设计者的主要精力是集中于程序设计技巧上,而无须重视数据结构 。 随着计算机应用领域的扩大和软,硬件的发展,计算机被更多地用于非数值处理,据统计,用计算机处理非数值性问题占了 90% 以上,非数值处理的特点是数据元素间的关系复杂,而计算相对简单 。 因此解决此类问题的关键已不再是分析数学和计算方法,而是要设计出合适的数据结构,才能有效地解决问题 。
利用计算机解决实际问题,不仅需要研究算法与程序结构,同时也需要研究程序的加工对象 ——数据的结构 。 数据结构直接影响算法的选择和程序的效率 。
程序设计的实质是对实际问题选择一种好的数据结构,
加之设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构 。
（ 1） 数据结构的基本概念数据,是指描述客观事物的数值,字符以及所有能输入到计算机并被计算机程序处理的符号的集合 。
数据的含义极为广泛,数值,字符,图形,图像,
声音等都是数据 。
数据元素,是数据集合中的一个个体,它是数据的基本单位 。
数据结构,是指相互之间存在某种关系的数据元素的集合 。 它一般包括以下三方面的内容：数据的逻辑结构,数据的存储结构和数据的操作实现算法 。
逻辑结构,是指数据元素之间的逻辑关系,它分为线性结构和非线性结构 。 线性表是典型的线性结构,而树形结构是典型的非线性结构 。
存储结构,是指数据元素及其之间的关系在计算机存储器中的表示方法 。 数据的存储结构主要有顺序存储结构和链式存储结构两种基本类型 。
数据的操作,是指对对数据实施的操作 。
从学科的角度来看,数据结构是计算机科学技术的一个分支,它主要研究数据的逻辑结构 (即数据元素之间的逻辑关系 )和物理结构 (即数据在计算机中是如何表示的 )以及它们之间的关系,并对这种结构定义相应的操作,设计出实现这些操作的算法 。
从课程的角度来看,数据结构是计算机科学与技术专业的一门重要的专业基础课,是教学计划中的核心课程之一 。 其中将系统地介绍线性表,栈,队列,串,
数组和广义表,树,图等基本类型的数据结构及其相应操作的实现算法,并将详细讨论在程序设计中经常会遇到的查找和排序技术 。 这些知识和技术不仅是一般非数值计算程序设计的基础,而且也是设计和实现如编译程序,操作系统,数据库管理系统等系统软件以及大型应用程序的重要基础 。
（ 2） 几种典型的数据结构简介
★ 线性表 （ Linear_List）
线性表是最简单且最常用的一种数据结构 。
① 线性表的定义,线性表是由 n (n≥ 0)个数据元素
（ 结点 ） a 1,a 2,…… a n 组成的有限序列 。 其中数据元素可以是一个数,一个符号或一个记录等信息,
不同的线性表中的数据元素可以是各种各样的,但同一线性表中的元素必定是同一数据对象 。
如：英文字母表 （ A,B,C,……………,Z） 是一个线性表 。 又如,学生情况表,如下表所示,是一种较为复杂的线性表 。
学生情况表
② 线性表的基本操作,线性表是一种相当灵活的数据结构,对线性表的数据元素不仅可以进行访问,还可以进行插入和删除等操作 。
常见的线性表基本操作有：
(a) InitList(L),构造空的线性表 L,即表的初始化 。
(b) ListLength(L),求线性表 L中的数据元素的个数,
(c) GetNode(L,i ),取线性表 L中的第 i个结点,要求
1≤ i≤ListLength(L) 。
(d) LocateNode(L,x ),在 L中查找 x结点,并返回该结点在 L中的位置 。 若 L中有多个结点的值和 x相同,则返回首次找到的结点位置；若 L
中没有 x结点,则返回一个特殊值表示查找失败 。
(e) InsertList(L,x,i ),在线性表 L的第 i个位置前插入新结点 x。 如果线性表 L原有 n个数据元素,则执行此操作后,其数据元素个数将变为 n+1。
(f) DeleteList(L,i ),删除线性表 L的第 i个结点,
如果线性表 L原有 n个数据元素,则执行此操作后,其数据元素个数将变为 n-1。
③ 线性表的存储结构,将一个线性表存储到计算机中可以采用许多不同的方法,常采用的方法有 顺序存储结构和链式存储结构 。
线性表的顺序存储 是把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里 。 用这种方法存储的线性表称为顺序表 。
设线性表的每个元素占用 C个存储单元,第一个单元的存储地址是该元素的存储地址,设表中开始第一个元素 a 1的存储地址是 Loc(a 1),那么线性表中的第 i
个数据元素 a i 的存储地址为：
Loc(a i)=Loc(a 1) + (i-1) * C 1≤i≤n
确定了存储线性表的起始地位置,线性表中任一数据元素都可随机存取,所以说 线性表的顺序存储结构是一种随机存取的存储结构 。
高级语言中数组类型也有随机存取的特性,因此通常采用一维数组来描述顺序表 。
线性表 顺序存储结构的优点,可以随机存取表中任一结点,实现对线性表的某些操作比较简单,如：计算线性表的长度,存取线性表中的任意一个结点,查找线性表中某一元素等等 。
缺点 是在实现线性表的 插入和删除 操作时,则需要移动大量数据元素而花费较多的时间 。
链式存储结构 是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续,甚至是零散分布在内存中的任何位置上,因此为了表示每个数据元素 a i与其直接后继数据元素 a i+1 之间的逻辑关系,除了存储其自身的信息外,还需存储指示直接后继的信息 。
这样,线性表每个数据元素的存储表示包括两个域：存储数据元素信息的域称为 数据域 ；存储直接后继存储位置的域称为 指针域 。 有 n个元素的线性表每个数据元素之间通过指针连接成为一个链式的结构,因此又称其为 链表 。
链表的优点,插入,删除操作简单,只须修改相应的指针域 。
缺点,不能随机存取线性表中数据元素,只能顺序存取,所以实现查找操作比较繁琐 。
★ 栈 （ Stack）
栈是特殊的线性表,它的逻辑结构和线性表相同,
只是其基本操作较线性表有更多的限制,故又称是受限的线性表 。 栈被广泛应用于各种程序设计中 。
① 栈的定义,栈是限制仅在表的一端 （ 即表尾 ）
进行插入和删除操作的线性表,通常称插入,删除这一端为 栈顶 （ Top）,另一端称为 栈底 （ Bottom） 。
当表中没有元素时称为 空栈 。 栈的示意图如下：
② 栈的基本操作：
(a) InitStack(S),构造一个空栈 S。
(b) StackEmpty(S),判栈空 。 若 S为空栈,则返回
TRUE,否则返回 FALSE。
(c) StackFull(S),判栈满 。 若 S为满栈,则返回
TRUE,否则返回 FALSE。
(d) Push(S,x),进栈 。 若栈 S不满,则将元素
x插入 S的栈顶 。
(e) Pop(S),退栈 。 若栈 S非空,则将 S的栈顶元素删去,并返回该元素 。
③ 栈的存储结构,栈也有两种存储表示方法,即顺序栈和链栈,栈一般采用顺序存储结构 。
顺序栈是使用一个连续的存储区域来存放栈元素,
并设置一个栈项指针 TOP,用来指示栈顶位置,进栈和退栈只能在栈顶进行 。
★ 树 （ Tree）
树形结构是一类非常重要的非线性结构,它用于描述数据元素之间的层次关系,类似于自然界中的树 。
树结构在客观世界中是大量存在的,例如族谱,行政组织机构都可用树形象地表示 。 在计算机领域中,树形结构的应用也非常广泛,磁盘文件的目录结构就是一个典型的例子,在编译程序中,用树来表示源程序的语法结构,在分析算法的行为时,可用树来描述其执行过程 。 树和二叉树是常用的树形结构,由于用二叉树表示对于树的存储和操作有很大意义,可以把对于树的许多处理转换到对应的二叉树中去做,因此,
先介绍树的基本概念,然后重点讨论二叉树的有关概念,存储结构和常用操作 。
① 树的基本概念：
树：是 n（ n≥ 0） 个结点的有限集 T,T为空时称为空树,T非空时,有且仅有一个特定的结点称为根结点,其余结点可被分成 m（ m≥ 0） 个互不相交的子集 T1,T2,…… Tm,其中每个子集本身又是一棵树,
并称其为根结点的子树 。
如图是一棵具有 12个结点的树 。
树结构中的基本术语：
孩子结点,双亲结点,树中某结点的各子树的根称为该结点的孩子；相应地该结点称为其孩子的双亲 。
结点的度,一个结点所拥有的子树的个数称为该结点的度 。
叶子结点,分支结点,度为 0的结点称为叶结点,
度不为 0的结点称分支结点 。
树的深度,树的叶结点的最大层数称为树的深度 。
② 二叉树的基本概念：
二叉树 （ Binary Tree）,是 n (n≥ 0) 个结点的有限集,它或是空集 （ n=0）,或是由一个根结点及两棵互不相交的,分别称为根的左子树和右子树组成 。
如下图是一棵二叉树 。
需要说明的是,尽管树和二叉树的概念之间有许多关系,但它们是两个概念 。
二叉树不是树的特殊情况,树和二叉树之间最主要的区别是,二叉树是有序的,二叉树的结点的子树要区分左子树和右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 。
完全二叉树和满二叉树是两种特殊形态的二叉树 。
满二叉树,在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶结点都在同一层上,这样的一棵二叉树称为满二叉树 。
完全二叉树,一棵深度为 K的有 n 个结点的二叉树,
对树中的结点按从上至下,从左到右的顺序进行编号,
如果编号为 i(1≤i≤n) 的结点与满二叉树中编号为 i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树 。 显然,一棵满二叉树必定是一棵完全二叉树 。
③ 二叉树的存储结构二叉树的存储结构有顺序存储和链式存储 。 顺序存储结构,就是用一组连续的存储单元存放二叉树中的结点,完全二叉树由于其结构的特点,通常采用顺序方式存储；链式存储结构是用链建立二叉树中结点之间的关系,通常采用的链式存储结构为 二叉链表 。
所谓二叉链表,是将二叉树中的结点设置为如下的结构体类型：
其中,data表示保存结点本身信息的信息域,lchild
和 rchild分别为指向结点的左孩子和右孩子的指针域 。
④ 二叉树的基本操作 ——遍历 （ Traversal）
所谓遍历是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问 。 但访问结点所做的操作依赖于具体的应用问题 。
根据二叉树的定义知道,一棵二叉树可看做由三部分组成：根结点,左子树和右子树 。 若又规定按先左子树后右子树的顺序进行遍历,则遍历有三种方式：
DLR,LDR和 LRD,它们分别被称为前序遍历,中序遍历和后序遍历 。 另外还有一种按二叉树中结点由上至下,
由左至右的顺序进行遍历的方法,叫层次遍历 。
前序遍历的方法为：
若二叉树为空,遍历结束,否则,① 访问根结点；
② 前序遍历根结点的左子树； ③ 前序遍历根结点的右子树 。
中序遍历的方法为：
若二叉树为空,遍历结束,否则,① 中序遍历根结点的左子树； ② 访问根结点； ③ 中序遍历根结点的右子树 。
后序遍历的方法为：
若二叉树为空,遍历结束,否则,① 后序遍历根结点的左子树； ② 后序遍历根结点的右子树； ③ 访问根结点 。
本章结束返回
系统组成,基本结构和工作原理,计算机中数据的表示方法 ——数制与码制,程序设计基础知识等内容 。 通过本章的学习,主要掌握以下内容：
计算机的基本概念,特点,用途及发展
数制及数制间的相互转换方法
计算机中数的表示方法,ASCII码和汉字编码
计算机基本结构和工作原理
程序设计语言,程序设计方法
算法与数据结构第 1章 计算机科学技术的基础知识
1.1 计算机概述
1.2 计算机科学与技术专业的知识结构
1.3 计算机的运算基础
1.4 逻辑代数与逻辑电路基础
1.5 计算机的基本结构和工作原理
1.6 程序设计基础
1.1 计算机概述
1.1.1 计算机的基本概念
1.1.2 计算机系统的组成
1.1.3 计算机的发展
1.1.4 计算机的分类
1.1.5 计算机的特点
1.1.6 计算机的用途 返回
1.1.1 计算机的基本概念
,计算机,顾名思义是一种计算的机器，它是由一系列电子器件组成 —英语名称为 Computer。
计算机可以对 数字、文字、颜色、声音、图形、图像 等各种形式的数据进行加工处理。
计算机具有各种计算的能力。 当用计算机进行数据处理时，首先把要解决的实际问题，用计算机语言编写成计算机程序，然后将待处理的数据和程序输入到计算机中，计算机按程序的要求，一步一步地进行各种运算，
直到存入的整个程序执行完毕为止。
计算机具有各种计算的能力。 在数据处理过程中，
计算机不仅能进行加、减、乘、除等算术运算，而且还能进行逻辑运算并对运算结果进行判断，从而决定以后执行什么操作。
计算机具有信息处理能力 。 在当今的信息社会里,各行各业,随时随处产生大量的信息,人们为了高效地获取,传送,检索信息及从信息中产生各种报表数据,必须将信息在计算机的控制下进行有效的组织和管理 。
综上所述,可以给计算机下一个定义：
计算机是一种能按照事先存储的程序,自动,高速地进行大量数值计算和各种信息处理的现代化智能电子设备 。
返回
1.1.2 计算机系统的组成计算机系统由计算机硬件和计算机软件两大部分组成。
硬件（ Computer hardware)
主要由 CPU,存储器、输入输出控制系统和各种输入输出设备等功能部件组成。
软件（ Computer software)
它包括计算机运行所需的各种程序、
数据及相关文档资料。
裸机脱离软件的计算机硬件称,裸机,。
硬件是软件赖以运行的物质基础，软件是人与硬件之间的界面。
操作员（人）
应用软件支撑软件系 编译程序统 ……..
软件 操作系统计算机硬件计算机软件计算机系统的层次结构返回
1.1.3 计算机的发展自 1946年 美国宾西法尼亚大学研制出世界上第一台电子数字计算机 ENIAC（ 电子数字积分计算机的英文缩写）至今，短短五十多年的时间内，计算机系统和计算机应用得到了飞速发展。元件制作工艺水平的不断提高是计算机发展的物质基础，因此以 计算机元器件 的变革作为标志，计算机的发展已经历了四代，并正在研制第五代 。
1,第一代计算机 —电子管计算机 （ 1946～ 1957年 ）
其主要特征是采用电子管作为主要元器件。 ENIA。
2．第二代计算机 —晶体管计算机（ 1958～ 1964年）
其主要特征是由电子管改为晶体管。
3．第三代计算机 —集成电路计算机（ 1965～ 1971年）
其主要特征是用半导体中小规模集成电路代替分立元件的晶体管。
4,第四代计算机 —大规模与超大规模集成电路计算机
（ 1972年至今 ）
其主要特征是以大规模和超大规模集成电路为计算机的主要功能部件。
5,新一代计算机 —智能计算机新一代计算机正在研制之中,主要特征是人工智能,
它将具有自然语言理解能力,模式识别能力和推理判断能力等,突破冯,诺依曼体系结构的限制,提出非冯,
诺依曼的体系结构,如神经网络计算机 。
6,微型计算机的发展概况微型计算机 （ 简称微机 ） 诞生于 1971年,属于第四代计算机,微型计算机的诞生和迅速普及是计算机发展史中最重大的事件 。 微型计算机具有体积小,重量轻,功耗小,可靠性高,使用环境要求不严格,价格低廉,易于成批生产等特点 。
世界上第一台微机是由美国 Intel公司年轻的工程师马西安,霍夫 （ M.E.Hoff） 于 1971年研制成功的 。
他大胆地提出了一个设想,把计算机的全部电路做在四个芯片上,即一片 4位微处理器 Intel4004,一片 320位的随机存取存储器,一片 256字节的只读存储器和一片 10位的寄存器,它们通过总线连接起来就组成了世界第一台 4位微型计算机 —MCS-4。
微型计算机的核心部件是 微处理器 （ MPU）,根据微处理器集成规模和功能,形成了微型计算机的不同发展阶段 。
1．第一代微型计算机
1972年 Intel公司研制成功 8位微处理器 Intel8008,它主要采用工艺简单、速度较低的 P沟道 MOS电路。由它装备起来的计算机 MCS-8称为第一代微型计算机。
2．第二代微型计算机第二代微处理器是在 1973年研制成功的，主要采用速度较快的 N沟道 MOS技术的 8位微处理器。具有代表性的产品有 Intel公司的 Intel8085,Motorola公司的 M6800,Zilog公司的 Z80等。由它装备起来的计算机称为第二代微型计算机。
3．第三代微型计算机第三代微处理器是在 1978年研制成功的，主要采用 H-MOS新工艺的 16位微处理器。其典型产品是 Intel公司的 Intel8086。 由第三代微处理器装备起来的计算机称为第三代微型计算机。
4．第四代微型计算机从 1985年起采用超大规模集成电路的 32位微处理器，标志着第四代微处理器的诞生。典型产品有 Intel公司的 Intel80386。
由第四代微处理器装备起来的计算机称为第四代微型计算机。 返回
1.1.4 计算机 的分类计算机科学技术的发展日新月异，它已成为一个庞大的家族。
计算机的种类很多，从不同角度对计算机有不同的分类方法。
1．按计算机处理数据的方式分类可以分为数字计算机,模拟计算机和数字模拟混合计算机三类。
2．按计算机的用途分类可分为通用计算机和专用计算机两类。
3．按计算机的规模和处理能力分类规模和处理能力主要是指计算机的体积,字长,运算速度,
存储容量,外设的配置,输入输出能力等主要技术指标,按其分类大体可分为巨型计算机,大 /中型计算机,小型计算机,微型计算机,工作站,服务器以及网络计算机等种类 。
总之,目前微型计算机与工作站,小型计算机乃至中大型计算机之间的界限已经越来越模糊 。 无论按哪一种方法分类,各类计算机之间的主要区别是运算速度,
存储容量及机器体积等 。
返回
1.1.5 计算机 的特点计算机作为一种通用的信息处理工具,它具有极高的处理速度,很强的存储能力,精确的计算能力和逻辑判断能力 。 虽然各类计算机在性能上,用途上,规模结构上有所不同,但它们都具备以下一些特点 。
1,运算速度快由于计算机是采用高速电子器件组成,因此能以极高的速度工作 。
目前的巨型机运算速度已达到每秒几百亿次运算,微机也可达到每秒亿次以上 。
2,计算精度高由于计算机采用二进制表示数据,因此它的精度主要取决于表示数据的位数,即机器字长 。 字长越长,其精度越高 。
3,具有记忆能力存储器是计算机的记忆部件,计算机把大量的数据和程序存入存储器,并把处理或计算的结果保存在存储器中 。 计算机存储器有内存和外存之分,目前,微型计算机的内存容量一般可以达到 512MB且可以进一步扩展,外存 （ 如硬盘 ） 容量可以达到十 GB甚至上百 GB。
4,具有逻辑判断能力计算机不仅具有运算能力,还可以进行各种逻辑判断,并根据判断的结果自动决定下一步应该执行的指令 。
5,具有自动控制能力计算机内可以存储程序,计算机可以在人们事先编制好的程序的控制 下自动地完成各种操作,无需人工干预 。 返回
1.1.6 计算机 的用途计算机在科学技术,国民经济,社会生活等各个方面都得到了广泛的应用 。 按照应用的领域计算机的用途归纳起来可分为以下几个方面 。
1,科学计算科学计算又称为数值计算,是指使用计算机来完成科学研究和工程技术中提出的数学问题计算 。 如人造卫星轨迹的计算 。
2,数据处理数据处理是指用计算机对数据进行输入,分类,加工,统计,排序,
传输,检索,存储,制表等操作,形成有用的信息 。 据统计,全世界计算机用于数据处理的工作量占全部计算机应用的 80%以上 。
3,过程控制过程控制又称为实时控制,自动控制,所谓过程控制是指用计算机及时采集数据,将数据检测,处理后,按最佳值迅速对控制对象进行自动控制或自动调节 。 目前广泛应用于钢铁工业,石油工业,医药工业等 。
4,计算机辅助系统计算机辅助系统主要包括计算机辅助设计,计算机辅助制造,计算机辅助教育等 。
5,人工智能人工智能是用计算机模拟或部分模拟人类的智能,一般是指模拟人脑进行演绎推理和采取决策的思维过程 。
6,电子商务电子商务是指通过计算机和网络进行商务活动 。 返回
1.2 计算机科学与技术专业的知识结构计算机科学技术学科经历半个多世纪的迅猛发展,已成为比较完备的学科体系,衍生了许多相对独立的方向和分支 。 从学科体系的角度,可将计算机科学与技术学科的内容划分为三个层面：
应用层,专业基础层和专业基础的理论基础层 。
1,应用层应用层是与计算机应用领域或用户最接近的层面,它包括人工智能应用与系统,信息,管理与决策系统,计算可视化,科学计算等计算机应用的各个方向 。
2,专业基础层专业基础层为应用层提供理论和方法指导及环境 。 它包括软件开发方法学,计算机网络与通信技术,程序设计科学,计算机体系结构,电子计算机系统基础 。
3,专业基础的理论基础层专业基础的理论基础层是为计算机专业基础提供理论指导或依据的更低层的理论层面,包含了计算机科学的最核心和最基础的理论 。 它主要包括计算理论和高等逻辑等内容 。 返回
1.3 计算机的运算基础基础
1.3.1 数制
1.3.2 码制
1.3.3 定点数与浮点数
1.3.4 信息编码返回
1.3.1 数制关于数，大家并不陌生，数是各种运算的基础。计算机处理的对象就是数据，在计算机中数值，字符、声音、图形、图像等都是数据，那么数据在计算机中是如何表示的？有哪些要求？
1．数制的概念按进位的原则进行计数叫进位计数制，简称 数制 。
人们熟悉十进制数，但除以之外，还有十六进制、十二进制等等。
基数,所谓某数制的基数是指该数制中允许选用的基本数码的个数。如十进制的基数是 10。
位权,一个数码处在数的不同位置时，它所代表的数值是不同的。每个数码所表示的数值等于该数码乘以一个与数码所在位置有关的常数，这个常数叫位权。
位权的大小是以基数为底,数码所在位置的序号为指数的整数次幂 。
例如,十进制数个位数位置上的位权为 100,千位数位置上的位权为 103,小数后第 3位的位权为 10-3。
例如,十进制数 1548.3687可以表示成：
1548.3687 = 1× 103+5× 102+4× 101+8× 100+
3× 10-1+6× 10-2+8× 10-3+7× 10-4
计算机的运算基础是二进制,计算机中采用二进制,
而不采用十进制,这是因为：
（ 1） 二进制的数码 0和 1,用电子器件极易实现 。
（ 2） 二进制数的运算规则简单 。
（ 3） 二进制数只有两个状态,数字的传输和处理不容易出错,计算机工作的可靠性高 。
（ 4） 二进制码的两个符号,0” 和,1” 正好与逻辑命题的两个值,真,和,假,相对应,为计算机实现逻辑运算和程序中逻辑判断提供了便利条件 。
2,常用的数制在计算机科学技术中常用的数制有：
十进制,二进制,八进制和十六进制 。
在计算机内部一切数据的存储,处理和传送均采用 二进制 形式 。
二进制不便于书写,通常用八进制或十六进制来书写,因此计算机学科引入了 八进制和十六进制 。
为了适应人的习惯,数值型数据在输入输出设备上则采用人们十分熟悉的 十进制 。
无论是哪一种数制,采用位权表示法的数制有四个重要的特征：
★ 逢 R进一 （ R为基数 ） 。 如十进制数逢十进一 。
★ 数字的总个数等于基数 。 如十进制数 0—9。
★ 最大的数字比基数小 1。 如十进制中最大数字为 9。
★ 每个数字都要乘以基数的幂次,该幂次由每个数字所在的位置决定 。
一般地,对于 R进制而言,其基数为 R,使用 R个数字表示数值,其中最大的数字为 R-1,任何一个 R进制数 N：
N = an an-1 …,,a1 a0 ·a-1…… a-m
均可表示为如下按权展开式形式：
N = an an-1 …,,a1 a0 ·a-1…… a-m
= an × Rn + an-1 × Rn-1 +… + a1 × R1 +
a0 × R0 + a-1 × R-1 +…… + a-m × R-m
（ 1） 十进制 （ 简记符为 D）
十进制用 0,1,2,3,4,5,6,7,8,9十个数码表示数值,采用,逢十进一,计数原则 。 基数为 10，
位权为 10i。
例如,十进制数 5246.376可表示成：
5246.376 = 5× 103+2× 102+4× 101+6× 100+
3× 10-1+7× 10-2+6× 10-3
（ 2） 二进制 （ 简记符为 B）
二进制用数字 0和 1表示数值,采用,逢二进一,
计数原则 。 基数为 2,位权为 2 i。
例如,二进制数 1011.101可表示成：
1011.101 = 1× 23+0× 22+1× 21+1× 20
+1× 2-1+0× 2-2+1× 2-3
二进制计数方式最本质的东西是每位数计满 2时,
向高一位进一,即,逢二进一,。
对于二进制数,小数点向右移一位,数值就扩大 2
倍,例如,11011.101=10× (1101.1101)；反之,小数点向左移一位,数值就缩小 2倍 。
例如,11011.101=1/10× (110111.01)。
另外,若个位数是 1,则此二进制数就是奇数,如
11,11101,110001等都是奇数,若个位数是 0,则此数就是偶数,如 110,111010,11000等都是偶数 。
二进制数的加法和乘法的运算规则如下：
加法运算规则,乘法运算规则：
0 + 0 = 0 0 × 0 = 0
0 + 1 = 1 0 × 1 = 0
1 + 0 = 1 1 × 0 = 0
1 + 1 = 10 1 × 1 = 1
[例 1.1] （ 1011） 2 + （ 11011） 2 =？
1 0 1 1
+ 1 1 0 1 1
1 0 0 1 1 0
即,1011 + 11011 = 100110
相当于十进制数 11+27=38。
[例 1.2] （ 1001） 2 × （ 110） 2 =？
1 0 0 1
× 1 1 0
1 0 0 1
+ 1 0 0 1
1 1 0 1 1 0
即,（ 1001） 2 × （ 110） 2 =（ 110110） 2
相当于十进制数 9× 6=54。
（ 3） 八进制 （ 简记符为 Q）
八进制用 0,1,2,3,4,5,6,7八个数码表示数值,采用,逢八进一,计数原则 。 基数为 8,位权为 8
i。
例如：
（ 473.25） 8 = 4 × 82 + 7 × 81 + 3 ×
80 + 2 × 8-1 + 5 × 8-2
（ 4） 十六进制 （ 简记符为 H）
十六进制用 0,1,2,3,4,5,6,7,8,9,A，
B,C,D,E,F十六个数码表示数值,采用,逢十六进一,计数原则 。 基数为 16,位权为 16 i。
例如：
（ 4AF8.94B） 16 = 4× 163+A× 162+F× 161+ 8× 160
+9× 16-1 +4× 16-2 +B× 16-3
综上所述可见,各种进位计数制的基本道理是相同的,只是在日常生活中不经常用到二进制,八进制和十六进制,对它们不十分熟悉而已,但它们之间存有内在的联系,它们之间可以相互转换 。
3,各种数制间的相互转换将数由一种数制转换成另一种数制称为数制间的转换 。
（ 1） 非十进制转换成十进制非十进制数转换成十进制数采用,位权法,,即把非十进制数写成各自的按权展开式,然后按十进制运算原则求和,其和值就是转换后对应的十进制数 。
[例 1.3] 将二进制数 1011101.1001转换成十进制数 。
（ 1011101.1001） 2 = 1× 26 + 0× 25 + 1× 24
+ 1× 23 + 1× 22 + 0× 21
+ 1× 20 + 1× 2-1 + 0× 2-2
+ 0× 2-3 + 1× 2-4
= 64+16+8+4+1+0.5+0.0625
=（ 93.5625） 10
[例 1.4] 将八进制数 763.24转换成十进制数 。
（ 763.24） 2 = 7× 82 + 6× 81 + 3× 80 + 2× 8-1
+ 4× 8-2
= 448 + 48 + 3 + 0.25 + 0.0625
= （ 499,3125） 10
[例 1.5] 将十六进制数 B2F转换成十进制数 。
（ B2F） 16 = B× 162 + 2× 161 + F× 160
= 11× 162 + 2× 161 + 15× 160
= 2816 + 32 + 15 = （ 2863） 10
（ 2） 十进制数转换成非十进制数将十进制数转换成二进制,八进制或十六进制等非十进制数的方法是相似的,十进制数转换非十进制数时,整数部分和小数部分分别进行转换,将两个转换结果结合起来就可以得到对应的非十进制数 。
★ 十进制整数转换成非十进制整数将十进制整数转换为非十进制整数采用,除基取余法,。 即,将十进制整数及此期间产生的商逐次除以需转换为数制的基数,直到商为零为止,并记下每一次相除所得到的余数,按从后往前的次序将各余数记作 K n K n -1K n-2…… K 0,从而构成转换后对应的非十进制整数 。
[例 1.6] 将十进制整数 125转换成对应的二进制整数 。
2 125 余数
2 62 1
2 31 0
2 15 1
2 7 1
2 3 1
2 1 1
0 1
则得,（ 125） 10 = （ 1111101） 2
[例 1.7] 将十进制整数 125转换成对应的十六进制整数 。
16 125 余数
16 7 13 （ D）
0 7
则得,（ 125） 10 = （ 7D） 16
[例 1.8] 将十进制整数 125转换成对应的八进制整数 。
8 125 余数
8 15 5
8 1 7
0 1
则得,（ 125） 10 = （ 175） 8
★ 十进制小数转换成非十进制小数将十进制小数转换为非十进制小数采用,乘基取整法,。 即：将十进制小数及此期间产生的积小数部分逐次乘以需转换为数制的基数,直到积的小数部分为零为止或达到一定精度为止,并记下每一次相乘所得到的整数部分,按照从前往后的次序,将各整数部分记作 k–1 k-2…… k-m,从而构成转换后对应的非十进制小数 。
[例 1.9] 将十进制小数 0.625转换成对应的十六进制小数 。
0.625 整数部分
× 16
3750
+ 625
10.000 10 (A)
则得,（ 0,625） 10 =（ 0,A） 16
[例 1.10] 将十进制小数 0.625转换成对应的二进制小数。
0.625 整数部分
× 2
1.250 1
0.25
× 2
0.5 0
× 2
1.0 1
则得：（ 0,625） 10 =（ 0,101） 2
[例 1.11] 将十进制小数 0.625转换成对应的八进制 小数
0.625 整数部分
× 8
5.000 5
则得,（ 0,625） 10 =（ 0,5） 8
[例 1.12] 将十进制小数 0.467转换成对应的二进制数
0.467 整数部分
× 2
0.934 0
× 2
1.868 1
0.868
× 2
1.736 1
0.736
× 2
1.472 1
…………,.
则得,（ 0,467） 10 =（ 0,0111…,） 2
如果一个十进制数既有整数部分，又有小数部分，
则应将整数部分和小数部分分别进行转换，然后把两者相加便得到结果。
[例 1.13] 将十进制数 125.625转换成对应的二进制数因为 （ 125） 10 =（ 1111101） 2
（ 0.625） 10 =（ 0.101） 2
所以 （ 125.625） 10=（ 1111101.101） 2
（ 3）二进制与八进制、十六进制之间的转换由于一位八进制数对应 3位二进制数，一位十六进制数对应 4位二进制数，于是二进制数与八进制数、
十六进制数之间的转换比较简单。
★ 二进制与八进制之间的转换二进制的基数是 2，八进制的基数是 8，由于 8=23，
因此，一位八进制数正好相当于 3位二进制数；反之，
3位二进制数可表示一位八进制数 。
若把二进制数转换为八进制数，只须以小数点为界，将整数部分从右向左每 3位一组，最高一组不足 3
位时，在最左端添 0补足 3位，小数部分从左向右，每
3位一组，最低一组不足 3位时，在最右端添 0补足 3位，
然后，将各组的 3位二进制数转换为对应的一位八进制数即可。反之，若将八进制数转换成二进制数，只要把每位八进制数用对应的 3位二进制数表示即可。
[例 1.14] 将二进制数 1101100111.10011转换成对的八进制数。
0 0 1 1 0 1 1 0 0 1 1 1,1 0 0 1 1 0
1 5 4 7 4 6
则得,（ 1101100111.10011） 2 =（ 1547.46） 8
[例 1.15] 将八进制数 576.32转换成对应的二进制数 。
（ 576.32） 8 = 101 111 110,011 010
则得,(576,32) 8 =（ 101111110,01101） 2
★ 二进制与十六进制之间的转换十六进制的基数是 16，由于 16=24，因此，一位十六进制数可用 4位二进制数表示。
若把二进制数转换为十六进制数,只须以小数点为界,将整数部分从右向左每 4位一组,最高一组不足
4位时,在最左端添 0补足,小数部分从左向右按 4位为一组,最低一组不足 4位时,在最右端添 0补足,然后,
将各组的 4位二进制数转换为对应的一位十六进制数即可 。 反之,若将十六进制数转换成二进制数,只要把每位十六进制数用对应的 4位二进制数表示即可 。
[例 1.16] 将二进制数 1101100111.10111转换成对应的十六进制数 。
0 0 1 1 0 1 1 0 0 1 1 1,1 0 1 1 1 0 0 0
3 6 7 B 8
则得,（ 1101100111,10111） 2 =（ 367,B8） 16
[例 1.17] 将十六进制数 5FD4,A3转换成对应的二进制数 。
（ 5FD4,A3） 8 = 0101 1111 1101 0100,1010 0011
则得,（ 5FD4,A3） 16
=（ 101111111010100,10100011） 2
返回
1.3.2 码制计算机处理的数据分为数值型和非数值型两类。
数值型数据是指数学中的代数值，具有量的含义，且有正负之分、整数和小数之分。 非数值型数据是指输入到计算机中的所有信息，没有量的含义，如英文字母、数字符号 0~9、汉字、声音、图形、
图像等。
在计算机中这些数据是如何表示的呢？由于计算机采用二进制，也就是说计算机只识别 0和 1形式的代码，所以输入到计算机中任何数值型和非数值型数据都必须转换为二进制代码 。
1．机器数与真值在计算机中,数值型数据是用二进制数来表示的,
数值型数据有正,负之分,那么在计算机内部是如何表示正,负号的呢？
在计算机内部数值型数据的最高位用来表示数值的正负,这一位通常称为 符号位 。 规定：用,0” 表示
,+” 号,用,1” 表示,﹣,号 。
在计算机内部数字和正负号都用二进制代码表示,
两者结合在一起构成数值型数据的机内表示 。 我们把这种连同数字与符号组合在一起的二进制数称为 机器数,由机器数所表示的实际值称为 真值 。
如,（ 00110101） 2 =（ +53） 10
即在计算机内部 00110101这一串二进制数代表十进制数 +53。
（ 10110101） 2 =（ ﹣ 53） 10
在计算机内部 10110101这一串二进制数代表十进制数 ﹣53 。
2．原码、反码和补码计算机中机器数可以用不同的码制来表示，常用的码制有原码表示法、反码表示法和补码表示法。
设机器字长为 n位，最高位为符号位，其余 n-1位为数值位。
★ 原码表示法原码：最高位为真值的符号 （ 正为 0,负为 1） 其余 n-1位为数值位且与真值的数值位相同 。 数 X的原码记为 [X]原 。
例如：假设机器字长 8位,二进制数 +1011011和
﹣ 1011011的原码分别表示为 01011011和 11011011。
注意,在原码表示中,零有两种表示形式,
即,[+0]原 =00000000,[﹣ 0]原 =10000000
原码所能表示的数的范围与机器字长有关,设机器字长为八位时,最高位为符号位,整数原码表示的范围为 ﹣ 127 ～ +127。 即最大数是 01111111,最小数是 11111111。 同理,机器字长为十六位时,整数原码的范围为 ﹣ 32767 ～ +32767。
[例 1.19] 假设字长为 8，求十进制数 +56与 ﹣56 的原码。
因为 （ 56） 10 =（ 111000） 2
所以 [+56]原 = 00111000 [﹣ 56]原 =10111000
用原码表示一个数简单,直观,与真值之间转换方便 。
这种表示法,对乘法和除法的符号判别是很方便的,在作乘法或除法时,把数的符号位按位相加后,就得到结果的符号位 。
但这种表示法对加,减法来说运算比较复杂,不能用它直接对两个同号数相减或两个异号数相加 。
例如：十进制数,39” 与,﹣ 56” 的两个原码直接相加 。
因为 [+39]原 = 00100111 [﹣ 56]原 = 10111000
0 0 1 0 0 1 1 1
+ 1 0 1 1 1 0 0 0
1 1 0 1 1 1 1 1
其结果符号位为 1表示是负数,真值为,1011111”,
即等于十进制数,﹣ 95”,这显然是错误的 。
又如，十进制数,+39” 与,+56” 的两个原码直接相减：
0 0 1 0 0 1 1 1
﹣ 0 0 1 1 1 0 0 0
1 1 1 0 1 1 1 1
其机器数为,11101111”,真值为十进制数 ﹣ 111，
这显然也是不对的 。 因此为了计算机中方便进行加,
减法而引入了反码和补码表示法 。
★ 反码表示法反码：正数的反码和原码相同,负数的反码是对该数的原码除符号位外各位取反,即,0” 变,1”,
,1” 变,0” 。 数 X的反码记为 [X]反 。
例如：设机器字长 8位,二进制数 +1011011和
﹣ 1011011的反码分别表示为 01011011和 10100100。
零的反码 表示有两种,即,[ +0]反 = 00000000
[﹣ 0]反 = 11111111
可以验证,任何一个数的反码的反码即是原码本身 。
反码通常作为求补过程的中间形式 。
★ 补码表示法补码：正数的补码和原码相同,负数的补码是对该数的原码除符号位外各位取反,最末位加 1。 即：反码加 1。 数 X的补码记为 [X]补 。
例如：设机器字长 8位,二进制数 +1011011和
﹣ 1011011的补码分别表示为 01011011和 10100101。
零的补码 表示是唯一的 。
即,[+0]补 = [﹣ 0]补 = 00000000。
补码所能表示的数的范围也与二进制数的位数
（ 即机器字长 ） 有关,假设用八位二进制数表示时,
最高位为符号位,整数补码表示的范围为 ﹣ 128 ～
+127。 用十六位二进制数表示整数补码时的范围为
﹣ 32768 ～ +32767。
[例 1.20] 设字长为 8,求十进制数 +56与 ﹣ 56的补码 。
[+56]补 = [+56]原 = 00111000
[﹣ 56]原 = 10111000 [﹣ 56]补 = 11001000
可以验证，任何一个数的补码的补码即是原码本身 。
引入补码后,加减法都可以用加法来实现,即减法变为加法来运算,并且两数的补码之,和,等于两数,和,的补码 。
即,[ X+Y ]补 = [ X ]补 + [ Y ]补
[ X﹣ Y ]补 = [ X+（ ﹣ Y） ]补 = [ X ]补 + [﹣ Y ]补
[例 1.21] 计算十进制数,39” 与,56” 之差
（ 39） 10﹣ （ 56） 10 = [39 ]补 + [﹣ 56 ]补
[39 ]补 = 00100111 [﹣ 56 ]补 = 11001000
0 0 1 0 0 1 1 1
+ 1 1 0 0 1 0 0 0
1 1 1 0 1 1 1 1
其结果 11101111为补码,对它再进行一次求补运算就得到结果的原码表示形式,即,[11101111] 补 = 10010001
则 10010001=﹣ 0010001= （ ﹣ 17） 10,由于 39﹣ 56 =﹣ 17,所以结果正确 。
由此可见,计算机中加减法运算都可以统一化成补码的加法运算,其符号位也参与运算 。 目前计算机中的加减法运算基本上都采用补码进行运算 。 返回
1.3.3 定点数与浮点数在计算机中，参与运算的数据，既有整数，也有小数，那么在计算机内部小数点是如何表示的呢？
在计算机系统中，当处理的数值含有小数部分时，计算机并不是采用某个二进制位来表示小数点，
而是用隐含规定小数点的位置来表示。
按小数点的位置是否固定，一般分为定点数和浮点数，相应地数据具有定点表示和浮点表示两种形式。
1,定点数在机器中,小数点位置固定的数称为 定点数,定点数根据小数点隐含固定位置不同,又分为 定点小数和定点整数 。
（ 1） 定点小数定点小数是指小数点隐含固定在最高数值位的左边,符号位右边,参与运算的数是纯小数 。
记作,X0,X -1 X -2 …… X –m,定点小数在计算机中表示的格式如下：
数值位符号位 隐含小数点位置
X0 X-1 X-2 ··· X-m
在定点小数表示中，机器中运算的数都是绝对值小于 1的纯小数。但实际上，参加运算的数不可能都是这样的纯小数，对于绝对值大于 1的数，若直接使用定点小数格式将产生,溢出,,因此应根据实际需要取一个
,比例因子,,将原数据按比例缩小，以定点小数格式表示，得到结果后再按该比例扩大，得到实际的结果。
例如,有一数为 110.1001将其乘以 2–3，
得,110.1001× 2 –3 = 0.1101001
这样,该数就通过比例因子 2 –3缩小为小于 1的数 。
设机器字长为 n位,其中一位是符号位,其余 （ n-1）
位是有效数值位,那么这种定点小数所能表示的数值范围为,﹣ 0.1111…… 11 ～ 0.1111…… 11
n-1位 n-1位即,﹣ (1-2 ﹣ ( n-1 ) )≤ x ≤ 1-2 ﹣ ( n-1 )
若采用补码运算,由于零的补码唯一,规定用
1.0000…… 00 表示 ﹣ 1,所以 n位字长的定点小数所能表示的数值范围为,﹣ 1≤ x ≤ 1-2 ﹣ ( n-1 ) 。
（ 2） 定点整数定点整数是指小数点隐含固定在整个数值的最右端,符号位右边所有的位数表示的是一个纯整数 。 记作,X n X n -1 X n - 2 …… X 1 X 0,定点整数在计算机中表示的格式如下：
数值位符号位 隐含小数点位置在定点整数表示中,机器中运算的数都是绝对值大于 1的整数,并且都是绝对值在一定范围内的整数,，
对于绝对值超出该范围或参与运算的数是小数,我们就不能直接使用定点整数格式表示,需要根据实际情况适当地选取一个,比例因子,进行调整 。
Xn Xn-1 Xn-2 ··· X0
n位字长（其是一位是符号位）的定点整数（补码）
所能表示的数值范围为：
﹣ 2 n-1 ≤ X ≤ 2 n-1﹣ 1
定点表示法所能表示的数值范围非常有限,计算机做定点运算时,很容易溢出 。 溢出是计算结果超出字长表示范围的现象,它使计算机的运算发生错误 。
无论是定点小数或定点整数，由于小数点都固定在一个位置，所以机器在运算时不必对位，可以直接进行加减运算。实现这种运算方法的电路都比较简单，
但表示数的范围受到限制，缺乏灵活性，且为了防止
,溢出,需要选择合适的,比例因子,,对运算前后的数据按比例因子折算，使用也不方便。
2．浮点数浮点数是指小数点位置不固定,根据需要而浮动的数,它既有整数部分又有小数部分 。
定点数所能表示的范围非常有限,在许多场合下是不够用的,浮点数表示法可以扩大数据的表示范围 。
在计算机中通常把浮点数分成阶码和尾数两部分来表示,其中阶码一般用补码定点整数表示,阶码用于表示该数的小数点位置,尾数一般用补码或原码定点小数表示,尾数用于表示数据的有效位 。
一个数 N用浮点数表示可以写成,N = M× RE
其中 M表示 尾数,E表示 指数,R表示 基数 。 基数一般取 2,8,16。 一旦计算机定义好了基数值,就不能再改变了,因此,基数在浮点数中不用表示出来,是隐含的 。
浮点数的格式多种多样，在设计时，阶码和尾数占用的位数可以灵活地设定，由于阶码确定数的表示范围，而尾数确定数的精度，所以 当字长一定时，分配给阶码的位数越多，则表示数的范围越大，但分配给尾数的位数将减少，从而降低了表示数的精度，反之，分配阶码的位数减少，则数的表示范围将变小，
但尾数的位数增加，从而使精度提高。
例如，某计算机字长为 32位，用 4个字节表示浮点数，阶码部分为 8位补码定点整数，尾数部分为 24位补码定点小数，基数为 2，如下图所示。
31 30 24 23 22 0
阶码部分 尾数部分阶符 阶码 尾符 尾数为了提高精度通常其尾数的最高位必须是非零的有效位,这称为 浮点数的规格化 形式 。
由于其阶码为 8位,由阶码最大值为 2 7﹣ 1 =（ 127） 10,阶码最小值为 ﹣ 2 7 = （ ﹣ 128） 10,这样格式所表示数的范围为：
﹣ 1× 2 127 ～ （ 1﹣ 2﹣ 23 ） × 2 127
由此可见，浮点数的表示范围要比定点数大得多，但也不是无限的，当计算机中参与运算的数超出了浮点数的表示范围时称为 溢出 。如果一个数的阶码大于计算机所能表示的最大阶码，则称为 上溢 ；反之，若小于最小阶码，则称为 下溢 。上溢时计算机将停止运算，转溢出中断处理程序进行溢出处理；下溢时计算机将该数作为机器零来处理，即把该浮点数的阶码和尾数全置成零，但仍能进行运算。
采用浮点表示的数,在运算之前要进行对齐小数点的操作 （ 称为 对阶 ）,才能进行加减运算 。
在计算机中判断两数的小数点是否对齐,只要判断两数的阶码是否相等,若相等,则说明两小数点的位置已对齐 。 所以实现浮点运算操作比较麻烦,设备也比较复杂 。
返回
1.3.4 信息编码信息编码是指对输入到计算机中的各种非数值型数据用二进制数进行编码的方式 。 所谓编码就是用若干位二进制代码,选择一定的组合原则来表示组成信息的各种符号 。 根据不同的用途有各种各样的编码方案,常用的有 ASCII码,BCD码,汉字编码和数据校验码 。
1,ASCII码
ASCII码是美国标准信息交换码,已被国际标准化组织定为国际标准,是目前最普遍使用的字符编码 。 字符是计算机中使用最多的非数值型数据,是人与计算机进行通信,交互的重要媒介 。
ASCII码有 7位码和 8位码两种编码方案,常用的是 7位码方案 。 7位 ASCII码是用七位二进制数进行编码的,可共表示 2 7 =128个字符 。
ASCII码的每个字符用 7位二进制码表示，其排列次序为 b6b5b4 b3b2b1b0 。通过查 ASCII码表可以找到数字、运算符、标点符号以及控制字符等字符与 ASCII码之间的对应关系。
例如：小写字母,g‖的 ASCII码为 1100111；
ASCII码 0110011对应的字符是数字,3” 。
字符 0～ 9十个数字字符的 ASCII码的高 3位编码
（ b6b5b4） 为 011,低 4位为 0000～ 1001。 当去掉高 3位的值时,低 4位正好是 0～ 9的二进制数形式 。 这样编码既满足正常的排序关系,又有利于完成 ASCII码与二进制数之间的转换 。
字母 A～ Z的编码值为 65～ 90（ 1000001～
1011010）,小写英文字母 a～ z的编码值为 97～ 122
（ 1100001～ 1111010）,大,小写字母编码差别仅表现在 b5位的值为 0或 1,对应大,小写英文字母 ASCII码值十进制形式相差 32,因此大,小写英文字母之间的编码转换非常便利 。
为了提高信息传输的可靠性，字符 ASCII码在计算机内实际是用 八位二进制代码 表示的,一个字符占一个字节存储空间,一个字节中的 ASCII码表示如图 1.5
所示。
有效编码位奇偶校验位
ASCII码的最高位 b7作为奇偶校验位 。 所谓 奇偶校验,是指在代码传送过程中用来检验是否出现错误的一种方法,一般分奇校验和偶校验两种 。 例如,奇
（ 偶 ） 校验规则为：若 7位 ASCII码中,1” 的个数为奇
（ 偶 ） 数,则校验位置,0”,否则置,1” 。 注意,
校验位仅在信息传输时有用,在对 ASCII码进行处理时校验位被忽略 。
b7 b6 b5 b4 b3 b2 b1 b0
2,BCD码
BCD码又称 8421码，是一种二 —— 十进制的编码，
它使用 4位二进制数表示一位十进制数。由于 4位二进制数可表示 16种状态，只取前 10种状态 0000～ 1001来表示十进制数码 0～ 9，从左到右每位二进制数的权分别是 8,4,2,1，因此又叫 8421码。这种编码既具有二进制形式，又具有十进制的特点，它是逢,十,进位的。 BCD码十个不同的码分别是,0000,0001,0010、
0011,0100,0101,0110,0111,1000和 1001，这十个码分别代表十进制数码 0,1,2,3,4,5,6,7,8、
9。
BCD码很直观，可以很容易实现与十进制的转换。
对于多位十进制数，可以直接使用一位十进制数用四位二进制数来编码表示。
例如：十进制数 258对应的 BCD码 001001011000；
反之,BCD码 1001 1000 0111 0010 对应的十进制数是 9872。
3．汉字编码计算机在处理汉字信息时需要对汉字进行编码，
由于汉字数量大，字形复杂，同音字多，所以汉字在计算机中的输入、内部处理、存储和输出都使用不同的编码。如 汉字输入码、汉字机内码、汉字交换码、
汉字字形码以及汉字地址码 等汉字信息处理系统在处理汉字时，不同环节使用不同的编码，并根据不同的处理层次和不同的处理要求，要进行一系列的汉字代码转换。从汉字输入到最终的汉字输出的转换过程如下图所示。
汉字 汉字输入设备 输入管理模块 汉字库 输出设备汉字输入码 国标码汉字机内码汉字字形码
（ 1）汉字输入码汉字输入码是为方便人工通过输入设备 (如键盘 )输入汉字而设计的代码。
输入码种类繁多，广泛采用的输入码主要有,
区位码,智能 ABC码,五笔字型码、快速输入码 等。
（ 2）汉字交换码 (又称为国标码）
汉字交换码是用于汉字信息处理系统之间或通信系统之间进行信息交换的汉字代码。
我国的国标 GB2312-80制定了汉字交换码的标准。
该标准规定了信息交换用的 6763个汉字和 682个非汉字图形字符编码。根据汉字使用频率的高低、构词能力强弱、实际用途的大小划分为两级汉字，一级汉字 3755个，
二级汉字 3008个。一级汉字按拼音顺序排列，同音汉字按笔画顺序排列；二级汉字按部首顺序排列。
国标码字符集中的任何一个汉字或图形符号都用两个 7位的二进制数表示，在计算机中用两个字节表示，
每个字节的最高位为 0，剩余 7位为 GB2312-80二进制编码。
（ 3）汉字机内码汉字机内码是供计算机系统内部进行汉字存储、加工处理、传输统一使用的代码。也称汉字内码。
目前国内应用较广的一种为两字节机内码，俗称变形国标码。即：
这种格式的机内码是将国标码的两个字节的最高位分别置 1得到的。其最大优点是机内码表示简单，和交换码之间有明显的对应关系。
即：机内码 =国标码 +8080H
（ 4）汉字字形码汉字字形码是指汉字字库中存储的汉字字形的数字化信息码，它主要用于汉字输出 (打印、显示等 )时产生的汉字字形。
有两种显示字形的方法,矢量字符和点阵字符 。一个汉字系统所允许使用的全部汉字的汉字字形编码称为
,汉字库,,存放于系统的汉字字形库的存储器中。
1 ××××××× 1 ×××××××
在通用汉字系统中，广泛以点阵的方式形成汉字，
这时的汉字字形码是汉字点阵字形的代码，以点阵形式组成的汉字字形码，由于点阵规格的不同，又分为
16× 16,24× 24,32× 32,48× 48，甚至更多点阵的汉字库。
对于 16× 16的点阵字形，字形码为 32个字节
(16× 16÷ 8=32)每个汉字占 32B,那么 16× 16点阵汉字字库（包括一、二级汉字 6763个）共占 230KB左右。
（ 5）汉字地址码是指汉字字形码在汉字字库中存放位置的代码，即字形信息的地址 。
需要向输出设备输出汉字时，必须通过地址码，才能在汉字库中取到所需的字形码，最终在输出设备上形成可见的汉字字形。
由于汉字字形信息都是按一定顺序连续存放在存储器中。因此，汉字地址码一般是连续有序的，并且与汉字机内码间有着简单的换算关系。 返回
1.4 逻辑代数与逻辑电路基础
1.4.1 逻辑代数
1.4.2 逻辑电路和逻辑设计基础返回
1.4.1 逻辑代数计算机之所以具有逻辑处理能力，是由于计算机中使用了实现各种逻辑功能的电路，逻辑代数是进行逻辑电路设计的数学基础。
逻辑代数是 1847英国数学家乔治 ·布尔首先创立的，所以有时又叫 布尔代数 。
逻辑代数与普通代数有本质的区别，逻辑代数表示的不是数量大小之间的关系，而且逻辑关系，
逻辑代数中的 0和 1，不是数量的 0和 1，它只代表所要研究问题的两种可能性或两种稳定的物理状态。
它是分析和设计逻辑电路的基本数学工具。
1．逻辑变量和逻辑函数逻辑电路具有输入和输出间的逻辑关系，为了对输入和输出间的逻辑关系进行数学表达和演算，所以提出了 逻辑变量 和 逻辑函数 两个术语。
一个逻辑电路如下图所示,A,B为输入,F为输出，
输入和输出之间的逻辑关系为 F = f（ A,B）。
A F
B
A,B,F为逻辑变量
F=(A,B)为逻辑函数逻辑变量和逻辑函数的逻辑取值,只取两个值 0
和 1,通常称为逻辑 0和逻辑 1。
F＝ f(A,B)
2．逻辑运算逻辑变量之间的运算，称为逻辑运算。它包括三种基本运算,逻辑与、逻辑或和逻辑非 。通过这三种基本运算，可推导出其它逻辑运算，如 异或运算 等等。
（ 1） 逻辑与运算逻辑与又称为逻辑乘,通常用,·” 表示 。 它的运算规则为：
0 ·0 = 0 读成 0与 0等于 0
0 ·1 = 0 读成 0与 1等于 0
1 ·0 = 0 读成 1与 0等于 0
1 ·1 = 1 读成 1与 1等于 1
即：与运算表示，只有参加运算的逻辑变量都同时取值为 1时，其与运算结果才等于 1。
现在举例说明与运算的物理意义 。 如某学校用电,
只有当学校电源总闸和教学楼分闸同时接通,教室里才有电使用 。
（ 2）逻辑或运算逻辑或又称逻辑加,通常用符号,+” 来表示,或运算的运算规则如下：
0 + 0 = 0 读成 0或 0等于 0
0 + 1 = 1 读成 0或 1等于 1
1 + 0 = 1 读成 1或 0等于 1
1 + 1 = 1 读成 1或 1等于 1
可见,在给定的逻辑量中,只要有一个为 1,逻辑或的结果就为 1。
逻辑或的这种作用,在日常生活中经常可以碰到 。
例如,房间里有一盏电灯,为了使用方便,装了两个开关,这两个开关并联,显然,任何一个开关接通或两个开关同时接通电灯都会亮 。
注意：逻辑加与算术加法的运算规律不完全相同 。 要特别注意,1 + 1 = 1。
（ 3）逻辑非运算逻辑非运算在普通代数中是没有的 。 在逻辑量上方加横线,
,—” 表示非 。 其运算规则为：
0 = 1 读成非 0等于 1； 1 = 0 读成非 1等于 0
例如室内电灯,不是亮就是灭,只有这两种可能 。
(4） 异或运算异或运算通常用符号,,表示,它的运算规则为：
0 0 = 0 读成 0同 0异或,结果为 0
0 1 = 1 读成 0同 1异或,结果为 1
1 0 = 1 读成 1同 0异或,结果为 1
1 1 = 0 读成 1同 1异或,结果为 0
在给定的两个逻辑量中,只要两个逻辑量的值相同,异或运算的结果就为 0；只有相异时,结果才为 1。
注意,当两个多位的逻辑量进行逻辑运算时,只在对应位之间按上述规律进行逻辑运算,不同位之间没有任何关系,当然,也就不存在算术运算中的进位或借位问题 。
例如,1 1 0 1 1 0 0 0
+ 0 1 0 1 1 1 1 0
1 1 0 1 1 1 1 0
+
+
+
+
+
返回
1.4.2 逻辑电路和逻辑设计基础
1,逻辑电路基础能实现逻辑运算的电路称为 逻辑门电路 （简称门电路），常用的门电路有,与,门,,或,门、
,非,门,,与非,门,,或非,门,,异或,门等。由基本门电路可以按逻辑设计组合成计算机硬件的基本功能电路，如：触发器、寄存器、计数器、
译码器、半加器、全加器等等。
（ 1）,与,门实现,与,运算的单元电路叫,与,门。,与,
门的逻辑符号如图所示,A F=AB
B
其逻辑函数表达式为,F = A B。
例如 A=1,B=0,则 F = A B = 1·0 = 0
&
（ 2）,或,门实现,或,运算的单元电路叫,或,门 。,或,门的逻辑符号如图所示,A F=A+B
B
其逻辑函数表达式为,F = A + B。
例如 A=0,B=0,则 F=A+B=0+0=0。
（ 3） ―非,门实现,非,运算的单元电路叫,非,门,或叫反相器 。,非,门的逻辑符号如图所示：
A F=A
其逻辑函数表达式为,F= A。
例如 A=1,则 F = A = 0。
1
≥ 1
（ 4）,与非,门
―与非,门是由,与,门和,非,门两个单元电路组合而成的逻辑电路,用以实现,与非,运算 。 ―与非,
门的逻辑函数表达式为,F = A B,其逻辑结构和逻辑符号如下图所示 。
A AB F=AB A F=AB
B B
例如,若 A=1,B=0,则 F= A B = 1·0 = 1。
（ 3） ―或非,门
―或非,门是由,或,门和,非,门两个单元门电路组合而成,用以实现,或非,运算 。,或非,门逻辑表达式为,F=A+B,其逻辑结构和逻辑符号如下图所示 。
A A+B F=A+B A F=A+B
B B
例如,若 A=1,B=0,则 F= A+B = 1+0 = 0。
1& ≥ 1
1& ≥ 1
（ 5）,异或,门
,异或,门是由,非,门,,与,门和,或,门逻辑组合而成的逻辑电路 。 用以实现,异或,运算 。 具有两个输入端的,异或,门由两个,非,门,两个,与,
门和一个,或,门组合而成 。
其逻辑函数表达式为,F =Ａ Ｂ = A B+ＡＢ,异或门的逻辑符号如下图所示 。
A F＝ A B
B
对于给定的输入 A和 B,可以得出 F=A B。
例如：若 A=1,B=0，
则 F= A B= A B+A B = 1 ·0+ 1 ·0 = 1
+
＝ 1 +
+
+
2,逻辑组合电路的分析与设计逻辑组合电路的分析是指找出组合电路逻辑功能的过程,而设计则是指按照给定的具体逻辑问题,求出简单的逻辑电路的过程 。
（ 1） 逻辑电路分析方法分析逻辑组合电路的目的是找出其逻辑功能,既然逻辑组合电路的输出为一逻辑函数,那么用真值表来表示电路功能就最为直观了 。 由小规模集成电路构成的组合电路的分析,通常先根据给定的逻辑电路,
由输入到输出逐级写出逻辑函数表达式,然后对其进行化简,进而得到最简的逻辑表达式,有时也用真值表来直观表示电路的逻辑功能 。
（ 2）逻辑设计方法与步骤逻辑组合电路的设计是要按照给定的逻辑问题,设计出能实现其逻辑功能的电路 。
逻辑组合电路设计的步骤如下：
① 描述逻辑电路应具备的逻辑功能
② 构造真值表,构造能够实现逻辑电路的逻辑功能的真值表。要列真值表首先得对事件的因果关系进行分析，把事件的起因定为输入变量，把事件的结果作为输出逻辑函数；其次要对逻辑变量赋予输入量各种组合值，用逻辑 0和 1分别表示两种不同状态；再根据给定事件的因果关系给出逻辑函数的值。
③ 写逻辑函数表达式,即根据真值表写出相应的逻辑函数表达式并进行化简。
④ 根据简化的逻辑函数表达式画逻辑图。 返回
1.5 计算机的基本结构和工作原理
1.5.1 计算机硬件的基本结构
1.5.2 计算机的工作原理返回
1.5.1 计算机硬件的基本结构计算机是一种按着程序自动、高速地进行信息处理的系统，它由硬件和软件两大部分组成。计算机硬件的基本功能是接受计算机程序的控制来实现数据输入、运算、数据输出等一系列基本操作。
计算机硬件是计算机系统的重要组成部分，它是由电子的、磁性的、机械的器件按一定结构组成的设备，
是计算机的物质基础。各种类型的计算机硬件虽然有不同的实现形式，但都有其相同的基本结构和特点。
自从 1946年世界上第一台计算机诞生，计算机的体系结构不断地改进完善，其性能成倍地提高。虽然现在的计算机系统从性能指标、运算速度、工作方式、应用领域和价格等方面都有了长足的发展，但基本结构仍一直沿袭冯,诺依曼传统的框架。
美国数学家 冯,诺依曼 研制了 EDVAC计算机,他提出了计算机应由五个基本部分组成,即,运算器,控制器,
存储器,输入设备和输出设备,并描述了五大部分的功能及其相互关系,还提出了,采用二进制,和,存储程序,两个重要基本思想 。,采用二进制,就是计算机中的数据和指令均以二进制形式存储和处理；,存储程序,
就是将程序事先存入存储器中,使计算机在工作时能自动地从存储器中读取指令,分析后执行 。
目前大多数计算机都采用冯,诺依曼体系结构,都属于冯,诺依曼型计算机,其基本结构如下图所示 。
1,运算器 （ Arithmetic Unit）
运算器是计算机对数据进行加工处理的部件,主要包括 算术逻辑单元 （ ALU） 和寄存器 。
主要功能是在控制器的控制下执行程序中的指令,
完成各种 算术运算 和 逻辑运算,实现逻辑判断 。
ALU主要完成加,减,乘,除等四则运算以及与,
或,非,移位等逻辑运算,寄存器用来暂存参加运算的操作数或运算结果 。
运算器的主要技术指标是 运算速度,其单位是
MIPS（ 每秒百万条指令 ） 。
2,控制器 （ Control Unit）
控制器的作用是指挥整个计算机的各个部件按照指令的功能要求有条不紊地协调工作 。
控制器由 程序计数器 （ PC）,指令寄存器 （ IR）,
指令译码器 （ ID）,时序电路和微操作控制电路 组成,
程序计数器 用来对程序中的指令进行计数,其内容存放预将执行的指令在内存储器中的存储地址,使得控制器能依次读取指令 。
指令寄存器 在指令执行期间暂时保存正在执行的指令 。
指令译码器 用来对指令的操作码进行译码,产生的译码信号识别了该指令要进行的操作,并传送给微控制部件,以便产生相应的控制信号 。
时序控制电路 用来生成时序信号,以协调在指令执行周期内部件的工作 。
微操作控制电路 用来产生各种控制操作命令 。
控制器和运算器 合在一起称为 中央处理器,
即 CPU（ Central Processing Unit）,它是计算机的核心 。
3,存储器存储器是计算机的记忆和存储部件,用来存储数据和程序 。 按功能存储器一般可分为 内存储器和外存储器 两大类 。
（ 1） 内存储器 （ 简称内存 ）
内存储器也称为主存储器 （ 简称主存 ）,用来存放当前运行程序的指令和数据 。
目前内存由半导体存储器所组成,它直接与运算器和控制器相连接 。
内存特点,直接与 CPU交换信息,存取速度快,存储容量较小,价格相对外存高等 。
按存取方式内存可分为 随机存取存储器 (简称 RAM）
和只读存储器 （ 简称 ROM） 。 RAM是一种读写存储器,
通常用来存放正在执行的程序及所需的数据 。 RAM存取速度快,但它只是临时存储信息,即加电记忆信息,
一但断电 RAM中的信息立即丢失 。
ROM中的信息只能读出而不能重新写入和修改,
其信息是制作时用专门仪器写入的 。 计算机断电后,
其中的信息不丢失 。 ROM常用来存放一些专用固定的程序,数据和系统配置软件 。 如 磁盘引导程序,
自检程序,I/O驱动程序 等 。
内存由若干存储单元组成,为了区别不同的存储单元,一般从,0” 开始对存储单元进行连续编号,
每个单元都有一个唯一的号码,我们把它称为存储单元的 地址 。 每个存储单元能存放一个二进制数,
或一条由二进制编码表示的指令 。 如下图所示：
每个存储单元由若干位二进制位组成,,位,
（ bit） 是存储器的最小存储单位,一位可存储一位二进制数,8位二进制代码称为一个 字节 （ Byte,简称 B）,
字节是计算机中数据处理和存储容量的基本单位 。
1 K = 1024 B 1 GB= 1024 MB
1 MB= 1024 K 1 TB= 1024 GM
一个存储单元中存入的信息称为一个,字,,一个字所包含的二进制数的位数称为,字长,。
小型机或微型机的字长一般为 16位或 32位,计算机的字长越长,其精确度越高 。
存储器所包含的存储单元的总数称为 存储容量,现在微机内存容量大多在兆字节以上 。
（ 2） 外存储器 （ 简称外存 ）
内存由于技术及价格等原因,容量有限,不可能容纳所有的系统软件及各种用户程序,因此,计算机系统都配置外存 。 外存又称为 辅助存储器,它是内存的扩充外存特点,存储容量大,价格低,但存取速度较慢,
不能与 CPU直接交换信息等 。
一般用来存放需要长期保存的,暂时不用的程序,
数据和结果,需要时可成批地和内存进行信息交换 。
目前常用的外存有 磁盘 （ 软盘,硬盘 ）,光盘,磁带 等 。 外存容量一般用 KB,MB,GB,TB来表示 。
4,输入 /输出设备输入 /输出设备简称 I/O设备,它是外部与计算机交换信息的渠道,用户通过输入设备将程序,数据,操作命令等输入计算机,输出设备将计算机处理的结果显示或打印出来 。
常用的输入设备有,键盘,鼠标器,扫描仪,光笔,
数字化仪和语音输入装置等 。
常用的输出设备有 显示器,打印机,绘图仪和声音播放装置等 。 返回
1.5.2 计算机的工作原理计算机是一种能存储程序和数据，并能自动对各种数字化信息进行处理的机器。
计算机之所以能自动进行信息处理，是因为它能将程序及数据存储在内存中，并能自动执行程序，
我们称之为 存储程序原理 。要使计算机能自动工作，
必须根据要解决的问题编好程序，并将程序转换成由机器语言指令组成的形式存入内存中，然后以存储程序的首地址启动机器执行第一条指令。以后，
计算机便开始自动地 取指令，分析指令，执行指令所规定的操作，周而复始，直到将该程序执行完毕。
以计算 3＋ 5＝ 8为例具体说明计算机工作原理和过程。要想让计算机计算 3＋ 5，首先编写好计算程序，假设用 8086指令系统编写此程序，程序如下：
MOV AL,X
ADD AL,Y
MOV SUM,AL
HLT
说明,X,Y,SUM是变量，其存储情况如下：
系统把这 4条指令组成的程序段存放到存储器中。
当把首地址置入程序计数器 IP中,便可启动计算机执行该程序，其工作过程如下：
1,取第一条指令并执行
（ 1） 取指令并分析指令在取指令机器周期内,取出第一条指令,MOV
AL,X‖的机器码送入指令寄存器 IR中,该指令的操作码部分经指令译码器分析产生传送操作的信号,
,告诉,微操作控制部件本指令将要执行传送操作 。
与此同时,指令寄存器中的寻址方式和形式地址部分经地址形成器,计算出源操作数的物理地址
（ 1FD40H）,目标操作数是内部寄存器 AL。 在取指令机器周期内还更新 IP的内容,为执行下一条指令作好准备 。
（ 2） 执行指令微操作控制部件接收到来自指令译码器的译码信号,取数和传递,,则转入执行,存储器读机器周期,。在该周期内将完成从地址为 1FD40H的单元中取出 X的值是 3，并送入寄存器 AL中，第一条指令执行完毕，转入执行第二条指令。
2,取第二条指令并执行
（ 1） 取指令并分析指令从存储单元中取出第二条指令,ADD AL,Y‖的机器码并送入 IR中,IR中的操作码部分经指令译码器 ） 译码产生,ADD‖的信号有效,同时从寻址方式和形式地址指明的目标操作数是寄存器 AL,源操作数是存储器,由地址形成器计算出操作数的存储单元地址为 1FD41H。 此外为取下一条指令准备 IP地址 。
（ 2） 执行指令微操作控制部件接收到来自 ID的译码信号,相加寄存器操作数和存储器操作数,,在此机器周期内要完成存储器读操作和加法操作。先从 1FD41H存储单元中取出 Y的值 5送到运算器输入端，运算器执行加法运算 3+5，得出和 8送入 AL中。第二条指令执行完毕，故转入执行第三条指令。
第三条指令与第一条指令相似,完成的都是数据传送,但传送的方向不同,完成的是存储器写操作,即将 AL的内容传送 （ 写 ） 到 SUM的存储单元之中
（ 1FD42H号单元 ） 。
第四条指令是停机指令,可在取指令机器周期内完成 。
综上所述,我们对计算机的自动工作原理作如下概括,从计算机程序员的角度看,计算机自动工作过程是执行预先编写好的程序的过程,
而执行程序的过程就是周而复始地完成取指令,分析指令和执行指令的过程 。
返回
1.6 程序设计基础
1.6.1 程序设计的概念
1.6.2 程序设计语言
1.6.3 算法与数据结构返回
1.6.1 程序设计的概念程序设计是软件开发过程中的一个重要环节,程序设计是计算机科学与技术专业学生的基本功,这个专业的学生将来大部分要从事程序设计工作,因此,必须掌握程序设计的基本要领,才能成为优秀的设计人员 。
1,什么是程序设计利用计算机解决问题,首先要按照人们的意愿,
借助计算机语言,将解决问题的方法,公式,步骤等编写成程序,然后将程序输入到计算机中,由计算机执行这个程序,这个设计和书写程序的整个过程就是程序设计 。
程序设计 是根据给出的具体任务,编制一个能正确完成该任务的计算机程序 。
计算机程序 是有序指令的集合或者是具有一定结构的语句的集合 。 它能被计算机执行 。
为了能很好地完成给定的任务,程序设计过程大致需要三步,① 确定算法与数据结构 ；
② 用流程图表示程序的思想 ；
③ 用程序设计语言编制计算机程序 。
2,程序设计方法目前程序设计方法主要有结构化程序设计和面向对象程序设计 。
结构化程序设计 是由荷兰学者 Dijkstra在 20世纪 70年代提出的,其 主要思想是自顶向下,逐步求精,模块编程 。
结构化程序设计采用自顶向下逐步求精的设计方法就是先设计顶层,然后步步深入,逐层细分,
逐步求精,直到整个问题可用程序设计语言明确地描述出来为止 。
结构化程序设计采用单入口单出口的控制结构,
即：程序由 顺序,选择,循环 三种基本控制结构组成 。 任何一个算法都可以用这三种基本结构实现,
任何复杂的程序都可以分解为由三种基本结构组成 。
3种基本结构如下图所示 。
结构化程序设计使得程序结构清晰,可读性好,
在出现问题时,便于查错,易于修改,提高了程序设计的质量 。 但随着软件规模和复杂性的增长,这种方法越来越不能适应庞大,复杂软件的开发,暴露出许多缺点,面向对象程序设计方法正是在这种背景下诞生的 。
面向对象的程序设计 （ Object Oriented
Programming,缩写为 OOP） 是一种先进的程序设计方法,OOP实际上是围绕着各类事物进行程序设计的,
OOP本质是把数据和处理数据的过程 （ 函数 ） 当成一个整体 — 对象 。 一旦在程序中建立了一个对象,
其他程序员可以在其他的程序中使用这个对象,完全不必重新编制繁琐复杂的代码 。 对象的重复使用可以大大地节省开发时间,切实地提高软件的开发效率 。
面向对象具有三个重要特性,即 封装性,继承性和 多态性 。
封装性,把数据结构同操作数据的过程组合在一起,把它们封装在一个类中 。
这种封装性能保护类中的数据与过程的安全,防止外界干扰和误用 。
继承性,这种特性很符合人的思维方式,通过继承,一个对象可以获得另一个对象的属性,并可加入一些属于自己的特性 。
多态性,就是一个接口,多种方式 。
多态性的优点在于通过提供一个相同的接口,可以通过不同的动作来访问,从而降低了问题的复杂度 。
面向对象程序设计并没有摒弃结构化程序设计方法,相反,它是在充分吸收结构化程序设计优点的基础上,引进了对象,类等新的,强有力的概念,从而开创了程序设计工作的新天地 。
2,程序设计风格程序设计时程序应 结构清晰,合理,编写出来的程序不仅可在机器上正确执行,还要便于程序的调试和维护,让别人能看懂 。
学习程序设计过程中,必须养成良好的程序设计风格 。 好的程序设计风格有助于提高程序的正确性,可读性,可维护性,可用性 。
建议从以下方面，逐步形成良好程序设计风格,
（ 1）编码格式和编码约定在整个程序中应保持一致；
（ 2）程序中应给出必要的注释。
（ 3）对变量、标识等的命名，采用,匈牙利命名法,。（ 4）程序书写采用缩进格式，突出程序的层次结构。 （ 5）每一行只写一条语句，使用括号间隔表达式或语句的组成部分。
（ 6）使用结构化、面向对象的编程技术，提高程序可重用性、可扩充性 。
（ 7）提高程序健壮性，预防用户的操作错误返回
1.6.2 程序设计语言编写计算机程序所用的语言即 程序设计语言,是人与计算机之间交换信息的工具 。 程序设计语言的发展从面向过程,到面向对象,进一步发展成为面向组件,经历了非常曲折的发展过程 。 总的来说可以分成 机器语言,
汇编语言,高级语言,面向对象语言 等等 。
1,机器语言机器语言是计算机第一代语言,它由 0,1代码构组的机器指令集合组成 。 是最底层,能直接被机器所接受的语言 。
用机器语言编写程序,计算机硬件可直接识别,执行速度比较快,基本上充分发挥了计算机的速度性能 。
不同的 CPU,其机器语言也不同 。 针对一种计算机所编写的机器语言程序,不能在另一种计算机上运行 。
机器语言不容易记忆,程序编写难度大,调试修改繁琐,且不易移植,但执行速度最快,它是一种面向机器的程序设计语言 。
2,汇编语言汇编语言是第二代程序设计语言 。
汇编语言是用助记符代替操作码,用地址符号代替地址码,使机器语言,符号化,,所以也称汇编语言是符号语言 。
汇编语言与特定类型的机器相对应,也是一种面向机器的语言 。 事实上,每一个计算机厂家都为自己的机器制定了一套机器码的,助记符,,即汇编语言指令系统 。
汇编语言与机器语言是一,一对应的,因此,对于不同的计算机,针对同一问题所编写的汇编语言源程序是互不通用的 。 用汇编语言编写的程序执行效率比较高,但通用性与可移植性仍然比较差 。
总的来说,汇编语言比机器语言前进了一步 。 但是,计算机不能直接识别用汇编语言编写的程序,必须由一种专门翻译程序将汇编语言程序翻译成机器语言程序,计算机才能执行 。
3,高级语言机器语言和汇编语言都是面向机器的语言,称为低级语言 。 它们对机器依赖性很大,用它们开发的程序通用性差,且要求程序员必须熟悉和了解计算机硬件的每一个细节,普通计算机用户很难胜任编程工作 。
随着计算机技术的发展及计算机应用领域的不断扩大,计算机用户的队伍不断壮大,而且这个队伍中绝大部分不是计算机专业人员 。 为此,从 20世纪 50年代中期开始,逐步发展了面向问题的程序设计语言,
称为 高级语言 。 高级语言与具体的计算机硬件无关,
其表达方式接近于被描述的问题,接近于自然语言和数学语言,易被人们接受和掌握 。
高级语言的显著特点是独立于具体的计算机硬件,
通用性和可移植性好 。
目前,计算机高级语言已有上百种之多,得到广泛应用的也有十几种,并且几乎每一种高级语言都有其最适用的领域 。
高级语言发展经历了二个阶段 。
第一阶段高级语言是 过程化 的语言,如,BASIC
语言,C语言,FORTRAN语言,COBOL语言,PASCAL语言,LISP语言等都是过程化的语言 。 过程化语言编程时需要一步一步地安排好机器的执行顺序,要告诉机器怎么做 。
第二个阶段的高级语言是 非过程化 语言 。 非过程化语言只需告诉机器做什么就可以了,由机器自己生成和安排执行的步骤 。 如 FOXBASE,FOXPRO都是非过程化的语言 。
用任一种高级语言编写的源程序都不能被计算机直接执行,在执行之前,必须由编译程序或解释程序翻译成机器能接受的目标代码 。 与低级语言相比,用高级语言编写的程序其执行的时间和空间效率要差 。
取其所长,上述三类语言可用在不同的场合,一般科学计算,数据处理采用高级语言比较合适,而实时控制因为速度要求高,往往采用汇编语言 。
4,面向对象程序设计语言 (OOPL)
OOPL是建立在用对象编程的方法基础上的,是当前程序设计采用最多的一种语言 。
OOPL具有封装性,继承性和多态性 。
OOPL有两大类：一类是纯粹的面向对象语言,在纯粹的面向对象语言中,几乎所有的语言成分都是
,对象,,如,Smalltalk,Java等,这类语强调开发快速原型的能力；另一类是混合型面向对象语言,如：
C++,Object Pascal,这类语言是在传统的过程化语言基础上增加面向对象机制,它所强调的是运行效率 。
成熟的面向对象语言通常都提供丰富的类库和强有力的开发环境 。
5,组件技术所谓组件可理解为自包含的,可编程的,可重用的,与语言无关的代码片段,可以作为整体很容易地插入到应用程序中 。 组件技术是计算机软件发展的最新结果,也是非常有效的软件构造方法 。 返回
1.6.3 算法与数据结构大型软件系统的开发,应运用软件工程的思想和方法进行,而解决较简单的实际问题时,需要遵循以下几个步骤：
★ 分析问题,确定算法将要解决的问题进行分析,提取操作的对象,
并找出操作对象之间的关系 。 在此基础上确定具体解决问题的方法和步骤,设计出一种优化算法 。
★ 选择程序设计语言进行程序设计选择适当的程序设计语言,将算法转换成程序代码 。 人们常把程序定义为：
程序 =算法 +数据结构 +程序设计语言 +工具和环境
★ 程序测试设计一组足够的测试数据,使用这组测试数据来运行程序 。
分析问题,确定算法在整个解决问题过程中是非常重要的一步,决不可忽视 。
1,算法
（ 1） 什么是算法算法是解题的步骤,是一组有穷的规则,它们规定了解决某一特定问题的一系列运算,是对解题方案的准确与完整的描述 。
制定一个算法,一般要经过设计算法,描述算法,
分析算法和验证算法等阶段 。
（ 2） 算法的特性一个算法具有下列五个重要的特性：
确定性,有穷性,可行性,输入和输出 。
（ 3） 算法的描述算法的描述方法可以归纳为以下几种,
① 自然语言 。
② 图形,如 N-S图,流程图,图的描述与算法语言的描述对应 。
③ 算法语言,即：程序设计语言,伪代码 。
（ 4） 衡量算法优劣的方法解决某一个实际问题可能有许多不同的算法,究竟如何来衡量这些算法的优劣？ 并从中选出较好的算法呢？
选用的算法首先应该是,正确的,。 此外,主要考虑如下 3点：
① 执行算法所耗费的时间,即时间特性 。
② 执行算法所耗费的存储空间,即空间特性 。
③ 算法应易于理解,易于编码,易于调试 。
当然,我们希望选用一个所占存储空间小,运算时间短,其它性能也好的算法 。 然而,实际上很难做到十全十美 。 原因是上述要求有时相互抵触,要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间 。 因此我们只能根据具体情况有所侧重 。
2,数据结构计算机发展初期,人们使用计算机主要是处理数值计算问题 。 由于数值计算的特点是数据元素之间的关系简单,但计算复杂,所以程序设计者的主要精力是集中于程序设计技巧上,而无须重视数据结构 。 随着计算机应用领域的扩大和软,硬件的发展,计算机被更多地用于非数值处理,据统计,用计算机处理非数值性问题占了 90% 以上,非数值处理的特点是数据元素间的关系复杂,而计算相对简单 。 因此解决此类问题的关键已不再是分析数学和计算方法,而是要设计出合适的数据结构,才能有效地解决问题 。
利用计算机解决实际问题,不仅需要研究算法与程序结构,同时也需要研究程序的加工对象 ——数据的结构 。 数据结构直接影响算法的选择和程序的效率 。
程序设计的实质是对实际问题选择一种好的数据结构,
加之设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构 。
（ 1） 数据结构的基本概念数据,是指描述客观事物的数值,字符以及所有能输入到计算机并被计算机程序处理的符号的集合 。
数据的含义极为广泛,数值,字符,图形,图像,
声音等都是数据 。
数据元素,是数据集合中的一个个体,它是数据的基本单位 。
数据结构,是指相互之间存在某种关系的数据元素的集合 。 它一般包括以下三方面的内容：数据的逻辑结构,数据的存储结构和数据的操作实现算法 。
逻辑结构,是指数据元素之间的逻辑关系,它分为线性结构和非线性结构 。 线性表是典型的线性结构,而树形结构是典型的非线性结构 。
存储结构,是指数据元素及其之间的关系在计算机存储器中的表示方法 。 数据的存储结构主要有顺序存储结构和链式存储结构两种基本类型 。
数据的操作,是指对对数据实施的操作 。
从学科的角度来看,数据结构是计算机科学技术的一个分支,它主要研究数据的逻辑结构 (即数据元素之间的逻辑关系 )和物理结构 (即数据在计算机中是如何表示的 )以及它们之间的关系,并对这种结构定义相应的操作,设计出实现这些操作的算法 。
从课程的角度来看,数据结构是计算机科学与技术专业的一门重要的专业基础课,是教学计划中的核心课程之一 。 其中将系统地介绍线性表,栈,队列,串,
数组和广义表,树,图等基本类型的数据结构及其相应操作的实现算法,并将详细讨论在程序设计中经常会遇到的查找和排序技术 。 这些知识和技术不仅是一般非数值计算程序设计的基础,而且也是设计和实现如编译程序,操作系统,数据库管理系统等系统软件以及大型应用程序的重要基础 。
（ 2） 几种典型的数据结构简介
★ 线性表 （ Linear_List）
线性表是最简单且最常用的一种数据结构 。
① 线性表的定义,线性表是由 n (n≥ 0)个数据元素
（ 结点 ） a 1,a 2,…… a n 组成的有限序列 。 其中数据元素可以是一个数,一个符号或一个记录等信息,
不同的线性表中的数据元素可以是各种各样的,但同一线性表中的元素必定是同一数据对象 。
如：英文字母表 （ A,B,C,……………,Z） 是一个线性表 。 又如,学生情况表,如下表所示,是一种较为复杂的线性表 。
学生情况表
② 线性表的基本操作,线性表是一种相当灵活的数据结构,对线性表的数据元素不仅可以进行访问,还可以进行插入和删除等操作 。
常见的线性表基本操作有：
(a) InitList(L),构造空的线性表 L,即表的初始化 。
(b) ListLength(L),求线性表 L中的数据元素的个数,
(c) GetNode(L,i ),取线性表 L中的第 i个结点,要求
1≤ i≤ListLength(L) 。
(d) LocateNode(L,x ),在 L中查找 x结点,并返回该结点在 L中的位置 。 若 L中有多个结点的值和 x相同,则返回首次找到的结点位置；若 L
中没有 x结点,则返回一个特殊值表示查找失败 。
(e) InsertList(L,x,i ),在线性表 L的第 i个位置前插入新结点 x。 如果线性表 L原有 n个数据元素,则执行此操作后,其数据元素个数将变为 n+1。
(f) DeleteList(L,i ),删除线性表 L的第 i个结点,
如果线性表 L原有 n个数据元素,则执行此操作后,其数据元素个数将变为 n-1。
③ 线性表的存储结构,将一个线性表存储到计算机中可以采用许多不同的方法,常采用的方法有 顺序存储结构和链式存储结构 。
线性表的顺序存储 是把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里 。 用这种方法存储的线性表称为顺序表 。
设线性表的每个元素占用 C个存储单元,第一个单元的存储地址是该元素的存储地址,设表中开始第一个元素 a 1的存储地址是 Loc(a 1),那么线性表中的第 i
个数据元素 a i 的存储地址为：
Loc(a i)=Loc(a 1) + (i-1) * C 1≤i≤n
确定了存储线性表的起始地位置,线性表中任一数据元素都可随机存取,所以说 线性表的顺序存储结构是一种随机存取的存储结构 。
高级语言中数组类型也有随机存取的特性,因此通常采用一维数组来描述顺序表 。
线性表 顺序存储结构的优点,可以随机存取表中任一结点,实现对线性表的某些操作比较简单,如：计算线性表的长度,存取线性表中的任意一个结点,查找线性表中某一元素等等 。
缺点 是在实现线性表的 插入和删除 操作时,则需要移动大量数据元素而花费较多的时间 。
链式存储结构 是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续,甚至是零散分布在内存中的任何位置上,因此为了表示每个数据元素 a i与其直接后继数据元素 a i+1 之间的逻辑关系,除了存储其自身的信息外,还需存储指示直接后继的信息 。
这样,线性表每个数据元素的存储表示包括两个域：存储数据元素信息的域称为 数据域 ；存储直接后继存储位置的域称为 指针域 。 有 n个元素的线性表每个数据元素之间通过指针连接成为一个链式的结构,因此又称其为 链表 。
链表的优点,插入,删除操作简单,只须修改相应的指针域 。
缺点,不能随机存取线性表中数据元素,只能顺序存取,所以实现查找操作比较繁琐 。
★ 栈 （ Stack）
栈是特殊的线性表,它的逻辑结构和线性表相同,
只是其基本操作较线性表有更多的限制,故又称是受限的线性表 。 栈被广泛应用于各种程序设计中 。
① 栈的定义,栈是限制仅在表的一端 （ 即表尾 ）
进行插入和删除操作的线性表,通常称插入,删除这一端为 栈顶 （ Top）,另一端称为 栈底 （ Bottom） 。
当表中没有元素时称为 空栈 。 栈的示意图如下：
② 栈的基本操作：
(a) InitStack(S),构造一个空栈 S。
(b) StackEmpty(S),判栈空 。 若 S为空栈,则返回
TRUE,否则返回 FALSE。
(c) StackFull(S),判栈满 。 若 S为满栈,则返回
TRUE,否则返回 FALSE。
(d) Push(S,x),进栈 。 若栈 S不满,则将元素
x插入 S的栈顶 。
(e) Pop(S),退栈 。 若栈 S非空,则将 S的栈顶元素删去,并返回该元素 。
③ 栈的存储结构,栈也有两种存储表示方法,即顺序栈和链栈,栈一般采用顺序存储结构 。
顺序栈是使用一个连续的存储区域来存放栈元素,
并设置一个栈项指针 TOP,用来指示栈顶位置,进栈和退栈只能在栈顶进行 。
★ 树 （ Tree）
树形结构是一类非常重要的非线性结构,它用于描述数据元素之间的层次关系,类似于自然界中的树 。
树结构在客观世界中是大量存在的,例如族谱,行政组织机构都可用树形象地表示 。 在计算机领域中,树形结构的应用也非常广泛,磁盘文件的目录结构就是一个典型的例子,在编译程序中,用树来表示源程序的语法结构,在分析算法的行为时,可用树来描述其执行过程 。 树和二叉树是常用的树形结构,由于用二叉树表示对于树的存储和操作有很大意义,可以把对于树的许多处理转换到对应的二叉树中去做,因此,
先介绍树的基本概念,然后重点讨论二叉树的有关概念,存储结构和常用操作 。
① 树的基本概念：
树：是 n（ n≥ 0） 个结点的有限集 T,T为空时称为空树,T非空时,有且仅有一个特定的结点称为根结点,其余结点可被分成 m（ m≥ 0） 个互不相交的子集 T1,T2,…… Tm,其中每个子集本身又是一棵树,
并称其为根结点的子树 。
如图是一棵具有 12个结点的树 。
树结构中的基本术语：
孩子结点,双亲结点,树中某结点的各子树的根称为该结点的孩子；相应地该结点称为其孩子的双亲 。
结点的度,一个结点所拥有的子树的个数称为该结点的度 。
叶子结点,分支结点,度为 0的结点称为叶结点,
度不为 0的结点称分支结点 。
树的深度,树的叶结点的最大层数称为树的深度 。
② 二叉树的基本概念：
二叉树 （ Binary Tree）,是 n (n≥ 0) 个结点的有限集,它或是空集 （ n=0）,或是由一个根结点及两棵互不相交的,分别称为根的左子树和右子树组成 。
如下图是一棵二叉树 。
需要说明的是,尽管树和二叉树的概念之间有许多关系,但它们是两个概念 。
二叉树不是树的特殊情况,树和二叉树之间最主要的区别是,二叉树是有序的,二叉树的结点的子树要区分左子树和右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 。
完全二叉树和满二叉树是两种特殊形态的二叉树 。
满二叉树,在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶结点都在同一层上,这样的一棵二叉树称为满二叉树 。
完全二叉树,一棵深度为 K的有 n 个结点的二叉树,
对树中的结点按从上至下,从左到右的顺序进行编号,
如果编号为 i(1≤i≤n) 的结点与满二叉树中编号为 i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树 。 显然,一棵满二叉树必定是一棵完全二叉树 。
③ 二叉树的存储结构二叉树的存储结构有顺序存储和链式存储 。 顺序存储结构,就是用一组连续的存储单元存放二叉树中的结点,完全二叉树由于其结构的特点,通常采用顺序方式存储；链式存储结构是用链建立二叉树中结点之间的关系,通常采用的链式存储结构为 二叉链表 。
所谓二叉链表,是将二叉树中的结点设置为如下的结构体类型：
其中,data表示保存结点本身信息的信息域,lchild
和 rchild分别为指向结点的左孩子和右孩子的指针域 。
④ 二叉树的基本操作 ——遍历 （ Traversal）
所谓遍历是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问 。 但访问结点所做的操作依赖于具体的应用问题 。
根据二叉树的定义知道,一棵二叉树可看做由三部分组成：根结点,左子树和右子树 。 若又规定按先左子树后右子树的顺序进行遍历,则遍历有三种方式：
DLR,LDR和 LRD,它们分别被称为前序遍历,中序遍历和后序遍历 。 另外还有一种按二叉树中结点由上至下,
由左至右的顺序进行遍历的方法,叫层次遍历 。
前序遍历的方法为：
若二叉树为空,遍历结束,否则,① 访问根结点；
② 前序遍历根结点的左子树； ③ 前序遍历根结点的右子树 。
中序遍历的方法为：
若二叉树为空,遍历结束,否则,① 中序遍历根结点的左子树； ② 访问根结点； ③ 中序遍历根结点的右子树 。
后序遍历的方法为：
若二叉树为空,遍历结束,否则,① 后序遍历根结点的左子树； ② 后序遍历根结点的右子树； ③ 访问根结点 。
本章结束返回
