- 浏览: 337072 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
alafqq:
很好的一篇启蒙hashmap的文章;HASHTABLE的93行 ...
使用数组和链表实现hash表存储信息 -
小帅1127:
我擦,我还以为有什么大坑呢,这也写出来。。。
if..else if和if..if的区别 -
fncj:
转下http://www.dodoer.com
hadoop单机版搭建图文详解 -
yueshang520:
Spring注解原理的详细剖析与实现 -
fncj:
转下,谢谢http://www.whohelpme.com/b ...
Spring注解原理的详细剖析与实现
1、定义
数组又叫做顺序表,顺序表是在内存中开辟一段连续的空间来存储数据,数组可以处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中,用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大小,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。
链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。链表是靠指针来连接多块不连续的的空间,在逻辑上形成一片连续的空间来存储数据。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放,不会造成内存空间的浪费。
2、二者区分:
A 从逻辑结构来看
A-1. 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。
A-2. 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项)
B 从内存存储来看
B-1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
B-2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦.
数组在内存中开辟连续的一块区域,如果一个数据要两个内存单元,一组5个数据10个单元就够了,无需标记其地址,因为数组定义时候标顶了第一个原始的地址,其他四个都知道了。
链表可可以是连续的,也可以是不连续的,但一般都是不连续的,一链5个数据,如果每个数据本身用2个内存单元,那么10个单元是不够的,因为每个数据都要表示出下个数据在哪里,所以一个数据本身用2个单元,再用1个单元表示此链下一个数据在什么地址。
C从访问顺序来看
数组中的数据在内存中的按顺序存储的,而链表是随机存储的!
C-1.要访问数组中的元素可以按下标索引来访问,速度比较快,如果对他进行插入操作的话,就得移动很多元素,所以对数组进行插入操作效率很低!
C-2.由于链表表是随机存储的,链表在插入,删除操作上有很高的效率(相对数组),如果要访问链表中的某个元素的话,那就得从链表的头逐个遍历,直到找到所需要的元素为止,所以链表的随机访问的效率就比数组要低
3、分别用数组和链表实现队列:
3-1数组实现
public class Queue <E>{ //每次放入队列的元素的个数 private int initLen=0; //每次增长的队列空间的大小 private int increaseLen=0; private Object[] src; //己放入对象的个数 private int count=0; public Queue(int initLen,int increaseLen){ this.initLen=initLen; this.increaseLen=increaseLen; src = new Object[initLen]; } public Queue(int initLen){ this(initLen,initLen/2); } public Queue(){ this(20,10); } /** * 在末尾向队列中增加一个字符串 * @param s:向队列中增加的字符串 */ public void add(E e){ src[count]=e; count++; if(count>=initLen){ //新建数组,是原数组长度的length+1 Object[] temp=new Object[src.length +increaseLen]; //将原数组中的复制到新数组中 for(int i=0;i<count;i++) { temp[i]=src[i]; } src=temp; } } /** * 在指定位置向队列中增加一个字符串s * @param s 向队列中增加的字符串 * @param index 队列中指定的位置 */ public void add(E e,int index){ if(count>=initLen){ //新建数组,是原数组长度的length+increaseLen Object[] temp=new Object[src.length +increaseLen]; //将原数组中的复制到新数组中 for(int i=0;i<count;i++) { temp[i]=src[i]; } //新数组赋值给原数组 src=temp; } //将原数组从index处的元素向后以一位 for(int i=count;i>index;i--) { src[i]=src[i-1]; } //将s添加到新数组中指定位置 src[index]=e; } /** * 得到队列中指定位置的字符串 * @param index 队列中指定的位置 * @return 返回指定位置的字符串 */ public E get(int index){ if(index>=0&&index<=count){ return (E)src[index]; } else return null; } /** * 返回当前字符串的位置 * @param s当前字符串 * @return 当前字符串的位置 */ public int getPos(E e){ int temp=-1; for(int i=0;i<count;i++){ if(e.equals(src[i])){ temp=i; break; } } //System.out.println("位置是:"+temp); if(temp==-1) System.out.println("队列中没有与 \""+e+"\" 匹配的字符串!"); return temp; } /** * 得到队列中字符串的长度即大小 * @return 返回的是字符串的大小 */ public int size(){ return count; } /** * 删除队列中指定位置的字符串 * @param index 要删除字符串的位置 * @return 返回锁删除的字符串 */ public E delete(int index){ //System.out.println("字符串的长度为"+src.length); //新建数组,是原数组长度的length+1 Object[] temp=new Object[count-1]; E e; //将原数组index前的元素复制到新数组中 for(int i=0;i<index;i++) { temp[i]=src[i]; } e=(E)src[index]; //将原数组index后的元素复制到新数组中 for(int i=index+1;i<count;i++) { temp[i-1]=src[i]; } //新数组赋值给原数组 src=temp; count--; //System.out.println("字符串的长度为"+src.length); return e; } /** * 删除指定的字符串 * @param s要删除的字符串 * @return TRUE删除成功 FALSE删除失败 */ public Boolean delete(E e){ int temp=-1; for(int i=0;i<count;i++){ if(e.equals(src[i])){ temp=1; break; } } if(temp!=-1)return true; return false; } /** * 替换队列中指定位置的字符串 * @param s新的字符串 * @param index要更新字符串的位置 * @return */ public Boolean replace(E e,int index){ if(index>count){ System.out.println("长度超出!!"); return false; } E temp; temp=(E)src[index]; src[index]=e; e=temp; return true; } }
3-2链表实现
public class Node<E> { public E Elem; public Node<E> next; public Node(E elem){ Elem=elem; } public String toString(){ return Elem.toString(); } } public class LinkQueueDemo <E>{ public Node head=null; public Node tail=null; /** * 在末尾向队列中增加一个节点 * @param s:向队列中增加的字符串 */ public void add(E elem){ if(head==null){ head=new Node(elem); tail=head; }else{ tail.next=new Node(elem); tail=tail.next; } //System.out.println("插入的Node是:"+elem); } /** * 得到队列中指定位置的字符串 * @param index 队列中指定的位置 * @return 返回指定位置的字符串 */ public Node get(int index){ Node temp=head; int count=0; if(index>this.size()){ System.out.println("index is out of the size:"+this.size()); return null; }else if(temp==null){ System.out.println("queue is empty;"); return null; }else{ while(count!=index){ count++; temp=temp.next; } return temp; } } /** * 返回当前节点的位置 * @param s当前字符串 * @return 当前字符串的位置 */ public int getPos(E e){ Node temp=head; Node query_Node=new Node(e); int count=0; if(temp==null){ System.out.println("queue is empty;"); return -1; }else{ while(temp.Elem!=query_Node.Elem&&temp.next!=null){ count++; temp=temp.next; } if(temp.next==null){ System.out.println("there is no such Node"); return -1; } return count; } } /** * 得到队列中字符串的长度即大小 * @return 返回的是字符串的大小 */ public int size(){ int len=0; Node temp=head; if(head==null) return 0; while(temp!=null){ len++; temp=temp.next; } return len; } /** * 删除队列中指定位置的字符串 * @param index 要删除字符串的位置 * @return 返回锁删除的字符串 */ public Node delete(int index){ Node temp=head; Node pretem=temp; int count=0; if(index>this.size()){ System.out.println("index is out of the size:"+this.size()); return null; }else if(temp==null){ System.out.println("queue is empty;"); return null; }else{ while(count!=index){ count++; pretem=temp; temp=temp.next; } pretem.next=temp.next; } return temp; } /** * 删除队列中第一个Node * @return 返回锁删除的node */ public Node delete(){ Node temp=head; if(temp==null){ System.out.println("the queue is empty!"); return null; }else{ if(head.next!=null){ head=head.next; } else{ head=null; } return temp; } } /** * 删除指定的字符串 * @param s要删除的字符串 * @return TRUE删除成功 FALSE删除失败 */ public Boolean delete(E e){ return false; } /** * 替换队列中指定位置的字符串 * @param s新的字符串 * @param index要更新字符串的位置 * @return */ public Boolean update(E e,int index){ Node temp=head; int count=0; if(index>this.size()){ System.out.println("index is out of the size:"+this.size()); return false; }else if(temp==null){ System.out.println("queue is empty;"); return false; }else{ while(count!=index){ count++; temp=temp.next; } temp.Elem=e; } return true; } public void printQueue(){ Node temp=head; int count=0; while(temp!=null){ System.out.println(count+":"+temp+" "); temp=temp.next; count++; } } }
评论
嗯,确实,这点我没有考虑到,这个内部定义会更好一些
public Queue(int initLen,int increaseLen){ 12. this.initLen=initLen; 13. this.increaseLen=increaseLen; 14. src = new Object[initLen]; 15. } 16. 17. public Queue(int initLen){ 18. this(initLen,initLen/2); 19. } public Queue(){ 22. this(20,10); 23. }
你的想法很好,可以让用户自己决定开辟多少空间,也可以由我们自己决定开辟多少空间,我就没想到(惭愧啊!~)。但是我很好奇,为什么你要加上第一个构造函数呢?如果用户输入的需要增加的空间过大,会很浪费资源的。那个要增长的空间长度可以由我们自己定啊!~(个人见解)
发表评论
-
apache日志信息详解
2011-11-06 21:19 6272一、访问日志的格式 Apache内建了记录服务器 ... -
浏览器如何工作
2011-08-19 08:57 0http://taligarsiel.com/Projects ... -
编码实现用JDK中的Proxy实现springAOP功能
2011-08-18 15:04 748http://blog.csdn.net/iamtheevil ... -
Spring注解原理的详细剖析与实现
2011-08-14 23:09 84241本文主要分为三部分: ... -
Spring装配基本属性的原理分析与代码实现
2011-08-11 15:37 1424首先,做一个配置属性的基本测试。修改beans.xml,使引用 ... -
编码剖析Spring依赖注入的原理
2011-08-10 20:01 1817一、注入依赖对象 基本类型对象注入: <b ... -
Spring的三种实例化Bean的方法
2011-08-10 14:03 1Spring的三种实例化Bean的方法 1、 使用 ... -
Spring管理bean的原理自定义实现
2011-08-10 10:44 61891、Spring通过BeanDefinition管理基于S ... -
spring环境搭建与测试
2011-08-10 08:40 3411Chapter1、搭建与测试spring的环境 1、 ... -
java回调机制实现
2011-08-08 09:06 2038Java的接口支持提供了一种获得回调的等价功能的 ... -
log4j的使用与详细分析
2011-08-05 13:32 2629一、什么是log4j? http://logging.a ... -
log4j使用详解
2011-08-04 23:05 2http://logging.apache.org/log4j ... -
java解析XML的四种方法的学习与比较
2011-03-30 20:55 7233四种XML解析方法: ... -
自定义日志模块实现
2011-03-30 09:58 1105package wxy.XXXX.Utils; impo ... -
synchronized(this)
2011-03-29 09:17 69411、当两个并发线程访问同一个对象object中的这个synch ... -
详细解析Java中抽象类和接口的区别(转)
2011-03-24 23:48 926在Java语言中, abstract cl ... -
NIO学习笔记(三)---通道
2011-03-09 23:06 15551、通道基础 ... -
NIO学习笔记(2)--缓冲区
2011-03-09 18:20 9381、一个Buffer对象是固定数量的数据的容器。其作用是 ... -
封锁管理子系统模拟实现java版
2011-03-09 18:01 1181封锁管理子系统模拟实现 文件锁定 ... -
NIO学习笔记(一)I/O缓冲区操作
2011-03-07 20:04 1230上图简单描述了数据从外部磁盘向运行中的进程的内存区域移动的 ...
相关推荐
队列关于数组与链表的实现, linux c语言
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
两个文件 一个是数组实现循环队列 一个是链表实现 功能是常用的基本功能 希望对大家有所帮助
众所周知,在普通的非线程安全队列有两种实现方式: 1.使用数组实现的循环队列。 2.使用链表实现的队列。 先看看两种方式的优劣: .Net Farmework中的普通队列Queue的实现使用了第一种方式,缺点是当队列空间不足会...
我们使用一种比较特殊的链表——非循环双向链表来实现队列。首先这里的说明的是构建的是普通的队列,而不是循环队列。当我们使用数组的时候创建循环队列是为了节省存储空间,而来到链表中时,每一个节点都是动态申请...
优先队列 优先队列(Priority Queue)是一种数据结构,它类似于常规的队列或栈,但每个元素都有与其关联的“优先级”。在优先队列中,元素的出队顺序是基于...下面是一个简单的基于数组和插入排序的优先队列实现示例:
标准栈与队列定义,包括数组和链表两种存储结构
学过数据结构的人都知道:栈可以用两种方式来实现,一种方法是用数组实现栈,这种栈成为静态栈;另外一种方法是用链表实现栈,这种栈叫做动态栈。 栈中通常存放着程序的局部变量等。栈通常有出栈和入栈操作。
Java数组和链表两种结构的操作效率,在哪些情况下(从开头开始,从结尾开始,从中间开始),哪些操作(插入,查找,删除)的效率高? Java内存泄露的问题调查定位:jmap,jstack的使用等等。 java高级 Java创建线程之后...
1.线性表:数据存储像一条线一样的结构,每个线性表上的数据最多只有前和后的两个方向,如数组、链表、队列、栈等都是这种结构,所以实现的数组的动态操作,其他结构也可轻易的类似实现。更重要的是,在这之后看源码...
实现栈的时候有两种思维 1 顺序栈:由数组去实现 存在假溢出问题:里面的元素个没有超过它的最大值,但是看起来也溢出了 ,我们必须要解决这个假溢出问题 因此我们设计顺序队列的时候要设计循环队列:文章说明了...
暴力解法有两种,一种是12排,然后和3,然后和4,继续下去; 另一种是先放到一个数组中进行排序,然后按照顺序连接 分而治之:两两合并 如果有k个链表,平均每个链表有n个节点 那么,第一轮,k/2次,每次2n个节点 第...
一、队列简介 队列是是一种受限的线性表,特点为先进先出...队列的实现和栈一样,有两种方案: 基于数组实现;基于链表实现; 队列的常见操作: enqueue(element):向队列尾部添加一个(或多个)新的项; dequeu
线性结构有两种不同的存储结构,即顺序存储结构和链式储存结构。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的。 链式存储的线性表称为链表,链表中的储存元素不一定是连续的,元素节点种存放数据元素...
C / C ++中的数据结构和算法 该代码由Amit Bansal在学习...插入删除中预定遍历顺序遍历后遍历级别顺序遍历查找二叉搜索树的高度检查树是否为二叉搜索树(2种方法) 在二分搜索树中查找最大和最小元素 AVL树 插入b。删除
栈和队列是两种基本的数据结构,同为容器类型。两者根本的区别在于: stack:后进先出 queue:先进先出 stack和queue是不能通过查询具体某一个位置的元素而进行操作的。但是他们的排列是按顺序的 对于stack我们可以...
复制代码 代码如下:<?php /** ** 一数组的概述 1....多维数组 (数组的数组,就是在数组中存有其他的数组) 2.php中有两种数组 索引数组:就是下标【键】是顺序整数的索引 关联数组 :下标是字符串作为索引 下
一、概念梳理 链表是计算机科学里面应用应用最广泛的数据结构之一。它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧、环形缓冲和队列) ...这里介绍两种不同的列表——单链表和双链表。
通过扩展类和实现接口两种方式定义匿名内部类。 机动时间和复习 2课时 <br> 第8章 异常和断言 4课时 理解异常和错误处理的概念。 学习使用throw,throws检测抛出...
◆ 详细介绍了数据抽象,强调规范和实现之间的区别 ◆ 广泛介绍了各种面向对象的编程技术 ◆ 重点是核心的数据结构,而不是非必要的C++语言语法 ◆ 说明了类和ADT在问题解决过程中的作用 ◆ 诠释了ADT的主要...