elemtype

.

根本概念

➢数据

数据是信息的载体,在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号

集合.

➢数据元素

数据元素也称为结点,是表示数据的根本单位,在计算机程序中通常作为一个整体进展考虑和处理.

➢数据项

数据项是构成数据元素的不可分割的最小单位.

➢数据对象

数据对象是具有一样性质的数据元素的集合,是数据的子集.

注意：在不产生混淆的情况下,将数据对象简称为数据.

➢数据结构

数据结构是指相互之间存在一定关系的数据元素的集合,即数据结构是一个二元组DataStructure=

R>,其中D是数据元素的集合,R是D上关系的集合.按照视点的不同,数据结构分为逻辑结构和存储结构.

➢数据的逻辑结构

数据的逻辑结构是指数据元素之间逻辑关系的整体.根据数据元素之间逻辑关系的不同,数据结构分为

四类：

⑴集合：数据元素之间就是"属于同一个集合〞,除此之外,没有任何关系；

⑵线性结构：数据元素之间存在着一对一的线性关系；

⑶树结构：数据元素之间存在着一对多的层次关系；

⑷图结构：数据元素之间存在着多对多的任意关系.

注意：数据结构分为两类：线性结构和非线性结构.

➢数据的存储结构

数据的存储结构又称为物理结构,是数据与其逻辑结构在计算机中的表示.通常有两种存储结构：顺序

存储结构和存储结构.

顺序存储结构的根本思想是：用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系是由

元素的存储位置来表示的.

存储结构的根本思想是：用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系是用指针来表

示的.

注意：存储结构除了存储数据元素之外,必须存储数据元素之间的逻辑关系.

➢抽象数据类型

抽象数据类型是一个数据结构以与定义在该结构上的一组操作的总称.抽象数据类型提供了使用和实

现两个不同的视图,实现了封装和信息隐藏.

➢算法的定义

通俗地讲,算法是解决问题的方法,严格地说,算法是对特定问题求解步骤的一种描述,是指令的有限序

列.

➢算法的特性

⑴输入：一个算法有零个或多个输入〔即算法可以没有输入〕,输入通常取自于某个特定的对象集合.

⑵输出：一个算法有一个或多个输出〔即算法必须要有输出〕,通常输出与输入之间有着某种特定的

关系.

⑶有穷性：一个算法必须总是〔对任何合法的输入〕在执行有穷步之后完毕,且每一步都在有穷时间内

完成.

⑷确定性：算法中的每一条指令必须有确切的含义,不存在二义性.并且,在任何条件下,对于一样的输

.

入只能得到一样的输出.

⑸可行性：算法描述的操作可以通过已经实现的根本操作执行有限次来实现.

➢线性表的定义

线性表简称表,是零个或多个具有一样类型的数据元素的有限序列.数据元素的个数称为线性表的长度,

长度等于零时称为空表.

➢线性表的逻辑关系

在一个非空表L＝中,任意一对相邻的数据元素ai-1和ai之间〔1＜i≤n〕存在序偶关系

〔ai-1,ai〕,且ai-1称为ai的前驱,ai称为ai-1的后继.在这个序列中,a1无前驱,an无后继,其它每个元素有且仅

有一个前驱和一个后继.

➢顺序表的存储结构定义

用MaxSize表示数组的长度,顺序表的存储结构定义如下：

#defineMaxSize100

typedefstruct

{

ElemTypedata[MaxSize];//ElemType表示不确定的数据类型

intlength;//length表示线性表的长度

}SeqList;

➢顺序表是随机存取结构

设顺序表的每个元素占用c个存储单元,如此第i个元素的存储地址为：

LOC=LOC＋×c

➢顺序表的优缺点

顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系,这使得顺

序表具有如下优点：

⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间；

⑵可以快速地存取表中任一位置的元素〔即随机存取〕.

同时,顺序表也具有如下缺点：

⑴插入和删除操作需移动大量元素.在顺序表上做插入和删除操作,等概率情况下,平均要移动表中一

半的元素.

⑵表的容量难以确定.由于数组的长度必须事先确定,因此,当线性表的长度变化较大时,难以确定适

宜的存储规模.

⑶造成存储空间的"碎片〞.数组要求占用连续的存储空间,即使存储单元数超过所需的数目,如果不

连续也不能使用,造成存储空间的"碎片〞现象.

➢单链表的存储结构定义

单链表的存储结构定义如下：

StructNode

{ElemTypedata;//ElemType表示不确定的数据类型

structNode*next;

}*first;//first为单链表的头指针

➢双链表的存储结构定义

双链表存储结构定义如下：

structDulNode

{

ElemTypedata;//ElemType表示不确定的数据类型

structDulNode*prior,*next;//prior为前驱指针域,next为后继指针域

.

}*first;//first表示双链表的头指针

➢栈的定义

栈是限定仅在表尾进展插入和删除操作的线性表.允许插入和删除的一端称为栈顶,另一端称为栈底,

不含任何数据元素的栈称为空栈.

➢栈的操作特性

栈的操作具有后进先出的特性.

➢队列的定义

队列是只允许在一端进展插入操作,而另一端进展删除操作的线性表.允许插入的一端称为队尾,允许

删除的一端称为队头.

➢队列的操作特性

队列的操作具有先进先出的特性.

➢循环队列中解决队空队满的判断条件

方法一：附设一个存储队列中元素个数的变量num,当num=0时队空,当num=QueueSize时为队满；

方法二：修改队满条件,浪费一个元素空间,队满时数组中只有一个空闲单元；即队空的条件是

front=rear,队满的条件是%QueueSize=front,队列长度为%QueueSize.

方法三：设置标志flag,当front=rear且flag=0时为队空,当front=rear且flag=1时为队满.

➢串的定义

串是零个或多个字符组成的有限序列.

➢空格串和空串的定义

只包含空格的串称为空格串.串中所包含的字符个数称为串的长度,长度为0的串称空串,记作"".

➢串的比拟

串的比拟是通过组成串的字符之间的比拟来进展的.

给定两个串：

X="x1x2…xn"

Y="y1y2…ym"

如此当n=m且x1=y1,…,xn=ym时,称X=Y；

当如下条件之一成立时,称X＜Y：

⑴n＜m,且xi=yi〔i=1,2,…,n〕；

⑵存在某个k≤min,使得xi=yi〔i=1,2,…,k-1〕,xk＜yk.

➢改良的模式匹配算法中next[j]的求法

用next[j]表示tj对应的k值〔1≤j≤m〕,其定义如下：

➢数组的根本操作

数组是一个具有固定格式和数量的数据集合,在数组上一般不能做插入、删除元素的操作.因此,在数组

中通常只有两种操作：

⑴读取：给定一组下标,读取相应的数组元素；

⑵修改：给定一组下标,存储或修改相应的数组元素.

➢二维数组的寻址

按行优先,设二维数组的行下标与列下标的X围分别为［l1,h1］与［l2,h2］,如此任一元素aij的存储地

址可由下式确定：

LOC<

a

ij>＝LOC

1

l

2

>＋<×＋>×c

0j=1

max{k|1≤k＜j且＂t

1

t

2

…t

k-1

＂=＂t

j-k+1

t

j-k+2

…t

j-1

＂}

1其它情况

next[j]=

.

➢特殊矩阵的定义

特殊矩阵是指矩阵中有很多值一样的元素并且它们的分布有一定的规律.

➢矩阵压缩存储的根本思想

压缩存储的根本思想是：⑴为多个值一样的元素只分配一个存储空间；⑵对零元素不分配存储空间.

➢对称矩阵的压缩存储中：下三角元素aij〔i≥j〕在一个数组SA中的下标为：k=i×/2+j-1.

上三角中的元素aij〔i＜j〕,如此访问和它对应的下三角中的元素aji即可,即：k=j×/2+i-1.

➢三角矩阵的压缩存储中：下三角矩阵中任一元素aij在一个数组SA中的下标k与i、j的对应关系为：

上三角矩阵元素aij在SA中的下标为：k=×<2n-i+2>/2+.

➢稀疏矩阵的压缩存储方式

组顺序表和十字链表

➢组的定义

structelement

{

introw,col;

ElemTypeitem

};

➢广义表的定义

广义表是n〔n≥0〕个数据元素的有限序列.

➢表头

当广义表LS非空时,称第一个元素为LS的表头；

➢表尾

称广义表LS中除去表头后其余元素组成的广义表为LS的.

➢长度

广义表LS中的直接元素的个数称为LS的长度；

➢深度

广义表LS中括号的最大嵌套层数称为LS的深度.

➢树的定义

树是n〔n≥0〕个结点的有限集合.当n＝0时,称为空树；任意一棵非空树满足以下条件：

⑴有且仅有一个特定的称为根的结点；

⑵当n＞1时,除根结点之外的其余结点被分成m〔m>0〕个互不相交的有限集合T1,T2,…,Tm,其中每个

集合又是一棵树,并称为这个根结点的子树.

➢结点的度、树的度

某结点所拥有的子树的个数称为该结点的度；树中各结点度的最大值称为该树的度.

➢叶子结点、分支结点

度为0的结点称为叶子结点,也称为终端结点；度不为0的结点称为分支结点,也称为非终端结点.

➢孩子结点、双亲结点、兄弟结点

某结点的子树的根结点称为该结点的孩子结点；反之,该结点称为其孩子结点的双亲

➢路径、路径长度

如果树的结点序列n1,n2,…,nk满足如下关系：结点ni是结点ni+1的双亲〔1≤i＜k〕,如此把n1,n2,…,

k=

i×/2+j-1当i≥j

n×/2当i＜j

.

nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度.

➢祖先、子孙

如果从结点x到结点y有一条路径,那么x就称为y的祖先,而y称为x的子孙.

注意：某结点子树中的任一结点都是该结点的子孙.

➢结点的层数、树的深度〔高度〕

规定根结点的层数为1,对其余任何结点,假如某结点在第k层,如此其孩子结点在第k+1层；树中所有结

点的最大层数称为树的深度,也称为树的高度.

➢二叉树的定义

二叉树是n〔n≥0〕个结点的有限集合,该集合或者为空集〔称为空二叉树〕,或者由一个根结点和两棵

互不相交的、分别称为根结点的左子树和右子树的二叉树组成.

➢二叉树的特点

二叉树的特点是：⑴每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点；⑵子树的次序

不能任意颠倒,某结点即使只有一棵子树也要区分是左子树还是右子树.

注意：二叉树和树是两种树结构.

➢二叉树的根本形态

二叉树具有五种根本形态：⑴空二叉树；⑵只有一个根结点；⑶根结点只有左子树；⑷根结点只

有右子树；⑸根结点既有左子树又有右子树.

➢斜树

所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和右

斜树统称为斜树.

斜树的特点：①每一层只有一个结点,即只有度为1和度为0的结点并且只有一个叶子结点；②斜树

的结点个数与其深度一样.

➢满二叉树

在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉

树称为满二叉树.

满二叉树的特点：①叶子结点都在最下一层；②只有度为0和度为2的结点.

➢完全二叉树

对一棵具有n个结点的二叉树按层序编号,如果编号为i〔1≤i≤n〕的结点与同样深度的满二叉树中编号

为i的结点在二叉树中的位置完全一样,如此这棵二叉树称为完全二叉树.

完全二叉树的特点是：①叶子结点只能出现在最下两层,且最下层的叶子结点都集中在左面连续的位

置；②如果有度为1的结点,只可能有一个,且该结点只有左孩子.

➢二叉树的根本性质

性质1二叉树的第i层上最多有2i-1个结点〔i≥1〕.

性质2在一棵深度为k的二叉树中,最多有2k-1个结点,最少有k个结点.

性质3在一棵二叉树中,如果叶子结点的个数为n0,度为2的结点个数为n2,如此

n0＝n2＋1.

性质4具有n个结点的完全二叉树的深度为1log

2

n

.

性质5对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号,如此对于任意的编号为i〔1

≤i≤n〕的结点〔简称为结点i〕,有：

⑴如果i＞1,如此结点i的双亲的编号为2/i；否如此结点i是根结点,无双亲；

⑵如果2i≤n,如此结点i的左孩子的编号为2i；否如此结点i无左孩子；

.

⑶如果2i＋1≤n,如此结点i的右孩子的编号为2i＋1；否如此结点i无右孩子.

➢二叉树的存储

包括：二叉树的顺序存储和二叉树的链式存储.

二叉链表的存储结构定义如下：

structBiNode

{

ElemTypedata;

BiNode*lchild,*rchild;

}*root;//root表示二叉链表的头指针

structTriNode

{

ElemTypedata;

TriNode*lchild,*rchild,*parent;//parent指向该结点的双亲

}*root;//三叉链表的头指针

➢遍历的含义

所谓遍历就是无重复无遗漏地访问.二叉树的遍历是指从根结点出发,按照某种次序访问二叉树中的所

有结点,使得每个结点被访问一次且仅被访问一次.

➢二叉树的遍历次序定义

前序遍历〔或称前根遍历、先序遍历〕

假如二叉树为空,如此空操作返回；否如此

⑴访问根结点；

⑵前序遍历根结点的左子树；

⑶前序遍历根结点的右子树.

中序遍历〔或称中根遍历〕

假如二叉树为空,如此空操作返回；否如此

⑴中序遍历根结点的左子树；

⑵访问根结点；

⑶中序遍历根结点的右子树.

后序遍历〔或称后根遍历〕

假如二叉树为空,如此空操作返回；否如此

⑴后序遍历根结点的左子树；

⑵后序遍历根结点的右子树；

⑶访问根结点.

层序遍历

二叉树的层序遍历是从二叉树的第一层〔根结点〕开始,从上至下逐层遍历,在同一层中,如此按从左到

右的顺序对结点逐个访问.

➢线索二叉树的定义

在一个具有n个结点的二叉链表中,利用n+1个空指针域存放指向该结点在某种遍历序列中的前驱和后

继结点的指针,指向前驱和后继结点的指针称为线索,加上线索的二叉树称为线索二叉树,相应地,加上线索

的二叉链表称为线索链表.

➢线索二叉树的存储结构定义

.

线索链表中的结点定义如下：

enumflag{Child,Thread};//枚举类型,枚举常量Child=0,Thread=1

structThrNode

{

ElemTypedata;//ElemType表示不确定的数据类型

ThrNode*lchild,*rchild;

flagltag,rtag;

}*root;//root表示线索链表的头指针

➢树的存储结构

包括：双亲表示法、孩子表示法、孩子兄弟表示法.

双亲表示法的存储结构定义如下：

#defineMaxSize100;//树中最大结点个数

structPNode//数组元素的类型

{

ElemTypedata;//树中结点的数据信息,

intparent;//该结点的双亲在数组中的下标

};

PNodeTree[MaxSize];

孩子表示法的存储结构定义如下：

structCTNode//孩子结点

{

intchild;

CTNode*next;

};

structCBNode//表头结点

{

ElemTypedata;

CTNode*firstchild;//指向孩子链表的头指针

};

孩子兄弟表示法又称为二叉链表表示法,存储结构定义如下：

structTNode

{

ElemTypedata;//ElemType表示不确定的数据类型

TNode*firstchild;//firstchild指向该结点的第一个孩子

TNode*rightsib;//rightsib指向该结点的右兄弟

};

➢树转换为二叉树

树转换为二叉树的方法是：

⑴加线——树中所有相邻兄弟结点之间加一条连线；

⑵去线——对树中的每个结点,只保存它与第一个孩子结点之间的连线,删去它与其它孩子结点之间的

连线；

⑶层次调整——以根结点为轴心,将树顺时针转动一定的角度,使之层次清楚.

➢森林转换为二叉树

森林转换为二叉树的方法如下：

⑴将森林中的每棵树转换成二叉树；

⑵从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子,当所有二

叉树连起来后,所得到的二叉树就是由森林转换的二叉树.

.

➢二叉树转换为树或森林

树和森林转换为二叉树的过程是可逆的,将一棵二叉树复原为树或森林的方法如下：

⑴加线——假如某结点x是其双亲y的左孩子,如此把结点x的右孩子、右孩子的右孩子、……,都与

结点y用线连起来；

⑵去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；

⑶层次调整——整理由⑴、⑵两步所得到的树或森林,使之层次清楚.

树的遍历序列与二叉树的遍历序列之间的对应关系

根据树与二叉树的转换关系以与树和二叉树遍历的操作定义可知,树的遍历序列与由树转化成的二叉

树的遍历序列之间具有如下对应关系：树的前序遍历序列等于二叉树的前序遍历序列,树的后序遍历序列等

于二叉树的中序遍历序列.

➢哈夫曼树中叶子结点的权值

叶子结点的权值是指对叶子结点赋予的一个有意义的数值量.

➢二叉树的带权路径长度

设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积

之和称做二叉树的带权路径长度,记为：

WPL=



n

k

kk

lw

1

其中,wk为第k个叶子结点的权值；lk为从根结点到第k个叶子结点的路径长度.

➢哈夫曼树定义

给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为

哈夫曼树,也称为最优二叉树.

➢哈夫曼算法的根本思想

哈夫曼算法的根本思想是：

⑴初始化：由给定的n个权值{w1,w2,…,wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集

合F＝{T1,T2,…,Tn}；

⑵选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树,

这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；

⑶删除与参加：在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树参加到F中；

⑷重复⑵、⑶两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树.

➢图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为：

G=

其中,G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合.

➢无向图与有向图

假如顶点vi和vj之间的边没有方向,如此称这条边为无向边,用无序偶对来表示；假如从顶点vi

到vj的边有方向,如此称这条边为有向边〔也称为弧〕,用有序偶对来表示,vi称为弧尾,vj称为弧头.

如果图的任意两个顶点之间的边都是无向边,如此称该图为无向图,否如此称该图为有向图.

➢简单图

假如不存在顶点到其自身的边,且同一条边不重复出现,如此称这样的图为简单图.

➢邻接、依附

在无向图中,对于任意两个顶点vi和vj,假如存在边,如此称顶点vi和vj互为邻接点,同时称边

依附于顶点vi和vj.

.

在有向图中,对于任意两个顶点vi和vj,假如存在弧,如此称顶点vj是vi的邻接点,同时称弧

依附于顶点vi和vj.

➢无向完全图、有向完全图

在无向图中,如果任意两个顶点之间都存在边,如此称该图为无向完全图.含有n个顶点的无向完全图有

n×/2条边.

在有向图中,如果任意两顶点之间都存在方向互为相反的两条弧,如此称该图为有向完全图.含有n个顶

点的有向完全图有n×条边.

➢稠密图、稀疏图

称边数很少的图为稀疏图,反之,称为稠密图.

➢顶点的度、入度、出度

在无向图中,顶点v的度是指依附于该顶点的边的个数,记为TD.在具有n个顶点e条边的无向图中,

有下式成立：

在有向图中,顶点v的入度是指以该顶点为弧头的弧的个数,记为ID；顶点v的出度是指以该顶点为

弧尾的弧的个数,记为OD.在具有n个顶点e条边的有向图中,有下式成立：

➢连通图、连通分量

在无向图中,假如任意顶点vi和vj之间有路径,如此称该图是连通图.非连通图的极某某通子图称

为连通分量.

➢强连通图、强连通分量

在有向图中,对任意顶点vi和vj,假如从顶点vi到vj和从顶点vj到vi均有路径,如此称该有向图

是强连通图.非强连通图的极大强连通子图称为强连通分量.

➢邻接矩阵的存储结构定义

假设图G＝有n个顶点,如此邻接矩阵是一个n×n的方阵,定义为：

邻接矩阵的存储结构定义如下：

#defineMaxSize10

typedefstruct

{

ElemTypevertex[MaxSize];//存放图中顶点的信息,ElemType表示不确定的数据类型

intarc[MaxSize][MaxSize];//存放图中边的信息

intvertexNum,arum;//图的顶点数和边数

}MGraph;

➢邻接表的存储结构定义

邻接表是一种顺序存储与存储相结合的存储方法,具体方法为：将顶点vi的所有邻接点链成一个单链表,

称为顶点vi的边表〔对于有向图如此称为出边表〕,边表的头指针和顶点的数据信息采用顺序存储〔称为顶

点表〕.所以,在邻接表中存在两种结点：顶点表结点和边表结点.

其中,vertex：数据域,存放顶点信息；

firstedge：指针域,边表的头指针；

adjvex：邻接点域,存放边该顶点的邻接点在顶点表中的下标；

next：指针域,指向边表中的下一个结点.

邻接表的存储结构定义如下：

structArode//定义边表结点

{

intadjvex;//邻接点域

1假如

i

,v

j

>∈E或

i

,v

j

>∈E

0否如此

arc[i][j]＝

vertexfirstedgeadjvexnext

顶点表结点边表结点

邻接表表示的结点结构

.

Arode*next;

};

structVertexNode//定义顶点表结点

{

ElemTypevertex;//ElemType表示不确定的数据类型

Arode*firstedge;

};

#defineMaxSize10

typedefstruct

{

VertexNodeadjlist[MaxSize];//顶点表

intvertexNum,arum;//图的顶点数和边数

}ALGraph;

➢图的遍历次序定义

深度优先遍历

从图中某顶点v出发进展深度优先遍历的根本思想是：

①访问顶点v；

②从v的未被访问的邻接点中选取一个顶点w,从w出发进展深度优先遍历；

③重复上述两步,直至图中所有和v有路径相通的顶点都被访问到.

广度优先遍历

从图中某顶点v出发进展广度优先遍历的根本思想是：

①访问顶点v；

②依次访问v的各个未被访问的邻接点v1,v2,……,vk；

③分别从v1,v2,…,vk出发依次访问它们未被访问的邻接点,直至图中所有与顶点v有路径相通的顶点

都被访问到.

➢最小生成树的定义

设G=是一个无向连通网,生成树上各边的权值之和称为该生成树的代价,在G的所有生成树中,代

价最小的生成树称为最小生成树.

➢普里姆〔Prim〕算法的根本思想

设G=是一个无向连通网,令T=是G的最小生成树.T的初始状态为U={v0}〔v0∈V〕,TE={},

然后重复执行下述操作：在所有u∈U,v∈V-U的边中找一条代价最小的边并入边集TE,同时v并入顶

点集U,直至U=V为止.

➢克鲁斯卡尔〔Kruskal〕算法的根本思想

设无向连通网为G＝,令G的最小生成树为T=,其初态为U＝V,TE={},然后按照边的权值由

小到大的顺序,依次考察边集E中的各条边.假如被考察边的两个顶点属于T的两个不同的连通分量,如此将

此边参加到TE中,同时把两个连通分量连接为一个连通分量；假如被考察边的两个顶点属于同一个连通分

量,如此舍去此边,以免造成回路.如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生

成树.

➢迪杰斯特拉〔Dijkstra〕算法的根本思想

设置集合S存放已经找到最短路径的顶点,S的初始状态只包含源点v,对vi∈V-S,假设从源点v到vi

的有向边为最短路径.以后每求得一条最短路径v,…,vk,就将vk参加集合S中,并将路径v,…,vk,vi

与原来的假设相比拟,取路径长度较小者为当前最短路径.重复上述过程,直到集合V中全部顶点参加到集合

S中.

➢Floyd算法的根本思想

.

假设从vi到vj的弧〔假如从vi到vj的弧不存在,如此将其弧的权值看成∞〕是最短路径,然后进展n次

试探.假如vi,…,vk和vk,…,vj分别是从vi到vk和从vk到vj中间顶点的序号不大于k-1的最短路径,如此

将vi,…,vk,…,vj和已经得到的从vi到vj中间顶点的序号不大于k-1的最短路径相比拟,取长度较短者为

从vi到vj中间顶点的序号不大于k的最短路径.

➢AOV网的定义

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点

表示活动的网,简称AOV网.

➢拓扑序列的定义

设G=是一个具有n个顶点的有向图,V中的顶点序列v1,v2,…,vn称为一个拓扑序列,当且仅当

满足如下条件：假如从顶点vi到vj有一条路径,如此在顶点序列中顶点vi必在顶点vj之前.

➢拓扑排序的根本思想

对AOV网进展拓扑排序的根本思想是：

⑴从AOV网中选择一个没有前驱的顶点并且输出它；

⑵从AOV网中删去该顶点,并且删去所有以该顶点为尾的弧；

⑶重复上述两步,直到全部顶点都被输出,或AOV网中不存在没有前驱的顶点.

➢查找算法的时间性能

查找算法用关键码的比拟次数来度量查找算法的时间性能.对于查找成功的情况,将关键码比拟次数的

数学期望值定义为平均查找长度,即：

ASL





n

i

ii

cp

1

其中,n表示问题规模,即查找集合中的记录个数；pi表示查找第i个记录的概率；ci表示查找第i个记录所

需的关键码的比拟次数.

➢顺序查找算法的时间复杂度

对于具有n个记录的顺序表,查找第i个记录时,需进展n-i+1次关键码的比拟.设每个记录的查找概率

相等,查找成功时,顺序查找的平均查找长度为：O；查找不成功时,关键码的比拟次数是n+1次,如此查

找失败的平均查找长度为O.

➢顺序查找的适用情况

顺序查找对表中记录的存储没有任何要求,顺序存储和存储均可应用；对表中记录的有序性也没有要求,

无论记录是否按关键码有序均可应用.

➢折半查找的适用情况

折半查找〔也称对半查找、对分查找、二分查找〕要求线性表中的记录必须按关键码有序,并且必须采

用顺序存储.

➢折半查找的根本思想

取有序表的中间记录作为比拟对象,如此

〔1〕假如给定值与中间记录的关键码相等,如此查找成功；

〔2〕假如给定值小于中间记录的关键码,如此在中间记录的左半区继续查找；

〔3〕假如给定值大于中间记录的关键码,如此在中间记录的右半区继续查找.

不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败.

➢折半查找的时间复杂度

具有n个结点的折半查找判定树的深度为1log

2

n.

最好情况：比拟1次,即查找的关键码是判定树的根结点；

最坏情况：比拟次数为1log

2

n

,即查找的关键码是判定树的最下一层结点；

.

平均情况：折半查找的平均时间复杂度为O.

查找不成功的比拟次数最多不超过树的深度,最多为1log

2

n

次.

➢二叉排序树的定义

二叉排序树或者是一棵空的二叉树,或者是具有如下性质的二叉树：

⑴假如它的左子树不空,如此左子树上所有结点的值均小于根结点的值；

⑵假如它的右子树不空,如此右子树上所有结点的值均大于根结点的值；

⑶它的左右子树也都是二叉排序树.

➢二叉排序树的查找性能

如果二叉排序树是平衡的,如此其查找效率为O.如果二叉排序树为一棵斜树,如此其查找效率

为O.因此,二叉排序树的查找性能在O和O之间.

➢平衡二叉树的定义

平衡二叉树或者是一棵空的二叉排序树,或者是具有如下性质的二叉排序树：

⑴根结点的左子树和右子树的深度最多相差1.

⑵根结点的左子树和右子树也都是平衡二叉树.

➢构造平衡二叉树的根本思想

在构造二叉排序树的过程中,每当插入一个结点时,首先检查是否因插入而破坏了树的平衡性,假如是,

如此找出最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的关系,进

展相应的旋转,使之成为新的平衡子树.

➢平衡调整的四种类型

设结点A为最小不平衡子树的根结点,对该子树进展平衡化调整有以下四种情况：

⑴LL型：结点x插在根结点A的左孩子的左子树上.

⑵RR型：结点x插在根结点A的右孩子的右子树上.

⑶LR型：结点x插在根结点A的左孩子的右子树上.

⑷RL型：结点x插在根结点A的右孩子的左子树上.

➢散列查找的根本思想

散列查找也称为哈希查找、Hash查找,其根本思想是：在记录的存储位置和它的关键码之间建立一个确

定的对应关系H,使得每个关键码key和唯一的一个存储位置H相对应.在查找时,根据这个确定的对应

关系找到给定值k的映射H,假如查找集合中存在这个记录,如此必定在H的位置上.

➢散列查找的根本概念

采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间称为散列表,将关键码映射为

散列表中适当存储位置的函数称为散列函数,所得的存储位置址称为散列地址.

对于两个不同的关键码k1≠k2,有H＝H,即两个不同的记录需要存放在同一个存储位置,这种现

象称为冲突,k1和k2相对于H称做同义词.

➢散列查找的关键问题

采用散列技术需要考虑的两个关键问题是：

⑴散列函数的设计.如何设计一个简单、均匀、存储利用率高的散列函数.

⑵冲突的处理.如何采取适宜的处理冲突方法来解决冲突.

➢处理冲突的方法

开放定址法

用开放定址法处理冲突得到的散列表叫做闭散列表.

所谓开放定址法,就是由关键码得到的散列地址一旦产生了冲突,就去寻找下一个空的散列地址,只要散列

表足够大,空的散列地址总能找到,并将记录存入.

.

①线性探测法

当发生冲突时,线性探测法从冲突位置的下一个位置起,依次寻找空的散列地址,即对于键值key,设

H=d,闭散列表的长度为m,如此发生冲突时,寻找下一个散列地址的公式为：

Hi=＋di>%m〔di=1,2,…,m-1〕.

线性探测法会出现非同义词之间对同一个散列地址争夺的现象,称为堆积或聚集.

②二次探测法

当发生冲突时,二次探测法寻找下一个散列地址的公式为：

Hi=＋di>%m〔di=12,－12,22,－22,…,q2,－q2且q≤m/2〕

③随机探测法

当发生冲突时,随机探测法探测下一个散列地址的位移量是一个随机数列,即寻找下一个散列地址的公

式为：

Hi=+di>%m〔di是一个随机数列,i=1,2,……,m-1〕

拉链法〔链地址法〕

用拉链法处理冲突构造的散列表叫做开散列表.

拉链法的根本思想是：将所有散列地址一样的记录,即所有关键码为同义词的记录存储在一个单链表中

——称为同义词子表,在散列表中存储的是所有同义词子表的头指针.

➢直接插入排序的根本思想

直接插入排序的根本思想是：依次将待排序序列中的每一个记录插入到一个已排好序的序列中,直到全

部记录都排好序.

➢直接插入排序算法的性能

·时间性能

最好情况：待排序序列为正序,时间复杂度为O；

最坏情况：待排序序列为逆序,时间复杂度为O.

平均情况：待排序序列中各种可能排列的概率一样,时间复杂度为O.

·空间性能

直接插入排序只需要一个记录的辅助空间.

·稳定性

直接插入排序是一种稳定的排序方法.

➢希尔排序的根本思想

希尔排序的根本思想是：先将整个待排序记录序列分割成假如干个子序列,在子序列内分别进展直接插

入排序,待整个序列根本有序时,再对全体记录进展一次直接插入排序.

➢希尔排序算法的性能

·时间性能

希尔排序算法的时间性能是所取增量的函数,其时间性能在O和O之间,当n在某个特定X

围时,希尔排序的时间性能约为O.

·空间性能

希尔排序只需要一个记录的辅助空间,用于暂存当前待插入的记录.

·稳定性

希尔排序是一种不稳定的排序方法.

➢起泡排序的根本思想

.

起泡排序的根本思想是：两两比拟相邻记录的关键码,如果反序如此交换,直到没有反序的记录为止.

➢起泡排序算法的性能

·时间性能

最好情况：待排序记录序列为正序,时间复杂度为O；

最坏情况：待排序记录序列为反序,时间复杂度为O；

平均情况：时间复杂度为O.

·空间性能

起泡排序只需要一个记录的辅助空间,用来作为记录交换的暂存单元.

·稳定性

起泡排序是一种稳定的排序方法.

➢快速排序的根本思想

快速排序又称为分区交换排序,其根本思想是：首先选一个轴值〔即比拟的基准〕,将待排序记录分割

成独立的两局部,左侧记录的关键码均小于或等于轴值,右侧记录的关键码均大于或等于轴值,然后分别对

这两局部重复上述过程,直到整个序列有序.

➢快速排序的性能

·时间性能

最好情况：时间复杂度为O.

最坏情况：待排序记录序列为正序或逆序,时间复杂度为O.

平均情况：时间复杂度为O.

·空间性能

最好情况下为O；最坏情况下,栈的深度为O；平均情况下,栈的深度为O.

·稳定性

快速排序是一种不稳定的排序方法.

➢简单项选择择排序的根本思想

简单项选择择排序的根本思想是：第i趟〔1≤i≤n-1〕排序通过n-i次关键码的比拟,在n-i+1个记

录中选取关键码最小的记录,并和第i个记录交换作为有序序列的第i个记录.

➢简单项选择择排序算法的性能

·时间性能

简单项选择择排序最好、最坏和平均的时间复杂度均为O.

·空间性能

在简单项选择择排序过程中,只需要一个用来作为记录交换的暂存单元.

·稳定性

简单项选择择排序是一种不稳定的排序方法.

➢堆的定义

堆是具有如下性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值〔称为小根堆〕；或者

每个结点的值都大于或等于其左右孩子结点的值〔称为大根堆〕.

➢堆排序的根本思想

首先将待排序的记录序列构造成一个堆〔假设利用大根堆〕,此时,选出了堆中所有记录的最大者即堆

顶记录,然后将它从堆中移走〔通常将堆顶记录和堆中最后一个记录交换〕,并将剩余的记录再调整成堆,这

样又找出了次大的记录,以此类推,直到堆中只有一个记录为止.

➢堆排序算法的性能

·时间性能

堆排序最好、最坏和平均的时间复杂度为O.

.

·空间性能

在堆排序算法中,只需要一个用来交换的暂存单元.

·稳定性

堆排序是一种不稳定的排序方法.

➢二路归并排序的根本思想

将假如干个有序序列进展两两归并,直至所有待排序记录都在一个有序序列为止.

➢二路归并排序算法的性能

·时间性能

归并排序算法最好、最坏、平均的时间性能的时间代价是O.

·空间性能

二路归并排序在归并过程中需要与原始记录序列同样数量的存储空间,以便暂存归并的中间结果,因此

其空间复杂度为O.

·稳定性

二路归并排序是一种稳定的排序方法.