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

Char 0 JAVA programing

寫程式的準則 程式碼要排版 有排版： 沒排版： 按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

練習 kb_inputOutput2

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

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

練習 kb_class2

如何在main class內建立一個method

練習 kb_class3

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

Example: stack 介面： 實作：

練習5 Interface-002

Char 1 Basic

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

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

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

Master theorem 遞迴式：

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

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

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

Recursive Fibonacci number(費氏數列)

練習 kb_Fibonacci

練習 10511-test005

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

練習 kb_Recursive_HanoiTower

Char 2 Array

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

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 = 898+ 2( j-1) => 14 = 2j => j=7 目的位址 來源位址 目的行-來源行 目的列-來源列

Example – Tridiagonal matrix(三對角線矩陣) 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_remove

練習 kb_arrayList_AddRemove

練習 kb_primeFactorization

練習 kb_findCompleteNum

練習 kb_findPrimes

練習 kb_gcd

練習 10511-test005

Char 3 Stack、Queue

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

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為左括號位置 印出左括號位置、右括號位置

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) 使用：

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 for Queue 建立Queue 操作Queue 加入：offer() 取得並移除：poll() 取得不移除：peek()

利用Linear Array製作Queue

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

Char 4 Linking list

Array VS Linking list Array 支援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

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

Alog - Reverse single linking list

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 Note： 1、deg(v) 2 2、height從1開始 3、高h的full binary tee總節點數 = 4、第i level的full binary tee節點數 =

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

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

BT traversal - Preorder

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

BT traversal - Postorder

給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

練習 steps

Char 8 Hashing

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

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