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、internal sort與external search Char8、Hashing Char9、Advanced Tree

3 Char 0 JAVA programing

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

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

6 Scanner 宣告： 使用：

7 Scanner Method:

8 Scanner

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

10 try、catch Def: 讓你的程式在執行階段時更加穩固，不易crash

11 練習 kb_inputOutput2

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

13 class (類別) 架構： e.g. 皆可多個 2個成員成員變數 1個成員建構子 2個methods

14 練習 kb_class2

15 如何在main class內建立一個method

16 練習 kb_class3

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

18 Example: stack 介面： 實作：

19 練習5 Interface-002

20 Char 1 Basic

21 Basic – Algorithm(演算法)
Input Output (一定要有輸出) 明確性 有限性 有效性 Note: 不一定要用程式語言來寫algo.

22 Basic – 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

23 Example – Time complexity
法一：代入法 法二：master theorem EX3：Give a Big-Oh notation

24 Master theorem 遞迴式：

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

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

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

28 Recursive Fibonacci number(費氏數列)

29 練習 kb_Fibonacci

30 練習 10511-test005

31 Recursive Hanoi Tower 1、搬移次數： T(n) = 2T(n-1) + 1 2、B柱至少需n-1空間

32 練習 kb_Recursive_HanoiTower

33 Char 2 Array

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

35 Example - Array A[1…j, 1…k]，each element two bytes，
A[2,2] be stored at 898 A[1,3] be stored at 910 求 j = ? Sol: Step1: 先決定row-major 或 column-major Step2: 代入公式 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 目的位址 來源位址 目的行-來源行 目的列-來源列

36 Example – Tridiagonal matrix(三對角線矩陣)
ANS: 13 How many non-zero elements in a 5X5 Tri-diagonal matrix ?

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

38 ArrayList Method: e.g.

39 練習 kb_arrayList_add_v1

40 練習 kb_arrayList_add_v2

41 練習 kb_arrayList_remove

42 練習 kb_arrayList_AddRemove

43 練習 kb_primeFactorization

44 練習 kb_findCompleteNum

45 練習 kb_findPrimes

46 練習 kb_gcd

47 練習 10511-test005

48 Char 3 Stack、Queue

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

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

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

52 Example

53 練習 kb_Stack_API

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

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

56 利用Array製作Stack

57 練習 kb_Stack_LinearArray

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

59 中序轉後序Alog.

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

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

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

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

64 後序計算Alog

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

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

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

68 Queue Def：先進先出 (FIFO) 使用：

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

70 JAVA API for Queue 建立Queue 操作Queue 加入：offer() 取得並移除：poll()
取得不移除：peek()

71 利用Linear Array製作Queue

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

73 Alog - 僅用n-1格

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

75 Alog – 充份利用n格

76 利用linking list製作Queue

77 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

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

79 Char 4 Linking list

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

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

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

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

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

85 如何刪除一個node Header 10 30 20 NULL n t

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

87 Alog - Reverse single linking list

88 Char 5 Tree

89 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

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

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

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

93 BT traversal - Preorder

94 BT traversal - Inorder Inorder:

95 BT traversal - Postorder

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

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

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

99 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

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

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

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

103 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

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

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

106 Char 6 Graph

107 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

108 Char 7 Search、Sort

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

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

111 Bubble sort Algo. 若有n筆data

112 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 往前比

113 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

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

115 練習 steps

116 Char 8 Hashing

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

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

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

120 Char 9 Advanced tree

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