課程名稱 |
(中文) 資料結構 (英文) Data Structures |
開課單位 | 電機工程學系 | ||
課程代碼 | E3510 | ||||
授課教師 | 鄭嘉慶 | ||||
學分數 | 3.0 | 必/選修 | 選修 | 開課年級 | 大三 |
先修科目或先備能力:計算機概論 | |||||
課程概述與目標:This course introduces the basic concepts of data structures. We will use C++ as the vehicle to study various data structures, including arrays, stacks, queues, linked list, trees, and graphs. Review of Basic C Programming, Basic Concepts, Arrays and Structures, Stacks and Queues, Lists, Trees, Graphs, Sorting, Hashing, Heap Structures, and Search Structures | |||||
教科書 | Data Structures & Algorithm Analysis in C++, 4th Edition, Mark A. Weiss, Addison Wesley, 2013 | ||||
參考教材 | C++ How to Program, 8th edition, Paul Deitel & Harvey Deitel, Pearson, 2012. |
課程大綱 | 學生學習目標 | 單元學習活動 | 學習成效評量 | 備註 | ||
週 | 單元主題 | 內容綱要 | ||||
1 | Course Overview | Introduction. Course Overview. | knowing the concepts of data structures. |
|
||
2 | Review of C++ Programming | Flow control, Functions | Practice the flow control of C++ language |
|
|
|
3 | Review of C++ Programming (continued) | Advanced C++ Features | Practice the usage of array, structure, and pointer |
|
||
4 | Algorithm Analysis | Mathematical basckground Model Running-Time |
Knowing the concepts of algorithm analysis |
|
||
5 | Algorithm Analysis (continued) | Mathematical basckground Model Running-Time |
Knowing the concepts of algorithm analysis |
|
|
|
6 | Arrays and Lists (continued) | Polynomials Sparse matrices Strings |
Using C++ to implement polynomials and sparse matrix |
|
|
|
7 | Stacks and Queues | Stacks Stack using dynamic array |
Knowing the structure of stack Using C++ language to implement stacks |
|
||
8 | Midterm Examination | chapter 0 - chapter3 | Review Chapter 0 - chapter 3 |
|
||
9 | Stacks and Queues (continued) | Queues Circular queues using dynamic arrays |
Knowing the structure of Queue Using C++ language to implement queue |
|
||
10 | Trees | Introduction of trees Binary Trees |
Knowing the structure of trees Using C++ language to implement binary tree |
|
||
11 | Trees (continued) | Balanced search trees Multi-way Search Trees |
Knowing the concepts of balanced search trees and multi-way Search Trees |
|
||
12 | Heaps | Heaps | Knowing the concepts of Heaps |
|
|
|
13 | Hashing | Hash function Hash tables |
Knowing the concepts of hashing |
|
|
|
14 | Sorting | Insertion sort, heapsort, mergesort, quicksort ... Lower bound analysis |
Knowing the concepts of sorting and a variety of sorting algorithms |
|
||
15 | Sorting (continued) | Insertion sort, heapsort, mergesort, quicksort ... A general lower bound analysis |
Knowing the concepts of sorting and a variety of sorting algorithms |
|
|
|
16 | Graphs | The Graph Abstract Data Type Elementary Graph Operations |
Knowing the graph structure and elementary graph operations |
|
||
17 | Final Examination | Chapter 4 - chapter 6 | Review chapter 4 - chapter 6 |
|
教學要點概述: |