信息学奥赛-计算机基础知识.doc

第一章 计算机基础知识2第一节 数制及其转换2第二节 算术运算和逻辑运算3第三节 原码、反码和补码5第四节 浮点数的表示方法6第五节 奇偶校验7第六节 ASCII码表8第二章 计算机硬件基础9第一节 中央处理器9第二节 存储器系统10第三节 输入输出系统11第三章 网络基础知识12第一节 网络的组成与结构12第二节 网络协议13第三节 Internet相关知识13第三节 Internet相关知识14第四章 其他相关基础知识15第一节 计算机病毒15第二节 数据库系统15第五章 数据结构之线性结构16第一节 线性表16第二节 栈17第三节 队列18第六章 数据结构之非线性结构19第一节 树的概念19第二节 树的表示方法和存储结构20第三节 二叉树的概念22第四节 二叉树的遍历24第五节 普通树的遍历27第六节 根据两种遍历顺序确定树结构28第七节 二叉排序树29第八节 最优二叉树(哈夫曼树)30AOE网32第一章 计算机基础知识第一节 数制及其转换一、二、八、十六进制转十进制的方法：乘权相加法。 例如：（11010110）2 = 127 + 126 + 025 + 124 + 023 + 122 + 121 + 020 = （214）10（2365）8 = 283 + 382 + 681 + 580 = （1269）10（4BF）16 = 4162 + 11161 + 15160 = (1215)10 带小数的情况：（110.011）2 = 122 + 121 + 120 + 02-1 + 12-2 + 12-3 = （6.375）10（5.76）8 = 580 + 78-1 + 68-2 = （5.96875）10（D.1C）16 = 13160 + 116-1 + 12*16-2 = （13.109375）10 二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。 例一：（43）10 = （101011）2例二：（0.375）10 = （0.011）2三、二进制转八进制的方法 一位数八进制与二进制对应表八进制二进制转换方法:对二进制以小数点为分隔，往前往后每三位划为一组，不足三位补0，按上表用对应的八进制数字代入即可。例如：(10111011.01100111) = 010,111,011.011,001,110 = （273.36）800001001201030114100510161107111三、二进制转十六进制的方法 一位数十六进制与二进制对应表十六进制二进制转换方法:对二进制以小数点为分隔，往前往后每四位划为一组，不足四位补0，按上表用对应的十六进制数字代入即可。例如：(10111011.01100111) = 1011,1011.0110,0111 = （BB.67）1600000100012001030011401005010160110701118100091001A1010B1011C1100D1101E1110F1111四、进制的英文表示法：以上都是用括号加数字的表示方法，另外还有英文表示法，就是以BIN、OCT、HEX、DEC分别代表二、八、十六、十进制。或者只写第一个字母。例如1101B表示是二进制。有些地方为了避免“O”跟“0”混淆，把O写成Q。第二节 算术运算和逻辑运算一、二进制的算术运算 1、加法运算规则： 0+0=0 0+1=1 1+0=1 1+1=10 2、减法运算规则： 0-0=0 0-1=1（向高位借1） 1-0=1 1-1=0 3、乘法运算规则： 00=0 01=0 10=0 11=1 二、逻辑运算 1、基本运算 逻辑乘，也称“与”运算，运算符为“”或“” 00=0 01=0 10=0 11=1 使用逻辑变量时，AB可以写成AB 逻辑加，也乘“或”运算，运算符为“+”或“” 0+0=0 0+1=1 1+0=1 1+1=1 逻辑非，也称“反”运算，运算符是在逻辑值或变量符号上加“” = 1 = 02、常用运算 异或运算：AB =AB 2、基本公式 0，1律 A0=0 A1=A A0=A A1=1 交换律 AB=BA AB=BA 结合律 ABC =（AB）C = A（BC） ABC =（AB）C = A（BC） 分配律 A（BC）= AB AC 重叠律 AA.A = A AA.A = A 互补律 A + = 1 A = 0 吸收律 AAB = A A（AB） = A AB = AB A（B） = AB 对合律 对一个逻辑变量两次取反仍是它本身 德摩根定理 = = +三、逻辑代数的应用1、逻辑表达式化简 例如： F = AAB=A（B） （利用分配律）=A （利用互补律以及0，1律） = A（利用吸收律） 2、对指定位进行运算，假设变量A有八位，内容是d7d6d5d4d3d2d1d0 将变量A的d5位清零 A（11011111）A 将变量A的各位置1 A（11111111）A 第三节 原码、反码和补码 计算机中参与运算的数有正负之分，计算机中的数的正负号也是用二进制表示的。用二进制数表示符号的数称为机器码。常用的机器码有原码、反码和补码。 一、原码 求原码的方法：设X；若X0，则符号位（原码最高位）为0，X其余各位取值照抄；若X0，则符号位为1，其余各位照抄。【例1】X=+1001001 X原 = 01001001【例2】X=-1001001 X原 = 11001001 二、反码 求反码的方法：设X；若X0，则符号位（原码最高位）为0，X其余各位取值照抄；若X0，则符号位为1，其余各位按位取反。【例3】X=+1001001 X反 = 01001001【例4】X=-1001001 X反 = 10110110 三、补码 求补码的方法：设X；若X0，则符号位（原码最高位）为0，X其余各位取值照抄；若X0，则符号位为1，其余各位按位取反后，最低位加1。【例5】X=+1001001 X补 = 01001001【例6】X=-1001001 X补 = 10110111 四、补码加减法 计算机中实际上只有加法，减法运算转换成加法运算进行，乘法运算转换成加法运算进行，除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。 1、补码加法 X+Y补 = X补 + Y补【例7】X=+0110011,Y=-0101001，求X+Y补 X补=00110011 Y补=11010111 X+Y补 = X补 + Y补 = 00110011+11010111=00001010 注：因为计算机中运算器的位长是固定的，上述运算中产生的最高位进位将丢掉，所以结果不是 100001010，而是00001010。 2、补码减法 X-Y补 = X补 - Y补 = X补 + -Y补 其中-Y补称为负补，求负补的方法是：对补码的每一位（包括符号位）求反，最后末位加“1”。【例8】X=+0111001,Y=+1001101，求X-Y补 X补=00111001 Y补=01001101 -Y补 = 10110011 X-Y补 = X补 + -Y补 = 00111001+10110011=11101100 五、数的表示范围 通过上面的学习，我们就可以知道计算机如果用一个字节表示一个整数的时候，如果是无符号数，可以表示0255共256个数（0000000011111111），如果是有符号数则能表示-128127共256个数（1000000001111111）。如果两个字节表示一个整数，则共有65536个数可以表示，大部分程序设计语言中整数的范围都是-3276832767的原因，可以看出这种整数类型是16位的有符号数，而且是补码表示的。第四节 浮点数的表示方法一、浮点数表示 一个数的浮点形式（设基数是2）可写成： N = M 2E 其中:M代表尾数,E代表阶码。 计算机中浮点数只用尾数和阶码表示，其形式如下： 阶码尾数符号尾数 浮点数的精度由尾数决定，数的表示范围由阶码的位数决定。 为了最大限度提高精度，尾数采用规格化形式，既1/2M1。采用二进制表示时，若尾数大于零，则规格化数应该是01XXXX的形式；若尾数小于零，则规格化数应为10XXXX的形式。 二、机器零 当浮点数的尾数为0或阶码为最小值时，计算机通常把该数当作零，因此程序中进行浮点运算时，判断某数是否为零，通常可以用小于某个极小值来代替。 三、实例 【例1】设X=0.011023 ,用补码、浮点数形式表示阶码为Xj=011，尾数为00110，这时由于X尾数不符合01XXXX的形式，因此不是规格化数，必须先进行规格化处理。方法：若尾数小于1/2，把尾数左移一位（不包括符号位），观察结果是否满足规格化条件，满足则在把阶码减1即可，否则继续左移和调整阶码；若尾数大于1，则把尾数右移一位（不包括符号位），观察结果是否满足规格化条件，满足则在把阶码加1即可，否则继续右移和调整阶码。上例中，00110左移一位为01100，符合规则化标准，此时阶码减1，为010即得到浮点表示形式。 这个数具体在计算机中如何表示要看计算机中规定的阶码和尾数的位数，若阶码和尾数均为16位，则上面的数X在计算机内部表示就是 00000000000000100110000000000000 ，不足均用零填充。 第五节 奇偶校验 计算机中数据在进行存储和传输过程中可能会发生错误。为了及时发现和纠正这类错误，在数据传输（存储）过程中要进行校验，常用的校验方法就是奇偶校验。 奇偶校验能发现一位或奇数位错误，且不能纠正错误。一般以字节（八位二进制）为单位加1位奇偶校验位。奇偶校验分奇校验和偶校验两种。 一、奇校验：一个字节前面加一位校验位使得“1”的个数保持为奇数，若八位二进制数中“1”的个数为偶数，则校验位为“1”；若八位二进制数中“1”的个数为奇数，则校验位为“0”。【例1】给1001100101101101加奇校验结果为110011001001101101 二、偶校验：一个字节前面加一位校验位使得“1”的个数保持为偶数，若八位二进制数中“1”的个数为偶数，则校验位为“0”；若八位二进制数中“1”的个数为奇数，则校验位为“1”。【例2】给1001100101101101加偶校验结果为010011001101101101第六节 ASCII码表代码字符代码字符代码字符代码字符代码字符32 52472H92112p33!53573I93113q34”54674J94114r35#55775K95_115s36$56876L96116t37%57977M97a117u38&58:78N98b118v3959;79O99c119w40(60 82R102f122z43+63?83S103g12344,6484T104h124|45-65A85U105i12546.66B86V106j12647/67C87W107k 48068D88X108l 49169E89Y109m 50270F90Z110n 51371G91111o 目前使用最广泛的西文字符集及其编码是 ASCII 字符集和 ASCII 码（ ASCII 是 American Standard Code for Information Interchange 的缩写），它同时也被国际标准化组织（ International Organization for Standardization, ISO ）批准为国际标准。 基本的 ASCII 字符集共有 128 个字符，其中有 96 个可打印字符，包括常用的字母、数字、标点符号等，另外还有 32 个控制字符。标准 ASCII 码使用 7 个二进位对字符进行编码，对应的 ISO 标准为 ISO646 标准。下表展示了基本 ASCII 字符集及其编码： 字母和数字的 ASCII 码的记忆是非常简单的。我们只要记住了一个字母或数字的 ASCII 码（例如记住 A 为 65 ， 0 的 ASCII 码为 48 ），知道相应的大小写字母之间差 32 ，就可以推算出其余字母、数字的 ASCII 码。 虽然标准 ASCII 码是 7 位编码，但由于计算机基本处理单位为字节（ 1byte = 8bit ），所以一般仍以一个字节来存放一个 ASCII 字符。每一个字节中多余出来的一位（最高位）在计算机内部通常保持为 0 （在数据传输时可用作奇偶校验位）。 由于标准 ASCII 字符集字符数目有限，在实际应用中往往无法满足要求。为此，国际标准化组织又制定了 ISO2022 标准，它规定了在保持与 ISO646 兼容的前提下将 ASCII 字符集扩充为 8 位代码的统一方法。 ISO 陆续制定了一批适用于不同地区的扩充 ASCII 字符集，每种扩充 ASCII 字符集分别可以扩充 128 个字符，这些扩充字符的编码均为高位为 1 的 8 位代码（即十进制数 128255 ），称为扩展 ASCII 码。下表展示的是最流行的一套扩展 ASCII 字符集和编码：第二章 计算机硬件基础第一节 中央处理器一、中央处理器的组成 中央处理器简称CPU，由控制器、运算器组成。运算器及控制器的基本功能：运算器是计算机进行算术和逻辑运算的部件，控制器是整个计算机中统一指挥和控制计算机各部件进行工作的控制中心。 二、运算器 运算器是负责对数据进行算术运算或逻辑运算的部件。运算器由算术逻辑单元（ALU）、累加器、状态寄存器、通用寄存器组等组成。如图： 算术逻辑运算单元、累加器和通用寄存器的位数决定了CPU的字长。 三、控制器 是计算机的指令执行部件，其工作是取指令、解释指令以及完成指令的执行。 控制器由指令指针寄存器、指令寄存器、控制逻辑电路和时钟控制电路等组成。 指令指针寄存器（IP）用于 产生及存放一条待取指令的地址。 指令寄存器用于存放指令。指令从内存取出后放入指令寄存器。 四、寄存器 寄存器数量增多可以提高CPU运行速度，但是不能太多，太多会使地址编码和指令长度变长，增加复杂度。由累加器、通用寄存器组、状态寄存器、指令寄存器、地址寄存器、其他寄存器等组成。 五、指令基本格式 单目运算：操作码 地址码 二目运算：操作码 第一地址 第二地址 六、寻址方式：CPU执行指令时寻找数据地址的方式 1、立即寻址：ADD AH,78 其中ADD是操作码，表示做加法；AH是寄存器名；78是个常数；该指令的意思是寄存器AH的值加上78。 2、直接寻址：ADD AH,(78) 78表示操作数的地址 3、间接寻址：ADD AH,(78) 78表示操作数地址的地址 4、相对寻址：ADD AH,*78 *78表示本指令地址+78，78称偏移量 5、变址寻址：ADD AH,(DI+78) DI是变址寄存器,存放一个地址,操作数地址是寄存器地址+78 6、寄存器直接寻址:ADD AH,78 AH是一个寄存器名,即寄存器直接寻址 7、寄存器直接寻址:ADD AH,(BX) BX是一个寄存器名,存放操作数的地址 七、指令分类 1、数据传送指令：MOV AH,BH IN AH,378 2、数据处理指令:算术运算、逻辑运算、移位、比较等 3、程序控制指令：转移、调用、返回 4、状态管理指令：中断、屏蔽中断 八、指令的执行过程 1、CPU发出指令地址 2、读取指令 3、指令送指令寄存器 4、指令译码 5、按指令操作码执行 6、形成下条要执行的指令的地址 九、时钟周期 一个指令执行的时间称为指令周期 计算机完成一个操作（如读取指令等）所需时间称为总线周期 计算机中最基本的时间单位是时钟周期，有CPU的主频决定。第二节 存储器系统一、存储器的分类 分类方法名称举例按存储介质分半导体存储器ROM、RAM（内存）、闪存（优盘）磁表面存储器硬盘、软盘、磁带光存储器CD-ROM、DVD-ROM按工作方式分随机存储器RAM（内存）、硬盘、软盘只读存储器ROM、CD-ROM顺序存储器磁带二、多层次存储体系:如图 三、主存储器 1、特点：容量小、读写速度快、价格高 2、编址方式：存储容量与地址线条数相对应，64M的存储器至少需要26跟地址线（226=64M） 注：我们目前的计算机大都是32位，也就是地址线条数有32条，所以其支持的最大内存容量为4G 3、分类： 随机存储器（RAM）：就是我们通常称的内存，主要参数是存储容量和工作频率。 例如：一条64M8的内存条表示该内存条有64M个单元，每个单元8位。 只读存储器（ROM）：只能读不能写，一般用于存放计算机启动所需的最基本程序。 缓冲存储器（Cache）：速度最快，一般集成于CPU中。 四、辅助存储器 1、磁带：顺序存储，一般只用在小型机以上的计算机中，用作数据备份。 2、软盘：目前常见的一般为3.5寸高密盘，容量为1.44MB，软盘结构如图 注意：盘面最外层的磁道称为0磁道，0磁道如果损坏，则盘片报废。 3、硬盘：硬盘由多个盘面组成一个柱形结构，其原来跟软盘类似，但是磁道更多。 4、光盘：利用光信号读取或写入的存储器。 CD-ROM：只读，容量650MB左右，一倍速为150KB/s DVD-ROM：只读，容量4.7GB左右，一倍速为1200KB/s CD-RW、DVD-RW：可擦写的光盘，但必须专门的刻录机。第三节 输入输出系统一、输入输出控制方式 1、程序查询方式：软件实现，效率低 2、中断方式：软硬件结合实现 中断请求-中断响应-中断处理-中断返回 3、直接存储器访问方式（DMA）：硬件实现 DMA请求-CPU响应并把总线控制权交给DMA控制器-数据交换-交还总线控制权 二、系统总线 分类：数据总线、地址总线、控制总线 总线标准：ISA总线、PCI局部总线、MCA总线 三、I/O接口 1、显卡：分辨率、颜色数决定显示效果和所需显存 例如：显示分辨率为12801024的32位真彩色，所需显卡显存最少为 12801024328 = 5MB 2、硬盘接口： IDE、EIDE Ultra DMA SCSI SATA 3、串行口 4、并行口：通常接针式打印机 5、USB接口：通用串行总线 四、显示器的有关知识 1、屏幕尺寸：15寸、17寸、19寸等 2、点间距：屏幕上象素与象素之间的距离，决定了显示器能显示的最大分辨率。 越小表示能显示的最大分辨率越大。 五、打印机：针式打印机、喷墨打印机、激光打印机。 激光打印机速度最快，针式打印机可以打印票据。 第三章 网络基础知识第一节 网络的组成与结构一、网络组成 1、通信主体：服务器和工作站 2、通信设备：传输介质、网络设备 3、通信协议：通常是TCP/IP 二、网络分类 按传输距离分：局域网（LAN）、城域网（MAN）、广域网（WAN） 按网络结构分：总线型、星型、环型、树型 三、网络拓扑结构第二节 网络协议第 33 页 共 33 页应用层表达层会话层传输层网络层数据链路层物理层一、OSI网络协议的层次国际标准化组织（ISO）提出的“开放系统互连模型（OSI）”是计算机网络通信的基本协议。 该协议分为七层。如下表二、网络设备极其作用第三节 Internet相关知识一、IP地址 每台与Internet连接的主机都必须有一个IP地址，IP地址采用分段式表示：共分4段，每段用一个字节即八个二进制位表示，实际的IP把二进制转换成十进制书写。如61.153.238.132，因为每段时一个字节，因此IP每段的数字大小最大为255。 IP地址分类如下表：目前32位IP地址资源几近枯竭，有人提出用48位表示IP，即IPV6 。 分类二进制表示十进制表示第一段数字A类0七位网络地址24位主机地址128B类1014位网络地址16位主机地址128191C类11021位网络地址8位主机地址192223二、域名：Internet的域名系统叫做DNS，DNS是树形结构的。 域名跟IP地址是多对一的关系 1、域名分级系统：一个域名最右边的部分通常叫顶级域名，往前依次为二级域名、三级域名等。 2、我国域名管理机构:CNNIC 3、常见域名含义： gov 政府 edu 教育 int 国际组织 com 商业组织 mil 军事部门 net 网络运行 org 其他组织 cn 中国 hk 香港 tw 台湾 uk 英国 jp 日本 三、一些常见名词解释 1、Intranet:企业内部网 2、ISP（Internet Service Provider）：因特网服务供应商 3、ICP（Internet Content Provider）：因特网内容供应商 4、IAP（Internet Acess Provider）：因特网接入供应商，目前一般都被ISP包含 5、BBS：电子公告栏，目前通常叫论坛 四、接入Internet的方法 1、PSTN拨号接入：必须设备MODEM，电话线，速度慢 2、DDN专线接入：速度快，费用高。 3、ISDN专线接入：利用传统电话网络的综合业务数字网。 4、分组交换接入 5、帧中继接入第四章 其他相关基础知识第一节 计算机病毒一、特点 寄生性、隐蔽性、非法性、传染性、破坏性 二、分类： 1、引导型病毒：寄生在系统引导区，比较容易被清除，现在已经很少见。 2、文件型病毒：寄生在可执行文件中，感染速度快，较易清除。 3、目录型病毒：寄生在系统目录结构中 4、混合型病毒：多种类型的混合 5、宏病毒：专门感染Microsoft Office 系列文件的病毒 6、蠕虫病毒：感染网络，使网速大大降低。 目前流行的病毒大多集成了黑客技术、木马技术和病毒技术三种，非常难以清除而且很容易中。 三、一些常见危害较大的病毒 1、CIH病毒:文件型病毒，4月26日发作时破坏性最大，首个能破坏硬件系统的病毒。 2、Melissa病毒：宏病毒，邮件传播 3、冲击波、震荡波病毒：利用WINDOWS的漏洞，使计算机自动重启并堵塞网络。第二节 数据库系统一、数据库是数据的一种组织形式，目前存储大量数据基本都采用数据库 常见的数据库软件有：FoxBase、FoxPro、Access、Sql Server、MySql、Sybase、Oracel等。除了最早的如FoxBase等软件，目前流行的数据库软件都是关系型数据库。 二、数据库数据结构数据库系统的数据结构可以认为是多张二维表，二维表中的列称为字段，行存放数据。如下图 二、数据操作 用以对数据库进行检索和更新（添加、删除、更新等）操作 三、数据的完整性约束条件 多个表之间的数据可能存在相互关联，必须保证其完整性 四、数据库操作语言SQL 数据库常用的操作语言称为SQL语言，是一种更高级化的语言，只须告诉计算机做什么事情即可。下面例举几条常用的语句。 1、SELECT 语句 语法：select from where 功能：从表中选出满足条件的记录列 2、INSERT 语句 语法：insert into (列名表) values() 功能：在表中插入一条新记录。 3、DELETE 语句 语法：delete * from where 功能：删除满足条件的记录 4、UPDATE 语句 语法：update set = where 功能：修改满足条件的表中某记录某字段的值第五章 数据结构之线性结构第一节 线性表一、概念 线性表是指由有限个类型相同的数据元素组成的集合，它有以下的特点： 1.有唯一的头结点(即第一个数据元素)和尾结点(即最后一个数据元素)； 2.除结点外，集合中的每个数据元素均只有一个前驱； 3.除尾结点外，集合中的每一个数据元素均只有一个后继。 二、线性表的存储结构 1、顺序结构：是通过数组说明分配连续地址的存储区，通过下标引用数组的相应元素。 2、链式结构：通过指引元素类型的变量对线性表中元素进行动态分配存储。 三、顺序存储结构 1、一维数组 数组存储的结构在数组声明时就需要事先分配相应的连续内存空间用来存放数据。 按首地址（表中第一个元素的地址）的位移来访问数组每一个元素的。 若第一个元素的地址是a，每个元素占用的存储空间为L，则数组的第i个元素的地址可以用如下公式计算： d(i)=a+(i-1)*L 2、二维数组 定义方法：:array1.n,1.m of 对于行为n，列为m的二维数组的元素访问方法： 若第一个元素的地址是a，每个元素占用的存储空间为L，则数组的第(i,j)个元素的地址可以用如下公式计算： 按行寻址：d(i,j)=a+(i-1)*m*L+(j-1)*L 按列寻址：d(i,j)=a+(j-1)*n*L+(i-1)*L 四、链式存储结构 链表是这样一种线性表，它的元素由数据和指针两部分组成，数据部分存放结点的有关信息，指针部分存放下一个结点的位置。 优点：可根据需要分配数据元素的存储区，也可随时撤消链表中数据元素的存储区，插入删除操作只须改变指针，无须移动数据。 缺点：它的数据元素必须在数据项以外至少增加一个指向后继元素的指针类型的数据项，查找其中的某个元素时必须中从第一个元素开始逐个往后找。 一个实例：Type pointer=node;node=Record; data:real; next:pointer; End;Var head,next:pointer; 1.Head为表的首指针，指向链表的第一个结点。 2.整个链表的存取必须从head指针出发，沿着每个结点的next指针顺序进行，最后个结点的next指针为“空”（nil）.第二节 栈一、栈的概念 栈是一种线性表，对它的插入和删除操作都限制在表的同一端进行。这一端叫做栈顶，另一个端叫做栈底。 栈又被成为“后进先出表”（LIFO）。 定义方法： Const m=栈元素的上限； Type stack=array1.m of Var s:stack; t:integer; 二、栈的基本运算 1.入栈：过程push(x)，往栈s中压入一个元素x。 procedure push(x:); begin if t=m then writeln(overflow) else begin t:=t+1; st:=x; end; end; 2.出栈：函数pop(x)，从栈s中弹出一个元素。 function pop:; begin if t=0 then writeln(empty) else begin pop:=st; t:=t-1; end; end; 3.读栈顶元素：函数top，读取栈s的栈顶元素。 function top:; begin if t=0 then writeln(empty) else top:=st; end;第三节 队列一、栈的概念 队列是从日常生活中的排队抽象出来的，根据排队的原则“先来先服务”。 所谓队列就是允许在一端进行插入，另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时，f=r=0。 队列又称为“先进先出（FIFO）”线性表。 定义方法： Const m=队列元素上限; Type duilie=array1.m of ; Var q:duilie; r,f:integer; 二、队列的基本运算 1.过程add(x)：队列q插入元素x Procedure add(x:integer); begin if r=m then writeln(overflow) else begin r:=r+1; qr:=x; end; end; 2.过程del(x)：取出队列q的队首元素y Procedure del(var y:integer); begin if f=r then writeln(empty) else begin f:=f+1; y:=qf; end; end;第六章 数据结构之非线性结构第一节 树的概念一、树的定义 树是一种常见的非线性的数据结构。 树的定义：树是n(n0)个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； 除根外，其余的每个结点都有且仅有一个前驱； 除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后驱（儿子结点）； 二、结点的分类 在树中，一个结点包含一个元素以及所有指向其子树的分支。 结点一般分成三类: 根结点：没有前驱的结点。在树中有且仅有一个根结点。如上图（b）中的r； 分支结点：除根结点外，有后驱的结点称为分支结点。如上图（b）中的a，b，c，x，t，d，i。分支结点亦是其子树的根； 叶结点：没有后驱的结点称为树叶。如上图（b）中的w，h，e，f，s，m，o，n，j，u为叶结点。由树的定义可知，树叶本身也是其父结点的子树。 根结点到每一个分支结点或叶结点的路径是唯一的。例如上图（b）中，从根r到结点i的唯一路径为rcti。 三、有关度的定义 结点的度：一个结点的子树数目称为该结点的度。在上图（b）中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。 树的度：所有结点中最大的度称为该树的度。图（b）中的树的度为3。 四、树的深度（高度） 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。 图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图（b）中树的深度为5。 五、森林 所谓森林，是指若干棵互不相交的树的集合。 如图（b）去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合Ta，Tb，Tc就为森林，这三棵子树的具体形态如图（c）。 六、有序树和无序树 按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。第二节 树的表示方法和存储结构一、树的表示方法 树的表示方法一般有两种： 自然界的树形表示法：用结点和边表示树，例如下图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。 括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如下图(b)可写成如下形式 （r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u） 二、树的存储结构 树的存储结构一般有两种 1.静态的记录数组 所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标。 Const n=树的度； max=结点数的上限；Type node=record data：； 数据域s ch：array1n of integer；指向各儿子的下标 end； treetype=array1.maxof node； Var tree：treetype；该图用静态数组方法保存如右表下标数据域treei.data儿子的下标序列treei.ch1r2342a5603b7004c89105w0006x111207f0008s0009t1314010u00011d150012e00013i16171814j00015h00016m00017o00018n000 2.动态的多重链表 由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下： Const n=树的度；Type treetype=node； node=record data：datatype；数据域 next：array1n of treetype；指向各儿子的指针域 end；Var root：treetype； 上图用多重链表表示如下：第三节 二叉树的概念一、二叉树的递归定义和基本形态 1.二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后继，且其子树有左右之分（次序不能任意颠倒）。 2.二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件： 有一个特定的结点称为根； 余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树； 由上述定义可以看出，二叉树和树是两个不同的概念: 树的每一个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2； 树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后继为左儿子，右后继为右儿子。 3.二叉树的五种基本形态 二、二叉树的两个特殊形态 1.满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如下图(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。 2.完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)） 三、二叉树的三个主要性质 性质1：在二叉树的第i（1）层上，最多有 2i-1个结点。 性质2：在深度为k(k1)的二叉树中最多有2k-1个结点。 性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。 二叉树的性质(1) 在二叉树中，第i层的结点总数不超过2(i-1)；(2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4) 具有n个结点的完全二叉树的深度为int（log2n）+1 (5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I1，则其父结点的编号为I/2；如果2*IN，则无左儿子；如果2*I+1N，则无右儿子。(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。四、普通有序树转换成二叉树 普通树为有序树T，将其转化成二叉树T的规则如下： T中的结点与T中的结点一一对应，即T中每个结点的序号 和值在T中保持不变； T中某结点v的第一个儿子结点为v1，则在T中v1为对应结点v的左儿子结点； T中结点v的儿子序列，在T中被依次链接成一条开始于v1的右链；由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。 五、森林转换成二叉树 如果m棵互不相交的普遍有序树组成了森林F=T1，Tm。我们可以按下述规则将森林F转换成一棵二叉树b=R，LB，RB： 若F为空（m=0），则b为空树； 若F非空（m0），则b的根R即为森林中第一棵树的根R(T1)；b的左子树LB是从T1的根结点的子树森林F1=T11，T12，T1k转换而成的二叉树；其右子树RB是从森林F2=T2，T3，Tm转换成的二叉树。 第四节 二叉树的遍历一、树的存储结构 1.顺序存储结构 将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括 一个数据域（data）； 三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。 满二叉树和完全二叉树一般采用顺序存储结构。 Const m=树中结点数上限；Type node=record结点类型 data：；数据值 prt，lch，rch：0m； 父结点、左儿子、右儿子编号 end； treetype=array1m of node；二叉树的顺序表类型Var Tree：treetype；二叉树 2.链式存储结构 对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域： 值域： data 左指针域：lch 右指针域：rch 这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点 Type bitrpetr=node；结点指针类型 node=record结点类型 data：；值域 lch，rch：bitreptr；左指针域和右指针域 end；Var bt：bitreptr；头指针二、二叉树的遍历 1.二叉树遍历的定义 按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。 2.二叉树遍历的顺序 如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。以下遍历以该树为例三、前序遍历 规则如下： 若二叉树为空，则退出。否则 访问处理根结点； 前序遍历左子树； 前序遍历右子树； 如上图的前序遍历结果为 a b d e h i c f g 顺序结构:Procedue preorder(i:integer);begin if i0 then begin 访问处理treei.data; preorder(treei.lch);递归遍历左子树 preorder(treei.rch);递归遍历右子树 end;end;链式