链表结构--课件

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