数据结构(线性表、栈、队列、二叉树、图).ppt

常见数据结构,线性表、栈、队列、二叉树、图,（一）、线性表,线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继，如图2.1所示。例如：英文字母表(A,B,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，,每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A，而字母B后面是字母C。,（二）、栈,栈是允许在一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。栈结构也称为后进先出表（LIFO）。,队列(Queue)的定义队列是限定仅在表的一端进行插入，在另一端进行删除操作的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。队列的插入操作，称为入队；队列的删除操作，称为出队。当队列中没有元素时称为空队列。设队列q=(a0，a1，a2，an-1)，则a0称为队头元素，an-1称为队尾元素。元素按a0，a1，a2，an-1的次序入队，出队也只能按照这个次序。队列和栈相反，队列的操作是按先进先出（FirstInFirstOut）的原则进行的，又称为先进先出的线性表（简称FIFO表）。,三、队列,（四）、二叉树类型与定义,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,介绍基本术语,叶子结点结点结点总数深度层,结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依次累计。树中结点的最大层次称为树的深度或高度。,性质1：在二叉树的第i层上至多有2i-1个结点。(i1),用归纳法证明：归纳基：归纳假设：归纳证明：,i=1层时，只有一个根结点，2i-1=20=1；,假设对所有的j，1ji，命题成立;,二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。,性质2：深度为k的二叉树上至多含2k-1个结点（k1）,证明：,基于上一条性质，深度为k的二叉树上的结点数至多为20+21+2k-1=2k-1,性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1,证明：,设二叉树上结点总数n=n0+n1+n2,又二叉树上分支总数b=n1+2n2,而b=n-1=n0+n1+n2-1,由此，n0=n2+1,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。,性质4：具有n个结点的完全二叉树的深度为log2n+1,证明：,设完全二叉树的深度为k,则根据第二条性质得2k-1n顶点1-边2-顶点2-v，点和边交替相接，且互不相同。,图的遍历,1、概念：从图中某一结点出发系统地访问图中所有结点，使每个结点恰好被访问一次，这种运算称图的遍历。为了避免重复访问某个结点，可以设一个标志数组visitedI，未访问时值为FALSE，访问一次后就改为TRUE。2、分类：深度优先遍历和广度优先遍历。,深度优先遍历：类似于树的先序遍历，从图中某个结点V0出发，访问此结点，然后依次访问从V0的未被访问的邻接点出发进行深度优先遍历，直到图中所有和V0有路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点V1作为起点，重复上述过程，直至图中所有结点都被访问到为止。,广度优先遍历：从图中某个结点V0出发，访问此结点，然后依次访问与V0邻接的、未被访问过的所有结点，然后再分别从这些结点出发进行广度优先遍历，直到图中所有被访问过的结点的相邻结点都被访问到。若此时图中还有结点尚未被访问，则另选图中一个未被访问过的结点作为起点，重复上述过程，直到图中所有结点都被访问到为止。,无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少有个顶点。,