数据结构之数组

数组是应用最广泛的一种数据结构，常常被植入到编程语言中，作为基本数据类型使用，因此，在一些教材中，数组并没有被当做一种数据结构单独拿出来讲 解（其实数组就是一段连续的内存，即使在物理内存中不是连续的，在逻辑上肯定是连续的）。其实没必要在概念上做纠缠，数组可以当做学习数据结构的敲门砖， 以此为基础，了解数据结构的基本概念以及构建方法数据结构不仅是数据的容器，还要提供对数据的操作方法，比如检索、插入、删除、排序等。

无序数组

下面我们建立一个类，对数组的检索、插入、删除、打印操作进行封装，简便起见，我们假设数组中没有重复值（实际上数组可以包含重复值）。

[java] view plaincopyprint?

1. public class Array { 
2.        
3.       private String [] strArray; 
4.       private int length = 0;       //数组元素个数 
5.              
6.       //构造方法，传入数组最大长度 
7.       public Array(int max){ 
8.              strArray = new String [max]; 
9.       } 
10.        
11.       //检测数组是否包含某个元素，如果存在返回其下标，不存在则返回-1 
12.       public int contains(String target){ 
13.              int index = -1; 
14.              for(int i=0;i<length;i++){ 
15.                     if(strArray[i] == target){ 
16.                            index = i; 
17.                            break; 
18.                     } 
19.              } 
20.              return index; 
21.       } 
22.        
23.       //插入 
24.       public void insert(String elem) { 
25.              strArray[length] = elem; 
26.              length++; 
27.       } 
28.        
29.       //删除某个指定的元素值，删除成功则返回true，否则返回false 
30.       public boolean delete(String target){ 
31.              int index = -1; 
32.              if((index = contains(target)) !=-1){ 
33.                     for(int i=index;i<length-1;i++){ 
34.                            //删除元素之后的所有元素前移一位 
35.                            strArray[i] =strArray[i+1];   
36.                     } 
37.                     length--; 
38.                     return true; 
39.              }else{ 
40.                     return false; 
41.              } 
42.       } 
43.        
44.       //列出所有元素 
45.       public void display(){ 
46.              for(int i=0;i<length;i++){ 
47.                     System.out.print(strArray[i]+"\t"); 
48.              } 
49.       } 
50.        
51. } 

无序数组的优点：插入快，如果知道下标，可以很快的存取

无序数组的缺点：查找慢，删除慢，大小固定。

有序数组

所谓的有序数组就是指数组中的元素是按一定规则排列的，其好处就是在根据元素值查找时可以是使用二分查找，查找效率要比无序数组高很多，在数据量很大时更加明显。当然缺点也显而易见，当插入一个元素时，首先要判断该元素应该插入的下标，然后对该下标之后的所有元素后移一位，才能进行插入，这无疑增加了很大的开销。

因此，有序数组适用于查找频繁，而插入、删除操作较少的情况。

有序数组的封装类如下，为了方便，我们依然假设数组中是没有重复值的，并且数据是按照由小到大的顺序排列的。

[java] view plaincopyprint?

1. public class OrderArray { 
2.       private int [] intArray; 
3.       private int length = 0;       //数组元素个数 
4.        
5.       //构造方法，传入数组最大长度 
6.       public OrderArray(int max){ 
7.              intArray = new int [max]; 
8.       } 
9.        
10.       //用二分查找法定位某个元素，如果存在返回其下标，不存在则返回-1 
11.       public int find(int target){ 
12.              int lowerBound = 0;                 //搜索段最小元素的小标 
13.              int upperBound = length-1;      //搜索段最大元素的下标 
14.              int curIn;                                   //当前检测元素的下标 
15.              
16.              if(upperBound<0){     //如果数组为空，直接返回-1 
17.                     return -1; 
18.              } 
19.              
20.              while(true){ 
21.                     curIn =(lowerBound+upperBound)/2; 
22.                      
23.                     if(target == intArray[curIn]){ 
24.                            return curIn; 
25.                     }else if(curIn ==lowerBound){ 
26.                     //在当前下标与搜索段的最小下标重合时，代表搜索段中只包含1个或2个元素， 
27.                     //如果低位元素和高位元素都不等于目标元素，证明数组中没有该元素，搜索结束 
28.                            if(target !=intArray[upperBound]){ 
29.                                   return -1; 
30.                            } 
31.                     }else{//搜索段中的元素至少有三个，且当前元素不等于目标元素 
32.                            if(intArray[curIn]< target){ 
33.                                   //如果当前元素小于目标元素，则将下一个搜索段的最小下标置为当前元素的下标 
34.                                   lowerBound =curIn; 
35.                            }else{ 
36.                                   //如果当前元素大于目标元素，则将下一个搜索段的最大下标置为当前元素的下标 
37.                                   upperBound =curIn; 
38.                            } 
39.                     } 
40.              } 
41.       } 
42.        
43.       //插入 
44.       public void insert(int elem) { 
45.              int location = 0; 
46.              
47.              //判断应插入位置的下标 
48.              for(;location<length;location++){ 
49.                     if(intArray[location] >elem) 
50.                            break; 
51.              } 
52.              //System.out.println(location); 
53.              //将插入下标之后的所有元素后移一位 
54.              for(inti=length;i>location;i--){ 
55.                     intArray[i] = intArray[i-1]; 
56.              } 
57.              
58.              //插入元素 
59.              intArray[location] = elem; 
60.              
61.              length++; 
62.       } 
63.        
64.       //删除某个指定的元素值，删除成功则返回true，否则返回false 
65.       public boolean delete(int target){ 
66.              int index = -1; 
67.              if((index = find(target)) != -1){ 
68.                     for(inti=index;i<length-1;i++){ 
69.                            //删除元素之后的所有元素前移一位 
70.                            intArray[i] = intArray[i+1];   
71.                     } 
72.                     length--; 
73.                     return true; 
74.              }else{ 
75.                     return false; 
76.              } 
77.       } 
78.        
79.       //列出所有元素 
80.       public void display(){ 
81.              for(int i=0;i<length;i++){ 
82.                     System.out.print(intArray[i]+"\t"); 
83.              } 
84.              System.out.println(); 
85.       } 
86. } 

有序数组最大的优势就是可以提高查找元素的效率，在上例中，find方法使用了二分查找法，该算法的示意图如下：

这个方法在一开始设置变量lowerBound和upperBound指向数组的第一个和最后一个非空数据项。通过设置这些变量可以确定查找的范围。然后再while循环中，当前的下标curIn被设置为这个范围的中间值。

如果curIn就是我们要找的数据项，则返回下标，如果不是，就要分两种情况来考虑：如果curIn指向的数据项比我们要找的数据小，则证明该元素 只可能在curIn和upperBound之间，即数组后一半中（数组是从小到大排列的），下轮要从后半段检索；如果curIn指向的数据项比我们要找的 数据大，则证明该元素只可能在lowerBound和curIn之间，下一轮要在前半段中检索。

按照上面的方法迭代检索，直到结束。

有序数组的优点：查找效率高

有序数组的缺点：删除和插入慢，大小固定

原文链接：http://blog.csdn.net/u012152619/article/details/41774325