Data Structure.

Presentation on theme: "Data Structure."— Presentation transcript:

1 Data Structure

2 目錄 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

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

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

5 Char 0 JAVA programming

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

7 英打 一分鐘測試英打速度

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

9 靜宜賽碼場 – 註冊 註冊

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

11 靜宜賽碼場 – 註冊

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

13 靜宜賽碼場 – 註冊

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

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

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

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

18 練習 kb_practice_helloJava

19 JDK( Java SE Development Kits)
手機、嵌入式系統 大型網站開發 JAVA JAVA ME JAVA EE 1 JAVA SE (JDK) 一般應用程式適用

20 2 3 點選安裝

21 檢查是否有這選項

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

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

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

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

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

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

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

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

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

31 Scanner Method:

32 Scanner 導入此類別 宣告 使用

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

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

35 改寫成如下： 加入try、catch

36 練習 kb_inputOutput2

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

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

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

40 練習 kb_class2

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

42 練習 kb_class3

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

44 Example: stack 介面： 實作：

45 練習5 Interface-002

46 Char 1 Basic

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

48 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

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

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

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

52 Master theorem 遞迴式：

53 Recursive GCD(最大公因數)

54 Recursive Fibonacci number(費氏數列)

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

56 Recursive Hanoi Tower n個

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

58 練習 kb_gcd2

59 練習 kb_Fibonacci

60 練習 10511-test005

61 練習 kb_Recursive_HanoiTower

62 Char 2 Array

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

64 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 = ( j-1) => 14 = 2j => j=7 Step2: 代入column-major公式 目的位址 = 來源位址 + d( (目的行-來源行)*陣列列數 + (目的列-來源列) )

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

66 ArrayList 宣告： 物件type e.g.

67 ArrayList Method: e.g.

68 練習 kb_arrayList_add_v1

69 練習 kb_arrayList_add_v2

70 練習 kb_arrayList_AddRemove

71 練習 kb_arrayList_remove

72 練習 kb_gcd

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

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

75 練習 kb_findPrimes

76 練習 10511-test005

77 Char 3 Stack、Queue

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

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

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

81 Example

82 練習 kb_Stack_API

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

84 利用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

85 利用Array製作Stack

86 練習 kb_Stack_LinearArray

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

88 中序轉後序Alog.

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

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

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

92 Example – 後序計算 Given a postfix expression as followed
* % 1 + /

93 後序計算Alog

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

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

96 Example3 –計算後序式的值

97 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();

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

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

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

101 Example

102 練習 Queue-002

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

104 Alog - 僅用n-1格

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

106 Alog – 充份利用n格

107 利用linking list製作Queue

108 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

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

110 練習 kb_Queue_API1

111 練習 10421-test001

112 練習 kb_Queue_API2

113 練習 kb_findCompleteNum

114 練習 10511-test005

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

116 Char 4 Linking list

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

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

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

120 如何連結兩個nodes Header 10 20 NULL

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

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

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

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

125 練習 kb_Linkedlist_reverse

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

127 練習 kb_Linkedlist_API

128 Char 5 Tree

129 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

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

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

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

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

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

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

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

137 解答

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

139 BT traversal - Preorder

140 BT traversal - Inorder Inorder:

141 BT traversal - Postorder

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

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

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

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

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

147 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

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

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

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

151 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

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

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

154 Char 6 Graph

155 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

156 Char 7 Search、Sort

157 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)

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

159 Bubble sort Algo. 若有n筆data

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

161 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

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

163 練習 10521-test003 steps

164 練習 1053-test005

165 練習 1041test004(變化)

166 Char 8 Hashing

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

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

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

170 Char 9 Advanced tree

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