資料結構之 數組

前序

前兩天在想研究樹時，想寫出樹的廣度優先周遊算法，但是想不出來怎麼寫，也參考了其它人寫的，但是還是了解不了程式的執行順序，

于是覺得自己還是從頭開始學習下資料結構，本來在大學時期已經重修過了的

，由于大一沒好好學習C語言，

是以後面第一次學習資料結構的時就可想而知了，我也忘記了考試成績，反正沒及格，補考也沒及格，大三的時候又重修了遍，第二次學習比

第一次學習是好一些，考試還得了80幾分了，也能大概看懂C語言程式了。

無序數組

     我是Java程式員，大多時候自己在程式中使用的都是使用無序數組，自己寫了一個無序數組的例子

package com.jaws.array;

public class NoSequenceArray {
	private int[] array = null;
	private int index = 0;//索引
	
	public  NoSequenceArray(int max) {
		array = new int[max];
	}
	
	/**
	 * 添加元素
	 * @param element
	 */
	public void add(int element){
		if (index>array.length-1) {
			throw new ArrayIndexOutOfBoundsException("數組容量已達到最大容量!");
		}
		this.array[index] = element;
		index++;
	}
	
	/**
	 * 根據元素值查找索引
	 * @param element
	 * @return 索引
	 */
	public int searchIndex(int element){
		for (int i = 0; i < this.index; i++) {
			if(element == array[i]){
				return i;
			}
		}
		return -1;
	}
	

	/**
	 * 删除元素
	 * @param element
	 */
	public void delete(int element){
		int indexTarget = this.searchIndex(element);
		if (indexTarget==-1) {
			return;
		}
		for (int i = indexTarget; i < this.index; i++) {
			array[i]=array[i+1];
		}
		array[this.index] = 0;
	}
	
	public void println(){
		System.out.println("數組包含的元素為：");
		for (int i = 0; i < array.length; i++) {
			System.out.println("["+i+"]"+":"+array[i]);
		}
	}
	
	public static void main(String[] args) {
		NoSequenceArray array = new NoSequenceArray(10);
		array.add(3);
		array.add(20);
		array.add(8);
		array.add(33);
		array.add(15);
		array.println();
		System.out.println("8的索引為："+array.searchIndex(8));
		array.delete(8);
		System.out.println("8的索引為："+array.searchIndex(8));
		array.println();
	}
}
           

輸出結果：

數組包含的元素有：
[0]:3
[1]:20
[2]:8
[3]:33
[4]:15
[5]:0
[6]:0
[7]:0
[8]:0
[9]:0
8的索引為：2
8的索引為：-1
數組包含的元素有：
[0]:3
[1]:20
[2]:33
[3]:15
[4]:0
[5]:0
[6]:0
[7]:0
[8]:0
[9]:0
           

  分析無序數組時間複雜度

操作	時間複雜度
插入	1
查找	O(N)
删除	O(N)

      插入操作，隻需在數組尾部插入資料即可，執行一步，是以時間複雜度為1

      查詢操作，數組長度為N，需要循環比對元素，如果運氣好，第一個元素為需要查找目标，如果運氣最差，最後一個元素為需要找到目标，

是以需要執行的步數為N/2，時間複雜度也就是O(N)

      删除操作，需要先查找到目标元素，再将[目标索引+1]到[N-1]的元素往前移動一步，是以整個删除操作需要N步，時間複雜度為O(N)

有序數組

    有序數組真很少使用，JDK提高的Arrays類提供對無序數組的排序功能和其它有用的功能，修改下測試的代碼

public static void main(String[] args) {
			NoSequenceArray noSeqArray = new NoSequenceArray(10);
			noSeqArray.add(3);
			noSeqArray.add(20);
			noSeqArray.add(8);
			noSeqArray.add(33);
			noSeqArray.add(15);
<span style="white-space:pre">			</span>System.out.println("排序前："+Arrays.toString(noSeqArray.array));
<span style="white-space:pre">			</span>Arrays.sort(noSeqArray.array);
<span style="white-space:pre">			</span>System.out.println(Arrays.binarySearch(noSeqArray.array, 33));
<span style="white-space:pre">			</span>System.out.println("排序後: "+Arrays.toString(noSeqArray.array));
		}
           

測試結果：

排序前：[3, 20, 8, 33, 15, 0, 0, 0, 0, 0]
9
排序後: [0, 0, 0, 0, 0, 3, 8, 15, 20, 33]
           

在使用過程發現了toString()方法，是以前面的無序的數組程式并不需要自己寫println方法，意外的發現啊

，還有排序、針對有序數組的二分法查找、填充(fill,用指定值填滿整個數組)、複制數組、equals等很多的有用功能。有時候寫自己寫了一些功能，在查詢JDK API時卻發現JDK已經提供了相同的功能，是以以為要多看看JDK API，說不定會有意外的收獲。