数据结构：数据结构复习2015

《数据结构：数据结构复习2015》由会员分享，可在线阅读，更多相关《数据结构：数据结构复习2015（92页珍藏版）》请在装配图网上搜索。

1、数据结构数据结构复习复习n 绪论绪论n 线性表线性表n 栈和队列栈和队列n 树树n 图图n 查找查找n 排序排序 数据结构定义数据结构定义:是一门研究是一门研究非数值计算非数值计算的程序设计问题中计算机的操作对象以的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科及它们之间的关系和操作等的学科。数据结构（数据结构（data structure）：）：数据元素数据元素和数据元素关系的集合和数据元素关系的集合。绪论绪论基本概念基本概念绪论绪论基本概念基本概念 根据数据元素间关系的基本特性，有四种基本数根据数据元素间关系的基本特性，有四种基本数据结构：据结构：集合集合：数据元素间除：数

2、据元素间除“同属于一个集合同属于一个集合”外，无外，无其它关系。其它关系。线性结构线性结构：一个对一个，如线性表、栈、队列。：一个对一个，如线性表、栈、队列。树形结构树形结构：一个对多个，如树。：一个对多个，如树。图状结构图状结构：多个对多个，如图。：多个对多个，如图。绪论绪论基本概念基本概念 数据的逻辑结构：只抽象反映数据元素的逻辑数据的逻辑结构：只抽象反映数据元素的逻辑关系关系 数据的存储（物理）结构数据的存储（物理）结构数据的逻辑结构在数据的逻辑结构在计算机存储器中的实现计算机存储器中的实现数据的逻辑结构与存储结构密切相关数据的逻辑结构与存储结构密切相关算法设计算法设计 逻辑结构逻辑结构

3、算法实现算法实现 存储结构存储结构存储结构分为：存储结构分为：顺序顺序存储结构存储结构借助元素在存储器中的借助元素在存储器中的相对位置相对位置 来表示数据元素间的逻辑关系。来表示数据元素间的逻辑关系。链式链式存储结构存储结构借助指示元素存储地址的借助指示元素存储地址的指针指针表表 示数据元素间的逻辑关系。示数据元素间的逻辑关系。绪论绪论基本概念基本概念 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：查找、排序、插入、删除、修改等数据的运算：查找、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树

4、形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：线性表特点：在数据元素的非空有限集中线性表特点：在数据元素的非空有限集中 存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元的数据元素素 存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据的数据元素元素 除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有只有一个前驱一个前驱 除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只只有一个后继有一个后继线性表线性表基本概念基本概念线性表线性表基本概念基本概念设设 A=（a1,a2,.,ai-1,ai,ai+

5、1,an）是一线性表）是一线性表1）线性表的数据元素可以是各种各样的，但同一线性）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；表中的元素必须是同一类型的；2）在表中）在表中 ai-1 领先于领先于 ai，ai 领先于领先于 ai+1，称，称 ai-1 是是 ai 的的直接前趋直接前趋，ai+1 是是ai 的的直接后继直接后继；3）在线性表中，除第一个元素和最后一个元素之外，）在线性表中，除第一个元素和最后一个元素之外，其他元素都其他元素都有且仅有一个直接前趋有且仅有一个直接前趋，有且仅有一个有且仅有一个直接后继直接后继。线性表是一种线性数据结构；。线性表是一种线性数

6、据结构；4）线性表中元素的个数）线性表中元素的个数 n 称为线性表的称为线性表的长度长度，n=0时时称为称为空表空表；5）ai 是线性表的第是线性表的第 i 个元素，称个元素，称 i 为数据元素为数据元素 ai 的序的序号，号，每一个元素在线性表中的位置，仅取决于它的每一个元素在线性表中的位置，仅取决于它的序号序号。线性表的存储表示线性表的存储表示在计算机内部可以采用两种不同方在计算机内部可以采用两种不同方法来表示一个线性表，它们分别是法来表示一个线性表，它们分别是顺序表示法和链表表示法顺序表示法和链表表示法。线性表的顺序存储结构线性表的顺序存储结构 线性表的链式存储结构线性表的链式存储结构顺

7、序存储结构的顺序存储结构的优点优点：1 1）存储密度大、空间利用率高）存储密度大、空间利用率高2 2）元素可随机存取）元素可随机存取顺序存储结构的顺序存储结构的缺点缺点：1 1）插入和删除时要移动大量的元素）插入和删除时要移动大量的元素2 2）长度较大的线性表须按最大需要的空间分）长度较大的线性表须按最大需要的空间分配存储空间配存储空间链式存储表示的实现链式存储表示的实现可定义一个结构体来表示一个结点可定义一个结构体来表示一个结点struct nodestruct nodetype data;type data;node node*next;next;头指针：头指针：存放线性链表中第一个结点的

8、存储地址；存放线性链表中第一个结点的存储地址；空指针：空指针：不指向任何结点，线性链表最后一个结点不指向任何结点，线性链表最后一个结点的指针通常是指针；的指针通常是指针；头结点：头结点：线性链表的第一元素结点前面的一个附加线性链表的第一元素结点前面的一个附加结点，称为头结点；结点，称为头结点；带头结点的线性链表：带头结点的线性链表：第一元素结点前面增加一个第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；附加结点的线性链表称为带头结点的线性链表；L L是头指针是头指针a ai-i-1 1a ai ia a2 2a a1 1a ai+i+1 1na an nL L线性链表的每个结

9、点中只有线性链表的每个结点中只有一个指针域故也称为单链表一个指针域故也称为单链表头结点头结点空指针空指针线性表线性表链式存储与实现链式存储与实现链式存储表示的特点链式存储表示的特点 逻辑上相邻的元素对应的存储位置是通过逻辑上相邻的元素对应的存储位置是通过指针指针反映反映的，不要求物理上相邻。进行插入、删除运算时，的，不要求物理上相邻。进行插入、删除运算时，只需修改指针域只需修改指针域 每个结点都设有一个指针域，存储空间的开销较大每个结点都设有一个指针域，存储空间的开销较大 一般一般不预先分配不预先分配好足够的存储空间以备使用，当有好足够的存储空间以备使用，当有元素时，需临时分配一个空的结点空间

10、，填上信息，元素时，需临时分配一个空的结点空间，填上信息，插入到线性链表中；当某个结点不再使用时，应将插入到线性链表中；当某个结点不再使用时，应将其存储空间释放。其存储空间释放。栈和队列是限定栈和队列是限定插入插入和和删除删除只能在表的只能在表的“端点端点”进行的线性表。进行的线性表。线性表线性表 栈栈 队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in栈和队列栈和队列基本概念基本概念 栈的定义和特点栈的定义和特点 定义：限定仅在定义：限定仅在表尾表尾进行插入或删除操

11、作的线性进行插入或删除操作的线性表，表尾表，表尾栈顶栈顶(top)，表头，表头栈底栈底(bottom/base)，不含元素的空表称空栈，不含元素的空表称空栈 特点：先进后出（特点：先进后出（FILO）或后进先出（或后进先出（LIFO）ana1a2.栈底栈底栈栈顶顶.出栈出栈进栈进栈栈栈s=(a1,a2,an)栈栈基本概念基本概念堆栈的定义堆栈的定义 堆栈是一种只允许在堆栈是一种只允许在表的一端进行插入和表的一端进行插入和删除运算删除运算的线性表。的线性表。允许进行运算的一端称为允许进行运算的一端称为栈顶栈顶，另一端则，另一端则称为称为栈底栈底。当表中没有元素时，称为当表中没有元素时，称为空栈空

12、栈。堆栈的插入运算简称为堆栈的插入运算简称为入栈或进栈入栈或进栈，删除，删除运算简称为运算简称为出栈或退栈出栈或退栈。根据堆栈的定义，每次删除的总是堆栈中当根据堆栈的定义，每次删除的总是堆栈中当前的前的栈顶元素栈顶元素，即最后进入堆栈的元素，即最后进入堆栈的元素 在进栈时，最先进入的元素一定在栈底，最在进栈时，最先进入的元素一定在栈底，最后进入的元素一定在栈顶。后进入的元素一定在栈顶。由于这一特点，我们常称堆栈是由于这一特点，我们常称堆栈是后进先出表后进先出表或下推表或下推表（LIFO Last In First OutLIFO Last In First Out）。）。堆栈的堆栈的特点特点栈

13、的链式存储与实现栈的链式存储与实现栈顶指针a1anan-1栈底元素栈底元素注意注意:链栈中链栈中指针的方向指针的方向链式栈链栈的特点链栈的特点 链表的头结点就是栈顶元素的结点链表的头结点就是栈顶元素的结点 根据堆栈的定义，新结点的插入和栈顶结点的删根据堆栈的定义，新结点的插入和栈顶结点的删除都在表头进行除都在表头进行 插入一个新元素，相当于在第一个结点之前插入一个新插入一个新元素，相当于在第一个结点之前插入一个新结点结点 删除链接栈的栈顶元素，就是删除链表的第一个结点。删除链接栈的栈顶元素，就是删除链表的第一个结点。不会有栈满而产生溢出的问题不会有栈满而产生溢出的问题例：对于一个栈，给出输入项

14、例：对于一个栈，给出输入项A A、B B、C C，如果输入项序，如果输入项序列由列由ABCABC组成，试给出所有可能的输出序列。组成，试给出所有可能的输出序列。A进进 A出出 B进进 B出出 C进进 C出出 ABCA进进 A出出 B进进 C进进 C出出 B出出 ACBA进进 B进进 B出出 A出出 C进进 C出出 BACA进进 B进进 B出出 C进进 C出出 A出出 BCAA进进 B进进 C进进 C出出 B出出 A出出 CBA不可能产生输出序列不可能产生输出序列CAB队列队列 队列的概念队列的概念 队列的有关运算队列的有关运算 抽象队列类的定义抽象队列类的定义 顺序队列的定义及其实现顺序队列的

15、定义及其实现 链式队列的定义及实现链式队列的定义及实现队列的概念队列的概念 队列简称队列简称队队，是一种只允许在，是一种只允许在表的一端进行插表的一端进行插入操作入操作而在表的而在表的另一端进行删除操作另一端进行删除操作的线性表。的线性表。允许进行插入的一端称为允许进行插入的一端称为队尾队尾，允许删除的一端，允许删除的一端称为称为队头队头。队的插入运算有时也简称。队的插入运算有时也简称进队进队，删除，删除运算简称为出队。运算简称为出队。队列也称为队列也称为先进先出表先进先出表。(FIFO)(FIFO)队列的有关运算队列的有关运算 进队进队 在队列的尾部插入一个新元素在队列的尾部插入一个新元素

16、出队出队 删除队列的队头元素删除队列的队头元素 测试队空测试队空 测试队列是否为空测试队列是否为空 测试队满测试队满 测试队列是否为满测试队列是否为满 清队清队 创建一个空队列创建一个空队列 队列的顺序存储结构队列的顺序存储结构-循环队列循环队列 队列的顺序存储结构的实现队列的顺序存储结构的实现 队列的顺序存储结构的特点队列的顺序存储结构的特点队列的顺序存储结构的特点队列的顺序存储结构的特点 进行插入运算，必须先测试队满与否进行插入运算，必须先测试队满与否 删除队头元素，必须先测试队列是否为删除队头元素，必须先测试队列是否为空空循环队列循环队列 可以把队列设想成可以把队列设想成头尾相连头尾相连

17、的循环表，即把的循环表，即把存储队列元素的表从逻辑上看成一个环，这存储队列元素的表从逻辑上看成一个环，这种队列通常称为种队列通常称为循环队列循环队列。循环队列的首尾相接，当队头指针循环队列的首尾相接，当队头指针frontfront和和队尾指针队尾指针rearrear进到进到maxsize-1maxsize-1时，再前进一时，再前进一个位置就自动到个位置就自动到0 0，这可以利用，这可以利用除法取余除法取余的的运算来实现。运算来实现。插入中修改队尾指针的语句可以写成：插入中修改队尾指针的语句可以写成：rear=(rear+1)%maxsizerear=(rear+1)%maxsize 删除中修改

18、队头指针的语句可以写成：删除中修改队头指针的语句可以写成：front=(front+1)%maxsizefront=(front+1)%maxsize 在循环队列示意图中，可以看到队列空和队在循环队列示意图中，可以看到队列空和队列满时，都有列满时，都有rear=frontrear=front，为区分队空队满，采用两种处理方法：为区分队空队满，采用两种处理方法：设一个设一个标志位标志位以区别队列是空还是满，以区别队列是空还是满，少用一个元素空间，约定以少用一个元素空间，约定以“队列头指针在队队列头指针在队列尾指针的下一位置上列尾指针的下一位置上”作为队列满的标志。作为队列满的标志。链式队列的定义

19、链式队列的定义 队列的链式存储结构就是用一个队列的链式存储结构就是用一个线性链表线性链表来来表示队列，简称表示队列，简称链接队链接队。把线性链表的把线性链表的头指针定义为队头指针头指针定义为队头指针headhead，把链表的把链表的最后结点指针最后结点指针rearrear作为队尾指针作为队尾指针，并且限定只能在链头进行删除，只能在链尾并且限定只能在链头进行删除，只能在链尾进行插入。这个线性链表就构成了一个链接进行插入。这个线性链表就构成了一个链接队列。队列。树是树是n个结点的有限集合，在任一棵非空树中：个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结

20、点。（2）其余结点可分为个互不相交的集合，而且这）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的些集合中的每一集合都本身又是一棵树，称为根的子树。子树。J JI IA AC CB BD DH HG GF FE E树是递归结构，在树的定义中又用到了树的概念。树是递归结构，在树的定义中又用到了树的概念。树树基本概念基本概念树树基本概念基本概念结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素数据元素+若干指向子树的分支若干指向子树的分支分支的个数分支的个数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点

21、度大于零的结点度大于零的结点DHIJM树树基本概念基本概念(从根到结点的从根到结点的)路径：路径：孩子孩子结点、双亲双亲结点、兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次:树的深度：树的深度：由从根到该结点所由从根到该结点所经分支和结点构成经分支和结点构成假设根结点的层次为假设根结点的层次为1,1,第第l 层的层的结点的子树根结点的层次为结点的子树根结点的层次为l+1树中叶子结点所在的最大层次树中叶子结点所在的最大层次ABCDEFGHIJMKL树树基本概念基本概念任何一棵非空树是一个二元组任何一棵非空树是一个二元组Tree=（root，F）其中：其中：root 称为根结点

22、，称为根结点，F 称为子树森林。称为子树森林。森林：森林：是是 m（m0）棵互不相交的树的棵互不相交的树的集合。集合。ArootBEFKLCGDHIJMF定义定义 二叉树的五种基本形态：二叉树的五种基本形态：NLRLRNNN二叉树二叉树基本概念基本概念二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构链式存储结构链式存储结构 使用数组存储二叉树完全二叉树的数组表示完全二叉树的数组表示012345678910113123126694051770624955880 01 12 23 34 45 5312312666 67 78 89 9706249551010111188940517二叉树的

23、顺序存储二叉树的顺序存储二叉树的顺序存储二叉树的顺序存储使用数组存储二叉树使用数组存储二叉树 A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEF1401326ABCDE FG链式存储结构链式存储结构二叉链表二叉链表二叉链表二叉链表二叉树的结点至少包含三个域：数据域二叉树的结点至少包含三个域：数据域datadata、指向其左孩子的指针域、指向其左孩子的指针域LchildLchild、指向、指向其右孩子的指针域其右孩子的指针域RchildRchild。如图所示，这种。如图所示，这种结构称为二叉链表，这种结构可以很方便地结构称为二叉链表，这种结构可以很

24、方便地根据根据Lchild Lchild 和和RchildRchild指针找到它的左孩子指针找到它的左孩子和右孩子。和右孩子。LchilddataRchild二叉链表二叉链表struct BintreeNodestruct BintreeNode Type data;/Type data;/结点的数据域结点的数据域 BintreeNode BintreeNode*Lchild;Lchild;BintreeNode BintreeNode*Rchild;Rchild;二叉链表二叉链表ADEBCF rootlchild data rchild结点结构结点结构:二叉树的链式存储二叉树的链式存储ABC

25、DEFG AB C E D F Groot孩子兄弟表示法图示孩子兄弟表示法图示C C的第一个的第一个孩子结点孩子结点E EE E的紧邻的的紧邻的右兄弟结点右兄弟结点ABCDEFG AB C E D F Groot AB C E D F G 孩子兄弟表示法图示孩子兄弟表示法图示树和森林与二叉树的转换树和森林与二叉树的转换树与二叉树之间的转换树与二叉树之间的转换森林与二叉树之间的转换森林与二叉树之间的转换树和森林的表示方法树和森林的表示方法 树的树的孩子兄弟链表结构孩子兄弟链表结构与二叉树的二叉链表与二叉树的二叉链表结构，都以结构，都以二叉链表二叉链表作为作为存储结构存储结构，它们的物，它们的物理

26、结构完全相同；理结构完全相同；在树和二叉树之间必然存在在树和二叉树之间必然存在一一对应一一对应关系；关系；如果把如果把森林中第二棵树的根结点森林中第二棵树的根结点看成是第一看成是第一棵树根结点的兄弟，同样可导出森林与二叉树棵树根结点的兄弟，同样可导出森林与二叉树的对应关系。的对应关系。I IA AC CB BD DH HG GF FE E树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子树与二叉树的转换树与二叉树的转换 F FI IA AB BD DH HG GC CE E 森林与二叉树的转换森林与二叉树的转换 森林：树的集合森林：树的集合 将将森林中树的根看成兄弟森

27、林中树的根看成兄弟，用树与二叉，用树与二叉树的转换方法，可进行森林与二叉树转换。树的转换方法，可进行森林与二叉树转换。ABCDEFGHIJABCDEFGHIJABCDEFGHIJ树与二叉树的转换树与二叉树的转换将一般树转换成一棵二叉树的步骤如下：将一般树转换成一棵二叉树的步骤如下：（1 1）在所有相邻兄弟结点之间加一条连线。）在所有相邻兄弟结点之间加一条连线。（2 2）对每个非终端结点，除了其最左孩子外，删去）对每个非终端结点，除了其最左孩子外，删去该结点与其它孩子结点的连线。该结点与其它孩子结点的连线。（3 3）以根结点为轴心，顺时针旋转）以根结点为轴心，顺时针旋转4545度。度。森林转换成

28、二叉树森林转换成二叉树如果如果F=TF=T1 1，T T2 2，.，T Tm m 是森林，则将其转换是森林，则将其转换成一棵二叉树成一棵二叉树B=B=（rootroot，LBLB，RBRB）的规则如下：）的规则如下：1 1）分别将树林中的每棵树转换为二叉树）分别将树林中的每棵树转换为二叉树2 2）从最后那棵二叉树开始，依次把后一棵二叉）从最后那棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵树的根结点的右孩子，树的根结点作为前一棵树的根结点的右孩子，直到所有的二叉树全部连接。直到所有的二叉树全部连接。二叉树的遍历二叉树的遍历先序遍历先序遍历中序遍历中序遍历后序遍历后序遍历由遍历序列恢复二叉树

29、由遍历序列恢复二叉树先序遍历先序遍历先序遍历二叉树的操作定义为：先序遍历二叉树的操作定义为：若二叉树为空，则空操作；若二叉树为空，则空操作；否则：否则：1)1)访问根结点（访问根结点（V V）；）；2)2)先序先序遍历左子树（遍历左子树（L L）3)3)先序先序遍历右子树（遍历右子树（R R）中序遍历中序遍历中序遍历二叉树的操作定义为：中序遍历二叉树的操作定义为：若二叉树为空，则空操作；若二叉树为空，则空操作；否则：否则：1)1)中序中序遍历左子树（遍历左子树（L L）；）；2)2)访问根结点（访问根结点（V V）；）；3)3)中序中序遍历右子树（遍历右子树（R R）；）；后序遍历后序遍历 后

30、序遍历二叉树的操作定义为：后序遍历二叉树的操作定义为：若二叉树为空，则空操作；若二叉树为空，则空操作；否则：否则：1)1)后序后序遍历左子树（遍历左子树（L L）；）；2)2)后序后序遍历右子树（遍历右子树（R R）；）；3)3)访问根结点（访问根结点（V V）；）；由遍历序列恢复二叉树由遍历序列恢复二叉树 已知二叉树的前序序列和中序序列可以已知二叉树的前序序列和中序序列可以唯一地构造出这棵二叉树。唯一地构造出这棵二叉树。已知二叉树的后序序列和中序序列也可已知二叉树的后序序列和中序序列也可以唯一地构造出这棵二叉树。以唯一地构造出这棵二叉树。但已知二叉树的后序序列和前序序列不但已知二叉树的后序序

31、列和前序序列不可以唯一地构造出这棵二叉树。可以唯一地构造出这棵二叉树。仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列先序序列中序序列中序序列例例:试分别找出满足以下条件的所有二试分别找出满足以下条件的所有二叉树。叉树。（1 1）二叉树的前序序列与中序序列相同）二叉

32、树的前序序列与中序序列相同 空树或缺左子树的单支树空树或缺左子树的单支树（2 2）二叉树的中序序列与后序序列相同）二叉树的中序序列与后序序列相同 空树或缺右子树的单支树空树或缺右子树的单支树（3 3）二叉树的前序序列与后序序列相同）二叉树的前序序列与后序序列相同 空树或只有根结点的二叉树空树或只有根结点的二叉树 二叉排序树的定义二叉排序树的定义 二叉排序树或者是一棵空树，或者是具二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：有下列性质的二叉树：(1)若它的左子树不空，则左子树上所有结若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；点的值均小于它的根节点的值；(2)若它的右

33、子树不空，则右子树上所有结若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；点的值均大于它的根节点的值；(3)它的左、右子树也分别是二叉排序树。它的左、右子树也分别是二叉排序树。二叉排序树的插入和删除操作二叉排序树的插入和删除操作 二叉排序树的插入二叉排序树的插入 二叉排序树的删除二叉排序树的删除 二叉排序树的插入二叉排序树的插入 二叉排序树是一种动态树表，其特点是，树的二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，而是在查找过程中，结构通常不是一次生成的，而是在查找过程中，当树中不存在关键码等于给定值时再进行插入。当树中不存在关键码等于给定值时再进行插入。插入的

34、原则是：若二叉排序树为空，则插入结插入的原则是：若二叉排序树为空，则插入结点为树的新根结点，否则进行在左子树和右子点为树的新根结点，否则进行在左子树和右子树上查找，直至某个结点的左子树或右子树为树上查找，直至某个结点的左子树或右子树为空为止，则插入结点作为一个新的叶结点，并空为止，则插入结点作为一个新的叶结点，并成为该结点的左孩子或右孩子。成为该结点的左孩子或右孩子。利用二叉排序树插入算法建立二叉排序树的例子：利用二叉排序树插入算法建立二叉排序树的例子：设有一个结点关键玛的输入序列为设有一个结点关键玛的输入序列为53，68，55，17，82，10，45，从空的二叉排序树开始，一个结点一个结点逐

35、步插入，最，从空的二叉排序树开始，一个结点一个结点逐步插入，最终建立一个二叉排序树。终建立一个二叉排序树。53536853685553685517536855178253685517821053685517821045（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。可分三种情况讨论：和插入相反，删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍仍然保持二叉排序树的特性然保持二叉排序树的特性。二叉排序树的删除二叉排序树的删除p左、右子树均非空左、右子树均非空沿沿 P 左子树的根左子树的根 C 的右子树分支找到

36、的右子树分支找到 S，S的右子树为空，将的右子树为空，将 S 的左子树成为的左子树成为 S 的双亲的双亲Q 的右子树，用的右子树，用 S 取代取代 p (5)FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(5)二叉排序树的删除二叉排序树的删除P左、右子树均非空左、右子树均非空若若 C 无右子树，用无右子树，用 C 取代取代 P (6)FPCPRCL中序遍历：中序遍历：CL C P PR FFCPRCL中序遍历：中序遍历：CL C PR F(6)二叉排序树的删除二叉排序树的

37、删除要删除二叉排序树中的要删除二叉排序树中的p结点，分三种情况：结点，分三种情况：P为叶子结点，只需修改为叶子结点，只需修改 P 双亲双亲 F的指针的指针：F-lchild=NULL F-rchild=NULL P只有左子树或右子树只有左子树或右子树P只有左子树，用只有左子树，用P的左孩子代替的左孩子代替P (1)(2)P只有右子树，用只有右子树，用P的右孩子代替的右孩子代替P (3)(4)p左、右子树均非空左、右子树均非空沿沿 P 左子树的根左子树的根 C 的右子树分支找到的右子树分支找到 S，S的右子树为空，将的右子树为空，将 S 的左子树成为的左子树成为 S 的双亲的双亲Q 的右子树，用

38、的右子树，用 S 取代取代 P (5)若若 C 无右子树，用无右子树，用 C 取代取代 P (6)二叉排序树的删除二叉排序树的删除应用实例应用实例赫夫曼树赫夫曼树 构造赫夫曼构造赫夫曼树步骤树步骤 根据给定的根据给定的n个权值个权值 w1,w2,wn，构造构造n棵只棵只有根结点的二叉树，令有根结点的二叉树，令其其权值为权值为wj；在森林中选取两棵根结点权值最小的树作左右子树，在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和左右子树根结点权值之和；在森林中删除这两棵树，同时将新得到的二叉树

39、加在森林中删除这两棵树，同时将新得到的二叉树加入森林中入森林中；重复上述两步，直到只含一棵树为止，这棵树即赫重复上述两步，直到只含一棵树为止，这棵树即赫夫曼树夫曼树。赫夫蔓编码（赫夫蔓编码（数据通信用的二进制编码数据通信用的二进制编码）用赫夫曼树可以构造一种不等长的二进制编码，用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的并且构造所得的赫夫曼编码赫夫曼编码是一种最优前缀编码，是一种最优前缀编码，即使得所传即使得所传电文的总长度最短电文的总长度最短。思想：思想：根据字符出现频率编码，使电文总长最根据字符出现频率编码，使电文总长最短。短。编码：编码：根据字符出现频率构造赫夫曼根据字符出现

40、频率构造赫夫曼树，然后树，然后将树中结点引向其左孩子的分支标将树中结点引向其左孩子的分支标为为“0”，引向，引向其右孩子的分支标其右孩子的分支标为为“1”；每个字符的编码即为；每个字符的编码即为从根到每个叶子的路径上得到的从根到每个叶子的路径上得到的0、1序列序列。应用实例应用实例赫夫曼树赫夫曼树例：例：假定用于通信的电文仅由假定用于通信的电文仅由5 5个字母个字母c1c1，c2c2，c3c3，c4c4，c5c5组成，各字母在电文中出现的频率分组成，各字母在电文中出现的频率分别为别为5 5，6 6，2 2，9 9，7 7。试为这。试为这5 5个字母设计不等长个字母设计不等长的赫夫曼编码，并给出

41、该电文的总码数。的赫夫曼编码，并给出该电文的总码数。字母集c1,c2,c3,c4,c5，频率 5,6,2,9,7 95627527697671395276713952795271667132900001111000110110111c2c5c4c1c3赫夫曼编码：赫夫曼编码：c1 c2 c3 c4 c5 110 00 111 10 01110 00 111 10 01电文总码数：电文总码数：5*3+6*2+2*3+9*2+7*2=55图图基本概念基本概念 图的定义图的定义 图图(Graph)图图G是由两个集合是由两个集合V(G)和和E(G)组组成的成的,记为记为G=(V,E)其中：其中：V(G

42、)是顶点的非空有限集是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或是边的有限集合，边是顶点的无序对或有序对有序对。例如：例如：G1=V1=v0,v1,v2,v3,v4 E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)V0V0 V4V4 V3V3 V1V1 V2V2图的术语与定义图的术语与定义 图的定义图的定义 有向图有向图有向图有向图G是由两个集合是由两个集合V(G)和和E(G)组组成的成的。其中：其中：V(G)是顶点的非空有限集是顶点的非空有限集。E(G)是是有向边有向边（也称弧）的有限集合，弧（也称弧）的有限集合，弧是顶点的

43、有序对，记为是顶点的有序对，记为，v,w是是顶点顶点，v为为弧尾弧尾，w为为弧头弧头。无向图无向图无向图无向图G是由两个集合是由两个集合V(G)和和E(G)组组成的成的。其中：其中：V(G)是顶点的非空有限集是顶点的非空有限集。E(G)是边的有限集合，边是顶点的无序对，是边的有限集合，边是顶点的无序对，记为记为(v,w)或或(w,v)，并且并且(v,w)=(w,v)。图的术语与定义图的术语与定义 例如：例如：G2=V2=v0，v1，v2，v3 E2=,例例245136G1图图G1中：中：V(G1)=1,2,3,4,5,6 E(G1)=,V0V0 V1V1 V2V2 V3V3图的术语与定义图的术

44、语与定义 图的基本术语图的基本术语1 邻接点及关联边邻接点及关联边 邻接点：边的两个顶点邻接点：边的两个顶点 关联边：若边关联边：若边e=(v,u),则称顶点则称顶点v、u 关连边关连边e2 顶点的度、入度、出度顶点的度、入度、出度 顶点顶点V的度的度=与与V相关联的边的数目相关联的边的数目 在有向图中：在有向图中：顶点顶点V的出度的出度=以以V为起点有向边数为起点有向边数 顶点顶点V的入度的入度=以以V为终点有向边数为终点有向边数 顶点顶点V的度的度=V的出度的出度+V的入度的入度 设图设图G 的顶点数为的顶点数为 n，边数为，边数为 e 图的所有顶点的度数和图的所有顶点的度数和=2*e （

45、每条边对图的所有顶点的度数和（每条边对图的所有顶点的度数和“贡献贡献”2度）度）V0V0 V4V4 V3V3 V1V1 V2V2e e V0V0 V1V1 V2V2 V3V3图的术语与定义图的术语与定义路径、回路路径、回路 无向图无向图 G=（V，E）中的顶点序列）中的顶点序列v1,v2,vk,若若(vi,vi+1)E(i=1,2,k-1)，v=v1,u=vk，则称该序列是从顶点，则称该序列是从顶点v到顶点到顶点u的路径；若的路径；若v=u，则称该序列为回路；，则称该序列为回路；有向图有向图 D=（V，E）中的顶点序列）中的顶点序列 v1,v2,vk,若若 E (i=1,2,k-1)，v=v1

46、，u=vk，则称该序列是从顶点则称该序列是从顶点v到顶点到顶点u的路径；若的路径；若v=u，则称该序列为回路；，则称该序列为回路；图的术语与定义图的术语与定义例如例如在在图图G1中，中，V0,V1,V2,V3 是是 V0 到到 V3 的的路径；路径；V0,V1,V2,V3,V0 是回路。是回路。在在图图G2中，中，V0,V2,V3 是是 V0 到到 V3 的路径；的路径；V0,V2,V3,V0 是回路。是回路。无向图无向图G1G1有向图有向图G2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3图的术语与定义图的术语与定义生成树生成树 包含无向图包含无向

47、图 G 所有顶点的的极小连通子图称为所有顶点的的极小连通子图称为G生成树。生成树。极小连通子图极小连通子图意思是：该子图是意思是：该子图是G的连通子图，的连通子图，在该子图中删除任何一条边，子图不再连通，若在该子图中删除任何一条边，子图不再连通，若T是是G的生成树当且仅当的生成树当且仅当T满足如下条件：满足如下条件：T是是G的连通子图的连通子图 T包含包含G的所有顶点的所有顶点 T中无回路中无回路连通图连通图G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3图的存储结构图的

48、存储结构一、数组表示法一、数组表示法(邻接矩阵表示邻接矩阵表示)邻接矩阵：邻接矩阵：G的邻接矩阵是满足如下条件的的邻接矩阵是满足如下条件的n阶矩阵：阶矩阵：Aij=Aij=1 1 若若(v(vi i,v,vj)E E 或或 v E E0 0 否则否则0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0在数组表示法中，用邻接在数组表示法中，用邻接矩阵表示顶点间的关系矩阵表示顶点间的关系 V0V0 V4V4 V3V3 V1V1 V2V20 1 1 00 1 1 00 0 0

49、00 0 0 00 0 0 10 0 0 11 10 0 00 0 0图的存储结构图的存储结构二、邻接表二、邻接表邻接表是图的链式存储结构邻接表是图的链式存储结构1、无向图的邻接表、无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中；顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储。关联同一顶点的边：用线性链表存储。V0V0 V4V4 V3V3 V1V1 V2V22 2 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 03 34 4该结点表示边该结点表示边（

50、V3 V2V3 V2）,其中的其中的2 2是是V2V2在一维数组中的位置在一维数组中的位置图的存储结构图的存储结构无向图的邻接表的特点无向图的邻接表的特点 1）在）在G邻接表中，同一条边对应两个结点；邻接表中，同一条边对应两个结点；2）顶点）顶点v的度：等于的度：等于v对应线性链表的长度；对应线性链表的长度；3）判定两顶点）判定两顶点v，u是否邻接：要看是否邻接：要看v对应线性对应线性链表中有无对应的结点。链表中有无对应的结点。4）在）在G中增减边：要在两个单链表插入、删除中增减边：要在两个单链表插入、删除结点；结点；5）设存储顶点的一维数组大小为）设存储顶点的一维数组大小为 m（m 图的图的

51、顶点数顶点数n），图的边数为），图的边数为 e，G占用存储空间为：占用存储空间为：m+2*e。G占用存储空间与占用存储空间与G的顶点数、边数均有的顶点数、边数均有关；适用于边稀疏的图。关；适用于边稀疏的图。图的存储结构图的存储结构二、邻接表二、邻接表2 有向图的邻接表有向图的邻接表顶点：用一维数组顶点：用一维数组存储（按编号顺序）存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储以同一顶点为起点的弧：用线性链表存储 V0V0 V1V1 V2V2 V3V31234v0v2v3v1vexdata firstarc 3 2 4 1adjvex next类似于无向图的邻接表，所不同的是：类似于无向

52、图的邻接表，所不同的是：以同一顶点为以同一顶点为起点起点的弧：用线性链表存储的弧：用线性链表存储图的遍历图的遍历 图的深度遍历（图的深度遍历（DFS）从图的某一顶点从图的某一顶点 V0 出发，访问此顶点；然后依出发，访问此顶点；然后依次从次从 V0 的的未被访问未被访问的邻接点出发，的邻接点出发，深度优先遍历深度优先遍历图，图，直至图中所有和直至图中所有和 V0 相通的顶点都被访问到；相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为

53、止所有顶点都被访问为止。V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7图的遍历图的遍历图的深度遍历（DFS）V1V2V4V5V3V7V6V8例例1例例2V1V2V4V5V3V7V6V8例例1深度遍历深度遍历1：V1 V2 V4 V8 V5 V6 V3 V7例例2深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7 由于由于没有规定访问邻接点的顺序没有规定访问邻接点的顺序，所以深，所以深度优先序列不是唯一的。度优先序列不是唯一的。例例1深度遍历深度遍历2：V1 V3 V7 V8 V6 V5 V2 V4图的深度遍历（DFS）V1

54、V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V5图的遍历图的遍历 图的广度遍历（图的广度遍历（BFS）从图的某一顶点从图的某一顶点V0V0出发，访问此顶点后，依次访出发，访问此顶点后，依次访问问V0V0的各个未曾访问过的邻接点；然后分别从这些邻的各个未曾访问过的邻接点；然后分别从这些邻接点出发，接点出发，广度优先遍历广度优先遍历图，直至图中所有已被访问图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重被访问，则另选图中一个未被访问的顶

55、点作起点，重复上述过程，直至图中所有顶点都被访问为止复上述过程，直至图中所有顶点都被访问为止。V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8图的最小生成树图的最小生成树 问题提出问题提出要在要在n个城市间建立通信联络网，个城市间建立通信联络网，顶点顶点表示城市表示城市权权城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小建立该通信网所需花费的总代价）最小最小代最小代价生成树价生成树 问题分析问题分析n个城

56、市间，最多可设置个城市间，最多可设置 n(n-1)/2 条线路条线路。n个城市间建立通信网，只需个城市间建立通信网，只需 n-1 条线路条线路。问题转化为：如何在可能的线路中选择问题转化为：如何在可能的线路中选择 n-1 条，能把条，能把所有城市（顶点）均连起来，且所有城市（顶点）均连起来，且总耗费（各边权值之总耗费（各边权值之和）最小和）最小。图的最小生成树图的最小生成树 普里姆算法的基本思想普里姆算法的基本思想 取图中任意一个顶点取图中任意一个顶点 v v 作为生成树的根，作为生成树的根，之后往生成树上添加新的顶点之后往生成树上添加新的顶点 w w。在添加的顶点在添加的顶点 w w 和已经

57、在生成树上的顶点和已经在生成树上的顶点 v v 之间必定存在一条边，并且该边的权值在所之间必定存在一条边，并且该边的权值在所有连通顶点有连通顶点 v v 和和 w w 之间的边中取值最小。之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树之后继续往生成树上添加顶点，直至生成树上含有上含有 n-1 n-1 个顶点为止。个顶点为止。图的最小生成树图的最小生成树 克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 考虑问题的出发点：为使生成树上边考虑问题的出发点：为使生成树上边的权值之和达到最小，则应使生成树中的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。每一条边的权值尽可能地小。具体做法：先构造一个只含具体做法：先构造一个只含 n 个顶点的个顶点的子图子图SG，然后从权值最小的边开始，若，然后从权值最小的边开始，若它的添加不使它的添加不使SG中产生回路，则在中产生回路，则在SG 上加上这条边，如此重复，直至加上上加上这条边，如此重复，直至加上n-1条边为止。条边为止。