数据结构与算法01 之数组-阿里云开发者社区

数据结构与算法01 之数组

2016-05-26 1208

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

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

普通数组的Java代码：

[java]view plain copy 
 
public class GeneralArray {  
    private int[] a;  
    private int size; //数组的大小  
    private int nElem; //数组中有多少项  
    public GeneralArray(int max) { //初始化数组  
        this.a = new int[max];  
        this.size = max;  
        this.nElem = 0;  
    }  
    public boolean find(int searchNum) { //查找某个值      
        int j;  
        for(j = 0; j < nElem; j++){  
            if(a[j] == searchNum)  
                break;  
        }  
        if(j == nElem)  
            return false;  
        else  
            return true;  
    }  
    public boolean insert(int value) { //插入某个值  
        if(nElem == size){  
            System.out.println("数组已满！");  
            return false;  
        }  
        a[nElem] = value;  
        nElem++;          
        return true;  
    }  
    public boolean delete(int value) {//删除某个值  
        int j;  
        for(j = 0; j < nElem; j++) {  
            if(a[j] == value) {  
                break;  
            }  
        }  
        if(j == nElem)   
            return false;  
        if(nElem == size) {  
            for(int k = j; k < nElem - 1; k++) {  
                a[k] = a[k+1];  
            }  
        }  
        else {  
            for(int k = j; k < nElem; k++) {  
                a[k] = a[k+1];  
            }  
        }  
        nElem--;  
        return true;  
    }  
    public void display() { //打印整个数组  
        for(int i = 0; i < nElem; i++) {  
            System.out.print(a[i] + " ");  
        }  
        System.out.println("");  
    }  
}    

有序数组的java代码：

[java]view plain copy 
 
public class OrderedArray {  
    private long[] a;  
    private int size; //数组的大小  
    private int nElem; //数组中有多少项  
    public OrderedArray(int max) { //初始化数组  
        this.a = new long[max];  
        this.size = max;  
        this.nElem = 0;  
    }  
    public int size() { //返回数组实际有多少值  
        return this.nElem;  
    }  
//--------------二分法查找某个值----------------//  
    public int find(long searchNum) {  
        int lower = 0;  
        int upper = nElem - 1;  
        int curr;  
        while(true) {  
            curr = (lower + upper) / 2;  
            if(a[curr] == searchNum)  
                return curr;  
            else if(lower > upper)   
                return -1;  
            else {  
                if(a[curr] < searchNum)   
                    lower = curr + 1;  
                else  
                    upper = curr - 1;  
            }  
              
        }  
    }  
    public boolean insert(long value) { //插入某个值  
        if(nElem == size){  
            System.out.println("数组已满！");  
            return false;  
        }  
        int j;  
        for(j = 0; j < nElem; j++){  
            if(a[j] > value)  
                break;  
        }  
          
        for(int k = nElem; k > j; k--) {  
            a[k] = a[k-1];  
        }  
        a[j] = value;  
        nElem++;          
        return true;  
    }  
    public boolean delete(long value) { //删除某个值  
        int j = find(value);  
        if(j  == -1){  
            System.out.println("没有该元素！");  
            return false;  
        }  
        if(nElem == size) {  
            for(int k = j; k < nElem - 1; k++) {  
                a[k] = a[k+1];  
            }         
            a[nElem-1] = 0;  
        }  
        else {  
            for(int k = j; k < nElem; k++) {  
                a[k] = a[k+1];  
            }  
        }  
        nElem--;  
        return true;  
    }  
    public void display() { //打印整个数组  
        for(int i = 0; i < nElem; i++) {  
            System.out.print(a[i] + " ");  
        }  
        System.out.println("");  
    }  
}  

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

数组比较简单，就讨论这么多，如有错误，欢迎留言指正~

转载：http://blog.csdn.net/eson_15/article/details/51126182

数据结构与算法01 之数组

热门文章

最新文章

相关课程

相关电子书

相关实验场景