13常见数据结构的Java实现.ppt

第13章　常见数据结构的Java实现 编写程序时，我们经常要和各种数据打交道，为处理这些数据所选用的数据结构对于程序的运行效率是非常重要的。 在学习数据结构这门课程的时候，人们要编写具体的算法去实现相应的数据结构。例如： 链表：需要实现链表建立、结点插入删除等算法； 栈：需要实现进栈和出栈等操作； 缺点：有些繁琐！ 第13章　常见数据结构的Java实现 在jdk1.2之后，Java提供了许多已实现的常见数据结构的类。 使用这些类创建数据结构时，就不需要再编写具体的算法，感觉像创建数组一样方便； 建议：参考相关教材，熟知数据结构的相关原理，以便于更熟练的用好这些类。 第13章　常见数据结构的Java实现 13.1　链表(LinkedList) 补充：动态数组(ArrayList) 13.2　栈 13.3　树集 13.4　树映射 13.5　散列集 13.6　散列表 补充：HashMap 13.7　向量 13.1 链表 链表：由若干个称作结点的对象组成的一种数据结构： 单链表：每个结点含有一个数据域和一个引用域 双链表：每个结点含有一个数据域和两个引用域 数组(静态)： 优点：可以快速随机查找，适合存储大量数据 缺点：使用之前必须定义大小；使用时大小不能动态改变，容易造成资源浪费或空间不足；增加、删除结点时比较慢 链表： 优点：使用之前无需定义大小，使用时可以动态的增加或减少数据 缺点：查找时候必须从第一个结点开始,相对较慢 接口List java.util包中的一个接口，Collection是它的父接口 该接口提供了若干方法，可以对列表中的元素进行精确地插入、删除、查找和修改。 LinkedList：实现了List接口的双链表类 ArrayList ：实现了List接口的动态数组类 注：详情请查看电子技术文档 LinkedList ArrayList 创建链表(LinkedList) 使用java.util包中的LinkedList类可以创建一个双链表对象。 如下操作创建了一个空链表： LinkedList mylist = new LinkedList()； 由于LinkedList类实现了接口List，因此： List list = new LinkedList()； 接口回调技术：把LinkedList对象的引用赋值给Collection接口变量或List接口变量，那么接口变量就可以调用类实现的接口方法 创建动态数组(ArrayList) 使用java.util包中的ArrayList类可以创建一个动态对象。 如下操作创建了一个初始容量为10的空数组： ArrayList mylist = new ArrayList()； 如下操作创建了一个初始容量为n的空数组： ArrayList mylist = new ArrayList(n)；//n为int型 由于ArrayList类实现了接口List，因此： List list = new ArrayList()； 接口回调技术 添加接点add()(LinkedList与ArrayList) public boolean add(Object element)： 将指定的元素追加到链表/数组的尾部 添加的数据是参数elememt指定的对象 例如：向列表中添加4个结点(每个结点中存放一个字符串)： mylist.add(“It”); mylist.add(“is”); mylist.add(“a”); mylist.add(“door”); 注意事项(一) public boolean add (Object element) 列表中每个结点的数据必须是Object类的对象 由于任何类都是Object类的直接或间接子类 因此，列表结点中的数据可以是任何类创建的对象,但不能是基本数据类型。 例如:向列表末尾添加一个新的结点 list.add(a); //√ list.add(a); //x list.add(new Character(a)); //√ list.add(1); //x list.add( new Integer(1) ); //√ 注意事项 (二) 方法：public Object get (int index) 作用：得到列表中指定位置处的元素中的对象 (索引从0开始) 注意：当列表调用get方法获取一个结点对象后， 要用类型转换运算符将该对象转化回原来的类型 String s = (String)list.get(0); Integer it = (Integer)mylist.get(0); System.out.println(Value()); Character ch = (Character