清华大学张思民Java课件第11章.ppt

Java语言程序设计,第11章 常见数据结构及算法分析,主讲：张思民,清华大学,主要内容,1、向量 2、堆栈 3、哈希表 4、算法分析,11.1 向量类Vector,11.1.1 向量类的构造方法 向量类提供了三种构造方法： public vector() public vector(int initialcapacity,int capacityIncrement) public vector(int initialcapacity),11.1.2 向量类的功能方法,1、插入功能 （1） addElement(Object obj) 将obj添加到向量的尾部。 (2) setElementAt(object obj,int index) 原来的对象将被覆盖。 (3) insertElementAt(Object obj,int index) 在指定的位置插入obj 。,2、删除功能,（1）removeElement(Object obj) 从向量中删除obj。 （2）removeAllElement() 删除向量中所有的对象。 （3）removeElementlAt(int index) 删除index所指的地方的对象。,3、查询搜索功能,（1）public final int indexOf(Object obj) 从向量头开始搜索obj ,返回所遇到的第一个obj对应的下标，若不存在此obj，返回-1。 （2）public final synchronized int indexOf(Object obj,int index) 从index所表示的下标处开始搜索obj。 （3）public final int lastIndexOf(Object obj) 从向量尾部开始逆向搜索obj。 （4）public final synchronized int lastIndexOf(Object obj,int index) 从index所表示的下标处由尾至头逆向搜索obj。 （5）public final synchronized Object firstElement() 获取向量对象中的首个obj。 （6）public final synchronized Object lastelement() 获取向量对象中的最后一个obj。,4、向量类的其它方法,（1）public final int size() 此方法用于获取向量元素的个数。 （2）public final synchronized void setsize(int newsize) 此方法用来定义向量大小。,11.2 堆栈（Stack）,1、堆栈的特性 Stack类是Vector类的子类。堆栈 “先进后出”，只在桟顶操作,Stack是一个容器，并具有以下特性： （1）堆栈是有次序的，堆栈数据结构只允许数据自有序列表的固定端(前端)做输入、输出操作，因此，最后被输入的数据项会最先被取出来。,（2）对堆栈的操作只能在一个名为top的位置上。用Push方法在堆栈顶部增加新的对象，用pop方法删除堆栈顶部的对象，也可以查询堆栈项部的对象。 （3） 用MakeEmpty方法可以清除堆栈的对象，也可用1sEmpty来查询该堆栈是否为空，以及查询堆栈的人小。,2、堆栈的方法,（1）堆栈的构造方法： public Stack()：创建一个空 Stack。 （2）堆栈的方法： empty()：测试堆栈是否为空。 peek()： 查看栈顶对象而不移除它。 pop()： 移除栈顶对象并作为此函数的值返回该对象。 push(E item)： 把数据压入栈顶。 search(Object o)：返回对象在栈中的位置，以 1 为基数。,11.3 哈希表(Hashtable),1、哈希表(Hashtable)的概念 哈希表就是记录与关键字之间有一个确定的对应关系的存储方式，它提供了一种很重要的快速检索方法。其基本思想是将关系码的值作为自变量，通过一定的函数关系计算出对应的函数值，把这个数值解释为结点的存储地址，将结点存入计算得到存储地址所对应的存储单元。检索时采用检索关键码的方法。现在哈希表有一套完整的算法来进行插入、删除和解决冲突。在 Java中哈希表用于存储对象，实现快速检索。,2、哈希表的方法,（1）构造方法 哈希表类中提供了三种构造方法，分别是： public Hashtable() public Hashtable(int initialcapacity) public Hashtable(int initialCapacity,float loadFactor),（2）插入 public synchronized void put(Object key,Object value) 给对象value设定一关键字key,并将其加到Hashtable中。若此关键字已经存在，则将此关键字对应的旧对象更新为新的对象Value。这表明在哈希表中相同的关键字不可能对应不同的对象(从哈希表的基本思想来看，这也是显而易见的)。,（3）检索 public synchronized Object get(Object key) 根据给定关键字key获取相对应的对象。 public synchronized boolean containsKey(Object key) 判断哈希表中是否包含关键字key。 public synchronized boolean contains(Object value) 判断value是否是哈希表中的一个元素。,（4）删除 public synchronized object remove(object key) 从哈希表中删除关键字key所对应的对象。 public synchronized void clear() 清除哈希表,（5）另外，Hashtalbe还提供方法获取相对应的枚举集合： public synchronized Enumeration keys() 返回关键字对应的枚举对象。 public synchronized Enumeration elements() 返回元素对应的枚举对象。,【例11-5】创建学生成绩表，用学号作关键字，如图11.5所示。,图11.5用学号作关键字的哈希表,11.4 算法分析,1、数组排序 排序是把一组数据按照值的大小递增或递减的次序重新排列的过程，它是数据处理中常用的算法。利用数组的顺序存储特点，可方便的实现排序。排序的算法有多种，这里讨论较易理解的“冒泡排序”。 “冒泡排序”的关键是对相邻的两个数组元素从后向前进行比较，若后面的元素的值小于前面元素的值，则将这两个元素交换位置，否则不进行交换。依次进行下去，最小的值逐渐“上升”到数组顶部（即第一个元素），就像水中气泡的上浮，而较大的值则沉到数组底部。,2、递归,递归是程序设计中常用的算法。所谓递归，其基本思想就是“自己调用自己”，一个方法直接或间接地调用自身的方法。 一个问题能否用递归实现，看其是否具有下面的特点： （1）需有完成任务的递推公式； （2）结束递归的条件。,例如，求一个正整数n的阶乘