注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

郁夫的博客

我爱你们,只是你们不知道!

 
 
 

日志

 
 
 
 

JAVA数据结构总结之一 数组--转  

2008-01-24 21:18:09|  分类: JAVA |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

JAVA数据结构总结之一 数组

       (NOTE:Pengli,do you know that the articles ware written foryou,hopping that you can carryout your dreams soon)

       在做JAVA开发的时候,很多同行也许和以前的我一样,不知道数据结构,或者说不重视数据结构在整个开发的过程所起到的作用,就像我认识一个人,他说他做了两年的JAVA,但是还来问我什么是static和abstract的区别!!呵呵,有点夸张了吧!也就像看过GOF《设计模式》的人和没有看过的人他们的思想就有很多的不同,写出来的代码的质量也相差很大!那么,深刻理解数据结构,无论是C还是JAVA,都会对你的编程思想产生很重要的影响!

      所以,我自己也来深入的学习学习JAVA的数据结构,一个一个的来,争取透彻。接下来所有的看法都是在我实际开发中总结学习而来,假如有所错误,希望发现的朋友能给我指出!大家一起进步,振兴中国软件!^_^

     为什么要用数据结构?只有有了需求,才会有下一步的动作嘛!其实,数据结构最大的用处的是存储现实世界的数据,将他们按照一定格式存储在内存中。这里的数据有区别于数据库里面的数据,因为数据库里面的数据是现实世界的物体的持久化保存,保存在硬盘或其他媒介里面,计算机断电后依然存在的,而这里的数据结构指的却是程序在运行中,如何将现实世界的数据(也许来自数据库,也许来自程序自己产生的数据)如何有效地组织,安排在计算机内存中以达到提高程序运行效率和内存安全的目的。数据结构大致包括:数组(无序数组、有序数组),栈,队列,链表,树(二叉树、红-黑树、2-3-4数)、哈希表、堆、图等几个,随着技术的发展会出现满足相应需求的数据结构来!所有的数据结构,无非就是几个问题:插入数据,查找数据,删除数据。新的数据结构的产生也其实就是现有的数据结构在目前遇到的问题无法达到预期效果(但是也许也和代码有关)。所以,研究数据结构,要深入地研究这几种操作的算法!

     首先来看看数组!

     1、数组在JAVA里面是以对象的形式存在,或者说存在数组里面的东西全部是对象。在JAVA里面声明数组如下:Object[]o = new Object[n] 或者Object o[] = newObject[n] 。当然Object也可以是java基本数据类型。假如声明的时候没有给数组初始化,那么数组里面的数据全是空值null(int、long、float是0)。

     2、数组的大小时固定的,即数组在定义大小之后,无法再去改变它的大小!这在用起来的时候似乎不太灵活,但是想想它在所有结构中是最简单的。鱼与熊掌不可兼得嘛!

     3、数组分为无序数组和有序数组。由于他们数据的排练方式有区别,所以他们在性能上就有一定程度的不同。有序数组的数据已经按照大小顺序排练好,所以他的查找效率很高,使用二分查找算法比线型查找的效率高很多。他们的性能比较如下表:

  有序数组 无序数组
 查找 最慢(因为使用线性查找,效率为O(n)) (使用二分查找,效率为O(lgN)
 插入 (因为需要比较,效率为O(1)) (因为每插入一个数都要进行排序,效率为O(N))
 删除 一般(效率为O(N)) 一般(效率为O(N))

     在说算法之前,还是先说说衡量算法效率的一个标准吧!就是大O表示法。大O表示法只是一个粗略的度量方法,因为在实际过程中,我们比较算法A和算法B,说A比B快两倍之类的评价,其实没有多大的意义。因为当数项的个数发生变化时对应的比例也会发生变化,有可能就会变成A比B快三倍了。所以我们需要的是效率与数据项之间的关系,这就是大O表示法。

      数组数据的组织结构如何?我是这样理解的:就像有一堆的学生要排队,要一个接一个地排成一排(相当于在内存里面开辟一条区域),说的形象一点就是一条直线段!那么如何这些学生的顺序如何排就是我们要研究的问题!

    一、查找

    由上表我可以看出有序数组和无序数组在查找性能上相差很多。先来看看二分查找的算法。

   它的算法描述:给出一个范围N,如100,现要查找某个数Key,如23。那么每查找一次,就将范围划分为两部分,根据key的大小而选择相应的那一部分(如1~50,51~100,23在1~50这一个部分),直到最后范围N不能在分割成两部分时的数就是答案。

   实践指出它:在查找时所进行的比较次数大致是 3.322*lgN 次。如在100内查找,就要比较3.322*lg100≈7次,而线性查找则需要100/2=50次。差别很大吧!!^_^

   下面看看算法(以前在大学学习的时候,台上的教授一说:"下面我们来看看算法.......",呵呵,我就开始瞌睡了,呵呵)


 public int findByKey_Order(long key) {
  int low = 0;
  int hight = point;
  while (true) {
   long v =myArray[(hight + low) / 2];
   if (v == key){
    return(hight + low) / 2;
   } else if(low > hight) {
    returnpoint;
   } else{
    if(key > v) {
     low= (hight + low) / 2 + 1;
    }else {
     hight= (hight + low) / 2 - 1;
    }
   }
  }
 }

      代码很简单。注意,方法返回的是所找到的数据的下标(注意哦,数组的下标是从0开始,不是从1,切记!!)。该方法封装在一个类,该类有一个private属性,即myArray的数组。代码很简单,没什么可说的。

下面看看有序数组的线性查找的算法,也很简单,就是一定要注意数组的长度和下标的关系。

 
 public int findByKey_Linear(long key) {
  int bound = 0;
  for (int i = 0; i < point;i++) {
   if(myArray[i] > key) {
    bound= point;
    break;
   }
   if(myArray[i] == key) {
    bound= i;
    break;
   }
  }
  return bound;
 }

      就是一个个地去比较,发现相等地了就返回它地下标。

      这里就有一个问题,就是:假如数组里面有重复地数据,怎么办呢?以上的算法都没有考虑这一情况,因为数组有重复的值,在实际写代码的时候会有很多的不便(就像一个球队,不可能有两个穿着相同球号衣服的队员吧?),并且会大大的降低结构的效率。所以,我会写一个方法,来剔除那些重复值,在进行所有的排序、查总前去除重复:

 
 public void doDup() {
        for(int i=0;i<point;i++){
         long v = myArray[i];
         for(int y=i+1;y<point;y++){
          if(myArray[y]==v){
           for(inta=y;a<point-1;a++){
           myArray[a] = myArray[a+1];
           }
           y--;
          point--;
          }
         }
        }
 }

      这里,每消除一个重复的数据,数组的长度就会缩小1,最高位用0或者NULL去补上。代码里面的point值,就是标识了myArray的目前的长度,是一个全局变量。我们看到,数组在删除一个数组的时候并没有象Iterator或者List那样,显示的调用一个remove的方法去做删除动作,而是将要删除的数据用比他高一位的数据去覆盖它,相当于比它高一位的数据全部向下挪一位。

二、插入

      无序数组的插入效率很高,不会受它的长度的影响,永远都是O(1),函数图象就是一条直线,原因就是:它在插入的时候不用检查数据的大小,只要在最高位放入数据就好。而有序数组,则要进行排序比较,将要插入的数据放在它该放的位置上,效率是O(N),受它的长度的影响。以下是有序数组的插入算法:

 
 public void addData(long data){ 
  int bound =0;  
  for (bound = 0; bound <point; bound++) {
   if(myArray[bound] > data){         
    break;
   }
  }
  for (int y = point+1; y >bound; y--) {
   myArray[y] =myArray[y-1];
  }
  myArray[bound] = data;
  point++;
 }

       由于有序数组一般是按照升序,即由小到达的顺序排练。所以,寻找要插入数据data的正确位置的时候,我们只要找到第一个比data大的数的位置,那么这个位置就是data的位置(下面的就不用比,因为肯定都比data大嘛!前面的findByKey_Linear有序数组的线性查找方法也是这个道理),从这个位置开始向上,每一个数都向上挪动一位以腾出一个位置给data,所以数组的长度要增加1。

      JAVA里面的数组,出了可以放简单的数之外,还可以放入对象,但是思想基本都差不多,万变不离其宗!

      数组的内容,大概就是这么多,重点就是二分查找法、线性查找发和算法效率的标准大O表示法!还有就是一定要清楚有序数组和无序数组的性能区别。以上给出的JAVA代码,过段时间,给出C版本的代码。

  评论这张
 
阅读(751)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017