[國考-電信類] 01 計算機概論-02 資料結構 筆記(一)

第一章. Basic Concept    Programs=Algorithms+Data Structures 程式是“演算法”加上“資料結構”

1. Pointer 指標

• *: the dereferencing operator
• &: the address operator

int *pi, i;

pi = &i; => i = 10; *pi = 10;

2. Allocation

• pi = (int *) malloc(sizeof(int)); 給int大小的空間
• 要free，否則會dangling reference

3. Algorithms

• Input: 有0或1個以上的輸入量
• Output: 至少1個以上的輸出量
• Definiteness: 描述必須無歧義(unambiguous)
• Finiteness: 有限步驟內完成
• Effectiveness: 有可行性，可實作

4. Data type:

• a collection of objects and a set of operators, e.g. {0, +1, -1, ...}, + / * / %

5. Abstract Data Type: 資料型態＋運算

• the specification of the objects and the operations on the objects is separated from the representation of the objects and the implementation of the operations, package (Ada) or class (C++)

6. Performance Analysis

• Space Complexity:
• Fixed: 程式碼，變數空間
• Variable: Input/Output佔用的stack
• Time Complexity:
• Ο上界:    0≤f(n)≤cg(n)    Ο(g(n))
• Ω下界:    0≤cg(n)≤f(n)    Ω(g(n))
• Θ:    0≤c1g(n)≤f(n)≤c2g(n)    Θ(g(n))
• e.g. f(n)=n^2-3n    0≤n^2-3n≤cn^2    Ο(n^2)

7. Performance Measurement:

• event timing in C: 量測執行時間