《链表结构课件.ppt》由会员分享，可在线阅读，更多相关《链表结构课件.ppt（30页珍藏版）》请在三一办公上搜索。
1、第一章,链表,1,t课件,课程目标,链表的概念链表的基本操作建表添加节点删除节点按序号查找定位其他链表循环链表双链表,2,t课件,本章的体验项目,程序实现的功能：遍历整个链表,运行的结果如图1-1所示,这幅图也说明了链表的结构：螳螂捕蝉黄雀在后,下面开始给大家详细的讲解链表,3,t课件,1.1链表的概念,在前面我们讲过数组的概念，我们看到数组作为数据存储结构有一定的缺陷：在无序数组中，搜索是低效的而在有序数组中插入效率又很低不管在哪一种数组中删除效率都很低创建一个数组之后，它的大小又是不可变的,4,t课件,在本章中，我们将看到一种新的数据存储结构，它可以解决上面的一些问题，这种数据存储结构就是
2、链表。,什么是链表？,链表是一种有序的列表。链表的内容通常存储与内存中分散的位置上。 链表由节点组成，每一个节点的结构都相同。节点分为数据域和链域，数据域顾名思义就是存放节点的内容，链域存放的是下一个节点的指针，也就是我们一开始说的螳螂捕蝉黄雀在后。,5,t课件,1.1.1节点,在链表中，每个数据项都被包括在“节点”(Node)中。节点是某个类的对象，这个类可以叫做Node。因为一个链表中有许多类似的节点，所以有必要用一个描述节点的类来表达节点。每个Node对象中都包含一个对下一个节点引用的字段（通常叫做next）。,数据域，用于存储节点的数据元素,链域，用于存放下一个节点对象,6,t课件,下
3、面的Node类定义了一个节点。它包含了一些数据和对下一个节点的引用,class Nodepublic int iDate;public double dDate; public Node next;,数据域,链域,7,t课件,这种类定义有时叫做“自引用”式，因为它包含了一个和自己类型相同的字段（本例中叫做next）。节点中仅包含两个数据项：一个int 类型的数据，一个 double 类型的数据。 在一个真正的应用程序中，可能包含更多的数据项。例如，一条个人纪录可能有名字、地址、社会保险好、头衔、工资和其他许多字段。通常，用一个包含这些数据的类的对象来代替这些数据项：,8,t课件,class N
4、odepublic Person person;public Node next;class Personpublic name; public age;public sex;,节点内容,指向下一节点,9,t课件,1.1.2链表的基本运算,初始化，加工型运算，其作用是建立一个空表L=null求表长，引用型运算，其结果是链表的长度，即有几个节点。读链表节点，引用型运算，若1i链表的长度,其结果是链表的第i个节点；否则，结果为一特殊定位（按值查找），引用型运算。插入，加工型运算。删除，加工型运算。这些运算在后面个小节为大家详细讲解,10,t课件,1.2 链表的操作,1.2.1 建表使用链表首先就是
5、要建表，也称作链表的初始化。为了便于实现各种运算，通常在链表的第一个节点之前增设一个类型相同的节点，称之为头节点，其他节点成为表节点或节点。建表就是建立一个如图所示的空表，空表由一个头引用和一个头节点（该节点同时也是为节点）组成。,头节点的结构和普通节点一样，只是通常不用于存取数据,11,t课件,1.2.2插入节点,在链表中插入节点是链表操作的优势。在链表中插入节点和添加节点的概念是不同的。插入节点是将一个节点放入链表中间而不是简单的追加在链表。链表的插入节点以及后面要讲的删除节点中，不必像以前的数组那样先将表中元素整体前移或后移，只需将欲插入位置的前一节点指向该节点并将该节点指向后一节点即可
6、。,12,t课件,插入节点的步骤,第一步：找到插入位置的前一个节点node1。第二步：生成要插入的节点node2。第三步：将node2指向node1得下一个节点，然后将node1 指向node2。这样一个节点就被插入到链表中了。public void addNode(Node node)node.next=this.next;/将新添加的节点指向以前节点的下一节点this.next=node;/将本节点指向要添加的节点,13,t课件,1.2.3删除节点,节点a,a的前趋,a的后继,两个概念：前趋，后继,14,t课件,删除节点的原理,让a的前趋指向a的后继。这样就达到将节点a删除的目的。（图中粗
7、线部分）,至于节点a，会由Java垃圾回收器将其销毁,15,t课件,ublic boolean delNode(String nodeName)Node p=head;if(!p.hasNext()System.out.println(此表为空);return false;while(p.hasNext()if(p.getNext().getName().equals(nodeName)p.setNext(p.getNext().getNext();break;p=p.getNext();return true;,寻找节点,删除节点,16,t课件,在链表中做删除操作的优缺点,在链表中做删除操作
8、的优点链表删除与数组删除的优点就是只要操作被删节点的前趋与后继，不需把所有的数据进行移动，这样就极大的节省了系统消耗。在链表中做删除操作的缺点当然这也有不足的地方，就是删除一个特定的节点时一定要先从头节点开始遍历，一直寻找到被删节点的前趋为止。,17,t课件,1.2.4按序号查找,按序号查找是链表的一种常用运算，其功能是对给定的参数i查找链表的第i个节点。在链表中，由于逻辑相邻的节点并不是存储在物理相邻的单元中，所以不能像顺序表那样，直接按序号i查找节点，在链表中只能从头节点出发，顺链域next逐个往下搜索，直到找到第i个节点为止。,18,t课件,Node node=head; int i=0
9、; System.out.println(-开始遍历-);while(node!=null) if(i= =2)System.out.println(“被查找的节点为：+node.getName(); break; i+;node=node.getNext();,查找第2个节点叫什么名字,生成一个节点对象帮助遍历,工作节点不断指向链表的下一个,19,t课件,1.2.5定位,定位和按序号查找意思差不多，又称按值查找。第一个值与要查找的值相等的节点序号就是运算结果 。方法：从头节点开始遍历，取每一个节点的值与被查找的值进行比较。如果相等则退出循环并取得该节点的序号，否则让工作节点再指向下一个继续寻
10、找。,20,t课件,1.3其他链表,我们以上所讲的操作都是基于单链表讲解的。除单链表之外链式存储结构还有,单向循环链表（简称循环链表）,双向循环链表（简称双链表）,21,t课件,1.3.1循环链表,循环链表与单链表的区别仅仅在于其尾节点的链域值不是null，而是一个指向头节点的引用。,该节点指向首节点,循环链表的主要优点,从表中任一节点出发都能通过后移操作而扫描整个循环链表。而对单链表来说，只有从头节点开始才能扫描表中全部节点,22,t课件,1.3.2双链表,在单链表中，每个节点所含的链域指向其后继节点，故从任一节点找其后继很方便。但要找前趋节点则比较困难。若在每个节点中增加一个链域，所含引用
11、所指向前趋节点，则可以克服上述困难。这样构成的链表中有两个方向不同的链域，称为双链表。,双链表的节点形式如图所示,指向前趋,指向后继,23,t课件,所有节点通过前趋引用和后继引用链接在一起，再加上起标识作用的头节点，就得到双向循环链表，简称双链表,双链表节点的定义形式为,class NodeString nodeName;Node prior;Node next;,24,t课件,双链表删除节点,设p指向待删除节点 p.getPrior().setNext(p.getNext(); p.getNext().setPrior(p.getPrior();,使p的前趋指向p的后继,使p的后继指向p的前
12、趋,注意：在单链表上作删除时，工作节点须指向待删除节点的前趋节点,25,t课件,双链表插入节点,设在节点node1后面链入一个新节点node2，需以下四步node2.setPrior(node1);node2.setNext(node1.getNext();node1.getNext().setPrior(node2);node1.setNext(node2);,注：四句代码的顺序不可以颠倒,26,t课件,拓展,JDK中提供的链表JDK也给我们提供了一种链表数据结构：java.util.LinkedList，我们可以方便的使用它。声明链表LinkedList list=new LinkedLi
13、st();添加节点,boolean add(E o),void add(int index,E element),将节点添加到链表的末尾,将节点插入到指定的位置,27,t课件,链表的遍历,LinkedList类没有提供遍历链表的类，而是通过工厂方法获得Iterator接口的实例，然后通过调用next()方法输出每一个元素。 不足的是Iterator中没有提供类似的add()方法。幸运的是Java数据结构库中提供了一个Iterator的子接口：ListIterator，由它定义了一个add()方法。这个方法同LinkedList中的add()方法是不同的，在它添加以后不返回boolean值，也就
14、是假定添加总是成功的。,28,t课件,LinkedList中常用的方法,LinkedList()创建一个控链表LinkedList(Collection elements)创建一个链表，并把elements的所有元素插入这个链表boolean add(Object element)在链表尾部插入一个元素void add(int index,Object element)在链表指定位置插入一个元素void addFirst(Object element)在列表头部插入一个元素void addLast(Object element)在列表尾部插入一个元素Object getFirst(Object element)返回列表头部的元素Object getLast(Object element)返回列表尾部的元素Object removeFirst(Object element)删除并返回列表第一个元素Object removeLast(Object element)删除并返回列表最后一个元素,29,t课件,小结,本章通过学习下列知识 链表的概念 链表的基本操作 建表 添加节点 删除节点 按序号查找 定位 其他链表 循环链表 双链表,30,t课件,
