数据结构知识点.docx

数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号〔数值、字符等〕的集合。
数据元素〔数据成员〕是数据的根本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等数据对象具有一样性质或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
完全二叉树：一假设设二叉树的深度为k,那么共有k层。除第k层外，其它各层（1〜k-1）的结点数都到达最大个数，第k层从右向左连续缺假设干结点，这就是完全二叉树二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V遍历根的左子树记作L遍历根的右子树记作R。那么可能的遍历次序有：前序VLR镜像VRL;中序LVR镜像RVL;后序LRV镜像RLV前序遍历二叉树算法的框架是：假设二叉树为空，那么空操作；否那么访问根结点（V）;前序遍历左子树（L）;前序遍历右子树（R）。遍历结果-+a*b-cd/ef树的后根次序遍历：当树非空时依次后根遍历根的各棵子树访问根结点：树后根遍历EFBCGDA;对应二叉树中序遍历EFBCGDA;树的后根遍历结果与其对应二叉树。
表示的中序遍历结果一样：树的后根遍历可以借助对应二叉树的中序遍历算法实现最小堆和最大堆：如果有一个关键码集合K={K0,K1,K2,K3,….,Kn-1}，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中。并满足Ki<K2i+1且Ki<K2i+2（或者Ki>K2i+1且KiK2i+2）i=0,1,••-.[〔n-2〕/2],那么称这个集合为最小堆或最大堆。堆是最高效的一种数据构造，每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。
堆的建立：有2种方式建立最小的堆，一种方式是通过第一个构造函数建立一个空堆，其大小通过动态存储分配得到，另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以调整形成一个堆。路径：从树中一个结点到达另一个结点之间的分支构成该两结点之间的路径。
路径长度：是指路径上的分支条数，树的路径长度是从树的根结点到每一个结点的路径长度之和。由树的定义，从根结点到达书中每一结点有且仅有一条路径。
Huffman树：带权路径长度最小的二叉树应是权值大的外结点离根结点最近的扩大二叉树。带路径长度最小的扩大二叉树不一定是完全二叉树。集合是成员（元素）的一个群集。集合中的成员可以是原子（单元素）,也可以是集合。
字典是一些元素的集合，每个元素有一个称作关键码〔key〕的域，不同元素的关键码互不一样。
散列方法：理想的搜索方法是可以不经过比拟，一次直接从字典中得到要搜索的元素。如果在元素存储位置与其关键码之间建立一个确定的对应函数关系Hash（）,使得每个关键码与构造中一个唯一的存储位置相对应：Address=Hash（key）。在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进展同样的计算，把求得的函数值当做元素存储位置，在构造中按此位置搜索。这就是散列方法。在散列方法中所用转换函数叫做散列函数。按此方法构造出来的表叫做散列表。使用散列方法进展搜索不必进展屡次关键码的比拟，搜索速度比拟快，可以直接到达或逼近具有此关键码的表项的实际存放地址。散列函数是一个压缩映象函数。关键