信息学奥赛-计算机基础知识 33页

第一章计算机基础知识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第33页共33页\n第一章计算机基础知识第一节数制及其转换一、二、八、十六进制转十进制的方法：乘权相加法。例如：（11010110）2=1×27+1×26+0×25+1×24+0×23+1×22+1×21+0×20=（214）10（2365）8=2×83+3×82+6×81+5×80=（1269）10（4BF）16=4×162+11×161+15×160=(1215)10带小数的情况：（110.011）2=1×22+1×21+1×20+0×2-1+1×2-2+1×2-3=（6.375）10（5.76）8=5×80+7×8-1+6×8-2=（5.96875）10（D.1C）16=13×160+1×16-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第33页共33页\n三、二进制转十六进制的方法一位数十六进制与二进制对应表十六进制二进制转换方法:对二进制以小数点为分隔，往前往后每四位划为一组，不足四位补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=11+1=102、减法运算规则：  0-0=0 0-1=1（向高位借1）1-0=11-1=03、乘法运算规则：  0×0=0 0×1=0 1×0=0 1×1=1二、逻辑运算1、基本运算  ①逻辑乘，也称“与”运算，运算符为“·”或“∧”     0·0=0 0·1=0 1·0=0 1·1=1     使用逻辑变量时，A·B可以写成AB  ②逻辑加，也乘“或”运算，运算符为“+”或“∨”     0+0=0  0+1=1 1+0=11+1=1第33页共33页\n  ③逻辑非，也称“反”运算，运算符是在逻辑值或变量符号上加“—”=1  =02、常用运算  异或运算：A⊕B=A·＋·B2、基本公式  ①0，1律     A·0=0     A·1=A     A＋0=A     A＋1=1   ②交换律     A＋B=B＋A     A·B=B·A   ③结合律     A＋B＋C=（A＋B）＋C=A＋（B＋C）     A·B·C=（A·B）·C=A·（B·C）  ④分配律     A·（B＋C）=A·B＋A·C  ⑤重叠律     A＋A＋...＋A=A     A·A·...·A=A  ⑥互补律     A+=1     A·=0  ⑦吸收律     A＋A·B=A      A·（A＋B）=A     A＋·B=A＋B     A·（＋B）=A·B  ⑧对合律     对一个逻辑变量两次取反仍是它本身  ⑨德·摩根定理     =·      =+三、逻辑代数的应用1、逻辑表达式化简  例如：F=·＋A·＋A·B           =·＋A（＋B）    （利用分配律）第33页共33页\n          =·＋A            （利用互补律以及0，1律）         =A＋              （利用吸收律）2、对指定位进行运算，假设变量A有八位，内容是d7d6d5d4d3d2d1d0  ①将变量A的d5位清零     A·（11011111）→A  ②将变量A的各位置1     A＋（11111111）→A   第三节原码、反码和补码   计算机中参与运算的数有正负之分，计算机中的数的正负号也是用二进制表示的。用二进制数表示符号的数称为机器码。常用的机器码有原码、反码和补码。一、原码求原码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位照抄。【例1】X=+1001001  [X]原=01001001【例2】X=-1001001  [X]原=11001001二、反码求反码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位按位取反。【例3】X=+1001001  [X]反=01001001【例4】X=-1001001  [X]反=10110110三、补码求补码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位按位取反后，最低位加1。【例5】X=+1001001  [X]补=01001001【例6】X=-1001001  [X]补=10110111四、补码加减法  计算机中实际上只有加法，减法运算转换成加法运算进行，乘法运算转换成加法运算进行，除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。1、补码加法  [X+Y]补=[X]补+[Y]补第33页共33页\n【例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五、数的表示范围   通过上面的学习，我们就可以知道计算机如果用一个字节表示一个整数的时候，如果是无符号数，可以表示0~255共256个数（00000000~11111111），如果是有符号数则能表示-128~127共256个数（10000000~01111111）。如果两个字节表示一个整数，则共有65536个数可以表示，大部分程序设计语言中整数的范围都是-32768~32767的原因，可以看出这种整数类型是16位的有符号数，而且是补码表示的。第四节浮点数的表示方法一、浮点数表示   一个数的浮点形式（设基数是2）可写成：                   N=M×2E   其中:M代表尾数,E代表阶码。   计算机中浮点数只用尾数和阶码表示，其形式如下：   阶码尾数符号尾数   浮点数的精度由尾数决定，数的表示范围由阶码的位数决定。 　为了最大限度提高精度，尾数采用规格化形式，既1/2≤M<1。采用二进制表示时，若尾数大于零，则规格化数应该是01XXXX的形式；若尾数小于零，则规格化数应为10XXXX的形式。二、机器零第33页共33页\n   当浮点数的尾数为0或阶码为最小值时，计算机通常把该数当作零，因此程序中进行浮点运算时，判断某数是否为零，通常可以用小于某个极小值来代替。三、实例【例1】设X=0.0110×23,用补码、浮点数形式表示阶码为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第33页共33页\n第六节ASCII码表代码字符代码字符代码字符代码字符代码字符32 52472H92\112p33!53573I93]113q34”54674J94^114r35#55775K95_115s36$56876L96`116t37%57977M97a117u38&58:78N98b118v39’59;79O99c119w40(60< 80P100d120x41)61=81Q101e121y42*62> 82R102f122z43+63?83S103g123{44,64@84T104h124|45-65A85U105i125}46.66B86V106j126~47/67C87W107k  48068D88X108l  49169E89Y109m  50270F90Z110n  51371G91[111o     目前使用最广泛的西文字符集及其编码是ASCII字符集和ASCII码（ASCII是AmericanStandardCodeforInformationInterchange的缩写），它同时也被国际标准化组织（InternationalOrganizationforStandardization,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位代码（即十进制数128~255），称为扩展ASCII码。下表展示的是最流行的一套扩展ASCII字符集和编码：第33页共33页\n第二章计算机硬件基础第一节中央处理器一、中央处理器的组成   中央处理器简称CPU，由控制器、运算器组成。   运算器及控制器的基本功能：运算器是计算机进行算术和逻辑运算的部件，控制器是整个计算机中统一指挥和控制计算机各部件进行工作的控制中心。二、运算器   运算器是负责对数据进行算术运算或逻辑运算的部件。运算器由算术逻辑单元（ALU）、累加器、状态寄存器、通用寄存器组等组成。如图：        算术逻辑运算单元、累加器和通用寄存器的位数决定了CPU的字长。三、控制器   是计算机的指令执行部件，其工作是取指令、解释指令以及完成指令的执行。   控制器由指令指针寄存器、指令寄存器、控制逻辑电路和时钟控制电路等组成。   指令指针寄存器（IP）用于  产生及存放一条待取指令的地址。   指令寄存器用于存放指令。指令从内存取出后放入指令寄存器。四、寄存器   寄存器数量增多可以提高CPU运行速度，但是不能太多，太多会使地址编码和指令长度变长，增加复杂度。由累加器、通用寄存器组、状态寄存器、指令寄存器、地址寄存器、其他寄存器等组成。五、指令基本格式   单目运算：操作码地址码   二目运算：操作码第一地址第二地址六、寻址方式：CPU执行指令时寻找数据地址的方式  1、立即寻址：ADDAH,78 其中ADD是操作码，表示做加法；AH是寄存器名；78是个常数；该指令的意思是寄存器AH的值加上78。  2、直接寻址：ADDAH,(78) 78表示操作数的地址  3、间接寻址：ADDAH,((78)) 78表示操作数地址的地址  4、相对寻址：ADDAH,*78  *78表示本指令地址+78，78称偏移量  5、变址寻址：ADDAH,(DI+78)DI是变址寄存器,存放一个地址,操作数地址是寄存器地址+78  6、寄存器直接寻址:ADDAH,78 AH是一个寄存器名,即寄存器直接寻址第33页共33页\n  7、寄存器直接寻址:ADDAH,(BX) BX是一个寄存器名,存放操作数的地址七、指令分类  1、数据传送指令：MOVAH,BH                  INAH,378  2、数据处理指令:算术运算、逻辑运算、移位、比较等  3、程序控制指令：转移、调用、返回  4、状态管理指令：中断、屏蔽中断八、指令的执行过程  1、CPU发出指令地址  2、读取指令  3、指令送指令寄存器  4、指令译码  5、按指令操作码执行  6、形成下条要执行的指令的地址九、时钟周期   一个指令执行的时间称为指令周期   计算机完成一个操作（如读取指令等）所需时间称为总线周期   计算机中最基本的时间单位是时钟周期，有CPU的主频决定。第二节存储器系统一、存储器的分类分类方法名称举例按存储介质分半导体存储器ROM、RAM（内存）、闪存（优盘）磁表面存储器硬盘、软盘、磁带光存储器CD-ROM、DVD-ROM按工作方式分随机存储器RAM（内存）、硬盘、软盘只读存储器ROM、CD-ROM顺序存储器磁带二、多层次存储体系:如图第33页共33页\n三、主存储器   1、特点：容量小、读写速度快、价格高   2、编址方式：存储容量与地址线条数相对应，64M的存储器至少需要26跟地址线（226=64M）   注：我们目前的计算机大都是32位，也就是地址线条数有32条，所以其支持的最大内存容量为4G   3、分类：   ①随机存储器（RAM）：就是我们通常称的内存，主要参数是存储容量和工作频率。      例如：一条64M×8的内存条表示该内存条有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）：硬件实现第33页共33页\n     DMA请求-->CPU响应并把总线控制权交给DMA控制器-->数据交换-->交还总线控制权二、系统总线   分类：数据总线、地址总线、控制总线   总线标准：ISA总线、PCI局部总线、MCA总线三、I/O接口   1、显卡：分辨率、颜色数决定显示效果和所需显存      例如：显示分辨率为1280×1024的32位真彩色，所需显卡显存最少为             1280×1024×32÷8=5MB   2、硬盘接口：     ①IDE、EIDE     ②UltraDMA     ③SCSI     ④SATA   3、串行口   4、并行口：通常接针式打印机   5、USB接口：通用串行总线四、显示器的有关知识   1、屏幕尺寸：15寸、17寸、19寸等   2、点间距：屏幕上象素与象素之间的距离，决定了显示器能显示的最大分辨率。越小表示能显示的最大分辨率越大。五、打印机：针式打印机、喷墨打印机、激光打印机。   激光打印机速度最快，针式打印机可以打印票据。第三章网络基础知识第一节网络的组成与结构一、网络组成  1、通信主体：服务器和工作站  2、通信设备：传输介质、网络设备  3、通信协议：通常是TCP/IP二、网络分类   按传输距离分：局域网（LAN）、城域网（MAN）、广域网（WAN）   按网络结构分：总线型、星型、环型、树型三、网络拓扑结构第33页共33页\n第二节网络协议第33页共33页应用层表达层会话层传输层网络层数据链路层物理层一、OSI网络协议的层次国际标准化组织（ISO）提出的“开放系统互连模型（OSI）”是计算机网络通信的基本协议。该协议分为七层。如下表二、网络设备极其作用第33页共33页第33页共33页\n第三节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位主机地址128~191C类11021位网络地址8位主机地址192~223二、域名：Internet的域名系统叫做DNS，DNS是树形结构的。域名跟IP地址是多对一的关系   1、域名分级系统：一个域名最右边的部分通常叫顶级域名，往前依次为二级域名、三级域名等。   2、我国域名管理机构:CNNIC   3、常见域名含义：   gov政府edu教育int国际组织com商业组织mil军事部门net网络运行 org其他组织   cn中国 hk香港 tw台湾 uk英国jp日本三、一些常见名词解释   1、Intranet:企业内部网   2、ISP（InternetServiceProvider）：因特网服务供应商   3、ICP（InternetContentProvider）：因特网内容供应商   4、IAP（InternetAcessProvider）：因特网接入供应商，目前一般都被ISP包含   5、BBS：电子公告栏，目前通常叫论坛四、接入Internet的方法   1、PSTN拨号接入：必须设备MODEM，电话线，速度慢   2、DDN专线接入：速度快，费用高。   3、ISDN专线接入：利用传统电话网络的综合业务数字网。   4、分组交换接入   5、帧中继接入第33页共33页\n第四章其他相关基础知识第一节计算机病毒一、特点   寄生性、隐蔽性、非法性、传染性、破坏性二、分类：   1、引导型病毒：寄生在系统引导区，比较容易被清除，现在已经很少见。   2、文件型病毒：寄生在可执行文件中，感染速度快，较易清除。   3、目录型病毒：寄生在系统目录结构中   4、混合型病毒：多种类型的混合   5、宏病毒：专门感染MicrosoftOffice系列文件的病毒   6、蠕虫病毒：感染网络，使网速大大降低。   目前流行的病毒大多集成了黑客技术、木马技术和病毒技术三种，非常难以清除而且很容易中。三、一些常见危害较大的病毒   1、CIH病毒:文件型病毒，4月26日发作时破坏性最大，首个能破坏硬件系统的病毒。   2、Melissa病毒：宏病毒，邮件传播   3、冲击波、震荡波病毒：利用WINDOWS的漏洞，使计算机自动重启并堵塞网络。第二节数据库系统一、数据库是数据的一种组织形式，目前存储大量数据基本都采用数据库  常见的数据库软件有：FoxBase、FoxPro、Access、SqlServer、MySql、Sybase、Oracel等。除了最早的如FoxBase等软件，目前流行的数据库软件都是关系型数据库。二、数据库数据结构数据库系统的数据结构可以认为是多张二维表，二维表中的列称为字段，行存放数据。如下图   第33页共33页\n二、数据操作   用以对数据库进行检索和更新（添加、删除、更新等）操作  三、数据的完整性约束条件  多个表之间的数据可能存在相互关联，必须保证其完整性四、数据库操作语言SQL   数据库常用的操作语言称为SQL语言，是一种更高级化的语言，只须告诉计算机做什么事情即可。下面例举几条常用的语句。   1、SELECT语句   语法：select<列名>from<表名>where<条件>   功能：从表中选出满足条件的记录列   2、INSERT语句   语法：insertinto<表名>[(列名表)]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、二维数组  ①定义方法：<数组名>:array[1..n,1..m]of<元素类型>第33页共33页\n  ②对于行为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=array[1..m]of<元素类型>  Var    s:stack;    t:integer;二、栈的基本运算　 1.入栈：过程push(x)，往栈s中压入一个元素x。　procedurepush(x:<元素类型>); begin第33页共33页\n   ift=m      thenwriteln(‘overflow’)      elsebegin            t:=t+1;            s[t]:=x;           end; end;   2.出栈：函数pop(x)，从栈s中弹出一个元素。　functionpop:<元素类型>; begin   ift=0      thenwriteln('empty')      elsebegin             pop:=s[t];             t:=t-1;           end; end;   3.读栈顶元素：函数top，读取栈s的栈顶元素。　functiontop:<元素类型>; begin   ift=0      thenwriteln('empty')      elsetop:=s[t]; end;第三节队列一、栈的概念  队列是从日常生活中的排队抽象出来的，根据排队的原则“先来先服务”。所谓队列就是允许在一端进行插入，另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时，f=r=0。队列又称为“先进先出（FIFO）”线性表。  定义方法：  Const    m=队列元素上限;  Type    duilie=array[1..m]of<元素类型>;  Var    q:duilie;r,f:integer;二、队列的基本运算　 1.过程add(x)：队列q插入元素x　Procedureadd(x:integer); begin   ifr=m第33页共33页\n      thenwriteln(‘overflow’)      elsebegin             r:=r+1;             q[r]:=x;           end; end;   2.过程del(x)：取出队列q的队首元素y　Proceduredel(vary:integer); begin   iff=r      thenwriteln(‘empty’)      elsebegin             f:=f+1;             y:=q[f];           end; end;第六章数据结构之非线性结构第一节树的概念一、树的定义   树是一种常见的非线性的数据结构。   树的定义：树是n(n>0)个结点的有限集，这个集合满足以下条件：   ⑴有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；   ⑵除根外，其余的每个结点都有且仅有一个前驱；   ⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后驱（儿子结点）；二、结点的分类   在树中，一个结点包含一个元素以及所有指向其子树的分支。   结点一般分成三类:第33页共33页\n   ⑴根结点：没有前驱的结点。在树中有且仅有一个根结点。如上图（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)可写成如下形式第33页共33页\n（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：array[1‥n]ofinteger；{指向各儿子的下标}      end； treetype=array[1..max]ofnode；Var tree：treetype；该图用静态数组方法保存如右表下标数据域tree[i].data儿子的下标序列tree[i].ch1r2342a5603b7004c89105w0006x111207f0008s0009t1314010u00011d150012e000第33页共33页\n13i16171814j00015h00016m00017o00018n000  2.动态的多重链表   由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n为树的度)个指针域共n+1个域组成，其表示方法如下： 　Const n=树的度；Type treetype=^node； node=record       data：datatype；{数据域}       next：array[1‥n]oftreetype；{指向各儿子的指针域}      end；Var root：treetype；　上图用多重链表表示如下：第三节二叉树的概念一、二叉树的递归定义和基本形态   1.二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后继，且其子树有左右之分（次序不能任意颠倒）。   2.二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：第33页共33页\n   ⑴有一个特定的结点称为根；   ⑵余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；  由上述定义可以看出，二叉树和树是两个不同的概念:   ⑴树的每一个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2；   ⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后继为左儿子，右后继为右儿子。   3.二叉树的五种基本形态二、二叉树的两个特殊形态  1.满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如下图(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。  2.完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）  三、二叉树的三个主要性质  性质1：在二叉树的第i（≥1）层上，最多有2i-1个结点。  性质2：在深度为k(k≥1)的二叉树中最多有2k-1个结点。  性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。二叉树的性质(1)在二叉树中，第i层的结点总数不超过2^(i-1)；(2)深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；(3)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4)具有n个结点的完全二叉树的深度为int（log2n）+1第33页共33页\n(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则如果I<>1，则其父结点的编号为I/2；如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。(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非空（m≠0），则b的根R即为森林中第一棵树的根R(T1)；b的左子树LB是从T1的根结点的子树森林F1={T11，T12，…T1k}转换而成的二叉树；其右子树RB是从森林F2={T2，T3，…，Tm}转换成的二叉树。第33页共33页\n第四节二叉树的遍历一、树的存储结构  1.顺序存储结构   将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括  ⑴一个数据域（data）；  ⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。满二叉树和完全二叉树一般采用顺序存储结构。　Const m=树中结点数上限；Type node=record{结点类型}       data：<数据类型>；{数据值}       prt，lch，rch：0‥m；{父结点、左儿子、右儿子编号}      end； treetype=array[1‥m]ofnode；{二叉树的顺序表类型}Var Tree：treetype；{二叉树}  2.链式存储结构   对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：  ⑴值域：data  ⑵左指针域：lch  ⑶右指针域：rch 这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点　　Type bitrpetr=^node；{结点指针类型} node=record{结点类型}       data：<数据类型>；{值域}　第33页共33页\n       lch，rch：bitreptr；{左指针域和右指针域}      end；Var bt：bitreptr；{头指针}二、二叉树的遍历   1.二叉树遍历的定义   按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。   2.二叉树遍历的顺序   如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、LRD、DLR、DRL、RDL、RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。 以下遍历以该树为例三、前序遍历   规则如下：   若二叉树为空，则退出。否则    ⑴访问处理根结点；    ⑵前序遍历左子树；    ⑶前序遍历右子树；  如上图的前序遍历结果为abdehicfg顺序结构:Proceduepreorder(i:integer); begin ifi<>0  thenbegin   访问处理tree[i].data;   preorder(tree[i].lch);{递归遍历左子树}   preorder(tree[i].rch);{递归遍历右子树}  end; end;链式结构:Proceduepreorder(bt:bitreptr); begin ifbt<>nil    thenbegin       访问处理bt^.data;       preorder(bt^.lch);{递归遍历左子树}       preorder(bt^.rch);{递归遍历右子树}     end; end;　第33页共33页\n四、中序遍历   规则如下：   若二叉树为空，则退出；否则   ⑴中序遍历左子树；   ⑵访问处理根结点；   ⑶中序遍历右子树；   如上图的中序遍历结果为dbheiafcg顺序结构:Procedueinorder(i:integer); begin ifi<>0  thenbegin   inorder(tree[i].lch);{递归遍历左子树}   访问处理tree[i].data;   inorder(tree[i].rch);{递归遍历右子树}  end; end;链式结构:Procedueinorder(bt:bitreptr); begin ifbt<>nil    thenbegin       inorder(bt^.lch);{递归遍历左子树}       访问处理bt^.data;       inorder(bt^.rch);{递归遍历右子树}     end; end;　五、后序遍历   规则如下：   若二叉树为空，则退出；否则   ⑴后序遍历左子树；   ⑵后序遍历右子树；   ⑶访问处理根结点；   如上图的后序遍历结果为dhiebfgca顺序结构:Proceduepostorder(i:integer);begin ifi<>0 thenbegin  postorder(tree[i].lch);{递归遍历左子树}  postorder(tree[i].rch);{递归遍历右子树}  访问处理tree[i].data; end;end;链式结构:Proceduepostorder(bt:bitreptr); begin ifbt<>nil    thenbegin      postorder(bt^.lch);{递归遍历左子树}      postorder(bt^.rch);{递归遍历右子树}      访问处理bt^.data;     end; end;第五节普通树的遍历一、先根次序遍历树第33页共33页\n   规则：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。上图先根遍历次序为rawxdhebfcstimonju   当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。二、后根次序遍历树   规则：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。   上图后根遍历次序为whdexafbsmonijtucr   当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。三、森林的遍历   1.先根遍历森林     若森林非空，则可按下述规则遍历之     ①访问森林中第一棵树的根结点；     ②先根遍历第一棵树中根结点的子树森林；     ③先根遍历其余树构成的森林；   若对下图的森林进行先根遍历，则得到森林的先根序列为ABDCEFGHJI。森林的先根遍历即为其对应的二叉树的前序遍历。  2.后根遍历森林    若森林非空，则可按下述规则遍历之     ①后根遍历森林中第一棵树的根结点的子树森林；     ②访问第一棵树的根结点；第33页共33页\n     ③后根遍历其余树构成的森林；   若对上图(a)中的森林进行先根遍历，则得到森林的后根序列为BCDAFEHJIG。森林的后根遍历即为其对应的二叉树的中序遍历。例如，对上图(c)中的二叉树进行中序遍历，亦可得出对应森林（上图(a)的后根遍历序列。第六节根据两种遍历顺序确定树结构一、由两种顺序确定树结构   遍历二叉树有三种规则：   前序遍历：根—左子树—右子树；   中序遍历：左子树—根—右子树；   后序遍历：左子树—右子树—根；   由于前序遍历的第一个字符和后序遍历的最后一个字符为根，中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构，因此二叉树的形态可以由其中序与后序或者前序与中序唯一确定。但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点，因此这两个遍历顺序可对应多种二叉树的形态。二、由中序遍历与后序遍历确定前序遍历   由二叉树的遍历规则可以看出，后序遍历的最后一个字符为根，中序遍历中位于该字符左侧的子串为左子树中序遍历的结果；中序遍历中位于该字符右侧的子串为右子树中序遍历的结果。   设中序遍历s1='s1…sk…sn'      后序遍历s2='s1……sn'   显然，后序遍历中的sn为二叉树的根。按照前序遍历的规则输出sn。在中序遍历中与sn相同的字符为sk。若k>1，说明左子树存在，位于sk左侧的子串s1…sk-1为左子树中序遍历的结果，后序遍历中的前缀s1…sk-1为左子树后序遍历的结果；若k1           {若左子树存在，则递归遍历左子树}             thensolve1(copy(s1，1，k-1)，copy(s2，1，k-1))；          ifk1       {若左子树存在，则递归遍历左子树}              thensolve2(copy(s1，1，k-1)，copy(s2，2，k-1))；           ifk0                thenp:=b[p]．l                elsebeginb[p]．l:=i;break;end          else            {若a[i]≥b[p]．data时顺右指针方向寻找顶点i的插入位置}              ifb[p]．r<>0第33页共33页\n                thenp:=b[p]．r                elsebeginb[p]．r:=i;break;end;      end;{while}  end;{for}end;{createtree}第八节最优二叉树(哈夫曼树)一、概念   在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使（Wk—第k个叶结点的权值；Pk—第k个叶结点的带权路径长度）达到最小。二、最优二叉树的构造方法  假定给出n个结点ki(i=1‥n)，其权值分别为Wi(i=1‥n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：   首先，将给定的n个结点构成n棵二叉树的集合F={T1，T2，……，Tn}。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步   ⑴在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；   ⑵在F中删除这两棵二叉树，同时将新得到的二叉树加入F重复⑴、⑵，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。三、最优二叉树的数据类型定义   在最优二叉树中非叶结点的度均为2，为满二叉树，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。   Constn=叶结点数的上限；         m=2*n-1；{最优二叉树的结点数}   Type        node=record{结点类型}          data：<数据类型>；{权值}          prt，lch，rch,lth：0‥m；{父指针、左、右指针和路径长度}        end；        wtype=array[1‥n]of<数据类型>；{n个叶结点权值的类型}        treetype=array[1‥m]ofnode；{最优二叉树的数组类型}   Vartree：treetype；               {其中tree[1‥n]为叶结点，tree[n+1‥2n-1]为中间结点，根为tree[2n-1]}第33页共33页\n四、构造最优二叉树的算法procedurehufm(w：wtype；vartree：treetype；varbt：integer)； functionmin(h：integer)：integer；{在前h个结点中选择父指针为0且权值最小的结点min}    begin      ml:=∞；      forp:=1tohdo        if(tree[p]．prt=0)and(m1>tree[p]．data)            thenbegini:=p；m1:=tree[p]．data；end；      min:=i；   end；{min} begin   fillchar(tree，sizeof(tree)，0)；{构造初始集合F}   fori:=1tondo     read(tree[i]．Data)；   fork:=n+1tomdo{构造最优二叉树}     begin{计算k为根的左儿子和右儿子}       i:=min(k-1)；       tree[i]．prt:=k；       tree[k]．lch:=i；       j:=min(k-1)；       tree[j]．prt:=k；       tree[k]．rch:=j；       tree[k]．data:=tree[i]．data+tree[j]．data；     end；{for}   bt:=m；  end；{hufm}{计算每一个叶结点的路径长度}procedureht(t:integer);{通过前序遍历计算每一个叶结点的路径长度} begin   ift=m{若结点t为根，则路径长度为0；否则结点t的路径长度为其父结点的路径长度+1}     thentree[t].lth:=0     elsetree[t].lth:=tree[tree[t].prt].lth+1；   iftree[t].lch<>0     thenbeginht(tree[t].lch)；ht(tree[t].rch)；end；{then}{分别递归左右子树}  end；{ht}　由此可见，叶结点t（1≤t≤5）的带权路径长度即为tree[t].lth*tree[t].data。AOE网AOE网（ActivityOnEdgNetwork）第33页共33页\n 　在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网,如下图。  AOE网具有以下性质：　　（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。　　（2）只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的时事件才能发生。　　可以将上图假想一个工程有6项活动，网中5个顶点，分别表示5个事件，边上的权值分别表示各项活动所需要的时间，事件v1表示工程开始，事件v3表示活动3和4完成后，活动5可以开始，事件v4表示活动2完成活动4和活动6开始，v5表示活动1完成活动3开始，事件v2表示工程结束。 　　关键路径（临界路径）：在AOE网络中从源点到汇点（结束顶点）的最长路径。关键路径上的活动为关键活动。第33页共33页