Lab13 --- 第十三週 繼續做 sorting, 但這次一定要用 struct!
   且兩位學生對調時必須整個 struct 做一次對調就換好!! 
   各相關檔案資料已經公佈在 e3.nctu 的教材講義區
Due: 下週(第14週)演習課開始的前一天晚上
Purpose: 熟悉 struct 的用法與了解使用 struct 的好處!
Description:  
  (1)如果你有完成 Lab12 不使用 struct 把學生資料排序好,
     請繼續完成這必須用 struct 把同一個學生的資料放在一起的Lab13.
     當然要把 Running script 與心得潑 (post)到 Lab13 繳交區。
     如果你的 Lab12 還沒完成, 那請繼續完成 Lab12, 
     至於 Lab13 就做輕鬆的: 改為寫心得, 測試並研究本週新給的範例, 
     然後把測試的 Running script 與研究心得潑到 Lab13 繳交區,
     這樣最高也可以拿到 80% 分數:-)。 
  (2)本週的Lab13是  Lab11, Lab12 的延續, 這次一定要使用 struct,
     你可以直接使用(#include)我提供的 mystu.h 或自己定義資料結構。
     (在這個檔案的最後附有 mystu.h 的內容)
     但是這次規定不可以使用 Quick sort, 其它任何 sorting 方法都可以!
  (3)這次的資料檔請改用 gen333.c 重新產生, 主要差異是這次的成績是
     用常態分佈(Normal distribution), 每次考試都是平均 75, 標準差7;
     你會發現算出的學期成績標準差只有三點多! Why?
     這應該是合理的! 因為每次考試都是標準差 7, 很多次合起來算一定變小!
     Why? 因為每次都考很好或每次都考很爛的一定是少數!
  (4)新給的範例: (注意有些函數在不同的檔案!)
     (a) qqsort.c -- qqsort( ), 使用與 qsort( ) 一樣的用法
         編譯:  gcc -c qqsort.c   會生出 qqsort.o 備用
     (b) qsort2.c -- qsort2( ), 也是使用與 qsort( ) 一樣的用法
         編譯:  gcc -c qsort2.c   會生出 qsort2.o 備用
     (c) hwk13tq2.c -- 使用 qsort2( ) 做 Lab13 的範例
         測試這個範例需要用到 qsort2.c, 
      gcc hwk13tq2.c qsort2.c   (因函數 qsort2( ) 在 qsort2.c 內) 
         此外, 你也可以在 gcc 時用 -D 指定換為其它 sorting 函數
         例如, gcc hwk13tq2.c -DQSORT  (這樣變為用Library的 qsort);
         或是, gcc hwk13tq2.c -DQQSORT qqsort.c  是改用 qqsort( )
         還有, default 是測試 1000 次, 大約要一分鐘多一些,
         你可以用 -DRUN=38 改為 測試 38 次, 例如:
      gcc hwk13tq2.c -DRUN=100 -DQSORT  用程式庫 qsort( ) 測100次
     (d) mystu.h  -- 裡面有 Student_t 這資料結構 struct 的定義,
            也順便宣告了 qqsort( ) 和 qsort2( )  的 prototype;
            該兩個宣告本來可以放 qqsort.h 和 qsort2.h 方便使用
            現在順便寫在 mystu.h, 
            反正依照規定, 宣告很多次只要都宣告相同是可以的 :-)
            也就是說, #include "mystu.h"  之後,
            萬一又 #include "qsort2.h"  這樣並不會有問題!
     (e) qqsort.h, qsort2.h  --- 阿就 qqsort( ), qsort2( )的宣告啊!
            這兩個檔案的內容也有附在最後!
     (f) testqs2.c -- 用一個簡單 array 測試 qsort2.c 的 qsort2( )
     (g) 如果你夠認真: 另外還有兩個 Merge sort 及它們的測試程式: 
         msort.c  -- 內含兩個不同做法的 merge sort 函數
         hwk13ms.c -- 測試  useMgSort( ) -- 比較函數須認得 Student_t
         hwk13m22.c -- 測試  msort( )  -- 用法跟 qsort( ) 一樣!
   (5)注意 hwk13tq2.c 內定(default)是測試 1000次累計 sorting 時間,
      這樣測試一千次再比看看比較公平, 各版本 quick sort 時間差不多,
      事實上是我寫的 qsort2( )比程式庫的 qsort( ) 快一點點 :-)
      阿不過比較容易懂的版本 qqsort( ) 則慢了一些,
      請用 gcc hwk13tq2.c -DQQSORT qqsort.c  生出執行檔案測試看看 !
      若要改變測試次數, 用 -DRUN=次數  就可以改變程式碼內容,
      不必真的去改程式原始檔!

*** mystu.h 內容: 
//mystu.h  --- @CopyLeft by tsaiwn@cs.nctu.edu.tw
// Header file for using msort( ), useMgSort( )
#ifndef _MYSTU_H_
#define _MYSTU_H_
// 以上這兩列 #ifndef 與 #define 以及最後的#endif 使得這檔案萬一..
// .. 萬一不小心被 #include 多次也沒關係!
/// 
 void msort(void*x, int n,int sz, int(*comp)(const void*, const void*));
  // 上面這  ( ) 的參數與用法跟 C Library qsort( ) 完全相同 
  /// 以下這兩個宣告對應到我們自己寫的 qqsort( ) 和 qsort2( )
 void qqsort(void*x, int n, int size,
           int (*cmp)(const void*, const void*));
 void qsort2(void*x, int n, int size,
                int (*cmp)(const void*, const void*) ); 
///
 // 以下是之前 hwk12qsort 抄來, 但再定義一個沒有 _t 的 :-) 
typedef struct {
   long sid;  int s1, s2, s3, s4; // struct 內各項目順序不重要
   double total;  // 學期總成績= (h*0.2 + m*0.3 + q*0.1+f*0.4); 
              /// 這裡的 s1, s2, s3, s4 就是 h, m, q, f
   long rank, recno;  // rank, original record number
   char name[9];  // student's name
} Student_t;   // 這種命名方式是不錯的習慣 ( _t) 
typedef Student_t Student;  // 這樣, 使得寫  Student 也可以:-)
///
void useMgSort(Student*, int, int(*comp)(Student*,int,int));
 /// 注意此 sorting function 接受的 comp 比較函數與 qsort 的不同!
 /// qsort 的 compare function 是接受兩個 pointer 指標
 /// 我們這個須接受三個參數:
 ///   一個 Student array (即Student*)和兩個整數 i, k;
 ///   該兩個整數指出要比的哪兩個元素之 index(subscript),不是pointer
 /// Usage of useMgSort:
 ///  useMgSort( x, n, myComp);
 ///     where x is a Student array, n is number of elements in x;
 ///     and myComp(int i, int k); is a compare function that
 ///     whill compare i-th element with k-th element
 ///     the compare function myComp( ) should return 1, 0, -1
 ///     to indicat that x[i] >, ==, < x[k]
 ///     And thus, x[ ] will be sorted in Ascending order.(遞增序)
#endif

 
*** qqsort.h 內容: 
//qqsort.h   @CopyLeft by tsaiwn@cs.nctu.edu.tw
#ifndef _QQSORT_H_
#define _QQSORT_H_

void qqsort(void*x, int n, int size,
           int (*cmp)(const void*, const void*));
#endif


*** qsort2.h 內容: 
//qsort2.h  -- another version of quick sort, as qsort( ) in C Library
// @CopyLeft by tsaiwn@csie.nctu.edu.tw
#ifndef _QSORT2_H_
#define _QSORT2_H_
 void qsort2(void*x, int n, int size,
                int (*cmp)(const void*, const void*) );
#endif

 
再次提醒: 
      User 可以不必改程式碼, 只要改 compiling option -D
   利用 conditional compiling 特性的, 
   用 -DQQSORT 或 -DQSORT  就可改變為使用 qqsort( ) 或 qsort( )
   不過要記得 qsort2( ) 在 qsort2.c, 還有 qqsort( ) 在 qqsort.c
   所以要記得所需檔案或乾脆 gcc hwk13tq2.c qsort2.c qqsort.c -D選項
   ** 其實 -DQSORT  時是不會用到 qsort2.c 和 qqsort.c