数据结构与常用算法的学习、刷题.zip

# data-structure章节 归纳过去和现在所学习的 数据结构与常用算法知识、以及刷题 ## 数据结构的基本概念 - 什么是数据？ > 数据（data）是描述客观事物的数字和字符的集合。 - 什么是数据对象？ > 数据对象（data object）是指性质相同的数据元素的集合，它是数据的一个子集。 - 什么是数据项？ > 数据项（data item）是具有独立含义的数据的最小单位，也称为字段或域（Feild）。 - 什么是数据结构？ > 数据结构（data structure）是指所有数据元素以及数据元素之间的关系，可看作是相互之间存在着某种特定关系的数据集合。 >> 数据结构可以分为逻辑结构和存储结构； >>> 逻辑结构由数据元素之间的逻辑关系构成。 >>> 存储结构是数据元素及关系（即逻辑结构）在计算机存储器中的存储表示，也成为数据的物理结构。 > 数据的运算：施加在该数据上的操作。 > 数据逻辑结构与数据存储结构无关，是独立于计算机，可以看作对现实世界中具体问题抽象而来的数学模型。 > 在现实世界中，元素之间的关系往往是多样的，但在数据结构中聚焦于讨论数据元素间的相邻和邻接关系。 > 数据逻辑结构的描述方式： > - 图表表示 （可以是类似于关系型数据库的数据表; 也可以是其他的简图，达意即可） > - 二元组表示 > 逻辑结构的类型 > - 集合（彼此间没有相邻关系，仅仅是“同属一个集合”） > - 线性结构 （彼此在排列上是一对一关系；除了首端元素的其他每个元素有且仅有一个前驱动元素，除了末端元素的其他元素有且仅有一个后继元素） > - 树形结构 （彼此间一对一关系；除首端元素外其他有且仅有一个前驱元素，除了末端元素外其他元素有一个或多个后继元素） > - 图形元素 （彼此间是多对多关系；每个元素都至少有一个前驱元素，至少有一个后继元素） > 存储结构的类型 > - 顺序存储结构：采用一组连续的存储单元存放所有的数据元素，所有的数据元素在计算机存储中占有一整块存储单元。 > - 链式存储结构：每个元素用一个内存结点存储，每个节点是单独分配的，所有的节点地质不一定是连续的。为了表示元素间的逻辑关系，给每个节点附加指针域，用于存放相邻节点的内存地址。 > - 索引存储结构：在存储元素数据的同时还建立附加的索引表；存储所有数据元素信息的表称为主数据表，其中每个数据元素有一个关键字和对应的存储地址。 > - 哈希存储结构：只存储元素的数据，不存储元素之间的逻辑关系。基本思想是根据元素的关键字通过哈希算法来计算一个值，将该值作为元素的内存地址来存储。 > ADT > 指的是用户进行软件设计从具体问题抽象而来的逻辑数据结构和基于逻辑数据结构上的运算（不考虑在计算机存储器中的具体存储） > ADT的描述： ``` ADT 抽象数据类型名称 { 数据对象：数据对象的声明 数据关系：数据关系的声明 基本运算：基本运算的声明 ( 基本运算名(参数列表):运算功能描述 ) } ``` --- ## 一. 线性表 ### (1) 稀疏数组 - ***稀疏数组的应用场景***:当某个二维数组中大部分元素都为0或者其他默认值，且只有极少量的不同值时；可以使用稀疏数组结构， 将原数组进行压缩，用压缩后的数组存储到磁盘中；从磁盘中读取出来使用时，再根据压缩逻辑将压缩后的数组 还原为原数组；这样达到了节省内存，节约磁盘的IO资源。 - ***稀疏数组的实现思路***: 1. 首行用于记录数组一共有几行几列，以及不同值数量； 2. 其他行用于记录 不同值的位置（所在行与所在列）和数值信息 ``` public class SparseArray { /** * 生成一个用于压缩示例的 16*16二维数组 */ public int[][] initArraydemo(){ int[][] arrDemo = new int[16][16]; //默认值为0 arrDemo[6][8] = 1; arrDemo[7][9] = 2; arrDemo[14][15] = 3; return arrDemo; } /** * 原数组压缩为稀疏数组 * @return 压缩后的数组 */ public int[][] transferToSparse(int[][] arr){ int count = 0;//记录不同值个数 for (int i = 0; i < arr.length; i++) { for (int i2 = 0; i2 < arr[i].length; i2++) { if(arr[i][i2] != 0){ count++; } } } //初始化压缩后的数组 int[][] newArr = new int[count + 1][3]; newArr[0][0] = arr.length; newArr[0][1] = arr[0].length; newArr[0][2] = count; int lines = 0;//记录不同值的行数 for (int i = 0; i < arr.length; i++) { for (int i2 = 0; i2 < arr[i].length; i2++) { if(arr[i][i2] != 0){ lines++; newArr[lines][0] = i; newArr[lines][1] = i2; newArr[lines][2] = arr[i][i2]; } } } return newArr; } /** * 将压缩后的稀疏数组还原为原数组 */ public int[][] rtnToArrSource(int[][] arr){ if(arr.length<1 || arr[0].length != 3){ throw new RuntimeException("压缩数组数据有误!"); } int[][] arrSource = new int[arr[0][0]][arr[0][1]]; for (int i = 1; i <= arr[0][2]; i++) { arrSource[arr[i][0]][arr[i][1]] = arr[i][2]; } return arrSource; } /** * 打印数组 * @param arr */ private void printArr(int[][] arr){ for (int i = 0; i < arr.length; i++) { for (int i1 = 0; i1 < arr[i].length; i1++) { System.out.printf("%d\t",arr[i][i1]); } System.out.println(); } } public static void main(String[] args) { SparseArray demo = new SparseArray(); int[][] arrSource = demo.initArraydemo(); demo.printArr(arrSource); System.out.println(); int[][] transferedArr = demo.transferToSparse(arrSource); demo.printArr(transferedArr); System.out.println(); demo.printArr(demo.rtnToArrSource(transferedArr)); } ``` ##### 附:手写动态数组--ArrayList自实现 ``` public class MyArrayList<E> implements MyList<E> { private final static int DEFAULT_CAPACITY = 10; private E[] arr;//基础数组 private int capacity; //当前基础数组的容量 private int size ; //当前动态数组的长度 public MyArrayList(int initCapacity){ doClear(initCapacity); } public MyArrayList(){ doClear(DEFAULT_CAPACITY); } public boolean add(E e) { //是否要扩容？ ensureCapacity(size+1); arr[size++] = e; return true; } public boolean add(int index, E e) { checkIndexIllegal(index); ensureCapacity(size+1); for (int i = size-1; i >= index; i--) { arr[i+1] = arr[i]; } arr[index] = e; size++; return true; } public E remove(int index) { checkIndexIllegal(index); E e = arr[index]; for (int i = index+1; i < size; i++) { arr[i-1] = arr[i]; } size--; ensureCapacity(size+1); //是否需要缩容 retu