ITeye博客

firesaijj的博客

firesaijj · 共 9 篇文章

数据结构学习---队列

像栈一样,队列(queue)也是表,然而,使用队列时插入在一端进行而删除在另一端进行。 队列的基本操作时enqueue入队,它是在表的末端(队尾(rear))插入一个元素,和dequeue出队它是删除并返回在表的开头(队首(front))的元素,如图是队列的抽象模型。 队列的数组实现 如同栈的情形一样,对于队列而言任何的表的实现都是合法的,对于每一种操作,链表实现和数组实现都给出快速的常数运行时间。队列的链表实现是简单直接的,下面讨论队列的数组实现。 对于每一个队列数据结构,保留一个数组theArray以及位置front和rear,代表队列的两段。还需要记录实际存在于队列中的元素个数curr…

2014-03-18T22:24:03Z · 数据结构 · 评论(0)

数据结构学习---栈

栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶。对栈的操作有进栈(push)和出栈(pop),前者相当于插入,后者则是删除最后插入的元素。最后插入的元素可以通过使用top在执行pop之前进行考查。对空栈进行的pop或top一般被认为是栈的ADT中的错误。 栈有时又叫做LIFO(后进先出)表。如图描述的模型只象征着push是输入操作而pop和top是输出操作。普通的清空栈的操作和判断是否为空栈的测试都是栈的操作指令系统的一部分,只不过我们能做的也基本上就只有push和Pop操作。 由于栈是一个表,因此任何实现表的方法都能实现栈。显然,ArrayList和LinkedLi…

2014-03-18T22:05:29Z · 数据结构 · 评论(0)

数据结构学习---基于双向链表实现的链接表

经过前面的学习,我们看到如果使用ListSLink对线性表进行每个元素的访问get(i)则需要n n的时间,因为在使用链表实现取i号数据元素的操作时,需要将节点的引用给从链表前向后移动i次,而取i+1时又不能在上一次操作---取i好数据元素-----中受益,必须从链表前端开始定位,则访问线性表中每一个元素一次所需要的时间为n n。这是难以接受的。 链接表可以看成是一组节点序列以及基于节点进行操作的线性结构抽象,或者说对链表的抽象。 链接表接口定义 package taxus.list; public interface LinkedList { //查询连接表当前的规模 public int…

2014-03-13T21:54:50Z · 数据结构 · 评论(0)

数据结构学习---线性表的数组实现与单链表实现比较

**1. 基于时间的比较 ** 线性表的操作主要有查询,插入,删除三类。 对于查找操作有基于序号的查找,即存取线性表中i号数据元素,由于数组的随机存取特性,在线性表的顺序存储实现中可以在常数1时间内完成,而在线性表中则需要从节点开始顺着链表才能获取,无法在常数时间内完成,因此顺序存储由于链式存储。查找操作还有基于元素的查找,即线性表是否包含某个元素,元素的序号是多少,这类操作的线性表的顺序存储与链式存储都需要从线性表中的序号为0的元素开始依次查找,因此两种实现性能相同,综上所述,如果在线性表的使用中主要操作时查找,那么应当选用顺序存储实现的线性表。 对于基于数据元素的插入,删除操作而言,当使…

2014-03-02T00:18:58Z · 数据结构 · 评论(0)

数据结构学习---线性表的单链表实现

在使用链表实现线性表是,既可以选择单链表,也可以选择双向链表,实际中的选择要依据需要实现的基本操作来决定。 在使用单链表实现线性表的时候,为了使程序更加简洁和方便,我们在单链表的最前面添加一个哑元节点,也称为头节点。在头节点中不存储任何实质的数据对象,其next指向线性表中0号元素所在的节点。头节点的引入也使线性表运算中的边界条件更容易一些。带头节点的单链表实现线性表结构图: 通过图可以暗处,对于任何基于序号的插入,删除,以及任何基于数据元素所在的节点的前后插入,删除,在带头节点的单链表中均可转换为在某个特定的节点之后完成节点的插入,删除,而不用考虑操作在连表中的头,中,尾等不同情况。 线性…

2014-03-01T23:40:58Z · 数据结构 · 评论(0)

数据结构学习---线性表的链式存储实现(双向链表)

单链表的优点是结构简单,但是单链表只能通过一个节点房后其后续节点,无法直接访问其前驱结点,要在单恋保重找到某个节点,必须从链表的首节点出发,依次向后寻找。为此在单链表的基础上进行扩展,使得不但能够访问其后续节点,也可访问前驱结点。做法为在单链表节点上增加一个域,指向节点直接前驱结点。双链表节点结构图,如图: 与但电力报节点定义类似,双向链表的节点定义通过实现节点完成。 代码 package taxus.list; public class DLNode implements Node { private Object element; private DLNode pre; private …

2014-03-01T22:55:57Z · 数据结构 · 评论(0)

数据结构学习---线性表的链式存储实现(单链表)

之前实现了线性表的数组实现方式,了解了其特性,查询很快,不过才进行元素插入和删除时需要移动元素才能完成。为了避免这种缺点,我们需要在每个单元中设置指针来表示元素之间的逻辑关系,增加了额外的存储空间。用链式存储是以空间为代价换取了时间,其实写代码基本没有绝对的事情,我们总是在寻找最合适的方式处理我们遇到的问题,在时间和空间之间找平衡点,有时候时间要求更多一点,有时候空间要求更多一点,具体情况具体分析。 链表存储数据元素的结构是通过单元的指针串起来形成的,在实际存储中并不像数组一样是连续的存储,链表分为单向链表,双向链表,不论哪种都有数据域和指针,只不过双向链表有前后两个指针,而单向链表只有ne…

2014-02-26T11:48:13Z · 数据结构 · 评论(0)

数据结构学习---线性表的数组实现LIstArray

线性表的数组实现,其内部存放数据的实际上就是一个可变容量的数组,大家都知道数组的特性,获取数组中I的数据的时间为常数,所以做查询非常快。 package taxus.list; public class ListArray implements List{ private final int LEN = 5; private int size; private Object[] elements; private Strategy strategy; public ListArray(){ this(new DefaultStrategy()); } public ListArray(Str…

2014-02-25T22:39:42Z · 数据结构 · 评论(0)

数据结构学习---线性表

本人第一次发帖,只是想把自己学习的知识做一个记录,在数据结构相关的内容里面大部分来自于周鹏的“数据结构--java语言版”一书,如有侵权望作者即时指出,谢谢。 工作了两年多,平时都不注意基本知识积累,或者曾经知道了,但是没有及时记录,过几个月就忘记了,现在出去找工作,很多都会问关于数据结构的知识,每次总是一知半解的回答,最终结果就是没通过面试,好的工作机会眼睁睁的看着没把握住,实在可惜,希望通过再次学习基础知识,能对java有更深的理解和认识。 所写的文章中,主要以代码为主,某些地方可能会写上我自己的体会和认识。新手发帖,写得不好,望各位大大多多指教 :) List接口,相信大家并不陌生,代…

2014-02-25T22:15:13Z · 数据结构 · 评论(0)