欢迎来到第壹文秘! | 帮助中心 分享价值,成长自我!
第壹文秘
全部分类
  • 幼儿/小学教育>
  • 中学教育>
  • 高等教育>
  • 研究生考试>
  • 外语学习>
  • 资格/认证考试>
  • 论文>
  • IT计算机>
  • 法律/法学>
  • 建筑/环境>
  • 通信/电子>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 第壹文秘 > 资源分类 > PPT文档下载
    分享到微信 分享到微博 分享到QQ空间

    Java数据结构链表.ppt

    • 资源ID:156449       资源大小:4.50MB        全文页数:33页
    • 资源格式: PPT        下载积分:10金币
    快捷下载 游客一键下载
    账号登录下载
    三方登录下载: 微信开放平台登录 QQ登录
    下载资源需要10金币
    邮箱/手机:
    温馨提示:
    快捷下载时,如果您不填写信息,系统将为您自动创建临时账号,适用于临时下载。
    如果您填写信息,用户名和密码都是您填写的【邮箱或者手机号】(系统自动生成),方便查询和重复下载。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP,免费下载
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    Java数据结构链表.ppt

    Java数据结构链表学习目标链表的概念单链表双链表数组的缺点数组是很有用的数据结构,但是有两个局限:若改变数据的大小就需要创建一个新数组并从原数组中拷贝所有数据至新数组;数组数据在内存中依次连续存储,向数组中插入一项要移动数组中其他数据。链表的概念链表这种数据结构是使用指针(即引用)将存储数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点,因而在插入或者删除时不再需要移动元素来腾出空间或填补空缺。需要作出的改变就是在每个单元中设置指针来表示表中元素之间的逻辑关系(前还是后)。因此每个单元至少有两个域,一个用于数据元素的存储,一个用于指向其他单元的指针。这种具有一个数据域和多个指针域的存储单元称为节点(Node)。链表的图示 数据 指针node(节点)节点本身就是对象节点的设计节点接口public interface Node /获取节点数据域public Object getData();/设置节点数据域public void setData(Object obj);单链表单链表的每个节点只有一个指向表中下一个节点的指针。第一个节点称为首节点,最后一个称为尾节点。尾节点的特征是next引用为空(null)。a0nextnodenodea1next单链表节点的设计除了需要实现Node接口定义的获取和设置数据域的两个方法以外,还需要提供对指向下一节点的指针的操作方法。为此提供两个方法,getNext()和setNext(Node node)。public class SinglyLinkedNode implements Node private Object obj;private SinglyLinkedNode next;单链表节点的设计(续)public SinglyLinkedNode() this(null, null);public SinglyLinkedNode(Object obj, SinglyLinkedNode next) this.obj = obj;this.next = next;单链表节点的设计(续)public SinglyLinkedNode getNext() return next;public void setNext(SinglyLinkedNode next) this.next = next;public Object getData() return obj;public void setData(Object obj) this. obj = obj;单链表的设计单链表的一个重要特性是只能通过前驱节点找到后续节点,而无法从后续节点找到前驱节点。因此在单链表中进行查找操作,只能从链表的首节点开始,通过每个节点的next引用来依次访问链表中的每个节点以完成相应的查找操作。为使程序更简洁,通常在单链表的最前面添加一个哑元节点,也称为头节点(Head),注意,有别于真正的首节点,头节点中不存储任何实质的数据对象,其next通常指向0位的元素。单链表的设计(续)通用的单链表类的初始化public class SinglyLinkedList /头节点private SinglyLinkedNode head;/元素个数private int size;public SinglyLinkedList() head = new SinglyLinkedNode();/为什么新建了SinglyLinkedNode类的对象,size还设为0?size = 0;单链表的设计(续)通用的单链表类的查找方法给定索引,返回节点public Object get(int index) throws IndexOutOfBoundsException if (size()=0) /添加size()方法return null; else if (index = size() throw new IndexOutOfBoundsException(); else SinglyLinkedNode node = head.getNext();for (; index 0; index-) node = node.getNext();return node.getData();单链表的设计(续)通用的单链表类的查找方法给定对象,返回索引public int indexOf(Object obj)SinglyLinkedNode node = head.getNext();int index = 0;while(node!=null)if(node.getData().equals(obj)return index;elseindex+;node = node.getNext();return -1;/如果没找到,返回-1练习请设计并实现操作单链表的方法:判断单链表结构中是否包含指定对象public boolean contains(Object obj)单链表的设计(续)对于任何基于序号的插入、删除,以及任何基于数据元素所在节点的前面或后面的插入、删除,在带头节点的单链表中均可转化为在某个特定节点之后完成节点的插入、删除,而不用考虑插入、删除是在链表的首部、中间还是尾部等不同情况。练习请设计并实现操作单链表的方法:将指定数据元素插入到链表尾部public void add(Object o)将指定数据元素插入到链表中指定位置public void add(int index,Object o)删除链表中指定位置的数据元素public boolean remove(int index)删除链表中第一次出现的指定数据元素public boolean remove(Object o)双链表双向链表是对单链表的扩充,以弥补单链表只能访问后续节点而不方便访问前驱节点的缺憾。双向链表的结构是在单链表的节点结构上新增加一个域,用来指向直接前驱节点。双向链表的图示Element(数据元素)Pointer(引用)Element (数据元素)Pointer(引用)Element(数据元素)Pointer(引用)nextprevnodenodenode节点双链表节点的设计除了需要实现Node接口定义的获取和设置数据域的两个方法以外,还需要提供对指向上下节点的指针的操作方法。为此提供四个方法,getNext()、setNext(Node node)、getPre()、setPre(Node node)public class DLinkedNode implements Node private Object obj;private DLinkedNode next;private DLinkedNode pre;双链表节点的设计(续)public DLinkedNode() this(null, null,null);public DLinkedNode(Object obj, DLinkedNode pre, DLinkedNode next) this.obj = obj;this.pre = pre;this.next = next;双链表节点的设计(续)public DLinkedNode getPre() return pre;public void setPre(DLinkedNode pre) this.pre = pre;public DLinkedNode getNext() return next;public void setNext(DLinkedNode next) this.next = next;public Object getData() return obj;public void setData(Object obj) this. obj = obj;双链表的设计在双链表中进行查找、删除、插入操作,即能从链表的首节点开始,也能从尾部开始,时间花费和单链表相比不占优势,但是为使程序更简洁,通常在双链表的最前面和最后面各添加一个哑元节点。这样,由于首尾节点的存在,插入、删除操作都可被看作在双向链表中间某个节点的插入、删除;并且因为首尾节点的存在,整个链表永远不会为空,因此在插入和删除节点之后,也不用考虑链表由空变为非空或由非空变为空的情况下head和tail的指向问题,从而简化了问题。双链表的设计(续)通用的双链表类的初始化public class DLinkedList /头节点private DLinkedNode head;/头节点private DLinkedNode tail;/元素个数private int size;public DLinkedList() head = new DLinkedNode();tail = new DLinkedNode();head.setNext(tail);tail.setPre(head);size = 0;双链表的设计(续)对边界条件的检测protected DLinkedNode check(Node p)throws Exceptionif(p=null)throw new Exception(“节点为空!”);if(p=head)throw new Exception(“节点不能指向头节点!”);if(p=tail)throw new Exception(“节点不能指向尾节点!”);DLinkedNode node = (DLinkedNode)p;return node;双链表的设计(续)演示一个方法的实现把给定对象作为第一个元素插入链表public void addFirst(Object o)DLinkedNode node = new DLinkedNode(o,head,head.getNext();head.getNext().setPre(node);head.setNext(node);size+;请设计将给定对象插入到尾部的方法public void addLast (Object o)双链表的设计(续)public void addLast (Object o)DLinkedNode node = new DLinkedNode(o, tail.getPre(),tail);tail.getPre().setNext(node);tail.setPre(node);size+;请设计方法移除指定元素public void remove(Node p)双链表的设计(续)public void remove (Node p)throws ExceptionDLinkedNode node = check(p);node.getPre().setNext(node.getNext();node.getNext().setPre(node.getPre();size-;请设计方法移除尾部元素public void removeLast()双链表的设计(续)请设计方法移除指定位置的元素public void remove(int index)请设计方法将链表中指定位置元素替换为指定的元素,并返回以前在指定位置处的元素public void set(int index,Object obj)链表的使用可以使用链表替代数组实现栈和队列。public class StackLinkedList private SinglyLinkedNode top;/ 指向栈顶元素private int size;/ 栈中元素数目public StackLinkedList() top = null;size = 0;public int getSize() return size;public boolean isEmpty() return (top = null) ? true : false;链表的使用public Object peek() if (isEmpty()return null;re

    注意事项

    本文(Java数据结构链表.ppt)为本站会员(p**)主动上传,第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知第壹文秘(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2023 1wenmi网站版权所有

    经营许可证编号:宁ICP备2022001189号-1

    本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!

    收起
    展开