數據結構之數組_數據分析師

數組是應用最廣泛的一種數據結構，常常被植入到編程語言中，作為基本數據類型使用，因此，在一些教材中，數組并沒有被當做一種數據結構單獨拿出來講 解（其實數組就是一段連續的內存，即使在物理內存中不是連續的，在邏輯上肯定是連續的）。其實沒必要在概念上做糾纏，數組可以當做學習數據結構的敲門磚， 以此為基礎，了解數據結構的基本概念以及構建方法數據結構不僅是數據的容器，還要提供對數據的操作方法，比如檢索、插入、刪除、排序等。

無序數組

下面我們建立一個類，對數組的檢索、插入、刪除、打印操作進行封裝，簡便起見，我們假設數組中沒有重復值（實際上數組可以包含重復值）。

[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之間，下一輪要在前半段中檢索。文章來自：CDA數據分析師培訓官網

按照上面的方法迭代檢索，直到結束。

有序數組的優點：查找效率高

有序數組的缺點：刪除和插入慢，大小固定