Java11(第11章数据结构及算法分析).ppt

Java语言程序设计 清华大学出版社 第11章常见数据结构及算法分析 主要内容 1 向量2 堆栈3 哈希表4 算法分析 11 1向量类Vector 11 1 1向量类的构造方法向量类提供了三种构造方法 publicvector publicvector intinitialcapacity intcapacityIncrement publicvector intinitialcapacity 11 1 2向量类的功能方法 1 插入功能 1 addElement 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 从向量头开始搜索obj 返回所遇到的第一个obj对应的下标 若不存在此obj 返回 1 2 publicfinalsynchronizedintindexOf Objectobj intindex 从index所表示的下标处开始搜索obj 3 publicfinalintlastIndexOf Objectobj 从向量尾部开始逆向搜索obj 4 publicfinalsynchronizedintlastIndexOf Objectobj intindex 从index所表示的下标处由尾至头逆向搜索obj 5 publicfinalsynchronizedObjectfirstElement 获取向量对象中的首个obj 6 publicfinalsynchronizedObjectlastelement 获取向量对象中的最后一个obj 4 向量类的其它方法 1 publicfinalintsize 此方法用于获取向量元素的个数 2 publicfinalsynchronizedvoidsetsize intnewsize 此方法用来定义向量大小 11 2堆栈 Stack 1 堆栈的特性Stack类是Vector类的子类 堆栈 先进后出 只在桟顶操作 Stack是一个容器 并具有以下特性 1 堆栈是有次序的 堆栈数据结构只允许数据自有序列表的固定端 前端 做输入 输出操作 因此 最后被输入的数据项会最先被取出来 2 对堆栈的操作只能在一个名为top的位置上 用Push方法在堆栈顶部增加新的对象 用pop方法删除堆栈顶部的对象 也可以查询堆栈项部的对象 3 用MakeEmpty方法可以清除堆栈的对象 也可用1sEmpty来查询该堆栈是否为空 以及查询堆栈的人小 2 堆栈的方法 1 堆栈的构造方法 publicStack 创建一个空Stack 2 堆栈的方法 empty 测试堆栈是否为空 peek 查看栈顶对象而不移除它 pop 移除栈顶对象并作为此函数的值返回该对象 push Eitem 把数据压入栈顶 search Objecto 返回对象在栈中的位置 以1为基数 11 3哈希表 Hashtable 1 哈希表 Hashtable 的概念哈希表就是记录与关键字之间有一个确定的对应关系的存储方式 它提供了一种很重要的快速检索方法 其基本思想是将关系码的值作为自变量 通过一定的函数关系计算出对应的函数值 把这个数值解释为结点的存储地址 将结点存入计算得到存储地址所对应的存储单元 检索时采用检索关键码的方法 现在哈希表有一套完整的算法来进行插入 删除和解决冲突 在Java中哈希表用于存储对象 实现快速检索 2 哈希表的方法 1 构造方法哈希表类中提供了三种构造方法 分别是 publicHashtable publicHashtable intinitialcapacity publicHashtable intinitialCapacity floatloadFactor 2 插入publicsynchronizedvoidput Objectkey Objectvalue 给对象value设定一关键字key 并将其加到Hashtable中 若此关键字已经存在 则将此关键字对应的旧对象更新为新的对象Value 这表明在哈希表中相同的关键字不可能对应不同的对象 从哈希表的基本思想来看 这也是显而易见的 3 检索publicsynchronizedObjectget Objectkey 根据给定关键字key获取相对应的对象 publicsynchronizedbooleancontainsKey Objectkey 判断哈希表中是否包含关键字key publicsynchronizedbooleancontains Objectvalue 判断value是否是哈希表中的一个元素 4 删除publicsynchronizedobjectremove objectkey 从哈希表中删除关键字key所对应的对象 publicsynchronizedvoidclear 清除哈希表 5 另外 Hashtalbe还提供方法获取相对应的枚举集合 publicsynchronizedEnumerationkeys 返回关键字对应的枚举对象 publicsynchronizedEnumerationelements 返回元素对应的枚举对象 例11 5 创建学生成绩表 用学号作关键字 如图11 5所示 图11 5用学号作关键字的哈希表 11 4算法分析 1 数组排序排序是把一组数据按照值的大小递增或递减的次序重新排列的过程 它是数据处理中常用的算法 利用数组的顺序存储特点 可方便的实现排序 排序的算法有多种 这里讨论较易理解的 冒泡排序 冒泡排序 的关键是对相邻的两个数组元素从后向前进行比较 若后面的元素的值小于前面元素的值 则将这两个元素交换位置 否则不进行交换 依次进行下去 最小的值逐渐 上升 到数组顶部 即第一个元素 就像水中气泡的上浮 而较大的值则沉到数组底部 2 递归 递归是程序设计中常用的算法 所谓递归 其基本思想就是 自己调用自己 一个方法直接或间接地调用自身的方法 一个问题能否用递归实现 看其是否具有下面的特点 1 需有完成任务的递推公式 2 结束递归的条件 例如 求一个正整数n的阶乘n 其定义