第1章数据结构1.3.ppt

第1章 数据结构,1.1 数据结构的基本概念1.2 线性结构1.3 非线性结构1.4 查找与排序,1.3.1 树,1.3.2 图,1.3 非线性结构,逻辑结构,1.3.1 树与二叉树,1.3.1.1 树的基本概念1.3.1.2 二叉树及其基本性质1.3.1.3 二叉树的存储结构1.3.1.4 二叉树的遍历1.3.1.5 二叉排序树1.3.1.6 树、森林与二叉树的转换1.3.1.7 二叉树应用举例,父结点：每一个结点只有一个前件，称为父结点。子结点：每一个结点可以有多个后件，都称为该结点的子结点。根结点：没有前件的结点只有一个，称为树的根结点。叶子结点：没有后件的结点称为叶子结点。,1.3.1.1 树的基本概念,1.3.1.1 树的基本概念,父结点、根结点、子结点、叶子结点、结点的度、树的度、树的深度,1.3.1.1 树的基本概念,1.3.1.1 树的基本概念,1.3.1.1 树的基本概念,树链表中的结点结构,1.3.1.1 树的基本概念,1.3.1 树与二叉树,1.3.1.1 树的基本概念1.3.1.2 二叉树及其基本性质1.3.1.3 二叉树的存储结构1.3.1.4 二叉树的遍历1.3.1.5 二叉排序树1.3.1.6 树、森林与二叉树的转换1.3.1.7 二叉树应用举例,1.什么是二叉树(1)非空二叉树只有一个根结点；(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,1.3.1.2 二叉树及其基本性质,例 画出具有3个结点的树和二叉树的所有不同形态。解：(1)具有3个结点的树有2种不同的形态，,1.3.1.2 二叉树及其基本性质,例 画出具有3个结点的树和二叉树的所有不同形态。解：(2)具有3个结点的二叉树有5种不同的形态，,树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树。即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。,1.3.1.2 二叉树及其基本性质,2.二叉树的基本性质性质1 在二叉树的第k层上，最多有2k1(k1)个 结点。性质2 深度为m的二叉树最多有2m1个结点。性质3 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。性质4 具有n个结点的二叉树，其深度至少为 log2n1 其中log2n表示取log2n的整数部分。,1.3.1.2 二叉树及其基本性质,3.满二叉树与完全二叉树满二叉树除了最后一层外，每一层上的所有结点都有两个子结点。,1.3.1.2 二叉树及其基本性质,(2)完全二叉树除了最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,1.3.1.2 二叉树及其基本性质,1.3.1.2 二叉树及其基本性质,性质5 具有n个结点的完全二叉树的深度为log2n1。性质6 设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点进行编号，则对于编号为k(k1，2，n)的结点有以下结论：(1)若k1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)。,1.3.1.2 二叉树及其基本性质,(2)若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。(3)若2k1n，则编号为k的结点的右子结点编号 为2k1；否则该结点无右子结点。,1.3.1.2 二叉树及其基本性质,1.3.1 树与二叉树,1.3.1.1 树的基本概念1.3.1.2 二叉树及其基本性质1.3.1.3 二叉树的存储结构1.3.1.4 二叉树的遍历1.3.1.5 二叉排序树1.3.1.6 树、森林与二叉树的转换1.3.1.7 二叉树应用举例,1.二叉链表#include stdlib.h struct btnode/*定义结点类型*/ET d；/*数据域*/struct btnode*lchild；/*左指针域*/struct btnode*rchild；/*右指针域*/；,1.3.1.3 二叉树的存储结构,1.3.1.3 二叉树的存储结构,1.3.1.3 二叉树的存储结构,2.二叉链表的生成(1)输入根结点值；(2)若左子树不空，则输入左子树，否则输入一个结束符；(3)若右子树不空，则输入右子树，否则输入一个结束符。,1.3.1.3 二叉树的存储结构,例如，,F,A,D,B,E,GH,P,其中表示结束符,C,1.3.1.3 二叉树的存储结构,二叉链表的生成#include stdio.h”#include stdlib.h”struct btnode int d；struct btnode*lchild；struct btnode*rchild；struct btnode*creatbt(bt，k)struct btnode*bt；int k；int b；struct btnode*p，*t；printf(input b：)；scanf(%d，&b)；,1.3.1.3 二叉树的存储结构,if(b!0)/*输入的不是结束符*/p(struct btnode*)malloc(sizeof(struct btnode)；pdb；plchildNULL；prchildNULL；if(k0)tp；/*若是第1个值，则置二叉链表头指针*/if(k1)btlchildp；/*链接到左子树*/if(k2)btrchildp；/*链接到右子树*/creatbt(p，1)；/*输入左子结点值*/creatbt(p，2)；/*输入右子结点值*/return(t)/*返回二叉链表头指针*/,1.3.1.3 二叉树的存储结构,1.3.1 树与二叉树,1.3.1.1 树的基本概念1.3.1.2 二叉树及其基本性质1.3.1.3 二叉树的存储结构1.3.1.4 二叉树的遍历1.3.1.5 二叉排序树1.3.1.6 树、森林与二叉树的转换1.3.1.7 二叉树应用举例,二叉树的遍历是要确定访问各结点的顺序,以便不重不漏地访问到二叉树的所有结点。实际就是将二叉树这种非线性结构按某种需要转化为线性序列，以便以后在对二叉树进行某种处理时直接使用。,1.3.1.4 二叉树的遍历,F,C,A,D,B,E,G,H,P,1.3.1.4 二叉树的遍历,1.前序遍历(DLR)若二叉树为空，则结束返回。否则：(1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。,1.3.1.4 二叉树的遍历,#include stdio.hstruct btnode int d；struct btnode*lchild；struct btnode*rchild；pretrav(bt)struc btnode*bt；if(bt!NULL)printf(%dn，btd)；pretrav(btlchild)；pretrav(btrchild)；return；,1.3.1.4 二叉树的遍历,A,C,B,D,F,E,H,G,P,2.中序遍历(LDR)若二叉树为空，则结束返回。否则：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。,1.3.1.4 二叉树的遍历,1.3.1.4 二叉树的遍历,#include stdio.hstruct btnode int d；struct btnode*lchild；struct btnode*rchild；intrav(bt)struc btnode*bt；if(bt!NULL)intrav(btlchild)；printf(%dn，btd)；intrav(btrchild)；return；,1.3.1.4 二叉树的遍历,A,C,B,D,F,E,H,G,P,3.后序遍历(LRD)若二叉树为空，则结束返回。否则：(1)后序遍历左子树；(2)后序遍历左子树；(3)访问根结点。,1.3.1.4 二叉树的遍历,1.3.1.4 二叉树的遍历,#include stdio.hstruct btnode int d；struct btnode*lchild；struct btnode*rchild；postrav(bt)struc btnode*bt；if(bt!NULL)postrav(btlchild)；postrav(btrchild)；printf(%dn，btd)；return；,1.3.1.4 二叉树的遍历,1.3.1 树与二叉树,1.3.1.1 树的基本概念1.3.1.2 二叉树及其基本性质1.3.1.3 二叉树的存储结构1.3.1.4 二叉树的遍历1.3.1.5 二叉排序树1.3.1.6 树、森林与二叉树的转换1.3.1.7 二叉树应用举例,二叉排序树及其构造(1)左子树上的所有结点值均小于根结点值；(2)右子树上的所有结点值均不小于根结点值；(3)左、右子树也满足上述两个条件。,1.3.1.5 二叉排序树,1.3.1.5 二叉排序树,1.3.1.5 二叉排序树,依次读入给定序列中的每一个元素：(1)若当前的二叉排序树为空，则读入的元素为根结点；(2)若读入的元素值小于根结点值，则将元素插入到左子树中；(3)若读入的元素值不小于根结点值，则将元素插入到右子树中。无论是插入到左子树还是右子树，同样按照上述方法处理。,1.3.1.5 二叉排序树,1.3.1.5 二叉排序树,1.3.1.5 二叉排序树,1.3.1.5 二叉排序树,1.3.1.5 二叉排序树,二叉排序树的查找：从根结点开始与被查值进行比较：(1)若被查值等于根结点值，查找成功。(2)若被查值小于根结点值，则查找左子树。(3)若被查值大于根结点值，则查找右子树。在左、右子树中查找时也采用上述方法。查找过程直到查找成功或所考虑的子树已空为止。,1.3.1.5 二叉排序树,1.3.1 树与二叉树,1.3.1.1 树的基本概念1.3.1.2 二叉树及其基本性质1.3.1.3 二叉树的存储结构1.3.1.4 二叉树的遍历1.3.1.5 二叉排序树1.3.1.6 树、森林与二叉树的转换1.3.1.7 二叉树应用举例,1.3.1.6 树、森林与二叉树的转换,树与二叉树的对应关系树与二叉树均可用二叉链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。,树变为二叉树的方法：（）连接亲兄弟（不包括堂兄弟）（）保留长子（断绝父亲与其他孩子关系）（）顺时针旋转45度 特点：根无右子树,1.3.1.6 树、森林与二叉树的转换,如图：F=T1，T2，T3,1.3.1.6 树、森林与二叉树的转换,森林转换为二叉树的方法 将森林 F=T1，T2.Tm的各棵树分别转成二叉树BT1，BT2.BTm 将BTi+1作为BTi根结点的右子树（i=1,2,.,m-1）,得到一棵BT。,1.3.1.6 树、森林与二叉树的转换,如图：F=T1，T2，T3,1.3.1.6 树、森林与二叉树的转换,二叉树转换森林的方法 将当前根结点和其左子树作为森林的一棵树,并将其右子树作为森林的其他子树；重复上面直到某结点的右子树为空。,1.3.1.6 树、森林与二叉树的转换,1.3.1 树与二叉树,1.3.1.1 树的基本概念1.3.1.2 二叉树及其基本性质1.3.1.3 二叉树的存储结构1.3.1.4 二叉树的遍历1.3.1.5 二叉排序树1.3.1.6 树、森林与二叉树的转换1.3.1.7 二叉树应用举例,1.3.1 树,1.3.2 图,1.3 非线性结构,逻辑结构,1.3.2.1 图的基本概念,1.3.2.2 图的存储结构,1.3.2.3 图的遍历,1.3.2 图,1.图的概念：若数据元素集合D中的各元素间存在任意前后件关系，则此数据结构称为图。2.在具有n个结点的无向图中，边的最大数目为n(n-1)/2。3.结点的后件个数称为该结点的出度,前件个数称为该结点的入度。入度与出度之和称为该结点的度。4.实际应用中,若图中任意两结点a与b间规定了一个值f(a,b)，则称该图为有值图。,1.3.2.1 图的基本概念,1.3.2.1 图的基本概念,1.3.2.1 图的基本概念,1.3.2.2 图的存储结构,1.关联矩阵 长度为n的一维数组D(1：n)存放图中各数据结点的信息。n阶的二维数组R(1：n，1：n)存放图中各结点的关联信息。其中二维数组R称为图的关联矩阵。在关联矩阵R中，每一个元素R(i，j)(1in，1jn)的定义为,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,2.求值矩阵,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,3.邻接表（“顺序索引链接”存储结构）,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,struct node/*单链表中结点结构*/int num；/*图中结点编号*/ET1 val；/*求值函数*/struct node*next；/*指针域*/；struct gpnode/*顺序存储空间中结点结构*/ET data；/*结点值*/struct node*link；/*指针域*/；,1.3.2.2 图的存储结构,1.3.2.2 图的存储结构,图邻接表的构造输入：图的结点数n；依次存放图中结点值的数组D(1：n)。输出：邻接表顺序存储空间的首地址。PROCEDURE CREATGP(D，n)定义DATA(1：n)，LINK(1：n)建立顺序存储空间FOR k0 TO n DO DATA(k)Dk；LINK(k)0 INPUT m，v/*输入图中第k个结点的后件信息*/WHILE(m0)DO/*输入后件信息未结束*/NEW(p)/*分配单链表结点*/NUM(p)m；VAL(p)v；NEXT(p)LINK(k)；LINK(k)p INPUT m，v/*继续输入后件信息*/RETURN,1.3.2.2 图的存储结构,#include stdio.h#include stdlib.hstruct node/*单链表中结点结构*/int num；/*图中结点编号*/int val；/*求值函数*/struct node*next；/*指针域*/；struct gpnode/*顺序存储空间中结点结构*/char data；/*结点值*/struct node*link；/*指针域*/；,1.3.2.2 图的存储结构,struct gpnode*creatgp(d，n)/*该函数返回顺序存储空间的首地址*/int n；char d；struct gpnode*head；struct node*p；int k，m，v；head(struct gpnode*)malloc(n*sizeof(struct gpnode)；for(k0；kn；k)/*依次对图中的每一个结点建立链接所有后件的单链表*/(headk)datadk；/*置顺序存储空间的结点值*/(headk)linkNULL；/*置顺序存储空间结点指针域为空*/printf(input linked list of%c:n，dk)；scanf(“%d%d”，&m，&v)；/*输入图中第k个结点的后件信息*/,1.3.2.2 图的存储结构,while(m0)/*输入后件信息未结束*/p(struct node*)malloc(sizeof(struct node)；pnumm；pvalv；/*后件结点号与求值函数值*/pnext(headk)link；/*新结点指针指向头结点*/(headk)linkp；/*将新结点链接到单链表链头*/scanf(%d%d，&m，&v)；/*继续输入后件信息*/return(head)；/*返回顺序存储空间的首地址*/,1.3.2.2 图的存储结构,1.深度(纵向)优先搜索法 从图中某一结点作为当前结点，然后进行以下过程：(1)处理或输出当前结点，记录当前结点的查访标志。(2)若当前结点有后件结点，则取第一个后件结点。若该后件结点未被查访过，则以该后件结点为当前结点用纵向优先搜索法进行查访。,1.3.2.3 图的遍历,深度优先搜索法遍历图的递归算法输入：图中结点数n；邻接表顺序存储空间DATA(1：n)与LINK(1：n)；单链表的存储空间NUM与NEXT。输出：遍历序列。PROCEDURE DFSGP(DATA，LINK，n，NUM，NEXT)定义标志数组MARK(1：n)FOR k1 TO n DO MARK(k)0 标志数组初始化k1FOR k1 TO n DODFS(DATA，LINK，k，MARK)IF MARK(k)0 THEN DFS(DATA，LINK，k，MARK)RETURN,1.3.2.3 图的遍历,PROCEDURE DFS(DATA，LINK，k，MARK，NUM，NEXT)OUTPUT DATA(k)处理或输出当前结点值MARK(k)1 记录当前结点的查访标志pLINK(k)当前结点的第一个后件结点WHILE(p0)DO 存在后件结点 kNUM(p)后件结点的结点编号 IF MARK(k)0 THEN 该后件结点未被查访过 DFS(DATA，LINK，k，MARK，NUM，NEXT)pNEXT(p)下一个后件结点 RETURN,1.3.2.3 图的遍历,#include stdlib.h#include“stdio.h”struct node/*单链表中结点结构*/int num；/*图中结点编号*/int val；/*求值函数*/struct node*next；/*指针域*/；struct gpnode/*顺序存储空间中结点结构*/char data；/*结点值*/struct node*link；/*指针域*/；,1.3.2.3 图的遍历,dfsgp(head，n)struct gpnode*head；int n；int k，*mark；markmalloc(n*sizeof(int)；/*定义标志数组空间*/for(k0；kn；k)markk0；/*标志数组初始化*/k1；/*for(k1；kn；k)*/dfs(head，k，mark)；/*if(markk10)dfs(head，k，mark)；*/printf(n)；free(mark)；/*释放标志数组空空间*/return；,1.3.2.3 图的遍历,static dfs(head，k，mark)/*递归函数*/struct gpnode*head；int k，*mark；struct node*p；printf(%c，(headk1)data)；/*输出当前结点值*/markk11；/*记录当前结点的查访标志*/p(headk1)link；/*当前结点的第一个后件结点*/while(p!NULL)/*还存在后件结点*/if(mark(pnum)10)/*该后件结点未被查访过*/dfs(head，pnum，mark)；/*递归调用*/ppnext；/*下一个后件结点*/return；,1.3.2.3 图的遍历,深度优先搜索法遍历图的非递归算法输入：图中的结点数n；邻接表的顺序存储空间DATA(1：n)与LINK(1：n)；单链表的存储空间NUM与NEXT。输出：遍历序列。PROCEDURE DFSGP(DATA，LINK，n，NUM，NEXT)定义标志数组MARK(1：n)定义栈顺序存储空间S(1：L)L足够大FOR k1 TO n DO MARK(k)0 标志数组初始化top0 栈初始化FOR m1 TO n DO,1.3.2.3 图的遍历,km IF MARK(k)0 THEN OUTPUT DATA(k)处理或输出当前结点值 MARK(k)1 记录当前结点的查访标志 PUSH(S，L，top，k)pLINK(k)当前结点的第一个后件结点 WHILE(p0)or(top0)DO IF(p0)THEN 存在后件结点 kNUM(p)后件结点的结点编号 IF MARK(k)0 THEN OUTPUT DATA(k)MARK(k)1 PUSH(S，L，top，k),1.3.2.3 图的遍历,ELSE pNEXT(p)取下一个后件结点 ELSE 无后件结点，但栈非空 POP(S，L，top，k)从栈中取出一个结点编号 pLINK(k)当前结点的第一个后件结点 RETURN,1.3.2.3 图的遍历,2.广度（横向）优先搜索法 从图的某一个结点出发，首先依次访问该结点的后件结点，然后再顺序访问这些后件结点的所有未被访问过的后件结点。依此类推，直到所有被访问结点的后件结点均被访问过为止。,1.3.2.3 图的遍历,广度优先搜索法遍历图输入：图中的结点数n；邻接表的顺序存储空间DATA(1：n)与 LINK(1：n)；单链表的存储空间NUM与NEXT。输出：遍历序列。PROCEDURE BFSGP(DATA，LINK，n，NUM，NEXT)定义标志数组MARK(1：n)定义循环队列顺序存储空间Q(1：n)FOR k1 TO n DO MARK(k)0 标志数组初始化frontn；rearn；s0 循环队列初始化m1FOR m1 TO n DO IF MARK(m)0 THEN 该结点未访问过,1.3.2.3 图的遍历,MARK(m)1；OUTPUT DATA(m)ADDCQ(Q，n，rear，front，s，m)将当前结点入队 WHILE(s0)DO 队列非空 DELCQ(Q，n，rear，front，s，k)从队列取出一个结点 pLINK(k)结点的后件链表头指针 WHILE(p0)DO 还有后件 kNUM(p)该后件的结点编号 IF(MARK(k)0)THEN 该后件结点未访问过 MARK(k)1；OUTPUT DATA(k)ADDCQ(Q，n，rear，front，s，k)将当前结点入队 RETURN,1.3.2.3 图的遍历,#include stdio.h#include stdlib.hstruct node/*单链表中结点结构*/int num；/*图中结点编号*/int val；/*求值函数*/struct node*next；/*指针域*/；struct gpnode/*顺序存储空间中结点结构*/char data；/*结点值*/struct node*link；/*指针域*/；,1.3.2.3 图的遍历,bfsgp(head，n)struct gpnode*head；int n；int*mark，*q，front，rear，s，k，m；struct node*p；markmalloc(n*sizeof(int)；/*定义标志数组存储空间*/for(k0；kn；k)markk0；/*标志数组初始化*/qmalloc(n*sizeof(int)；/*定义循环队列顺序存储空间*/frontn；rearn；s0；/*循环队列初始化*/m1；/*for(m1；mn；m)*/if(markm10)/*该结点未访问过*/,1.3.2.3 图的遍历,markm11；/*记录查访标志*/printf(%c,(headm1)data)；/*输出该结点*/addcq(q，n，&rear，&front，&s，m)；/*将当前结点入队*/while(s1)/*循环队列非空*/delcq(q，n，&rear，&front，&s，&k)；p(headk1)link；/*结点的后件链表头指针*/while(p!NULL)/*还有后件*/kpnum；/*该后件的结点编号*/if(markk10)/*该后件结点未访问过*/printf(%c，(headk1)data)；markk11；/*记录查访标志*/addcq(q，n，&rear，&front，&s，k)；,1.3.2.3 图的遍历,ppnext；/*/free(mark)；free(q)；return；,1.3.2.3 图的遍历,