北大数据结构与算法实习报告

1、实习报告这个题目就是要根据一个中序遍历和一个构树的规则构造一棵BST，我采用的算法是o(nlogn) + o(n)的算法， 其中o(nlogn)是指将label按照从小到大的顺序排列， 我用到了库函数的快速排序。而o(n)是指将结点构造成一个BST。下面的内容分为两个方面， 一是构造二叉树的算法分析， 二是代码的优化。一 、o(n)的建树方法首先确定我们从题目中知道的信息，即二叉树结点的个数， 以及每个结点的描述， 题目要求我们建立一棵BST， 其中BST又满足heap的性质， 即父亲结点的priority必须大于它的子结点的priority值， 输出按照二叉树的中序遍历形式。显然这道题不可能

2、用我们常规的建树方法， 即建BST或heap的常规方法，由于结点有50000，所以我们建树的算法必须为o(nlogn) 或者o(n)。首先我们将结点按照label排序， 这样排好序的序列就是我们要构造的BST的中序遍历。然后我们根据中序遍历建树。从中序遍历中的第一个结点到最后一个结点， 逐一加入我们构造的树中，第一个结点可以独立构成一棵满足条件的树。按照中序遍历的定义，第二个结点可以是第一个结点的父亲结点（其左儿子为第一个结点） 或者是第一个结点的右儿子， 然后又可以根据两个结点的priority确定到底是放在那里。加入第三个结点也是这样操作的， 首先根据中序遍历的定义确定它可以放的位置， 然

3、后再根据heap的性质确定到底是放在哪个位置。依此类推， 当加入第I + 1个结点时， 我们知道，前面I个结点已经构造成了一棵满足条件的BST， 由中序遍历的定义， 可知第I个结点肯定在已经构造的树的最右边， 且没有右儿子。对于第I + 1个结点， 它可以放的方式有两种， 一是作为整棵已经构造好的树的根， 其中前面构造好的树为它的左子树， 二是从已构造好的BST的根结点到它的最右边的那个结点， 有一条“斜线”，如图所示： root temp i由于新加入的结点要使新构造成的二叉树满足中序遍历，那么第I+1 个结点， 可以作为这条“斜线”上任一个结点temp的右儿子， 然后原来temp的右子树作

4、为它的左子树，这样树中已经加入的 I +1 个结点就仍然满足中序遍历的条件。显然除了这两种情况，就不可能有其他的方式了。然后根据heap确定到底是插在哪里。如果第I + 1个结点的priority大于原来根结点的priority那么肯定是第一种情况， 否则， 我们应该在“斜线中”由第I个结点开始向上查找， 直到查找到的结点的priority大于第I + 1个结点的priority， 然后进行插入操作。整个算法完成。复杂度分析 显然我们需要对每个结点都进行一次插入， 然后每次插入的时候“代价”是多少呢？由于我们是从第I个结点向上查找， 并且每次查找完以后， 此次查找过的结点除了最后一个查找到的结

5、点， 都会成为新加入结点的左子树，也就是说以后在每次查找中，不可能遍历到他们了， 换句话来说，就是在查找的过程中， 每个结点最多可能被一次或两次遍历到， 综合起来， 构造树的复杂度为o(n)， 而快排需要o(nlogn)的复杂度， 所以整个算法的复杂度为o(nlogn)。下面为主要构树的代码：struct NodeType/二叉树结点类型char label12;int priority;int RightChild, LeftChild, father;root = 0;/从0结点开始构造树i = 1;/然后将0后面的结点依次插入while (i NodeAmount) /*查找新插入结点应

6、该插入的位置从i - 1， 开始查找， 一直沿着它的父亲指针， 查找到一个比新插入结点priority大的结点那么i 就插在它后面， 而它原来的右子树就成为i结点的左子树*/TempNode = i - 1;CurrPriority = BinaryTreei.priority;while (BinaryTreeTempNode.father != -1 & BinaryTreeTempNode.priority CurrPriority) BinaryTreei.LeftChild = BinaryTreeTempNode.RightChild;/查找到结点的右子树成为i的左子树Binary

7、TreeBinaryTreei.LeftChild.father = i;/纪录父亲结点BinaryTreeTempNode.RightChild = i;/查找到的结点的右儿子为 iBinaryTreei.father = TempNode;/纪录父亲结点else BinaryTreeroot.father = i;BinaryTreei.LeftChild = root;root = i;i+;二 、代码的优化虽然算法已经得出， 但是对于这道题来说， 要在规定的时间内通过还是有一点问题的。那么到底是什么地方浪费了时间呢？显然不可能是构造树的过程，在这里由于已知结点的个数，我采用的是静态的数

8、组来存储树结构，这样就有几点好处：编程容易， 不用考虑繁琐的指针操作。速度快， 指针操作的速度显然要比数组慢。 那么原因就只可能是快排或者输入的时候比较慢了，由于输入要以字符串的形式读入， 而且读入的字符串的数目也比较多，由常识可以知道， 如果用c+的读入会比较慢， 而改用c的读入就会比较快了， 这个题目的输入还要注意的一点是要把字符串进行分析， 因为按照c的读入， 我们只能将一个结点/用一个字符串读入，但是我们显然要得到每个结点的priority，这里有两种方法， 一种是遍历字符串中/后面的所有字符， 然后将后面的转化为整数， 另外一种方法是用c+的库函数itoa（）将字符串转化， 这里后面

9、一种方法显然更好一些。不过输入并不是最主要的原因， 我们都知道快速排序是一种比较快的排序方法， c+提供了qsort 和 sort两种快排， 但是两者又有区别， 即qsort和sort都需要提供一个比较函数，但是qsort稍微“死”一点，就是函数的定义格式已经规定了， 当我们传入两个参数时是传入两个地址实参， 而sort则比较灵活， 它是传入两个要比较的序列元素类型参数， 并且可以利用引用传参。可以想象， 如果是用qsort的话，由于是传入实参，所以每次传入总会要进行两个赋值操作， 极为浪费时间， 但是sort就可以利用引用传参，避免了不必要的赋值操作，相比于qsort快了很多。其他的优化就是纯粹代码上的优化了， 比如说if语句括号里面的表达式谁先谁后等等， 这个不再赘述。下面是关于各个优化的效果， 从这个表中可以看出上面的一些不起眼的小聪明有多大的用处。各个不同的实现方法在poj上所用时间，空间完全用c+的输入，用string存储label，快排没有用引用Time Limit Exceed/4992K用c+输入， 用string存储label，快排用了引用1593MS/4992K用c输入， char数组存label，快排用引用343MS/17