datastruc当turebysunli.ppt

* * * * Software Architecture * 优先队列 性质：队列通过insert和extract操作维护元素队列 其中extract返回队列中最小（最大）值 * Software Architecture * 优先队列（堆实现） Insert：n++,x(n)=t,siftup(x[1..n]) Extract: return x(1), x(1)=x(n),n--,siftup(x[1..n-1]) * Software Architecture * 排序： 利用优先队列： N次Insert： N次Extract for i=(2…n) siftup(i) for i=n i=2 i-- swap(1,i) siftdown(i-1) 对比快排优于时间复杂度（最坏情况） 劣于空间复杂度 但一般情况下快排仍要比堆排序快 快排为什么那么快：/pongba/archive/2008/06/13/2544933.aspx * Software Architecture * 程序中的堆： 要求对象只能分配在堆： Class UPNum{}; UPNun n; //error! UPNum *p=new UPNum ; //fine 析构函数声明为私有，建立伪构造函数 private: ~UPNum(); public: void destroy() const(delete this;) P-destroy(); * Software Architecture * 禁止对象分配在堆上 UPNum *p=new UPNum；//error 将new声明为私有 Class UPNum{ private: static void *operator new(size_t size); static void operator delete(void *ptr); }; 判断对象是否在分配堆上？ 树 常见结构： 二叉树?二元查找树 ?平衡二叉树 Struct btree{ int m_value; btree* left; btree* right; } * * ISP * Software Architecture * 查询二叉树：BST 优势在于快速查找数据 基本操作：查询，插入，删除 时间复杂度logn * Software Architecture * 1.遍历顺序 在BST中查一个树：给出的序列不可能是检查的序列： 252 401 398 330 344 397 363 202 911 240 912 245 363 2 252 401 398 330 后面的值均小于后大于之前的值 * Software Architecture * 遍历顺序 输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 4 7 5 12 10 ?? 10?????????????????????????????????????????? /?? \????????????????????????????????????????? 5???? 12? ????????????????????????????????????? / ? \??????????? ??????????????????????????? 4???? 7? * Software Architecture * 1.在后续遍历得到的序列中，最后一个元素为树的根结点。 Root=seq[n] 2.比根结点小的元素都应该位于序列的左半部分； seq[1…i] 3.从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点seq[j…n-1] 根据这样的划分，把序列划分为左右两部分，我们递归地确认序