第4章算法与基本数据结构.ppt.ppt

例：求1+2+3+…100 的和 算法描述： 第一步：将i的初始值设为1，累加和sum的初始值设为0 第二步：将sum+i的值赋给sum 第三步：将i的值+1 第四步：如果i的值100重复第二步，否则执行下一步 第5步：输出结果sum的值 结构化程序设计 基本概念 基本数据结构 基本数据结构 基本数据结构 基本数据结构 栈 队列 若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子或子结点。 父结点相同的结点互称为兄弟。 一棵树上的任何结点(不包括根本身)称为根的子孙。 反之，若B是A的子孙，则称A是B的祖先。 (3)结点的层数(或深度)从根开始算起：根的层数为l，其余结点的层数为其双亲的层数加l。 一棵树中所有结点层数的最大值称为该树的高度或深度。 二叉树 ?形态和基本性质 ?形态和基本性质 ?形态和基本性质 ?形态和基本性质 ?遍历 顺序查找 二分查找(折半查找) 直接插入排序 冒泡排序 初始状态： 9 4 6 5 8 2 第一趟： 4 9 6 5 8 2 4 6 9 5 8 2 4 6 5 9 8 2 4 6 5 8 9 2 4 6 5 8 2 9 第二趟: 4 5 6 2 8 第三趟： 4 5 2 6 第四趟： 4 2 5 第五趟： 2 4 直接选择排序 本章基本要求 ?基本知识点： （1）掌握算法的特性和基本要求； （2）掌握线性表的结构及栈和队列的概念； （3）掌握树形结构、概念及其遍历。 （4）掌握查找与排序算法 ?重点与难点： （1） 掌握树形结构及其遍历法。 二叉树有5种基本形态，如图所示 二叉树的基本性质 ①二叉树第i(i≥1)层上至多有2i-1个结点。 ②深度为k(k≥1)的二叉树至多有2k-1个结点。 ③对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2+1。 空树 只有根节点 只有左子树 只有右子树 有左右子树 基本数据结构 ?树 二叉树 满二叉树 一棵深度为k(k≥1)且有2k -1个结点的二叉树称为满二叉树，这种树的特点是每一层上的结点数都是最大结点数。如图所示。 二叉树 完全二叉树 深度为k(k≥1)有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。 二叉树 ⑤ 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1≤i≤n)的结点x有： 若i=l，则结点x是根，无双亲；若i1，则x的双亲结点P的编号为i/2。 若2*in，则结点x无左孩子(且无右孩子)；否则，x的左孩子的编号为2*i。 若2*i+1n，则结点x无右孩子；否则，x的右孩子的编号为2*i+1。 二叉树 二叉树的顺序存储 将一棵树中的所有n个结点按层编号，将编号为i的结点存入一维数组的第i个单元。 若二叉树不是完全二叉树，则通过在非完全二又树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。 用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。 ?存储结构 二叉树 11 10 9 8 7 6 5 4 3 2 1 地址 7 6 5 4 3 2 1 元素 二叉树的链式存储 结点结构中设两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针唯一确定的。 ?存储结构 二叉树 二叉树的遍历：就是按某种次序“访问”二叉树上的所有结点，使得每个结点被访问一次，而且仅被访问一次。 二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。 限定先左后右，则遍历有先根(序)、中根(序)和后根(序)遍历。 二叉树 (1)先根遍历 ①访问根结点； ②先根遍历左子树； ③先根遍历右子树。 ?遍历 二叉树 (2)中根遍历 ①中根遍历左子树； ②访问根结点； ③中根遍历右子树。 (3)后根遍历 ①后根遍历左子树； ②后根遍历右子树； ③访问根结点 下图二叉树的三种遍历序列 先根遍历序列： 中根遍历序列： 8、4、9、2、10、5、11、l、12、6、3、7 后根遍历序列： 8、9、4、10、11、5、2、12、6、7、3、1 ?遍历 二叉树 1 2 4 8 9 5 10 11 3