Java语言程序设计基础教程课件(第12章)

第12章常见数据结构的Java实现链表的基本操作栈树集树映射散列表散列集向量12.1链表线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列：(a1,a2,a3,…an)n为线性表的长度(n≥0)，n=0的表称为空表。线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储，也就是将线性表中的数据元素依次存放在某个存储区域中的表称为顺序表；用链式存储结构存储的线性表称为链表。一维数组是用顺序方式存储的线性表。单链表：每个节点含有一个数据和下一个节点对象的引用；双链表：含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用。12.1.1链表的创建使用java.util包中的LinkedList类，可以创建一个链表对象。例如：LinkedListmylist=newLinkedList();//创建了一个空双链表也可以使用add()方法向链表依次增加节点。例如增加节点：mylist.add(“It”);mylist.add(“is”);mylist.add(“a”);mylist.add(“door”);这样就形成了4个节点的链表，数据依次为“It”、“is”、“a”、“door”，4个节点是自动链接的。【例12-1】本例构造一个含有４个节点的链表，并输出节点中的数据。importjava.util.*;publicclassLinkListOne{publicstaticvoidmain(Stringargs[]){LinkedListmylist=newLinkedList();mylist.add(It);//链表中的第一个节点。mylist.add(is);//链表中的第二个节点。mylist.add(a);//链表中的第三个节点。mylist.add(door);//链表中的第四个节点。intnumber=mylist.size();//获取链表的长度。for(inti=0;inumber;i++){Stringtemp=(String)mylist.get(i);System.out.println(第+i+节点中的数据:+temp);}}}程序运行结果如下所示：12.1.2LinkedList类中的常用方法LinkedList的常用方法包括：publicbooleanadd(Objectelement)//向链表末尾添加一个新的节点，该节点中的数据是参数element指定的对象。publicvoidadd(intindex,Objectelement)//向链表指定位置添加节点，该节点中的数据是参数element指定的对象。publicvoidaddFirst(Objectelement)//向链表头添加新节点，该节点中的数据是参数element指定的对象。publicvoidaddLast(Objectelement)//向链表尾添加新节点，该节点中的数据是参数element指定的对象。publicObjectremoveFirst()//删除第一个节点，并返回这个节点中的对象。publicObjectremoveLast()//删除最后一个节点，并返回这个节点中的对象。publicObjectremove(intindex)//删除指定位置的节点publicObjectget(intindex)//得到指定位置的节点publicObjectgetFirst()//得到链表第一个节点的对象。publicObjectgetLast()//得到链表最后一个节点的对象。intindexOf(Objectelement)：返回节点对象element在链表中首次出现的位置，如果链表中无此节点对象则返回-1。publicintlastIndexOf(Objectelement)：返回节点对象element在链表中最后出现的位置，如果链表中无此节点对象则返回-1。publicObjectset(intindex,Objectelement)//将当前链表index位置节点中的对象替换成参数element指定的对象，返回被替换对象。publicintsize()//返回量表的长度，即节点的个数。publicbooleancontains(Objectelement)：判断链表节点对象中是否含有element。【例12-2】本例包含了LinkedList类中的一些常用方法。importjava.util.*;publicclassep12_2{publicstaticvoidmain(Stringargs[]){LinkedListlist=newLinkedList();list.add(is);list.add(a);intnumber=list.size();System.out.println(现在链表中有+number+个节点：);for(inti=0;inumber;i++){Stringtemp=(String)list.get(i);System.out.println(第+i+节点中的数据：+temp);}list.add(0,It);number=list.size();list.add(number-1,door);number=list.size();System.out.println(现在链表中有+number+个节点：);for(inti=0;inumber;i++){Stringtemp=(String)list.get(i);System.out.println(第+i+节点中的数据：+temp);}list.remove(0);list.remove(1);list.set(0,open);number=list.size();System.out.println(现在链表中有+number+个节点：);for(inti=0;inumber;i++){Stringtemp=(String)list.get(i);System.out.println(第+i+节点中的数据：+temp);}}}程序运行后的效果如下所示：12.1.3使用Iterator类遍历链表迭代器（Iterator）模式，又叫做游标（Cursor）模式。它的定义为：提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。从定义可见，迭代器模式是为容器而生。很明显，对容器对象的访问必然涉及到遍历算法。迭代器给我们提供了一种通用的方式来访问集合中的元素。BooleanhasNext()：如果仍有元素可以迭代，则返回true。Objectnext()：返回迭代的下一个元素。voidremove()：从迭代器指向的集合中移除迭代器返回的最后一个元素。使用Iterator接口遍历链表：一个链表对象可以使用iterator()方法获取Iterator变量，Iterator对象中每个数据成员刚好是链表节点中的数据，而且这些数据成员是按顺序存放在Iterator对象中的，Iterator对象使用next()方法可以得到其中的数据成员。在例子12-1和例子12-2中我们借助get方法实现了遍历链表。我们可以借助Iterator对象实现遍历链表，一个链表对象可以使用iterator()方法获取一个Iterator对象，后者使用next()方法遍历链表。在下面的例子12-3中，我们把学生的成绩存放在一个链表中，并实现了遍历链表。【例12-3】这个例子中，把学生的成绩存放在一个链表中，并实现了遍历链表。importjava.util.*;classStudent{Stringname;intnumber;floatscore;Student(Stringname,intnumber,floatscore){this.name=name;this.number=number;this.score=score;}}publicclassLinkListThree{publicstaticvoidmain(Stringargs[]){LinkedListmylist=newLinkedList();Studentstu_1=newStudent(赵好民,9012,80.0f),stu_2=newStudent(钱小青,9013,90.0f),stu_3=newStudent(孙力枚,9014,78.0f),stu_4=newStudent(周左右,9015,55.0f);mylist.add(stu_1);mylist.add(stu_2);mylist.add(stu_3);mylist.add(stu_4);Iteratoriter=mylist.iterator();while(iter.hasNext()){Studentte=(Student)iter.next();System.out.println(te.name++te.number++te.score);}}}程序运行后的效果如下所示：12.2栈栈（Stack）也是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，是一种后进先出（LIFO）的数据结构。只能在一端进行输入或输出数据的操作，堆栈把第一个放入该堆栈的数据放在最底下，而把后续放入的数据放在已有数据的顶上，表尾称为栈顶（top），表头称为栈底（bottom）。栈的物理存储可以用顺序存储结构，也可以用链式存储结构。向堆栈中输入数据的操作称为“压栈”，从栈中输出数据的操作称为“弹栈”。12.2.1栈的常用方法使用java.util包中的Stack类创建一个堆栈对象，堆栈对象可以使用以下方法：publicObjectpush(Objectdata)//输入数据，实现压栈操作publicObjectpop()//输出数据，实现弹栈操作publicbooleanempty()//测试堆栈是否为空。如果空，返回true，否则返回falsepublicobjectpeek()//查看堆栈顶端的数据，但不删除该数据。publicintsearch(Objectdata)//返回对象在栈中的位置，最顶端的位置是１，向下依次增加，如果堆栈不含此数据，则返回-1。【例12-5】本例将数字１，２，３，４，５，6压入堆栈，然后弹出。importjava.util.*;classStackOne{publicstaticvoidmain(Stringargs[]){Stackmystack=newStack();mystack.push(newInteger(1));mystack.push(newInteger(2));mystack.push(newInteger(3));mystack.push(newInteger(4));mystack.push(newInteger(5));mystack.push(newInteger(6));while(!(mystack.empty())){Integertemp=(Integer)mystack.pop();System.out.print(+temp.toString());}}}程序运行后的结果如下所示：堆栈是很灵活的数据结构，使用堆栈可以节省内存的开销。比如，递归是一种很消耗内存的算法，我们可以借助堆栈消除大部分递归，达到和递归算法同样的目的。Fibonacii整数序列是我们熟悉的一个递归序列，它的第n