计算机软件及应用软件技术基础复习重点课件

一、何谓信息（information）信息是对现实世界中存在的客观实体、现象、关系进行描述的数据；信息是消息；信息是知识；信息是经过加工后并对实体的行为产生影响的数据。

数据（Data）是现实世界客观存在的实体或事物的属性值，表现为人们感官听到的事实和看到的景象；数据和信息的关系信息是有一定含义的数据；信息是经过加工（处理）后的数据；信息是对决策有价值的数据；一、何谓信息（information）信息是对现实世界中存1信息的基本属性：事实性、等级性、可压缩性、可扩散性、可传输性、共享性、增值性与再生性、转换性。信息产品的三个层次：

数据——数据采集，用于事物处理系统；

信息——数据处理，用于管理信息系统；

知识——信息融合，用于决策支持系统。

信息技术（informationtechnology，IT）主要由计算机硬件技术、计算机软件技术和通信技术三大部分组成。包含信息的产生、检测、变换、存储、传递、处理、显示、识别、提取、控制和利用等具体内容。信息的基本属性：信息技术（informationt2第三节软件（Software）随着信息化、网络化和数字化时代的到来，社会对“软件”的需求激增。如今，世界发达国家都把软件列为国家发展的关键技术领域。美国国家关键技术委员会将软件列为六大关键技术之一；欧洲共同体将“软件和信息处理”列为关键技术；我国把信息产业放在优先发展的地位，看作是中国发展高新技术、赶超世界先进水平的一次千载难逢的机遇。

硬件（hardware）：泛指计算机的物理设备与外设；

硬件系统：由运算器、控制器、存储器、输入设备、输出设备组成；其中，运算器和控制器合为中央处理器，简称CPU；只有硬件系统的计算机，为“裸机”；可以狭义地将计算机系统定义为有硬件系统和软件系统两部分组成；第三节软件（Software）随着信息化、网络化和数字3一、软件与程序

软件（software）：是指计算机程序、方法、规则的文档以及在计算机上运行它时必须数据的集合。程序与软件有联系也有区别。

程序（program）：为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合；是人们求解问题的逻辑思维活动的代码化描述；程序的要便于阅读、交流。一、软件与程序软件（software）：是指计算机程序、41、按功能划分软件分类软件系统软件应用软件操作系统网络系统语言编译器工具软件管理软件实时软件科学计算、数据处理嵌入式软件人工智能软件专用领域软件1、按功能划分软件分类软件系统软件应用软件操作系统管理软件5四、计算机软件的发展软件伴随计算机技术的发展经历了三个阶段：程序设计阶段软件设计阶段软件工程阶段四、计算机软件的发展软件伴随计算机技术的发展经历了三个阶段6第四节计算机开发系统的发展1、机器语言2、汇编语言3、高级语言4、面向对象的程序设计第四节计算机开发系统的发展1、机器语言7

算法和数据结构是程序的两个重要方面，这二者的有机结合就构成了程序。

通常用执行算法时所占用的空间大小和消耗时间的多少作为衡量算法优劣的标准。

即算法的分析主要包含时间和空间两个方面，称为时间复杂度和空间复杂度。用数学符号“O”表示复杂度的数量级例如：O(1)常量级O(n),O(n2),...,O(nk)多项式级O(log2n),O(nlog2n)对数级O(2n),O(en)指数级第一节算法分析算法和数据结构是程序的两个重要方面，这二者的有机结合8用数学符号“O”表示复杂度的数量级例如：O(1)常量级O(n),O(n2),...,O(nk)多项式级O(log2n),O(nlog2n)对数级O(2n),O(en)指数级用数学符号“O”表示复杂度的数量级91、时间复杂度算法中某一具体语句在算法的运行过程中执行的次数即为该语句的频度，记做F(n)；

时间复杂度是以算法中频度最大的语句来度量的，可记做T(n)=O(F(n))。for(k=0;k<n;k++)for(j=0;j<n;j++)for(i=0;i<n;i++)a[i]=1;时间复杂度为O(n3)

1、时间复杂度算法中某一具体语句在算法的运行过程中102、空间复杂度实现算法可能需占用的存储空间一般有：1）

指令、常数和系统变量所占用的存储空间；2）

Ｉ／Ｏ数据所占用的存储空间；3）

算法执行过程中所需的辅助空间。算法的空间复杂度分析，是指对该算法在执行过程中所需辅助空间大小的分析。

空间复杂度也用O(n)表示。常见的空间复杂度有：O(1)、O(n)、O(n2)、O(n3)上例为i、j、k与n无关，空间复杂度为O(1)。

2、空间复杂度实现算法可能需占用的存储空间一般有：算113、算法的特性与描述

(1)算法特性

算法是对特定问题的求解步骤的一种描述，是指令的有限序列。作为算法，有以下几个基本特性：1）有穷性，每条指令执行的次数与时间都是有限的，必须在若干步之后终止；2）确定性，每条指令的含义明确，不能存在二义，即在相同条件下的结果唯一；3）可行性，算法所描述的操作可以通过有限的基本操作实现；4）输入，算法应当有0个或多个输入；5）输出，算法也应当有1个或多个输出。3、算法的特性与描述(1)算法特性12算法还应具有如下性能指标：1）正确性2）可读性

3）健壮性4）高效性算法还应具有如下性能指标：13第二节程序设计基础迭代法递推法递归法穷举法分治法贪心法回溯法第二节程序设计基础迭代法14迭代法一般用于求方程的近似根的算法设计。例如：对于方程f(x)=0，通过相应的数学推导可以得到

x=g(x)，则其求根过程为：1）将方程的任意一个近似根赋给变量x0；2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；3）当x0与x1的差的绝对值还小于指定的精度（E）要求时，重复第2步；如若方程有根且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就是方程的根。 1、迭代法迭代法一般用于求方程的近似根的算法设计。1、迭代法15若一个对象部分地由自己组成或按自己定义，则可称之为递归的。在递归的定义中至少要有一条是非递归的，做为递归的终止条件，即边界条件。采用递归方法来解决问题的三个条件：1）可把一个问题转化为一个新的问题，而这个新问题的解决方法仍与原问题的解法相同；2）可通过转化过程使问题得到解决；3）必定要有一个明确的结束递归的条件，否则递归将回无止境地进行下去。3、递归法若一个对象部分地由自己组成或按自己定义，则可称之为递归的16递归算法的执行过程分递推和回归两阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在各个层中，各有自己的参数和局部变量。堆栈递归算法的执行过程分递推和回归两阶段。编17穷举法也称枚举法：顺序列举，排列列举，组合列举程序=数据结构+算法穷举法也称枚举法：顺序列举，排列列举，组合列举程序=数据18通过上述例子可以看出：描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。数据结构定义：数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的学科。通过计算机解决问题，可以通过分析数学方程式来建立数学模型，并以之为加工对象的程序设计，这种程序设计的方式为数值分析型程序设计。总通过上述例子可以看出：通过计算机解决问题，可以通过分19数据（data)：是信息的载体，是可以用计算机表示并加工的各种“符号”的集合；

数据元素（dataelement）：是数据的基本单位，是数据集合中的一个个体；亦称节点（node）或记录（record）；

数据项（dataitem）：

有独立含义的数据最小单位，也称域(field)；

数据对象（dataobject）：有相同性质的数据元素的集合；2、数据结构的基本概念和术语2、数据结构的基本概念和术语20

数据结构（datastructure)：

数据元素和数据元素关系的集合，是指同一数据对象中个数据元素间存在的关系。数据结构的定义常采用集合论的方式，表示为：

S=（D，R）其中，数据结构S是一个二元组D是一个数据元素的非空有限集合R是定义在D上的关系的非空有限集合数据结构（datastructure)：211）数据的逻辑结构：是指数据元素及其关系的数学特性，反映数据之间的逻辑关系。三种基本结构:

线性结构:

数据元素存在着线性(一对一)的关系；

树形结构:数据元素存在着层次(一对多)的关系；

图形结构:数据元素存在着任意(多对多)的关系。2）数据的存储结构：数据在计算机内部的存储方式。3）数据的操作：数据的操作即是对数据进行的处理。3、数据结构研究的主要问题1）数据的逻辑结构：是指数据元素及其关系的数学特性，反映数据221.数据的逻辑结构2.数据的存储结构3.数据的运算：检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.顺序存储B.链式存储

线性表栈队列树形结构图形结构数据元素在计算机内部的组织方式4、数据结构的三个方面反映数据元素之间的逻辑关系数据结构是一门研究数据组织、存储和运算的一般方法的学科1.数据的逻辑结构A.线性结构A.顺序存储线性表树形结构数23存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素313462）链式存储h∧元素41346元素31536元素21400元素11345存储地址存储内容指针1345元素114001346元24在数据处理的过程中，大量的数据都是以表格的形式出现的，这种表格称为线性表，它是数据元素的有限序列。线性表是一种最简单、最常见的数据结构。线性表的主要运算有插入、删除、查找和排序。线性表的常用存储结构有：向量、链表。第二节线性表（LinearList）在数据处理的过程中，大量的数据都是以表格的形式出现的25线性结构特点：对于数据元素的线性非空有限集合存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个外，集合中每个数据元素均只有一个前驱；除最后一个外，集合中每个数据元素均只有一个后继。线性表上常用的运算有：初始化、求长度、取元素、定位、插入及删除等。线性表中的数据元素是各种各样的，同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序列关系。二、线性表的特点与基本运算线性结构特点：对于数据元素的线性非空有限集合线性表中26线性表中的数据元素是各种各样的，同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序列关系。线性表中的数据元素是各种各样的，同一线性表中的元素必定具有相27线性表的存储结构采用顺序存储结构，称之为顺序表，亦为向量；采用链式存储结构，称之为链表。四、线性表的存储结构及其运算线性表的存储结构四、线性表的存储结构及其运算28a1a0aiai+1an-1…………an-1……在线性表的第i个元素之后插入一个新的元素x，先移动，后插入。01i-1in-1a1a0aiai+1an-1…………xa1a0aiai+1an-1…………ai+1x4）顺序表插入运算过程a1a0aiai+1an-1…………an-1……在线29线性表链式存储结构的描述在高级语言中，链式存储结构用“结构指针”来描述，对于有些没有结构指针的高级语言，也就没有相应的链式结构了。datalinkpstructLNode{intdata;structLNode*link;};struct*h,*p;结点中只含一个指针域的链表叫单链表(*p)表示指针变量p所指向的结点；(*p).datap->data表示p指向结点的数据域；(*p).linkp->link表示p指向结点的指针域；生成一个structLNode型新结点：

p=(structLNode*)malloc(sizeof(structLNode));

系统回收p结点：free(p)；1）线性表链式存储结构的描述线性表链式存储结构的描述datalinkpstructL302）线性链表的基本运算设p、q、s均为structLNode变量，常用的几种基本运算是：A）指针赋值s=p;q=p->link;psqB）指针移动p=p->link;ppC）在某点后插入s->link=p->link;p->link=s；^^heads2）线性链表的基本运算设p、q、s均为structLNo31E）删除某结点if(p->link!=NULL){q=p->link;p->link=q->link;free(q);}//删除p的后继结点headD）在某点前插入q=head；while（q->link!=p）q=q->link;q->link=s;s->link=p；^spheadpqE）删除某结点headD）在某点前插入^spheadpq323.顺序表和链表的比较二者各有优、缺点，可从以下三方面比较：1、线性表的长度：顺序表的存储空间是静态分配的，故其上、下界是固定的，若执行过程中表长需要发生变化（插入、删除），就要留足空间，从而产生浪费，又可能因为不足而使表产生溢出。在表长经常发生变化时，采用链表很方便。2、线性表的主要操作：顺序表连续存放，可随机存取表中任何记录，适于频繁的查找操作的表，但是进行插入、删除、移动时，就很不方便。链表进行查找时，只能顺序从首指针起，比较浪费时间，但是插入、删除运算时，只需要较小的时间就可完成，但是其每一数据元素，多一指针域，浪费存储空间。3、高级语言实现：有些高级语言不支持指针，自然只能采用顺序表。3.顺序表和链表的比较二者各有优、缺点，可从以下三方面比较331、定义：限定只能在表的一端进行插入和删除运算的特殊的线性表。其集合论的定义方法与线性表相同。特点：后进先出（LIFO）、先进后出（FILO)。设有栈表示为：s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素，其原理示意图为。栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端；n=0时，为空栈；栈的存储结构可采用顺序结构、链式结构。一、堆栈(Stack)a1a2…anbottomtop1、定义：限定只能在表的一端进行插入和删除运算的特殊的线性34（2）链栈用指针来实现的栈叫链栈。栈的容量事先不能估计时采用的存储结构。链栈的类型说明如下：structlnode{intdata；structlnodelink；}2）链栈X^topbottom（2）链栈2）链栈X^topbottom35intlpush(structlnode*s,inte){structlnode*pp=(structlnode*)malloc(sizeof(structlnode));p->data=e;p->link=s;s=p;return(1);}例1、链栈的进栈操作X^topbottoms^peintlpush(structlnode*s,in36intlpop(structlnode*s,int*pe){if(s==NULL)return(0);*pe=s->data;s=s->link;return(1);}例2、链栈的出栈操作X^topbottomsintlpop(structlnode*s,i37运算符**/*+-（）；优先级43322110.

3）表达式的求值思想：从左到右扫描表达式，若当前读入的是操作数，则进操作数（NS）栈，若读入的符号是运算符，应进行判断：若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。2.若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。3.若读入的是“；”，且运算符栈顶的符号也是“；”时，则表达式处理结束。从操作数栈弹出表达式结果。3）表达式的求值思想：从左到右扫描表达式，若当前读入的是操作38以表达式:A*B+C/D;为例说明利用栈的求值过程如下：;a)初态OSNSBA*;b)压栈OSNSBT1*;b)运算OSNST1=A*BDCT1/+;d)压栈OSNSDT2T1/+;e)运算T2=C/DOSNSDT2T3/+;e)运算T3=T2+T1OSNS以表达式:A*B+C/D;为例说明利用栈的求值过程如下：39二、队列（queue）1、定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。特点：此种结构称为先进先出（FIFO）表。常用运算：1）设置一个空队列；2）插入一个新的队尾元素，称为进队；3）删除队头元素，称为出队；4）读取队头元素；anan-1……a3a2a1队尾队首二、队列（queue）1、定义：一种特殊的线性结构，限定40将头尾连接成一个环，形成的队列就是循环队列。让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;实现方法：利用“模”运算。入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];B循环队列将头尾连接成一个环，形成的队列就是循环队列。B循环队列41intEnQueue(intQ[],intx,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if((rear+1)%MAX==front)return(0);else{rear=(rear+1)%MAX;Q[rear]=x;*pr=rear;return(1);}}计算出新的队尾a）循环队列的入队算法intEnQueue(intQ[],intx,i42intDeQueue(intQ[],int*py,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if(rear==front)return(0);else{front=(front+1)%MAX;*py=Q[front];*pf=front;return(1);}}b）循环队列的出队算法intDeQueue(intQ[],int*py43a1a11a12……..a1na2a21a22……..a2n

amam1am2……..amn….ai=(ai1,

ai2,

……..

,

ain)(1<=i<=n)数组中每一行是一个线性表数组中每一列也是一个线性表a1a11a12……..44由于数组是线性表的推广，可用线性表的一般形式定义二维数组为：B=（K，R）其中，K={Kij|1<=i<=m,1<=j<=n}R由以下两种关系组成：ROW={（Kij，Kij+1）|1<=i<=m,1<=j<=n-1}COL={（Kij，K1+ij）|1<=i<=m-1,1<=j<=n}数组特点:结构固定、元素同构；数组运算：给定一组下标，存取相应的数据元素；给定一组下标，修改数据元素的值。一、数组的定义由于数组是线性表的推广，可用线性表的一般形式定义453、特殊矩阵的压缩存储特殊矩阵：值相同元素或非零元素的分布具有一定规律。1）下三角阵a1100

……..0

a21a220

……..0……………….0an1an2an3……..annA=按行优先存放：{a11,

a21,

a22,

a31,a32,…,

an1,an2,…,

ann

}Loc(aij)=Loc(a11)+[(i*(i-1)/2+(j-1)]*S

R=1前i-1行非零元素个数∑R=i(i-1)2i-13、特殊矩阵的压缩存储特殊矩阵：值相同元素或非零元素的分布具46a11a12…a1na21a22…a2n…am1am2…amna11a12……..a1na21a22……..a2nam1am2……..amn….Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*S

1、按行优先顺序存放先排右下标，后排左下标，即以左下标为主序存放。a11a12…a1na21a22…a2n…am1a47Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*S

2、按列优先顺序存放a11a12……..a1na21a22……..a2nam1am2……..amn….先排左下标，后排右下标，即以右下标为主序存放。a11a21…am1a12a22…am2…a1na2n…amnLoc(aij)=Loc(a11)+[(j-1)483、特殊矩阵的压缩存储特殊矩阵：值相同元素或非零元素的分布具有一定规律。1）下三角阵a1100

……..0

a21a220

……..0……………….0an1an2an3……..annA=按行优先存放：{a11,

a21,

a22,

a31,a32,…,

an1,an2,…,

ann

}Loc(aij)=Loc(a11)+[(i*(i-1)/2+(j-1)]*S

R=1前i-1行非零元素个数∑R=i(i-1)2i-13、特殊矩阵的压缩存储特殊矩阵：值相同元素或非零元素的分布具49a11a12

0………...0a21a22a23

0

……..00

a21a22a23

0

………………0………..0

0

…an-1,n-2an-1.n-1an-1,n0

0

…………an,n-1ann.A=按行优先存放：{a11,

a12,

a21,

a22,

a23,a32,a34,

…an,n-1,

ann

}

Loc(aij)=Loc(a11)+2*(i-1)+(j-1)

4、三对角阵a11a120……….50三、稀疏矩阵（矩阵的压缩存储）矩阵在科学运算中十分广泛，且随计算机应用的发展，出现了大量的高介矩阵，这些矩阵中的绝大部分元素往往为零值。定义：非零元较零元少，且分布没有一定规律的矩阵。压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值。三、稀疏矩阵（矩阵的压缩存储）矩阵在科学运算中十分广51顺序存储结构三元组稀疏矩阵的转置运算30007

00-100-1-20000000000020M=30-10000-2000-1000000027

0000M=行列值245-223-113-132751311行列值715254-123-232-131311顺序存储结构三元组稀疏矩阵的转置运算300522）带辅助向量的三元组表示为了便于通过三元组法访问稀疏矩阵中的元素，通常附设两个向量POS和NUM，称为行辅助向量。它们满足：POS（1）=1POS（i）=POS（i-1）+NUM（i-1），2<=i<=m其中，POS（i）表示稀疏矩阵中第i行的第一个非零元素在三元组中的行号；NUM（i）表示稀疏矩阵中第i行的非零元素的个数。30007

00-100-1-20000000000020M=i12345POS13466NUM212012）带辅助向量的三元组表示为了便于通过三元组法访问稀533）伪地址表示法伪地址表示法是通过本元素在矩阵中（含0元素）按行优先顺序的相对位置。在上例中，M中非0元素的伪地址为：{1，5，8，11，12，24}伪地址表中每个节点含两个字段：一个是伪地址，另一个是元素值。伪地址值13578-111-112-2242该方法节省空间，但是在运算过程中要计算伪地址，浪费时间。3）伪地址表示法伪地址表示法是通过本元素在矩阵中（含541）带行指针向量的单链表设置一个行指针向量，向量中每个元素为一个指针，指向本行矩阵的第一个非0元素节点，若本行无非0元素，则指针为空。矩阵中每一个非0元素由三个数据域，列、元素值以及指向本行下一个非0结点的指针，同一行的非0元素构成一个单链表。^31^-13-11^24^-22^7530007

00-100-1-20000000000020M=1）带行指针向量的单链表设置一个行指针向量，向量中每55定义：树是由n个（n>=0）结点组成的有限集合T。其中有且仅有一个结点为根结点（root）

A,其余结点可分为m（m>=0）个互不相交的有限集合T1、T2、…、Tm，其中的每一个集合Ti本身又是一棵树，称为根结点root的子树。n=0时，树为空树。特点：树中至少有一个结点，根；树中各子树是互不相交的集合。B

E

LKT1

FDH

I

T3J

MCG

T2一、树的定义定义：树是由n个（n>=0）结点组成的有限集合T。其56

B

E

LKT1

FDH

I

T3J

MCG

T2一、树的定义ABELKT1FDHIT3JMCGT257结点（Node）：树中的元素，含数据项及若干指向其子树的指针；结点的度（Degree）：结点拥有的子树数。树中最大结点的度数称为树的度数；结点的层次（Level）：从根结点开始算起，根为第一层；叶子（Leaf）：度为零的结点，也称端结点；孩子（Child）：结点子树的根称为该结点的孩子结点；兄弟（Sibling）：同一双亲的孩子；双亲（Parent）：孩子结点的上层结点；深度（Depth)：树中结点的最大层次数。森林（Forest）：M棵互不相交的树的集合。有序树：树中结点在同层中按从左到右有序排列、不能互换的称为有序树，反之，称为无序树。1、树的常用术语BE

LKT1FDHT3MCGT2AIJ结点（Node）：树中的元素，含数据项及若干指向其子树的指针58

一棵n个结点的k叉树，有nk个指针域，有用的指针域为n-1个，空链域为nk-（n-1）个。2、树的存储1）结点异构型：根据每个结点的子树数设置相应的指针域，由于树中每个结点的度不尽相同，同一棵树中各结点的结构形式也不同。节约空间，运算不便。2）结点同构型：每个结点的指针域数目均为树的度数。运算方便，浪费空间。比较不同的k值：

2、树的存储1）结点异构型：根据每个结点的子树数设置59二、二叉树（BinaryTree）二叉树的五种基本形态：仅有根结点右子树为空左子树为空左右子树均非空定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。特点：1）每个结点至多有二棵子树(即不存在度大于2的结点)；2）二叉树的子树有左、右之分，且其次序不能任意颠倒。空二叉树二、二叉树（BinaryTree）二叉树的五种基本形态：601）二叉树的第i层上至多有2i-1（i1）个结点；2）深度为h的二叉树中至多含有2h–1个结点；3）若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1。ABCDEF1、二叉树的基本性质1）二叉树的第i层上至多有2i-1（i1）个结点；A612）完全二叉树特点：指深度为k的，有n个结点的，且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，完全一致，则为完全二叉树。1）满二叉树特点：深度为h且含有2h-1个结点的二叉树，为满二叉树。图示满二叉树，结点编号为自上而下，自左而右。4231567891011121314154231567891011124231567891011122、特殊形式的二叉树2）完全二叉树1）满二叉树42315678910111213623）平衡二叉树特点：又称AVL树，它或为一棵空树，或具如下性质：其左子树和右子树都是平衡二叉树，且左、右子树的深度之差的绝对值不超过1。左、右子树的深度之差为平衡因子，平衡二叉树的平衡因子只能为0，-1，1。3）平衡二叉树63由于二叉树常常用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。为此，给定一棵树，可以找到唯一的一棵二叉树与之对应。1）普通树转换为二叉树的方法：对每个孩子进行自左至右的排序；在兄弟之间加一条连线；对每个结点，除了左孩子外，去除其与其余孩子之间的联系；以根结点为轴心，将整个树顺时针转45度。4、一般树转换为二叉树由于二叉树常常用二叉链表表示，为了使一般树也能用二叉64ABCDEGHFI1）树转换为二叉树ABCDEGHFIABCDEGHFIABCDEGHFIABCDEGHFI1）树转换为二叉树ABCDEGHFIABC65T[16]若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。11ABCFED

●●●●●●●●●12489105637121314152h-1=24-1=151)顺序存储结构用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。0000FE000DC0BA151413121110987654321005、二叉树的存储结构（顺序和链式存储结构）T[16]若父结点在数组中i下标处，其左孩子在2*i处，右661、遍历定义遍历是指按某条搜索路线依次寻访树中每个结点，每个结点被访问且只被访问一次。对二叉树的遍历，总共有六种方式；按先左后右的原则，一般使用三种遍历：先序遍历(DLR):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(LDR):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。三、二叉树的遍历（traversing）1、遍历定义三、二叉树的遍历（traversing）67先序遍历：DLR中序遍历：LDR后序遍历：LRDDLRADLRDLR>B>>DCDLRABDCBDACDBCA2遍历算法>>voidPre(structTreeNode*T){if(T!=NULL){printf(T->data);Pre(T->lchild);Pre(T->rchild);}}/*先序遍历*/ADBCT1T2T3先序遍历：DLRDL683）由遍历序列恢复二叉树

DLR是先访问根结点，再按DLR方式遍历根结点的左子树，后按DLR方式遍历根结点的右子树。即：在DLR序列中，第一个结点一定是二叉树的根结点；

LDR是先用LDR方式遍历左子树，再访问根结点，后用LDR方式遍历右子树。因此，根结点在LDR序列中必将之分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的LDR序列。据这两个子序列，可在DLR序列中找到对应的左子序列和右子序列。在DLR序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。上述过程，就可以确定二叉树的三个结点。同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归，便可得到一棵二叉树。同理，若已知结点的后序、中序序列，就可以唯一地确定一棵二叉树。已知：DLRABCDEFGHI

LDRBCAEDGHFI3）由遍历序列恢复二叉树同理，若已知结点的后序、中序693）由遍历序列恢复二叉树

同理，若已知结点的后序、中序序列，就可以唯一地确定一棵二叉树。已知：DLRABCDEFGHI

LDRBCAEDGHFI3）由遍历序列恢复二叉树同理，若已知结点的后序、中序701、哈夫曼树（Huffman)最优树：是带权的路径长度最短的树，常用于信息检索；路径长度：从一个结点到另一结点之间经过的分支数目称为这对结点间的路径长度；树的路径长度：从树根到每一结点的路径长度之和，用PL表示；结点带权的路径长度：为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：为树中叶子结点带权路径长度之和。记作：其中：Wk为树中每个叶子结点的权；Lk为每个叶子结点到根的路径长度。WPL最小的二叉树就称作最优二叉树或哈夫曼树。=nkWPL=WKLK1四、哈夫曼树及其应用（WPL）1、哈夫曼树（Huffman)=nkWPL=WKLK171abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35例1：有4个结点，权值分别为7、5、2、4，构造有4个叶子结点的二叉树。=nkWPL=WKLK1abcd7524WPL=7*2+5*2+2*2+4*2=3672例：给定权值{7，5，2，4}，构造哈夫曼树。1）根据给的n个权值{w1,w2,········，wn}构造n棵二叉树的集合F={T1,T2,········，Tn},每棵二叉树仅有一个带权为wi的根结点；2)在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。且规定左子树根结点的权值小于右子树根结点的权值；3）将新的二叉树加入到森林F中，去除原两棵权值最小的树；4）重复2、3步骤，直至F中只剩一棵树为止。18a711cdb5624(d)abcd7524(a)2、哈夫曼树的构造过程6cd(b)ab7511bcd(c)a7例：给定权值{7，5，2，4}，构造哈夫曼树。18a711c73方法：1）用{2，4，2，3，3}作为叶子结点的权值生成一棵哈夫曼树，并将对应权值wi的叶子结点注明对应的字符；2）约定左分支表示字符“0”，右分支表示字符‘1’3）从叶子结点开始，顺着双亲反推上去，直到根结点，路径上的‘0’或‘1’连接的序列就是结点对应的字符的二进制编码的逆序。146833442200001111T;ACS各字符编码是

T；ACS

000110110111上述电文编码：11010111011101000011111000011000哈夫曼编码---利用哈夫曼树构造通讯中的电文编码（前缀码）。例：要传输的电文是{CAS；CAT；SAT；AT}，要传输的字符集是:D={C，A，S，T，；}，字符出现的频率分别是W={2，4，2，3，3}4、哈夫曼编码方法：146833442200001111T;ACS各字符编74146833442200001111T;ACS各字符编码是

T；ACS

000110110111上述电文编码：11010111011101000011111000011000

4、哈夫曼编码146833442200001111T;ACS各字符编码是75图(Graph)：图G是由两个集合V(G)和E(G)组成的,记为G=(V,E），其中：V(G)是顶点的非空有限集；E(G)是边的有限集合，边是顶点的无序对或有序对；有向图：有向图G是由两个集合V(G)和E(G)组成的，其中：V(G)是顶点的非空有限集，E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头，（v,w)!=(w,v)。无向图：无向图G是由两个集合V(G)和E(G)组成的，其中：V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 。一、图的基本概念图(Graph)：图G是由两个集合V(G)和E(G)组成的,76有向图(Digraph)G1

G=(V,E)顶点集合V={V1，V2，V3，V4}弧的集合E={<V1，V3>,<V3，V4>,<V2，V4>,<V4，V1>}V1V3V2V4G1无向图(Undigraph)G2V1V3V2V4G2顶点集合V={V1，V2，V3，V4}边的集合E={(V1,V3),(V1,V2),(V1,V4),(V2,V4)}顶点(V1,V3)与(V1,V3)表示同一条边有向图(Digraph)G1G=77权：与图的边或弧相关的数叫权(Weight），可以表示从一个顶点到另一个顶点的距离或耗费；带权的图叫网；子图：图G(V,E)和图G’(V’,E’),若V’V，E’E，则称G’为G的子图；顶点的度：无向图中，顶点的度为与每个顶点相连的边的数目；有向图中，顶点的度分成入度与出度；入度：以该顶点为头的弧的数目；出度：以该顶点为尾的弧的数目；二、图的相关术语V1V3V2V4V1V3V2V4路径：路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)；路径上的边或弧的数目，称为该路径的长度。网络的路径长度定义为路径上权值之和；简单路径：除第一个和最后一个顶点外，序列中其余顶点各不相同的的路径为简单路径；第一个与最后一个顶点相同的简单路径为回路；连通图：在无向图中，若从Vi到Vj存在路径，则称Vi到Vj是连通的；若在顶点集合V中每一对不同的顶点Vi到Vj都连同，则称G为连通图；强连通图：对于有向图，若从顶点Vi到Vj和从Vj到Vi之间都有路径，则称这两个顶点是强连通的；对于有向图中任何一对顶点都是强连通，则此图为强连通图。权：与图的边或弧相关的数叫权(Weight），可以表示从一个78V1V3V2V4

V1V2V3V4

V10111

V21001

V31000

V41100特点：由上述可知，无向图或网络的邻接矩阵是对称的。并且，该法比较简单，用一个二维数组就可存储。缺点：浪费空间，可用处理“稀疏”矩阵的方式去处理。V1V3V2V4V1V279邻接表是图的一种链式存储结构。在邻接表中，对图中的每个结点建立一个单链表。第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）.在边少的情况下，用邻接表比邻接矩阵节省存储空间。V1V3V2V4V1V3V2V42、邻接表4321∧3∧4∧4∧1432121∧113∧4∧4∧2邻接表是图的一种链式存储结构。在邻接表中，对图中的每个结点建80V1V2V4V5V3V7V6V8V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8V1V2V4V8V3V6V7V5三、图的遍历从图中某一顶点出发，访遍图中其余顶点,且使每个顶点仅被访问且仅被访问一次。1、深度优先遍历(DFS)从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。V1V2V4V5V3V7V6V8V1V2V4V8V812、广度优先遍历(BFS)从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。V1V2V3V4V5V6V7V8V1V2V3V4V6V7V8V5V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V82、广度优先遍历(BFS)从图的某一顶点V0出发，访82迪克思特拉算法（Dijkstra）1）设A[1..n,1..n]为有向图的带权邻接矩阵，A[i,j]表示弧(Vi,Vj)上的权值，若(Vi,Vj)不存在，则A[i,j]为无穷大；S为已找到从源点V0出发的最短路径的终点集合，初始状态为{V0}；DIST[1..n]为个终点当前找到的最短路径长度，初始值为DIST[i]=A[V0,i]；算法描述：2）选择u，使DIST[u]=min{DIST[w]|w!∈S,w∈V},S=S∪{u},其中，V为有向图的顶点集合；3）对于所有不在S中终点w，若DIST[u]+A[u,w]<DIST[w],则修改DIST[w]为DIST[w]=DIST[u]+A[u,w]；4）重复操作2）、3）共n-1次，由此可求得从V0到各终点的最短路径。迪克思特拉算法（Dijkstra）1）设A[1..83

弗洛伊德算法思想：逐步试着在原直接路径中考虑其它顶点作为中间点，如增加中间点后得到的路径较原路径长度减小，则以此新路径长度代替原值而修改矩阵元素；若增加中间点后的路径比原路径更长，就维持原相应的矩阵元素值不变。1）初始状态

弗洛伊德算法思想：逐步试着在原直接路径中考虑其它顶点84第一节查找

查找，也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素。不同的数据结构采用不同的查找方法，查找的效率直接影响数据处理的效率；关键字——是数据元素中某个数据项的值，它可以标识一个数据元素.查找方法评价：查找速度、占用存储空间多少、算法本身复杂程度、平均查找长度ASL(AverageSearchLength)。

为确定记录在表中的位置，需和给定值进行比较的关键字的个数的数学期望值叫查找算法的平均查找长度。查找的结果：查找成功，则返回找到满足条件的结点；查找失败，则返回找不到满足条件的结点的信息。Ci为找到表中第i个元素所需比较次数其中：pi为查找表中第i个元素的概率，且对含有n个记录的表：ASL=∑PiCini=1∑Pi=1ni=1第一节查找查找，也叫检索，是根据给定的某个值，在表85（b）K=80(i=4)804080306010202501234567intSearch_Seq(structSTableST[],intn,intKey){inti=n;ST[0].key=Key;while(ST[i].key!=Key)i--;

/*从表尾往前查*/

return(i);}监视哨使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。找到：返回元素在线性表中的存储位置；未找到：返回0。(i=0)012345679040803060102025（b）K=90

顺序查找的算法：01234567（a）初态40803060102025（b）K=80(i=4)80408030601020286基本思想：对有序文件，进行查找，先找“中间记录”，进行比较，根据不同情况，逐步缩小范围，直到找到或确认找不到该记录为止。适用条件：必须在具有顺序存储结构的有序表中进行。算法实现：设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值；初始时，令low=1，high=n，mid=(low+high)/2；

让k与mid指向的记录比较，若k==r[mid].key，找成功，若k<r[mid].key，则high=mid-1；若k>r[mid].key，则low=mid+1；重复上述操作，直至low>high时，查找失败。二、对分查找（折半查找、二分法查找）基本思想：对有序文件，进行查找，先找“中间记录”，进行比87查找23和79的过程如下图：mid=[(low+high)/2](08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)highlow=mid+1mid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid查找23和79的过程如下图：mid=[(low+high88查找方法比较顺序查找折半查找分块查找ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找ASL最大最小两者之间表89四、二叉排序树查找（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1．定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；四、二叉排序树查找（1）若它的左子树不空，则左子树上所有结点903.二叉排序树的生成对于任意的一组数据元素序列{R1，R2，…，Rn}，生成二叉排序树的过程如下：1）令R1为二叉排序树的根结点；2）若R2<R1，令R2为R1的左子树的根结点；否则，R2为R1的右子树的根结点；3）R2，…，Rn结点插入方法同上。3.二叉排序树的生成对于任意的一组数据元素序列{911010181018310183810183123101881221018381227101838122718序列{10，18，3，8，12，2，7，1}构成一棵二叉排序树的过程101018101831018381018312310188924.删除二叉排序树上的结点上述查找过程可见，在查找过程中，生成了一条查找路径：从根结点出发，沿4.删除二叉排序树上的结点上述查找过程可见，在查找过程中，生93动态查找，就是在查找失败时进行“插入”操作，将要查找的关键字插入到结构中；若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。动态查找，就是在查找失败时进行“插入”操作，将要查找的关键字94二叉排序树在生成（插入）过程中，若其形态始终保持“匀称”，亦接近平衡二叉树，则平均查找长度就小；反之，平均查找长度就长。二叉排序树的平均查找长度介于对分查找与线性查找之间。20,8,6,17,54,32,3,80208546173280354,32,20,8,17,6,80,32085461732803ASL=(1+2*2+3*4+4)/8=2.6ASL=(1+2*2+3+4+5*2+6)/8=3.5二叉排序树在生成（插入）过程中，若其形态始终保持“匀95哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系，是可以根据关键字的值而直接计算出元素所在位置的函数,可表示H（KEY）。哈希表：哈希表是一种存储结构，是能用散列技术进行查找的表，也叫散列存储。通过哈希函数和解决冲突的办法把键值存放在哈希表中。采用哈希技术主要目标是提高查找效率，要求缩短查表和填表的时间.哈希查找：又叫散列查找，利用哈希函数进行查找的过程。冲突：两个不同的关键字K1和K2计算出相同的存储位置的现象称为冲突，K1和K2互为同义词。1、哈希函数/哈希表的基本概念哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关961）直接定址法：

H(K)=K或H(K)=A*K+B；(其中A、B为常数)；

取关键字或关键字的某个线性函数值为散列地址。

例：某公司一险种投保费交纳表（20年），将年份作关键字，哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3项即可。地址010203……20年份123…….20保费…….…….…….…………2、哈希函数的构造方法1）直接定址法：地址010203……20年份972）数字分析法:

该法适用于较大的静态数据，在已知所有关键字键值的情况下，分析每一位的数字分布是否均匀，删除不均匀分配的数字位，根据存储空间的大小来确定所取地址的位数。542422241542813678542228171542389671542541577542886376542193552422836281396515853135存储空间从0-10002）数字分析法:542422241422存储空间从0-1983）平方取中法:若一组关键字的值在每一位上对某些数字的重复频度都很高，就不宜采用数字分析法，取关键字平方后的中间几位为哈希函数。

H(Key)=Key2=anan-1…a2a1

0100,1100,1200,1160,2060,2061,2163,2261,2262设存储空间0-1000平方后，取2、3、4位构成哈希地址如下：010,210,440,345,243,247,678,112,1163）平方取中法:0100,1100,1200,1160,20994）除留余数法：取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数。即H（K）=KMODp（pm）p一般选取小于等于表长的质数。

H（K）=KMODp+C（pm）C的作用可以调节最终的地址范围，为小于表长的某一整型常数。5）折叠法：将关键字的值分为几段，尔后叠加求和。A、移位折叠，将各段左对齐后相加；B、边界折叠，将奇数段、偶数段倒排后相加。4）除留余数法：H（K）=KMODp+100排序中的关键字可是主关键字也可是次关键字，若是主关键字则排序结果唯一；