数据结构
学前
经典算法面试例题：
1)有一个字符串str1="123 1234 12345"，和一个子串str2="1234"
现在要判断str1是否含有str2，如果存在，返回第一次出现的位置，否则返回-1
// KMP算法 - 部分匹配表
2)汉诺塔游戏
小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘
// 分治算法
3)八皇后问题
在8 * 8格的国际象棋上摆放八个皇后
任意两个皇后都不能处于同一行、同一列、同一斜线上，问有多少种摆法
// 回溯算法
4)马踏棋盘（骑士周游问题）
将马随机放在国际象棋的8 * 8格棋盘上
按马走日进行移动，每个方格只进入一次，走遍棋盘上全部方格
// 图的深度优化遍历算法（DFS）+贪心算法优化
数据结构和算法概述
数据（data）、结构（structure）研究组织数据的方式，提高代码效率及美观
用程序解决现实生活中的问题
程序 = 数据结构 + 算法
实际编程中的问题
public static void main(String[] args){
String str = "Java";
String newStr = str.replaceAll("MyJava"); // 算法支撑的字符串替换方法
System.out.println("newStr = "+newStr);
}
// 例：试写出用单链表表示的字符串类及字符串节点类的定义，
// 并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置的成员函数
// 例：五子棋游戏
// 判断游戏输赢，实现存盘退出和继续上局
// 棋盘—>二维数组（稀疏数组）—>写入文件（存档）—>读取文件（读取二维数组）->恢复成二维数组棋盘（接上局）
// 例：约瑟夫问题（丢手帕问题） => 单项环形链表
// 修路问题 => 最小生成树（数据结构 + 普利姆算法）
// 最短路径问题 => 图 + 弗洛伊德算法 线性结构和非线性结构
线性结构
特点：数据元素之间存在一对一的线性关系
存储结构： 顺序存储结构、链式存储结构
顺序存储的线性表称为顺序表，其中存储的元素是连续的
链式存储的线性表称为链表，其中存储的元素不一定连续，元素节点中存放数据元素以及相邻元素的地址信息
例：数组、队列、链表、栈
非线性结构
例：二维数组（多维数组）、广义表、数结构、图结构
稀疏数组和队列
稀疏（sparsearray）数组
要求：编写五子棋程序中存盘退出和续上盘功能
分析问题：存盘使用的二维数组很多值为默认0，记录了很多没有意义的数据 -> 稀疏数组
当一个数组中大部分元素为同一个值时，使用稀疏数组保存
处理方法：
记录数组行列数，不同值的个数
把具有不同值的元素行列及值记录在一个小规模数组中，缩小程序的规模
应用实例：
使用稀疏数组，保留二维数组（棋盘、地图等）
把稀疏数组存盘，并且可以重新恢复为原来的二维数组
转换思路：
1. 遍历原始二维数组，得到有效数据的个数sum
2. 根据sum创建稀疏数组 sparseArr int [sum+1] [3]
3. 将二维数组的有效数据存入稀疏数组
// 将稀疏数组存盘到文件中
1. 读取稀疏数组的第一行，根据第一行数据，创建原始二维数组
2. 读取稀疏数组剩余行数据，赋给原始二维数组即可
代码实现：见eclipse
队列
基本概念：
队列是一个有序列表，可以用数组或链表实现
遵循先入先出原则
数组模拟队列
队列本身是有序列表，用数组结构存储列队数据
maxSize是列队最大容量，front / rear表示队列前后端，分别随着数据的输入 / 输出而改变
数据存入队列时称 " addQueue " ，两个步骤：
1) 将尾指针后移：rear + 1，当front == rear（空）
2) 若尾指针 rear 小于队列最大下标maxSize - 1 ，则将数据存入数组元素
否则无法存入数据。 当 rear == maxSize - 1 时，表示队列满
代码实现：见eclipse
拼多多集团-PDD公司福利 474人发布
