《清华大学张思民Java课件第11章.ppt》由会员分享，可在线阅读，更多相关《清华大学张思民Java课件第11章.ppt（22页珍藏版）》请在金锄头文库上搜索。
1、Java语言程序设计语言程序设计第第11章章 常见常见数据结构及数据结构及算法分析算法分析主讲：张思民主讲：张思民 清华大学清华大学主要内容主要内容1、向量、向量2、堆栈、堆栈3、哈希表、哈希表4、算法分析、算法分析11.1 向量类向量类Vector11.1.1 向量类的构造方法向量类的构造方法向量类提供了三种构造方法：publicvector()publicvector(intinitialcapacity,intcapacityIncrement)publicvector(intinitialcapacity)11.1.2 向量类的功能方法向量类的功能方法1、插入功能（1）addEleme
2、nt(Objectobj)将obj添加到向量的尾部。(2)setElementAt(objectobj,intindex)原来的对象将被覆盖。(3)insertElementAt(Objectobj,intindex)在指定的位置插入obj。2、删除功能、删除功能（1）removeElement(Objectobj)从向量中删除obj。（2）removeAllElement()删除向量中所有的对象。（3）removeElementlAt(intindex)删除index所指的地方的对象。3、查询搜索功能、查询搜索功能（1）publicfinalintindexOf(Objectobj)从向量头
3、开始搜索obj,返回所遇到的第一个obj对应的下标，若不存在此obj，返回-1。（2）publicfinalsynchronizedintindexOf(Objectobj,intindex)从index所表示的下标处开始搜索obj。（3）publicfinalintlastIndexOf(Objectobj)从向量尾部开始逆向搜索obj。（4）publicfinalsynchronizedintlastIndexOf(Objectobj,intindex)从index所表示的下标处由尾至头逆向搜索obj。（5）publicfinalsynchronizedObjectfirstElement
4、()获取向量对象中的首个obj。（6）publicfinalsynchronizedObjectlastelement()获取向量对象中的最后一个obj。4、向量类的其它方法、向量类的其它方法（1）publicfinalintsize()此方法用于获取向量元素的个数。（2）publicfinalsynchronizedvoidsetsize(intnewsize)此方法用来定义向量大小。11.2 堆栈（堆栈（Stack）1、堆栈的特性Stack类是Vector类的子类。堆栈“先进后出”，只在桟顶操作Stack是一个容器，并具有以下特性：（1）堆栈是有次序的，堆栈数据结构只允许数据自有序列表的固
5、定端(前端)做输入、输出操作，因此，最后被输入的数据项会最先被取出来。（2）对堆栈的操作只能在一个名为top的位置上。用Push方法在堆栈顶部增加新的对象，用pop方法删除堆栈顶部的对象，也可以查询堆栈项部的对象。（3）用MakeEmpty方法可以清除堆栈的对象，也可用1sEmpty来查询该堆栈是否为空，以及查询堆栈的人小。2、堆栈的方法（1）堆栈的构造方法：publicStack()：创建一个空Stack。（2）堆栈的方法：empty()：测试堆栈是否为空。peek()：查看栈顶对象而不移除它。pop()：移除栈顶对象并作为此函数的值返回该对象。push(Eitem)：把数据压入栈顶。sea
6、rch(Objecto)：返回对象在栈中的位置，以1为基数。11.3 哈希表哈希表(Hashtable)1、哈希表(Hashtable)的概念哈希表就是记录与关键字之间有一个确定的对应关系的存储方式，它提供了一种很重要的快速检索方法。其基本思想是将关系码的值作为自变量，通过一定的函数关系计算出对应的函数值，把这个数值解释为结点的存储地址，将结点存入计算得到存储地址所对应的存储单元。检索时采用检索关键码的方法。现在哈希表有一套完整的算法来进行插入、删除和解决冲突。在Java中哈希表用于存储对象，实现快速检索。2、哈希表的方法、哈希表的方法（1）构造方法哈希表类中提供了三种构造方法，分别是：pub
7、licHashtable()publicHashtable(intinitialcapacity)publicHashtable(intinitialCapacity,floatloadFactor)（2）插入publicsynchronizedvoidput(Objectkey,Objectvalue)给对象value设定一关键字key,并将其加到Hashtable中。若此关键字已经存在，则将此关键字对应的旧对象更新为新的对象Value。这表明在哈希表中相同的关键字不可能对应不同的对象(从哈希表的基本思想来看，这也是显而易见的)。（3）检索publicsynchronizedObjectge
8、t(Objectkey)根据给定关键字key获取相对应的对象。publicsynchronizedbooleancontainsKey(Objectkey)判断哈希表中是否包含关键字key。publicsynchronizedbooleancontains(Objectvalue)判断value是否是哈希表中的一个元素。（4）删除publicsynchronizedobjectremove(objectkey)从哈希表中删除关键字key所对应的对象。publicsynchronizedvoidclear()清除哈希表（5）另外，Hashtalbe还提供方法获取相对应的枚举集合：publicsy
9、nchronizedEnumerationkeys()返回关键字对应的枚举对象。publicsynchronizedEnumerationelements()返回元素对应的枚举对象。【例例11-5】创建学生成绩表，用学创建学生成绩表，用学号作关键字，如图号作关键字，如图11.5所示。所示。图11.5用学号作关键字的哈希表11.4 算法分析算法分析1、数组排序排序是把一组数据按照值的大小递增或递减的次序重新排列的过程，它是数据处理中常用的算法。利用数组的顺序存储特点，可方便的实现排序。排序的算法有多种，这里讨论较易理解的“冒泡排序”。“冒泡排序”的关键是对相邻的两个数组元素从后向前进行比较，若后
10、面的元素的值小于前面元素的值，则将这两个元素交换位置，否则不进行交换。依次进行下去，最小的值逐渐“上升”到数组顶部（即第一个元素），就像水中气泡的上浮，而较大的值则沉到数组底部。2、递归递归是程序设计中常用的算法。所谓递归，其基本思想就是“自己调用自己”，一个方法直接或间接地调用自身的方法。一个问题能否用递归实现，看其是否具有下面的特点：（1）需有完成任务的递推公式；（2）结束递归的条件。例如，求一个正整数例如，求一个正整数n的阶乘的阶乘n!，其定义为，其定义为n(n-1) n-2) 1 且定义且定义 0!=1，1!=1，比如，比如，4！4321。我们用递归方法来求解，其过程可表示如图我们用递归方法来求解，其过程可表示如图11.8所示的形式。所示的形式。习题十一习题十一1、设有一数列：a1=3，a2=8，an=2an-1+2an-2，使用堆栈结构输出an的若干项。2、编写一程序，用哈希表实现学生成绩单的存储与查询。
