课程概况
学习了基本的数据结构后，我们已经可以用程序来解决现实中的一些问题了。但是，怎样提升程序在运行效率呢？
如何快速地把图书按序号从小到大整理好？如何通过一个ID编号在数据库中高效地查找相对应的信息？如何迅速找到所有内容中含有“数据结构”的文档？《高级数据结构与算法》将通过使用高级的数据结构和高效的算法，让你学会如何解决这些对运行时间要求比较严格的问题。
高级数据结构和算法能够根据实际情况，满足一些复杂问题对数据规模、运行时间的要求，帮助我们更有效地解决问题。当我们面对实际问题的时候，高级数据结构和算法让我们有更广泛的空间，选择出与问题本身最为契合的数据结构，并利用相关算法来提升运行效率。
完成这门课之时，你将掌握多维数组、广义表、Trie树、AVL树、伸展树等高级数据结构，并结合内排序、外排序、检索、索引有关的算法，高效地解决现实生活中一些比较复杂的应用问题。合理使用这些高级数据结构和相关算法是程序运行效率的关键因素，学好这门课会让你在之后的计算机专业课程以及项目设计中更得心应手，同时也将让你站在更高的角度去理解问题、设计程序。
课程大纲
第一周 内排序（上）Lecture 1 Internal Sorting I
• 排序问题的基本概念 The Basic Concept of Sorting
• 插入排序 ( Shell 排序) Insertion Sort (Shell Sort)
• 选择排序 (堆排序) Selection Sort (Heap Sort)
• 交换排序（冒泡排序、快速排序）Exchange Sort (Bubble Sort, Quick Sort)
第二周 内排序（下）Lecture 2 Internal Sorting II
• 归并排序 Merge Sort
• 桶排序 Bin Sort
• 静态基数排序 Static Radix Sort
• 链式基数排序 Linked Radix Sort
• 索引排序 Indexing Sort
• 排序算法的时间代价 The Complexity of Sorting
第三周 文件与外排序 Lecture 3 File and External Sort
• 主存、外存、文件的组织 Main Memory, External Memory and File’s Architecture
• 外排序 External Sort
第四周 检索 Lecture 4 Searching
• 检索的概念 The Concept of Searching
• 基于线性表的检索 Linear Searching
• 集合的检索 Set-based Searching
• 散列表的概念和散列函数 The Concept of Hash Table, Hash Function
• 散列冲突处理 Solving Hash Collision
• 散列的实现及性能分析 The Implementation of Hash Table and Its Complexity Analysis
第五周 索引 Lecture 5 Indexing
• 静态索引 Static Indexing
• 倒排索引 Inverted Indexing
• B树 B-Trees
• B+树 B+-Trees
• 位索引技术 Bitmap Indexing
• 红黑树 Red-Black Tree
第六周 高级数据结构（上——线性结构）Lecture 6 Advanced Data Structures I , List-Structure
• 多维数组 Multilists
• 广义表 Generalized Tables
• 存储管理 Memory Management
第七周 高级数据结构（下——树形结构）Lecture 7 Advanced Data Structures II , Tree-Structure
• Trie 树 Trie Trees
• AVL树概念及插入算法 The AVL Tree and Its Inserting Algorithm
• AVL树删除及性能分析 The Deletion of AVL Trees, Complexity Analysis
• Splay树 Splay Tree
第八周 数据结构应用（不考核）Lecture 8 The application of Data Structures (Optional)
预备知识
熟悉C/C++描述的基础数据结构与算法
Basic Data Structures and Algorithms in C/C++
参考资料
[1] 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008年 6月。普通高等教育“十一五”国家级规划教材。
Textbook: Ming Zhang, Tengjiao Wang, Haiyan Zhao, "Data Structures and Algorithms", Higher Education Press, 2008.
[2] 张铭，赵海燕，王腾蛟，《数据结构与算法实验教程》，高等教育出版社，2011年 1月。普通高等教育“十一五”国家级规划教材。
[3] 张铭、赵海燕、王腾蛟，《数据结构与算法－－学习指导与习题解析》，高等教育出版社，2005年 10月。 “十五”国家级规划教材配套参考书。
[4] S. Sahni ，《数据结构算法与应用—C++语言描述》 ，汪诗林等译，机械工业出版社，2000.
[5] M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影印，2003年1月。
[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Inroduction to Algorithms, 高等教育出版社影印，2002年5月。
[7] D. E.Knuth 著，苏运霖 译，《计算机程序设计艺术，第1卷基本算法》，国防工业出版社，2002年。
[8] J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
[9] C. A. Shaffer, Data Structures and Algorithm Analysis in C++, Third Edition, Dover Publications., 2011.
[10] 王晓东，《算法设计与分析》 ，清华大学出版社，2003年1月。
常见问题
2. 课程采用的算法语言? Which programming languages does the course use?
本课程采用基于C++的伪代码授课和出习题。编程作业是POJ（http://dsalgo.openjudge.cn/）自动评判的，该平台目前接受 C、C++、Java等都可以。
