站在巨人肩牓上 .. by tsaiwn@csie.nctu.edu.tw 關於資料結構/演算法相關: Java JCF (Java Collection Framework), C++ STL (Standard Template Library; 女共匪寫的:-), 甚至 C Library 的 qsort( ) 和 mergesort( ) 都很好用! 如果聽了這還不太知道我在說甚麼的請研究以下我寫的一些使用範例, 該些範例可在這找到: http://www.cs.nctu.edu.tw/~tsaiwn/oop/02_handouts/ 裡面有個子目錄 STL_JCF, 點進去看就是了! 另外, 有個 JavaSrc 的子目錄, 裡面放 Java JDK 的 sorce code src.zip 該 src.zip 就是在安裝好 JDK 之後在 JDK 根目錄內 copy 來的! aList.cpp, aList.java -- 使用 list / List, ArrayList, LinkedList vec.cpp, vec.java --- 使用 vector / Vector stk.java --- 使用 Stack util.java --- test java.util.*, 包括 Arrys.sort(), Collections.sort() sortList.cpp sort list / List : aList.cpp, aList.java sortVec.cpp, sortVec.java --- sort vector / Vector (Collections) sortVec2.cpp, sortVec2.java sortVec3.cpp, sortVec3.java sortVec5.cpp, sortVec5.java sortVec6.cpp sortAry.cpp, sortAry.java --- sort(array); Arrays.sort( ) vect.cpp --- demo how the class vector doing its job 另外, 也請參考上學期sort學生資料的習題, 以及與 stack 和 queue 有關的範例也值得你多看幾遍! 關於 STL source code 可到這抓: http://www.sgi.com/tech/stl/stl.zip =====================================================
善用 Library 可以讓你程式寫得更快更好更漂亮... 例如 java.util.*; 裡面有很多好用的工具類別 class
============================ To Sort an array: (要把陣列排序) C Language: 用 qsort 配合自己寫的 compare function 可 sort 任何連續的記憶體 C++ STL: 有許多 container class 並可使用 iterator 存取 container 內資料 ! 可直接叫用 <algorithm> 內的 copy( ) 把資料在 container 與 array間複製可直接叫用 <algorithm> 內的 sort( ) 被 sort 的物件類別要有 operator<( ) 可用可搭配 compare function 或 Comparator 做參數 Comparator 是含有 boolean operator( ) (para_1, para_2) 的 class Java Language: 在 java.util.*; 內有許多 container class 與 Utility(工具) class 可用 Arrays.asList(array) 把 array 弄成 List (是 Collection) 使用 Arrays.sort( ); 可以搭配Comparator 當參數做排序! 若為 class 物件的 array, 該 class 須 implements java.lang.Comparable 且要把 int compareTo(該class物件) 這函數寫好! 所謂的 Comparator (比較器), 就是.. 是有 implements java.util.Comparator 的 class 的物件, 且該class須寫好 int compare(Object a, Object b) 這 function, 注意 Java 沒辦法把函數當作參數傳!!! *Sort array of primitive data types (八大原始型別的 array) 只能 sort 成自然序 (Ascending order)! 那要 Descending order 怎辦? ==> sort 好後用 Loop 做 reverse 就好了! (注意 C++ 可以傳比較函數, 也可使用比較器; Java 只能使用比較器, 不可以傳比較函數! 可是 Java 的比較器必須是物件型別才有, 不能用於原始型別! ----------------------- To sort a List: Java 要用 Collections.sort(List<T> a); 可搭配 Comparator C++ STL 的 list 內有 sort( ), 也可搭配 compare function 或 Comparator C++ 可以只 sort list 的一部份; Java 必須整個 List 一起 sort ----------------------- To sort a Vector: Java 要用 Collections.sort(List<T> a); 可搭配 Comparator (因為 Java 的 Vector 是 List; 且 Java 的 Stack 是 Vector) Java 的 Vector 有 copyInto(Object [ ]array) 可 copy 到 array C++ STL 的 sort(vector<T> a); 也可搭配 compare function 或 Comparator C++ 可以只 sort vector 的一部份; Java 必須整個 Vector 一起 sort ===========================================
關於比較函數compare function ... C 語言: int 函數, 傳回 -1, 0, 1 代表小於, 等於, 大於 C程式庫的 qsort( )與 mergesort( ) 所需要的 call back function, 是個 int 函數, 要負責把兩個參數比較並回傳 -1, 0, 或 1, 參數是 void*, 阿就是void指標, 我們要自己轉型(cast)! C++ STL 內的 sort: STL 的 sort 是 template function, 不論是獨立使用的 compare function, 還是比較器內的比較函數, 都是 bool 函數, 要傳回第一個是否小於第二個, 據實回答則會 sort 為自然序, 就是遞增(Ascending order); 當然若故意說相反, 則會排序為遞減 (Descending order)! Java : 不論是可比較之類別內的 compareTo( ), 還是 Comparator (比較器)內的 compare( ) 都是類似 C 的 qsort 用的比較函數,是 int, 要傳回 -1, 0, 1 ** 所謂"可比較之類別"就是有 implements java.lang.Comparable 的類別 ** 所謂的"比較器類別"則是有 implements java.util.Comparator 的類別因為比較器算是工具, 放在 java.util.* 這 package. *** 注意 C++ STL 的 bool operator<( ) 與 bool operator( ) (pa, pb) 都是須傳回 true 或 false 的 boolean function
=================================================== 是否 Stable (穩定) ? Stable means that if two object resolve to the same value, their relative orders in the list are guaranteed to be the same as they were sorted before. * qsort( ) in C Library is NOT stable; mergesort( ) is Stable! The qsort() function conforms to ISO/IEC 9899:1990 * sort( ) in C++ STL is NOT stable; However, stable_sort( ) is a stable sort. 請參看 http://www.cplusplus.com * java.util.Arrays.sort( ) is a stable sort 請參看 http://java.sun.com/reference/api/ ============================================== Template function (樣板函數; 就是參數是泛用型別的函數) C++: template <class T> void printVector(vector<T> a) { vector<T>::iterator i; for(i= a.begin( ); i != a.end( ); ++i) cout << *i << " "; cout << endl; } --------------------------------- Java Generic function: (this is a generic function; can accept Vector of any Object) <T> void printV(Vector<T> a) { //vector<int>::iterator it; // C++ STL Iterator<T> it = a.iterator( ); cout.print("\n Vector contains:"); // print out content: for( ; it.hasNext( ); ) System.out.print(" "+ it.next( ) ); System.out.println(); }// printV( ===============================================================
期末考猜題.. Q: Java 的 JFC 和 JCF 都很重要, 請各用約50~80字簡單說明各是啥? A: JFC: 全名 Java Foundation Classes , 名稱是仿照 Microsoft 的 MFC (Microsoft Foundation Classes), 是 Java 的 GUI API (Graphical User interface 工具類別程式庫), 例如 Window, Frame, Panel, Button, Menu 等等圖形元件類別, 除了 java.awt.* 之外, 主要還包括 Swing library (javax.swing.*), Java 2D APIs 等, 總共大約有六百個 classes. 其中 Swing Library 因為不使用 native host OS UI, 稱為 Lightweight UI, 不需要用到 OS 的 native resources. 但 java.awt.* 要用到 native resources, 為 heavyweight components. JCF: Java Collection Framework, 在 java.util.* 內, 包括很多與 Data Structure 有關且可 reusable 的 class 與 Interface, 就是資料結構課本內討論到的常用資料結構, 有 Collection, List, Vector, Stack, Queue, Hashtable,.. 等 container, 更有 java.util.Arrays 和 java.util.Collections 各有很多好用的函數, 可以處理各種 array 和 collection, 包括 sort 和 search. java.util.* 內除了 JCF 外, 還有很多工具類別, 如 Random, Date, StringTokenizer, Scanner, .. 等等. -------------------------------------------------- Q: 請大略說明 C++ STL 的 vector 如何 "必要時自動長大 " ? 假設在寫 template<class T> class Vec { ... }; 要說出資料欄, constructor, operator[ ] 及各常用函數大概如何寫! A: C++ STL 的 vector 其實是偷用指標指到用 new 要來的空間; 要塞入資料時若發現 size 已經等於 capacity, 則要長大: 去要一塊兩倍 capacity 的新空間, 把舊資料都 copy 過去, 把內部指標改指到新區域, 更新 capacity 和 size, 把舊區域還掉! (記得要先備份指到舊區域的指標以免沒法還!) -------------------------------------------------- Q: 請大略比較 java.util.Collection 與 java.util.Collections A: Collection 是一個 Interface, 宣告所有 implements 它或是 implements 它的子孫者依定要寫的函數! 其中最重要的有 size( ), iterator( ), toArray( ), add( ) 等;; Collections 則是一個工具類別(utility class), 裡面有許多靜態函數(static functions), 例如 sort(List) 與 sort(List, Comparator), 注意是 Stable! (Why?) 可在已經排序搜尋的 binarySearch, 可把 List 顛倒的 reverse(List), 可生出反向比較器的 reverseOrder() 和 reverseOrder(Comparator), 可把全部資料變成可依序拿取之 Enumeration 的 enumeration( ), 可把 Enumeration 變成 ArrayList 的 list(Enumeration); -------------------------------------------------- Q: 請舉例說明 java.lang.Comparable 與 java.util.Comparator 之用途與用法. A: 必須有 implements java.lang.Comparable 的物件才可直接比較注意該 class 內要完成 public int compareTo(target) 有 implements java.util.Comparator (比較器) 的物件可以用於 sort, 注意該 class 內要完成 public int compare(first, second) 可利用 Collections.reverseOrder(Comparator) 生出反向比較器. 常用於 Arrays.sort( ) 與 Collections.sort( ), 當然也可以傳給自己寫的 sorting function. -------------------------------------------------- -------------------------------------------------- Q: 請舉例說明 C++ STL iterator 與 Java Iterator 之用法 A: (a) C++ STL 的 iterator 是寫在各 container class內, 用起來完全類似指標, 若 it 是 iterator, 用 *it 取得其內容; 例如若 av 是個vector<int> vector<int> it = av.begin( ); for( ; it!= av.end( ); ++it) cout << " " << *it; (b) Java Iterator 是個 Interface, 有三個 functions: bool hasNext( ); Object next( ); void remove( ) 若 it 是 iterator, 用 it.next( ) 取得目前 Iterator 指的元素; 假設有 Vector<Integer> av; 則要印全部可: Iterator<Integer> it = av.iterator( ); for( ; it.hasNext( ); ) System.out.print( it.next( ) ); -------------------------------------------------- Q: C++ 與 Java 都支援 Function name overloading 與 Polymorphism, 請舉例比較 Function name overloading 與 Polymorphism; 並大略說明 compiler 如何作出該兩項重要特性, 並以此說明 Static binding 與 dynamic binding. A: Binding 一般指變數 bind 到記憶體, 或是函數名稱 bind 到正確 function. Function name overloading : 函數名稱重複, 也就是說多個函數同名, 但是要從參數的數目或type可看出要用哪一個 function; Compiler編譯時會把各參數的type偷加到函數名稱, 如此就不會叫錯對象, 自動 bind 到正確函數, 因在 Run 之前就 bind好, 是為 static binding! Polymorphism 是指用 Base class 的指標(C++)或參考(Java)去操作衍生類別的物件, 或說指定要執行某衍生類別的函數; 也就是說 Polymorphism 的function不但同名且參數也相同, 但它們是在有繼承關係之不同的 class 內; Compiler 須翻譯出一些句子, 在生出物件時把正確的 function之address填到某處, 然後C++翻譯 p->fun( ); 或Java翻譯 p.fun( ); 這類句子時要翻譯成去執行 p 指過去後位移若干再指過去之處後再位移若干內所指過去的函數; 這樣在 Run time 才 bind 到正確 function 是為 dynamic binding ! -------------------------------------------------- Q: 請大略說明 Compiler 如何做出 call by value 與 call by reference 以及 C/C++ 的 call by address to pointer? A: 被叫用的函數一定到堆疊拿資料(透過 CPU 的 BP 加一個值) Call by value: copy 一份參數的 value 放到堆疊 call by Reference: 把參數的 address 放到堆疊, 然後被叫用的函數內用到其對應參數都改為 *參數名, 也就是取值或稱"解參照" 就是說, 跟 call by address to pointer 完全一樣, 只是使用者寫法不同 call by Reference: 把參數的 address 放到堆疊, 然後被叫用的函數內是用指標變數接收此參數當作所需值的 address -------------------------------------------------- Q: (a)請依照佔用記憶體最小大最多寫出 Java 的八個 primitive data type 以及其 class wrapper; (b)舉出若干class wrapper內一些常用函數 A: (a) 依序 boolean, Boolean; byte, Byte; char, Character; short, Short; int, Integer; long, Long; float, Float; double, Double (b) Character 內有許多類似 C 語言 <ctype.h> 內的字元檢查函數. 類似C的 atoi, atof 等: int Integer.parseInt(String), Long.parseLong(string), double Double.parseDouble(String)等! 各 class wrapper 內都有對應之原始型別的 MIN_VALUE 和 MAX_VALUE; 且都有 compareTo( ), 另外實數還有 compare( ), Integer 和 Long 都有可轉為 16進位, 8進位, 以及2進位的functions. ==================================================================