文档章节

数据结构与算法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

© 著作权归作者所有

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

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

zaking
05/10
0
0
浅解前端必须掌握的算法(五):堆排序(上)

前言 虽然前端面试中很少会考到算法类的题目,但是你去比如像腾讯一样的大厂面试的时候就知道了,对基本算法的掌握对于从事计算机科学技术的我们来说,还是必不可少的,每天花上 10 分钟,轻...

程序猿何大叔
07/02
0
0
菜鸟数据科学入门01 - 工具包概略

数据科学是什么?为什么要学习数据科学? 来不及解释了,先上车 -。- 开车之前,为接下来的系列文章做准备,先来罗列一下 Python 科学计算生态中常见的工具包。 IPython IPython 为 NumPy、S...

Kidult
2017/12/21
0
0
C 扩展类库--celib

celib 是使用ANSI C开发的一个扩展类库(c extend library),包含了一些常用的数据结构和算法的封装,可以应用到项目或者用于学习。 目前已经包含的封装如下: (01). 动态数组。 (02). bitmap...

狮子的魂
2014/01/03
1K
0
狮子的魂/celib

celib是使用ANSI C开发的一个扩展类库(c extend library),包含了一些常用的数据结构和算法的封装,可以用于应用或者学习。 目前已经包含的封装如下: (01). 动态数组。 (02). bitmap。 (03)...

狮子的魂
2014/09/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Shell编程(expect同步文件、指定host和同步文件、构建文件分发系统、批量执行命令)

expect脚本同步文件 需求:自动同步文件 实验准备: A机器:192.168.248.130 B机器:192.168.248.129 实现: 1.A机器编写4.expect脚本文件,内容如下所示: #!/usr/bin/expectset passwd "...

蛋黄_Yolks
40分钟前
2
0
ppwjs之bootstrap颜色:背景颜色

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
40分钟前
1
0
Ubuntu与 Fedora之对比

大家好。今天我将重点介绍两个流行的Linux发行版之间的一些特性和差异; Ubuntu 18.04和Fedora 28。它们都有自己的包管理; Ubuntu使用DEB,而Fedora使用RPM,但它们都具有相同的桌面环境(GNO...

linuxprobe16
44分钟前
2
0
线性代数入门

线性代数的概念对于理解机器学习背后的原理非常重要,尤其是在深度学习领域中。它可以帮助我们更好地理解算法内部到底是怎么运行的,借此,我们就能够更好的做出决策。所以,如果你真的希望了...

牛奋Debug
昨天
3
0
开发5分钟,调试2小时 - 该如何debug?

几年来我在答疑群、论坛、公众号、知乎回答的各种问题,没有一万也有八千。其中有三分之二以上都是在帮人看报错,帮人 debug(调试代码)。 可以说,会不会 debug,有没有 debug 的意识,懂不...

crossin
昨天
4
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部