////////////////// 2010/11/26 Friday //hwk12qsort.c --- sample program to SORT studat.txt //========== Originally by tsaiwn@csie.nctu.edu.tw //====== Modified by student_ID student_Name _______________ const char *hahaha = " \n" " 五都選舉在明天, 藍綠搶票爭撒錢; \n" " 管他誰輸誰當選, 太陽依舊在天邊。 \n" " 既然現在課已選, 就該習題多多練; \n" " 程式一點也不難, 不該偷懶又擺\爛。 \n" // 那個ㄅㄞˇ 有問題 " .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?!\n"; /// 上面的"擺\" 反斜線不可以去掉, 不然翻譯有錯!! /// /// 因為 擺\爛 的 "擺\" 之內碼是0xc2 0x5c; 0x5c 是反斜線 !! ////// 阿字串中的 \ 是逃脫字符! 例如 \n 是 NewLine, \t 是跳格 ////// 所以 "\\" 就變成一個反斜線! What if 內碼第一Byte是 \ ? ////// 如果註解 // 後面的最後一個字是 擺 阿那會怎樣呢??? /// /// 注意, 這範例只做照學號排序(sorting), 照題目規定應該.. /// 請看習題說明, 關於 全部同學的平均 和 標準差.. /// 在資料看完一遍後就可算出來! 不必先算平均喔! /// .. 算這些統計資料的做法以前範例已經給過, 再不懂舉手問 :-) // 站在巨人的肩膀上: // 這版本是偷用 C 程式庫中的 qsort( ) 做排序 // 注意使用 qsort( ) 須先照規定寫好 call back function // .. 阿就是compare function 參數要照規定接受兩個 const void* // *** 想要不同順序, 只要寫不同的 compare function 傳給qsort // *** 注意， qsort 只知道資料是連續一堆 bytes, // *** 每當它想比較, 就會把兩項資料在記憶體的起點傳給比較函數 // *** 所以比較函數的參數是 (const void*, const void*) ///*** 你的比較函數必須自己轉換成你知道的型別(type) ///*** 因為你 call qsort( ), 然後 qsort( ) 回頭 call 你寫的 ///*** .. call 你寫的 比較函數, 所以稱為 call back function! #include #include #include #include char* fileName = "studat.txt"; // Data File long test( ); // 會傳回有幾個 records /// /// 雖然定義 struct 有很多寫法, 建議用這種寫法: 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) /// void sort(Student_t*, long left, long right); // sort( ) is your sorting program according to the score // left 是開始那項的 index, 最後一筆是 right void sort2Print(Student_t*, long n); // n records // sort2Print() is your another sorting program (照學號) // 注意我故意把參數用不同的寫法 ! 不是第幾個到第幾個 void print(Student_t*, long,int); // 用來印出資料, 但只印出一部份! ////// 第三個參數是個 FLAG, 表示要不要印名次 ? void readALL(Student_t *y, long, char*file,double*s,double*ss); // read ALL data from file into y[ ]; s=sum, ss=sum of square /// int main( ) { Student_t * stus; // 等一下用 malloc 要記憶體, 當作 stus[ ] long long tStart, tStop; long i, k, n; double tRun; double sum, sumSquare, average, variance, std; n = test( ); // 這列以上不准改! test( )會傳回 record 數目 // 打開檔案讀資料到記憶體, 也可寫成 function 在此 call 它 ! // 一邊讀, 一邊算出每個人的學期總成績; 或讀完再算也可以! // ..注意, 還要算出全部同學的平均 和 標準差 stus = (Student_t*) malloc(sizeof(Student_t)*n); // n 筆 // Note that malloc( )的單位是 Bytes // in C++: stus = new Student_t[n]; readALL( stus, n, fileName,&sum, &sumSquare); //into stus[ ] // 記得要用 "&" 把 sum 和 sumSquare 的address傳過去 average = sum / n; // 以下變異數公式以前給過, 忘了就上網查 variance = (sumSquare - sum*sum/n) / n; // sumSquare是平方和 std = sqrt(variance); // 高中就學過"變異數開根號就是標準差" printf(" N= %ld, Average= %.2f, STD標準差= %.3f\n", n, average, std); printf("Before sort...\n"); print(stus, n, 0); // 叫用 print( ) 印出部份資料, 不印名次 // todo.. print average, standard deviation tStart = clock( ); sort(stus, 0, n-1); // call your sort 程式, 照總成績由高到低 // this means to sort stus[0..n-1]; 從 stus[0]..stus[n-1] tStop = clock( ); tRun = 1.0*(tStop - tStart)/CLOCKS_PER_SEC; // in printf("...Sorting done in %.5f seconds.\n", tRun); /// fill in the rank (填入名次) for(i=0; i< n; i++) stus[i].rank = i+1; // 第 0 個是第一名 printf("After sort...\n"); print(stus, n, 1); // 叫用 print( ) to print partial data+名次 // Extra credit: 要有名次, 同分者比期末考, 再同比期中考, .. /// /// part 2 sort2Print(stus, n); // 在裡面做照學號由小到大sort, 要測時間 printf("=== 其實這些分數根本不是常態分佈, 是 Uniform 分布!\n"); printf(" N= %ld, Average= %.2f, STD 標準差= %.3f\n", n, average, std); printf("==> 站在巨人肩膀上: 本程式叫用 C 程式庫的 qsort,\n\t" "Sort %ld 筆資料依成績遞減Descending in %.3f 秒.\n",n, tRun); printf("Hint: 用 rand( )%%32767/32767.0 生出 12 個數加總, " "然後減去6.0;\n\t這樣就是 N(0, 1)的常態分配亂數;\n" "\t把這亂數乘以你要的標準差, 再加上你希望的平均數;\n" "\t.. 這樣, 就會是你希望的常態分佈成績!\n"); fprintf(stderr, "%s Hit ENTER key...", hahaha); getchar( ); return 0; } // main( /// /// /// ================ ============== ============== /// print one student, with Final grade? with Rank? void printStudent(Student_t yy, int prtFinal, int prtRank); /// void print(Student_t *x, long nStu, int rankFLAG) { // 我用傳參數 // 當程式是由多人合作時, 最好儘量少用 Global 變數 ! int i; for(i=0; i < 6; ++i) printStudent(x[i], 1, rankFLAG); // with total score printf("...\n"); printf("Stu ID name hwk mid quiz fin" " 學期成績 名次\n"); for(i=nStu-5; i< nStu; ++i) printStudent(x[i], 1, rankFLAG); } /// do NOT modify the following code long test( ) { // 這函數不准改 ! long id; char name[9]; int s1, s2, s3, s4, kk; static char buf[99]; FILE* fp; fp = fopen(fileName, "rt"); // read, text if(fp==0) { // Fail to open it fprintf(stderr, "File %s NOT found!\n", fileName); getchar( ); exit(38); // force to exit with an error } fgets(buf, sizeof(buf), fp); // stdin if(feof(fp) ) { fprintf(stderr, "EOF encounted.\n"); return; } fprintf(stderr, "Line-1: %s\n", buf); fgets(buf, sizeof(buf), fp); // stdin fprintf(stderr, "Line-2: %s\n", buf); s1=s2=s3=s4=0; kk = sscanf(buf,"%ld %s %d %d %d %d", &id, name, &s1, &s2, &s3,&s4); printf("kk=%d\n", kk); if( kk != 4) printf(" something Wrong with data!\n"); printf("id=%ld name = %s\n", id, name); printf("score= %d %d %d %d\n", s1, s2, s3, s4); fprintf(stderr, " counting..."); fflush(stderr); kk = 2; // already read 2 records while(! feof(fp) ) { // 只要檔案還沒結束 buf[0] = 0; fgets(buf, sizeof(buf), fp); if( feof(fp) ) { // EOF 也可能有讀到不完整的 Line if(buf[0] == 0) break; // 沒有讀到啦 } ++kk; // got one record } fprintf(stderr, " .. done.\nTotal %d records in file %s\n", kk, fileName); // 印到 stderr (螢幕) fflush(stderr); fclose(fp); // close the file return kk; // total kk records in the file } // test( /////////////////// /// 以下myComp is a 比較函數 that will compare 總成績 total, /// 要讓 qsort 做 Descending 排序, 若同分, 則照原 record no遞增 /// ..這樣就等同於 stable(穩定)的 sort; (注意qsort不是 stable !) int myComp(const void*pa, const void*pb) { // for sort( ) 總成績 Student_t * sa = (Student_t*) pa; // cast (轉型) Student_t * sb = (Student_t*) pb; // 其實 cast 電腦沒做任何事 if(sa->total < sb->total) return 1; if(sa->total > sb->total) return -1; /// toal 總成績相同, 比期末考 s4, 仍是遞減序 Descending order if(sa->s4 < sb->s4) return 1; if(sa->s4 > sb->s4) return -1; // 又同分ㄟ, 若要繼續比期中考是在 s2 , 請自己練習 (太簡單 :-) /// 成績同, 以下是比原來讀入的序號, 但用遞增序! if(sa->recno < sb->recno) return -1; // 這樣是遞增 if(sa->recno > sb->recno) return 1; // return sa-sb; return 0; } //myComp( void sort(Student_t x[ ], long left, long right) { // 我用傳參數! // call Library qsort( ) qsort((void*)x, right-left + 1, sizeof(Student_t), myComp); // 注意程式庫 qsort( ) 要這 4 項資料作參數: // 1.資料起點(address), 2.有幾項, 3.每項多少Bytes, 4.比較函數 // 再注意: "比較函數" 必須接受 兩個指標 (const void*) } // sort( /// /// 再來是 a 比較函數that compares ID, 要讓 qsort 做 Ascending 排 int compID(const void*pa, const void*pb) { // for sort2Print( Student_t * a = (Student_t*) pa; // cast 轉型 Student_t * b = (Student_t*) pb; if(a->sid < b->sid) return -1; //左小右大回傳 -1 : Ascending if(a->sid > b->sid) return 1; return 0; // ID 相同 ? 不管它 ! } //compID( void sort2Print(Student_t *x, long n) { // 要照學號由小到大 ! /// 參數.. // 注意我故意用不同於前面 sort( ) 的寫法喔 ! 此處 n是說有 n 筆 // Ascending order, 記得要量時間, 除了clock( )還有更準的自己查 long long tStart, tStop; // long long 是 64 bits double tRun; printf("...Now Sorting according to student ID..."); tStart = clock( ); qsort((void*)x, n, sizeof(Student_t), compID); // 注意寫法 ! tStop = clock( ); tRun = 1.0*(tStop - tStart)/CLOCKS_PER_SEC; // 注意上面的 1.0* 不可拿掉! Why? printf("\n...Sorting done in %.5f seconds.\n", tRun); /// printf("\n === Now already sorted in Student_ID" " at ascending order.\n"); print(x, n, 1); // call print( ) to print some data+rank } //sort2Print( /// /// 以下的宣告其實是多餘的 ! 因為馬上就要寫了 :-) int readStudent(Student_t * gg, FILE* fp); // read One學生資料 // /// /// read One student data int readStudent(Student_t * stu, FILE* fp) { // default stdin // 這裡的 stu 是一個指標, 指向一個學生 // 注意 default 參數要 C++ 才有, C 不可使用 default 參數 static char buf[999]; int nRead; // 讀到幾項資料? fgets(buf, sizeof(buf), fp); nRead = sscanf(buf, "%ld %s %d %d %d %d", &(stu->sid), stu->name, &(stu->s1), &(stu->s2), &(stu->s3), &(stu->s4) ); /// 題目規定這樣: // 學期總成績= (h*0.2 + m*0.3 + q*0.1+f*0.4); /// 這裡的 s1, s2, s3, s4 就是 h, m, q, f stu[0].total = 0.2*stu->s1 + 0.3*stu[0].s2 + 0.1*stu->s3 + 0.4*stu->s4; stu->total = ((int)(100* stu->total +0.50000001))/100.0; stu[0].rank = 1; // 大家都是第一名 :-); stu-> 改用 stu[0]. 可 stu[0].recno = 0; // 這樣寫 OK, (I do not know recno :-) // 注意, stu[0] 就是 *stu ; 以前說過任何時候 *p 就是 p[0] // 阿所以 stu->gg 就是 stu[0].gg 也就是 (*stu).gg return nRead; // 這是 sscanf 回報給我們的 }// readStudent( /// void readALL(Student_t x[ ], long n, char*file, double sum[ ], double *sumsum) { long i; double tmp; FILE* fp = fopen(file, "rt"); // 偷懶, 不防呆 sum[0] = sumsum[0] = 0.0; // sum[0] 就是 *sum for(i=0; i < n; ++i) { readStudent( &x[i], fp); // 注意 &x[i] tmp = x[i].total; // 該學生的總成績 sum[0] += tmp; // 注意 sum[0] 就是 *sum 啦 sumsum[0] += tmp*tmp; // 平方和 x[i].recno = i; // 注意寫法喔! record no., 0..n-1 // 多把 recno 也記下, 目的是讓 sort 看起來是 Stable // 這是因為 qsort( ) 不是 stable sort // 所以, 我們從 compare function 下手! (看後面該函數) }// for i fclose(fp); // 負責任, 我打開的阿就我自己來關掉它 :) }// readALL( /// void printStudent(Student_t stu, int finalFlag, int rankFlag) { // 注意 default 參數要 C++ 才有, 所以這程式要當作 C++ // finalFlag !=0 ==> 印學期成績; rankFlag 要不要印名次 printf("%8d ", stu.sid); printf("%8s ", stu.name); printf("%3d %3d %3d %3d ", stu.s1, stu.s2, stu.s3, stu.s4); if(finalFlag) { // 這樣寫是若不印 total, 那一定不會印名次! Why? printf("%6.2f ", stu.total); // 學期成績 if(rankFlag) { // 印名次, 須有印學期成績 printf("%5d", stu.rank); // note that stu is a struct }// if rankFlag } // finalFlag printf("\n"); // done } /// /// === === === End of the hwk12qsort.c === === === /// /*********** D:\test> path C:\Dev-Cpp\bin;%path% D:\test> gcc hwk12qsort.c D:\test> a.exe Line-1: 9943760 錢YLs 75 11 84 42 Line-2: 9941564 林PHe 3 80 96 91 kk=6 something Wrong with data! id=9941564 name = 林PHe score= 3 80 96 91 counting... .. done. Total 81503 records in file studat.txt N= 81503, Average= 62.55, STD標準差= 15.988 Before sort... 9943760 錢YLs 75 11 84 42 43.50 9941564 林PHe 3 80 96 91 70.60 9938531 孫VBd 82 60 84 35 56.80 9929387 簡ORa 81 5 99 5 29.60 9918783 林HCs 42 2 83 83 50.50 9926001 錢SHx 40 47 66 79 60.30 ... Stu ID name hwk mid quiz fin 學期成績 名次 9998487 章CDl 64 54 99 59 62.50 9998488 簡VKc 41 40 52 51 45.80 9998499 章AJk 14 98 90 77 72.00 9998501 趙HTq 74 94 67 71 78.10 9998502 王UTt 73 66 92 38 58.80 ...Sorting done in 0.06200 seconds. After sort... 9918979 蔡TSs 99 99 96 98 98.30 1 9927716 魏TEk 94 99 96 99 97.70 2 9983647 陳NWu 98 95 98 99 97.50 3 9963171 錢NNt 99 95 94 99 97.30 4 9993126 孫AHi 99 99 90 97 97.30 5 9995847 趙OSn 91 99 96 99 97.10 6 ... Stu ID name hwk mid quiz fin 學期成績 名次 9931010 陳QVi 8 5 12 2 5.10 81499 9937701 章BFr 12 5 4 2 5.10 81500 9946983 吳OVw 1 8 8 2 4.20 81501 9935478 張AQa 10 1 6 3 4.10 81502 9973775 張IAk 1 0 4 6 3.00 81503 ...Now Sorting according to student ID... ...Sorting done in 0.07800 seconds. === Now already sorted in Student_ID at ascending order. 9917001 林DOs 61 93 13 82 74.20 21276 9917002 蔡SOk 99 12 83 2 32.50 78011 9917003 魏SGj 83 12 56 41 42.20 72114 9917004 蔡UDb 6 10 57 39 25.50 80065 9917005 林LXa 42 35 55 49 44.00 70390 9917006 吳KAk 81 66 92 48 64.40 40112 ... Stu ID name hwk mid quiz fin 學期成績 名次 9998499 章AJk 14 98 90 77 72.00 25453 9998500 吳LLi 82 98 88 91 91.00 911 9998501 趙HTq 74 94 67 71 78.10 14637 9998502 王UTt 73 66 92 38 58.80 50171 9998503 林JUg 96 95 90 41 73.10 23345 === 其實這些分數根本不是常態分佈, 是 Uniform 分布! N= 81503, Average= 62.55, STD 標準差= 15.988 ==> 站在巨人肩膀上: 本程式叫用 C 程式庫的 qsort, Sort 81503 筆資料依成績遞減Descending in 0.062 秒. Hint: 用 rand( )%32767/32767.0 生出 12 個數加總, 然後減去6.0; 這樣就是 N(0, 1)的常態分配亂數; 把這亂數乘以你要的標準差, 再加上你希望的平均數; .. 這樣, 就會是你希望的常態分佈成績! 五都選舉在明天, 藍綠搶票爭撒錢; 管他誰輸誰當選, 太陽依舊在天邊。 既然現在課已選, 就該習題多多練; 程式一點也不難, 不該偷懶又擺爛。 .. ㄟ..你寫的 code 遠比老師給的範例還少很多阿好意思嗎?! Hit ENTER key... D:\test> ***************************************************/