清华邓俊辉数据结构
0.A.syllabus.1 0.B.introduction.9 0.C.bigo.17 0.D.algorithm_analysis .34 0.X.sorting+lower Bound.56 1.Sequence.a.adt+interface.66 1.Sequence.b.vector.79 1.Sequence.c.list.90 1.Sequence.d.cursor.105 1.Sequence.e.application .110 1.Sequence.f.ordered Vector.114 1.Sequence.g.insertionsort.131 1.Sequence.x.java Implementation.138 1.Sequence.y.skiplist .145 2.Stacks+queues.a.stack.158 2.Stacks+queues.b.applications.167 2.Stacks+queues.c.recursion .185 2.Stacks+queues.d.probebacktrack.196 2.Stacks+queues.e.queue.208 3.String.a.representation+implementation .214 3.String.b.pm.221 3.String.c.kmp .231 3.String.d.bm.251 4.Trees.a.introduction.266 4.Trees.b.binary Tree .283 4.Trees.c.preorder Traversal.291 4.Trees.d.inorder Traversal.300 4.Trees.e.postorder Traversal.308 4.Trees.f.breadthfirst Traversal.319 4.Trees.g.huffman Tree.324 5.Bst.a.binary Search Tree.341 5.Bst.b.avl Tree.353 5.Bst.c.splay Tree .371 5.Bst.d.btree .390 5.Bst.e.redblack Tree .411 5.Bst.x.kdtree.431 6.Hashing.a.hashing .450 6.Hashing.b.collision.465 6.Hashing.c.karprabin.480 6.Hashing.d.bucketsort+radixsort .488 6.Hashing.x.md5.497 6.Hashing.y.languages.503 7.Pq.a.basic Implementation.510 7.Pq.b.binary Heap .516 7.Pq.c.selectionsort .527 7.Pq.d.tournamentsort.531 7.Pq.e.heapsort .537 7.Pq.x.leftist Heap.546 8.Graph.0.introduction.557 8.Graph.a.implementation.565 8.Graph.b.bfs.580 8.Graph.c.dfs .593 8.Graph.d.genericsearch.612 8.Graph.e.topological Sorting.618 8.Graph.f.biconnectivity.625 8.Graph.g.mst.638 8.Graph.h.sp.657 8.Graph.x.maxflow.684 9.Sorting.a.quicksort .695 9.Sorting.b.mergesort .704 9.Sorting.c.selection+median.709 9.Sorting.d.shellsort.723 邓俊辉dengtsinghua.edu.cn2010年6月14日星期一0. 绪论(a) 课程简介- 1 -Data Structures i 2010; i = log(i);? 一定不含分支转向?if (1+1 != 2) goto UNREACHABLE;? 一定不能有(递归)调用?? 全是顺序执行即可?? .- 24 -Data Structures i1?递归版:return Fib(n-1) + Fib(n-2)/为何这么慢??复杂度: T(0) = T(1) = 1T(n) = T(n1) + T(n2) + 1, n>1/令S(n) = (T(n) + 1)/2则S(0) = 1 = Fib(1),S(1) = 1 = Fib(2)故S(n) = S(n1) + S(n2) = Fib(n+1)?于是T(n) = 2*S(n) 1 = 2*Fib(n+1) 1 = O O(Fib(n+1) = O O(2n)?迭代版: T(n) = O O(n)- 48 -Data Structures /O(1)while (0 >= 1; /O(1)p *= p; /O(1)return(pow); /O(1)?复杂度循环次数= r的二进制位数= n= log2(r