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

《常见数据结构的Java实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第13章　常见数据结构的Java实现编写程序时，我们经常要和各种数据打交道，为处理这些数据所选用的数据结构对于程序的运行效率是非常重要的。在学习数据结构这门课程的时候，人们要编写具体的算法去实现相应的数据结构。例如：链表：需要实现链表建立、结点插入删除等算法；栈：需要实现进栈和出栈等操作；缺点：有些繁琐！第13章　常见数据结构的Java实现在jdk1.2之后，Java提供了许多已实现的常见数据结构的类。使用这些类创建数据结构时，就不需要再编写具体的算法，感觉像创建数组一样方便；建议：参考相关教材，熟知数据结构的相关原理，

2、以便于更熟练的用好这些类。第13章　常见数据结构的Java实现13.1链表(LinkedList)补充：动态数组(ArrayList)13.2栈13.3树集13.4　树映射13.5　散列集13.6　散列表补充：HashMap13.7向量13.1链表链表：由若干个称作结点的对象组成的一种数据结构：单链表：每个结点含有一个数据域和一个引用域双链表：每个结点含有一个数据域和两个引用域数组(静态)：优点：可以快速随机查找，适合存储大量数据缺点：使用之前必须定义大小；使用时大小不能动态改变，容易造成资源浪费或空间不足；增加、删除结

3、点时比较慢链表：优点：使用之前无需定义大小，使用时可以动态的增加或减少数据缺点：查找时候必须从第一个结点开始,相对较慢对比接口Listjava.util包中的一个接口，Collection是它的父接口该接口提供了若干方法，可以对列表中的元素进行精确地插入、删除、查找和修改。LinkedList：实现了List接口的双链表类ArrayList：实现了List接口的动态数组类注：详情请查看电子技术文档LinkedListArrayList列表创建链表(LinkedList)使用java.util包中的LinkedList类可

4、以创建一个双链表对象。如下操作创建了一个空链表：LinkedListmylist=newLinkedList()；由于LinkedList类实现了接口List，因此：Listlist=newLinkedList()；接口回调技术：把LinkedList对象的引用赋值给Collection接口变量或List接口变量，那么接口变量就可以调用类实现的接口方法创建动态数组(ArrayList)使用java.util包中的ArrayList类可以创建一个动态对象。如下操作创建了一个初始容量为10的空数组：ArrayListmyli

5、st=newArrayList()；如下操作创建了一个初始容量为n的空数组：ArrayListmylist=newArrayList(n)；//n为int型由于ArrayList类实现了接口List，因此：Listlist=newArrayList()；接口回调技术添加接点add()(LinkedList与ArrayList)publicbooleanadd(Objectelement)：将指定的元素追加到链表/数组的尾部添加的数据是参数elememt指定的对象例如：向列表中添加4个结点(每个结点中存放一个字符串)：my

6、list.add(“It”);mylist.add(“is”);mylist.add(“a”);mylist.add(“door”);注意事项(一)publicbooleanadd(Objectelement)列表中每个结点的数据必须是Object类的对象由于任何类都是Object类的直接或间接子类因此，列表结点中的数据可以是任何类创建的对象,但不能是基本数据类型。例如:向列表末尾添加一个新的结点list.add("a");//√list.add('a');//xlist.add(newCharacter('a'));/

7、/√list.add(1);//xlist.add(newInteger(1));//√基本数据类型引用数据类型类布尔类型：boolean数组接口字符类型：char数值类型浮点数类型：float，double整数类型：byte，short，int，long基本数据类型基本类型的包装类byteshortintlongdoublefloatbooleancharByteShortIntegerLongDoubleFloatBooleanCharacter基本类型包装类所在系统包：java.langP96注意事项(二)方法：p

8、ublicObjectget(intindex)作用：得到列表中指定位置处的元素中的对象(索引从0开始)注意：当列表调用get方法获取一个结点对象后，要用类型转换运算符将该对象转化回原来的类型Strings=(String)list.get(0);Integerit=(Integer)mylist.get(0);Sy