【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);——用于测试使用