常用的数据结构和算法3.ppt

* 让我们来举例说明链表不同于数组的主要特点之一。在一个数组中，每一项占用一个特定的位置。这个位置可以用一个下标号直接访问。它就像一徘房子，你可以凭地址找到其中特定的一间。 在链表中，寻找一个特定元索的惟一方法就是沿着这个元索的链一直向下寻找。它很像人们之间的关系。可能你问Harrv，Bob在哪。Harry不知道，但是他想Jane可能知道，所以你又去问Jane。Jane看到Bob和SaIIy一起离开了办公室，所以你打SalIy的手机，她说她在Pekr的办公室和Bob分开了，所以……但是总有线索。不能直接访问到数据项；必须使用数据之间的关系来定位它。你从第一项开始，到第二个．然后到第三个,直到发现要找的那个数据项。 专业教程 理论讲解部分 Ver3.1 第018课 算法及数据结构 概述： 链表的使用 重点： 难点： 链表的使用 链表的使用 第018课 算法及数据结构 3 链表 数组的缺陷: 插入,删除的效率非常低 数组大小不可变,无法实现动态生成. 第018课 算法及数据结构 链表的优势: 解决了数组无法动态增长及减小的问题. 插入删除的效率非常高 导致用途非常广泛 3 链表 第018课 算法及数据结构 3.1 链结点(Link) 在链表中,每个数据项都被包含在“链结点”(Link)中。一个链结点是某个类的对象，这个类可以叫做Link。每个Link对象中都包含一个对下一个链结点引用的字段(通常叫做next)。但是链表本身的对象中有一个字段指向对第一个链结点的引用。 3 链表 第018课 算法及数据结构 下面是一个Link类定义的一部分。它包含了一些数据和对下一个链结点的引用： class Link{ public int iData; public double dData; public Link next; } class Link{ public inventoryItem iI; public Link next; } 一个int和double类型的数据, 或者inventoryItem类型的li。 一个对下一个Link的引用next 3.1 链结点(Link) 3 链表 第018课 算法及数据结构 3.2 依靠关系查询 在数组中,我们使用的是位置进行查询. 在链表中,我们使用的是节点之间的关系进行查询 查询的过程不同 3 链表 第018课 算法及数据结构 3.3 MyLink 下面是Node类,节点类,它描述了每一个节点所要保存的内容. class Node{ private int key; private int value; private Node next; public Node(int key,int value){ this.key = key; this.value = value; next = null; } } key 键值,数据是依靠键值来查询的 value 数据,实际要存储的内容 next 下一个节点的引用. 3 链表 第018课 算法及数据结构 MyLink类,链表类.除了要包含Node,还要有一个头节点. private Node head; head描述了当前链表的第一个元素的引用,当一个链表拥有了头节点,也就意味着拥有了全部的链表. 3.3 MyLink 3 链表 第018课 算法及数据结构 链表的初始化 当链表创建之初,仅仅拥有一个空的head就可以了.其内容是逐渐添加进去的 public MyLine() { head = null; } 此时,你已经拥有了一个链表,只是它是一个空链表. 3.3 MyLink 3 链表 第018课 算法及数据结构 节点的添加 这里实现的是一个将链表自动增长的过程. 首先,找到链表的尾部. 然后,将新的节点添加到链表的尾部. 3.3 MyLink 3 链表 public void addNode(int key,int value){ if(head == null){ head = new Node(key,value); }else{ Node current = head; while(current.next != null){ current = current.next; } current.next = new Node(key,value); } } 第018课 算法及数据结构 节点的添加 链表为空,直接将节点添加到head中 尾部的查找 新节点的添加 3.3 MyLink 3 链表 第018课 算法及数据结构 节点的查询 链表的查询只能从前向后依次进行,