資料結構

Data Structures

學期

113-2

學分

0 學分

當期課號

517502

永久課號

MGIF10008

開課單位

資訊管理與財務金融系

授課教師

徐熊健

校區

光復

類別

必修

上課時間表

節	週一
9 17:30–18:20	資料結構 M101（光復） 3 節連堂
A 18:30–19:20
B 19:30–20:20

* 根據陽明交大上課時間表所列

概述

This course is aimed at preparing the students with basic computing theory, representation schemes and solution methods through programming practice and implementation.

先修科目

Basic computer programming skills

備註

無備註

教學方式

https://sites.google.com/view/sjshyudsimf FB: ds113_imf_nycu

評分方式

35% Programming assignments 25% Midterm 25% Final 15% In-class participation

課程大綱

Introduction

講授：

3
Arrays

Arrays, Memory allocations, 1D, 2D, 3D arrays, Structures and Pointers

講授：

6
Programming tool introduction

示範：

3
Stack

Definition, behavior, implementations and applications of Stacks

講授：

3
Queue

Definition, behavior, implementations and applications of Queues

講授：

3
Linked Lists

Singly linked lists and Chains, Insertion/deletion/search in linked lists, Linked stack/queue, Doubly linked lists

講授：

6
Tree

Definition, behavior, implementations and applications of Trees, Heap, Binary search trees, Balanced binary search tree, AVL trees

講授：

9
Midterm Exam.

其他：

3

備註：Exam.
Graphs

Definition, behavior, implementations and applications of Graphs, DFS/BFS, Minimum cost spanning trees, Shortest paths, Transitive Closure, AOV networks

講授：

9
Sorting

Selection/Bubble/Insertion/Quick/Merge/Heap sorts, How fast can we sort

講授：

3
Final Exam.

其他：

3

備註：Exam.

週次計畫

週次	主題
第 1 週	Introduction/Prerequisite Definitions of Data Structures and Algorithms, Flow chart of programming, Selection sort. Please join the FB club: ds113_imf_nycu to receive the timely news. 2025-02-17(一) 時數：[2025-02-17]徐熊健(3.00)
第 2 週	Performance evaluation Simplifying functions Performance analysis: Big-O Recursion 2025-02-24(一) 時數：[2025-02-24]徐熊健(3.00)
第 3 週	Performance analysis: Omega and Theta Optimal algorithms: defition and examples Passed by value, address Simple array operations: transpose, addition, multiplication 2025-03-03(一) 時數：[2025-03-03]徐熊健(3.00)
第 4 週	Magic squares Knight tours Addressing in 1/2/3-d arrays 2025-03-10(一) 時數：[2025-03-10]徐熊健(3.00)
第 5 週	Addressing in k-d arrays Stack: Concept, stack frame, array implementation, push/pop Balanced parentheses Rat in a maze: data structures 2025-03-17(一) 時數：[2025-03-17]徐熊健(3.00)
第 6 週	Rat in a maze: algorithm (try and error) Program demonstration Genarate Maze randomly Arithmetic expressions: infix/postfix/prefix Transformation from infix to postfix: Examples 2025-03-24(一) 時數：[2025-03-24]徐熊健(3.00)
第 7 週	Transformation from infix to postfix/prefix Transformation from postfix to prefix Transformation from prefix to postfix struct node 2025-03-31(一) 時數：[2025-03-31]徐熊健(3.00)
第 8 週	Linked lists Insertion, deletion, search in singly linked list Linked stack, linked queue Conctenating two linked lists Inverting linked list Circular lists Circular linked lists with header nodes Polynomial addition using linked lists 2025-04-07(一) 時數：[2025-04-07]徐熊健(3.00)
第 9 週	Doubly linked list Doubly/circular linked list with header node Sparse matrix Trees: definition and terminologies Generalized list for trees Left-child-right-sibling Binary trees 2025-04-14(一) 時數：[2025-04-14]徐熊健(3.00)
第 10 週	Midterm Exam 2025-04-21(一) 時數：[2025-04-21]徐熊健(1.00)
第 11 週	Binary trees: full, complete, formal, skew Inorder/postorder/preorder traversal Binary search tree: insertion BST+inorder-traversal ==> sorted sequence 2025-04-28(一) 時數：[2025-04-28]徐熊健(3.00)
第 12 週	Binary search tree: Deletion Non-recursive search in BST Non-recursive traversal: inorder/preorder/postorder Level-order traversal Copy/Equality/Counting nodes of binary trees Determine a binary tree by (infix, prefix) 2025-05-05(一) 時數：[2025-05-05]徐熊健(3.00)
第 13 週	Determine a binary tree by (infix, postfix) AVL tree: insertion/deletion Height of AVL tree: O(logn) Properties of trees/binary trees Heap_motivation 2025-05-12(一) 時數：[2025-05-12]徐熊健(3.00)
第 14 週	Heap_insertion/deletion/sort Graph: terminologies Shortest path: Single source all destination/Dijkstra algorithm 2025-05-19(一) 時數：[2025-05-19]徐熊健(3.00)
第 15 週	Transitive Closure Minimum cost spanning trees AOV networks 2025-05-26(一) 時數：[2025-05-26]徐熊健(3.00)
第 16 週	Sorting I: Insertion/Quick sort, How fast can we sort; Sorting II: Merge/Heap sort, List/Table sort 2025-06-02(一) 時數：[2025-06-02]徐熊健(3.00)
第 17 週	Final Exam 2025-06-09(一) 時數：[2025-06-09]徐熊健(1.00)

教科書

E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd Edition), Silicon Press, 2008, NJ. 徐熊健,資料結構與演算法,第五版,高立圖書512326,ISBN: 978-986-378-425-8

Office Hours

地點: AB101
時間: GH, Monday
聯絡方式: sjshyu@gmail.com sjshyu@nycu.edu.tw