当前位置:首页 >> 学科竞赛 >> 信息学竞赛辅导资料

信息学竞赛辅导资料


第 0 章 概述
0.1 关于信息学奥林匹克竞赛
全国青少年信息学奥林匹克竞赛(简称 NOI)及其分区联赛(NOIP)由中国计算机学 会主办。 是中国科协和教育部委托并批准中国计算机学会举办的信息技术普及活动, 其宗旨 就是在青少年中普及计算机科学,激发青少年的学习兴趣,并从竞赛中发现人才。 NOIP 是同一时间在全国各个省份同时开展的比赛,1995 年开始举

办第一届。只有在分 区赛中表现十分突出的学生才有机会代表其所在省份参加全国信息学奥林匹克竞赛 (NOI) 。 如果在 NOI 中表现极其优秀,就会有机会代表国家参加国际奥林匹克竞赛(IOI) 。 北京曾于 2000 年成功举办第 12 届国际奥林匹克竞赛(IOI) 。 NOIP 分两个等级组:普及组和提高组。每组竞赛分两轮:初试和复试。初试形式为笔 试,侧重考察学生的计算机基础知识和编程的基本能力,并对知识面的广度进行测试。初试 为资格测试,获本省初试成绩在本赛区前 15%的学生进入复赛。复试形式为上机编程,着 重考察学生对问题的分析理解能力,数学抽象能力,编程语言的能力和编程技巧、想象力和 创造性等。各省 NOIP 的各等奖项在复试的优胜者中产生。 比赛中使用的程序设计语言是 PASCAL 或 C/C++。 初赛内容与要求: 1.计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通 信网络的主要特征、数字化) 2.信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输入输 出方式) 3.信息的表示与处理(信息编码、微处理部件 MPU、内存储结构、指令, 程序,和存储程序原理、程序的三种基本控制结构) 4.信息的存储、组织与管理(存储介质、存储器结构、文件管理、数据库 管理) 5.信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的部件 间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP 协议、HTTP 协议、 WEB 应用的主要方式和特点) 6.人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径(文 本及交互操作) ) 7.信息技术的新发展、新特点、新应用等。 1. Windows 和 LINUX 的基本操作知识 2. 互联网的基本使用常识 (网上浏览、搜索和查询等) 3. 常用的工具软件使用(文字编辑、电子邮件收发等)

计 算 机 的 基 本 常 识

基 本 操 作

1

数 据 程 序 设 计 的 基 本 知 识 程 序 设 计 结 构

1.程序语言中基本数据类型(字符、整数、长整、浮点) 2. 浮点运算中的精度和数值比较 3.一维数组(串)与线性表 4.记录类型(PASCAL)/ 结构类型(C) 1.结构化程序设计的基本概念 2.阅读理解程序的基本能力 3.具有将简单问题抽象成适合计算机解决的模型的基本能力 4.具有针对模型设计简单算法的基本能力 5.程序流程描述(自然语言/伪码/NS 图/其他) 6.程序设计语言(PASCAL/C/C++)- 2003 仍允许 BASIC 1.初等算法(计数、统计、数学运算等) 2.排序算法(冒泡法、插入排序、合并排序、快速排序) 3.查找(顺序查找、二分法) 4.回溯算法

基 本 算 法

复赛内容与要求: 在初赛内容的基础上增加以下内容: 1.指针类型 2.多维数组 3.单链表及循环链表 4.二叉树 5.文件操作(从文本文件中读入数据,并输出到文本文件中)

数 据 结 构

程 序 设 计

1.算法的实现能力 2.程序调试基本能力 3.设计测试数据的基本能力 4.程序的时间复杂度和空间复杂度的估计

算 法 处 理

1.离散数学知识的应用(如排列组合、简单图论、数理逻辑) 2.分治思想 3.模拟法 4.贪心法 5.简单搜索算法(深度优先 广度优先)搜索中的剪枝 6.动态规划的思想及基本算法

2

第一章 计算机中的数据表示
计算机能处理的数据除了像 128、32.56 等这样的数值型数据外,还能处理文字、图片、 声音等类型的数据。 在计算机中, 所有这些数据都是以二进制编码的形式存在的, 也就是说, 不管是文字、图形、声音、动画,还是电影等各种信息,在计算机中都是以 0 和 1 组成的二 进制代码表示的。 将各种数据表示为不同二进制串的方法称为信息编码。 本章的主要内容就 是介绍计算机中各种不同类型数据的编码方法。

1.1 数值数据的表示
1.1.1 进位计数制
进位计数制简称为数制,是指用一组固定的 R 个数字符号的线性排列,按照由低位向 高位“逢 R 进一”的计数规则来表示数目的方法。我们习惯使用的是十进制,另外还有 八进制、十二进制、十六进制、六十进制等等。 回顾十进制中的个位、十位、百位、千位…,可以发现,任何一个数中的每一个位都与 一个量值相关联。例如,在数 7235 中,个位 5 的位置与量值 1 相关联,十位 3 的位置与量 值 10 相关联,百位 2 的位置与量值 100 相关联,千位 7 的位置与 1000 相关联。每一个位的 量值都是它右边的位的量值的 10 倍。 在进位计数制中, 这个与位关联的量值通常被称为权值或权。 每个位上的数字所表示的 数值等于该数字乘以该位的权值。 一种进位计数制中所用到的所有的表示数的符号被称为数符,数符的个数被称为基数 (用 R 表示)。在十进制中,用到的表示数的符号是 0,1,2,3,4,5,6,7,8,9 这十个 阿拉伯数字,因此基数 R=10。 二进制的数符则只有 0 和 1,因此其基数 R=2。八进制的数符为 0,1,2,3,4,5,6, 7,基数 R=8。十六进制的数符有 16 个,分别是 0,1,2,3,4,5,6,7,8,9,A,B, C,D,E,F,基数 R=16 如果我们把数的每个位,从小数点向左依次编号为 0,1,2,?,n,从小数点向右依 次编号为-1,-2,?,-m,并将每个编号都称为位序号,我们可以看到,位序号为 i 的位的 权值是基数 R 的 i 次方。 将数中的每一个数字与其所在位置的权的乘积求和,就是这个数所 表示的大小。 例如十进制数 7235 就可表示为:

(7235)10 ? 7 ? 103 ? 2 ? 102 ? 3 ? 101 ? 5 ? 100
二进制数 101101.11 可表示为

(101101.11) 2 ? 1 ? 25 ? 1 ? 2 4 ? 1 ? 23 ? 1 ? 2 2 ? 0 ? 21 ? 1 ? 20 ? 1 ? 2-1 ? 1 ? 2-2 ? 32 ? 0 ? 8 ? 4 ? 0 ? 1 ? 0.5 ? 0.25 ? (45.75)10
八进制 274 可表示为

3

(274)8 ? 2 ? 82 ? 7 ? 81 ? 4 ? 80 ? 128 ? 56 ? 4 ? (188)10
表 1.1 各种进制表示的 0-16 数值的对照表 十进制 0 1 2 3 4 5 6 7 8 二进制 0 1 10 11 100 101 110 111 1000 八进制 0 1 2 3 4 5 6 7 10 十六进制 0 1 2 3 4 5 6 7 8 十进制 9 10 11 12 13 14 15 16 二进制 1001 1010 1011 1100 1101 1110 1111 10000 八进制 十六进制 11 12 13 14 15 16 17 20 9 A B C D E F 10

为了表达方便起见,常在数字后加一缩写字母作为不同进制数的标识。 B -→ 二进制 Q(或 O) -→ 八进制 D -→ 十进制(可省略) H -→ 十六进制 例如: (1011)2 可表示为 1011B,十六进制数(89A2)16 可表示为 89A2H。 计算机内部是采用二进制位串来表示数据的。主要是因为: (1)技术实现简单,计算机是由逻辑电路组成,逻辑电路通常只有两个状态,开关的 接通与断开,这两种状态正好可以用“1”和“0”表示。 (2)简化运算规则:两个二进制数和、积运算组合各有三种,运算规则简单,有利于 简化计算机内部结构,提高运算速度。 (3)适合逻辑运算:逻辑代数是逻辑运算的理论依据,二进制只有两个数码,正好与 逻辑代数中的“真”和“假”相吻合。 (4)易于进行转换,二进制与十进制数易于互相转换。 (5)用二进制表示数据具有抗干扰能力强,可靠性高等优点。因为每位数据只有高低 两个状态,当受到一定程度的干扰时,仍能可靠地分辨出它是高还是低。 在计算机科学的学习过程中, 除二进制和十进制外, , 还经常用到八进制和十六进制数, 计算机能直接识别的数据为二进制数, 八进制、 十进制和十六进制数主要是便于人的书写与 记忆。

1.1.2 不同数制之间的转换
1. 二进制、八进制、十六进制数向十进制数的转换 如前面的例子所示,将各位数字与它的权相乘,其积相加,和数就是十进制。再看下面 的例子:

4

(3506.2)8 = 3×83+ 5×82+ 0×81+ 6×80+ 2×8-1 = 1862.25

(10111.1011) 2=2 4 +2 2+2 1 +2 0 +2 -1 +2-3 +2-4 =16+4+2+1+0.5+0.125+0.0625 =(23.6875) 10 89A2H=8×16 +9×162+10×161+2×160 =32768+2304+160+2 =35234
2.十进制与二进制之间的转换 一个十进制数一般可分为整数部和小数两个部分。 通常把整数部分和小数部分分别进行 转换,然后再组合起来。 a.十进制整数转换成二进制整数, 采用逐次“除 2 取余”法,即用 2 不断去除要转换的十进制数,直至商为 0 为 止。将所得各次余数,以最后余数为最前位,即得所转换的二进制数。 例 1.1 将十进制数 117 转换为二进制整数。
3

2 2 2 2 2 2 2

117 58 29 14 7 3 1 0

余数为 1 0 1 0 1 1 1



(117) 10 =(1110101) 2

实际计算式经常使用如下例子所采用的除法式子 例 1.2: 将(57)10 转换为二进制 2 |57 2 |28 ???1 2 |14 ???0 2 |7 ???0 2 |3 ???1 2 |1 ???1 0 ???1 (57)10 = 1110012

5

b.十进制小数转换成二进制小数。 采用逐次“乘 2 取整”法,即用 2 不断地乘要转换的十进制小数,直至所得积数 为 0 或小数点后的位数达到要求为止。把每次乘积的整数部分,以第一个整数为最高 位,依次排列,即可得到要转换的二进制小数。 例 1.3 将十进制小数 0.6875 转换成二进制数。 × 0. × 0. × 1. 0. × 1. ∴ 0. 6875 2 1. 3750 整数部分为 1 3750 2 7500 整数部分为 0 2 5000 整数部分为 1 5000 2 0000 整数部分为 1

(0.6875) 10 =(0.1011) 2

c.任意十进制数转换成二进制数。 对于既有整数部分又有小数部分的十进制数,可以将其整数部分和小数部分别转 换成二进制数,再把两者组合起来。 例 1.4 将十进制数 117.6875 转换成二进制数。

(117.685) 10 =(117) 10 +(0.6875) 10 =(1110101) 2 +(0.1011) 2 =(1110101.1011) 2
3. 二进制数与八进制数之间的转换 a. 二进制数转换为八进制数。 二进制数与八进制数之间的相互转换是十分方便的, 因为三位二亓制位相当于一 位八进制位。因此,二进制数转换为八进制数可用“三位一并法” ,即把待转换的二 进制数从小数点开始,分别向左、右两个方向每三位一组(最后不足三位数补“0” , ) 然后对每三位二进制数用相应的八进制数码表示。 例 1.5 将二进制数 11001011.01011 转换成八进制数。

011 3

001 1

011 3

. .

010 2

110 6

∴ (11001011.01011) 2 =(313.26) 8

6

b. 八进制数转换为二进制数。 八进制数转换为二进制数,其方法为上述转换的逆过程,即每一位八进制数码用 三位二进制数码表示,也就是“一分为三”的方法。 例 1.6 将八进制数 245.36 转换为二进制数。

2 ↓ 010

4 ↓ 100

5 ↓ 101

. .

3 ↓ 011

6 ↓ 11 0

∴ (245.36) 8 =(10100101.01111) 2
4.二进制数与十六进制数之间的转换 a. 二进制数转换成十六进制数。 因为四位二进制数对应于一位十六进制数,因此,把二进制数转换为十六进制数 可用“四位一并法” ,即把待转换的二进制数从小数点开始,分别向左、右两个方向 每四位为一组(最后不足四位数补“0” ,然后对每四位二进制数用相应的十六进制 ) 数码表示。 例 1.7 将二进制数 11001011.01011 转换为十六进制数。 1100 C 1011 B . . 0101 5 1000 8

∴ (11001011.01011) 2 =(CB.58) 16 b. 十六进制数转换为二进制数。 十六进制数转换为二进制数,其方法是上述转换的逆过程,即将每一位十六进制 数码用四位二进制数码表示,也就是“一分为四”的方法。 例 1.8 将十六进制数 1A5.C2 转换成二进制数。 1 ↓ 0001 ∴ A ↓ 1010 5 ↓ 0101 . . C ↓ 1100 2 ↓ 0010

(1A5.C2) 16 =(110100101.1100001) 2

1.1.3 计算机数值数据的表示
计算机中采用二进制来表示数值数据,由于计算机内用于表示“ 0”和“1”的电 子元件个数是有限的,因此计算机能存储和处理的二进制数的位数也是有限的。 由于一般的数值数据既有正数也有负数,因此,计算机中需要一种方法来表示数 的正负号的。事实上方法很简单,就是用二进制数串的最高位(左边第一位)来表示 数的符号,并约定以“0”表示正,以“1”表示负。 对小数点则不需要显示表示,而是根据事先约定的规则确定小数点的位置,因此说小 数点的位置总是是隐含的。 根据小数点位置的不同规定方式, 计算机中的数有 “定点” “浮 和
7

点”两种表示形式。 1. 定点数 定点数将计算机中的小数点位置视为是固定不变的。有两种定点数,定点整数和定点 小数。如果小数点位置约定在最低数值位的后面,则该数是定点整数;如果小数点位置约定 在最高数值位和符号位之间,则该数是定点小数。

定点整数

定点小数 例如,假定用两个字节存放一个定点数,则以定点方式表示的十进制整数 195 为:

以定点方式表示的十进制纯小数-0.6876 为:

这里,(-0.6876)10=(-0.10110000000001101?)2,转换为二进制称为无限循环小数,存储 时超出存储空间的位被截断丢弃,从而影响了数的精度。 定点整数只能表示正数,而定点小数只能存放纯小数(整数部分为 0 的小数) 。 如果知道一个定点数的小数点位置约定和占用存储空间大小,那么很容易确定其表示 数的范围。数值范围是指一种数据类型所能表示的数的最大值和最小值。 无符号数 对定点整数,有时可以不必考虑其正负号,这时保留其符号位就没有意义了,因 此,计算机中就有了一种新的数据类型,被称为无符号整数,无符号整数在计算机中 存储时是没有符号位的。

8

真值和机器数 真值:正、负号加二进制数绝对值的书写形式,例如,X=+1011、y=-1011。 机器数:在计算机中使用的连同符号一起数码化表示的二进制数的形式。 用最高位表示符号位, “0”表示正号, “1”表示负号,其余各位表示二进制数绝 对值大小。这种表示方法就是一种机器数表示,被称为原码表示。 例如:真值为 X=+1011 和 y=-1011 的二进制数的原码表示为 X= 0 1011,y=1 1011。 由于原码表示的机器数虽然便于利用运算器作二进制加法运算,但并不适合做减法, 为了将加、减运算简化为单纯的二进制加运算,以便于在计算机中实现各种运算,实际计算 机内部在存储定点数的时候大多采用的都是补吗表示。 不管是定点整数还是定点小数,正数的补码与原码完全相同,负数的补码也可由原码 求得,符号位不变,其余各位变翻(1 变 0,0 变 1) ,然后加 1(二进制加法,有进位是需 要进位) 。 例:x=+1001100B,则[x]补=01001100B=[x]原 x=-1001100B,则[x]原= 11001100B 由[X]补求[-X]补(求机器负数) 方法:连同符号一起将各位取反,末位再加 1。 例:设字长 N=8 位,X= +1001001B,则 [X]补= 01001001B,[-X]补= 10110111B x=-1001100B,则[x]原= 11001100B [x]补=10110100B,[-x]补=01001100B 当补码加法运算的结果不超出机器范围时,可得出以下重要结论: (1) 用补码表示的两数进行加法运算,其结果仍为补码。 (2) [X+Y]补=[X]补+[Y]补。 (3) 符号位与数值位一样参与运算。 (4) [X-Y]补=[X]补+[-Y]补。 给定一个二进制代码,赋予它不同的类型,其代表的数值是不一样。而该代码的类型 是由人编程指定的。 例:计算机内一个 8 位二进制数 10000001B 作为无符号二进制数它的值是 129,作为有符号整数的原码值为-1,作为有符号整数 的补码,则代表的值为-127。而如果作为有符号小数的原码值则成了-0.0000001B,作为 有符号小数的补码,其值为-0.11111111B(-127/128) 。 定点数在计算机内部的表示方法除了原码和补码外,还有反码、移码等表示方式。 2.浮点数 定点数只能表示整数和纯小数, 为了表示一个类似于 21.35 这样的普通实数必须使用浮 点数。顾名思义,浮点数就是指小数点位置可浮动的数,那它是如何实现小数点浮动的呢? 其实十分简单,类似于我们学过的科学记数法。 我们知道,任何一个十进制数 x 都可以写成如下形式: [x]补=10110100B

x ? a *10 n

9

其中,a 是一个带小数点的数,且 1 ?| a |? 10 ,n 是一个整数。 这就是所谓的科学记数法。同样的道理,任何一个二进制数,也可以写成上面的形式, 即对任意二进制数 N,都可记为:

N ? M * 2E
其中,规定 M 为一个纯小数,E 是一个整数,并且称 M 为尾数,E 为阶码,这就是二 进制数 N 的浮点表示。2 被称为阶的基数(或底) ,它的二进制形式应为“10” ,但是为了书 写方便,一般还是写作“2” 。 从上面的式子可以看出,任何一个带小数点的二进制数都可以由尾数、阶码、和底来 表示,因此只要记住这三个部分,也就记住了这个数。但由于底数为常数 2,因此只要记住 尾数和阶码就可以了。因此,浮点数在计算机内的表示方式为: MS 1位 E n+1 位 M m位

MS 是尾数的符号位,设置在最高位上。E 为阶码,有 n+1 位,为整数,其中有一位符 号位,设置在 E 的最高位上,用来表示正阶或负阶。M 为尾数,有 m 位,由 MS 和 M 组成 一个定点小数。MS=0,表示正号,MS=1,表示负号。 根据 IEEE 754 国际标准,常用的浮点数有两种格式,单精度浮点数和双精度浮点数。 单精度浮点数(32 位),阶码 8 位,尾数 24 位(内含 1 位符号位)。如下图所示:

其中,S是浮点数的符号位,1 位,0 表示正数,1 表示负数。M是尾数,单精度为 23 位,双精度为 53 位,用定点小数表示(通常使用补码) ,小数点放在尾数域的最前面。E: 阶码,单精度为 8 位,双精度为 11 位,阶符采用隐含方式,即采用移码方式来表示正负指 数。

1.2 非数值数据的表示
非数值数据,包括字符、图形图像以及声音等,下面将主要介绍字符和图形图像的编 码方法。

1.2.1 英文字符编码
字符是计算机处理的主要对象。字符编码就是规定用怎样的二进制码来表示字母、数

10

字及各种符号,以便使计算机能够识别、存储和处理它们。目前,使用最广泛的字符编码是 美国信息交换标准代码 ASCII(American Standard Code for Information Interchange) 。 ASCII 码已被国际标准化组织接受为国际标准,在世界范围内通用。 标准 ASCII 码使用 7 个二进位对字符进行编码,总共包含 128 个常用字符。从 0 到数 字 127 代表不同的常用符号,例如大写 A 的 ASCII 码是 65,小写 a 则是 97。
ASCII 值 控制字符 ASCII 值 控制字符 ASCII 值 控制字符 ASCII 值 控制字符 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 NUT SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI DLE DCI DC2 DC3 DC4 NAK SYN TB CAN EM SUB ESC FS GS RS US 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 (space) ! ” # $ % & , ( ) * + , . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 @ A B C D E F G H I J K L M N O P Q R X T U V W X Y Z [ \ ] ^ — 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 、 a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~ DEL

其中 0~32 以及 127 表示的是“回车”“换行”“退格”等控制字符,其余均为可显 、 、 示的普通字符,包括阿拉伯数字、大写英文字母、小写英文字母、常用标点符号等。各控制
11

字符的含义如下:
字符 NUL SOH STX ETX EOY ENQ ACK BEL BS HT LF 含义 空操作 字符 VT 含义 垂直制表 字符 SYN 含义 空转同步 信息组传送结束 作废 纸尽 换置 换码 文字分隔符 组分隔符 记录分隔符 单元分隔符 删除

标题开始 FF 正文开始 CR 正文结束 SO 传输结束 SI 询问字符 DLE 承认 报警 DC1 DC2

走纸控制 ETB 回车 移位输出 CAN EM

移位输入 SUB 空格 设备控制 1 设备控制 2 设备控制 3 设备控制 4 否定 ESC FS GS RS US DEL

退一格 DC3 横向列表 DC4 换行 NAK

仔细观察 ASCII 表可以发现,数字 0 的 ASCII 码为 48,其余数字的 ASCII 则为该数字 代表的数加 48; A 的 ASCII 为 65,依次加 1 便可以得出出 B 的 ASCII 为 66,C 的 ASCII 为 67 等等;小写字母的 ASCII 码则为对应大写字母的 ASCII 加 32. 计算机在存储字符时, 实际存储的是字符的 ASCII 码。 每个 ASCII 码以 1 个字节(Byte) 储存,而一个 ASCII 码只用了一个字节中七个二进制位,多出来的一位(最高位)在计算 机内部通常保持为 0。由于标准 ASCII 字符集字符数目有限,后来又将最高的一个位也编入 这套编码码中,成为八个位的扩展 ASCII(ExtendedASCII)码,扩展 ASCII 码加上了许多外 文和表格等特殊符号,成为目前常用的编码。

1.2.2、汉字编码
由于汉字比西文字符不仅数量多,而且字形复杂,所以用计算机处理汉字要比处理西 文字符困难得多,必须解决汉字的输入、存储、处理和输出等一系列技术问题。汉字处理技 术的关键是汉字编码问题。根据汉字处理过程中不同的要求,汉字编码可分为国际码、输入 码、机内码和字形码等几大类。 (一)汉字国标码 汉字国标码亦可称为汉字交换码,主要用于汉字信息处理系统之间或者通信系统之间 交换信息使用,简称 GB 码。该标准共收集常用汉字 6763 个,另外还有各种图形符号 682 个,共计 7445 个。6763 个汉字分成常用一级汉字和较少使用的二级汉字两个部分,其中一 级汉字 3755 个,按拼音字母顺序排列,二级汉字 3008 个,按偏旁部首排列。 GB 码规定每个汉字、图形符号都用两个字节表示,每个字节只使用低 7 位编码,因此 最多能表示出 128×128=16384 个汉字。 (二)汉字机内码 汉字在计算机内部其内码是唯一的。因为汉字处理系统要保证中西文的兼容,当系统 中同时存在 ASCII 码和汉字国标码时,将会产生二义性。例如:有两个字节的内容为 30H
12

和 21H,它既可表示汉字“啊”的国标码,又可表示西文“0”和“!”的 ASCII 码。为此, 汉字机内码应对国标码加以适当处理和变换。 GB 码的机内码为二字节长的代码,它是在相应 GB 码的每个字节最高位上加“1” ,即 汉字机内码=汉字国标码+8080H 例如,上述“啊”字的国标码是 3021H,其汉字机内码则是 B0A1H。再如,系表所示 的汉字“中华”的国标码和区位码。 汉字 中 华 国标码 8680(01010110 01010000)B 5942(00111011 00101010)B 汉字内码 (11010110 11010000)B (10111011 10101010)B

(三)汉字输入方法 大体可分为:区位码(数字码) 、音码、形码、音形码。 区位码将汉字编码码中的 6763 个汉字分为 94 个区,每个区中包含 94 个汉字(位) , 区和位组成一个二维数组,每个汉字在数组中对应一个唯一的区位码。汉字的区位码定长 4 位,前 2 位表示区号,后 2 位表示位号,区号和位号用十进制数表示,区号从 01 到 94,位 号也从 01 到 94。例如, “中”字在 54 区的 48 位上,其区位码为“54-48”“国”字在 25 , 区的 90 位上,其区位码为“25-90” 。 需要注意的是:汉字区位码并不等于汉字国标码,它们两者之间的关系可用以下公式 表示: 国标码=区位码(十六进制)+2020H 音码是音、形混合的编码。优点是大多数人都易于掌握,但同音字多,重码率高,影 响输入的速度。 形码:根据汉字的字型进行编码,编码的规则较多,难于记忆,必须经过训练才能较 好地掌握;重码率低。如:五笔。 音形码:将音码和形码结合起来,输入汉字,减少重码率,提高汉字输入速度; (四)字形码 是指供计算机输出汉字(显示或打印)字形用的二进制信息,也称字模或字形码。根 据采用的技术可划分为两种,位图点阵字模和矢量字模。早期采用的是位图点阵字模,一般 的点阵规模有 16× 16,24× 24,64× 等,每一个点在存储器中用一个二进制位(bit)存储。 64

例如,图是“大”的 16× 点阵字模。它将需 8× bit 的存储空间,每 8 bit 为 1 字节, 16 32 所以,需 32 字节的存储空间。在相同点阵中,不管其笔划繁简,每个汉字所占的字节数相

13

等。

点阵字模的一个缺点就是汉字在放大后会使汉字变成颗粒状,像是有马赛克拼成的, 从而影响字形美观。 矢量字模保存的是一个汉字的描述信息,比如一个笔划的起始、终止坐标,半径、弧 度等等。在显示、打印该汉字时,要经过一系列的数学运算才能输出结果,但理论上可以被 无限地放大,笔划轮廓仍然能保持圆滑,不会有失真现象。 所有汉字字及符号的字模的集合就是字库, 在计算机中通常以文件方式存在。 Windows 系统的字库在 FONTS 目录下,既有点阵字库也有矢量字库,如果字体扩展名为 FON,表示 该文件为点阵字库,扩展名为 TTF 则表示矢量字库。 (五)汉字地址码 汉字地址码是指每个汉字字形码在汉字字库中的相对位移地址,它与机内码之间存在 简明的对应转换关系。 (六)计算机处理汉字的过程模型 计算机中汉字处理的模型如图所示。 用户要输入汉字时通过键盘使用输入码进行输入, 输入法程序将输入码转换为汉字机内码存入内存; 输出时输出程序根据存储的汉字机内码获 取汉字汉字地址码, 再通过地址码在字库中找到相应汉字的字形码, 并将汉字字形码传送给 输出设备,输出设备根据字形码输出汉字。
输入汉字 用户 键盘 输入码 转换程序 机 内 码 字形编码 显示器/打印机 汉字库及程序 机内码 输出 存储器

汉字信息处理系统的模型
14

1.2.3 图形的表示方法
目前表示图形图像的流行技术可以划分为两类,位图技术(bit map technique)和矢量 技术(vector technique) 。前面介绍的点阵字模和矢量字模采用的是相同的技术。 在位图技术中,一幅图像被看成是由很多个点组成的,每一个点称为一个像素(pixel, 是 picture element 的缩写) 。计算机通过依次存储每个独立的像素的特性(主要是颜色、亮 度等特性)来存储图像。我们以最简单的单色图形来进行说明。单色图形包含的颜色仅仅 有黑色和白色两种,为了便于理解,我们可以想象把一个网格叠放到图形上。网格把图形 分成许多单元,每个单元就是一个像素。对单色图,每个像素不是黑色就是白色,如果像 素的颜色为黑色,则在计算机中用 0 来表示,如果像素的颜色为白色,则在计算机中用 1 来表示。这样网格的每一行就可用一串 0 和 1 来表示了,如图所示。

存储一幅单色位图图像 对彩色图形来说,其表示方法与单色图形类似,只不过每个像素都需要使用多个二进 制位来表示不同的颜色信息。有两种方法很普及,其中一种是 RGB 编码,这种编码中, 每个像素都被表示为红、绿、蓝三种颜色成分的亮度。每一个颜色的亮度通常要用一个字 节来表示,因此,要表示一个原始图像中的像素就需要 3 个字节的存储空间。 另外一种方法是采用一个“亮度”成分和两个颜色成分来描述一个像素。 “亮度”成分 基本上就是像素红、绿、蓝成分的总和,也就是像素中白光的数量,其他两个成分称为蓝 色度和红色度,它们分别取决于在像素中所计算的像素亮度和蓝或红光数量的差别。 为图技术的一个缺点是图像不能随意调节大小,基本上增大图像的唯一途径是放大每 一个像素,这样做的结果是使图像变成了马赛克拼图。解决这一问题的一种方法是采用矢 量技术。 矢量技术使用直线和曲线来描述图形,它将构成图形的元素分解成一些点、线、矩形、 多边形、圆和弧线等等,而这些元素都可通过数学公式计算获得的。矢量图是由点组成线,
15

线组成图形,描述图象的几何特性,精度很高,不会失真。例如,一幅花的矢量图形实际 上是由线段形成外框轮廓, 由外框的颜色以及外框所封闭区域的颜色决定花显示出的颜色。 由于矢量图形可通过公式计算获得,所以矢量图形文件体积一般较小。矢量图形最大 的优点是无论放大、缩小或旋转等不会失真;最大的缺点是难以表现色彩层次丰富的逼真 图像效果。Adobe 公司的 Illustrator、Corel 公司的 CorelDRAW 是众多矢量图形设计软件中 的佼佼者。大名鼎鼎的 Flash MX 制作的动画也是矢量图形动画。

1.2.4 声音和视频的数字化表示
自然界的声音是一种连续变化的模拟信息,可以采用 A/D 转换器对声音信息进行数字 化。声音文件的后缀名有:wav、mp3 等; 视频信息可以看成连续变换的多幅图像构成,播放视频信息,每秒需传输和处理 25 幅 以上的图像。视频信息数字化后的存储量相当大,所以需要进行压缩处理。视频文件后缀 名有:avi、mpg 等。

16

第 2 章 计算机系统组成原理
2.1 计算机系统组成
计算机系统由软件系统和硬件系统两部分组成。
运算器 中央处理器 主机 内存储器 硬件系统 输入设备 外部设备 输出设备 外存储器 计算机系统 操作系统 网络软件 系统软件 软件系统 编译软件 诊断软件 系统服务程序 程序设计语言 应用软件 办公软件包、数据库管理系统等 控制器

2.2 计算机的软件系统
计算机系统中的程序及相关文档被称为软件,所有程序及相关文档的总和称为软件系 统。程序是为实现一定功能,用计算机程序设计语言所编制的语句的有序集合。文档是描述 程序设计的过程及程序的使用方法等的有关资料。 程序是可由计算机执行, 而文档是不能执 行的。软件系统按其功能可分为系统软件和应用软件两大部分。 应用软件是指利用计算机的软、 硬件资源为某一应用领域解决某个实际问题而专门开发 的软件。 应用软件必须在系统软件的支持下才能运行。 最常见的应用软件是办公软件 (office 套件) ,包括文字处理软件(WorD.wps 等) 、演示文稿软件(PowerPoint) 、电子表格处理软 件(Excel)等。其余的还有图形图像处理软件,例如 photoshop、多媒体软件,如 3DMax、 flash 等等。还有数据库系统、程序开发软件、各种电脑游戏等等。 系统软件主要的功能是控制和维护计算机的正常运行、 管理计算机的各种资源来满足应 用软件的需要。 系统软件又可以分为两类, 一类是操作系统, 另一类是被称为实用软件 (utilty software)的软件单元。

17

2.3 计算机的硬件系统
计算机的硬件由中央处理器(CPU) 、内部存储器(简称内存) 、输入设备和输出设备等 部分组成。将这些设备的引脚插在计算机主电路板(称为主板 motherboard)相应的插槽上 再加上电源,就可组成一台完整的计算机。 CPU 是计算机的核心处理部件,内部集成了控制器和运算器等部件。运算器也被称为 算数/逻辑单元,主要包括执行加法减法等数据操作的电路,控制器主要包括控制协调计算 机各部件运行的电路。 CPU 每次操作能直接处理的二进制数据位数称为机器的字长,例如进行一次加法运算 时,进行加运算的两个数的为数,或是进行一次数据传输所能同时传输的数据位数。 为了能临时存放信息,CPU 内部还包含若干被称为寄存器的存储单元,这些寄存器又 被分为通用寄存器和专用寄存器。寄存器用于存放可立即进行运算的数据。 CPU 内部连接运算器、控制器、以及寄存器等部件的线路称为总线,为了区别于主板 上的连接 CPU、内存、外设等部件的系统总线,CPU 内部的总线被称为内部总线。

内部存储器简称内存,也被称为计算机的主存储器,用于存放正在执行的程序和数据。 CPU 只能直接执行和处理放入内存中的程序和数据。主存储器是由半导体存储器芯片组成 的。构成计算机内存存储器芯片由两种,一种是只读存储器(ROM ,Read Only Memory) , 另一种是随机存储器(RAM ,Random Access Memory) 。ROM 中的内容是计算机制造商在 计算机出厂前写入的,其内容一般情况下不可更改,断电后其内容不会丢失。ROM 通常用 于存放计算机的自检程序和引导程序等内容。RAM 就是我们通常所说的内存条,占主存的 绝大部分,断电后其所存储的信息将会丢失。主存相对造价高、速度快、但容量小。 随着技术的不断进步,CPU 的执行速度越来越快,但内存的读写速度却一直提高不大, 这样内存的性能就大大限制了 CPU 性能的发挥。为了解决这一问题,现在的计算机中一般 都配有一定数量的高速缓存。 高速缓存也是一种半导体存储器,它的速度要比内存要高的多,基本能与 CPU 的运行 速度相匹配,但造价较高,因而容量不能做的太大而充当主存。为了既能提高内存向 CPU 提供指令和数据的速度,又能保证有足够容量的主存空间,将高速缓存置于 CPU 与内存之 间,将 CPU 即将使用的数据和指令预先批量存入高速缓存中,让 CPU 从高速缓存中直接读

18

取指令和数据,从而提高计算机的整体性能。 内存是计算机的基本部件, 没有内存计算机是不能运行的。 高速缓存不是计算机系统必 须的部件。早期的计算机是没有高速缓存的。 辅助存储器(简称辅存或外存)包括磁盘、光盘等,相对造价低、容量大、信息可长期 保存,但读写速度较慢。目前常见的 U 盘也是一种辅助存储器,它的存储体是一种被称为 闪存芯片的半导体存储芯片。 综上所述,我们可以看到,计算机的存储系统包括以下四个层次: (1)CPU 内部的寄存器(Register) (2)高速缓冲存储器(Cache) (3)主板上的主存储器 (4)以外设形式出现的辅助存储器 四种存储器的读写速度依次递减,存储容量依次递增,造价递减。 存储器的容量单位 计算机中的所有信息都是用二进制编码表示的,即用“0”和“1”组成的串表示,因此存储 器的容量是指存储器能存放多少个二进制位 B.。通常 8 位编为一组,称为一个字节 B.。表 示存储器容量的单位有 KB.MB.GB 以及 TB 等。 1KB=210B 1MB=220B 1GB=230B 内存地址 一般把存储器中的一个字节称为一个内存单元。 为了正确地访问这些内存单元, 必须为 每个内存单元编上号。 根据一个内存单元的编号即可准确地找到该内存单元。 内存单元的编 号就是所谓内存地址。

输入输出设备简称为 I/O 设备,也被称为外部设备(Peripheral) ,主要用于计算机用户 与计算机的交互。I/O 设备分为两种,一种是输入(Input)设备,如键盘(标准输入设备) 、 鼠标等,另一种是输出(Output)设备,如显示器(标准输出设备) 、打印机等。 外部设备和主机间进行连接的电路被称为 I/O 接口,也称为外设接口,主要完成信号 变换、数据缓冲、联络控制等工作。一些比较简单的 I/O 接口电路通常与电脑主板一体, 而较复杂的 I/O 接口电路制成独立的电路板被称为接口卡,如网卡、显卡等。 在计算机内部,将 CPU、内存、外部存储器、输入输出设备等连接在一起的是一块被 称为主板(mainboarD.的电路板,主板就是主电路板的意思,又叫系统板(systemboard)或母板 (motherboard),是计算机最基本的也是最重要的组成部件之一。 主板一般为矩形电路板,上面安装了组成计算机的主要电路系统,一般有 BIOS 芯片、 I/O 控制芯片、键盘和面板控制开关接口、指示灯插接件、扩充插槽、主板及插卡的直流电

19

源供电接插件等元件。 主板上用于连接各部件的线路被称为系统总线, 它连接着主板上的各 接口电路以及 CPU 插槽、内存插槽等部件。 电路板上用于连接计算机各主要部件的导线被称为总线(Bus) ,为区别于内部总线, 主板上的总线称为系统总线。系统总线是计算机各种功能部件之间传送信息的公共通信干 线,它是由导线组成的传输线束,按照所传输的信息种类,总线可以划分为数据总线、地址 总线和控制总线,分别用来传输数据、数据地址和控制信号。总线是 CPU、内存、输入、 输出设备传递信息的公用通道, 主机的各个部件通过总线相连接, 外部设备通过相应的接口 电路再与总线相连接, 从而形成了计算机硬件系统。 采用总线结构连接各部件使得计算机的 组合灵活、扩展方便。 数据总线(DB:Data Bus) :处理器与存储器或外设交换信息的通道,个数(条数)是 一次能够传送数据的二进制位数。 地址总线(AB :Address Bus ) :指定存储器或外设的具体单元,个数反映访问的主存 储器容量或外设范围。 控制总线(CB :Control Bus ) :传送控制信号,比如 CPU 向存储器发送的数据读或 写命令等。

2.2 计算机的工作原理
计算机工作的过程其实就是执行程序的过程。 而程序本质上就是控制计算机完成特定功 能的一组有序的指令的集合,或简称为指令序列。 指令 指令是能被计算机识别并执行的一种二进制代码, 一条指令完成一种基本操作。 指令中 明确规定了计算机从内存的哪个位置取数, 进行什么操作, 然后将操作结果送到什么地方去 等步骤。 指令通常分为操作码和操作数两部分。 操作码规定了操作的类型或性质, 被控制器译码 后将按一定的时间节拍产生一系列完成该指令功能的控制信号。 操作数则指明了被操作的数 据或者被操作数据的存储位置。 操作码 操作数

指令分类 数据传送指令:专门用于 CPU 和内存之间的数据传递 数据处理指令:进行加减乘除以及逻辑运算等功能 程序控制指令:控制程序执行流程 输入输出指令:完成外部设备和主机之间的数据交换 其它指令 :对计算机的硬件进行管理等。 指令系统 一个计算机系统能执行的所有指令的集合被称为指令系统。从系统结构的角度看,它是 系统程序员看到的计算机 CPU 的主要属性。不同计算机的指令系统包含的指令种类和数目 也不同。一般均包含算术运算型、逻辑运算型、数据传送型、判定和控制型、移位操作型、 位(位串)操作型、输入和输出型等指令。 指令系统是表征一台计算机性能的重要因素,它的格式与功能不仅直接影响到机器的硬 件结构,而且也直接影响到系统软件,影响到机器的适用范围。 目前我们常见的计算机的 CPU 都是采用 x86 指令集的,不论是台式机还是笔记本电脑, 它们都属于同一类型的 CPU,不管是 INTEL 生产的还是 AMD 生产的。除此之外,世界上
20

还有比这些更快的 CPU,比如 Alpha,但它们不是用 x86 指令集,不能使用数量庞大的基于 x86 指令集的程序,如 Windows。之所以说指令系统是一个 CPU 的根本属性,就是因为指 令系统决定了一个 CPU 能够运行什么样的程序。 中国国产的龙芯系列 CPU 的指令系统也不是基于 x86 的, 而是基于 MIPS 的, 因此不能 运行广为流行的 Windows 操作系统,这也正是我们几乎见不到龙芯电脑的原因。 另外,目前流行的智能手机其本质也是一台计算机,但它们的 CPU 基本也基本都不是 基于 x86 的,多数都是基于 ARM 的。 计算机的基本工作原理——存储程序原理 预先把指挥计算机如何进行操作的指令序列(即程序)和原始数据输入到计算机内存中, 然后启动计算机; 运行时,在控制器控制下,从内存中取出第 1 条指令送入控制器,经控制器分析后产生 完成该指令的各种定时控制信号; 在这些信号控制下完成该指令规定的操作, 包括存储器中取出数据、 进行指定的运算和 逻辑操作、结果送入内存等。 接下来,取出第 2 条指令,在控制器的指挥下完成规定操作,依此进行下去,直到遇到 停止指令。 程序与数据一样存储, 按照程序编排的顺序, 一步一步地取出指令并自动地完成指令规 定的操作,这是计算机最基本的工作原理。

这一原理最初是由美籍匈牙利数学家冯?诺依曼于 1945 年提出来的,故称为冯?诺依曼 原理。虽然现在的计算机系统从性能指标、运算速度、工作方式、应用领域和价格等方面与 当时的计算机有很大差别,但基本结构没有变。 计算机从取指令到执行完指令所用的时间被称为指令周期, 不同指令的指令周期并不一 定相同。 时钟频率 每条指令的执行都需要计算机的不同部件分别进行若干操作,这些操作被称为微操作。 一条指令的所有微操作中,有些是可以并行执行的,有些则必须按一定的先后顺序执行。 每个微操作的执行都是需要花费一定的时间,不同微操作所需要的时间往往是不同的, 为了简化设计, 一般将大多数微操作执行完成所需要的时间规定为一个机器周期, 那些在一 个机器周期内不能完成的微操作可让它用 2 个机器周期甚至 3 个机器周期完成。

21

性能高的计算机的机器周期要比性能低的计算机的机器周期要短, 也就是完成一个微操 作所需的时间要少,因而执行同一条指令的时间也要短,因此执行速度也快。 计算机的机器周期长短是由一个时钟控制的, 该时钟周期性地发出脉冲信号, 因此也被 称为时钟脉冲源, 计算机的各部件就是通过这个脉冲源发出的脉冲信号来开始执行每一个微 操作的。该时钟每秒发出的脉冲信号数量称为计算机的时钟频率。 时钟频率越高,则机器周期越短,计算机执行速度越快。

2.3 操作系统
操作系统是控制和管理计算机上的所有软件和硬件资源,方便用户使用计算机的软件, 它是硬件与应用程序之间的接口。 操作系统提供了用户存储查找文件的方法、 提供了用户执 行运行程序的方法、还提供了用户应用程序运行的环境。 操作系统最著名的例子是微软公司的 Windows, 目前已有很多版本, 目前广泛使用的版 本是 Windows XP 和 Windows7,最新的版本 Windows 8 也日渐普及。操作系统的另一个典 型例子是 UNIX,但它通常是较大型的计算机上使用的操作系统,一个例外是苹果公司发布 的用于 Mac 机的操作系统 Mac OS 的核心,使用的也是 UNIX。既能运行于大型机也能运行 于微型机的 Linux 操作系统是一个非专利产品, 它是由一些计算机爱好者以非盈利目的开发 的,我们可以免费获得它的源代码和相关文档。目前,它在计算机爱好者和计算机专业的学 生中已十分流行,而且被公认为是当今可使用的最可靠的操作系统之一。正因如此,许多商 业公司以更实用的方式包装销售 Linux 产品,比如我国的红旗 Linux。 实用软件是由一些能够扩充操作系统功能的软件单元组成的。 典型的例子包括数据压缩 解压缩、多媒体播放软件、网络通信软件等。目前实用软件和应用软件的概念已变得十分模 糊了。

操作系统分类 操作系统按用户界面可分为字符界面(命令行界面)操作系统和图形用户界面(GUI) 操作系统。字符界面操作系统的例子是 DOS 以及早期的 Linux、Unix;而图形用户界面的 操作系统则有微软的 Windows、苹果的 Macintosh OS 等,现在的 Lnux、Unix 均提供 GUI 界面,图形用户界面已成为主流。 按用户数分为单用户操作系统和多用户操作系统。 多用户操作系统是指多人同时使用一 台计算机。Windows 是单用户的。多用户的例子是小型机或大型机上的 Unix 操作系统。 按任务数可分为单任务操作系统和多任务操作系统。多任务是指同时能执行多个程序。 Windows 是单用户多任务。 按系统功能又可分为批处理系统、分时操作系统、实时操作系统等、网络操作系统、分
22

布式操作系统等。 网络操作系统是指利用网络低层所提供的数据传输功能, 为网络用户提供局域网共享资 源管理服务和其他网络服务功能, 单机操作系统则只为本地用户服务, 不能满足网络环境的 要求。 操作系统的功能 (1)处理机管理 处理机管理的目的是有效地、合理地分配 CPU 的时间。根据管理方式的不同,操作系 统可分为两种,单道程序系统和多道程序系统。 单道程序系统是指任一时刻只允许一个程序在系统中执行, 一个程序执行结束后才能执 行下一个程序。 多道程序系统则是多道程序同时在执行, 计算机内存中同时存放了几道相互 独立的程序,宏观上并行(同时在执行) ,微观上串行,各程序轮流地占有 CPU,交替执行, 这种系统也称为并发系统。 计算机上, 一个正在执行的程序被称为进程。 因此, 在多任务操作系统中存在多个进程。 现在的主流操作系统均为多任务操作系统。 (2)存储(内存)管理 计算机内存是 CPU 可以直接存取的存储器。 操作系统的存储管理主要功能有 4 个方面: 存储器分配:多个进程共享存储器,分配、释放存储器。 地址的转换:程序员编写程序使用的逻辑地址(从 0 开始)转换为实际内存地址。 虚拟内存:用硬盘空间模拟内存 信息的保护: 防止一个进程的存储空间被其它的进程破坏, 主要采用软件和硬件结合的 保护措施。 (3)设备管理 当前操作系统的设备管理的功能主要用三个方面, 一是提供对连接到计算机上的外部设 备的进行集中、统一管理,例如,Windows 系统中的设备管理器。 二是通过通道技术和缓冲区技术来提高设备的使用效率。 设备缓冲区是介于两个设备或 设备与应用程序之间传递数据的内存区域,提供给不同速度的设备之间传递数据。 三是提供设备的即插即用功能。连接到计算机上的不同的设备需要有不同的驱动程序, 使用设备之前,该设备的驱动程序必须被安装。除安装驱动程序外,多数设备还必须要正确 配置参数才能使用。 因此, 给计算机添加设备是一件比较繁琐的事情, 非专业人员很难操作。 为了解决这一问题,现代的操作系统引入了“即插即用”的概念。 即插即用(Plug and Play,简称 PnP)是指把设备连接到计算机上后无需手动配置可以 立即使用。 即插即用技术需要设备和操作系统的支持, 目前计算机上的几乎所有设备都实现 了即插即用功能。 通用即插即用 UPnP 是指让计算机自动发现和使用基于网络的硬件设备, 例如网络打印 机、Internet 网关和消费类电子设备等,可实现“零配置”和“隐性”的联网过程。 (4)文件系统管理 文件是存放在外存上的一组相关信息的集合,它可以是程序、文档、图片、声音或视频 信息等 。 文件必须有名字,即文件名。文件名通常由主文件名和扩展名组成,中间用“.”连接。 其格式为“文件名.扩展名” ,例如:Iexplore.exe。Windows 系统的文件的命名规则如下: 2. 文件名长度最长 255 个字符 3. 不能出现的符号:\ / : “ < > | ? * 4. 最后一个“.”后面的部分称为文件的扩展名,通常用来表示文件的类型,例如.EXE 表示是 Windows 的可执行文件,.doc 则是 Word 文档,TXT 为纯文本文件。下表

23

为 Windows 系统中常见的文件扩展名所代表的文件类型。 文件类型 可执行程序 源程序文件 Office 文档 流媒体文件 压缩文件 网页文件 图像文件 音频文件 扩展名 EXE、COM C、CPP、BAS DOC、XLS、PPT WMV、RM、QT ZIP、RAR HTM、ASP BMP、JPG、GIF WAV、MP3、MID 说 明 可执行程序文件 程序设计语言的源程序文件 Word、Excel、Powerpoint 创建的文档 能通过 Internet 播放的流式媒体文件 压缩文件 前者是静态的,后者是动态的 不同格式的图像文件 不同格式的声音文件

需要注意,UNIX 及 LINUX 中文件名有大小写区别,而 Windows 中无大小写区别。 除文件名外,每个文件还具有文件大小、占用存储空间大小、文件建立和修改的日期与 时间、 文件的所有者信息以及文件的访问权限等属性。 Windows 文件访问权限属性有三种只 读属性、隐藏属性、和归档属性。 磁盘管理 硬盘分区:硬盘是 PC 的主要存储部件,使用时通常划分成几个逻辑上独立的区域(最 多 4 个) ,这些磁盘分区被称为卷。磁盘分区一是为了方便管理磁盘上的众多文件,二是为 了安装不同的系统,如 Windows XP、Linux 等。 硬盘分区有两类,主分区和扩展分区。 住分区只能创建一个逻辑盘, 磁盘上的多个主分区通常用于安装不同操作系统。 扩展分 区中可创建多个逻辑盘,但一个硬盘只能创建一个扩展分区。个人电脑中,一块磁盘能划分 的主分区和扩展分区总数不能超过 4。 为了区分不同的磁盘或逻辑磁盘,Windows 操作系统通常分别为它们分配一个盘符。 软盘的盘符为 A:和 B:硬盘的逻辑盘的盘符从 C:开始,最多可到 Z: 。光盘、U 盘的盘 符作为硬盘的逻辑盘分配。 目录/文件夹:建立目录/文件夹是为了便于文件管理。 路径:指明文件的存放位置。Windows 中路径的格式为: <盘符>\<文件夹名>\??\<文件夹名>\<文件名>

2.4 计算机的发展
在计算机发展史上,差分机和分析机占有重要的地位。它们的研制者查尔斯·巴贝奇 (Charles Babbage,1791-1871)是英国人。 英国著名诗人拜伦的女儿 ada lovelace 曾设计了巴贝奇分析机上解伯努利方程的一个程 序。她甚至还建立了循环和子程序的概念。由于她在程序设计上的开创性工作,ada lovelace 被称为世界上第一位程序员。 1946 年 2 月 15 日, 世界上第一台电子计算机 ENIAC (Electronic Numerical Integrator And Calculator—电子数字积分器和计算器)在美国宾夕法尼亚大学诞生。 c. 第一代计算机
24

1946-20 世纪 50 年代末,电子管时代计算机。主要特点: ①采用电子管作为计算机的主要逻辑部件。体积大,耗电量大,寿命短,可靠性差,成 本高。 ②采用电子射线管、磁鼓存储信息,容量很小。 ③输入输出装置落后,主要使用穿孔卡片,速度慢,容易出错,使用不方便。 ④软件上,使用机器语言和汇编语言编程。 这一时期的典型机器: 国外的:ENIAC 、UNIVAC。 国内的:103、104 等。 d. 第二代计算机 1958-1964 年,晶体管计算机时代。主要特点: ①采用晶体管作为计算机的主要逻辑部件,体积减小, 重量减轻,成本下降,能耗降 低,可靠性和运算速度到了提高。 ②采用磁芯作主存储器,磁盘、磁鼓作外存储器。 ③软件方面有了系统软件(监控程序) ,提出了操作系 统的概念,出现了高级语言, 如 FORTRAN,ALG0L60 等。 这一时期的典型机器:国外的:IBM7090 等,国内的:441B 等 e. 第三代计算机 1964-1972 年,集成电路计算机时代。主要特点: ①采用中、小规模集成电路做主要逻辑部件,从而使计算机体积更小,重量更轻,耗电 更省,寿命更长,成本更低,运算速度有了更大的提高。 ②采用半导体存储器做主存储器, 存储容量和存储速度有了大幅度的提高, 增强了系统 的处理能力。 ③软件方面,系统软件有了很大的发展,出现了分时操作系统,多用户可以共享计算机 资源。 ④在程序设计方法上, 采用了结构化程序设计, 为研制更加复杂的软件提供了技术上的 保证。 这一时期的典型机器:国外 IBM-360 等;国内 709 等。 f. 第四代计算机 1972 年至今,大规模、超大规模集成电路计算机时代。主要特点: ①采用大规模、超大规模集成电路作基本逻辑部件,使计算机体积、重量和成本大幅度 的降低,运算速度和可靠性大幅度的提高。 ②作为主存储器的半导体存储器,其集成度越来越高,容量越来越大;外存储器除了广 泛地使用软、硬磁盘外,还引进了光盘。 ③各种使用方便的输入输出设备相继出现,如鼠标、图像扫描仪、纯平及液晶显示器、 激光打印机、绘图仪等。 ④各种实用软件层出不穷,极大地方便了用户。 ⑤多媒体技术崛走,计算机集图像、图形、声音与文字处理于一体,在信息处理领域掀 起了一场革命。 计算机分类 计算机按其性能、价格和体积大小分为巨型计算机、大型计算机、小型计算机和微型计 算机等类型。 微型机计算机的出现主要是由于集成电路技术的出现。 由于采用了大规模和超大规模集 成电路技术,能把原来体积很大的中央处理机也就是 CPU(Center Processing Unit)的电路

25

集成在一片面积很小(仅十几平方毫米)的电路芯片上,称为微处理器(Microprocessor, 简称μ P) ,微处理器的出现开创了微型计算机的新时代。 摩尔定律:计算机的 CPU 性能“每 18 个月,集成度将翻一翻,速度将提高一倍,而其 价格将降低一半” ,集成度表明微处理器的生产工艺水平,常用芯片上集成的晶体管数量来 表达。

2.5 程序设计语言及其发展
编写程序所使用的语言就是程序设计语言。程序设计语言的发展经历了三个阶段: 机器语言→汇编语言→高级语言 (1)第一代语言—机器语言 依赖于机器,不同的计算机有不同的语言,它由一系列指令组成,每条指令用 二进制 或八进制编码,主要在上世纪 50 年代初使用,例如,0000001011001111 表示加法指令。机 器语言是唯一计算机可以直接执行的语言。 (2)第二代语言—汇编语言 汇编语言也称为符号语言, 用符号代替机器语言中的二进制编码。 上世纪 50 年代出现, 至今仍有使用。 如:MOV AL , 5 计算机不能直接识别和执行汇编语言,它必须经过一个汇编程序(系统软件)转换成机 器语言后才能执行,它仍依赖于机器,不同的计算机有不同的汇编语言,不能通用。 (3)第三代语言—高级语言 高级语言也叫算法语言,计算机不能直接识别和执行。上世纪 60 年代出现。一般地, 把用高级语言或汇编语言编写的程序称为源程序。源程序须经过编译程序(系统软件)编译 成机器语言程序(目标程序)后才能执行,过程如下:

高级语言程序的执行除了编译执行方式外还有另外一种方式, 即解释执行方式。 在这种 执行方式中, 一次只读一行源程序, 将该行源程序翻译成机器语言并执行, 翻译结果不保存。 这种方式下, 每次运行用户程序时都必须要用解释程序。典型的代表是早期的 BASIC 语言, PCLogo 等。 (4)第四和第五代语言 第四代语言—非过程化语言 它只描述需要求解的问题是什么,典型的如 SQL 语言(结构化查询语言) ,例如: select “男生” from “ 03 级” where “年龄< 21” 第五代语言—智能化语言 主要为人工智能领域设计的,如专家 系统,知识库系统等 (5)典型的高级语言 FORTRAN 语言。诞生于 20 世纪 50 年代,是世界上第一个被正式推广使用的高级语 言。它是为科学、工程问题或企事业管理中的那些能够用数学公式表达的问题而设计的,其
26

数值计算的功能较强。至今仍是数值计算领域所使用的主要语言。 BASIC 语言。诞生于 20 世纪 60 年代中后期,该语言简单易学,是一种会话型语言, 适合初学者学习。至今 Basic 语言已有许多高级版本,尤其是 Visual Basic,给广大用户在 Windows 环境下开发软件带来了极大的方便。 ALGOL 语言。 诞生于 20 世纪 60 年代初期, 是建立在坚实理论基础上的程序设计语言, 60 年代曾被认为是最有前途的程序设计语言,但现在已经很少有人使用了。 PASCAL 语言。 诞生于 20 世纪 70 年代初, 是一种结构化程序设计语言, 适合于教学、 科学计算、数据处理和系统软件开发等。目前逐步被 C 语言所取代。 C 语言。诞生于 20 世纪 70 年代初,80 年代开始风靡全世界,适应于系统软件、数 值计算、数据处理等,目前成为高级语言中使用最多的语言之一。 C++语言。诞生于 20 世纪 80 年代,是作为 C 语言的改进而开发的,主要是在 C 语言 的基础上增加了对面向对象程序设计的支持。 Java 语言。诞生于 20 世纪 90 年代,是一种新型的跨平台分布式程序设计语言,具有 简单、安全、稳定、可移植性强等特性,将成为未来网络环境上的“世界语”。Java 语言是 基于 C++的,其最大特点是“一次编写,处处运行”。

2.5 信息技术与信息社会
信息是经过加工的、 能够对接受者的行为和决策产生影响的数据。 信息技术 (Intermation Technology,IT)是关于信息的产生、发送、传输、接受、变换、识别、控制等应用技术的 总称,是由计算机技术、通信技术、微电子技术结合而成,有时也叫做“现代信息技术” 。 现代信息技术主要有以下特点: 数字化:大量信息可以被压缩,并以光速进行传输。 多媒体化:文字、声音、图形、图像、视频等信息媒体与计算机集成在一起,以接近于 人类的工作方式和思考方式来设计与操作。 高速度、网络化 (3)智能化:在以 WEB 技术为核心的超媒体的世界里,软件代理收集任何可能想要 在网络上取得的信息。 信息社会就是信息化社会的简称, 信息化包含两层意思, 一是指人们的一切活动要以信 息为中心,社会经济活动要借助于信息展开、定向;二是指社会生产部门的技术装备、管理 方法、人员素质、工作效率都能达到现代信息技术所要求的水平。信息技术是信息社会的基 础。

27

第 3 章 算法与程序设计方法
3.1 算法的基本概念
计算机能解决问题, 是因为人们事先安排好了计算机解决问题的方法和执行步骤, 我们 将未解决某一个问题而采取的方法和步骤称为算法。 更准确一点说, 计算机算法可以理解为 由基本运算按照规定的运算顺序所构成的完整的解题步骤, 或者看成按照要求设计好的有限 的确切的计算序列, 并且这样的步骤和序列可以解决一类问题。 利用计算机解题的过程实际 上是在让计算机实施某种算法。 对同一个问题,往往会有不同的算法。 例:有 8 个小球,其中 7 个重量相同,仅有一个重量较重,用天平如何找出那个较重的 小球? 算法 1 把 8 个小球分成 4 组,依次将这 4 组放在天平上,直到某一组天平不平衡时, 就可以确定最重的小球。 最多需要称 4 次。 算法 2: 第一步:从 8 个小球中任取 6 个,将这 6 个小球每边 3 个置于天平上称; 第二步:若天平平衡,则最重的小球在剩余的两个小球中,只需将那两个小球在天平上 再称一次则可; 第三步:若天平不平衡,则重的小球必定在较重一边的那三个小球中,这时,只需将较 重的一边的三个小球中任取两个再称一次, 如果天平平衡, 则剩余的那个小球就为要找的小 球,若不平衡,则重的那一边的小球就是要找的小球。 算法 2 需要 2 次称重就可以找到较重的小球,因此,从操作所用的时间方面,算法 2 要比算法 1 好。 作为练习,请设计一个算法,从 12 个小球中找出较重的一个小球来,当然这 12 个小球 中仍然是有 11 个同样重,一个比其余 11 个要重一些。并计算一下,你的方法需要称重几次 才能找出。 1. 算法的基本特征 ⑴有穷性:一个算法其操作步骤应当是有限的; ⑵确定性:算法中的每一个步骤应当有确定的意义,不能有二义性;对于相同的输入必 须有相同的执行结果。 ⑶有效性:算法中的每一个步骤应当正确、可行,并且能有效地执行; ⑷有零个或多个输入:执行算法时需要从外界获取的信息; ⑸有一个或多个输出:执行算法后应当得到正确的结果。 2. 算法的基本运算和操作 算法的基本运算和操作包括: 算术运算、 逻辑运算、 关系运算、 数据传输 (变量赋值等) 。 3. 算法的基本控制结构与描述方法 算法中各操作之间的执行顺序称为算法的控制结构。 一个算法一般都可以用顺序、 选择、 循环 3 种基本控制结构组合而成。 描述算法的工具通常有自然语言、流程图、N-S 结构化流程图、算法描述语言等。 (1)用自然语言表示算法 ——用人们日常使用的语言和语序来表示算法。
28

例:输入 n 个整数,输出其中最大的数。 用自然语言描述算法如下: 设置变量:n 代表整数的个数, num 代表参与取值比较的整数,i 代表已参与取值比较 的整数个数,max 代表 n 个整数中的最大数。 步骤 1:从键盘输入一个整数给 n(设 n=5) ,将 1=>i ; 步骤 2:从键盘输入一个整数给 num,再将 num=>max; 步骤 3:如果 i<n,再从键盘输入一个整数给 num; 步骤 4:如果 num>max,将 num=>max,否则 max 的值为原值; 步骤 5:i+1=>i,如果 i<n,重复步骤 3 和步骤 4;否则输出 max 的值,即输出 n 个整 数中的最大数。 (2)用伪代码表示算法——一种接近于程序设计语言,但又不受语言语法约束的算法 表示法。 输入 n 个整数,输出其中最大的数。 input n /*总共输入数的个数*/ input num /*输入第一个数存入变量 num 中*/ max=num /*第一个数有可能是最大值*/ i=1 /*已输入了一个数 */ while i<n do /*如果输入的数的个数少于 n 就循环执行下面的操作*/ input num /*再输入一个数放入 num 中*/ if num>max then /*如果输入的数比 max 中的数大,就将刚输入的数存入 max 中*/ max=num end if i=i+1 /*输入数的个数增加 1(计数)*/ end do /*要循环执行的操作到本行为止*/ print max /*输出最大数*/ (3)用流程图表示算法——用一些图框和方向线表示算法的图形表示法。 常用流程图符号及含义如下:

上面例子的算法用流程图表示为:

29

(4)用 N-S 流程图表示算法——用一些基本结构图框来表示算法的图形表示法。 基本结构图框及含义如下:

上面例子的算法用 N-S 图表示为:

4. 算法基本设计方法 算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。 5. 算法复杂度 算法复杂度包括时间复杂度和空间复杂度。 算法的时间复杂度是指执行算法所需要的计 算工作量。同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的 计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开 这些与计算机硬件、软件有关的因素,可以认为一个特定算法"运行工作量"的大小,只依赖 于问题的规模(通常用整数 n 表示) ,它是问题规模的函数。即 算法的工作量=f(n) 算法的空间复杂度是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包

30

括算法程序所占的空间、 输入的初始数据所占的存储空间以及算法执行过程中所需要的额外 空间。 其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存 储空间。如果额外空间量相对于问题规模来说是常数,则称该算法是原地工作的。在许多实 际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术,以便尽量减少不必要的 额外空间。

3.2

结构化程序设计

1. 结构化程序设计的原则 结构化程序设计方法引入了工程思想和结构化思想, 使大型软件的开发和编程得到了极 大的改善。软件人员在进行程序设计时,首先应集中考虑主程序的算法,写出主程序后再动 手逐步完成子程序的调用。而对这些“子程序”也可以用调用主程序的方法逐步完成其下一 层的调用。这就是自顶向下、逐步细化、模块化的程序设计。 ① 自顶向下:先考虑整体,再考虑细节;先考虑全局目标,再考虑局部目标; ② 逐步求精:对复杂问题应设计一些子目标作为过渡,逐步细化; ③ 模块化:把程序要解决的总目标分解为分目标,再进一步分解为具体的小目标,把 每个小目标称为一个模块。 限制使用 goto 语句:在程序开发过程中要限制使用 goto 语句。 2. 结构化程序的基本结构 结构化程序的基本结构有三种类型:顺序结构、选择结构和循环结构。 ① 顺序结构:是最基本、最普通的结构形式,按照程序中的语句行的先后顺序逐条执 行; ② 选择结构:又称为分支结构,它包括简单选择和多分支选择结构; ③ 循环结构:根据给定的条件,判断是否要重复执行某一相同的或类似的程序段。循 环结构对应两类循环语句: 先判断后执行的循环体称为当型循环结构; 先执行循环体后判断 的称为直到型循环结构。

3.3

面向对象方法

面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 1. 对象 通常把对象的操作也称为方法或服务。 属性即对象所包含的信息, 它在设计对象时确定, 一般只能通过执行对象的操作来改变。 属性值应该指的是纯粹的数据值,而不能指对象。 操作描述了对象执行的功能,若通过信息的传递,还可以为其他对象使用。 对象具有如下特征:标识惟一性、分类性、多态性、封装性、模块独立性。 2. 类和实例 类是具有共同属性、 共同方法的对象的集合。 它描述了属于该对象类型的所有对象的性 质,而一个对象则是其对应类的一个实例。 类是关于对象性质的描述, 它同对象一样, 包括一组数据属性和在数据上的一组合法操 作。 3. 消息 消息是实例之间传递的信息, 它请求对象执行某一处理或回答某一要求的信息, 它统一
31

了数据流和控制流。 一个消息由三部分组成:接收消息的对象的名称、消息标识符(消息名)和零个或多个 参数。 4. 继承 广义地说,继承是指能够直接获得已有的性质和特征,而不必重复定义它们。 继承分为单继承与多重继承。单继承是指,一个类只允许有一个父类,即类等级为树形 结构。多重继承是指,一个类允许有多个父类。 5. 多态性 对象根据所接受的消息而做出动作, 同样的消息被不同的对象接受时可导致完全不同的 行动,该现象称为多态性。

32

第7章

数据结构

7.1 数据结构的基本概念
数据结构指相互有关联的数据元素的集合。数据结构研究 3 个方面的内容: ① 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; ② 在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; ③ 对各种数据结构进行的运算。 数据的逻辑结构是对数据元素之间的逻辑关系的描述, 它可以用一个数据元素的集合和 定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通 常记为 D;二是 D 上的关系,它反映了数据元素之间的前后件关系,通常记为 R。一个数据 结构可以表示成:B=(D,R) 其中,B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系,一般用二元组来 表示。 例如,如果把一年四季看作一个数据结构,则可表示成:B =(D,R) D ={春季,夏季,秋季,冬季} R ={(春季,夏季),(夏季,秋季),(秋季,冬季)} 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 (也称数据的物理 结构) 。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表 示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系) ,在数据的存储 结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构, 常用的存储结构有顺序、 链接 等存储结构。 顺序存储方式主要用于线性的数据结构, 它把逻辑上相邻的数据元素存储在物理上相邻 的存储单元里,结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域, 用指针来体现数据元素之间逻辑 上的联系。

7.2 线性结构和非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类 型:线性结构与非线性结构。 如果一个非空的数据结构满足下列两个条件: ① 有且只有一个根结点; ② 每一个结点最多有一个前件,也最多有一个后件。 则称该数据结构为线性结构。 线性结构又称线性表。 在一个线性结构中插入或删除任何 一个结点后还应是线性结构。栈、队列、串等都为线性结构。 如果一个数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据 结构都是非线性结构。 线性表的顺序存储结构具有以下两个基本特点:

33

① 线性表中所有元素所占的存储空间是连续的; ② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 元素 ai 的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,ADR(a1)为第一个元素的地址,k 代 表每个元素占的字节数。 (3)顺序表的运算有查找、插入、删除 3 种。

7.3



栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。 在栈中, 一端是封闭的, 既不允许进行插入元素, 也不允许删除元素; 另一端是开口的, 允许插入和删除元素。通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素 时称为空栈。栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是 最先被插入的元素,从而也是最后才能被删除的元素。 栈是按照“先进后出”或“后进先出”的原则组织数据的。例如,枪械的子弹匣就可以 用来形象的表示栈结构。 子弹匣的一端是完全封闭的, 最后被压入弹匣的子弹总是最先被弹 出,而最先被压入的子弹最后才能被弹出。 栈的基本运算有 3 种:入栈、退栈与读栈顶元素。 (1)入栈运算:入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即 top 加 1) 然后将新元素插入到栈顶指针指向的位置。 , 当栈顶指针已经指向存储空间的最后 一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈"上溢"错误。 (2)退栈运算:退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈 顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针减一(即 top 减 1) 。当栈顶指 针为 0 时,说明栈空,不可进行退栈操作。这种情况称为栈的"下溢"错误。 (3)读栈顶元素:读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除 栈顶元素, 只是将它赋给一个变量, 因此栈顶指针不会改变。 当栈顶指针为 0 时, 说明栈空, 读不到栈顶元素。 注意:栈是按照"先进后出"或"后进先出"的原则组织数据,但是出栈方式有多种选择, 在考题中经常考查各种不同的出栈方式。

7.4

队列

队列是只允许在一端进行删除, 在另一端进行插入的顺序表, 通常将允许删除的这一端 称为队头,允许插入的这一端称为队尾。当表中没有元素时称为空队列。 队列的修改是依照先进先出的原则进行的, 因此队列也称为先进先出的线性表, 或者后 进后出的线性表。例如:火车进遂道,最先进遂道的是火车头,最后是火车尾,而火车出遂 道的时候也是火车头先出,最后出的是火车尾。若有队列: Q =(q1,q2,?,qn) 那么,q1 为队头元素(排头元素) ,qn 为队尾元素。队列中的元素是按照 q1,q2,?, qn 的顺序进入的,退出队列也只能按照这个次序依次退出,即只有在 q1,q2,?,qn-1 都 退队之后,qn 才能退出队列。因最先进入队列的元素将最先出队,所以队列具有先进先出 的特性,体现“先来先服务”的原则。 队头元素 q1 是最先被插入的元素, 也是最先被删除的元素。 队尾元素 qn 是最后被插入 的元素, 也是最后被删除的元素。 因此, 与栈相反, 队列又称为 “先进先出” (First In First
34

Out,简称 FIFO) 或“后进后出” (Last In Last Out,简称 LILO)的线性表。 入队运算是往队列队尾插入一个数据元素;退队运算是从队列的队头删除一个数据元 素。 队列的顺序存储结构一般采用队列循环的形式。循环队列 s=0 表示队列空;s=1 且 front=rear 表示队列满。计算循环队列的元素个数: “尾指针减头指针” ,若为负数,再加 其容量即可。

7.5

链表

在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数 据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结 点(即前件或后件) 。 链式存储方式既可用于表示线性结构,也可用于表示非线性结构。 线性表的链式存储结构称为线性链表。 在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以指向其 前件结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向链表。 在线性链表中, 各数据元素结点的存储空间可以是不连续的, 且各数据元素的存储顺序 与逻辑顺序可以不一致。在线性链表中进行插入与删除,不需要移动链表中的元素。 线性单链表中,HEAD 称为头指针,HEAD=NULL(或 0)称为空表。 如果是双项链表的两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件 结点。 线性链表的基本运算:查找、插入、删除。 栈也是线性表, 也可以采用链式存储结构。 带链的栈可以用来收集计算机存储空间中所 有空闲的存储结点,这种带链的栈称为可利用栈。 疑难解答:在链式结构中,存储空间位置关系与逻辑关系是什么? 在链式存储结构中, 存储数据结构的存储空间可以不连续, 各数据结点的存储顺序与数 据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。

7.6 图与树
图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G=(V,E) 其中:G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中顶点之间边的集合。 若图中的边为有向的,则称为有向图。若图中的边为无向的,则称为无向图。

若一条边以某个结点为顶点, 则称该边与该结点相关联。 若两个结点与同一条边相关联,
35

则称这两个结点相邻。 若一条边只与一个结点相关联则称之为自环。 若在同一对结点之间存 在多条边则称之为重边。含重边的图叫多重图。无自环也无重边的无向图称为简单图。我们 主要学习简单图。 没有边的简单图称为空图, 任意两结点之间都存在一条边的简单图称为完 全图。n 个结点的完全图记为 Kn。 节点 v 所关联的边的条数称为节点的度,记为 d(v)。有向图中,以结点 v 为始点的边 数目称为 v 的正度,也称为出度,记为 d+(v)。以结点 v 为终点的边数目称为 v 的负度(入 度) ,记为 d-(v)。 显然,d+(v)+ d-(v)=d(v)。 如果存在一个图 G’,其所有边包含于 G 的边,所有点包含于 G 的点,称为 G 的子图。 图的性质: (1)有 n 个结点,m 条边的图的总度数位 2m; (2)度为奇数的结点必为偶数个; (3)有向图 G 中正度之和等于负度之和; (4)完全图 Kn 中的边数为 n(n-1)/2; (5)非空简单图中一定存在度相同的结点。 每条边都赋予一个实数做为该边的权,则成为赋权图。

在无向图 G=(V, E)中, 结点 u 到 v 的路径是指是一个顶点序列(u=v0,v1,v2, ?, vm=v), 其中,任意两个相邻的顶点(vj-1,vj)均存在一条边与这两个点关联。若 G 是有向图,则路 径也是有方向的。非赋权图的路径上边的条数,称为路径长度,而带权图的路径长度则定义 为路径上各边的权之和。 在无孤立顶点的图中,若存在一条路经,经过图中每条边一次且仅一次,则称此路为欧 拉路。一笔画问题本质上就是判断一个图是否存在欧拉路。 在无孤立顶点的图中,若存在一条路经,经过图中每条边一次且仅一次,且回到原来位 置,则称此路为欧拉回路。存在欧拉回路的图,称为欧拉图。 定理:存在欧拉路的条件:图是连通的,且存在 0 个或 2 个奇点。如果存在 2 个奇点, 则欧拉路一定是从一个奇点出发,以另一个奇点结束。 存在欧拉回路的条件:图是连通的,且不存在奇点。 哈密尔顿图:在无孤立顶点的连通图中,若存在一条路,经过图中每个顶点一次且仅一 次,则称此图为哈密尔顿图。哈密尔顿环:是一条沿着图的 n 条边环行的路径,它访问每一 个顶点一次且仅一次,并且返回到它的开始位置。 一个不含任何回路的连通图称为树,用 T 表示。T 中的边称为树枝,度为 1 的结点称为 树叶。

36

树的性质: (1)T 连通且无回路; (2)T 连通且每条边都是割边; (3)T 连通且有 n-1 条边; (4)T 有 n-1 条边且无回路; (5)T 的任意两结点间有唯一道路; (6)T 无回路,但在任意两结点间加上一条边后恰有一个回路; (7)以上性质都是等价的。 除树叶外,其余结点的正度最多为 2 的外向树称为二叉树。其他情况称作多叉树。如果 它们的正度都是 2,则称为完全二叉树。如果节点有权重,则称为赋权二叉树。 通常,在树中指定且仅指定一个特定的结点作为树的根;当树中的节点数当 n>1 时, 除根结点之外的其余结点被分成 m(m>0)个互不相交的有限集合 T1,T2,? ,Tm,其中每个 集合又是一棵树,并称为这个根结点的子树。 在树结构中,每一个结点只有一个前驱,称为父结点,没有前驱的结点只有一个,就是 树的根结点,简称树的根。每一个结点可以有多个后继,称为该结点的子结点,没有后继的 结点称为叶子结点,也称为终端结点。具有同一个双亲的孩子结点互称为兄弟结点。 在树结构中,一个结点所拥有的后继结点(子节点)的个数称为该结点的度,叶子结点 的度为 0。所有结点中最大的度称为树的度。注意,这里树的结点的度的定义与前面图的结 点的度定义是不同的。度不为 0 的结点称为分支结点,也称为非终端结点。 如果树的结点序列 n1, n2, ?, nk 有如下关系:结点 ni 是 ni+1 的双亲(1<=i<k) ,则 把 n1, n2, ?, nk 称为一条由 n1 至 nk 的路径;路径上经过的边的个数称为路径长度。 结点所在层数:根结点的层数为 1;对其余任何结点,若某结点在第 k 层,则其孩子结 点在第 k+1 层。树的深度是指树中所有结点的最大层数,也称高度。 层序编号将树中结点按照从上层到下层、 同层从左到右的次序依次给他们编以从 1 开始 的连续自然数。

37

7.7 二叉树
二叉树是一种很有用的非线性结构,具有以下两个特点: ① 非空二叉树只有一个根结点; ② 每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树。 在二叉树中,每一个结点的度最大为 2,即所有子树(左子树或右子树)也均为二叉树。 另外,二叉树中的每个结点的子树被明显地分为左子树和右子树。 在二叉树中, 一个结点可以只有左子树而没有右子树, 也可以只有右子树而没有左子树。 当一个结点既没有左子树也没有右子树时,该结点即为叶子结点。 下图是一个典型的二叉树,在该二叉树中,A 有后代 B,C;B 有后代 D,E;C 有后代 F。 结点 D,E,F 均为叶子结点。根结点 A 和结点 B 的度为 2,结点 C 的度为 1,叶子结点 D,E, F 的度为 0。该树的度为 2。根结点 A 在第 1 层,结点 B,C 在第 2 层,结点 D,E,F 在第 3 层。该树的深度为 3。

2. 二叉树基本性质 二叉树具有以下几个性质: 性质 1:在二叉树的第 k 层上,最多有 2
m
k ?1

(k≥1)个结点。

性质 2:深度为 m 的二叉树最多有 2 ? 1 个结点。 性质 3:在一棵二叉树中,如果叶子结点数为 n0,度为 2 的结点数为 n2,则有: n0= n2+1。 证明: 设 n 为二叉树的结点总数,ni 为二叉树中度为 i 的结点数(i=0,1,2) ,则有: n=n0+n1+n2 在二叉树中,除了根结点外,其余结点都有唯一的一个分枝进入,由于这些分枝是由度 为 1 和度为 2 的结点射出的, 一个度为 1 的结点射出一个分枝, 一个度为 2 的结点射出两个 分枝,所以有:
38

n=n1+2n2+1 因此可以得到:n0=n2+1 。 性质 4:具有 n 个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取 log2n 的整数部分。 小技巧:在二叉树的遍历中,无论是前序遍历,中序遍历还是后序遍历,二叉树的叶子 结点的先后顺序都是不变的。 3. 满二叉树与完全二叉树 满二叉树是指这样的一种二叉树: 除最后一层外, 每一层上的所有结点都有两个子结点。 在满二叉树中, 每一层上的结点数都达到最大值, 即在满二叉树的第 k 层上有 2k-1 个结点, 且深度为 m 的满二叉树有 2m-1 个结点。 完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最 后一层上只缺少右边的若干结点。 对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点, 若其右分支下的子孙结点的最大层次为 p,则其左分支下的子孙结点的最大层次或为 p,或 为 p+1。 完全二叉树具有以下两个性质: 性质 1:具有 n 个结点的完全二叉树的深度为[log2n]+1。 性质 2:设完全二叉树共有 n 个结点。如果从根结点开始,按层次(每一层从左到右) 用自然数 1,2,??,n 给结点进行编号,则对于编号为 k(k=1,2,??,n)的结点有 以下结论: 若 k=1,则该结点为根结点,它没有父结点;若 k>1,则该结点的父结点编号为 INT(k/2) ; ② 若 2k≤n,则编号为 k 的结点的左子结点编号为 2k;否则该结点无左子结点(显然 也没有右子结点) ; ③ 若 2k+1≤n,则编号为 k 的结点的右子结点编号为 2k+1;否则该结点无右子结点。 1.6.2 二叉树的遍历 在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树。在先左后右的原则下,根 据访问根结点的次序,二叉树的遍历分为三类:前序遍历、中序遍历和后序遍历。 (1)前序遍历 先访问根结点,然后遍历左子树,最后遍历右子树;并且在遍历左、右子树时,仍需先 访问根结点,然后遍历左子树,最后遍历右子树。例如,对图 1-1 中的二叉树进行前序遍历 的结果(或称为该二叉树的前序序列)为:A,B,D,E,C,F。 (2)中序遍历 先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然 先遍历左子树,然后访问根结点,最后遍历右子树。例如,对图 1-1 中的二叉树进行中序遍 历的结果(或称为该二叉树的中序序列)为: D,B,E, A,C,F。 (3)后序遍历 先遍历左子树、然后遍历右子树,最后访问根结点;并且,在遍历左、右子树时,仍然 先遍历左子树,然后遍历右子树,最后访问根结点。例如,对图 1-1 中的二叉树进行后序遍 历的结果(或称为该二叉树的后序序列)为: D, E,B, F,C,A。

7.8 拓扑排序
在有向图中若以顶点表示活动, 用有向边表示活动之间的优先关系, 则这样的有向图称
39

为以顶点表示活动的网(Activity On Vertex Network) ,简称 AOV 网。 例如:某工程可分为 V0、V1、V2、V3、V4、V5、V6,7 个子工程,工程流程可用如下 AOV 网表示。其中顶点:表示子工程(也称活动) ,有向边:表示子工程间的顺序关系。

拓扑有序序列是由 AOV 网中的所有顶点构成的一个线性序列, 在这个序列中体现了所有 顶点间的优先关系。一个 AOV 网的拓扑有序序列并不是惟一的。 对于某个 AOV 网, 如果它的拓扑有序序列能被构造成功,则该网中不存在有向回路, 其各子工程可按拓扑有序序列的次序进行安排。 存在有向回路的 AOV 网不能构造出拓扑有序 序列,例如,下图所示的 AOV 网不能求得它的拓扑有序序列,因为图中存在一个回路{B, C, D}。

拓扑排序就是由 AOV 网构造拓扑有序序列的过程。 拓扑排序算法: 1)从有向图中选取一个没有前驱的顶点,并输出之; 2)从有向图中删去此顶点以及所有以它为尾的弧; 重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。 上述算法操作的结果只有两种, 一种是网中全部顶点均被输出, 说明网中不存在有向回 路; 另一种是网中顶点未被全部输出,剩余的顶点均有前驱顶点,说明网中存在有向回路。 例:写出下图所示网所有可能的拓扑有序序列。

可能的拓扑有序序列有: v1,v2,v3 ,v4,v5 ,v6 v1,v2,v3 ,v5,v4 ,v6 v1,v2,v4,v3 ,v5 ,v6 v2,v1,v4,v3 ,v5 ,v6

; ; ; ;

40

v2,v1,v3,v4 ,v5 ,v6 ; v2,v1,v3,v5 ,v4 ,v6 ; v2,v4,v1,v3 ,v5 ,v6 ;

7.9 哈夫曼树与哈夫曼编码
哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。 所谓树的带权路径长度, 就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为 0 层,叶结点到根 结点的路径长度为叶结点的层数) 。树的带权路径长度记为 WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln) N 个权值 Wi(i=1,2,...n)构成一棵有 N 个叶结点的二叉树, 相应的叶结点的路径长度为 Li(i=1,2,...n)。可以证明哈夫曼树的 WPL 是最小的。 哈夫曼编码步骤: 一、对给定的 n 个权值{W1,W2,W3,...,Wi,...,Wn}构成 n 棵二叉树的初始集合 F= {T1,T2,T3,...,Ti,...,Tn}, 其中每棵二叉树 Ti 中只有一个权值为 Wi 的根结点, 它的左右 子树均为空。 (为方便在计算机上实现算 法,一般还要求以 Ti 的权值 Wi 的升序排列。 ) 二、 F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树, 在 新二叉树的 根结点的权值为其左右子树的根结点的权值之和。 三、从 F 中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合 F 中。 四、重复二和三两步,直到集合 F 中只有一棵二叉树为止。 简易的理解就是, 假如我有 A,B,C,D,E 五个字符, 出现的频率 (即权值) 分别为 5,4,3,2,1, 那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取 1,2 构成新树,其根 结点为 1+2=3,如图:

虚线为新生成的结点, 第二步再把新生成的权值为 3 的结点放到剩下的集合中, 所以集 合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:

再依次建立哈夫曼树,如下图:

41

其中各个权值替换对应的字符即为下图:

所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010 哈夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等 场合。 对于哈夫曼树, 有一个很重要的特性, 即对于具有 n 个叶子节点的哈夫曼树, 共有 2*n-1 个节点。 证明:对于二叉树来说,有三种类型节点,即度数(只算出度)为 2 的节点,度数为 1 的节点和度数为 0 的叶节点。 而哈夫曼树的非叶子节点是由两个节点生成的, 因此不能出现 度数为 1 的节点,而生成的非叶子节点的个数为叶子节点个数减一,于此定理就得证了。

7.10 查找
查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始, 依次将线性表中的元素与被查找的元素相比较, 若相等则表示查找成功; 若线性表中所有的 元素都与被查找元素进行了比较但都不相等,则表示查找失败。 例如,在一维数组[21,46,24,99,57,77,86]中,查找数据元素 99,首先从第 1 个元素 21 开始进行比较, 比较结果与要查找的数据不相等, 接着与第 2 个元素 46 进行比较, 以此类推,当进行到与第 4 个元素比较时,它们相等,所以查找成功。如果查找数据元素 100,则整个线性表扫描完毕,仍未找到与 100 相等的元素,表示线性表中没有要查找的元 素。 在下列两种情况下也只能采用顺序查找: ①如果线性表为无序表, 则不管是顺序存储结构还是链式存储结构, 只能用顺序查找; ②即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。 1.7.2 二分法查找 二分法查找,也称拆半查找,是一种高效的查找方法。能使用二分法查找的线性表必须 满足用顺序存储结构和线性表是有序表两个条件。 “有序”是特指元素按非递减排列,即从小到大排列,但允许相邻元素相等。下一节排 序中,有序的含义也是如此。 对于长度为 n 的有序线性表,利用二分法查找元素 X 的过程如下:
42

步骤 1:将 X 与线性表的中间项比较; 步骤 2:如果 X 的值与中间项的值相等,则查找成功,结束查找; 步骤 3:如果 X 小于中间项的值,则在线性表的前半部分以二分法继续查找; 步骤 4:如果 X 大于中间项的值,则在线性表的后半部分以二分法继续查找。 例如,长度为 8 的线性表关键码序列为:[6,13,27,30,38,46,47,70],被查元 素为 38,首先将与线性表的中间项比较,即与第 4 个数据元素 30 相比较,38 大于中间项 30 的值,则在线性表[38,46,47,70]中继续查找;接着与中间项比较,即与第 2 个元素 46 相比较,38 小于 46,则在线性表[38]中继续查找,最后一次比较相等,查找成功。 顺序查找法每一次比较,只将查找范围减少 1,而二分法查找,每比较一次,可将查找 范围减少为原来的一半,效率大大提高。 对于长度为 n 的有序线性表,在最坏情况下,二分法查找只需比较 log2n 次,而顺序查 找需要比较 n 次。

7.11

排序

1. 交换类排序法 (1)冒泡排序法 首先,从表头开始往后扫描线性表,逐次比较相邻两个元素的大小,若前面的元素大于 后面的元素,则将它们互换,不断地将两个相邻元素中的大者往后移动,最后最大者到了线 性表的最后。 然后,从后到前扫描剩下的线性表,逐次比较相邻两个元素的大小,若后面的元素小于 前面的元素,则将它们互换,不断地将两个相邻元素中的小者往前移动,最后最小者到了线 性表的最前面。 对剩下的线性表重复上述过程,直到剩下的线性表变空为止,此时已经排好序。 在最坏的情况下,冒泡排序需要比较次数为 n(n-1)/2。 (2)快速排序法 任取待排序序列中的某个元素作为基准(一般取第一个元素) ,通过一次排序,将待排 元素分为左右两个子序列, 左子序列元素的排序码均小于或等于基准元素的排序码, 右子序 列的排序码则大于基准元素的排序码, 然后分别对两个子序列继续进行排序, 直至整个序列 有序。 2. 插入类排序法 ① 简单插入排序法,最坏情况需要 n(n-1)/2 次比较; ② 希尔排序法,最坏情况需要 O(n1.5)次比较。 3. 选择类排序法 ① 简单选择排序法,最坏情况需要 n(n-1)/2 次比较; ② 堆排序法,最坏情况需要 O(nlog2n)次比较。 相比以上几种(除希尔排序法外) ,堆排序法的时间复杂度最小

43

第 8 章 计算机网络
8.1 计算机网络的概念
计算机网络由一组通过通信设备和线路连接起来的独立的计算机组成, 其目的是为运行 在不同计算机上的程序之间提供通信服务。 能够利用计算机网络进行通信的程序通常被称为 网络程序。 正在运行中的网络程序称为网络进程, 计算机网络主要就是为不同计算机上的网 络进程提供通信服务的。 进程是操作系统的核心概念之一, 是指程序在一个数据集合上的运行过程, 是操作系统 进行资源分配和调度的一个独立单位。 通俗一点说, 进程就是程序在计算机上的一次执行活 动,当你启动了一个程序,你就启动了一个进程,退出一个程序,也就结束了一个进程。 网络中的计算机分为两类,一类运行应用程序,称为主机,这些运行在主机上的应用进 程才是网络的真正“用户”。另一类计算机专门负责转发数据,这类计算机中最典型的代表是 以太网交换机和路由器。
主机A

交换机

路由器R1

路由器R3

交换机

路由器R2 主机B

图 1.1 一个网络的例子 主机上的应用进程是不会直接与以太网交换机或是路由器交互的, 不管这些进程是否正 在使用网络进行信息交换, 它们基本上感觉不到路由器和交换机的存在, 因此可以说交换机 和路由器对应用进程来说是“透明的”。 人们研究并建设计算机网络的主要目的是进行数据通信 (包括文件传输、 电话、 IP email、 视频会议、信息发布、交互式娱乐、网上音乐等)和资源共享(软件、硬件、数据等资源) 。 按覆盖地理范围的不同计算机网络可分为: (1)广域网 WAN (Wide Area Network):广域网也称为远程网,它所覆盖的地理范围 从几十公里到几千公里,覆盖一个国家、地区,或横跨几个洲; (2)城域网 MAN (Metropolitan Area Network):设计目标是要满足几十公里范围内的 大量企业、机关、公司的多个局域网互连的需求,以实现大量用户之间的数据、语音、图形
44

与视频等多种信息的传输功能; (3)局域网 LAN (Local Area Network) :局域网用于将有限范围内(如一个实验室、一 幢大楼、一个校园)的各种计算机、终端与外部设备互连成网;存在多种基于不同技术的局 域网,比如以太网、无线局域网(蓝牙、WIFI 等) 。 需要注意,因特网(Internet)不是广域网,它是一个互联网,互联网(internet)是一 种“网络的网络” (network of networks) ,它把许多网络连接在一起。单个网络(network) 是由若干结点(node)和连接这些结点的链路(link)组成。而互联网则是用链路把不同的 网络连接到一起。 网络 结点 链路 互联网(网络的网络)

(a

(b

因特网的发展 因特网起源于美国国防部的科研项目 ARPANET。 1969 年创建的 ARPANET 只是一个单 个的分组交换网(不是互联网) 。70 年代中期 ARPA 开始研究多种网络的互联技术,导致 ARPANET 逐渐成为互联网。1983 年 TCP/IP 协议成为 ARPANET 上的标准协议。人们把 1983 年作为因特网的诞生时间。 70 年代后期,NSF(美国国家科学基金会)看到 ARPANET 对于大学研究工作的巨大 影响,决定设计一个 ARPANET 的后继网,从 1985 年起,围绕六个计算中心建设计算机网 络,1986 年建成了国家科学基金网 NSFNET,并与 ARPANET 相连。它是一个三级网络: 主干网、地区网、校园网。ARPANET 和 NSFNET 形成了 Internet 的基础。 从 1993 年开始,由美国政府资助的 NSFNET 逐渐被若干个商用的 ISP 网络所代替。 1994 年开始创建了 4 个网络接入点 NAP (Network Access Point), 分别由 4 个电信公司经 营。从 1994 年到现在,因特网逐渐演变成多级结构网络,其特点是出现了因特网服务提供 者 ISP (Internet Service Provider),并逐渐形成了多层次 ISP 结构的因特网。 因特网是世界上规模最大和增长速率最快的计算机网络, 没有人能够准确说出因特网究 竟有多大。因特网的迅猛发展始于 20 世纪 90 年代。由欧洲原子核研究组织 CERN 开发 的万维网 WWW (World Wide Web)被广泛使用在因特网上,大大方便了广大非网络专业人 员对网络的使用,成为因特网的这种指数级增长的主要驱动力。

8.2 分组、协议与层次结构
网络上传送的信息是以分组(packet)为单位的,它的主要内容一般是由应用进程生成 的一系列二进制字节序列,这些二进制字节序列被称为用户数据,其含义与网络无关,由应 用进程进行解释。分组中除包含用户数据外,还包括一些控制信息,这些控制信息是为了能 正确传送分组而提供给网络使用的, 比如标识目的地的地址信息等。 控制信息一般被按固定 的结构组织在一起,并添加在用户数据的前面随数据一起传输,通常被称为分组首部。分组

45

首部的组织结构再加上其后的数据部分就是所谓的分组结构或分组格式。 分组结构的定义是 通信协议的一部分。 所谓协议,就是通信双方在相互通信时所遵循的规则、标准和约定。协议是通信双方使 用的“语言” ,它除了规定分组的结构外,还要规定通信过程中不同分组的交换顺序、交换 方式以及如何对分组所包含的信息进行解析等。 网络协议是由三个要素组成: (1) 语义。语义是解释控制信息每个部分的意义。它规定了需要发出何种控制信息,以 及完成的动作与做出什么样的响应。 (2) 语法。语法是用户数据与控制信息的结构与格式,以及数据出现的顺序。 (3) 时序。时序是对事件发生顺序的详细说明。 (也可称为“同步”) 。 人们形象地把这三个要素描述为:语义表示要做什么,语法表示要怎么做,时序表示做 的顺序 一个协议通常只解决通信过程中某一特定情况下的某一特定问题。 为了实现计算机网络 的通信功能,需要解决大量各种各样的问题。为了解决这些问题,计算机网络也就需要用到 大量各种各样的协议。 网络通信所需要的所有这些协议组成的集合被称为协议族。 因特网所 使用的协议族是 TCP/IP 协议族。 为了使问题简化,便于管理和模块化,在设计网络时,人们把实现网络功能所需解决的 各种不同问题按功能划分到不同的层次上, 相应协议也就位于网络的不同层次上, 这就是所 谓的协议分层。 “分层”可将庞大而复杂的问题,转化为若干较小的局部问题,而这些较小 的局部问题就比较易于研究和处理。 事实证明, 将网络按功能分层设计是十分合理有用的措 施。 协议族中的各种协议按功能对应到网络的不同层次后, 画出的层次结构示意图类似于数 据结构中堆栈的结构图,所以有时也将协议族称为协议栈。

在网络的分层体系结构中, 每层都完成独立的功能, 但是每层功能的实现需要借助下层 的服务来完成,同时向上层提供更高级的服务。层间通信只能在层间进行,不能跨层调用。 每个层次都从上层取得数据, 加上首部信息形成新的数据单元, 将新的数据单元传递给下一 层次。 分层的例子:

46

主机 1 向主机 2 通过一个简单网络发送文件时, 可以将要做的工作进行如下的层次划 分: (1)直接与传送文件相关的工作,包括确信对方已做好接收和存储文件的准备、双方 协调好一致的文件格式等,这些工作可用一个文件传送模块来完成。 两个主机将文件传送模块作为最高的一层, 剩下的工作由下面的模块负责。 只看两个主 机上的两个文件传送模块时,就好像文件以及相关的文件传送命令,直接传送到对方一样。 (2)然后的工作是保证两个系统之间的文件传送和文件传送命令交换的可靠性,为此 可设计一个通信服务模块,作为下一个层次。 (3) 剩余的工作就是需要设计一个网络接入模块, 负责做与网络接口细节有关的工作。 例如,规定传输的帧格式,帧的最大长度等。 因特网就是按分层方式设计的,按照功能的不同,因特网被分四个层次: 第一层被称为网络接口层 (Host-to-Network layer) 它主要由基础的物理通信信道构成, , TCP/IP 对这一层没有任何要求,它可以是任何一种物理信道,如以太网、无线局域网或者 使用调制解调器的拨号连接等。 通过这些物理信道直接相连的计算机可以不经过路由器而直 接通信,通常,这些不通过路由器就可以直接通信的计算机被称为位于同一个 IP 子网内。 第二层是互联网层(Internet layer),该层对应的协议是 IP 协议,它所解决的问题是使网 络上的任意两台主机之间能够传送分组, 也就是在任意两台主机之间找一条由物理信道和路 由器组成的通路,使分组能沿这条通路由一台主机传送到另一台主机。因此,IP 的主要功 能是将分组从网络中的一台主机传送到另一台主机。 IP 协议利用 IP 地址区分网络中的不同计算机,当一台主机向网络中的另一台主机机发 送一个分组时,必须将目的主机的 IP 地址填写到该 IP 分组的首部的“目的地址”字段中, 因为只有这样, 网络中的路由器在收该分组后, 才能根据它所携带的目的地址为它选择一条 正确的输出线路将它向目的主机方向转发。 IP 协议是一种“不可靠的”协议,从主机 A 发送给主机 B 的一个分组序列在传送过程 中有可能会丢失分组或被重新排序,尽管发生的几率并不高。IP 提供的这种不可靠的通信 服务被称为“数据报”服务。 IP 之上的第三层是传输层(Transport layer), 它的主要目标是使运行在不同计算机上的任 意两个或多个进程之间能够相互传送数据, 也就是为进程之间提供通信服务。 传输层协议把 数据从一个进程运送到另一个进程,因此是一种端到端的传输协议(end-to-end transport protocol) 。 需要强调的是,传输层协议是利用下层 IP 协议的功能完成其端到端传输的。传输层协 议在收到应用进程要发送的用户数据后, 首先在用户数据前添加上自己的首部构成传输层协 议数据单元,然后将该数据单元交给 IP,IP 负责将该数据单元传送到目的主机并交给目的 主机的相应传输协议,再由该传输协议将用户数据交给目的应用进程。

47

应用层

HTTP



SMTP

DNS



RTP

运输层

TCP

UDP

互联网层

IP

网络接口层

网络接口 1

网络接口 2



网络接口 3

图 1.2 TCP/IP 协议栈 TCP/IP 协议族的传输层存在两个协议:TCP 和 UDP。应用进程可选择这两个协议中的 任何一个进行数据通信。 TCP 是一个可靠的协议,它检测 IP 传送的数据中可能发生的丢失、失序等错误,并采 取一定的措施更正这些错误, 从而为用用程序提供可靠的数据通信服务。 为了实现可靠的通 信,TCP 在传送数据之前必需先建立连接,通信完成之后还需要释放链接,所以我们经常 说 TCP 提供面向连接的通信服务。 UDP 则不会尝试从 IP 的错误中进行恢复,它只是将 IP 主机到主机之间的不可靠的“数 据报”服务简单地扩展为应用程序到应用程序之间。 它在通信时并不建立连接,因而 UDP 是 无连接的。 TCP 和 UDP 所要解决的一个共同问题是进程的寻址问题,也就是如何区别不同进程的 问题。 每台主机上一般都会同时运行多个进程, 而这些进程又都有可能利用网络与远端的进 程进行通信,比如,你通常会一边通过浏览器看着新闻,一边迅雷还在帮你下载着文档,同 时你的 QQ 还在等着你的同学给你发来的消息。当主机从网络收到一个发给本机的 IP 分组 后, 会根据这个分组的首部中的 “协议字段”的内容决定是交给 TCP 还是 UDP 处理, 但是, 由于主机上同时会有多个进程在使用 TCP 或 UDP 进行通信,当 TCP 或是 UDP 在收到这个 分组后,应该将它交给哪一个进程呢?TCP 和 UDP 利用端口号来解决这一问题的。 端口号就是所谓的进程地址,它本质上是分配给应用进程的一个 16 位的二进制数,当 两个进程需要利用 TCP 或是 UDP 进行通信时,必须分别为它们各自分配一个端口号,而且 还要将自己的端口号告知通信对端的进程,这样,通信对端的进程在发送数据时,只要在 TCP 或 UDP 首部的 “目的端口号” 字段中指明要接收数据的进程所使用的端口号就可以了。 当 TCP 或 UDP 在收到 IP 层转交的数据分组后,它就会根据首部字段中的目的端口号决定 将数据交给那一个进程。 最高一层是应用层(Application layer),这一层的协议都是针对某种具体应用的,它定义 了某种应用的具体框架,直接为用户的应用程序提供服务,例如 HTTP 用于浏览器向 Web 服务器请求网页内容,SMTP 则用于邮件的发送。 对与你自己开发的应用程序,根据程序的具体功能,你可以选择使用已有的标准协议, 也可以开发并是自己的应用层协议。 但对大多数网络应用程序, 都需要你自己设计并实现应 用层协议。 在网络的分层结构中, 每层都完成独立的功能。 每层功能的实现都需要借助下层的服务

48

来完成,同时本层还要向上层提供更高级的服务。例如,在 TCP/IP 协议族中,TCP 或是 UDP 的主要功能是完成不同主机上的进程之间的通信,也就是说不同主机上的进程之间是 直接利用 TCP 或是 UDP 提供的通信服务进行直接通信的,而 TCP 或 UDP 要上层的应用进 程提供通信服务,还必须要调用下层 IP 的功能,将数据分组从源主机传输到目的主机。 各层的功能是由各层的协议控制完成的, 网络的层次结构一旦确定, 各层的功能也就随 之确定了,但各层所使用的协议则可以采用不同的版本。

8.3

IP 地址

使用 TCP/IP 协议族通信的计算机网络通常被称为 IP 网络, 因特网就是全世界最大的一 个 IP 网络。 在 IP 网络中,每一台主机都至少会分配一个 IP 地址,准确一点说,IP 地址不是分配给 主机的,而是分配给主机上的网络接口的。网络接口是主机与底层物理通信信道的连接,每 一个 IP 地址都代表了一台计算机与底层物理通信信道的一个连接。每一个网络接口都是属 于唯一的一台主机,因此只要它连接到网络,使用该接口的 IP 地址就可以定位这台主机。 主机可以有多个网络接口, 例如一台主机可以有一个有线以太网口, 同时还有一个无线 网口 (WiFi) 如果要使它们都可以使用, , 则每一个网络接口都必需至少分配一个 IP 地址 (实 际上,在有些系统中一个接口可以有多个 IP 地址) 。 IP 地址的一个重要作用是区分同一个 IP 网络中的不同网络接口, 因此同一 IP 网络中不 能存在相同的 IP 地址。 IP 地址的另一个作用就是标识计算机所在的地理位置,路由器在转发分组时所依据的 就是分组所携带的目的主机的 IP 地址。当计算机从网络的一个地理位置移动到另一个地理 位置时,比如从山东农业大学移动到了清华大学,计算机的 IP 地址必需作出相应变更。 目前存在两个版本的 IP 协议,IPv4 和 IPv6,这两个版本最大的差别就是它们的 IP 地 址是不相同的。IPv4 地址是一个 32 位的二进制数,通常采用点分十进制表示,即将这 32 位二进制数平均分为 4 组,并用点(.)隔开,然后再将每组数写为对应的十进制数。 如 11001010110000101000010100000001 11001010.11000010.10000101.00000001 202.194.133.1 IPV6 的地址则是一个 128 位的二进制数,其书写方式一般采用冒号 16 进制方式书写。

8.4 域名系统
当你通过因特网访问另一台计算机或服务器时,你必须知道对方的 IP 地址,但是人们 对记忆大量的数字方式的 IP 地址是有困难的。为此引入了域名系统。比如,你想访问中央 电视台的网站看一下节目预告,你没有必要记住它的网站所在计算机的 IP 地址,你只要记 住其域名“www.cctv.com”就行了。域名通常情况下要比 IP 地址好记得多。 当然,引入域名系统的好处还不仅仅在于此,比如,当 CCTV 的网站所在的计算机因 为某种原因改变了 IP 地址,只需在域名服务器上更改一下记录则可,而不必通知它的每个 用户。这一点有手机的同学可能深有体会,你换了一个手机号,你必须通告所有你的亲戚朋 友你的新手机号,这比较麻烦,而且还经常有人通知不到。如果也像因特网上的计算机一样 给你的手机起一个域名, 别人给你打电话时只用你手机的域名进行拨号就能拨通, 那你换手 机号好后也只需在你注册的域名服务器上更改一下记录则可。 这样可能就方便多了。 但很遗

49

憾,现在的电信服务商还没有提供手机的域名服务。 需要注意,计算机间通信最终使用的还是 IP 地址而不是域名。事实上,当你在使用域 名与另外的计算机建立联系时,你计算机上的域名解析程序将域名“翻译”成了相应的 IP 地址。 这里的翻译其实是查询,域名解析程序是通过查询域名服务器获取对应的 IP 地址的。 而域名服务器的 IP 地址是事先配置好的。下图是 Windows 系统的网络配置页面,你可以看 到在下面需要填写域名服务器的 IP 地址。当然,你的计算机上所配置域的名服务器的 IP 地 址(包括你的计算机的 IP 地址和子网掩码以及缺省网关)是由你所在的电信服务商告诉你 的。

有些同学可能会问, 我的电脑在上网上前怎么从来没配置过?那是因为为了方便用户上 网,现在的因特网服务商一般都提供主机的自动配置功能。你只需要在上图中选中“自动获 取 IP 地址”和自动获取 DNS 服务器地址,并连好网线(或插好无线上网卡) ,你的计算机 便会自动在网上搜索一个被称为 DHCP 服务器的服务器来获取 IP 地址等配置信息。 因特网采用层次树状结构的命名方法来给计算机起名。 任何一个连接在因特网上的主机 或路由器都可以有一个唯一的层次结构的域名, 当然也可以没有, 比如你上网用的计算机就 没有域名。域名的结构由标号序列组成,各标号之间用点隔开,各标号分别代表不同级别的 域名。 ? . 三级域名 . 二级域名 . 顶级域名 各级域名由其上一级的域名管理机构管理,顶级域名由 ICANN 管理。ICANN 是 The Internet Corporation for Assigned Names and Numbers 的简写,也就是因特网名称与数字地址 分配机构。 顶级域名有三类: 国家顶级域名 nTLD:如: .cn 表示中国,.us 表示美国,.uk 表示英国,等等。 通用顶级域名 gTLD:最早的顶级域名包括: .com (公司和企业) .net (网络服务机构) .org (非赢利性组织)

50

等等 我国只管理顶级域名 cn 下的二级域名。Cn 下的二级域名被划分为“类别域名”和“行 政区域名”两类,类别域名有 6 个:科研机构.ac;工商金融企业.com;教育机构.edu;政府 机构.gov;互连网络机构;非赢利组织.org,行政区域名有 34 个:对应各省、直辖市和自治 区,由两个字母组成,例如,北京.bj,上海 sh,浙江 zj 等等。二级域名下申请注册三级域 名的管理办法是: 在.edu 下的申请,由中国教育和科研计算机网络中心负责; 其他二级域名下的申请注册由中国互连网络信息中心 CNNIC 负责,在 CNNIC 网站上 可以查到中国互连网络的各项管理规定和发展情况。

8.5 因特网应用
1. WEB World Wide Web (WWW)是 Tim Berners Lee(蒂姆·伯纳斯·李)于 1991 年发明的。 1989 年夏天,蒂姆开发出了世界上第一个 Web 服务器和第一个 Web 客户机。 虽然以现在 的眼光来看这只能算是一个简单的电话号码查询, 但它却实实在在是一个所见即所得的超文 本浏览/编辑器。1989 年 12 月,蒂姆为他的发明正式定名为 World Wide Web,即我们熟悉 的 WWW;1991 年 5 月 WWW 在 Internet 上首次露面,从此揭开了 Internet 的新纪元,从 此我们也开始了网上的冲浪。 万维网使用统一资源定位符 URL (Uniform Resource Locator)来标志万维网上的各种文 档。每一个文档在整个因特网的范围内具有唯一的标识符 URL。URL 的一般形式: <协议>://<主机>:<端口>/<路径> 这里,协议可以是 ftp(文件传送协议 FTP) 、http(超文本传送协议 HTTP)等。 客户程序与服务器程序之间进行交互所使用的协议是超文本传送协议 HTTP (HyperText Transfer Protocol)。 超文本标记语言 HTML (HyperText Markup Language)使得万维网页面的设计者可以很 方便地用一个超链从本页面的某处链接到因特网上的任何一个万维网页面, 并且能够在自己 的计算机屏幕上将这些页面显示出来。 HTML 定义了许多用于排版的命令 (即标签) HTML 。 把各种标签嵌入到万维网的页面中。这样就构成了所谓的 HTML 文档。HTML 文档是一 种可以用任何文本编辑器创建的 ASCII 码文件。 例: 一个超文本文档。 将下面的内容用记事本存入一个文本文档, 并将扩展名改为 html, 双击该文档就可用浏览器查看一下文档的效果。 <HTML> <HEAD> <TITLE>一个 HTML 的例子</TITLE> </HEAD> <BODY> <H1>HTML 很容易掌握</H1> <P>这是第一个段落。虽然很 短,但它仍是一个段落。</P> <P>这是第二个段落。</P> </BODY> </HTML> 在万维网中用来进行搜索的程序叫做搜索引擎。 全文检索搜索引擎是一种纯技术型的检

51

索工具。 它的工作原理是通过搜索软件到因特网上的各网站收集信息, 找到一个网站后可以 从这个网站再链接到另一个网站。 然后按照一定的规则建立一个很大的在线数据库供用户查 询。用户在查询时只要输入关键词,就从已经建立的索引数据库上进行查询(并不是实时地 在因特网上检索到的信息) 。 2.文件传输:文件传送协议 FTP (File Transfer Protocol) 是因特网上使用得最广泛的文 件传送协议。 FTP 提供交互式的访问,允许客户指明文件的类型与格式,并允许文件具有存取权限。 FTP 屏蔽了各计算机系统的细节。 3.电子邮件 电子邮件的快捷和方便是传统邮件不可比拟的, 一个电子邮件系统的构成包括: 电子邮 件协议、用户代理、电子邮件服务器。用户代理 UA 就是用户与电子邮件系统的接口,是 电子邮件客户端软件。用户代理的功能:撰写、显示、处理和通信典型的例子包括 Outlook、 foxmail 等。但现在很多人都不用,都使用基于 Web 的电子邮件系统。 邮件服务器的功能是发送和接收邮件, 同时还要向发信人报告邮件传送的情况 (已交付、 被拒绝、丢失等) 。邮件服务器需要使用发送和读取两个不同的协议。发送邮件用简单邮件 传送协议 SMTP。客户接收邮件使用 POP3 协议。 电子邮件地址的格式: 收件人邮箱名@邮箱所在主机的域名 符号“@”读作“at” ,表示“在”的意思。 例如,电子邮件地址 xxnn@163.com 4.即时通信:即时通信(IM)是指能够即时发送和接收互联网消息等的业务。1998 年即 时通信的功能日益丰富, 逐渐集成了电子邮件、博客、音乐、电视、游戏和搜索等多种功能。 即时通信不再是一个单纯的聊天工具,它已经发展成集交流、 资讯、 娱乐、 搜索、电子商务、 办公协作和企业客户服务等为一体的综合化信息平台。 随着移动互联网的发展, 互联网即时 通信也在向移动化扩张。目前,微软、AOL、Yahoo 等重要即时通信提供商都提供通过手机 接入互联网即时通信的业务, 用户可以通过手机与其他已经安装了相应客户端软件的手机或 电脑收发消息。 现在国内的即时通信工具按照使用对象分为两类:一类是个人 IM,如:QQ,百度 hi, 网易泡泡,盛大圈圈,淘宝旺旺等等。QQ 的前身 OICQ 在 1999 年 2 月第一次推出,目前 几乎接近垄断中国在线即时通讯软件市场。百度 Hi 具备文字消息、音视频通话、文件传输 等功能,您可通过它找到志同道合的朋友,并随时与好友联络感情;另一类是企业用 IM, 简称 EIM,如:E 话通,UC,EC 企业即时通信软件,UcSTAR、商务通等。 5.Web2.0:Web2.0 是相对 Web1.0 的新的一类互联网应用的统称。Web1.0 的主要特 点在于用户通过浏览器获取信息。Web2.0 则更注重用户的交互作用,用户既是网站内容的 浏览者, 也是网站内容的制造者。 所谓网站内容的制造者是说互联网上的每一个用户不再仅 仅是互联网的读者,同时也成为互联网的作者;不再仅仅是在互联网上冲浪,同时也成为波 浪制造者;在模式上由单纯的“读”向“写”以及“共同建设”发展;由被动地接收互联网信息向 主动创造互联网信息发展,从而更加人性化! 雅虎旗下图片分享网站 Flickr,是一家提供免费及付费数位照片储存、分享方案之线上 服务,也提供网络社群服务的平台。一般认为 Flickr 是 Web 2.0 应用方式的绝佳例子。

52


更多相关文档:

信息学竞赛辅导资料

信息学竞赛辅导资料_学科竞赛_高中教育_教育专区。信息学奥赛。。第0 章 概述 0.1 关于信息学奥林匹克竞赛全国青少年信息学奥林匹克竞赛(简称 NOI)及其分区联赛(...

信息学奥赛(初赛)辅导教材

金华一中信息学(计算机)奥林匹克竞赛辅导教程 第一部分一、初赛的要求 试题的知识范围 1.1 计算机的基本常识 ① 计算机和信息社会(信息社会的主要特征、计算机的...

信息学奥赛培训资料

信息学奥赛培训资料_学科竞赛_高中教育_教育专区。桃江一中信息学奥赛培训辅导资料...*分区联赛辅导丛书 *学生计算机世界报及少年电世界杂志 2 第一章第一节 计算机...

信息学奥赛(NOIP)必看经典书目汇总

3、 《学习指导》 (推荐指数:5 颗星) 刘汝佳著, 《算法艺术与信息学竞赛》的辅导书。 (PS:仅可在网上搜到,格式为 PDF) 。 4、 《奥赛经典》 (推荐指数:...

信息学奥赛(NOIP)必看经典书目汇总

2、《算法艺术与信息学竞赛》(推荐指数:5 颗星) 刘汝佳著,传说中的黑书。 3、《学习指导》(推荐指数:5 颗星) 刘汝佳著,《算法艺术与信息学竞赛》的辅导书。...

(信息学奥赛辅导)排列与组合基础知识

(信息学奥赛辅导)排列与组合基础知识_学科竞赛_高中教育_教育专区。第1页 排列...问(1)从中任取 2 本书有多少种方案?(2)从中取 2 本相同文字的书有多少...

怎样做好信息学奥赛培训辅导

怎样做好信息学奥赛培训辅导临邑洛北中学西校 摘要: 信息学奥林匹克竞赛是智力...这本书充分考虑了初中学生这个年 龄段的学习心理和认知特点, 结合初级比赛当中...

信息学奥林匹克竞赛培训教案(校本课程)

信息学奥林匹克竞赛培训教案(校本课程)_学科竞赛_高中教育_教育专区。信息学奥林...1.2.2 由信息高速公路热引发的全球信息化浪潮 在现代,能源、材料与信息是社会...

怎样做好信息学奥赛培训辅导

怎样做好信息学奥赛培训辅导_计算机软件及应用_IT/计算机_专业资料。怎样做好信息学奥赛培训辅导 信息技术理论课教学模式信息技术组 在《信息技术》教学中有这样的...

信息学奥赛培训教程C++版

信息学奥赛培训教程C++版_学科竞赛_初中教育_教育专区...*分区联赛辅导丛书 *学生计算机世界报及少年电世界杂志...计算机的电子元器件; 软件即程序和有关 文档资料。...
更多相关标签:
信息学竞赛 | 算法艺术与信息学竞赛 | 2016安徽省信息学竞赛 | 奥林匹克信息学竞赛 | 合肥市信息学竞赛 | 高中信息学竞赛 | noip信息学竞赛题目 | 信息学竞赛学什么 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com