第一章 计算机基础知识 ........................................................... 2
第一节 数制及其转换 ......................................................... 2 第二节 算术运算和逻辑运算 ................................................... 4 第三节 原码、反码和补码 ..................................................... 7 第四节 浮点数的表示方法 ..................................................... 9 第五节 奇偶校验 ............................................................ 10 第六节 ASCII码表 ........................................................... 12 第二章 计算机硬件基础 .......................................................... 13
第一节 处理器 .......................................................... 13 第二节 存储器系统 .......................................................... 15 第三节 输入输出系统 ........................................................ 17 第三章 网络基础知识 ............................................................ 19
第一节 网络的组成与结构 .................................................... 19 第二节 网络协议 ............................................................ 20 第三节 Internet相关知识 .................................................... 20 第三节 Internet相关知识 .................................................... 21 第四章 其他相关基础知识 ........................................................ 23
第一节 计算机病毒 .......................................................... 23 第二节 数据库系统 .......................................................... 23 第五章 数据结构之线性结构 ...................................................... 25
第一节 线性表 .............................................................. 25 第二节 栈 .................................................................. 27 第三节 队列 ................................................................ 29 第六章 数据结构之非线性结构 .................................................... 31
第一节 树的概念 ............................................................ 31 第二节 树的表示方法和存储结构 .............................................. 33 第三节 二叉树的概念 ........................................................ 36 第四节 二叉树的遍历 ........................................................ 40 第五节 普通树的遍历 ........................................................ 44 第六节 根据两种遍历顺序确定树结构 .......................................... 46 第七节 二叉排序树 .......................................................... 47 第八节 最优二叉树(哈夫曼树) ................................................ 48 AOE网 ...................................................................... 50
.
.
第一章 计算机基础知识
第一节 数制及其转换
一、二、八、十六进制转十进制的方法：乘权相加法。 例如：
（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×16 + 1×16+ 12*16 = （13.109375）10
二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。 例一：（43）10 = （101011）2
例二：（0.375）10 = （0.011）2
0
-1
-2
.
.
三、二进制转八进制的方法 一位数八进制与二进制对应表
八进制 二进制 转换方法:对二进制以小数点为分隔，往前往后每三位划为一组， 0 1 2 3 4 5 6 7 000 不足三位补0，按上表用对应的八进制数字代入即可。 001 例如：(10111011.01100111) 010 011 100 101 110 111 = 010,111,011.011,001,110 = （273.36）8 三、二进制转十六进制的方法 一位数十六进制与二进制对应表 十六进制 0 1 2 3 4 5 6 二进制 转换方法:对二进制以小数点为分隔，往前往后每四位划 0000 0001 0010 0011 0100 0101 0110 为一组，不足四位补0，按上表用对应的十六进 制数字代入即可。 例如：(10111011.01100111) = 1011,1011.0110,0111 = （BB.67）16 .
.
7 8 9 A B C D E F 0111 1000 1001 1010 1011 1100 1101 1110 1111 四、进制的英文表示法：
以上都是用括号加数字的表示方法，另外还有英文表示法，就是以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、乘法运算规则：
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=1 1+1=1
③ 逻辑非，也称“反”运算，运算符是在逻辑值或变量符号上加“—”
0 = 1 1 = 0
2、常用运算
异或运算：A⊕B =A·B＋A·B 2、基本公式 ① 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 + A = 1 A·A = 0 ⑦ 吸收律
A＋A·B = A A·（A＋B） = A A＋A·B = A＋B A·（A＋B） = A·B ⑧ 对合律
对一个逻辑变量两次取反仍是它本身 ⑨ 德·摩根定理 AB = A·B A•B= A+B 三、逻辑代数的应用 1、逻辑表达式化简
例如： F = A·B＋A·B＋A·B
=A·B＋A（B＋B） （利用分配律）
.
.
=A·B＋A （利用互补律以及0，1律） = A＋B （利用吸收律）
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]补
【例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 × 2 其中:M代表尾数,E代表阶码。
计算机中浮点数只用尾数和阶码表示，其形式如下：
阶码 尾数符号 尾数 E
浮点数的精度由尾数决定，数的表示围由阶码的位数决定。
为了最大限度提高精度，尾数采用规格化形式，既1/2≤M<1。采用二进制表示时，若尾数大于零，则规格化数应该是01XXXX的形式；若尾数小于零，则规格化数应为10XXXX的形式。 二、机器零
当浮点数的尾数为0或阶码为最小值时，计算机通常把该数当作零，因此程序中进行浮点运算时，判断某数是否为零，通常可以用小于某个极小值来代替。 三、实例
.
.
【例1】设X=0.0110×2 ,用补码、浮点数形式表示阶码为Xj=011，尾数为00110，这时由于X尾数不符合01XXXX的形式，因此不是规格化数，必须先进行规格化处理。 方法：若尾数小于1/2，把尾数左移一位（不包括符号位），观察结果是否满足规格化条件，满足则在把阶码减1即可，否则继续左移和调整阶码；若尾数大于1，则把尾数右移一位（不包括符号位），观察结果是否满足规格化条件，满足则在把阶码加1即可，否则继续右移和调整阶码。
上例中，00110左移一位为01100，符合规则化标准，此时阶码减1，为010即得到浮点表示形式。
这个数具体在计算机中如何表示要看计算机中规定的阶码和尾数的位数，若阶码和尾数均为16位，则上面的数X在计算机部表示就是
00000000000000100110000000000000 ，不足均用零填充。
3
第五节 奇偶校验
计算机中数据在进行存储和传输过程中可能会发生错误。为了及时发现和纠正这类
错误，在数据传输（存储）过程中要进行校验，常用的校验方法就是奇偶校验。 奇偶校验能发现一位或奇数位错误，且不能纠正错误。一般以字节（八位二进制）为单位加1位奇偶校验位。奇偶校验分奇校验和偶校验两种。
一、奇校验：一个字节前面加一位校验位使得“1”的个数保持为奇数，若八位二进制数中“1”的个数为偶数，则校验位为“1”；若八位二进制数中“1”的个数为奇数，则校验位为“0”。
【例1】给1001100101101101加奇校验结果为110011001001101101
.
.
二、偶校验：一个字节前面加一位校验位使得“1”的个数保持为偶数，若八位二进制数中“1”的个数为偶数，则校验位为“0”；若八位二进制数中“1”的个数为奇数，则校验位为“1”。
【例2】给1001100101101101加偶校验结果为010011001101101101
.
.
第六节 ASCII码表
代码 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 字符 ! ” # $ % & ’ ( ) * + , - . / 0 1 2 3 代码 52 53 54 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 71 字符 4 5 6 7 8 9 : ; < = > ? A B C D E F G 代码 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 90 91 字符 H I J K L M N O P Q R S T U V W X Y Z [ 代码 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 字符 \\ ] ^ _ ` a b c d e f g h i j k l m n o 代码 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 字符 p q r s t u v w x y z { | } ~ 目前使用最广泛的西文字符集及其编码是 ASCII 字符集和 ASCII 码（ ASCII 是 American
Standard Code for Information Interchange 的缩写），它同时也被国际标准化组织（ International Organization for Standardization, ISO ）批准为国际标准。
基本的 ASCII 字符集共有 128 个字符，其中有 96 个可打印字符，包括常用的字母、数字、标点符号等，另外还有 32 个控制字符。标准 ASCII 码使用 7 个二进位对字符进行编码，对应的 ISO 标准为 ISO6 标准。下表展示了基本 ASCII 字符集及其编码：
字母和数字的 ASCII 码的记忆是非常简单的。我们只要记住了一个字母或数字的 ASCII 码（例如记住 A 为 65 ， 0 的 ASCII 码为 48 ），知道相应的大小写字母之间差 32 ，就可以推算出其余字母、数字的 ASCII 码。
虽然标准 ASCII 码是 7 位编码，但由于计算机基本处理单位为字节（ 1byte = 8bit ），所以一般仍以一个字节来存放一个 ASCII 字符。每一个字节中多余出来的一位（最高位）在计算机部通常保持为 0 （在数据传输时可用作奇偶校验位）。
由于标准 ASCII 字符集字符数目有限，在实际应用中往往无法满足要求。为此，国际标准化组织又制定了 ISO2022 标准，它规定了在保持与 ISO6 兼容的前提下将 ASCII 字符集扩充为 8 位代码的统一方法。 ISO 陆续制定了一批适用于不同地区的扩充 ASCII 字符集，每种扩充 ASCII 字符集分别可以扩充 128 个字符，这些扩充字符的编码均为高位为 1 的 8 位代码（即十进制数 128~255 ），称为扩展 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、编址方式：存储容量与地址线条数相对应，M的存储器至少需要26跟地址线（226=M）
注：我们目前的计算机大都是32位，也就是地址线条数有32条，所以其支持的最大存容量为4G 3、分类：
① 随机存储器（RAM）：就是我们通常称的存，主要参数是存储容量和工作频率。 例如：一条M×8的存条表示该存条有M个单元，每个单元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、显卡：分辨率、颜色数决定显示效果和所需显存
例如：显示分辨率为1280×1024的32位真彩色，所需显卡显存最少为 1280×1024×32÷8 = 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） 按网络结构分：总线型、星型、环型、树型 三、网络拓扑结构
.
.
第二节 网络协议
一、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位主机地址 16位主机地址 8位主机地址 十进制表示第一段数字 <128 128~191 192~223 B类 10 14位网络地址 21位网络地址 C类 110 二、域名：Internet的域名系统叫做DNS，DNS是树形结构的。 域名跟IP地址是多对一的关系
1、域名分级系统：一个域名最右边的部分通常叫顶级域名，往前依次为二级域名、三级域名等。
2、我国域名管理机构:CNNIC 3、常见域名含义：
gov edu 教育 int 国际组织 商业组织 mil 军事部门 net 网络运行 org 其他组织
中国 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、二维数组
① 定义方法：<数组名>:array[1..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=array[1..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; s[t]:=x; end; end;
2.出栈：函数pop(x)，从栈s中弹出一个元素。
function pop:<元素类型>;
begin
.
.
if t=0
then writeln('empty') else begin pop:=s[t]; t:=t-1; end; end;
3.读栈顶元素：函数top，读取栈s的栈顶元素。
function top:<元素类型>; begin if t=0
then writeln('empty') else top:=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
Procedure add(x:integer); begin if r=m
then writeln(‘overflow’)
else begin r:=r+1; q[r]:=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:=q[f]; end; end;
第六章 数据结构之非线性结构
第一节 树的概念
一、树的定义
树是一种常见的非线性的数据结构。
树的定义：树是n(n>0)个结点的有限集，这个集合满足以下条件： ⑴ 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； ⑵ 除根外，其余的每个结点都有且仅有一个前驱；
⑶ 除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后驱（儿子结点）；
二、结点的分类
在树中，一个结点包含一个元素以及所有指向其子树的分支。 结点一般分成三类:
.
.
⑴ 根结点：没有前驱的结点。在树中有且仅有一个根结点。如上图（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：array[1‥n] of integer；{指向各儿子的下标} end； treetype=array[1..max]of node； Var tree：treetype； 数据域 儿子的下标序列 下标 tree[i].data tree[i].ch 1 2 3 4 5 该图用静态数组方法保存如右表 6 x 11 12 0 r a b c w 2 5 7 8 0 3 6 0 9 0 4 0 0 10 0 .
.
7 8 9 10 11 12 13 14 15 16 17 18 f s t u d e i j h m o n 0 0 13 0 15 0 16 0 0 0 0 0 0 0 14 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 2.动态的多重链表
由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下：
Const
n=树的度； Type
.
.
treetype=^node； node=record data：datatype；{数据域} next：array[1‥n] 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(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
(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}转换成的二叉树。
.
.
第四节 二叉树的遍历
一、树的存储结构 1.顺序存储结构
将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括 ⑴ 一个数据域（data）；
⑵ 三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。 满二叉树和完全二叉树一般采用顺序存储结构。
Const m=树中结点数上限； Type node=record{结点类型}
data：<数据类型>；{数据值} prt，lch，rch：0‥m； {父结点、左儿子、右儿子编号} end； treetype=array[1‥m] of node；{二叉树的顺序表类型} .
.
Var Tree：treetype；{二叉树} 2.链式存储结构
对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域： ⑴ 值域： 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 i<>0 .
链式结构: Procedue preorder(bt:bitreptr); begin if bt<>nil .
then begin 访问处理tree[i].data; preorder(tree[i].lch);{递归遍历左子树} preorder(tree[i].rch);{递归遍历右子树} end; end; then begin 访问处理bt^.data; preorder(bt^.lch);{递归遍历左子树} preorder(bt^.rch);{递归遍历右子树} end; end;
四、中序遍历 规则如下：
若二叉树为空，则退出；否则 ⑴ 中序遍历左子树； ⑵ 访问处理根结点； ⑶ 中序遍历右子树；
如上图的中序遍历结果为 d b h e i a f c g
顺序结构: Procedue inorder(i:integer); begin if i<>0 then begin inorder(tree[i].lch);{递归遍历左子树} 访问处理tree[i].data; inorder(tree[i].rch);{递归遍历右子树} end; end; 链式结构: Procedue inorder(bt:bitreptr); begin if bt<>nil then begin inorder(bt^.lch);{递归遍历左子树} 访问处理bt^.data; inorder(bt^.rch);{递归遍历右子树} end; end;
五、后序遍历 规则如下：
若二叉树为空，则退出；否则 ⑴ 后序遍历左子树； ⑵ 后序遍历右子树；
.
.
⑶ 访问处理根结点；
如上图的后序遍历结果为 d h i e b f g c a
顺序结构: Procedue postorder(i:integer); begin if i<>0 then begin postorder(tree[i].lch);{递归遍历左子树} postorder(tree[i].rch);{递归遍历右子树} 访问处理tree[i].data; end; end; 链式结构: Procedue postorder(bt:bitreptr); begin if bt<>nil then begin postorder(bt^.lch);{递归遍历左子树} postorder(bt^.rch);{递归遍历右子树} 访问处理bt^.data; end; end; 第五节 普通树的遍历
一、先根次序遍历树
规则：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。
上图先根遍历次序为 r a w x d h e b f c s t i m o n j u
当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。
二、后根次序遍历树
规则：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。
.
.
上图后根遍历次序为 w h d e x a f b s m o n i j t u c r
当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。
三、森林的遍历 1.先根遍历森林
若森林非空，则可按下述规则遍历之 ① 访问森林中第一棵树的根结点；
② 先根遍历第一棵树中根结点的子树森林； ③ 先根遍历其余树构成的森林；
若对下图的森林进行先根遍历，则得到森林的先根序列为A B D C E F G H J I。森林的先根遍历即为其对应的二叉树的前序遍历。
2.后根遍历森林
若森林非空，则可按下述规则遍历之
① 后根遍历森林中第一棵树的根结点的子树森林； ② 访问第一棵树的根结点； ③ 后根遍历其余树构成的森林；
.
.
若对上图(a)中的森林进行先根遍历，则得到森林的后根序列为B C D A F E H J I G 。森林的后根遍历即为其对应的二叉树的中序遍历。例如，对上图(c)中的二叉树进行中序遍历，亦可得出对应森林（上图(a)的后根遍历序列。
第六节 根据两种遍历顺序确定树结构
一、由两种顺序确定树结构 遍历二叉树有三种规则：
前序遍历：根—左子树—右子树； 中序遍历：左子树—根—右子树； 后序遍历：左子树—右子树—根；
由于前序遍历的第一个字符和后序遍历的最后一个字符为根，中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构，因此二叉树的形态可以由其中序与后序或者前序与中序唯一确定。但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点，因此这两个遍历顺序可对应多种二叉树的形态。 二、由中序遍历与后序遍历确定前序遍历
由二叉树的遍历规则可以看出，后序遍历的最后一个字 符为根，中序遍历中位于该字符左侧的子串为左子树中序遍历的结果；中序遍历中位于该字符右侧的子串为右子树中序遍历的结果。 设 中序遍历s1='s1…sk …sn' 后序遍历s2='s1……sn'
显然，后序遍历中的sn为二叉树的根。按照前序遍历的规则输出sn。在中序遍历中与sn相同的字符为sk。若k>1，说明左子树存在，位于sk左侧的子串s1…sk-1为左子树中序遍历的结果，后序遍历中的前缀s1…sk-1为左子树后序遍历的结果；若k end; 三、由中序遍历与前序遍历确定后序遍历 原理同前，程序略微有些不同，看下面: procedure solve2(s1，s2:string)；{计算和输出中序遍历s1和前序遍历s2对应的后序遍历} var k:integer； begin if length(s2)=1 {若当前子树仅剩一个节点，则输出} then write(s2) else begin k:=pos(s2[1]，s1)； {在中序遍历中寻找子树根} if k>1 {若左子树存在，则递归遍历左子树} then solve2(copy(s1，1，k-1)，copy(s2，2，k-1))； if k 所谓二叉排序树是指具有下列性质的非空二叉树 ⑴ 若根结点的左子树不空，则左子树的所有结点值均小于根结点值； ⑵ 若根结点的右子树不空，则右子树的所有结点值均不小于根结点值； ⑶ 根结的左右树也分别为二叉排序树； 显然，对二叉排序树进行中序遍历，可得出结点值递增的排序序列。 {假设待排序的数存在数组a中} procedure createtree; begin fillchar(b，sizeof(b)，0); b[1].data:=a[1]; {二叉排序树初始化} for i:=2 to n do begin b[i] .data:=a[i]; p:=1; while true do . . begin if a[i] 一、概念 在具有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个。 Const n=叶结点数的上限； 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] of node；{最优二叉树的数组类型} Var tree：treetype； {其中tree [1‥n]为叶结点，tree [n+1‥2n-1]为中间结点，根为tree [2n-1]} 四、构造最优二叉树的算法 procedure hufm(w：wtype；var tree：treetype；var bt：integer)； function min (h：integer)：integer；{在前h个结点中选择父指针为0且权值最小的结点min} begin ml:=∞； for p:=1 to h do if (tree[p]．prt=0)and(m1>tree[p]．data) then begin i:=p；m1:=tree[p]．data； end； min:=i； . . end；{min} begin fillchar (tree，sizeof(tree)，0)；{构造初始集合F} for i:=1 to n do read(tree[i]．Data)； for k:=n+1 to m do {构造最优二叉树} 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} {计算每一个叶结点的路径长度} procedure ht(t:integer);{通过前序遍历计算每一个叶结点的路径长度} begin if t=m{若结点t为根，则路径长度为0；否则结点t的路径长度为其父结点的路径长度+1} then tree[t].lth:=0 else tree[t].lth:=tree[tree[t].prt].lth+1； if tree[t].lch<>0 then begin ht(tree[t].lch)；ht(tree[t].rch)；end；{then}{分别递归左右子树} end；{ht} 由此可见，叶结点t（1≤t≤5）的带权路径长度即为tree[t].lth*tree[t].data。 AOE网 AOE网（Activity On Edg Network） 在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网,如下图。 . . AOE网具有以下性质： （1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 （2）只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的时事件才能发生。 可以将上图假想一个工程有6项活动，网中5个顶点，分别表示5个事件，边上的权值分别表示各项活动所需要的时间，事件v1表示工程开始，事件v3表示活动3和4完成后，活动5可以开始，事件v4表示活动2完成活动4和活动6开始，v5表示活动1完成活动3开始，事件v2表示工程结束。 关键路径（临界路径）：在AOE网络中从源点到汇点（结束顶点）的最长路径。关键路径上的活动为关键活动。 .
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- huatuo0.cn 版权所有 湘ICP备2023017654号-2
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务