《游戏开发中常用数据结构和算法.ppt》由会员分享，可在线阅读，更多相关《游戏开发中常用数据结构和算法.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、深入深入Java编程编程专业教程理论讲解部分Ver3.1第018课 算法及数据结构概述：链表的使用重点：难点：链表的使用 链表的使用第018课 算法及数据结构3 链表 数组的缺陷:插入,删除的效率非常低数组大小不可变,无法实现动态生成.第018课 算法及数据结构链表的优势:解决了数组无法动态增长及减小的问题.插入删除的效率非常高导致用途非常广泛3 链表第018课 算法及数据结构3.1 链结点(Link)在链表中,每个数据项都被包含在“链结点”(Link)中。一个链结点是某个类的对象，这个类可以叫做Link。每个Link对象中都包含一个对下一个链结点引用的字段(通常叫做next)。但是链表本身的
2、对象中有一个字段指向对第一个链结点的引用。3 链表第018课 算法及数据结构 下面是一个Link类定义的一部分。它包含了一些数据和对下一个链结点的引用：class Linkpublic int iData;public double dData;public Link next;class Linkpublic inventoryItem iI;public Link next;一个int和double类型的数据,或者inventoryItem类型的li。一个对下一个Link的引用next3.1 链结点(Link)3 链表第018课 算法及数据结构3.2 依靠关系查询在数组中,我们使用的是位置
3、进行查询.在链表中,我们使用的是节点之间的关系进行查询查询的过程不同3 链表第018课 算法及数据结构3.3 MyLink下面是Node类,节点类,它描述了每一个节点所要保存的内容.class Nodeprivate 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类,链表类
4、.除了要包含Node,还要有一个头节点.private Node head;head描述了当前链表的第一个元素的引用,当一个链表拥有了头节点,也就意味着拥有了全部的链表.3.3 MyLink3 链表第018课 算法及数据结构链表的初始化当链表创建之初,仅仅拥有一个空的head就可以了.其内容是逐渐添加进去的public MyLine()head=null;此时,你已经拥有了一个链表,只是它是一个空链表.3.3 MyLink3 链表第018课 算法及数据结构节点的添加这里实现的是一个将链表自动增长的过程.首先,找到链表的尾部.然后,将新的节点添加到链表的尾部.3.3 MyLink3 链表publ
5、ic void addNode(int key,int value)if(head=null)head=new Node(key,value);elseNode current=head;while(current.next!=null)current=current.next;current.next=new Node(key,value);第018课 算法及数据结构节点的添加链表为空,直接将节点添加到head中尾部的查找新节点的添加3.3 MyLink3 链表第018课 算法及数据结构节点的查询 链表的查询只能从前向后依次进行,无法使用随机搜索.private Node getNode(i
6、nt key)Node current=head;if(head.key=key)return head;elsecurrent=head.next;while(current.key!=key)current=current.next;return current;3.3 MyLink3 链表第018课 算法及数据结构节点的删除节点的删除包括两个方面的内容待删除节点及其前继节点的查找将待删除节点删除3.3 MyLink3 链表第018课 算法及数据结构节点的删除Node current;Node parent;分别来描述当前正在查询的节点及其父节点.一旦当前节点与待删除节点相同则确认找到删除
7、节点并删除之.否则删除失败3.3 MyLink3 链表第018课 算法及数据结构节点的删除节点删除过程非常简单,只需要将其前继节点的next指向待删除节点的next就可以.除非有必要,需要对删除节点作相应处理,否则等待垃圾回收处理即可valuekeyvaluekeyvaluekeyparentcurrent3.3 MyLink3 链表第018课 算法及数据结构public boolean delNode(int key)Node current=head;Node parent;if(head=null)return false;else if(head.key=key)head=head.n
8、ext;return true;else确定链表不为空,否则删除失败头节点比较特殊,需要特殊处理3.3 MyLink3 链表第018课 算法及数据结构current=head.next;parent=head;while(current.key!=key)current=current.next;parent=parent.next;if(current!=null)parent.next=current.next;return true;else return false;查询待删除节点及其前继节点如果查到待删除节点则删除.否则删除失败3.3 MyLink3 链表第018课 算法及数据结构节
9、点的插入插入通常使用两种插入方式:按照位置插入,按照顺序插入.其思想不变,都是按照某种规则,找到待插入位置,然后进行插入操作.下面介绍插入时的操作3.3 MyLink3 链表第018课 算法及数据结构节点的插入valuekeyvaluekeyvaluekeyparentcurrent首先,找到待插入位置的前继节点parent.然后,将待插入节点current.next指向parent.next.最后,将parent.next指向插入节点current3.3 MyLink3 链表第018课 算法及数据结构节点的插入public boolean insertNode(Node newNode,in
10、t index)Node preNode=head;if(preNode=null|index=0)newNode.next=preNode;preNode=newNode;return true;elsewhile(preNode.next!=null&index-0)preNode=preNode.next;newNode.next=preNode.next;preNode.next=newNode;return true;节点位置的查找节点的插入3.3 MyLink3 链表小结：链表的创建 节点的添加 节点的查找 节点的删除 节点的插入第018课 算法及数据结构1、简述链表的创建及插入过程.小测验：第018课 算法及数据结构2、简述链表的查找及删除过程.3、简述链表的插入过程 实现有序链表的插入操作.课后作业：第018课 算法及数据结构