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

文档介绍：专业教程理论讲解部分 第 018 课算法及数据结构?概述: ?链表的使用?重点: ?难点: ?链表的使用?链表的使用第 018 课算法及数据结构 3 链表数组的缺陷:?插入,删除的效率非常低?数组大小不可变,无法实现动态生成. 第 018 课算法及数据结构链表的优势:?解决了数组无法动态增长及减小的问题. ?插入删除的效率非常高导致用途非常广泛 3 链表第 018 课算法及数据结构 链结点(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 链结点(Link) 3 链表第 018 课算法及数据结构 依靠关系查询?在数组中,我们使用的是位置进行查询. ?在链表中,我们使用的是节点之间的关系进行查询查询的过程不同 3 链表第 018 课算法及数据结构 MyLink 下面是 Node 类,节点类,它描述了每一个节点所要保存的内容. class Node{ private int key; private int value; private Node next; public Node(int key,int value){ = key; = value; next = null; }} key 键值,数据是依靠键值来查询的 value 数据,实际要存储的内容 next 下一个节点的引用. 3 链表第 018 课算法及数据结构 MyLink 类, Node, 还要有一个头节点. private Node head; head 描述了当前链表的第一个元素的引用,当一个链表拥有了头节点,也就意味着拥有了全部的链表. MyLink 3 链表第 018 课算法及数据结构链表的初始化当链表创建之初,仅仅拥有一个空的 head public MyLine() { head = null; }此时,你已经拥有了一个链表,只是它是一个空链表. MyLink 3 链表