資料結構
Data Structure
學期
114-1
學分
3
學分
當期課號
910379
永久課號
SESE10137
開課單位
系統工程與科技學士學位學程
授課教師
莊曜嘉
類別
必修
上課時間表
| 節 | 週二 | 週四 |
|---|---|---|
1 08:00–08:50 | 資料結構 | |
3 10:10–11:00 | 資料結構 2 節連堂 | |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
概述
本課程旨在介紹電腦科學中資料結構的核心概念與其在C++程式語言中的實現方式。課程內容將從基礎的資料型態與抽象資料型態(ADT)開始,逐步深入探討陣列、堆疊、佇列、鏈結串列、樹狀結構、圖形等重要資料結構。此外,課程也會涵蓋各種排序與搜尋演算法的分析與應用。課程目標是讓學生能夠: 1.理解不同資料結構的特性與適用場景。 2.具備使用C++設計與實作各種資料結構的能力。 3.學習分析演算法的時間與空間複雜度,並能選擇最適合的演算法來解決問題。 4.培養良好的程式設計風格與解決問題的能力。
先修科目
C或C++城市語言能力
教學方式
教學方法: 以教師課堂講授為主,搭配投影片、程式碼範例與實際演練。 課程網站: 所有課程公告、講義、作業繳交及補充資料均會發布於學校的數位學習平台。
評分方式
Midterm: 25% Final: 35% Quiz: 10% Group Report: 20% Class status: 10%
課程大綱
- 線性資料結構
- 樹狀結構
- 圖形
- 排序與搜尋
- 雜湊(Hashing)
- 基礎概念
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | 課程簡介: 課程目標、評分標準、C++複習 |
| 第 1 週 | 課程簡介: 課程目標、評分標準、C++複習 |
| 第 2 週 | 演算法分析: 時間與空間複雜度、Big-O表示法 |
| 第 2 週 | 演算法分析: 時間與空間複雜度、Big-O表示法 |
| 第 3 週 | 陣列與結構: 一維與二維陣列、結構與類別 |
| 第 3 週 | 陣列與結構: 一維與二維陣列、結構與類別 |
| 第 4 週 | 堆疊(Stack): 堆疊的ADT、陣列與鏈結串列實作 |
| 第 4 週 | 堆疊(Stack): 堆疊的ADT、陣列與鏈結串列實作 |
| 第 5 週 | 佇列(Queue): 佇列的ADT、線性與環狀佇列 |
| 第 5 週 | 佇列(Queue): 佇列的ADT、線性與環狀佇列 |
| 第 6 週 | 鏈結串列(Linked List): 單向與雙向鏈結串列、環狀鏈結串列 |
| 第 6 週 | 鏈結串列(Linked List): 單向與雙向鏈結串列、環狀鏈結串列 |
| 第 7 週 | 樹(Tree)的基本概念: 樹的定義、術語、二元樹 |
| 第 7 週 | 樹(Tree)的基本概念: 樹的定義、術語、二元樹 |
| 第 8 週 | 二元樹的走訪: 前序、中序、後序走訪 |
| 第 8 週 | 二元樹的走訪: 前序、中序、後序走訪 |
| 第 9 週 | 二元搜尋樹(BST): 搜尋、插入、刪除操作 |
| 第 9 週 | 二元搜尋樹(BST): 搜尋、插入、刪除操作 |
| 第 10 週 | 期中考試 |
| 第 10 週 | 期中考試 |
| 第 11 週 | 圖形(Graph)的基本概念: 圖的定義、表示法(鄰接矩陣、鄰接串列) |
| 第 11 週 | 圖形(Graph)的基本概念: 圖的定義、表示法(鄰接矩陣、鄰接串列) |
| 第 12 週 | 圖形的走訪: 深度優先搜尋(DFS)、廣度優先搜尋(BFS) 2 |
| 第 12 週 | 圖形的走訪: 深度優先搜尋(DFS)、廣度優先搜尋(BFS) 2 |
| 第 13 週 | 排序(Sorting)I: 氣泡排序、選擇排序、插入排序 |
| 第 13 週 | 排序(Sorting)I: 氣泡排序、選擇排序、插入排序 |
| 第 14 週 | 排序(Sorting)II: 快速排序、合併排序 |
| 第 14 週 | 排序(Sorting)II: 快速排序、合併排序 |
| 第 15 週 | 搜尋(Searching): 循序搜尋、二元搜尋 |
| 第 15 週 | 搜尋(Searching): 循序搜尋、二元搜尋 |
| 第 16 週 | 期末總複習與總結 |
| 第 16 週 | 期末總複習與總結 |
教科書
書名: Fundamentals of Data Structures in C++, 2/e 作者: Ellis Horowitz, Sartaj Sahni, Dinesh Mehta 出版者: Silicon Press 出版年: 2006