《计算概论》课程第十九讲 C 程序设计语言应用

Size: px

Start display at page:

Download "《计算概论》课程第十九讲 C 程序设计语言应用"

铅妤屈
5 years ago
Views:

1 Java 高级技术课程 Java 语言的高级特性李戈北京大学信息科学技术学院软件研究所 2009 年 4 月 18 日

2 对象容器能够容纳其它对象的对象 ; 对象容器容纳的对象称为对象容器的元素 ; 对象容器的作用对象容器提供了一些有用的数据结构和算法, 是程序组织和操纵批量数据的强有力工具 ; 重用对象容器可提高程序员的软件开发效率 ; 如何使用对象容器了解对象容器类所能存放对象的类型, 它的结构特点以及它可以提供的操作

3 Java 中的数组 Java 中的数组与对象容器的关系数组也是对象容器, 而且是一种最基本的容器在 Java 语言中只有数组能容纳基本类型的数据 ; 其它的对象容器都不能容纳基本类型的数据, 只能容纳对象 ( 严格地说是对象引用 ), 它们要存放基本数据类型的数据只能使用基本数据类型的包装类 ;

4 对象容器的形态对象容器需要提供的基本操作应该是多态的, 即 : 能适用于任意类型的对象, 这种多态性有两种实现方式 : 使用类属机制对象容器能存放的对象类型是创建对象容器时的参数, 一旦容器类的对象实例创建之后, 它只能存放该类型或它的子类型的对象,C++ 语言的对象容器采用这种实现方式 ; 使用统一根类设计一个根类, 对象容器存放的对象都声明为该类型, 使容器能存放任意类型的对象 Java 语言使用第二种实现方式 ;

5 对象容器的形态两种实现方式的比较 ( 编译时的类型检查 ) 类属机制实现的多态性, 编译时就能够确定容器所存放对象的类型信息, 操作容器内的对象时编译器能够进行更多的类型检查, 生成的代码可以更为安全且具有更高的运行效率采用单根类实现的多态性必须将对象的类型转换为根类类型, 丢失了对象的特有信息, 从而操作容器内的对象时编译器无法进行更多的类型检查当要使用存放在容器内的对象时, 必须将其类型转换为该对象原来的类型, 对这种类型转换的检查只能在运行时进行, 因此编译器生成的代码相对低效, 且可能引发运行时异常

6 对象容器的类型主要有四个因素影响对象容器 : 是否允许存放重复的对象指容器中包含有多个使用深比较相等的对象 ; 存放的对象之间是否有序如果所存放的对象有序, 则对象之间必须是可比较的 ; 如何访问所存放的对象随机访问 : 能用常数时间访问容器内任意位置的对象 ; 顺序访问 : 只能从存放对象的起始或者末尾位置开始访问 ; 分为 : 单向顺序访问和双向顺序访问 ; 存放对象的数目是否有限制容器是否可以自动扩展以存放更多的对象 ;

7 Java 对象容器的种类按对象容器能存放的对象将容器分为两种 : 类集 (collection) 容器其中存放的基本单位是单个对象 ; 用接口 Collection 描述这种容器的基本操作 ; 包括添加 (add) 删除 (remove) 查找是否包含某对象 (contains) 及返回迭代器 (iterator) 用于遍历容器内对象等 JavaAPI 提供一个抽象类 AbstractCollection 给出了该接口的最基本的实现映射 (map) 容器存放的基本单位是对象对 (object pairs) 一个为键 (key) 对象, 一个为值 (value) 对象 ; 用接口 Map 描述这种容器的基本操作

8 Java 对象容器的种类根据是否能存放重复的对象, 类集容器可分为两类 : 列表容器允许存放重复的对象可通过下标 ( 即存放的位置 ) 随机访问其中的对象 ; Java API 用接口 List 描述它们的基本操作, 并提供抽象类 AbstractList 作为基本实现 ; 集合容器不允许存放重复的对象, 是数学中集合的一种实现只能单向遍历存放的对象, 不能双向遍历, 不能随机访问 Java API 用接口 Set 描述它们的基本操作, 并提供抽象类 AbstractSet 作为基本实现 ;

9 各类 Java 对象容器的特点 Java 对象容器的种类

10 Java 对象容器的具体类列表容器具体类包括 :LinkedList ArrayList Vector 和 Stack 类 LinkedList 内部使用双向链表实现 ; 类 ArrayList 相当于是一个变长数组 ; 集合容器具体类包括 :HashSet 和 TreeSet 类 HashSet 使用散列表, 实现普通集合容器接口 Set; 类 TreeSet 使用平衡二叉树实现有序集合容器接口 SortedSet; 映射容器具体类包括 :HashMap WeakHashMap TreeMap 和 HashTable 类 HashMap 和 HashTable 内部都采用散列表存放对象对, 但类 HashTable 的方法实现了线程同步, 而类 HashMap 放弃了同步实现类 WeakHashMap 也与类 HashMap 类似 ; 只是类 WeakHashMap 在它所存放的键对象引用不再使用时会自动删除该键对象及对应的值对象类 TreeMap 则实现接口 SortedMap, 内部使用平衡二叉树存放元素

11 Java 的对象容器

12 Java 对象容器的具体类

13 Java 对象容器的配套设施用于辅助对象容器的接口包括 :Iterator Comparable 和 Comparator 接口 Iterator 抽象了遍历类集对象容器内所有对象的行为, 主要包括 hastnext() 方法和 next() 方法 ; 接口 Comparable 和 Comparator 用于对象之间的比较, 使得对象可以放入有序的对象容器 ; 用于辅助对象容器的类包括 : 类 Arrays 和 Collections 类 Arrays 用于辅助操纵最基本的对象容器数组提供对数组进行二分查找 (binary search) 排序 (sort) 填充 (fill) 以及判断两个数组相等 (equals) 等一系列的公有静态方法 ; 类 Collections 用于辅助操纵除数组以外的对象容器对列表容器内的对象进行二分查找和排序 ; 对类集容器内的对象进行统计 ( 如求最大值和最小值 );

14 程序包 java.util Java 对象容器的配套设施 Java 的对象容器都定义在程序包 java.util 中 ; 该程序包提供了对象容器操作日期时间压缩解压缩数据等一系列有用的工具程序包 java.util 中有关对象容器的部分包括 : 一些接口 : 给出了对对象容器所要提供的基本操作的抽象 ; 一些类 : 给出了对象容器的一些具体实现 ; 一些辅助工具 : 用于操纵包装对象容器 ; 类集框架 (Java Collections Framework) Java 2 SDK 1.2 版以后的 Java API 文档规范提供了一个类集框架 ; 概述了 Java 对象容器的组成, 设计目标等, 描述如何使用 Java 的对象容器 ; 通过它可以方便地查找各种对象容器的文档规范

15 类集容器

16 类集容器创建类集容器的类都必须实现接口 Collection 或其后代接口, 对于 Java 语言的对象模型而言, 因为只能通过对象引用访问对象实例, 因此对象容器存放的总是对象引用而非对象实例对象容器添加删除的都是对象引用, 这些操作不会影响该引用指向的对象实例只有通过迭代器获取容器内的对象引用后, 将其向下转换为合适的类型, 并调用这个类的方法才可能改变对象实例的状态

17 boolean add (Object o) booleanaddall(collection c) void clear() boolean contains(object o) boolean containsall(collection c) 接口 Collection boolean equals(object o) 比较此 collection 与指定对象是否相等 int hashcode() 返回此 collection 的哈希码值 boolean isempty() Iterator iterator() 返回在此 collection 的元素上进行迭代的迭代器 boolean remove(object o) boolean removeall(collection c) boolean retainall(collection c) int size() Object[] toarray() 返回包含此 collection 中所有元素的数组

18 说明 : 接口 Collection 判断两个对象是否相等都是通过调用该对象的 equals() 方法完成, 因此放入容器的对象必须重定义合适的 equals() 方法以确定两个对象是否具有逻辑 ( 通常是深比较 ) 意义上的相等程序员重定义 equals() 方法的同时也应重定义 hashcode() 方法, 以保证调用 equals() 方法比较相等的两个对象返回相同的散列码 hashcode() 方法用于将对象放入使用散列表实现的对象容器时计算对象的散列码实现接口 Collection 的容器类必须为 equals() 和 hashcode() 这两个方法给出合适的实现

19 列表容器是一种类集容器列表容器能随机访问列表容器内的对象 ; 允许存放重复的对象 ; 支持单向遍历和双向遍历 ; 列表容器必须实现接口 List 接口 List 是类集容器接口 Collection 的子接口定义了一些体现列表容器特点的方法 : 使用下标插入删除修改访问对象的方法返回对象下标的方法返回列表专用迭代器的方法等类 ArrayList 类 LinkedList

20 import java.util.*; public class DemoArrayList { public static void main(string[] args) { int index; 列表容器类 ArrayList, 可看作可变长的数组类型, 它的典型用法与使用数组类型相似 // 构造方法使用一个整数作为参数, 指定该容器能存放元素的个数 // 所有容器在存满元素时都会自动扩充容量以容纳更多的元素 List arraylist = new ArrayList(5); // 可以添加 10 个元素, 因为 arraylist 会自动扩充容量 for (index = 0; index < 10; index++) arraylist.add(new SmallClass(index * 10)); for (index = 0; index < arraylist.size(); index++) { SmallClass obj = (SmallClass) arraylist.get(index); System.out.println("Element[" + index + "] = " + obj.get()); arraylist.set(index, new SmallClass(obj.get() + 1)); /* trimtosize() 是类 ArrayList 中的常用方法, 用于将数组的容量缩减到数组中存放的元素的个数, 该方法是类 ArrayList 特有的方法, 这里必须将其强制转换为 ArrayList 类型 */ ((ArrayList) arraylist).trimtosize();

21 import java.util.linkedlist; 类 LinkedList 的特点是容易区分头位置和尾位置, 经常用于实现栈操作 ; class LinkedListStack { private LinkedList data = new LinkedList(); public boolean isempty() { return data.isempty(); public Object top() { return data.getfirst();// 取栈顶元素 public void push(object element) { data.addfirst(element); // 压入元素 public void pop() { data.removefirst(); // 弹出元素 public class DemoLinkedList { public static void main(string[] args) { LinkedListStack stack = new LinkedListStack(); stack.push(" 第一个字符串 "); stack.push(" 第二个字符串 "); stack.push(" 第三个字符串 "); while (!stack.isempty()) { System.out.println(stack.top()); stack.pop();

22 集合容器是一种类集容器集合容器数学上集合的实现, 不允许存放重复的对象只能单向遍历, 不能访问对象存放的位置信息, 不能随机访问集合容器内存放的对象集合容器类必须实现接口 Set 接口 Set 是接口 Collection 的子接口, 明确了一些方法的语义 : addall(collection c) : 将当前集合与类集容器 c 作集合并运算 ; removeall(collection c): 将当前集合与类集容器 c 作集合差运算 ; retainall(collection c): 将当前集合与类集容器 c 作集合交运算 ; containsall(collection c): 判断类集容器 c 是否是当前集合子集 ; 类 HashSet 类 TreeSet

23 import java.util.*; public class DemoSet { public static void main(string[] args) { Set hashset = new HashSet(); for (int i = 0; i < 10; i++) { int temp = (int) (Math.random() * 100); hashset.add(new SmallClass(temp)); System.out.println("Hash Set: " + hashset); Set treeset = new TreeSet(); for (int i = 0; i < 10; i++) { int temp = (int) (Math.random() * 100); treeset.add(new SmallClass(temp)); System.out.println("Tree Set: " + treeset); 类 HashSet 的容器存放的对象无序, 而类 TreeSet 的容器存放的对象有序 Hash Set: [19, 83, 35, 34, 57, 79, 51, 96, 48, 70] Tree Set: [15, 27, 55, 61, 64, 84, 86, 94, 99]

24 映射容器

25 映射容器映射容器用于存放键值对象对 ; 每一个键对象都惟一地对应一个值对象, 但不同的键对象可以对应相同的值对象 ; 映射容器内存放的键对象不允许重复 ; 映射容器内存放值对象则可以重复 ; 接口 Map 描述了映射容器应该实现的方法 ; 映射容器类必须实现接口 Map 或其后代接口 ;

26 接口 Map Object put(object key, Object value): 将映射容器内的键对象 key 关联到值对象 value void putall(map map): 对参数指定的映射容器 map 的每一个键值对象对, 调用当前映射容器的方法 put(object key, Object value) Object remove(object key) void clear() Object get(object key) boolean containskey(object key) boolean containsvalue(object value) Set entryset(): 将映射容器转换为集合容器, 该集合容器中存放类型为 Map.Entry 的键值对象对 Set keyset(): 将映射容器存放的所有键对象转换为集合容器 Collection values(): 将映射容器存放的所有值对象转换为类集容器 boolean isempty() int size() boolean equals(object o) int hashcode()

27 关于 Map.Entry 方法 entryset() 返回映射容器的一个集合容器视图, 该集合容器所存放对象的动态类型是 Map.Entry, 这是为描述映射容器所存放的键值对象对应该实现的方法而定义在接口 Map 中的嵌套接口 : public interface Map {... // 其它成员 public static interface Entry { Object getkey(); // 返回键对象 Object getvalue(); // 返回值对象 // 将值对象替换为新的对象 value, 返回被替换的值对象 ( 引用 ) Object setvalue(object value); // 实现该接口的类应该提供深比较相等的实现 boolean equals(object o); int hashcode(); // 相应地也应该定义 hashcode() 方法... // 其它成员

28 class Person implements Comparable { private String name; // 姓名 private Sex sex; // 性别 private int age; // 年龄 public Person(String name, Sex sex, int age) { this.name = name; this.sex = sex; this.age = age; public String getname() {return name; public Sex getsex() {return sex; public int getage() {return age; public void setage(int age) {this.age = age; public String tostring() {return "[ 姓名 :" + name + ", 性别 :" + sex + ", 年龄 :" + age + "]"; // 重定义 equals() 和 hashcode() 以作为映射容器的值对象 public boolean equals(object other) { if (other == null) return false; if (other == this) return true; if (!(other instanceof Person)) return false; Person temp = (Person) other; return name.equals(temp.name) && sex.equals(temp.sex); // 待续通信录中的 Person 类

29 // 继续 public int hashcode() { int result = 17; result = 37 * result + name.hashcode(); result = 37 * result + sex.hashcode(); return result; public int compareto(object other) { if (other == null) return 1; if (other == this) return 0; if (!(other instanceof Person)) throw new ClassCastException(" 比较的不是两个 Person 对象 "); Person temp = (Person) other; int value; // 同样在比较两个 Person 对象时也不涉及 age, 以保证 compareto() 与 equals() 的一致性 if ((value = name.compareto(temp.name))!= 0) return value; else return sex.compareto(temp.sex); 通信录中的 Person 类

30 import java.util.*; public class DemoEntrySet { public static void main(string[] args) { Map phonebook = new HashMap(); // 创建类 HashMap 的映射容器 // 添加元素到映射容器 phonebook.put(new PhoneNumber(" "), new Person(" 赵女士 ", Sex.WOMAN,30)); phonebook.put(new PhoneNumber(" "), new Person(" 赵女士 ", Sex.WOMAN,30)); phonebook.put(new PhoneNumber(" "), new Person(" 罗先生 ", Sex.MAN, 28)); phonebook.put(new PhoneNumber(" "), new Person(" 罗先生 ", Sex.MAN, 28)); phonebook.put(new PhoneNumber(" "), new Person(" 李先生 ", Sex.MAN, 34)); // 转换为存放元素类型为 Map.Entry 的集合容器, 通过该容器遍历映射容器 phonebook Set book = phonebook.entryset(); Iterator iterator = book.iterator(); while (iterator.hasnext()) { Map.Entry phone = (Map.Entry) iterator.next(); System.out.println(" 电话 :" + phone.getkey() + ", 属于 :"+ ((Person) phone.getvalue()).getname()); if (phone.getkey().equals(new PhoneNumber(" "))) phone.setvalue(new Person(" 衣女士 ", Sex.WOMAN, 28)); 待续通信录主程序

31 // 通过键对象集遍历映射容器 phonebook, 可知电话的主人已经被修改为衣女士 Set phonenumber = phonebook.keyset(); iterator = phonenumber.iterator(); while (iterator.hasnext()) { PhoneNumber number = (PhoneNumber) iterator.next(); Person person = (Person) phonebook.get(number); System.out.println(" 电话 :" + number + ", 属于 :" + person.getname()); // 可通过 phonenumber 删除 phonebook 中的元素 phonenumber.remove(new PhoneNumber(" ")); phonenumber.remove(new PhoneNumber(" ")); // 仍可使用先前得到的集合容器 book 进行遍历, 不过要重新获取迭代器, 否则会抛出异常 // 以下的遍历结果显示 phonebook 中的电话号码和都已经被删除 iterator = book.iterator(); while (iterator.hasnext()) { Map.Entry phone = (Map.Entry) iterator.next(); System.out.println(" 电话 :" + phone.getkey() + ", 属于 :" + ((Person) phone.getvalue()).getname()); // 不支持通过 phonenumber 添加元素, 以下语句会抛出异常 UnsupportedOperationException phonenumber.add(new PhoneNumber(" ")); 通信录主程序

32 映射容器类类 HashMap HashTable 和 TreeMap 类 HashMap 内部使用散列表存放元素, 元素之间没有顺序 ; 类 TreeMap 是有序映射容器, 存放的元素之间有顺序, 这个顺序通过存放的对象实现接口 Comparable 或在创建容器时指定实现接口 Comparator 的对象而确定类 HashTable 与 HashMap 基本类似, 相当于类 HashMap 的同步实现版本

33 import java.util.*; public class DemoMap { public static void main(string[] args) { Map bookone = new HashMap(); // 使用类 HashMap 创建普通映射容器 bookone.put(new PhoneNumber(" "), new Person(" 赵女士 ", Sex.WOMAN, 30)); bookone.put(new PhoneNumber(" "), new Person(" 赵女士 ", Sex.WOMAN, 30)); bookone.put(new PhoneNumber(" "), new Person(" 罗先生 ", Sex.MAN, 28)); bookone.put(new PhoneNumber(" "), new Person(" 李先生 ", Sex.MAN, 34)); System.out.println(" 在普通映射容器中的电话号码 :"); Set bookset = bookone.entryset(); Iterator iterator = bookset.iterator(); while (iterator.hasnext()) { Map.Entry obj = (Map.Entry) iterator.next(); System.out.println(" 电话 :" + obj.getkey() + ", 属于 :" + ((Person) obj.getvalue()).getname()); 在普通映射容器中的电话号码 : 电话 : , 属于 : 李先生电话 : , 属于 : 赵女士电话 : , 属于 : 赵女士电话 : , 属于 : 罗先生

34 import java.util.*; public class DemoMap { public static void main(string[] args) { Map bookone = new HashMap(); // 使用类 TreeMap 创建有序映射容器 Map booktwo = new TreeMap(); // 添加元素到映射容器在有序映射容器中的电话号码 : 电话 : , 属于 : 赵女士电话 : , 属于 : 赵女士电话 : , 属于 : 李先生电话 : , 属于 : 罗先生 booktwo.put(new PhoneNumber(" "), new Person(" 赵女士 ", Sex.WOMAN, 30)); booktwo.put(new PhoneNumber(" "), new Person(" 赵女士 ", Sex.WOMAN, 30)); booktwo.put(new PhoneNumber(" "), new Person(" 罗先生 ", Sex.MAN, 28)); booktwo.put(new PhoneNumber(" "), new Person(" 李先生 ", Sex.MAN, 34)); System.out.println(" 在有序映射容器中的电话号码 :"); bookset = booktwo.entryset(); iterator = bookset.iterator(); while (iterator.hasnext()) { Map.Entry obj = (Map.Entry) iterator.next(); System.out.println(" 电话 :" + obj.getkey() + ", 属于 :" + ((Person) obj.getvalue()).getname());

35 数组操纵工具对象容器操纵工具类 Arrays 是 Java API 提供的操纵数组的辅助工具类, 它提供了一系列的静态公有方法来辅助操纵各种数组, 完成填充 (fill) 排序 (sort) 查找 (search) 和比较等功能, 这些功能扩充了 Java 语言数组类型处理数据的能力容器操纵工具类 Collectoins 是 Java API 提供的操纵除数组外其它对象容器的辅助工具类, 它提供的一系列静态公有方法除可辅助操纵各种对象容器 ( 主要是列表容器 ) 外, 还可对各种对象容器进行包装, 以得到同步实现和不可修改的对象容器

36 import java.util.*; public class DemoUnmodifiable { public static void main(string[] args) { List list = new LinkedList(); for (int i = 0; i < 10; i++) 在有序映射容器中的电话号码 : 电话 : , 属于 : 赵女士电话 : , 属于 : 赵女士电话 : , 属于 : 李先生电话 : , 属于 : 罗先生 list.add(new SmallClass(i * 10)); // 返回 list 的一个不可修改的视图! List umlist = Collections.unmodifiableList(list); // 下述语句将抛出 UnsupportedOperationException 异常 // umlist.add(new SmallClass(999)); // 通过原来的容器对象仍可修改容器中的元素 list.remove(new SmallClass(70)); // 这种修改也会影响该容器的不可修改容器视图, 在以下的遍历中可发现 // 内部整数值为 70 的对象已经被删除 Iterator iterator = umlist.iterator(); while (iterator.hasnext()) { SmallClass obj = (SmallClass) iterator.next(); System.out.println(obj); // 修改该容器内存放的对象与不可修改容器的不可修改性无关! obj.set(777);

37 迭代器 (Iterator) 对象容器操纵工具在组织和操纵批量数据时, 遍历所有的数据是其中一项重要的操作 ; 迭代器是对象容器的遍历行为的一种抽象 ; 迭代器的设计目标是将遍历行为与组织数据的对象容器的其它行为 ( 如插入删除元素等 ) 分离开 ; 迭代器模式的基本思想是定义一个迭代器接口 Iterator, 支持遍历行为的对象容器 ( 称为迭代器的基础容器 ) 通常使用内部类实现该接口, 对象容器的使用者可通过公有方法获得该容器的一个迭代器对象 ;

38 迭代器 (Iterator) 迭代器接口 Iterator 定义为 : public interface Iterator { public boolean hasnext(); // 判断容器是否有下一元素 public Object next(); // 返回基础容器的下一元素 public void remove(); // 删除基础容器的当前元素

39 迭代器 (Iterator) 迭代器 (Iterator) 的实现 public abstract class AbstractList extends AbstractCollection implements List {... // 其它语句 // 定义私有类实现接口 Iterator private class Itr implements Iterator {... // 实现接口 Iterator 的方法 // 使用公有方法返回类 Itr 的一个实例作为使用者使用的迭代器 public Iterator iterator() { return new Itr();...

40 迭代器 (Iterator) 的使用迭代器 (Iterator) // container 是任意的类集容器 Iterator iterator = container.iterator(); while (iterator.hasnext()) { // 假定 container 存放对象的类型是 MyClass // 返回容器 container 存放的当前元素的引用, 并移向下一元素 MyClass obj = (MyClass)iterator.next();... // 利用对象引用 obj 对该元素进行修改等其它操作 // 进一步可根据某种条件过滤 ( 即删除 )container 中的当前元素 if (...) iterator.remove();

41 注意事项 : 迭代器 (Iterator) 方法 next() 返回的对象引用与基础容器的当前对象引用指向同一个对象实例, 使用者使用返回的对象引用进行操作也会影响容器中的对象引用所指向的对象实例 ; 方法 remove() 是将容器内的当前对象引用删除, 不会影响后续的遍历过程 ; 通用迭代器是一次性消耗品, 当遍历完容器所有元素之后, 通用迭代器对象就再也没有用了, 因为通用迭代器对象没有提供返回到起始位置的方法 ; 在获得迭代器后, 只能通过迭代器的 remove() 方法删除 ( 或增加 ) 基础容器内的元素, 否则会抛出异常 ConcurrentModificationException, 迭代器的这种性质被称为 failfast( 遇并发修改则即时作废 )

42 迭代器 (Iterator) 例如下述程序片段将抛出异常 ConcurrentModificationException: Iterator iterator = container.iterator(); container.add(new MyClass()); // 改变容器内的元素 while (iterator.hasnext()) { // 下述语句抛出异常 MyClass obj = (MyClass)iterator.next();

43 好好想想, 有没有问题? 谢谢!

KillTest 质量更高服务更好学习资料半年免费更新服务

KillTest 质量更高服务更好学习资料半年免费更新服务 KillTest 质量更高服务更好学习资料 http://www.killtest.cn 半年免费更新服务 Exam : 310-065Big5 Title : Sun Certified Programmer for the Java 2 Platform, SE 6.0 Version : Demo 1 / 14 1. 35. String #name = "Jane Doe"; 36. int

《计算概论》课程 第十九讲 C 程序设计语言应用

《计算概论》课程第十九讲 C 程序设计语言应用