【Java】_ 數組、哈希表、疊代器以及随機數生成器

學習資料來源：斯坦福大學公開課程式設計方法cs106aJAVA（下載下傳中心有資源）

相關學習資料已上傳至下載下傳中心：學習過程中使用的代碼、筆記初稿以及課程講義（有興趣者可自行下載下傳）

學習過程中的大部分程式需要導入acm.jar包（已上傳至下載下傳中心，也可自行進入http://jtf.acm.org/ 進行下載下傳），

數組（ARRAY）：同時記錄一組資料的方法    ——  （有序，同質(類型相同)）

    一維數組

        用法：

            type[] name = new type[sizse];

        數組長度：myArr.length——length是類裡的一個public變量

        數組傳入函數時為引用——對象

    多元數組—矩陣（matrix）  

        用法：int[][] matrix = new int[2][3];

        例如：二維數組

            scores[2][100] —— scores.length = 2    scores[0].length = 100

    動态數組（ArrayList）—— import java.util.*; —— 動态變化

    動态數組是模闆（template），需要指定資料類型（<>）

            ArrayList<String> strList = new ArrayList<String>();//聲明動态數組

            String line = “hello”;

            strList.add(line);——向動态數組中添加元素

            strList.size();——傳回動态數組元素個數

            strList.get(i);——根據索引傳回動态數組元素

        ArrayList的方法：

            boolean add(<T> element) —— 添加元素

            void add(int index, <T> element) —— 将元素添加至指定位置

            <T> remove(int index) —— 删除指定元素

            boolean remove(<T> element) —— 傳回删除是否成功

            void clear() —— 移除清單中所有元素

            int size() —— 傳回元素個數

            <T> get(int index) —— 傳回指定元素

            <T> set(int index, <T> value) —— 給指定元素指派

            int indexOf(<T> value) —— 搜尋元素（傳回索引号）

            boolean contains(<T> value) —— 傳回是否存在指定元素

            boolean isEmpty() —— 傳回清單是否為空

        示例：

            public void run() {

               ArrayList<String> sList = new ArrayList<String>();//建立動态清單

               while(true){//向清單中添加元素

                   String line = readLine(“?”);

                   if（line.equals(“”)）break;

                   sList.add(line);

               }

              for(int I = 0; i < sList.sizse(); i++)//輸出清單中的所有元素

                  println(sList.get(i));

              }

            }

        ArrayList 中存放的是對象

            int double boolean char 是基本資料類型

                基本資料類型對應的類：

                    int    Integer

                    double    Double

                    boolean    Boolean

                    char    Character

            示例：

                ArrayList<Integer> list = new ArrayList<Integer>();——不能使用ArrayList<int>

                int x = 5;

                list.add(x);

    數組和動态數組的優缺點比較：

        ArrayList：

            優點：它能動态改變大小    

            提供其它操作：提供很多進階操作來自動支援一些功能（比如包含）

            缺點：計算機實際處理方面相對于數組效率較低

                  文法可能會冗長（需要很多說明）

            是以在事先知道數組的大小的條件下（有固定的長度） —— 盡量采用正常數組

    （GImage-——圖檔的實質是像素組成的數組）

排序和查找：

    線性查找（Linear Search）—— 周遊所有元素

        private int linearSearch(int key, int[] array) {

            for(int i = 0; i < array.length; i ++) {//周遊所有元素,查找元素存在則傳回其鍵值

                    if(key == array[i]) return i;

            return -1;//查找失敗

        }

    折半查找（binary search）—— 用于有序數組

        private int binarySearch(int key) {

            int lh = 0;

            int rb = disp.length() – 1;

            while (lh <= rb){

                int mid = (lh + rb) / 2;

                if (key == disp.get(mid)) return mid;//找到元素則傳回其鍵值

                if(key < disp.get(mid)) {//查找的元素在左半邊

                    rh = mid – 1;

                } else if{//查找的元素在右半邊

                    lh = mid + 1;

                }

                return -1;

    排序：冒泡排序

接口(Interface) —— 一系列方法的集合 —— 某些類中通用的函數集合   

    接口的文法：

        public class ClassName

                  implements InterfaceName    ——   實作某某接口

        {

                code

    映射（Map）—— java中的一個接口 —— 将某個特定主鍵和某個特定值聯系起來

    （key —— 特定主鍵（大小寫敏感），value —— 特定值）

    例如：字典（詞語—解釋），通訊錄（姓名—手機号）

        HashMap（有兩個類型：鍵，值）：是一個實作映射接口的類

        (哈希表的實質是一個模闆，哈希表中的任何東西都實作了映射)

        哈希表中最常用的兩個方法：

            put —— 添加資料    dict.put(key,value);

            get —— 提取資料    dict.get(key);傳回值或 null

        例1 — 字典 — 從字元串到字元串的映射的散清單（哈希表）

            HashMap<String, String> dict = new HashMap<String, String>();

        例2 — 電話本 — 從字元串到×××的映射的散清單（哈希表）

            HashMap<String, Integer> phonebook = new HashMap<String,Integer>();

            phonebook.remove(key);//移除指定元素

            phonebook.containskey(key);//傳回是否含有指定元素  true or false

            phonebook.size();//傳回元素個數

    結構：

疊代器(Iterator) —— 列舉集合中的值

    用法：

    Iterator在ArrayList中的用法：

        ArrayList<String> names = new ArrayList<String>();

        Iterator<String> it = names.iterator();—— 有序

        while(it.hasNext()) {//判斷集合中是否還有元素

          println(it.next());//輸出元素

    Iterator在HashMap中的用法：

        Iterator<String> i = phonebook. —— 無序

                                keySet(). —— 傳回一組鍵

                                  ietator();//建立疊代器（哈希表鍵值集合）

        輸出集合中的元素除了可以使用疊代器通過while循環周遊集合外，還有另一種周遊集合的方法：

        foreach結構  （java5.0以後可用）

            for(String name:phonebook.keyset() { —— 需要調用疊代器的集合)

              prinln(name)；

随機數生成器： private RandomGenerator rgen=RandomGenerator.getInstance();

    方法：

        int nextInt(int low, int high)——傳回一個介于low,high之間的一個随機數

        int nextInt(int n)——傳回一個介于0~n-1的随機數

        double nextDouble(double low, double high)——傳回一個随機數d    low<=d<high

        double nextDouble()——傳回一個随機數d 0<=d<1

        boolean nextBoolean()——傳回true的機率為50%

        boolean nextBoolean(double p)——傳回為true的機率為p 0<=p<1

        Color nextColor()——随機産生一種顔色

        賦予随機數計數器的第一個值稱為種子，種子決定随機數産生的序列，一般用于測試資料

            rgen.setSeed(1);——用于測試使用