Data Structure

本課程將對計算機科學中常使用到的資料結構做一個完整的介紹。並分析各個ADT的操作與演算法的 時間與空間複雜度。本課程使用C++程式語言實作。

• 賴旭昭
• 李元凱

Lecture	Content	Reading
1	Introduction, Review of C++, Sorting	Section 7.2
2	Algorithmic Complexity (Insertion Sort)	Section 1.7.
3	Experimental Performance Measurement.	Section 1.7.
4	Abstract Data Types.	Sections 1.3 and 2.1.
5	Sparse Matrices.	Section 2.4.
6	Arrays.	Section 2.5.
6.5	Templates in C++	Section
7	Stacks.	Section 3.6.
8	Stacks.	Section 3.2.
9	Queues.	Section 3.3.
9.5	Evaluation of Expressions	Section 3.6.
10	Linked Lists.	Sections 4.1 and 4.2.
11	The Template Class Chain.	Section 4.3.
12	Iterators and Chain Variants.	Sections 4.3, 4.4, 4.10.
13	Trees.	Section 5.1.
14	Binary Trees.	Section 5.2.
15	Binary Tree Traversals.	Section 5.3.
16	Priority Queues.	Sections 5.6 and 7.6.
17	Max Heaps and Leftist Trees	Sections 5.6 and 9.2.
18	Binary Search Trees.	Section 5.7.
19	Selection Trees.	Section 5.8.
20	Disjoint Sets	Section 5.10.
21	Graphs.	Section 6.1.
22	Graph Search Methods.	Section 6.2.
23	Min Cost Spanning Trees.	Section 6.3.
24	Shortest Path Problems (Dijkstra).	Section 6.4.1.
25	Shortest Paths (Bellman Ford).	Section 6.4.2.
26	All Pairs Shortest Paths.	Section 6.4.3
27	Sorting.	Sections 7.3 and 7.5
28	External Sorting.	Section 7.10.
29	External Sorting.	Section 7.10.
30	External Sorting.	Section 7.10.
31	External Sorting (Run Merging, Huffman Codes).	Section 7.10.
32	Hash Tables.	Sections 8.2.1 and 8.2.2.
33	Hash Tables.	Sections 8.2.4 and 8.2.5
34	Bloom Filters.	Section 8.4
35	Amortized Complexity.	Section 9.3.1.
36	Binomial Heaps.	Section 9.3.
37	Binomial Heaps (analysis).	Section 9.3.6.
38	Fibonacci Heaps.	Section 9.4.
39	Fibonacci Heaps (analysis) .	iSection 9.4.5
40	Pairing Heaps.	Section 9.5
41	Interval Heaps.	Section 9.7
42	Static Dictionaries.	Section 10.1
43	Dynamic Dictionaries (AVL Trees).	Section 10.2
44	Red Black Trees.	Section 10.3
45	Red Black Trees.	Section 10.3
46	Splay Trees.	Section 10.4
47	Splay Trees (analysis).	Section 10.4
48	B Trees.	Section 11.2
49	B Trees (continued).	Section 11.2
50	B+ Trees.	Section 11.3
51	Digital Search Trees and Binary Tries.	Section 12.1
52	Binary Tries and Compressed Binary Tries .	Section 12.2
53	Patricia.	Section 12.2.3
54	Higher Order Tries.	Section 12.3
55	Router/Classifier/Firewall Tables.	Section 12.5
56	Suffix Trees.	Section 12.4

• 網際網路簡介
• 大學校園網站法律案例教材