八大資料結構

1、什麼是資料結構？

資料結構是以某種特定的佈局方式儲存資料的容器；

2、為什麼需要資料結構？

資料是計算機科學當中最關鍵的實體，而資料結構則可以將資料以某種組織形式儲存；

3、常見的資料結構包含？

陣列、連結串列、佇列、棧、雜湊表、樹、堆和圖；

陣列（Array）：有序表，有序的元素序列；

陣列在記憶體中佔一片連續的儲存區；C語言中規定，陣列名就代表了該陣列的首地址；

動態陣列：在宣告時沒有確定陣列大小的陣列，當要用它時可重新指出陣列的大小；

稀疏陣列（Sparse Array）：一種只為陣列中的非零元素分配記憶體的特殊型別陣列，記憶體中儲存了稀疏陣列中非零元素的下標和值。

package com.what21.structure.array.dynamic.case01.mode01;import java.util.Iterator;public class DynamicArrayList<T> implements Iterable<T>{	// 擴容因子	private double capacityFactor;	private T[] data;	private int size = 0;	public DynamicArrayList() {		this(10, 1.5);	}	public DynamicArrayList(int size, double capacityFactor) {		this.capacityFactor = capacityFactor;		this.init(size);	}	@SuppressWarnings("unchecked")	private void init(int size) {		if (size >= 0) {			data = (T[]) new Object[size];		} else {			data = (T[]) new Object[10];		}	}	/**	 * 檢查擴容	 */	private void checkCapacity() {		if (size > data.length - 1) {			@SuppressWarnings("unchecked")			T[] capacityData = (T[]) new Object[(int) (data.length * this.capacityFactor)];			System.arraycopy(this.data, 0, capacityData, 0, this.data.length);			this.data = capacityData;		}	}	/**	 * 容器大小	 * 	 * @return	 */	public int size() {		return size;	}	/**	 * 新增元素	 * 	 * @param t	 */	public void add(T t) {		this.checkCapacity();		this.data[size++] = t;	}	/**	 * 獲取元素	 * 	 * @param index 下標	 * @return	 */	public T get(int index) {		T t = null;		if (index >= 0 && index < data.length) {			t = data[index];		}		return t;	}	/**	 * 移除元素	 * 	 * @param t	 */	public void remove(T t) {		if (t == null) {			return;		}		int operateIndex = -1;		for (int i = 0; i < this.size(); i++) {			if (t.equals(data[i])) {				operateIndex = i;			}		}		if (operateIndex > -1) {			removeByIndex(operateIndex);		}	}	/**	 * 新增元素	 * 	 * @param t	 */	public T removeByIndex(int index) {		// 檢查範圍		if (index < 0 || index > size - 1) {			return null;		}		T t = this.data[index];		@SuppressWarnings("unchecked")		T[] arrayData = (T[]) new Object[size];		System.arraycopy(this.data, 0, arrayData, 0, index);		System.arraycopy(this.data, index + 1, arrayData, index, size - index - 1);		this.data = arrayData;		size--;		return t;	}	public Iterator<T> iterator() {		return new DynamicArrayListIterator<T>(this.data, this.size);	}	// ===========================================================================//	// === java.util.Iterator	// ===========================================================================//		@SuppressWarnings("hiding")	private class DynamicArrayListIterator<T> implements Iterator<T> {		private T[] data;		private int size;		private int cursor = 0;		public DynamicArrayListIterator(T[] data, int size) {			this.data = data;			this.size = size;		}		@Override		public boolean hasNext() {			if (this.data == null) {				return false;			}			if (this.cursor < this.size) {				return true;			}			return false;		}		@Override		public T next() {			return this.data[this.cursor++];		}	}	// ===========================================================================//	// === The end	// ===========================================================================//}

package com.what21.structure.array.dynamic.case01.mode01;import java.util.Iterator;public class DynamicArrayListDemo {	public static void main(String[] args) {		// 定義動態陣列		DynamicArrayList<Integer> intList = new DynamicArrayList<Integer>();		// 初始化動態陣列		for (int i = 1; i <= 30; i++) {			intList.add(i);		}		// 列印動態陣列		System.out.println("普通的for迴圈訪問陣列：");		System.out.println("陣列的元素共有：" + intList.size());		for (int i = 0; i < intList.size(); i++) {			System.out.printf("%d ", intList.get(i));		}		System.out.println();		printSeparator();		// 操作動態陣列		int removeValue = intList.removeByIndex(9);		System.out.println("刪除元素值：" + removeValue);		intList.remove(27);		System.out.println("刪除元素值：" + 27);		intList.add(97);		System.out.println("新增元素值：" + 97);		intList.add(199);		System.out.println("新增元素值：" + 199);		printSeparator();		// 列印動態陣列		// 使用增強的for迴圈，需要實現java.lang.Iterable介面；		System.out.println("增強的for迴圈訪問陣列：");		System.out.println("陣列的元素共有：" + intList.size());		for (Integer value : intList) {			System.out.printf("%d ", value);		}		System.out.println();		printSeparator();		// 迭代器		System.out.println("迭代器遍歷陣列：");		Iterator<Integer> intIterator = intList.iterator();		while (intIterator.hasNext()) {			System.out.printf("%d ", intIterator.next());		}		System.out.println();	}	/**	 * @param array	 */	static void printSeparator() {		for (int i = 0; i < 45; i++) {			System.out.printf("%s", "--");		}		System.out.println();	}}

package com.what21.structure.array.sparser.case01.mode01;public class SparserArrayDemo {	public static void main(String[] args) {		// 11行11列		int[][] towDimensionArray = new int[11][11];		for (int i = 0; i < towDimensionArray.length; i++) {			for (int j = 0; j < towDimensionArray[0].length; j++) {				towDimensionArray[i][j] = 0;			}		}		// 賦值		towDimensionArray[1][2] = 1;		towDimensionArray[2][3] = 2;		towDimensionArray[3][4] = 3;		towDimensionArray[4][5] = 4;		towDimensionArray[5][6] = 5;		System.out.println("二維陣列：");		iterate(towDimensionArray);		// 轉稀疏陣列		int[][] sparserArray = toSparserArray(towDimensionArray);		System.out.println("二維陣列轉稀疏陣列：");		iterate(sparserArray);		System.out.println("稀疏陣列轉二維陣列：");		int[][] convertedTwoDimensionArray = toTwoDimension(11, 11, sparserArray);		iterate(convertedTwoDimensionArray);	}	/**	 * @param row          行	 * @param column       列	 * @param sparserArray 稀疏陣列	 * @return	 */	private static int[][] toTwoDimension(int rows, int column, int[][] sparserArray) {		int[][] twoDimensionArray = new int[rows][column];		if (twoDimensionArray == null || twoDimensionArray.length <= 0) {			return twoDimensionArray;		}		// 為二維陣列賦值		for (int i = 0; i < sparserArray.length; i++) {			int rowSubscript = sparserArray[i][0];			int columnSubscript = sparserArray[i][1];			int value = sparserArray[i][2];			twoDimensionArray[rowSubscript][columnSubscript] = value;		}		return twoDimensionArray;	}	/**	 * @param towDimensionArray	 */	static int[][] toSparserArray(int[][] towDimensionArray) {		// 第一步，求出有多少有效個數據		int rows = 0;		for (int[] oneDimensionArray : towDimensionArray) {			for (int value : oneDimensionArray) {				if (value > 0) {					rows++;				}			}		}		// 第二步：建立稀疏陣列		int[][] sparserArray = new int[rows][3];		// 第三步：為稀疏陣列賦值		int sparserArrayRows = 0;		for (int i = 0; i < towDimensionArray.length; i++) {			for (int j = 0; j < towDimensionArray[i].length; j++) {				int value = towDimensionArray[i][j];				if (value > 0) {					sparserArray[sparserArrayRows][0] = i;					sparserArray[sparserArrayRows][1] = j;					sparserArray[sparserArrayRows][2] = value;					sparserArrayRows++;				}			}		}		return sparserArray;	}	/**	 * @param array	 */	static void iterate(int[][] array) {		if (array == null || array.length <= 0) {			return;		}		for (int i = 0; i < 45; i++) {			System.out.print("--");		}		System.out.println();		// 列印		for (int i = 0; i < array.length; i++) {			for (int j = 0; j < array[i].length; j++) {				System.out.printf("%d\t", array[i][j]);			}			System.out.println();		}		for (int i = 0; i < 45; i++) {			System.out.printf("%s", "--");		}		System.out.println();	}}