//gen222.c  --- generate studat.txt, by tsaiwn@cs.nctu.edu.tw
/// 這版本 gen222.c 所生出的 data 不會是 worst case
/// 所以, 即使你的 quick sort 寫很爛沒修正也不會有問題 :-)
//因為: genID( ) 內改用我們新寫的亂數函數 int rand32( );
/// 這樣生出的亂數才可以很大!
/// 因為 Dev-C++ 的亂數 (應該說 MINGW32 的亂數)只有 16 bits
///  最大只有到 32767, 用在產生學號時不夠用!
/// 所以我們原先所生出的學號後面五萬多筆都是照順序的! 
///// (因為我們連續10次亂數找不到沒用過的學號後就改用循序找)
/// .. 這樣的 data, 用在沒有修正的"quick sort" 會變很爛! Why?
/// 因就是資料結構課本上說的 worst case ! 甚至會使程式當掉 !
///   Why? 因為不斷的 recursive call 會造成 Stack 爆掉!
/// 當然, 程式庫中的 qsort 和 C++ STL 的 sort 不會被data搞死,
 ///// 因為, 它們都是有修正過的 quick sort 聰明版本!
///
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
char nameLast[ ][3]={"趙", "錢", "孫", "李", "陳", "林",
        "陳","林","吳", "魏", "王", "蔡", "章", "張", "簡" };
const int N_LAST = (sizeof(nameLast) / sizeof(nameLast[0]) );
#define NSTU_MIN  81357
#define NSTU_VAR 200
#define NSTU_MAX  (NSTU_MIN + 568) 
#define ID_BASE 9917001
#define FILE_NAME "studat.txt"
int myRand( ) {  // 分數, 但不要太難看 :-) 隨便寫的 :)
    int ans = rand( ) % 100; if(ans < 35) ans+=80;
    return ans % 100; //  0..99 或說 [0, 99]
}
void genName(char*p) {  // 生出姓名 
  char mm,m2,m3;  char tmps[5]={0};
  *p = 0; // 清除字串
  strcat(p, nameLast[rand( )% N_LAST]);
  mm = 'A' + rand( )%26;  // 'A'..'Z'
  m2 = 'A' + rand( )%26;
  m3 = 'a' + rand( )%26;  // 'a' .. 'z'
  sprintf(tmps, "%c%c%c", mm, m2, m3);
  strcat(p, tmps);
}    
extern int nStudent;  // 先宣告 , 因為 genID( ) 要用到 
////////////////  若int是32 bit, 確保 rand32( ) 是 32 bit 亂數
int rand32( ) {   // assume int 是等於 long 為 32 bits
   int ans=0;
   ans = rand( ) &0x7fff;   // 0111 1111 1111 1111 保留右邊 15 bits
   ans = ans << 16;   // 往左移動 16 bits
   ans = ans | rand( );  // OR 起來, 這樣 rand( )若有 31 bits 也 OK
   return ans;  // 萬一 int 是 16 bit 那這樣沒用! Why?
} // rand32(  
///  ///  //////////////////////////
long genID( ) {
   static char idFlag[NSTU_MAX];
   int k = rand( ) % nStudent;  // 一開始用亂數決定 
   int nTry = 0;
   while(idFlag[k] !=0) {  // 若已經用過就要繼續重新產生
       k = rand32( ) % nStudent;  ///////////////
       if(++nTry > 10) break;  //最多做10次, 總不能沒完沒了啊 !
   }  //.. 然後改用由開始往後慢慢找沒有用過的
   if(idFlag[k]!=0) { // 已經用過! 剛剛沒找到可用的  ..
      k=0;   // 只好從頭開始找, 找第一個未用過的 ..
      while(idFlag[k] !=0) ++k;  // Loop 到發現未用過的就停
   }
   idFlag[k] = 1;   // 那我就用這個囉 :) 並標示為用過了 
   return ID_BASE + k;   // 加上基本號 ID_BASE
} // genID(
///
 int nStudent;   // 定義, 注意前面有宣告所以在這之前可以用到!
 long sid;  // 學號
 char name[9];
 int hwk, mid, quiz, fin;  // homework, midterm, quiz, final exam
void getNextStuData( ) {  // generate one student's data
   sid = genID( ); genName(name);
   hwk = myRand( ); mid = myRand( ); quiz = myRand( );
   fin = myRand( );
}
int main( ) {
    FILE* fp;
    int i;
    srand( time(0) );  // randomize; make it true random
    int n = NSTU_MIN + rand( ) % NSTU_VAR;  // 每次人數不同
    nStudent = n;   // nStudent 是 Global 變數 
    fp = fopen(FILE_NAME, "wt");
    if(fp == 0) { fprintf(stderr, "Sorry error...\n"); return 1; }
    for(i = 1; i<= n; ++i) {
       getNextStuData( );  // 資料在 global, 省得傳來傳去 :)
       fprintf(fp, "%7d %9s %3d %3d %3d %3d\n",
                  sid, name, hwk, mid, quiz, fin);
    } // for i
    fclose(fp);
    fprintf(stderr, "File %s generated successfully.\n", FILE_NAME);
    fprintf(stderr, "Total %d student records.\n", n);
    fprintf(stderr, " Hit ENTER key...");
    getchar(); return 0;
}
/******
D:\test> path C:\Dev-Cpp\bin;%path% 
D:\test> gcc gen222.c
D:\test> a.exe
**************************/