数据结构
数据结构包括
- 线性结构(数据元素之间存在一对一的线性关系)
- 顺序存储结构(数组)
- 顺序存储的线性表为顺序表,顺序表中的元素是连续的
- 链式存储结构 (链表)
- 链式存储的线性表为链表,链表存储元素不一定连续,元素节点中存储数据元素以及相邻元素的地址信息
- 数组
- 队列
- 链表
- 栈
- 顺序存储结构(数组)
- 非线性结构
- 二维数组
- 多维数组
- 广义表
- 树结构
- 图结构
稀疏数组
实际的一个需求:
编写的五子棋程序中,有存盘退出和续上盘的功能
使用二维数组记录棋盘
分析问题
因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据
由此引申出稀疏数组
- 稀疏数组
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组
稀疏数组处理的方法是:
- 记录数组一共有几行几列,有多少不同的值
- 把具有不同值得元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
举例
原始的二维数组:
0 0 0 22 0 0 15
0 11 0 0 0 17 0
0 0 0 -6 0 0 0
0 0 0 0 0 39 0
91 0 0 0 0 0 0
0 0 28 0 0 0 0
转换后:
行 | 列 | 值 | |
---|---|---|---|
[0] | 6(这里记录了该数组有多少行) | 7(这里记录了该数组有多少列) | 8(这里记录的是有多少值) |
[1] | 0 | 3 | 22 |
[2] | 0 | 6 | 15 |
[3] | 1 | 1 | 11 |
[4] | 1 | 5 | 17 |
[5] | 2 | 3 | -6 |
[6] | 3 | 5 | 39 |
[7] | 4 | 0 | 91 |
[8] | 5 | 2 | 28 |
二维数组转稀疏数组的思路:
- 遍历原始的二维数组,得到有效数据的个数
sum
- 根据sum就可以创建稀疏数组sparseArr
int[sum + 1][3]
- 将二维数组的有效数据存入稀疏数组
稀疏数组转原始的二维数组的思路:
- 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的
chessArr = int[6][7]
- 在读取稀疏数组后几行的数据,并赋值给原始的二维数组即可
代码实现
/**
* @description:稀疏数组和二维数组
* @author :virus
* @date :2020/4/18 18:09
*/
package structAndComputed;
public class SparseArr {
public static void main(String[] args) {
// 1. 创建一个原始的二维数组 11 * 11
// 0:表示没有棋子 1表示黑子 2表示白子
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
// 输出原始的二维数组
System.out.println("原始的二维数组:");
for (int[] row : chessArr1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
// 将二维数组 转 稀疏数组
// 1. 得到非0的数据的个数
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j] != 0) {
sum++;
}
}
}
// 2. 创建一个对应的稀疏数组
int sparseArr[][] = new int[sum + 1][3];
// 给稀疏数组赋值
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
// 遍历二维数组,将非0的值存放到稀疏数组中
int count = 0; // 用于记录是第几个非0数据
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j] != 0) {
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr1[i][j];
}
}
}
// 输出稀疏数组的形式
System.out.println("稀疏数组的输出:");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
}
System.out.println();
// 将稀疏数组 恢复成 二维数组
// 1. 先读取稀疏数组的第一行,创建原始的二维数组
int chessArr2[][] = new int[sparseArr[0][1]][sparseArr[0][1]];
// 2. 读取稀疏数组的后几行的数据(从第2行开始),并赋值给二维数组即可
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
// 输出恢复后的二维数组
System.out.println("恢复后的二维数组");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
二叉树的各种计算公式
n
个节点的二叉树一共有((2n)!)/(n! * (n+1)!)
种
n
层二叉树的第n层最多为2^(n-1)
个
- 二叉树节点计算公式
N = n0+n1+n2
,度为0
的叶子节点比度为2
的节点数多一个。N=1*n1+2*n2+1
- 对任何一棵二叉树T,如果其终端节点数为
n0
,度为2
的节点数为n2
,则n0=n2+1
- 具有
n
个节点的完全二叉树的深度为log2(n) + 1
排序算法
常见的冒泡排序
PHP版本
/**
* 冒泡排序
* @param array $arr
* @return array
*/
function bubble($arr = [])
{
$c = count($arr);
for ($i = 0; $i < $c - 1; $i++) {
for ($j = 0; $j < $c - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
数组元素反转
思路:
就是对称位置的元素反转,表示对称位置需要两个索引
需要用第三个变量进行交换
min代表最左边的索引,max代表最右边的索引
当min < max时,代表反转完成,停止循环,这是条件
min从左往右 ,为++
max从右往左,为–
Java
public class Demo03ArrayReverse {
public static void main(String[] args) {
int[] array = { 10, 20, 30, 40, 50 };
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
System.out.println("===============");
for (int min = 0, max = array.length - 1;min < max; min++, max--) {
int temp = array[min];
array[min] = array[max];
array[max] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
}
比较数组元素的最大值
看过的一个很好的例子,
比武招亲
意思就是说很多选手组成了一个数组 =>
int array = {X,X,X,X}
比如设定第一个为当前擂主 =>
int max = arrary[0]
然后依次上擂台比试,就是循环,依次留下最大的,最后留下的就是最大的
Java
public class Demo02ArrayMax {
public static void main(String[] args) {
// 5个选手
int[] array = { 5, 15, 30, 20, 10000};
int max = array[0]; // 比武擂台
for (int i = 1; i < array.length; i++) {
// 如果当前元素,比max更大,则换人
if (array[i] > max) {
max = array[i];
}
}
// 谁最后最厉害,就能咋max当中留下最大值
System.out.println("最大值:" + max);
}
}
字符串匹配问题
问题描述:
有一个字符串
str1 = “abceddededqw”
和一个子串str2="dde"
现在要判断str1是否含有str2,如果存在,就返回第一次出现的位置,如果没有,就返回-1
要求用最快的速度来完成匹配
- 常见思维:暴力匹配
- KMP算法:《部分匹配表》
马踏棋盘
方法:图的深度优先遍历算法DFS + 贪心算法