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

《Java语言程序设计基础教程课件(第12章).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第12章　常见数据结构的Java实现链表的基本操作栈树集树映射散列表散列集向量12.1链表线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列：(a1,a2,a3,…an)n为线性表的长度(n≥0)，n=0的表称为空表。线性表按其存储结构可分为顺序表和链表。用顺

2、序存储结构存储，也就是将线性表中的数据元素依次存放在某个存储区域中的表称为顺序表；用链式存储结构存储的线性表称为链表。一维数组是用顺序方式存储的线性表。单链表：每个节点含有一个数据和下一个节点对象的引用；双链表：含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用。12.1.1链表的创建使用java.util包中的LinkedList类，可以创建一个链表对象。例如：LinkedListmylist=newLinkedList();//创建了一个空双链表也可以使用add()方法向链表依次增加节点

3、。例如增加节点：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

4、=newLinkedList();mylist.add("It");//链表中的第一个节点。mylist.add("is");//链表中的第二个节点。mylist.add("a");//链表中的第三个节点。mylist.add("door");//链表中的第四个节点。intnumber=mylist.size();//获取链表的长度。for(inti=0;i

5、点中的数据:"+temp);}}}程序运行结果如下所示：12.1.2LinkedList类中的常用方法LinkedList的常用方法包括：publicbooleanadd(Objectelement)//向链表末尾添加一个新的节点，该节点中的数据是参数element指定的对象。publicvoidadd(intindex,Objectelement)//向链表指定位置添加节点，该节点中的数据是参数element指定的对象。publicvoidaddFirst(Objectelement)//向链表头添

6、加新节点，该节点中的数据是参数element指定的对象。publicvoidaddLast(Objectelement)//向链表尾添加新节点，该节点中的数据是参数element指定的对象。publicObjectremoveFirst()//删除第一个节点，并返回这个节点中的对象。publicObjectremoveLast()//删除最后一个节点，并返回这个节点中的对象。publicObjectremove(intindex)//删除指定位置的节点publicObjectget(intindex)

7、//得到指定位置的节点publicObjectgetFirst()//得到链表第一个节点的对象。publicObjectgetLast()//得到链表最后一个节点的对象。intindexOf(Objectelement)：返回节点对象element在链表中首次出现的位置，如果链表中无此节点对象则返回-1。publicintlastIndexOf(Objectelement)：返回节点对象element在链表中最后出现的位置，如果链表中无此节点对象则返回-1。publicObjectset(intind

8、ex,Objectelement)//将当前链表index位置节点中的对象替换成参数element指定的对象，返回被替换对象。publicintsize()//返回量表的长度，即节点的个数。publicbooleancontains(Objectelement)：判断链表节点对象中是否含有element。【例12-2】本例包含了LinkedList类中的一些常用方法。importjava.util.*;publicclassep12_2{publicst