数据结构与算法01 之数组
数据结构与算法01 之数组
乐在克里特 发表于12个月前
数据结构与算法01 之数组
  • 发表于 12个月前
  • 阅读 1
  • 收藏 1
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

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

    普通数组的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

标签: 数据结构基础
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 14
博文 254
码字总数 387494
×
乐在克里特
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: