站在巨人肩牓上 .. by tsaiwn@csie.nctu.edu.tw 關於資料結構/演算法相關: Java JCF, C++ STL, 甚至 C Library 的 qsort( )和 mergesort( ) 都很好用以下範例在這 http://www.csie.nctu.edu.tw/~tsaiwn/oop/02_handouts/ aList.cpp, aList.java -- 使用 list / List, ArrayList, LinkedList vec.cpp, vec.java --- 使用 vector / Vector stk.java --- 使用 Stack 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 sortAry.cpp, sortAry.java --- sort(array); Arrays.sort( ) vect.cpp --- demo how the class vector doing its job 另外也請參考上學期 LAB12 以及與 stack 和 queue 有關範例 STL source code: http://www.sgi.com/tech/stl/stl.zip ============================================================ 善用 Library 可以讓你程式寫得更快更好更漂亮... 例如 java.util.*; 裡面有很多好用的工具類別 class ============================ Sort array: C: 用 qsort 配合自己寫的 compare function 可 sort 任何連續的記憶體 C++ STL: 有許多 container class 並可使用 iterator 存取 container 內資料 ! 可直接叫用內的 copy( ) 把資料在 container 與 array間複製可直接叫用內的 sort( ) 被 sort 的物件類別要有 operator<( ) 可用可搭配 compare function 或 Comparator 做參數 Comparator 是含有 boolean operator( ) (para_1, para_2) 的 class Java: java.util.*; 內有許多 container class 與 Utility(工具) class 可用 Arrays.asList(T[ ]) 把array T[ ] 弄成 List (是 Collection) 使用 Arrays.sort( ) 與 Collections.sort( )可以搭配Comparator 做參數若為 class 物件的 array, 該 class 須 implements java.lang.Comparable 且要把 int compareTo(該class物件) 這函數寫好 Comparator 是有 implements java.util.Comparator 的 class 物件且須寫好 int compare(Object a, Object b) 這 function 注意 Java 沒辦法把函數當作參數傳!!! *Sort array of primitive data types (八大原始型別的 array) 只能 sort 成自然序 (Ascending order)! 那要 Descending order 怎辦? ==> sort 好後用 Loop 做 reverse 就好了! ----------------------- sort List: Java 要用 Collections.sort(List a); 可搭配 Comparator C++ STL 的 list 內有 sort( ), 也可搭配 compare function 或 Comparator C++ 可以只 sort list 的一部份; Java 必須整個 List 一起 sort ----------------------- sort Vector: Java 要用 Collections.sort(List a); 可搭配 Comparator (因為 Java 的 Vector 是 List; 且 Java 的 Stack 是 Vector) Java 的 Vector 有 copyInto(Object [ ]array) 可 copy 到 array C++ STL 的 sort(vector a); 也可搭配 compare function 或 Comparator C++ 可以只 sort vector 的一部份; Java 必須整個 Vector 一起 sort =========================================== Java : 不論是 compareTo( ), 還是Comparator 內的 compare( ) 都是類似 C 的 qsort 用的比較函數, int, 要傳回 -1, 0, 1 注意 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. * java.util.Arrays.sort( ) is a stable sort ============================================== C++: template void printVector(vector a) { vector::iterator i; for(i= a.begin( ); i != a.end( ); ++i) cout << *i << " "; cout << endl; } --------------------------------- Java: (this is a generic function; can accept Vector of any Object) void printV(Vector a) { //vector::iterator it; // C++ STL Iterator 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 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 vector 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 av; 則要印全部可: Iterator 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 語言內的字元檢查函數. 類似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. ================================================================== Q: 請問 java.util.Random 內哪個 function 可生出標準常態分配的亂數? 假設函數內已經寫了 java.util.Random haha= new java.util.Random( ); 請寫一個 statement 可以生出平均 75.0, 標準差 8.0 的常態分配的亂數放 ans; A: double ans = haha.nextGaussian( ) * 8.0 + 75.0; -------------------------------------------------- Q: 若已知字串 s 有三到五個 token 但不確定幾個, 只知各token用逗號或空白或TAB或分號隔開, 請寫一個完整Java程式把字串 s 中的所有 token 印成一列(line)一個token. A: // 使用 StringTokenizer //s2tkn.java import java.util.*; class s2tkn { public static void main(String xxx[ ]) { String s = "Hello there, happy Economic Framework"; StringTokenizer stkn = new StringTokenizer(s, " \t,"); while(stkn.hasMoreTokens( ) ) System.out.println("" + stkn.nextToken( ) ); } // main( } // class -------------------------------------------------- Q: Java 規定每個圖型元件須自己用 paint(Graphics) 把自己畫出來, 請問若發現我們畫的圖畫面會閃爍要如何解決? A: (a)先改寫 update(Graphics g) 成直接叫用 paint(Graphics); (b)使用Double buffer: 在準備好另一個畫圖區, 畫好才一次畫到螢幕 Image offscreen = createImage(寬度, 高度); Graphics bg2 = offscreen.getGraphics( ); // use Graphics methods 修改 paint: public void paint(Graphics g) { // 原先用 g.drawXXX... 的都改為 bg2.drawXXX... // ... g.drawImage(offscreen, 0, 0, this); // 最後才畫到螢幕 } // paint( -------------------------------------------------- Q: 簡單說明 Java 的 Reflection, 簡單說明有何用處? A: Java Reflection 就是可以自己知道自己是啥，有如照鏡子! 這是指 Java 程式在執行時期(Run time) ..可以知道各變數的細節，可以動態檢查 (Dynamic checking)各變數與各類別的一些屬性! 除了自己寫程式可以善用這 feature, JavaBean 與 EJB (Enterprise JavaBean)在設計階段也使用這 reflection 來做 Introspection (自我反省, 反查自己), 以便設計工具可以知道 Bean 內的變數欄位與存取函數 -------------------------------------------------- Q: 考慮聊天室程式, 假設有 Hashtable a; 且其每項的 key 是聊天者的 nickname, 每項的value 是一個 class Brother 的物件(object), 該 class 內有連線聊天者的 Socket 以及相關資訊等等變數, 請大略說明可以用 Hashtable 的哪個 function 搭配哪個 interface 的哪兩個 functions 以便取得所有聊天者的相關資訊? 大略說明如何使用各 function. Hint: java.util.Enumeration -------------------------------------------------- Q: 簡單介紹 Java 程式分類. A: Java程式分為: Java application (stand-along) program Java Applet 在網站上, 會被抓到 client端搭佩Browser Java Servlet 在網站上, 會在該站機器直接執行的程式 JSP 在網站上的網頁裡面夾著片片段段的 Java程式碼, 會被先翻譯成Servlet (一次), 然後在該站上直接執行, 這種程式的主要目的是生出網頁丟回 client端 Browser Java MIDlet 在行動裝置如手機等上執行的 Java 程式 Java card Applet 在 Smart card 上的Java 程式, 如 iCash, 悠遊卡 -------------------------------------------------- --------------------------------------------------