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

第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类可以创建一个双链表对象。如下操作创建了一个空链表：LinkedListmylist=newLinkedList()；由于LinkedList类实现了接口List，因此：Listlist=newLinkedList()；接口回调技术：把LinkedList对象的引用赋值给Collection接口变量或List接口变量，那么接口变量就可以调用类实现的接口方法创建动态数组(ArrayList)使用java.util包中的ArrayList类可以创建一个动态对象。如下操作创建了一个初始容量为10的空数组：ArrayListmylist=newArrayList()；如下操作创建了一个初始容量为n的空数组：ArrayListmylist=newArrayList(n)；//n为int型由于ArrayList类实现了接口List，因此：Listlist=newArrayList()；接口回调技术添加接点add()(LinkedList与ArrayList)publicbooleanadd(Objectelement)：将指定的元素追加到链表/数组的尾部添加的数据是参数elememt指定的对象例如：向列表中添加4个结点(每个结点中存放一个字符串)：mylist.add(“It”);mylist.add(“is”);mylist.add(“a”);mylist.add(“door”);注意事项(一)publicbooleanadd(Objectelement)列表中每个结点的数据必须是Object类的对象由于任何类都是Object类的直接或间接子类因此，列表结点中的数据可以是任何类创建的对象,但不能是基本数据类型。例如:向列表末尾添加一个新的结点list.add(a);//√list.add('a');//xlist.add(newCharacter('a'));//√list.add(1);//xlist.add(newInteger(1));//√基本数据类型引用数据类型类布尔类型：boolean数组接口字符类型：char数值类型浮点数类型：float，double整数类型：byte，short，int，long基本数据类型基本类型的包装类byteshortintlongdoublefloatbooleancharByteShortIntegerLongDoubleFloatBooleanCharacter基本类型包装类所在系统包：java.lang注意事项(二)方法：publicObjectget(intindex)作用：得到列表中指定位置处的元素中的对象(索引从0开始)注意：当列表调用get方法获取一个结点对象后，要用类型转换运算符将该对象转化回原来的类型Strings=(String)list.get(0);Integerit=(Integer)mylist.get(0);System.out.println(it.intValue());Characterch=(Character)mylist.get(0);System.out.println(ch.charValue());List接口中的常用方法publicbooleanadd(Objectelement)：向列表末尾添加一个新的结点，该结点中的数据是参数elememt指定的对象publicvoidadd(intindex,Objectelement)：向列表的指定位置添加一个新的结点，该结点中的数据是参数elememt指定的对象publicObjectremove(intindex)删除指定位置上的结点publicbooleanremove(Objectelement)删除首次出现含有数据elemen的结点publicvoidclear()删除列表的所有结点，使当前列表成为空列表List接口中的常用方法publicObjectget(intindex)：得到列表中指定位置处结点中的对象publicintindexOf(Objectelement)：返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回-1publicintlastindexOf(Objectelement)：返回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回-1publicObjectset(intindex,Eelement)：用指定元素替换列表中指定位置的元素intsize()：返回列表中的元素数。LinkedList类中的新增方法publicvoidaddFirst(Objectelement)：向列表的头添加新结点，该结点中的数据是参数elememt指定的对象的引用publicvoidaddLast(Objectelement)：向列表的末尾添加新结点，该结点中的数据是参数elememt指定的对象publicObjectremoveFirst()：删除第一个结点，并返回这个结点中的对象publicObjectremoveLast()：删除最后一个结点对象，并返回这个结点中的对象LinkedList类中的新增方法publicObjectgetFirst()：得到列表中第一个结点中的对象。publicObjectgetLast()：得到列表中最后一个结点中的对象请参见教材例题ArrayList类中的新增方法voidtrimToSize()：将此ArrayList实例的容量调整为列表的当前大小voidensureCapacity(intminCapacity)：增加此ArrayList实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数请编写应用程序，用LinkedList的常用方法来完成四小花旦的换届选举。赵薇—章子怡—周迅—徐静蕾原四小花旦新四小花旦赵薇—周迅—李冰冰—范冰冰importjava.util.*;publicclassFourStar{publicstaticvoidmain(String[]args){Listlist=newLinkedList();list.add(赵薇);list.add(章子怡);list.add(周迅);list.add(徐静蕾);System.out.println(---原四小花旦--:);printList(list);list.remove(徐静蕾);list.remove(章子怡);list.add(李冰冰);list.add(范冰冰);System.out.println(***新四小花旦***:);printList(list);}赵薇—章子怡—周迅—徐静蕾赵薇—周迅—李冰冰—范冰冰---原四小花旦--:赵薇章子怡周迅徐静蕾***新四小花旦***:赵薇周迅李冰冰范冰冰staticvoidprintList(Listlist){intlen=list.size();for(inti=0;ilen;i++){Strings=(String)list.get(i);System.out.println(s);}}}遍历列表(Iterator)列表对象可以使用iterator()方法获取一个Iterator对象；Iterator对象中每个数据成员刚好是列表结点中的数据，而且这些数据成员是按顺序存放在Iterator对象中的。Iterator对象使用next()方法可以得到它中的数据成员。注意：使用Iterator对象遍历链表要比链表使用get方法遍历链表的速度快。迭代器Iterator的方法摘要booleanhasNext()如果仍有元素可以迭代，则返回true。Objectnext()返回下一个元素。voidremove()移除最后一个元素。ArrayList与LinkedList都可以获得一个Iterator对象来遍历。13.2栈栈是一种“后进先出”的数据结构，只能在一端进行输入或输出数据的操作。操作特点：栈把第一个放入该栈的数据放在最底下，而把后续放入的数据放在已有数据的顶上。向栈中输入数据的操作称为“压栈”，从栈中输出数据的操作称为“弹栈”。13.2栈后进先出的来历：由于栈总是在顶端进行数据的输入输出操作，所以弹栈总是输出(删除)最后压入栈中的数据。就像一个每次只能容纳一个人进出的死胡同。13.2栈使用java.util包中的Stack类，可以创建一个栈对象。栈对象可以使用publicObjectpush(Objectdata);输入(加入)数据，实现压栈操作.使用publicObjectpop();输出(删除)数据，实现弹栈操作。使用publicbooleanempty();判断栈是否还有数据，有数据返回false，否则返回true。13.2栈使用publicObjectpeek();查看栈顶端的数据，但不删除该数据。使用publicintsearch(Objectdata);获取数据在栈中的位置，最顶端的位置是1，向下依次增加；如果堆栈不含有此数据，则返回-1；13.2栈栈是很灵活的数据结构，使用它可以节省内存的开销。比如，递归是一种很消耗内存的算法，我们可以借助于栈消除大部分的递归算法，达到和递归算法相同的目的。13.3树集树集：是一些结点组成的数据结构，结点按着树形一层一层的排列（完全二叉树）。TreeSet类可以创建一个树集对象：结点添加顺序：与链表不同的是，用add()方法增加结点时，结点会按其存放的数据的“大小”一层一层地依次排列；结点排放顺序：在同一层中的结点从左到右递增排列，下一层的都比上一层的小。13.3树集1.构造方法TreeSet()：使用java.util包中TreeSet类的构造方法来创建一个树集，例如：TreeSetmytree=newTreeSet();使用add()方法为树集添加结点，例如：add(“boy”)；两个字符串对象s1和s2可以使用s1.compare(s2)比较大小：s1.compare(s2)