簡介資料結構與演算法

1.演算法

演算法是指令構成的集合，遵循這些指令能讓程式完成任務。通常演算法包會包含5個原則。

1. 有0~多個輸入資料
2. 至少要有一個結果
3. 每一個指令都要明確不含糊
4. 每一個指令都要是可行的
5. 在有限的步驟後便會結束，不會產生無窮迴圈

第五點也是一個程式跟演算法最大的不同，例如作業系統，除非系統當機，否則它將一直處於等待迴路中，直到有工作來臨。

1-1.以Selectioon sort為例

（ 這個for loop的目的是要找第i小的數字 ） 

for(i=0;i<n;i++){
Examine list[i] to list[i-1] and suppose that the smallist integer at list[min];
Intercange list[i] and list[min]
假設最小值出現於index min中，找到list[min]時，將list[i]與list[min]互換
}

1-2.以Binary Search為例

1. Given a sorted array list with n>=1 distinct integers, figure out if an integer seachnum is in list or not
2. 因為是排序過的陣列，所以利用中位數來進行搜尋，大則往後，小則往前，借此二分(binary)

while (there more integers to check)
{
 middle = (left+right)/2
 if(searchnum < list[middle]
    right  = middle -1;
 else if (search num == list[middle])
    return middle;
 else left = middle +1;
}

1-3.表示方法：

我們常常透過流程圖與虛擬碼來陳述一個演算法的步驟。值得一提的是虛擬碼，他介於口語與程式語法間，既能兼顧設計邏輯又可簡便表達演算法的內容。

2.Recursive Algorithm

• Direct recursion: 自己呼叫自己
• Indirect recursion: A呼叫B,B再呼叫A 

用於在問題本身是遞迴呼叫時（如階乘，費波那契）Recursive 最重要的是要決定跳出條件，以免造成Stack Overflow

3.Data Abstration

3-1簡介Data type

• Data type definition : A data type is a collection of objects and a set of operations that act on those object.
• e.g. int and arithmetic operations
• 程式語言內附的Data type稱為Predefined的Data type，使用者自行定義的則稱User-defined types ，但不是所有程式語言都會讓使用者創造User-defined data type
•  不論是哪一種類型的Data type，Data type都是由Object與Operation構成
• 就資料安全的角度來看，直接外露object給使用者是相當危險的，所以須透過operation處理

3-2 ADT

Definition: An abstract data type is a data type whose specification of the objects an the operations on the objects is separated from the representation of the objects and the implementation of the operations.

• 外漏給使用者看的只有specification，而specification並不一定要完成
• 抽象就是取出事物普遍性的本質，隱藏不必要的細節，只保留了目標必要的信息
• Catagories of function of a data type
• 建構式
• Transformers
• Observers/Reporters