04算法与基本数据结构.jsp1.ppt

算法与基本数据结构 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 数据的存储结构 数据的存储结构 算法通常由两个基本要素组成： 对数据对象的运算和操作 算法的控制结构 各种排序法比较 ⑤ 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i 1≤i≤n 的结点x有： 若i l，则结点x是根，无双亲；若i 1，则x的双亲结点P的编号为i/2。 若2i n，则结点x无左孩子 且无右孩子 ；否则，x的左孩子的编号为2i。 若2i+1 n，则结点x无右孩子；否则，x的右孩子的编号为2i+1。 基本数据结构 ?树 ?形态和基本性质 二叉树 二叉树的顺序存储 将一棵树中的所有n个结点按层编号，将编号为i的结点存入一维数组的第i个单元。 若二叉树不是完全二叉树，则通过在非完全二又树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。 用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。 基本数据结构 ?树 ?存储结构 二叉树 元素 1 2 3 4 5 6 7 地址 1 2 3 4 5 6 7 8 9 10 11 二叉树的链式存储（通常存储方式） 结点结构中设两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针唯一确定的。 基本数据结构 ?树 ?存储结构 二叉树 ?遍历 二叉树的遍历：就是按某种次序“访问”二叉树上的所有结点，使得每个结点被访问一次，而且仅被访问一次。 二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、DRL、LDR、LRD、RDL、RLD 6种遍历二叉树方案。若限定先左后右，则只有DLR、LDR、LRD三种情况，分别称之为先根 序 、中根 序 和后根 序 遍历。 基本数据结构 ?树 二叉树 1 先根（前序）遍历 ①访问根结点； ②先根遍历左子树； ③先根遍历右子树。 基本数据结构 ?树 ?遍历 二叉树 2 中根（中序）遍历 ①中根遍历左子树； ②访问根结点； ③中根遍历右子树。 3 后根（后序）遍历 ①后根遍历左子树； ②后根遍历右子树； ③访问根结点 下图二叉树的三种遍历序列 先根遍历序列： 1、2、4、8、9、5、10、11、3、6、12、7 中根遍历序列： 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）第一个元素就是要查找的元素，则比较次数为1次。 （2）最后一个元素是要找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，比较次数为n次。 （3）需要比较n/2次。因此查找算法的时间复杂度为O n 。 查找与排序 ?查找 1 顺序查找 当线性表为无序表，不管何种存储结构，只能用顺序查找。 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找 2 二分查找 折半查找 “有序”是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。 二分查找法的基本思想是：每次将处于查找区间中间位置上的数据元素的键值x与给定值K比较，若不等则缩小查找区间 若K比中间值大则舍弃下半部分，若K比中间值小则舍弃上半部分 并在新的区间内重复上述过程，直到查找成功或查找区间长度为0 即查找不成功 为止。 当有序表的长度为n时，时间复杂度为 o log2n ，即在最坏的情况下，二分查找只需比较 次。 查找与排序 ?查找 使用二分查找的线性表满足两个条件： 用顺序存储结构