数据结构总结甄选

数据结构总结

一、绪论

1、数据结构：数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示

和实现”的学科。具有相同特征的数据元素的集合，如果在这些数据元素之间存在一种或多种特定的关系，则称为一种数据结构。

2、建立模型：

3、数据：客观对象的符号表示；

数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑和处理，通常具有完整确定的实际意义。（节点、顶点、记录）

数据项：数据不可分割的最小标识单位。一个数据元素可由若干数据项组成，通常不具有完整确定的实际意义。

4、数据的逻辑结构：数据之间的逻辑关系，是抽象的数学模型。

5、数据元素之间存在四种基本结构：

集合（无关系），

线性结构（一对一）：除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，如表、栈。

树形结构（一对多）：每一个元素只有一个直接前趋，有0个或多个直接后继。如树

图状结构（多对多）：每一个元素可以有0个或多个直接前趋，有0个或多个直接后继。如图。

7、数据的存储结构：顺序存储结构，链式存储结构，散列结构和索引结构。

8、一个算法必须满足以下五个重要特性：有穷性、确定性、可行性、有输入和有输出。

9、评价算法的标准：正确性，可读性，可维护性，健壮性，效率。

10、算法效率的度量：计算复杂度、渐进复杂度

11、老师的课后题：

数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构：数据元素和数据元素关系的集合。

数据的逻辑结构：只抽象反映数据元素的逻辑关系

数据的存储（物理）结构：数据的逻辑结构在计算机存储器中的实现。

存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。

链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。

数据的逻辑结构与存储结构密切相关：算法设计→逻辑结构；算法实现→存储结构。

数据的运算：检索、排序、插入、删除、修改等

第二章、线性表的基本概念

1、线性表特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素。存在唯一的一个被称作“最后一个”的数据元素。除第一个外，集合中的每个数据元素均只有一个前驱。除最后一个外，集合中的每个数据元素均只有一个后继。

2、线性表的元素

1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；

2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前趋，ai+1是ai的直接后继；

3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。线性表是一种线性数据结构；

4）元素的个数n称为表的长度，n=0时称为空表；

5）ai是表的第i个元素，称i为数据元素ai的序号，每个元素在线性表中的位置，仅取决于它的序号。

6）可在表的任意位置进行插入和删除操作。

3、顺序表的特点：用连续的存储单元存放线性表的元素，元素存储顺序与元素的逻辑顺序一致。

4、线性表的链式存储结构特点：

1）用一组任意的存储单元存储线性表的数据元素。

2）利用指针实现了用不相邻的存储单元存放逻辑上相邻的一组元素。

3）每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息（指针）。

5、结点

数据域：数据元素本身的信息

指针域：指示直接后继的存储位置

6、几个概念：

头指针：存放线性链表中第一个结点的存储地址；

空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针；

头结点：线性链表的第一数据元素结点前面的一个附加结点，称为头结点。头结点不保存数据。

带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；

6、链表中没有数据结点称为：空表

7、结点的形式定义：

TypedefstructLNode{

ElemTypedata;/数据域

structLnodene_t;/指针域

}LNode，LinkList；

LinkListL；

/L为单链表的头指针，是LinkList类型的变量

8、单链表操作的特点：单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。

9、静态链表：用数组实现的链式结构，称为静态链表。

10、线性链表的特点：

1.用一组任意的存储单元存储线性表中数据元素；

2.通过指针保存直接后继元素的存储地址来表示数据元素之间的逻辑关系；

3.通过头指针（或首结点）给出线性链表；

4.链表中结点空间是动态分配的；

5.插入、删除操作通过修改结点的指针实现；

6.只能顺序存取元素，不能直接存取元素。

11、循环链表（带有头结点的单向环表）

最后一个结点的指针域的指针又指回第一个结点（头结点）的链表。判断为是否空表的条件：h->ne_t==h

12、循环链表的特点：

1.从一个结点可找到链表中的任意一个结点；

2.判断是否为表尾结点的条件：p->ne_t==L。

3.有时，用表尾指针表示循环链表。

第三章栈

1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。表尾端称为栈顶，表头端称为栈底。

2、能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。

3、第一个进栈的元素在栈底；最后一个进栈的元素在栈顶；第一个出栈的元素为栈顶元素；

最后一个出栈的元素为栈底元素。栈的特点：后进先出

4、空栈top=base；栈满top-base=stacksize(无可分配空间)

7、栈的链式存储结构，也称链栈

8、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针

9、队列是限定仅能在表头进行删除，表尾进行插入的线性表。

10、能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。

11、第一个入队的元素在队头；最后一个入队的元素在队尾；第一个出队的元素为队头元素；

最后一个出队的元素为队尾元素，队列的特点：先进先出。

13、存在问题：

设数组大小为M，则：当front=0，rear=M时，再入队发生溢出——真溢出，当front0，rear=M时，再入队发生溢出——假溢出。

14、队列的应用：

1）解决计算机主机与外设不匹配的问题；

2）解决由于多用户引起的资源竞争问题；

3）离散事件的模拟——模拟实际应用中的各种排队现象；

4）用于处理程序中具有先进先出特征的过程。

第五章数组和广义表

1、数量固定，数据类型相同的（变量）元素组合在一起。使用一个名称代表它。这个名称就是数组名。如果要访问其中某个元素(变量)，可以使用元素的索引值(下标)来访问它。在C语言中，数组元素的索引值从0开始。

2、二维数组是数据元素为线性表的线性表。

3、数组的逻辑结构：二维数组中的每个元素都受两个线性关系的约束——行关系、列关系。

4、数组的基本操作：1）读：给定一组下标，读出对应的数组元素；2）写：给定一组下标，存储或修改与其相对应的数组元素。读/写操作本质上只对应一种操作——寻址。确定指定元素在内存中的物理地址。

5、数组的存储：两种形式，既可以是顺序存储，也可以采用链式结构。

6、数组的存储结构与寻址——一维数组

设具有M个元素的一维数组的下标范围为闭区间[0,M-1]，每个数组元素占用L个存储单元。ai的存储地址：Loc(ai)＝Loc(a0)＋i_L

7、数组的存储结构与寻址——二维数组

常用的映射方法有两种：

按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。

按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。

8、值相同元素或者非零元素的分布有一定规律的矩阵，称为特殊矩阵。（对称矩阵、上（下）三角矩阵。）

9、含有较多值相同或较多零元素，且值相同或者零元素分布没有一定规律的矩阵称为稀疏矩阵。

10、稀疏矩阵采用三元组存储：(行,列,值)

11、广义表是一种不同构的线性结构，

12、广义表的基本性质

1.广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；

2.在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素称为原子(atom)，也可以是广义表，称为广义表的子表(sublist)；

3.当每个元素均为原子且类型相同时，就是线性表。

13、广义表的术语

表头：LS的第一个元素称为表头

表尾：其余元素组成的表称为LS的表尾

表长：为最外层包含元素个数

深度：所含括弧的重数。原子的深度为0，“空表”的深度为1

例：A=()空表表长：0；深度：1

B=(b,c,d)表长：3，深度：1

C=(a,B)=(a,(b,c,d))表长：2，深度：2

D=(A,B,C)=((),(b,c,d),(a,(b,c,d)))表长：3，深度：3

14任何一个非空广义表LS=(1,2,,n)均可分解为：表头Head(LS)=1和表尾Tail(LS)=(2,,n)两部分。

例如：D=(E,F)=((a,(b,c))，F)Head(D)=E，Tail(D)=(F)；Head(E)=aTail(E)=((b，c))；Head(((b,c)))=(b，c)，Tail(((b,c)))=()；Head((b,c))=b,Tail((b,c))=(c)；Head((c))=cTail((c))=()

15、求广义表的深度GListDepth(L)：广义表L的深度=广义表L中括号重数

例L=(a,(b,c),((d)))

GListDepth(a)=0原子

GListDepth((b,c))=1线性表

GListDepth(((d)))=2

GListDepth(L)=3

16、比较广义表和线性表的结构特点。

相似处：都是链表结构。

不同处：1广义表的数据元素可能还是个广义表；2删除时，不仅要删除原子结点，还需要删除相应的表结点。

17、广义表的特殊形态

在广义表中，若任意一个元素(原子、子表)只能在广义表中出现一次，称为纯表，纯表：对应一棵树。

线性表是只包含原子的纯表。若存在共享元素（原子或子表在表中出现多次），则称为再入表，如果再入表中没有回路：对应一个DAG(有向无环图)。

递归表是有回路的再入表，循环表(cycliclist，递归表)对应有向图。

18、广义表应用：函数的调用关系，内存空间的引用关系，LISP语言

第六章树和二叉树

一、树是n个结点的有限集合。树是递归结构，树的定义是递归定义。

任意一棵非空树中：

（1）有且仅有一个称为根root的结点。

（2）其余结点可分为若干个互不相交的集合，且这些集合中的每一集合本身又是一棵树，称为根的子树。

二、树的应用

常用的数据组织形式—计算机的文件系统。

不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式进行组织。

三、树的基本术语

树的结点：包含一个数据元素的内容及若干指向子树的分支。

孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。

双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如B是E的双亲。

兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。

堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。

祖先结点：某一结点的祖先是从根到该结点所经分支上的所有结点；如H的祖先为A、D。

子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J。结点的度：结点子树的个数；如D的度为3。

叶子结点：也叫终端结点，是度为0的结点；如E、F、G、H、I、J。

分枝结点：度不为0的结点；如A、B、C、D。

结点层次：根结点的层定义为1，根的孩子为第2层结点，依此类推。

树的高度（深度）：树中结点的最大层次；如图所示树的高度为3。

树的度：树中各结点的度的最大值；如图所示树的度为3。

有序树：子树之间存在明确的次序关系的树。

无序树：不考虑子树的顺序。

森林：m（m>=0）棵互不相交的树的集合。

结点:数据元素+若干指向子树的分支

结点的度:分支的个数

树的度:树中所有结点的度的最大值

叶子结点:度为零的结点

分支结点:度大于零的结点

(从根到结点的)路径：由从根到该结点所经分支和结点构成

孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点

结点的层次:假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1

树的深度：树中叶子结点所在的最大层次

森林：是m（m≥0）棵互不相交的树的集合。任何一棵非空树是一个二元组Tree=（root，F）

其中：root称为根结点，F称为子树森林。

有序树：子树之间存在明确的次序关系的树。

无序树：子树之间没有顺序要求。

四、二叉树

定义：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左和右子树的、互不相交的二叉树组成。

形式定义：数据关系R满足：

若D＝Φ，则R＝Φ，称为是空二叉树。

若D≠Φ，则R＝{H}，H是如下二元关系：

(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；

(2)若D-{root}≠Φ，则存在D-{root}＝{Dl,Dr}，且Dl∩Dr=Φ。

性质1：

在二叉树的第i层上至多有2i-1个结点(i≥1)。例：i=3：最多4个结点

性质2：

深度为k的二叉树上至多含2k-1个结点(k≥1)。

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1两类特殊的二叉树

满二叉树：指的是深度为k且含有2k-1个结点的二叉树。

完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。

性质4：

具有n个结点的完全二叉树的深度为log2n+1。

性质5：

若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲；否则i不等于1，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子；否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点；否则，编号为2i+1的结点为其右孩子结点。

五、二叉树的存储结构

1、二叉树的顺序结构

对于完全二叉树，采用一组连续的内存单元，按编号顺序依次存储完全二叉树的结点。

2.二叉链表——二叉链表中每个结点包含三个域：数据域、左指针域、右指针域。

3.三叉链表——三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域。

4.静态二叉链表——采用数组存贮。

5.双亲链表

六、遍历的基本概念

遍历：按某种搜索路径访问二叉树中的每个结点，且每个结点仅被访问一次。

访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据等。

二叉树的遍历

二叉树的遍历，就是按某种次序访问二叉树中的结点，要求每个结点访问一次且仅访问一次。

二叉树由根、左、右三部分组成。

二叉树的遍历可以分解为：访问根，遍历左和遍历右。

令：L：遍历左、D：访问根结点、R：遍历右

有六种遍历方法：基本：DLR，LDR，LRD；镜象：DRL，RDL，RLD

约定先左后右，有三种遍历方法：DLR、LDR、LRD，分别根据访问根结点的次序称为：先序遍历、中序遍历和后序遍历。

先序遍历（DLR）若二叉树非空

（1）访问根结点；

（2）先序遍历左；

（3）先序遍历右。

中序遍历（LDR）若二叉树非空

（1）中序遍历左；

（2）访问根结点；

（3）中序遍历右。

后序遍历（LRD）若二叉树非空

（1）后序遍历左；

（2）后序遍历右。

（3）访问根结点；

七、线索二叉树

遍历二叉树的结果可求得结点的一个线性序列。指向线性序列中的“前趋”和“后继”的指针，称作“线索”。

八、树的存贮结构

1、双亲表示法——通过保存树每个结点的双亲结点的位置，来表示树中结点之间的结构关系。

2、孩子表示法——通过保存树中每个结点的孩子结点的位置，表示树中结点之间的结构关系。

方法1：多重链表（类似二叉链表，采用多叉结点）

两种方式：定长结点和不定长结点

定长结点：优点是结点结构一致，便于实现树的操作。缺点是浪费一些内存空间。

不定长结点：优点是节省内存空间。缺点是不定长的结点会使一些操作实现变复杂。

方式2：孩子链表

将树中的每个结点的孩子排列起来，看成一个线性表，采用线性链表进行存贮。

3、孩子兄弟表示法——用二叉链表作为树的存贮结构。

九、最优二叉树（赫夫曼树）

路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；

路径长度：路径上的分支数目称为路径长度；

结点的权：给树中结点所赋的具有物理意义的值；

结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；

树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作WPL=wi_Li。

哈：假设有n个权值（w1,w2,,wn），构造有n个叶子结点的二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小的二叉树称为哈。

构造Huffman树步骤

1.根据给定的n个权值{w1,w2,wn}，构造n棵只有根结点的二叉树，令其权值为wj

2.在森林中选取两棵根结点权值最小的树作左右，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。

3.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。

4.重复上述两步，直到只含一棵树为止，这棵树即哈。

Huffman编码（数据通信用的二进制编码）

用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使得所传电文的总长度最短。

思想：根据字符出现频率编码，使电文总长最短。

编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标为“0”，引向其右孩子的分支标为“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。

译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束

第七章图

图的定义：图(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为弧头。

无向图——无向图G是由两个集合V(G)和E(G)组成的。

其中：V(G)是顶点的非空有限集。E(G)是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v,w)=(w,v)。

连通分量（强连通分量）

无向图G的极大连通子图称为G的连通分量。

极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

有向图D的极大强连通子图称为D的强连通分量。

极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。生成树—包含连通图G所有顶点的极小连通子图称为G生成树。

极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树

当且仅当T满足如下条件：T是G的连通子图、T包含G的所有顶点、T中无回路

邻接表——邻接表是图的链式存储结构

1、无向图的邻接表

顶点：通常按编号顺序将顶点数据存储在一维数组中；

关联同一顶点的边：用线性链表存储。

无向图的邻接表的特点

1）在G邻接表中，同一条边对应两个结点；

2）顶点v的度：等于v对应线性链表的长度；

3）判定两顶点v，u是否邻接：要看v对应线性链表中有无对应的结点。

4）在G中增减边：要在两个单链表插入、删除结点；

5）设存储顶点的一维数组大小为m（m图的顶点数n），图的边数为e，G占用存储空间为：m+2e。G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图。

2、有向图的邻接表（类似于无向图的邻接表，不同的是：以同一顶点为起点的弧：用线性链表存储）

顶点：用一维数组存储（按编号顺序）

以同一顶点为起点的弧：用线性链表存储

3、有向图的逆邻接表（类似于有向图的邻接表，不同的是：以同一顶点为终点弧：用线性链表存储）

顶点：用一维数组存储（按编号顺序）

以同一顶点为终点的弧：用线性链表存储。

三、图的遍历

图的深度遍历（DFS）

从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；

若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。（没有规定访问邻接点的顺序，所以深度优先序列不是唯一的）

图的广度遍历（BFS）

从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。

四、图的最小生成树

1、普算法（Prim）

设G=（V，GE）为一个具有n个顶点的连通网络，T=（U，TE）为构造的生成树。

（1）初始时，U={u0}，TE=；

（2）在所有uU、vV-U的边（u,v）中选择一条权值最小的边，不妨设为（u,v）；

（3）(u,v)加入TE，同时将v加入U；

（4）重复(2)(3)，直到U=V为止；

2、克(Kkal)算法

设连通网N=(V,{E})。

令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量。

在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量上为止。

3、两种算法比较

算法名普算法克算法

时间复杂度O(n2)O(eloge)

适应范围稠密图稀疏图

五、有向无环图

——拓扑排序

AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（ActivityOnVerte_network），简称AOV网。

若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继。

AOV网中不允许有回路，这意味着某项活动以自己为先决条件。

拓扑排序

把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。

检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

拓扑排序的方法

在有向图中选一个没有前驱的顶点且输出之。

从图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

——关键路径

AOE网

AOE——用边表示活动的网。它是有一个带权的有向无环图。

顶点——表示事件，弧——表示活动，

权值——活动持续的时间。

路径长度——路径上各活动持续时间之和

关键路径——路径长度最长的路径叫关键路径

AOV网、AOE网，用都能表示工程各子工程的流程，一个用顶点表示事件，一个用边表示活动，但AOV网侧重表示活动的前后次序，AOE网除表示活动先后次序，还表示了活动的持续时间等，因此可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。

六、最短路径

路径长度最短的最短路径的特点：在这条路径上，必定只含一条弧，并且这条弧的权值最小。

下一条路径长度次短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该点（只含一条弧）；或者是从源点经过顶点v1，再到达该顶点（由两条弧组成）。

再下一条路径长度次短的最短路径的特点：可能有三种情况：或者直接从源点到该点（只含一条弧）；或者是从源点经过顶点v1，再到达该顶点（由两条弧组成）；或者是从源点经过顶点v2，再到达该顶点。

其余最短路径的特点：它或者是直接从源点到该点（只含一条弧）；或者是从源点经过已求得最短路径的顶点，再到达该顶点。

求最短路径步骤：

1、初始时令S={V0}，T={其余顶点}，T中顶点对应的距离值，若存在，为弧上的权值，若不存在，为无穷

2、从T中选取一个其距离值为最小的顶点W，加入S，

3、对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值；

4、重复上述步骤，直到S中包含所有顶点，即S=V为止

第九章查找

查找表：由同一类型的数据元素（或记录）构成的集合。

查找表的基本操作

1)查询某个“特定的”数据元素是否在表中

2)检索某个“特定的”数据元素的各种属性

3)插入一个数据元素

4)删去某个数据元素

静态查找表：只作查询和检索操作的查找表。

动态查找表：在查找过程中同时作插入或删除操作的查找表。

记录：由若干数据项构成的数据元素。

主关键字：能唯一地标识一个记录的关键字。

次关键字：用以识别若干记录的关键字。

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的记录，则称查找成功，查找结果为该记录在查找表中的位置；否则称为查找不成功，查找结果为0或NULL。

查找方法评价：平均查找长度

平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度。

用于度量查找算法的效率——查找算法的基本操作：比较

静态查找：在指定的表中查找某一个“特定”的数据元素是否存在，检索某一个“特定”数据元素的各种属性。动态查找：在查找的过程中同时插入表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。

一、静态查找表

静态查找

顺序表的查找：顺序查找

有序表的查找：折半查找

索引顺序表的查找：分块查找

1、顺序表查找特点

无排序要求；

存储结构：顺序、链式；

平均查找长度ASLss=(n+1)/2；

2、有序表查找

查找表：用有序表表示

查找方法：折半查找（二分查找）

查找过程：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止

树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树。

折半查找的特点

要求元素按关键字有序。

存储结构：顺序。

平均查找长度ASLbs=log2(n+1)-1

3、索引顺序表的查找

查找表的组织：分块索引，除表本身以外，尚需建立一个“索引表”。

查找方法：查找索引表；在数据块内顺序查找

4、查找方法比较

二、二叉树和平衡二叉树

动态查找

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

（1）若左不空，则左上所有结点的值均小于根结点的值；

（2）若右不空，则右上所有结点的值均大于根结点的值；

（3）根结点的左、右也分别为二叉排序树。

二叉排序树的特点：是一种动态树表，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。

新插入结点的特点：一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点

插入新结点的时机：当查找不成功时。

插入算法：

（1）执行查找算法，找出被插入结点的双亲结点；

（2）判断被插入结点是其双亲结点的左孩子结点还是右孩子结点，将被插入结点作为叶子结点插入；

（3）若二叉树为空，则首先单独生成根结点。

对二叉排序树进行中序遍历可以得到有序序列

二叉排序树的特点

含有n个结点的二叉排序树不唯一，与结点插入的顺序有直接关系。当查找失败后，在叶结点插入。删除某个结点后，二叉排序树要重组。

没有对树的深度进行控制。

二叉排序树的适用范围

用于组织规模较小的、内存中可以容纳的数据。对于数据量较大必须存放在外存中的数据，则无法快速处理。

二叉排序树的特点之一（缺陷）：没有对树的深度进行控制。

在构造二叉排序树的过程中进行“平衡化”处理，成为平衡二叉树（AVL树）。

平衡二叉树

AVL树得名于它的发明者XXX和XXX。

结点的平衡因子：该结点左的深度减去右的深度。

平衡二叉树：所有结点的平衡因子只可能是－1、0、1的二叉排序树，或者说每个结点的左、右深度差绝对值不超过1。

平衡的二叉排序树是对二叉排序树的改进。

平衡二叉排序树：所有结点的平衡因子只可能是－1、0、1的二叉排序树，或者说每个结点的左、右深度差绝对值不超过1。

平衡二叉树——LL调整：新插入结点在A的左根结点的左上。

平衡二叉树——RR调整：新插入结点在A的右根结点的右上

平衡二叉树——LR调整：新插入结点在A的左根结点的右上。

平衡二叉树——RL调整：新插入结点在A的右根结点的左上。

三、B-树和B+树

动态查找

B-树：B+树：

定义。定义。与B树的差异

查找算法。查找算法，与B树算法的差异

插入算法——结点分裂，使B树升高。

删除算法——结点合并，使B树降低。

B-树的定义：B-树是一种平衡的多路查找树。

定义：一棵m阶的B树，或为空，或为满足下列特征的m叉树：

(1)树中每个结点至多有m棵子树；

(2)若根结点不是叶子结点，则至少有两棵子树；

(3)除根之外的所有非终端结点至少有m/2棵子树；

(4)所有的非终端结点中包含下列信息数据

B-树的查找过程

从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。

若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；

若查找不成功，则返回插入位置。

B-树的插入过程

在查找不成功之后，需进行插入。

显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况：

1）插入后，该结点的关键字个数n

2）插入后，该结点的关键字个数n=m，则需进行“结点分裂”，

(A0,K1,,Ks-1,As-1,Ks,As,Ks+1,,Kn,An)

令s=m/2，在原结点中保留：

(A0，K1，，Ks-1，As-1)

建新结点p

将（Ks，p）插入双亲结点。

如果双亲结点插入后也满，则继续对双亲结点进行结点分裂操作。

如果双亲结点为空，则建立新的根结点。

在插入新关键字时，需要自底向上分裂结点，最坏情况下，从被插关键字所在叶结点到根的路径上的所有结点都要分裂。B-树是通过结点的分裂而长高的。

B+树：B-的一种变形。定义：一棵m阶的B+树是满足下列特征的m叉树：

(1)树中每个结点至多有m棵子树；

(2)若根结点不是叶子结点，则至少有两棵子树；

(3)除根之外的所有非终端结点至少有m/2棵子树；

(5)所有叶子结点均在同一层，其中存放数据文件中记录的关键字及指向该记录的指针，或存放数据文件分块后每块的最大关键字及指向该块的指针。叶结点按关键字大小顺序排序。可以将每个叶结点看成一个基本索引块（直接指向数据文件）。

(6)所有分支结点可看成是索引的索引，使结点中仅包含它的各个子结点中最大（或最小）关键字的分界值及子结点的指针。

B+树的查找

B+树有两个头指针：一是指向B+树的根结点；另一是指向关键字码最小的叶结点，所有叶结点链成线形表，则可以直接从最小关键字开始顺序检索。

当从B+树根结点开始随机查找时，检索方法与B树相似，但若在分支结点中的关键字与检索关键字相等时，检索并不停止，要继续查找到叶结点为止。

四、哈表

散列法（哈法）基本思想

一个确定的函数关系h

以结点的关键字Key为自变量

函数值hash(Key)作为结点的存储地址

检索时也是根据这个函数计算其存储位置

通常散列表的存储空间是一个一维数组

散列地址是数组的下标

散列法的几个重要概念

负载因子α=n/m

散列表的空间大小为m

填入表中的结点数为n

某个散列函数对于不相等的关键字计算出了相同的散列地址。在实际应用中，不产生冲突的散列函数极少存在同义词

发生冲突的两个关键字

散列法（哈法）

哈表——应用哈函数，由记录的关键字确定记录在表中的地址，将记录放入此地址，这样构成的表叫哈表。哈查找——又叫散列查找，利用哈函数进行查找的过程叫哈查找。

构造哈函数的基本原则

运算尽可能简单

尽可能减少冲突

函数的值域必须在表长的范围内

构造哈函数

直接定址法：取关键字或关键字的某个线性函数值为哈地址。

数字分析法：取关键字的若干数位组成哈地址。

平方取中法：取关键字平方后的中间几位为哈地址。

折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为哈地址。

除留余数法：取关键字被某个不大于哈表长m的数p除后所得余数为哈地址。

哈函数为H(key)=key%p，p<=m

随机数法：选择一个随机函数，取关键字的随机函数值为它的哈地址。H(key)=random(key)

散列法（哈法）

在构造这种特殊的“查找表”时，除了需要选择一个“好”（尽可能少产生冲突）的哈函数之外，还需要找到一种“处理冲突”的方法。

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈地址。

常用的解决冲突的方法：开放地址法，链地址法，再哈法，建立一个公共溢出区。

解决冲突的方法

开散列方法（openhashing，也称为拉链法，separatechaining）

把发生冲突的关键码存储在散列表主表之外

闭散列方法（closedhashing，也称为开地址方法，openaddressing）

把发生冲突的关键码存储在表中另一个槽内

1、顺序表，线性表的优缺点

答：顺序表的特点：用连续的存储单元存放线性表的元素，元素存储顺序与元素的逻辑顺序一致

线性表特点：在数据元素的非空有限集中

存在唯一的一个被称作“第一个”的数据元素。

存在唯一的一个被称作“最后一个”的数据元素。

除第一个外，集合中的每个数据元素均只有一个前驱。

除最后一个外，集合中的每个数据元素均只有一个后继。

2、什么是链表基本操作

链表：多个结点链接成一个表，它是线性表的链式存储结构。用指针实现。

基本操作：1、取数据元素操作2、插入操作3、删除操作

3、多少种链表之间的关系基本算法

线性链表：

循环链表（带有头结点的单向环表）：最后一个结点的指针域的指针又指回第一个结点（头结点）链表

双向链表：结点中有两个指针域，其一指向直接后继，另一指向直接前趋。

静态链表：用数组实现的链式结构，称为静态链表

3、栈什么场景下应用基本操作

定义:是限定仅在表尾进行插入或删除操作的线性表。

（表尾称为栈顶；表头程栈底；后进先出的线性表LIFO结构）

应用：数值转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值

基本操作：1）初始化操作2）销毁栈操作3）置空栈操作4）取栈顶元素操作

5）进栈操作6）退栈操作7）判空操作

4、队列种类基本操作

定义：队列是限定仅能在表头进行删除，表尾进行插入的线性表。是一种先进先出的线性表FIFO

（插入端称为队尾；删除端称为队头）

链队列：用链表表示的队列称为链队列。

循环队列：需要控制位置，头尾指针位置。

基本操作：1）初始化操作2）销毁操作3）置空操作4）出队操作

5）取队头元素操作6）入队操作7）判空操作

5、递归（基本术语）

定义：简单说，一个用自己定义自己的概念，称为递归定义。（任何递归程序都可通过非递归程序实现）

6、稀疏矩阵

含有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵

稀疏矩阵采用三元组存储：(行,列,值)

7、广义表性质

定义：广义表是一种不同构的线性结构，是线性表的推广。

基本性质：1.广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；

2.在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素称为原子，也可以是广义表，称为广义表的子表(sublist)；

3.当每个元素均为原子且类型相同时，就是线性表

广义表的术语：

表头：LS的第一个元素称为表头

表尾：其余元素组成的表称为LS的表尾

表长：为最外层包含元素个数

深度：所含括弧的重数。原子的深度为0，“空表”的深度为1

广义表和线性表的结构特点。

相似处：都是链表结构。

不同处：1广义表的数据元素可能还是个广义表；2删除时，不仅要删除原子结点，还需要删除相应的表结点。广义表的特殊形态：

图包含递归表包含再入表包含纯表(树)包含线性表。广义表是线性与树型结构的推广。

广义表应用：函数的调用关系、内存空间的引用关系、LISP语言

定义：是N个结点的有限集。（树是递归结构，树的定义是递归定义）

树的应用：常用的数据组织形式——计算机的文件系统

9、二叉树

定义：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左和右子树的、互不相交的二叉树组成

10、二叉树性质

性质1：在二叉树的第i层上至多有2的i-1次方个结点(i≥1)。例：i=3：最多4个结点

性质2：深度为k的二叉树上至多含2的k-1次方个结点(k≥1)。

性质3：对任何一棵二叉树T，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1

完全二叉树和满二叉树是两个特殊形态二叉树

性质4：具有n个结点的完全二叉树的深度为(log2n)+1。

性质5：若对含n个结点完全二叉树从上到下从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲；否则i不等于1，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子；否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点；否则，编号为2i+1的结点为其右孩子结点。

11、如何遍历2叉树

遍历：按某种搜索路径访问二叉树中的每个结点，且每个结点仅被访问一次。

访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据等。

二叉树的遍历：二叉树的遍历，就是按某种次序访问二叉树中的结点，要求每个结点访问一次且仅访问一次。

（二叉树由根、左、右三部分组成。二叉树的遍历可以分解为：访问根，遍历左和遍历右。）令：L：遍历左、D：访问根结点、R：遍历右六种遍历方法：基本：DLR，LDR，LRD；镜象：DRL，RDL，RLD约定先左后右有三种遍历方法：DLR、LDR、LRD，分别根据访问根结点次序称为：先序遍历、中序遍历和后序遍历。

12、二叉树的基本操作

InitBiTree、DestroyBiTree、CreateBiTree、ClearBiTree、BiTreeEmpty、BiTreeDepth

13、赫夫曼树是什么满树

定义：有n个权值，构造有n个叶子结点的二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度（WPL）最小的二叉树称为哈。（树的带权路径长度WPL=树中所有叶子结点的带权路径之和）

满二叉树：指的是深度为k且含有2k-1个结点的二叉树。

完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。

14、平衡二叉树

平衡二叉树：所有结点的平衡因子只可能是－1、0、1的二叉排序树，或者说每个结点的左、右深度差绝对值不超过1。（平衡的二叉排序树是对二叉排序树的改进）。

15、什么是有向图无向图

图的定义：图(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为弧头。

无向图——无向图G是由两个集合V(G)和E(G)组成的。

其中：V(G)是顶点的非空有限集。E(G)是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v,w)=(w,v)。

16、邻接表邻接表是图的链式存储结构

17、最小生成树最小生成树的算法

定义：对于N个顶点的连通网可建立不同的生成树，其中耗费最小代价的生成树就成为最小生成树。

算法：1、普算法（Prim）2、克(Kkal)算法

算法比较：

算法名普算法克算法

时间复杂度O(n2)O(eloge)适应范围稠密图稀疏图

18、图的存储结果临界表如何画

1、数组表示法（邻接矩阵表示）2、邻接表3、十字链表4、临界多重表

1，2叉树的5个性质

2，数据结构的定义

3，算法排序，查找算法的中间过程

4，算法题，链表的算法