不要因为现实的平凡,就否定了那华丽的梦想!

2.6 伯克利 CS61B 数据结构

课程名称

Data Structures

课程概要
《CS61B:数据结构》是加州大学伯克利分校开设的一门课程,重点讲解计算机科学中的数据结构和算法设计。课程内容覆盖了广泛的基本数据结构,如数组、链表、栈、队列、哈希表、树、图等,以及这些数据结构的实现和应用。学生将深入学习如何有效地组织和存储数据,以及如何选择合适的结构来优化程序的性能。课程还包括高级主题,如平衡树、图的遍历与最短路径算法、并查集等,帮助学生掌握解决复杂问题的技巧。通过编程实践,学生不仅学会如何实现和操作这些数据结构,还将培养出高效解决问题和优化代码的能力。此外,课程强调算法分析与性能评估,指导学生在设计和实现数据结构时如何分析其时间和空间复杂度。总的来说,这门课是为学生提供扎实的数据结构基础,并为后续更高级的计算机科学课程奠定基础。
课程大纲
1. 导论 - Introduction
2. 类的定义与使用 - Defining and Using Classes  
3. 链表(一):引用、递归与链表 - Lists I References Recursion and Lists  
4. 链表(二):单链表实现 - Lists II SLLists 
5. 链表(三):双链表与数组 - Lists 3 DLLists and Arrays
6. 测试 - Testing
7. 链表(四):数组与链表对比 - Lists IV Arrays and Lists
8. 继承(一):接口与实现继承 - Inheritance I Interface and Implementation Inheritance
9. 继承(二):继承扩展、类型转换与高阶函数 - Inheritance II Extends Casting Higher Order Functions
10. 继承(三):子类型多态、比较器与Comparable接口 - Inheritance III Subtype Polymorphism Comparators Comparable
11. 继承(四):迭代器与对象方法 - Inheritance IV Iterators Object Methods
12. 渐进分析(一) - Asymptotics I
13. 期中复习 - Midterm Review
14. 并查集 - Disjoint Sets
15. 并查集与渐进分析(二) - Disjoint Sets + Asymptotics 2
16. 二叉搜索树(一) - BST 1
17. B树(2-3树与2-3-4树) - B-Trees (2-3 2-3-4 Trees)
18. 红黑树 - Red Black Trees
19. 散列法(一) - Hashing I
20. 散列法(二) - Hashing II
21. 堆与优先队列 - Heaps and Priority Queues
22. 树与图的遍历 - Tree and Graph Traversals
23. 图的遍历与实现 - Graph Traversals and Implementations
24. 最短路径 - Shortest Paths
25. 最小生成树 - Minimum Spanning Trees
26. 最小生成树(续)与有向无环图 - MSTs (continued) Directed Acyclic Graphs
27. 软件工程(一) - Software Engineering I
28. 前缀操作与字典树 - Prefix Operations and Tries
29. 排序(一):选择排序与堆排序 - Sorting I Selection Sort Heapsort
30. 排序(二):归并排序与插入排序 - Sorting II Mergesort Insertion Sort
31. 软件工程(二) - Software Engineering II
32. 排序(三):快速排序 - Sorting III Quicksort
33. 排序(四):理论界限 - Sorting IV Theoretical Bounds
34. 软件工程(三) - Software Engineering III
35. 排序(五):快速排序优化与基数排序 - Sorting V - More Quicksort Radix Sorts
36. 排序(六):基数排序与比较排序对比 - Sorting VI Radix vs Comparison Sorting
37. 软件工程(四) - Software Engineering IV
38. 数据压缩 - Compression
39. 可计算性与P=NP问题 - Computability P=NP
40. 课程总结 - Summary
学习指南