欢迎来到乐乐文库,课件爱好者! | 帮助中心 精品ppt课件,ppt课件精品!
乐乐文库,课件爱好者
首页 乐乐文库,课件爱好者 > 资源分类 > PPT文档下载

041 042 数据结构和算法的Java实现_穷举&ampamp;递归&ampamp;链表.ppt

  • 资源大小:1.19MB        全文页数:37页
  • 资源格式: PPT        下载权限:游客/注册会员/VIP会员    下载费用:15金币 【人民币15元】
游客快捷下载 游客一键下载
会员登录下载
下载资源需要15金币 【人民币15元】

邮箱/手机:
温馨提示:

支付成功后,系统会根据您填写的邮箱或者手机号作为您下次登录的用户名和密码(如填写的是手机,那登陆用户名和密码就是手机号),方便下次登录下载和查询订单;
特别说明:
请自助下载,系统不会自动发送文件的哦;
支付方式: 支付宝   
验证码:   换一换

 
友情提示
2、本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

041 042 数据结构和算法的Java实现_穷举&ampamp;递归&ampamp;链表.ppt

2006,1,Java高级程序设计 专业教程 理论讲解部分 Ver 3.1,2006,2,课程概述,穷举算法 递归算法 链表,重点,穷举算法 递归算法 链表,难点,递归算法 链表,学习目标,掌握穷举算法 掌握递归算法 掌握链表的使用,2006,3,依次查询所有可能情况,以获得目标值.,利用计算机计算速度快的特点,在备选项目不是特别多的情况下可以使用,查询过程要无遗漏,不重复,穷举并不是说不要任何地优化,在有明显得条件可以优化的前提下还是应该尽量优化程序,6.1 穷举法,2006,4,例利用穷举法在1-100的自然数中找出所有的素数,public class Qiongju { private int[] result; public Qiongju{ result new int[40]; } public void deal{ int point 0; result[point] 2; forint i 3;i100;i2{ ifisPrimeNumberi{ result[point] i; } } },6.1 穷举法,2006,5,public boolean isPrimeNumberint n{ forint i 2;iMath.sqrtn1;i{ ifni 0{ return false; } } return true; } public static void mainString[] args { // TODO Auto-generated method stub Qiongju qj new Qiongju; qj.deal; forint i 0;iqj.result.length;i{ System.out.printlnqj.result[i]; } } },6.1 穷举法,2006,6,主要思想,对所有可能为素数的数进行检验.,在能够简化的情况下要尽量的简化,首先要保证不遗漏,保证每一个可能的数都要检验到,6.1 穷举法,2006,7,在程序设计中,函数直接或者间接调用其自身的方法叫做递归调用,简称递归.其设计方法被应用到很多特殊问题的解决上,函数A,,,,函数B,函数C,,,,6.2 递归,2006,8,递归要点,每次递归调用都要使问题简单化,当递归达到某种程度后能够的到一个已知解以结束递归调用,6.2 递归,2006,9,据说毕达哥拉斯理论家,又称一群在毕达哥拉斯以毕达哥拉斯理论闻名领导下工作的古希腊的数学家,发现了在数字序列1,3,6,10,15,21, ..省略号说明这个序列无限地继续下去 中有一种奇特的联系。你能知道这个序列的下一个数字是什么吗,例,6.2 递归,2006,10,这个数列中的第n项是由第n1项加M得到的。由此,第二项是由第一顶U加上2,得3。第三项是由第二项3加上3得到6*依此类推。 这个序列户的数字被称为三角数字,因为它们可以被形像化地表示成对象的一个三角形排列.,分析,6.2 递归,2006,11,6.2 递归,2006,12,以Sn代表第n项的值,有如下表示,Sn Sn-1n,当n1时,当n1时,Sn1,6.2 递归,2006,13,public int triangleint num{ ifnum 1{ return 1; }else{ return trianglenum-1num; } },代码表示如下,当n 1时,Sn 1;,当n1时,Sn Sn-1n,6.2 递归,2006,14,,,,数组的缺陷,插入,删除的效率非常低,数组大小不可变,无法实现动态生成.,6.3 链表,2006,15,链表的优势,解决了数组无法动态增长及减小的问题.,插入删除的效率非常高,导致用途非常广泛,6.3 链表,2006,16,在链表中,每个数据项都被包含在“链结点”Link中。一个链结点是某个类的对象,这个类可以叫做Link。每个Link对象中都包含一个对下一个链结点引用的字段通常叫做next。但是链表本身的对象中有一个字段指向对第一个链结点的引用。,6.3 链表,2006,17,下面是一个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,6.3 链表,2006,18,,在数组中,我们使用的是位置进行查询.,在链表中,我们使用的是节点之间的关系进行查询,查询的过程不同,6.3 链表,2006,19,下面是Node类,节点类,它描述了每一个节点所要保存的内容.,class Node{ private int key; private int value; private Node next; public Nodeint key,int value{ this.key key; this.value value; next null; } },key 键值,数据是依靠键值来查询的,value 数据,实际要存储的内容,next 下一个节点的引用.,6.3 链表,2006,20,MyLink类,链表类.除了要包含Node,还要有一个头节点.,private Node head;,head描述了当前链表的第一个元素的引用,当一个链表拥有了头节点,也就意味着拥有了全部的链表.,6.3 链表,2006,21,链表的初始化,当链表创建之初,仅仅拥有一个空的head就可以了.其内容是逐渐添加进去的,public MyLine { head null; },此时,你已经拥有了一个链表,只是它是一个空链表.,6.3 链表,2006,22,节点的添加,这里实现的是一个将链表自动增长的过程.,首先,找到链表的尾部.,然后,将新的节点添加到链表的尾部.,6.3 链表,2006,23,public void addNodeint key,int value{ ifhead null{ head new Nodekey,value; }else{ Node current head; whilecurrent.next null{ current current.next; } current.next new Nodekey,value; } },节点的添加,链表为空,直接将节点添加到head中,尾部的查找,,新节点的添加,6.3 链表,2006,24,节点的查询,链表的查询只能从前向后依次进行,无法使用随机搜索.,private Node getNodeint key{ Node current head; ifhead.key key{ return head; }else{ current head.next; whilecurrent.key key{ current current.next; } return current; } },6.3 链表,2006,25,节点的删除,节点的删除包括两个方面的内容,待删除节点及其前继节点的查找,将待删除节点删除,6.3 链表,2006,26,节点的删除,Node current; Node parent;,分别来描述当前正在查询的节点及其父节点.,一旦当前节点与待删除节点相同则确认找到删除节点并删除之.否则删除失败,6.3 链表,2006,27,节点的删除,节点删除过程非常简单,只需要将其前继节点的next指向待删除节点的next就可以.,除非有必要,需要对删除节点作相应处理,否则等待垃圾回收处理即可,value,,key,value,,key,value,,key,,,,,,,parent,current,,,,6.3 链表,2006,28,public boolean delNodeint key{ Node current head; Node parent; ifhead null{ return false; }else ifhead.key key{ head head.next; return true; }else{,确定链表不为空,否则删除失败,头节点比较特殊,需要特殊处理,6.3 链表,2006,29,current head.next; parent head; whilecurrent.key key{ current current.next; parent parent.next; } ifcurrent null{ parent.next current.next; return true; }else return false; } },查询待删除节点及其前继节点,如果查到待删除节点则删除.否则删除失败,6.3 链表,2006,30,节点的插入,插入通常使用两种插入方式按照位置插入,按照顺序插入.,其思想不变,都是按照某种规则,找到待插入位置,然后进行插入操作.,下面介绍插入时的操作,6.3 链表,2006,31,节点的插入,value,,key,value,,key,value,,key,,,,,,parent,current,,,首先,找到待插入位置的前继节点parent.,然后,将待插入节点current.next指向parent.next.,最后,将parent.next指向插入节点current,6.3 链表,2006,32,节点的插入,public boolean insertNodeNode newNode,int index{ Node preNode head; ifpreNode null || index 0{ newNode.next preNode; preNode newNode; return true; }else{ whilepreNode.next null } },节点位置的查找,节点的插入,6.3 链表,2006,33,本课小结,本课介绍了穷举算法、递归算法以及链表的使用。穷举算法又称为没有算法的算法,是一种比较简单、易于掌握的算法;递归算法是一种直接或者间接调用自身方法的算法,它的使用及掌握略复杂,但确是一种很好的算法工具;链表是一种比较基础的数据结构,很多其它复杂的数据结构会借助链表来实现,链表是数据结构的基础。,2006,34,小测验,1.画出MIDP的层次结构 。,2.借助图示描述MIDlet的生命周期 。,2006,35,小测验答案,1.画出MIDP的层次结构 。 答,2006,36,小测验答案,2.借助图示描述MIDlet的生命周期 。 答,2006,37,课后作业,【作业1】下载一款手机游戏,查看在不同的生命周期下,游戏的不同反应。,

注意事项

本文(041 042 数据结构和算法的Java实现_穷举&ampamp;递归&ampamp;链表.ppt)为本站会员(w89153)主动上传,乐乐文库,课件爱好者仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知乐乐文库,课件爱好者(发送邮件至1748365562@qq.com或直接QQ联系客服),我们立即给予删除!

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

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

站长联系QQ:1748365562
工信部备案号: 鄂ICP备17024083号                 公安局备案号:42118102000213

收起
展开