程式設計實習第十三次上課 傅榮勝.

Presentation on theme: "程式設計實習第十三次上課 傅榮勝."— Presentation transcript:

1 程式設計實習第十三次上課 傅榮勝

2 Jung-Sheng Fu, DEE, NUU, ROC
再次提醒下週小考 下個禮拜6/10上機小考 考試分兩個時段： 4:10~5:00 U 曾樺陽(含)之前 5:10~6:00 U 王裕意(含)之後 Jung-Sheng Fu, DEE, NUU, ROC

3 Jung-Sheng Fu, DEE, NUU, ROC
範例： 請寫一個函式，其參數如下： 一陣列 此陣列的長度 函式的傳回值為此陣列長度的最大值之駐標，如陣列A為{1，2，6，3，2}，則會傳回2，因為A[2] = 6 在main function中，先用用亂數產生一個100個元素值為0~100的值之陣列，再呼叫本題的函式找出最大值元素的駐標。 Jung-Sheng Fu, DEE, NUU, ROC

4 Jung-Sheng Fu, DEE, NUU, ROC
範例 如果上題中除了要傳回最大元素的index之外，也要傳回最大值，該如何做？ 請注意，我們只能有一個傳回值。 所以，只能使用參數來接收，但此參數的使用必須使用參考引用或傳址引用，在此我們用較簡單的參考引用。 問題：為什麼陣列不用&就可以用參數來接收或改變值？ Jung-Sheng Fu, DEE, NUU, ROC

5 Jung-Sheng Fu, DEE, NUU, ROC
講解上次作業 有些同學上傳的相似度極高，請說明 P(n, r) = n (n  1)  … (n  r +1)表示從n個人中選取r個來排隊的方法數。 請寫一個遞迴函式會傳回P(n, r)之值 使用二分法的遞迴函式解出aq % n。 Jung-Sheng Fu, DEE, NUU, ROC

6 Jung-Sheng Fu, DEE, NUU, ROC
一維陣列的排序處理 (Sorting) 使用一維陣列時，常常會有需要將陣列的資料依序排列的問題，如：由小到大排序或由大到小排序。 在此，若時間允許，我們介紹一種常見的最影單的排序方法(但效能較差)： 汽泡排序法 叫用標準函式庫的函式可以省去自己重新寫程式的麻煩。 Jung-Sheng Fu, DEE, NUU, ROC

7 Jung-Sheng Fu, DEE, NUU, ROC
汽泡排序法 汽泡排序法是一種最容易了解的排序方法，這個方法的運作邏輯為將兩個相臨的汽泡(元素)做比較，比較大的汽泡(元素)就往上浮(右移)。 Jung-Sheng Fu, DEE, NUU, ROC

8 Jung-Sheng Fu, DEE, NUU, ROC
汽泡排序法 資料交換 (例：bubble.cpp ) Jung-Sheng Fu, DEE, NUU, ROC

9 Jung-Sheng Fu, DEE, NUU, ROC
叫用函式庫內建的排序函式qsort Qsort的排序效能遠高於汽泡排序法，但稍複雜，有興趣的同學可選修資料結構作進一步的了解。 在此我們要學著使用呼叫標準函式庫的qsort。 函式庫中的qsort可以 支援所有的資料型別(double，int，…等等)， 而且可以定義比較大小的規則，而此規則必須是一個函數，也就是說要用另一個函數當成是它的參數 但怎麼可以另函數當參數呢？替代方法是用函數指標當參數 因此使用qsort的概念有些複雜，但很重要，請仔細認真聆聽。今天沒有習題，只要照著老師一步步完成並存檔， Jung-Sheng Fu, DEE, NUU, ROC

10 Jung-Sheng Fu, DEE, NUU, ROC
函數指標 指標不一定要指向資料，它也可以指向函數，稱為函數指標(function pointer)。 對於一個函數而言，其名稱即是一個函數指標，永遠指向函數的開頭處。 宣告函數指標的語法如下： 資料型態 (*函數指標)(參數串列); Jung-Sheng Fu, DEE, NUU, ROC

11 Jung-Sheng Fu, DEE, NUU, ROC
快速排序法 qsort()函數的雛型如下： #include <stdlib.h> void qsort( void *base, size_t nelem, size_t width, int (*fcmp)(const void *e1, const void *e2) ); 其中base指向欲被排序的陣列之開頭處，nelem為陣列的大小， width為每個陣列元素所佔的記憶體空間。 而fcmp則為函數的指標，指向一個使用者自定的比較函數，而該函數的參數為指標，分別指向陣列中的兩個元素，假如 e1>e2 則傳回一正整數，若e1=e2則傳回0，若e1<e2則傳回一個負數。 Jung-Sheng Fu, DEE, NUU, ROC

12 定義快速排序法的比較函數 – 以整數元素為例
int compare(const void *a, const void *b) { int x, y; x = *((int*)a); //先將指標轉換為正確的指標(整數指標) y = *((int*)b); if( x > y ) return( 1 ); //較大時傳回 +1 if( x < y ) return( -1 ); //較小時傳回 -1 return( 0 ); //相等時傳回0 } 雛型：int (*fcmp)(const void *e1, const void *e2); Jung-Sheng Fu, DEE, NUU, ROC

13 Jung-Sheng Fu, DEE, NUU, ROC
使用快速排序法 – 以整數陣列為例 #include <stdlib.h> … int compare(const void*a, const void *b); int main() { int i, j, n, temp; int num[10]; qsort(num, 10, sizeof(int), compare ); //呼叫快速排序法 } Jung-Sheng Fu, DEE, NUU, ROC