八大数据结构
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;
}@Overridepublic boolean hasNext() {if (this.data == null) {return false;
}if (this.cursor < this.size) {return true;
}return false;
}@Overridepublic 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();
}
}
