教學大綱與進度

課程基本資料：

學年期	課號	課程名稱	階段	學分	時數	修	教師	班級	人	撤	備註
112-2	327651	資料結構	1	3.0	3	★	古瓊昇	電機一丙	55	0	計中電腦教室

教學大綱與進度：

教師姓名	古瓊昇　教師諮商時間(Office Hours)
Email	johnsonku@ntut.edu.tw
最後更新時間	2024-06-12 12:28:19
課程大綱	本課程主要針對以下內容進行說明,包含數據結構的基礎概念：陣列（array）、鏈結串列（linked list）、堆疊（stack）、佇列（queue）、樹（tree）、圖（graph）等。並清楚解釋數據結構的運作原理：陣列的插入、刪除、查找、排序等操作；鏈結串列的插入、刪除、查找等操作；堆疊的推入、彈出、查詢等操作；佇列的加入、刪除、查找等操作。講述演算法：排序演算法（如：快速排序、插入排序、選擇排序等）、搜尋演算法（如：二分搜尋、哈希搜尋等）。 表明數據結構應用：數據結構在資料庫、檔案系統、圖形處理等方面的應用。並且搭配實作：實作陣列、鏈結串列、堆疊、佇列、樹、圖等數據結構，並利用C++語言進行演示。 I. Introduction to Data Structures Definition of data structures Types of data structures (arrays, linked lists, trees, graphs, etc.) Algorithm analysis and time complexity II. Arrays and Lists One-dimensional and multi-dimensional arrays Dynamic arrays and resizing Linked lists and their implementation III. Stacks and Queues Definition and implementation of stacks Definition and implementation of queues Applications of stacks and queues IV. Trees Definition and properties of trees Binary trees and binary search trees Tree traversal algorithms (in-order, pre-order, post-order) V. Hash Tables Definition and implementation of hash tables Hash functions and collision resolution Applications of hash tables VI. Graphs Definition and representation of graphs Graph traversal algorithms (DFS, BFS) Shortest path algorithms (Dijkstra’s, Bellman-Ford) VII. Sorting Algorithms Definition and implementation of sorting algorithms (Bubble sort, Insertion sort, Quick sort, Merge sort, etc.) Comparison of sorting algorithms VIII. Advanced Data Structures Heaps and priority queues Tries Bloom filters IX. Conclusion Recap of key concepts and data structures Discussion of real-world applications of data structures Preparing for a career in data structures and algorithms.
課程進度	第一週 Chapter 1 C++ Primer : 1.1 Basic C++ Programming Elements 1.2 Expressions 1.3 ControlFlow 1.4 Functions 1.5 Classes 1.6 C++ Program and File Organization 1.7 WritingaC++Program 第二週 Chapter 2 Object-Oriented Design : 2.1 Goals,Principles,and Patterns 2.2 Inheritance and Polymorphism 2.3 Templates 2.4 Exceptions 第三週Chapter 3 Arrays, Linked Lists, and Recursion : 3.1 UsingArrays 3.2 Singly Linked Lists 3.3 Doubly Linked Lists 3.4 Circularly Linked Lists and List Reversal 3.5 Recursion 第四週 Chapter 4 Analysis Tools : 4.1 TheSeven Functions Used in This Book 4.2 Analysis of Algorithms 4.3 Simple Justification Techniques 第五週 Chapter 5 Stacks, Queues, and Deques: 5.1 Stacks 5.2 Queues 第六週 Chapter 5 Stacks, Queues, and Deques: 5.3 Double-Ended Queue 第七週Chapter 6 List and Iterator ADTs: 6.1 Vectors 6.2 Lists 第八週Chapter 6 List and Iterator ADTs: 6.3 Sequences 6.4 Case Study: Bubble-Sort on a Sequence 第九週 期中考 第十週Chapter 7 Trees: 7.1 General Trees 7.2 Tree Traversal Algorithms 第十一週 Chapter 7 Trees: 7.3 Binary Trees 第十二週Chapter 8 Heaps and Priority Queues: 8.1 The Priority Queue Abstract Data Type 8.2 Implementinga Priority Queue with a List 8.3 Heaps 8.4 Adaptable Priority Queues 第十三週Chapter 9 Hash Tables, Maps, and Skip Lists 9.1 Maps 9.2 Hash Tables 9.3 Ordered Maps 第十四週Chapter 9 Spread Spectrum Signals for Digital Communications 9.4 Skip Lists 9.5 Dictionaries 第十五週Chapter 10 Search Trees: 10.1 Binary Search Trees 10.2 AVL Trees 10.3 Splay Trees 10.4 (2,4) Trees 10.5 Red-Black Trees 第十六週Chapter 11 Sorting, Sets, and Selection: 11.1 Merge-Sort 11.2 Quick-Sort 11.3 Studying Sorting through an Algorithmic Lens 11.4 Sets and Union/Find Structures 11.5 Selection 第十七週Chapter 12 Strings and Dynamic Programming & Chapter 13 Graph Algorithms 第十八週 期末考
評量方式與標準	期中考 30% 期末報告 30% 平時作業 40%
使用教材、參考書目或其他	【遵守智慧財產權觀念，請使用正版教科書，不得使用非法影印教科書】 使用外文原文書：是 Michael T. Goodrich, Roberto Tamassia, David M. Mount, "Data Structures and Algorithms in C++ 2/e", John Wiley, 2011
課程諮詢管道	Office hour or making an appointment by email
課程對應SDGs指標
備註	6/12 課程聯結：https://meet.google.com/vvy-hkny-jnq