文档介绍：数据结构和算法
?
算法是对特定问题求解步骤的一种描述,是指令的有限序列。
算法的5个特性:
2 确定性 3 有穷性 4 输入(大于等于0个)5 输出(必须有输出)
时间复杂度是将一个算法转换成程序并在计算机上执行时,其运行所需要的时间。
空间复杂度是指算法在计算机内执行时所需存储空间的度量
程序=数据结构+算法
软件=程序+文档
数据的逻辑结构指的是数据元素之间的关系。
数据的物理结构指的是:数据结构在计算机中的标识,具体存放在哪个位置。
?什么情况下最差?
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
在几乎有序的情况下效率最差,无序的情况下效率最高。
?
NP问题叫非确定性问题。NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
递归算法:是一种直接或者间接地调用自身的算法。
递归算法的特点
递归过程一般通过函数或子过程来实现。
递归算法:在函数或子过程的内部,直接或者间接地调用自己的算法。
递归算法的实质:是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
用一组连续的存储单元存储二叉树的数据元素。将二叉树中编号为i的结点的数据元素存放在分量bt[i]中。根据完全二叉树的特性,结点在向量中的相对位置蕴含着结点之间的关系。显然,这种顺序存储结构仅适合于完全二叉树,因为在顺序存储结构中,仅以结点在向量中的相对位置表示结点之间的关系,因此,一般的二叉树也必须按完全二叉树的形式来存储,这将造成存贮的浪费。在最坏的情况下,一个深度为k且只有k个结点的单支树(树中无度为2的结点)却需2k- 1个存储分量。
?如何利用堆进行排序?
n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)
树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
大根堆排序算法的基本操作:
①初始化操作:将R[1..n]构造为初始堆;
②每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。