计算机-数据结构与算法.docx

欢迎阅读第一章数据结构与算法1.1算法1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述。1=1S=0DO WHILE Ifront,那么循环队列中的元素个数为rear-front；如果rearl,那么该结点的父结点的编号为INT（k/2）。假设2k这n,那么编号为k的左子结点编号为2k；否那么该结点无左子结点（显然也没有右子结点）。假设2k+lWn,那么编号为k的右子结点编号为2k+l；否那么该结点无右子结点。4、二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。与线性链表类似，用于存储二叉树中各元素的存储结点也由两局部组成：数据域和指针域。但在二叉树中，由于 每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指 向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。批注wx3:这样，不仅节省了存储空间，又能方便地 确定每一个结点的父结点与左右子结点的位置，但顺序 存储结构对于一般的二叉树不适用。* ： 一般二叉树通常采用链式存储结构，对于满二叉树与完全二叉树来说，可以按层序进行顺序存储。5、二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：（1）前序遍历（DLR）：假设二叉树为空，那么结束返回。否那么：首先访问根结点，然后遍历左子树，最后遍历右子 树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。（2）中序遍历（LDR）：假设二叉树为空，那么结束返回。否那么：首先遍历左子树，然后访问根结点，最后遍历右子 树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历（LRD）：假设二叉树为空，那么结束返回。否那么：首先遍历左子树，然后遍历右子树，最后访问根结 点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。1.7查找技术查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找结果：（查找成功：找到；查找不成功：没找到。）平均查找长度：查找过程中关键字和给定值比拟的平均次数。1、顺序查找基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比拟，直到两者相符，查到所要 找的元素为止。否那么就是表中没有要找的元素，查找不成功。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比拟，最坏情况下 需要比拟8次。顺序查找一个具有n个元素的线性表，其平均复杂度为0 （n）。以下两种情况下只能采用顺序查找：1）如果线性表是无序表（即表中的元素是无序的），那么不管是顺序存储结构还是链式存储结构，都只能用顺序 查找。2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。