Data Structure

目錄 Char1、Basic Char2、Array Char3、Stack與Queue Char4、Linking List Algo 5個條件 Recursive 時間複雜度 Char2、Array Char3、Stack與Queue 使用、製作、應用 Char4、Linking List 製作Stack、Queue Char5、Tree BT、BST Char6、Graph 表達、traversal Char7、Search與Sort Internal search、external search Char8、Hashing Char9、Advanced Tree

配分 項目 備註 正課 20% 實習課 10% 平常表現 統一會考 70% 期中筆試15% 期中上機考20% 期中筆試15% 期中上機考20% 期末筆試15% 期末上機考20% 自學檢則(加分) [時間地點]： [計分方式]： 每題加0.5分，最高加到10分

教科書 書籍名稱：動畫圖解資料結構使用Java 書價 ： 定價 580元/本，團購價(79折) 460元/本

Char 0 JAVA programming

JAVA programming 寫程式的準則 輸入、輸出 例外控制 類別

英打 https://10fastfingers.com/typing-test/english 一分鐘測試英打速度

靜宜賽碼場 網頁版 沒辦法寫程式 用來加課程、看資訊 軟體版 可寫程式

靜宜賽碼場 – 註冊 註冊 http://coding.pu.arping.me/

靜宜賽碼場 – 註冊 輸入可收到信的email

靜宜賽碼場 – 註冊

靜宜賽碼場 – 註冊 填寫「學習家族組名」 Ex: 資工一A Ex: 資訊工程系 Ex: 中文姓名 Ex: 410616594

靜宜賽碼場 – 註冊

靜宜賽碼場 – 加選課程 登入「網頁版」賽碼場來加選課程 1 確定是否真的有登入成功 3 4 2

靜宜賽碼場 – 軟體版 路徑： 執行：

靜宜賽碼場 – 軟體版 6 1 3 4 2 5

靜宜賽碼場 – 軟體版 操作流程 選擇編譯器 開始寫程式 寫完程式後按自訂測資 確認local端執行結果正確 (尚未上傳到server) 確認server端執行結果正確(已上傳到server)

練習 kb_practice_helloJava

JDK( Java SE Development Kits) http://www.oracle.com/technetwork/java/javase/downloads/index.html 手機、嵌入式系統 大型網站開發 JAVA JAVA ME JAVA EE 1 JAVA SE (JDK) 一般應用程式適用

2 3 點選安裝

檢查是否有這選項

靜宜賽碼場 -評判伺服器訊息 Local端程式正確 (尚未通過server端驗證) 點選

靜宜賽碼場 -評判伺服器訊息 Server端程式正確 (已通過server端驗證且上傳) 當local端驗證無誤，則點選

靜宜賽碼場 -評判伺服器訊息 語法出錯

靜宜賽碼場 – 評判伺服器訊息 沒有輸出 (可能沒印出data)

靜宜賽碼場 – 評判伺服器訊息 輸出的格式有錯

靜宜賽碼場 – 評判伺服器訊息 執行時間超時 (可能你的程式進入無限迴圈)

寫程式的準則 程式碼要排版 有排版： 沒排版： 按tab鍵 來縮排

變數的命名 有效的變數： 1、開頭不能是數字 2、不可夾帶下列符號 「-」 「:」 e.g. e.g.

Scanner 宣告： 使用： 讀取一個字串： 讀取一行字串：

Scanner Method:

Scanner 導入此類別 宣告 使用

練習 kb_inputOutput1 輸入三個data， 第一個為int型態的data 第二個為double型態的data 第三個為String型態的data 使用scanner取得此三個data，並且 印出此三個data

try、catch Def: 讓你的程式在執行階段時更加穩固，不易crash 無法除以0，造成例外錯誤

改寫成如下： 加入try、catch

練習 kb_inputOutput2

class (類別) Def：藍圖 (or 模版) Jordan 11 鞋子模版 產生實體

class (類別) 架構： 皆可多個

Example 2個成員成員變數 2個成員建構子 2個methods

練習 kb_class2

如何在main class內建立一個method method須加上static

練習 kb_class3

Interface(介面) Def：僅宣告methods，不實作methods 建立： 實作： 介面名稱 (隨便命名) 僅宣告不實作 Note： 1、interface 不可直接new 2、interface 可繼承

Example: stack 介面： 實作：

練習5 Interface-002

Char 1 Basic

Algorithm(演算法) Algorithm須滿足的5個條件 Input Output (一定要有輸出) 明確性 有限性 有效性 明確性：不會有「應該」 有限性：有限的時間內 有效性：紙與筆就可以trace Note: 不一定要用程式語言來寫algo.

Time complexity 時間複雜度 (Time complexity) O(Big-Oh) Ω(Omega) Ө(theta) Note: The time taken by a program = compiler time + execution time The space needed by a program = instruction + data + stack

Time complexity In decreasing order 階層 指數 多項式 Hn (調和級數) =

Example Give a Big-Oh notation (1) (2) (3)

Example Ordering by asymptotic growth rate in ascending order Sol: 2^10 2^logn 3n+100logn 4nlogn+2n n^2+10n 2^n

Master theorem 遞迴式：

Recursive GCD(最大公因數)

Recursive Fibonacci number(費氏數列)

Recursive Ackermann’s function A(2,2) = ? A(2,1) = ? A(1,2) = ?

Recursive Hanoi Tower n個

1、n個盤子由A->C的總搬移次數? 2、B柱至少需多少空間才夠? n-1空間

練習 kb_gcd2

練習 kb_Fibonacci

練習 10511-test005

練習 kb_Recursive_HanoiTower

Char 2 Array

Array 二維陣列儲存在主記憶體中的方式： Row major Column major

Example A[1…j, 1…k]，each element two bytes， A[2,2] be stored at 898 Step1: 先決定row-major 或 column-major 為column-major A[1,3]=A[2,2]+d( (3-2)*j + (1-2) ) A[1,3]=A[2,2]+2( (3-2)*j + (1-2) ) => 910 = 898+ 2( j-1) => 14 = 2j => j=7 Step2: 代入column-major公式 目的位址 = 來源位址 + d( (目的行-來源行)*陣列列數 + (目的列-來源列) )

Tridiagonal matrix(三對角線矩陣) 只有對角線和上下兩線有值 其它都是0 ANS: 13 How many non-zero elements in a 5X5 Tri-diagonal matrix ?

ArrayList 宣告： 物件type e.g.

ArrayList Method: e.g.

練習 kb_arrayList_add_v1

練習 kb_arrayList_add_v2

練習 kb_arrayList_AddRemove

練習 kb_arrayList_remove

練習 kb_gcd

練習 kb_primeFactorization 質因數分解：將一個正整數寫成幾個因數的乘積 (除了1以外)

練習 kb_findCompleteNum 完全數：所有的因子的和恰好等於它本身 (除了自身以外的因數) e.g. 6，它有因數1、2、3、6，除去它本身6外，1+2+3＝6

練習 kb_findPrimes

練習 10511-test005

Char 3 Stack、Queue

Stack Stack Def 製作 應用 利用Array製作Stack 利用Linking list製作Stack Prefix、Infix、Postfix

Stack Def：一個容器，依先進後出(FILO)方式儲放data 使用：

JAVA API - Stack<E> 宣告： 方法：

Example

練習 kb_Stack_API

Example – Stack的操作 若Stack空間大小為3，依序執行下列operations，則最後Stack的內容為何? push 1 push 2 push 3 push 4 pop pop push 5 push 6 push 7 pop pop

利用Array製作Stack 實作三個操作： 1、push：放data進去 4 3 2 1、判斷是否已滿 2、pop：取data出來 1 3、empty：判斷stack是否為空 4 3 2 1 -1 1、判斷是否已滿 2、top+1 3、存入data 1、判斷是否為空 2、取出data 3、top-1 top 判斷top是否為-1

利用Array製作Stack

練習 kb_Stack_LinearArray

Example – 中序轉後序、前序 Ex1：中序式： 求Postfix、Prefix ? Ex2：中序式： EX1: Postfix: ABC*+DE/- Prefix: -+A*BC/DE EX2: Pre: =x=y-+-*abc+a/bcd

中序轉後序Alog.

中序轉後序Alog 原則： 在stack內大優先權的data須在小優先權的data上面 「(」在stack外具最大優先權， 遇到「)」則pop且print直至「(」 遇到「(」則push 遇到「運算子」則比較優先權

Example 寫出A+B*(C-D)中序轉換後序過程 (含stack內容)

Example – 後序轉中序 後序式： 求Infix ? Postfix: ABC*+DE/- Prefix: -+A*BC/DE

Example – 後序計算 Given a postfix expression as followed 20 5 3 + 6 * 8 3 - % 1 + /

後序計算Alog

Example1 – 托號配對 kb_Stack_() [想法] 一、1、看到左括號就push 2、看到右括號就pop (1) 若Stack不空則pop (2) 若Stack為空則印出「不合法配對」並離開程式 3、看到非左右括號就印出「非合法字元」並離開程式 二、檢查Stack是否為空，為空印出「合法配對」、不空印出「不合法配對」

Example2 – 托號配對 kb_Stack_ParenthesisMatching [想法] 1、看到左括號就push左括號位置 2、看到右括號就pop (1) 若Stack不空則pop來取得左括號位置 (2) 若Stack為空則指定-1為左括號位置 印出左括號位置、右括號位置

Example3 –計算後序式的值

Queue Def 製作 使用 應用 利用Array製作Queue 利用Linking list製作Queue JAVA Queue API [法一] linear array [法二] Circular array 用n-1格空間 用n格空間 利用Linking list製作Queue [法一] single linking list [法二] Circular linking list 使用 JAVA Queue API 建立 加入 刪除 應用 排隊理論、BFS ：Queue<String> q = new LinkedList<String>(); ：q.offer(item); ：q.poll();

Queue Def：先進先出 (FIFO) 使用： 取data (從前端) 加data (從後端)

Example – Queue的操作 若Queue空間大小為3，依序執行下列operations，則最後Queue的內容為何? Add 1 Add 2 Add 3 Add 4 Delete Delete Delete Add 6 Add 7 Delete Delete

JAVA API - Queue<E> 宣告： 方法： LinkedList不會有滿的問題，所以不須檢查是否為滿 Queue is an interface，所以不能寫成如下

Example

練習 Queue-002

利用Circular array製作Queue (僅用n-1格) Front與Rear在的那格不存data

Alog - 僅用n-1格

利用Circular array製作Queue (充份利用n格)

Alog – 充份利用n格

利用linking list製作Queue

Add() Step1： 建立一個node t Step2： 將t加入queue 1、front=t ; 10 NULL Step2： 將t加入queue Case1：若queue為空 Case2：若queue為不為空 t 10 NULL 10 20 NULL front rear front rear 1、front=t ; 2、rear = t ; 10 1、 rear.next = t ; 2、 rear = t ; NULL rear t

Delete() Case1：若queue為空 不做操作，回傳-1 Case1：若queue不為空 1、t = front ; 10 20 NULL t front rear front 1、t = front ; 2、front = t.next;

練習 kb_Queue_API1

練習 10421-test001

練習 kb_Queue_API2

練習 kb_findCompleteNum

練習 10511-test005

期末考考試範圍 第五章 鍊節串列 (Ch. 5-1~ Ch. 5-9) 第六章 樹狀結構 (Ch. 6-1~ Ch. 6-6) 第七章 圖形結構 (不列入期末考試範圍) 第八章 排序       (Ch. 8-1~ Ch. 8-5) 第九章 搜尋       (不列入期末考試範圍)

Char 4 Linking list

Array VS LinkedList Array LinkedList 支援Random、Sequential access Insert or Delete麻煩 O(n) Insert or Delete容易 O(1) 無法動態增刪空間 可動態增刪空間 佔用連續mem空間 可不佔用連續mem空間

Linking list Def：由多個node組成，每個node至少包含 一個link欄位來指向其它node Node結構： EX： Data Link Header 10 -1 42 NULL

Linking list的node製作 C語言：用structure JAVA：用class

如何連結兩個nodes Header 10 20 NULL

如何插入一個node Header 10 20 NULL n1 30 t

如何刪除一個node Header 10 30 20 NULL n1 t 不需做刪除的動作，java會自動回收垃圾

Reverse single linking list Header 10 -1 42 NULL reverse NULL 42 -1 10 Header

Alog - Reverse single linking list 10 -1 42 NULL r q p

練習 kb_Linkedlist_reverse

JAVA API - LinkedList 刪除節點 加入節點 插入節點 連結 Note: index從1開始

練習 kb_Linkedlist_API

Char 5 Tree

Tree Binary tree (二元樹，BT) 種類 Traversal 依外型 Skewed BT Full BT Complete BT Strict BT 依應用 Heap 建立 Top-down Buttom-up 加入 刪除 Binary search tree 建立、加入、刪除 Traversal Preorder Inorder Postorder

Binary Tree 特性： 1、deg(v) 2 2、height從1開始 3、第i level的full binary tee節點數 = 4、高h的full binary tee總節點數 =

BT的種類 Skewed BT Full BT Complete BT Strict BT

內部節點、外部節點 [分析] 若degree為0則為外部節點，否則為內部節點 1、內部節點：8、3、10、6、14 2、外部節點：1、4、7、13

兩種建立tree的方式 一、Array 二、Linked list

用陣列建立tree [分析] 如何決定陣列空間大小? 若tree高為3，所以建立一個空間大小為 的陣列 8 3 10 1 6 14 [分析] 如何決定陣列空間大小? 若tree高為3，所以建立一個空間大小為 的陣列 8 3 10 1 6 14 為何第0格不放data? 0 1 2 3 4 5 6 7

用陣列建立tree [分析] 如何判斷此節點為內部 or 外部節點 內部節點 8 3 10 1 6 14 0 1 2 3 4 5 6 7

練習 kb_Tree_CreateCompleteBT Array size=4 Index 0不存data 1個內部節點 2個外部節點

解答

BT traversal Preorder (前序) 中左右 Inorder (中序) 左中右 Postorder (後序) 左右中

BT traversal - Preorder

BT traversal - Inorder Inorder: 1 3 4 6 7 8 10 13 14

BT traversal - Postorder

練習 10512-test003 二元樹的拜訪 Binary Tree Traversal

解答 Steps: 1、建立一個array並將input data存入 2、建立三個methods，前、中、後序並執行

給order建BT 給中序、前序 or 中序、後序可決定唯一BT 給前序、後序無法建立唯一BT

給中序、前序建BT Preorder：ABCDEFGHI Inorder ：BCAEDGIHF Sol：

給運算式建BT 運算式： A+B*C-D/E 1、以BT表示 2、寫出Preorder、Postorder Sol： 1、 2、Preorder： -+A*BC/DE Postorder： ABC*+DE/-

Example 若complete BT的nodes值為a,b,c,d,e,f,g,h,I,j,k 已知postorder為d e b h I f j k g c a， 畫出此BT

Heap (堆積) Def 種類 Min-heap Max-heap 操作 建立 新增 刪除

Heap (堆積) 可分成min-Heap、max-Heap Def：為一個complete BT，可為空，若不為空， (1) root具最大鍵值 (2) all父點鍵值≥ 子點鍵值 e.g. max-Heap

如何建立Heap 法一：Top-down 法二：bottom-up 邊insert邊調整成heap 1、先建好complete binary tree 2、再調整成heap

Example - Heap 三、Insert 20 、40、80 給予資料： 26、5、77、1、61、11、59、15、48、19 一、建立max-Heap using Top-Down manner using Bottom-up manner 二、Delete max 三、Insert 20 、40、80

Binary Search Tree (BST) Def：為一個二元樹，可為空，若不空則 1、左子樹all node鍵值 < root 2、右子樹all node鍵值 > root e.g.

Example - BST 7、2、9、0、5、6、8、1 (1) 建BST (2) delete 7 、delete 2

Char 6 Graph

Graph Graph 圖的表示方式 圖的搜尋方法 Spanning Tree Shortest path problem Adjacency matrix Adjacency list 圖的搜尋方法 DFS、BFS Spanning Tree Min Spanning tree Kruskal’s algo. (邊) Prime’s algo. (點) Sollin’s algo. (樹) Shortest path problem Dijkstra algo

Char 7 Search、Sort

Search、Sort Search Sort Linear search Binary search Internal sort Comparison & swap技巧 Insertion sort Selection sort Bubble sort Shell sort Quick sort Heap sort Distribution & merge技巧 Radix sort External sort Merge sort B tree Selection tree Avg time = O(n) Avg time = O(nlogn)

Bubble sort(氣泡排序) Data： 26、5、77、19、2 Step1：26、5、77、19、2 5、26、19、2、77 swap

Bubble sort Algo. 若有n筆data

Insertion sort(插入排序) Data： 26、5、77、19、2 Step1：26、5、77、19、2 5、26、77、19、2 Step2：5、26、77、19、2 5、26、77、19、2 Step3： 5、26、77、19、2 5、 19、 26、77、2 Step4： 5、 19、 26、77、2 2、5、26、77、19 往前比

Selection sort(選擇排序) Data： 26、5、77、19、2 Step1：2、5、77、19、26 往後比 Data： 26、5、77、19、2 Step1：2、5、77、19、26 Step2：2、5、77、19、26 Step3：2、5、19、77、26 Step4：2、5、19、26、77

Quick sort Data： 26、5、77、19、2 Step1：26、5、77、19、2 [19、5、2]、26、[77] j 找≥𝑝𝑘 找≦𝑝𝑘 PK

練習 10521-test003 steps

練習 1053-test005

練習 1041test004(變化)

Char 8 Hashing

Hashing Def: 一種data儲存、搜尋的機制，存取data時須先 經過hashing function算出hashing address，再 依此位址至hashing table中存取 e.g. 同一個位址發生collision 滿的時候發生overflow (當3個slots已滿又想放時)

Overflow常見的處理方式 1、linear probing 2、quadratic probing 3、chain 4、double hashing 5、rehashing

Hashing的優點 1、data search前不須先經過排序 2、可做保密

Char 9 Advanced tree

Advanced tree Advanced tree Min-max heap Deap Extended binary tree Huffman algo. B tree of order m