清华大学《数据结构》邓俊辉

0.A.syllabus................................................................[1]0.B.introduction.........................................................[9]0.C.big‐o...................................................................[17]0.D.algorithm_analysis............................................[34]0.X.sorting+lowerBound.........................................[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.orderedVector.................................[114]1.Sequence.g.insertionsort....................................[131]1.Sequence.x.javaImplementation.......................[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.probe‐backtrack......................[196]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.binaryTree............................................[283]4.Trees.c.preorderTraversal.................................[291]4.Trees.d.inorderTraversal...................................[300]4.Trees.e.postorderTraversal...............................[308]4.Trees.f.breadth‐firstTraversal............................[319]4.Trees.g.huffmanTree.........................................[324]5.Bst.a.binarySearchTree.....................................[341]5.Bst.b.avlTree......................................................[353]5.Bst.c.splayTree..................................................[371]5.Bst.d.b‐tree........................................................[390]5.Bst.e.red‐blackTree...........................................[411]5.Bst.x.kd‐tree.......................................................[431]6.Hashing.a.hashing..............................................[450]2.Stacks+queues.e.queue......................................[208]6.Hashing.b.collision..............................................[465]6.Hashing.c.karp‐rabin...........................................[480]6.Hashing.d.bucketsort+radixsort.........................[488]6.Hashing.x.md5....................................................[497]6.Hashing.y.languages...........................................[503]7.Pq.a.basicImplementation.................................[510]7.Pq.b.binaryHeap................................................[516]7.Pq.c.selectionsort...............................................[527]7.Pq.d.tournamentsort..........................................[531]7.Pq.e.heapsort.....................................................[537]7.Pq.x.leftistHeap..................................................[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.topologicalSorting................................[618]8.Graph.f.bi‐connectivity.......................................[625]8.Graph.g.mst........................................................[638]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]8.Graph.h.sp..........................................................[657]邓俊辉[e-mail]0.绪论(a)课程简介-1-FAQ：教师1DataStructures&Algorithms(Spring2010),TsinghuaUniversity❖主讲：邓俊辉，[e-mail]❖助教00240074于泽，[e-mail]30240184李锐喆，[e-mail]白彦冰，[e-mail]-2-FAQ：选修，还是不选修2DataStructures&Algorithms(Spring2010),TsinghuaUniversity❖目标定位——是否需要选修数据结构程序设计语言：编写出合法的程序数据结构与算法：实现高效处理大规模数据的算法软件工程：参与团队编写大规模、复杂、鲁棒和高效的软件❖基本条件——可否选修数据结构已修C语言程序设计，有一定的编程基础通过作业0进一步自我测试❖更多条件——能否学好数据结构对计算机科学与应用的兴趣多思考、多动手、多讨论的习惯目标明确，心态平和投入落实，持之以恒-3-FAQ：考评及要求3DataStructures&Algorithms(Spring2010),TsinghuaUniversity❖考核形式=编程实验+测验/考试+加分//00240074、30240184根据实际情况，期末可能做总体微调❖编程实验在提供的范围内选做，积分累计在线试测，限时提交//特殊情况须提前寄出MD5或请假白盒、黑盒测试结合，结果正确性兼顾代码质量❖测验/考试基本知识点的掌握基本方法和技巧的灵活运用❖加分课堂参与+课后交流+作业创