八大数据结构

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("%dt", array[i][j]);
}
System.out.println();
}
for (int i = 0; i < 45; i++) {
System.out.printf("%s", "--");
}
System.out.println();
}

}