0%

数据结构笔记

排序

1、堆排序,我觉得拿到最大的十个元素堆排序是不需要排完的,因为堆排序的算法是将(从大到小排)大顶堆的最上面的元素输出,作为排序的结果,每一次把堆顶的元素拿出去之后,它会把堆的最右下角位置的元素拿到堆顶填补空缺,此时这个补位的元素左右子树都是大顶堆,将这两个子树的堆顶元素和补位元素比较,选择较大的做交换,并将这个子树一直做上面的调整,直到叶子节点,此时堆顶又是一个可以输出的最大元素,这就完成了一趟排序,要输出十个元素,只需要十趟排序。
2、快速排序,最坏情况(有序),递归树成为单支树,每次划分只得到一个比上一次少一个记录的子序列。

数组和广义表

1、广义表的表头(Head)和表尾(Tail):
当广义表非空时,称第一个元素a1为广义表的表头,其余元素组成的表(a2, a3, …,an)称为广义表的表尾。
表头可能是原子,也可能是广义表,但表尾一定是广义表。