Graph - 圖

1.如何定義一張圖：
 
圖(Graph)是由點(Vertex)與邊(Edge)構成，以G = (V,E)表示。

Linked list - 鍊表

1.Why Linked list ?

因為Array在使用上存在兩個問題

1. 在宣告時，就得指定大小，如果分配太多會造成空間的浪費，若分配太少又會出現錯誤，
2. 若要刪除或插入某個元素至陣列中，通常須對其他元素進行平移

而Linked list能透過pointer動態的分配紀憶體空間，補足了Array這兩個缺點。

2. Linked list的核心人物：pointer

• Pointer存放的是記憶體位置

• & ： the address operator （對一個變數取得它的位置）
• *  ： the de-referencing operator （到這個變數的位置去取得它的值）
• e.g. ：int * p = &x;
• int * p  ：宣告一個儲存int位置的pointer
• p = &x ：讓p儲存x的地址
• 而*p形同*&x，對x的位置取值，自然能取得x的值囉

• 誤用Pointer
• Dangling pointer
• pointer記錄到失效的記憶體位置（比如已經被刪除的變數），進而取到錯誤的值
• Memory leakage
• 忘了去deallocate不必要用的空間

3.Linked list

• Singly linked list
• 結構 ：
• 一個pointer的欄位，指向下一個節點(node)
• 一個data的欄位，儲存這個節點的資料
• 通常我們會用一個指標Head來指向第一個節點
• 通常最後一個節點會指向NULL
• 對linked的操作
• 1.定義一個節點的結構(struct)
• 2.當要新增一個節點時
• 先分配記憶體給這個新節點
• 把list中最尾端節點的指標指向新節點
• 3.當要移除一個節點時 -> free

Queue - 佇列

Queue跟Stack一樣都是有順序性的，存與取之間有一定的規則。直觀來看，Queue其實就像隊列，排頭的當然先服務，後到的就得等前面完事才能往前走，當然，我們不考慮插隊的情形，每次要加入這個隊伍的，都必須排在隊伍尾端，所以成了FIFO(First in First out)的型式。

1.Queue ADT

• Queue CreatQ(maxQueueSize) ：創造一個空的quene
• Boolen IsFull(quene,maxQueuesize)：判斷quene是否滿了，
• Boolen isEmpty(queue)：判斷quene是否為空
• Quene Add(queue,item)：添入item是quene
• Element Delete(queue)：刪除quene中的一個物件，並把它傳回給item

Queue的操作都與Stack類似，主要有兩個不同：

其一是stack有一方是底，我們只需要一直把東西丟進去丟進去，不過quene則是兩端皆開放的，要分別處理排頭跟排尾，所以我們需要兩個變數(front , rear)來儲存quene的頭跟尾，而front與rear的初始值一樣可以當作-1，配合於isEmpty的判斷上。

• add : rear = rear +1
• delete : front = front +1;

第一，從上述的操作，我們可以看出quene會不斷地往右偏移，所以在判斷isFull時，我們不能僅考慮rear是否>maxQuenesize，我們要思考的是，這個隊列是不是真的滿了？如果沒滿，則要把整個隊列往左平移。

2.Circular Queue

它是一個環狀的queue，這能解決上述第二個問題，不過他也得付出一點代價，即只能放MAX_Queue_Size - 1個元素，剩下一個必須用來判斷queue為空或為滿。

3.其他quene形式

• Double ended queue：兩端都能放且兩端都能拿的queue
• Priority queue：元素在queue的位置跟它的priority值有關，跟進入queue的時間無關
• Double ended priority queue

Stack 堆疊

1.什麼是Stack?

如果把input的資料當成積木，Stack就像疊積木一樣，把新加入的磚塊放在後加入的上面，要拿出也是把新加入的拿出，屬於LIFO (Last - in -First out)模型。

2. System Stack

有些語言函式的呼叫也是個Stack，比如Function A呼叫了Function B，而Function B又呼叫了Function C，用Stack結構來表示的話：

FunctionC

FunctionB

FunctionA

FunctionC會先執行，完成後才會是B與A。
當然囉，如果函式巢狀增加，這些積木也會越疊越高，而高度也是有個極限的，當到某個地步後還要疊的話，就會發生stack overflow的情形，所以在Recursive的終止條件上要特別注意。


4.Stack 的抽象資料結構

• Stack CreateS(maxStackSize) ：創造一個空Stack，並給予這個Stack最大容許儲存量
• Boolean IsFull(stack, maxStackSize)：確認stack是否滿了，避免push時把item丟入錯誤區塊
• Boolean IsEmpty(stack)：確認stack是否為空，避免pop時丟出的錯誤資料
• Stack Push(stack,item)：配合isFull使用，當還有位置放時，把item放入stack
• Element Pop(stack)：配合isEmpty使用，當裡頭還有物件，就把物件丟給item

實作stack最簡單的方法就是用一維陣列去處理它，為此我們需要兩個東西，一個是陣列stack[MAX_SIZE]來儲存，另一個就是top，用來表示目前存了多少item。

top

...

...

Stack[2]

Stack[1]

Stack[0]

在創造一個Stack時，可以把top設為一個非合理範圍，比如 -1，這樣便可在isEmpty上做判斷。
每當push就top++，如果top合理，便加入物件，pop則把top--，丟出物件。

5.一些Stack的應用

System Stack就是堆疊的基本應用，他用於在Run-time時決定Function呼叫的順序。在進行Backtracking與Recursive上，也涉及了Stack的概念。

時間複雜度

-Compile time :
-Execution time

     -Program step:       
   
        Definition : a program step is a syntactically meaningful program step whose execution time is independent of the instance characteristics,which means that something like the header of a sub program, a declaration of a variable (without assignment) is not consider as program step.
        Cautious : the execution time of program steps may be different,which depends on the degree of complexity.
   
    -How to ?
        -by a global variable (count) to calculate step by step.
        -by a table on counting the product of s/e(step/execution) and frequency (Fig.1.3)
       
    -So whats the different between two methods?
        -a global variable returns a number,
        -a table presents a function of time and step. e.g. 2n+n , n is a scale of input.
   
    -The best / average / worst step count.

---

-The big O notation:
    -Definition :   
    f(n) = O(g(n)) iff there exist positive constants c and n0 such that f(n) <= cg(n) for all n,n>=n0

-The omega notation:
    -Definition :
    f(n) = omega(g(n)) iff there exist positive constants c and n0 such that f(n) >= cg(n) for all n,n>=n0

-The theta notation:
    -Definition :
    f(n) = theta(g(n)) iff there exist positive constants c1,c2 and n0 such that c1g(n0) <=f(n)<=c2g(n) for all n,n>=n0.

-結論：
    1.Ｏ考慮的是函數上限(Upper bound)，omega則考慮下限，theta則是Ｏ跟omega的夾擠
    2.取的都是最函數趨勢影響最重要的一項

Array - 陣列

1.陣列

陣列可想成是相同資料型態的一組集合，每個集合中的元素都會有一個索引值，透過 [ ]
陣列存取運算子，我們便能取得陣列中的元素。

2.C語言中實做一個陣列

當編譯器遇到了一個 Element_type array[SIZE] 的宣告，它會分配 SIZE 個連續記憶體給這個陣列，其中每份記憶體都足以儲存Element_type的大小。

也由於分配出的記憶體是連續的，我們能瞭解每一個元素的記憶體位置。對於第i個元素，他的位置是：

array + (i-1)*sizeof(Element_type)

還記得嗎，c的陣列是從0開始的，所以必須先執行 (i-1)。要特別注意，當i=0的時候，就是陣列本身，也是第0個元素儲存的位置，所以我們能夠這麼說：

array = &array[0]

有了每個元素的位置，利用 * 運算子就能夠依照位置取得元素的值了，若要取得第i個元素(從0開始)的值：

array[i] = *(array + i);

上述兩種取值方法是等價的。
 值得一提的是，在C語言中，我們不必對i*sizeof(Element_type)進行處理。

簡介資料結構與演算法

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

演算法效率與Big oh

要討論一個演算法的效率，可以從空間複雜度和時間複雜度兩方面來分析。

關於空間複雜度，指的是演算法所占用的儲存空間，可以考慮為固定空間與變動空間的總和。固定空間指的是程式用來儲存指令、變數、常數及結構等等所耗費的空間。而可變空間則涉及了程式的輸入大小，或者遞歸呼叫等等所要占用的空間，需要視解決的問題而更動。一般而言，程式所需的全部空間S(P) ＝Sp(I) + c，前者為變動空間，後者c為一常數，屬於固定空間。


關於時間複雜度，考慮的是演算法執行完成要花費多少時間，包括了編譯和執行時間，不過一個程式編譯後能執行多次而不需重新編譯，因此，我們真正關心的是程式的執行時間。至於如何得知執行時間？基本上有兩個方法，一是利用計時程式來幫助我們，例如引入<time.h>，不過這會因硬體設備產生偏差，二是土法煉鋼，計算出程式需要多少個步驟完成，但這又讓我們面臨一個新問題，如何定義一個步驟？
我們先暫且假設一個步驟等同於一個指令，意思是t++這種簡單的指令與t=t+3*a+4*b+5*c這種複雜的計算都為一個步驟，現在。我們已經能藉由一個變數來對一個程式記數，例如：


step告訴我們這個程式共花了103個步驟，如果將50改為一個自由輸入的變數n，那麼步驟總數即為2n＋3次。

題外話，你可能會很好奇為何int i沒有被列入step，因為從系統的角度來看，宣告一個變數只是在編譯時建立一個空間，並不會產生什麼對應的程式碼，除非在宣告時有分配一個值給變數。

不過還記得嗎？先前我們對步驟的定義一點也不精確，即便一行一行的慢慢數，也未必有助於估計效率。換句話說，既然從一開始就是估計，結果也是夠用就好，那麼夠用又是指什麼程度呢？如果從極限的角度出發，在n極大時，2n+3的3影響微乎其微，一兆與一兆零三元相差無幾，進一步而言，an^2+b與cn+d，我們不必精確知道常數a、b、c、d，代表什麼，因為函數的成長趨勢告訴我們，在n突破某個值後，前者所耗費的時間必定會超越後者。當然，不排除在n不夠大時考量效率會做出錯誤判斷，但通常我們在意的往往是相當大的輸入，而不是拘泥幾微秒的差距。

---

Big O notation


談時間複雜度，總是不能忘記他的老跟班Big-Oh，它是一個漸進符號，至於為什麼用Ｏ，有人說是代表Order，有人說是形容你看到它的表情。總之，Ｏ能夠描述函數漸進的趨勢，他的快樂夥伴還有Ω (omega)跟Θ(theta)，不過目前先介紹他們的老大。

1.Big-Oh定義：

f(n) = O(g(n))：存在常數Ｃ、Ｍ，對於所有大於Ｍ的輸入Ｎ，使得f(n)不大於Ｃ*g(n)

簡單來說，f(n)的成長速度不會超過g(n)，頂多跟他一樣快而已。
以上文舉例：f(n) = 2n+3，g(n)=n，則當N大於3時，f(n)不大於3*g(n)，我們便可以說f(n) = Ｏ(n)
再舉一個比較常見的例子：當N>5時，10n²+10 < 11n²，因此10n² +10 = O(n²)

「看，很簡單吧」。「我們在這裡沒有什麼錯誤，只有快樂的意外。」

g(n)怎麼來的？怎麼突然蹦出一個3？4不行嗎？4也是符合答案啊，教科書就這麼討厭4嗎？如果要亂入的話，我也能讓g(n)=99n，這樣我Ｎ＝1的時候也對呀，而且我答案還是f(n) = O(99n)耶。更傷心的是，它還舉了滿滿一頁的例子來嘲諷我，不禁令我回想起童年中那顆超級爆炸頭。

首先，範例就真的只是個範例，他沒有要你求任何東西。先回顧一下定義，f(n)的成長速度不會超過g(n)，換句話說，當n非常非常大的時候，f(n)一定會比g(n)矮，那如果我們把g(n)整形成g'(n)：

g'(n) = g(n)+1，f(n)會不會比g'(n)矮？會

g'(n) = g(n)+2，f(n)會不會比g'(n)矮？當然會

g'(n) = g(n)+2，f(n)會不會比g'(n)矮？肯定會

我們能一直＋＋＋＋＋出各式各樣的g'(n)，當然，g'(n)=2g(n)也是個可行的辦法，定義告訴我們：只要g(n)在座標軸的右端比f(n)高就成了，別去在乎他高了多少。照這樣看來，g(n)會有很多種可能囉？就定義上來看，沒錯，如果符合定義，我們就能舉出各式各樣的答案。

但是，這樣會導致一個問題，答案多樣性，它是生物多樣性的好朋友，常見於作業、考卷讓學生被當掉。
比方說 f(n)=123n+456，那我能說g(n)=n，g(n)＝n²，或者像g(n)=e^n2+5n+8這種奇葩函數，只要能找到適合Ｃ和Ｍ，都算是個解。為了解決這個問題，我們希望g(n)越小越好，如此它才最接近，也最能夠描述逼近的趨勢，所以當f(n)=123n+456n時，我們預期g(n)＝n，而不是n²，儘管這個答案是正確的。

說了這麼多，那要怎麼去預期？

最直觀地去想，找影響趨勢最大的就對啦，我們考慮的是極限，所以攻略目標是一個函式裡，極限值最大的那個，從成長趨勢的大原則說起，

多重指數函數 >  階乘 > 指數函數 > 多項式函數 > 對數函數 > 常函數