文档章节

数据结构与算法01 之数组

乐在克里特
 乐在克里特
发布于 2017/02/23 13:53
字数 647
阅读 2
收藏 1

       数组是应用最广泛的数据存储结构。它被植入到大部分的编程语言中,由于数组十分易懂,所以在这里就不赘述,主要附上两端代码,一个是普通的数组(无序数组),另一个是有序数组。有序数组是按关键字升序(或降序)排列的,这种排列使快速查找数据项成为可能,即可以使用二分查找。

    普通数组的java代码

 

  1. public class GeneralArray {  
  2.     private int[] a;  
  3.     private int size; //数组的大小  
  4.     private int nElem; //数组中有多少项  
  5.     public GeneralArray(int max) { //初始化数组  
  6.         this.a = new int[max];  
  7.         this.size = max;  
  8.         this.nElem = 0;  
  9.     }  
  10.     public boolean find(int searchNum) { //查找某个值      
  11.         int j;  
  12.         for(j = 0; j < nElem; j++){  
  13.             if(a[j] == searchNum)  
  14.                 break;  
  15.         }  
  16.         if(j == nElem)  
  17.             return false;  
  18.         else  
  19.             return true;  
  20.     }  
  21.     public boolean insert(int value) { //插入某个值  
  22.         if(nElem == size){  
  23.             System.out.println("数组已满!");  
  24.             return false;  
  25.         }  
  26.         a[nElem] = value;  
  27.         nElem++;          
  28.         return true;  
  29.     }  
  30.     public boolean delete(int value) {//删除某个值  
  31.         int j;  
  32.         for(j = 0; j < nElem; j++) {  
  33.             if(a[j] == value) {  
  34.                 break;  
  35.             }  
  36.         }  
  37.         if(j == nElem)   
  38.             return false;  
  39.         if(nElem == size) {  
  40.             for(int k = j; k < nElem - 1; k++) {  
  41.                 a[k] = a[k+1];  
  42.             }  
  43.         }  
  44.         else {  
  45.             for(int k = j; k < nElem; k++) {  
  46.                 a[k] = a[k+1];  
  47.             }  
  48.         }  
  49.         nElem--;  
  50.         return true;  
  51.     }  
  52.     public void display() { //打印整个数组  
  53.         for(int i = 0; i < nElem; i++) {  
  54.             System.out.print(a[i] + " ");  
  55.         }  
  56.         System.out.println("");  
  57.     }  
  58. }    

 

    有序数组的java代码:

  1. public class OrderedArray {  
  2.     private long[] a;  
  3.     private int size; //数组的大小  
  4.     private int nElem; //数组中有多少项  
  5.     public OrderedArray(int max) { //初始化数组  
  6.         this.a = new long[max];  
  7.         this.size = max;  
  8.         this.nElem = 0;  
  9.     }  
  10.     public int size() { //返回数组实际有多少值  
  11.         return this.nElem;  
  12.     }  
  13. //--------------二分法查找某个值----------------//  
  14.     public int find(long searchNum) {  
  15.         int lower = 0;  
  16.         int upper = nElem - 1;  
  17.         int curr;  
  18.         while(true) {  
  19.             curr = (lower + upper) / 2;  
  20.             if(a[curr] == searchNum)  
  21.                 return curr;  
  22.             else if(lower > upper)   
  23.                 return -1;  
  24.             else {  
  25.                 if(a[curr] < searchNum)   
  26.                     lower = curr + 1;  
  27.                 else  
  28.                     upper = curr - 1;  
  29.             }  
  30.               
  31.         }  
  32.     }  
  33.     public boolean insert(long value) { //插入某个值  
  34.         if(nElem == size){  
  35.             System.out.println("数组已满!");  
  36.             return false;  
  37.         }  
  38.         int j;  
  39.         for(j = 0; j < nElem; j++){  
  40.             if(a[j] > value)  
  41.                 break;  
  42.         }  
  43.           
  44.         for(int k = nElem; k > j; k--) {  
  45.             a[k] = a[k-1];  
  46.         }  
  47.         a[j] = value;  
  48.         nElem++;          
  49.         return true;  
  50.     }  
  51.     public boolean delete(long value) { //删除某个值  
  52.         int j = find(value);  
  53.         if(j  == -1){  
  54.             System.out.println("没有该元素!");  
  55.             return false;  
  56.         }  
  57.         if(nElem == size) {  
  58.             for(int k = j; k < nElem - 1; k++) {  
  59.                 a[k] = a[k+1];  
  60.             }         
  61.             a[nElem-1] = 0;  
  62.         }  
  63.         else {  
  64.             for(int k = j; k < nElem; k++) {  
  65.                 a[k] = a[k+1];  
  66.             }  
  67.         }  
  68.         nElem--;  
  69.         return true;  
  70.     }  
  71.     public void display() { //打印整个数组  
  72.         for(int i = 0; i < nElem; i++) {  
  73.             System.out.print(a[i] + " ");  
  74.         }  
  75.         System.out.println("");  
  76.     }  
  77. }  

    对于数组这种数据结构,线性查找的话,时间复杂度为O(N),二分查找的话时间为O(longN),无序数组插入的时间复杂度为O(1),有序数组插入的时间复杂度为O(N),删除操作的时间复杂度均为O(N)。

 

http://blog.csdn.net/eson_15/article/details/51126182

© 著作权归作者所有

共有 人打赏支持
乐在克里特
粉丝 16
博文 268
码字总数 394729
作品 0
杭州
程序员
私信 提问
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
05/10
0
0
【算法】LeetCode算法题-Two Sum

程序 = 数据结构 + 算法。 算法是每一位程序员学习成长之路上无法避开的重要一环,并且越早接触越好。今后会每天做些算法题,至少每天做一道题目,同时会记录自己的解题思路和代码,通过【算...

小川94
10/15
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
09/27
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
10/02
0
0
转行程序员?你可能忽略了一件事。

     程序 = 数据结构 + 算法   ——图灵奖得主,计算机科学家N.Wirth(沃斯)      作为程序员,我们做机器学习也好,做python开发也好,java开发也好。   有一种对所有程序员无一...

java进阶架构师
10/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

微服务分布式事务实现

https://www.processon.com/view/link/5b2144d7e4b001a14d3d2d30

WALK_MAN
今天
2
0
《大漠烟尘》读书笔记及读后感文章3700字

《大漠烟尘》读书笔记及读后感文章3700字: 在这个浮躁的社会里,你有多久没有好好读完一本书了? 我们总觉得自己和别人不一样,所以当看到别人身上的问题时,很少有“反求诸己”,反思自己。...

原创小博客
今天
3
0
大数据教程(9.5)用MR实现sql中的jion逻辑

上一篇博客讲解了使用jar -jar的方式来运行提交MR程序,以及通过修改YarnRunner的源码来实现MR的windows开发环境提交到集群的方式。本篇博主将分享sql中常见的join操作。 一、需求 订单数据表...

em_aaron
今天
3
0
十万个为什么之什么是resultful规范

起源 越来越多的人开始意识到,网站即软件,而且是一种新型的软件。这种"互联网软件"采用客户端/服务器模式,建立在分布式体系上,通过互联网通信,具有高延时(high latency)、高并发等特点...

尾生
今天
3
0
Terraform配置文件(Terraform configuration)

Terraform配置文件 翻译自Terraform Configuration Terraform用文本文件来描述设备、设置变量。这些文件被称为Terraform配置文件,以.tf结尾。这一部分将讲述Terraform配置文件的加载与格式。...

buddie
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部