Java，数据结构和算法，八大数据结构，动态数组、稀疏数组

IT小奋斗2021-02-12 22:10:13

八大数据结构

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();}}