数据结构 珍藏 课件 精品课程 考研 大学课程 期末 复习 重点.ppt

* 1、一趟快速排序（一次划分） 　目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且 R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i-1) 枢轴 (i+1≤j≤t)。 10.3.2 快速排序 * s t low high 设 R[s]=52 为枢轴 将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字 将 R[low].key 和 枢轴的关键字进行比较，要求R[low].key ≤ 枢轴的关键字 high 23 low 80 high 14 low 52 例如 R[0] 52 low high high high low * 45 12 53 3 37 24 100 61 90 78 按中序遍历： 3，12，24，37，45，53，61，78，90，100 递增 中序遍历二叉排序树可得到一个关键字的有序序列 * 查找过程： 若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。 122 250 300 110 200 99 105 230 216 * 查找算法: Bitree searchbst(bitree t, keytype key) { if ((!t) || key= = t-data.key) return(t); else if (keyt-data.key ) return(searchbst(t-lchild,key)); else return(searchbst(t-rchild,key)); } 2、平衡二叉树（又称AVL树） 起因：提高查找速度，避免最坏情况出现。如右图情况的出现。常使用平衡二叉树。 40 24 55 12 37 12 24 37 40 55 * 平衡因子：某结点的左子树的高度减去右子树的高度的结果称为该结点的平衡因子。 平衡二叉树：每个结点的平衡因子都为 ＋1、－1、0 的二叉树。或者说每个 结点的左右子树的高度最多差一的二叉树。 14 12 5 3 9 28 63 53 60 50 17 18 7 30 14 5 3 9 28 63 53 60 50 17 18 30 是平衡树 不是平衡树 * 平衡二叉排序树失衡后的调整： 假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a。平衡二叉排序树失衡后的调整有四种情况： LL型调整 LR型调整 RR型调整 RL型调整 * 9.3 哈希表 9.3.1哈希表 1、基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较，一次存取就能得到所查元素的查找方法。 2、哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫~。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。 * 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~。 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~。 关键字 集合 存储地址 集合 hash * 9.3.2 哈希函数的构造方法 1、直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突。 实际中能用这种哈希函数的情况很少。 * 2、数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。 * 例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数。 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ….. ….. ?