文档章节

数据结构与算法01 之数组

乐在克里特
 乐在克里特
发布于 2017/02/23 13:53
字数 647
阅读 1
收藏 1
点赞 0
评论 0

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

    普通数组的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
杭州
程序员
浅解前端必须掌握的算法(五):堆排序(上)

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

程序猿何大叔
07/02
0
0
狮子的魂/celib

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

狮子的魂
2014/09/13
0
0
C 扩展类库--celib

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

狮子的魂
2014/01/03
1K
0
菜鸟数据科学入门01 - 工具包概略

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

Kidult
2017/12/21
0
0
【目录】Linux 环境C/C++ 开发笔记,持续更新

C++ 知识要点: 计算机经典书籍 收藏,不断更新..... http://990487026.blog.51cto.com/10133282/1876827 【平台搭建】 编程语言排行榜: http://www.tiobe.com/tiobe_index?page=index QT w...

990487026
2016/05/18
0
0
深入分析ConcurrentHashMap(VS Hashtable VS HashMap)

聊聊并发(四)深入分析ConcurrentHashMap本文是作者原创,发表于InfoQ:http://www.infoq.com/cn/articles/ConcurrentHashMap 术语定义术语 英文 解释哈希算法 hash algorithm 是一种将任意...

tantexian
2016/05/27
27
0
浅入浅出数据结构(1)——什么是数据结构及算法

在很多数据结构相关的书籍,尤其是中文书籍中,常常把数据结构与算法“混合”起来讲,导致很多人初学时对于“数据结构”这个词的意思把握不准,从而降低了学习兴趣和学习信心。然而实际上,数...

你的社交帐号昵
05/15
0
0
面试常考的常用数据结构与算法【简】

数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的时间内考察一个人...

anlve
05/01
0
0
浅解前端必须掌握的算法(五):堆排序(下)

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

程序猿何大叔
07/05
0
0
利用线性表的顺序结构求集合的并、交、差、补(C语言实现)

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算,做个记录,希望也能帮助到其他人。 一、算法分析   (1)用数组A,B,C,E表示集合。假定A={1,3,4,5,6...

Tim_JX
2014/03/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

sap netweaver developer studio安装svn插件

问题 我现在在Sap的IDE(netweaver developer studio)上面安装svn插件。 步骤 确定IDE使用的eclipse版本 Help→About SAP NetWeaver Developer Studio→Installation Details→Features→F...

亚林瓜子
8分钟前
0
0
Spring Cloud云服务架构 - commonservice-config配置服务搭建

1. 介绍 Spring Cloud Config为分布式系统中的外部配置提供服务器和客户端支持。使用Config Server,您可以在所有环境中管理应用程序的外部属性。客户端和服务器上的概念映射与Spring Enviro...

itcloud
9分钟前
1
0
大数据开发学习的内容介绍,成都大数据培训机构哪里好?

大数据开发培训已经成为了越来越多人的选择,大数据开发工程师也是各公司争相争夺的金领人才之一了,在当今科技发展非常迅速的社会里,越来越多人把职业规划投向了大数据开发。这里为大家整理...

加米谷大数据
13分钟前
2
0
函数

函数 函数是Python中最主要也是最重要的代码组织和复用手段。作为最重要的原则,如果你要重复使用相同或非常类似的代码,就需要写一个函数。通过给函数起一个名字,还可以提高代码的可读性。...

火力全開
14分钟前
0
0
gulp-webserverf启动服务,局域网无法访问

如题,gulp-server启动的服务,只能本机访问,局域网通过ip无法访问; 启动的其它项目,均可以访问成功; 网上资源,很多说什么防火墙之类的问题,都无果; 只需要给启动服务添加参数即可, ...

littleFaye
16分钟前
0
0
RabbitMQ实战:5种模式和示例

应用RabbitMQ的5种队列 一、简单队列 P:消息的生产者 C:消息的消费者 红色:队列 生产者实现思路: 创建连接工厂ConnectionFactory,设置服务地址127.0.0.1,端口号5672,设置用户名、密码...

spinachgit
17分钟前
0
0
mysql常见报错标号对应原因以及处理方法

mysql常见报错标号以及对应解决方法 报错标号 报错现象 解决方法 原因 1449 Cause: java.sql.SQLException: The user specified as a definer ('authplat_dev'@'%') does not exist 在控制台...

ChinaHYF
19分钟前
0
0
Java 监控系统技术选型

(1)操作系统监控 Sigar oshi (2)Tomcat监控 JMX 日志 (3)Oracle监控 日志 直连SQL查询 基于Druid连接池 (4)拓扑图 jtopo http://www.jtopo.com/demo/statictis.html...

cccyb
21分钟前
1
0
解决IDEA中moduel配置了maven依赖可是依然不能使用依赖中的类

POM.xml中明明配置了依赖,也开启了maven的 auto-import 下面的刷新maven也没用: 直到使用下面的解决办法才使依赖生效: IDEA打开右侧 maven projects 点击顶部的M图表(看下图) 出现如下对...

颖辉小居
22分钟前
0
0
Nginx proxy pass路由转发简单用法

一,在nginx中配置proxy_pass时的加不加/的问题要注意proxy_pass后的url最后的/当加上了/,相当于是绝对根路径,则nginx不会把location中匹配的路径部分代理走如果没有/,则会把匹配的...

binhu
22分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部