# data-structure **Repository Path**: studygo/data-structure ## Basic Information - **Project Name**: data-structure - **Description**: 数据结构学习，刷题 - **Primary Language**: Java - **License**: MulanPSL-2.0 - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2021-10-13 - **Last Updated**: 2022-05-11 ## Categories & Tags **Categories**: Uncategorized **Tags**: 数据结构 ## README # 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 implements MyList { 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); //是否需要缩容 return e; } public boolean set(int index, E e) { checkIndexIllegal(index); arr[index] = e; return true; } public E get(int index) { checkIndexIllegal(index); return arr[index]; } public int size() { return size; } /** * 清空数组 */ public void clear(){ doClear(DEFAULT_CAPACITY); } private void doClear(int initCapacity){ arr = (E[]) new Object[initCapacity]; this.size = 0; } /** * 扩容与缩容的处理 * 扩容缩容要注意时间复杂的震荡的问题！ * @param needCapacity 当前需要的存储容量 */ private void ensureCapacity(int needCapacity) { if(needCapacity <= capacity) return; int newCapacity = needCapacity; if( needCapacity<<3 < capacity ) { //容量四倍于所需以上，缩容； newCapacity = capacity >> 2; } E[] newArr = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newArr[i] = arr[i]; } arr = newArr; } /** * 检测参数中的索引是否合法 */ private void checkIndexIllegal(int index) { if(index < 0 || index > size-1){ //抛出自定义异常 throw new IndexOutOfArrayExceptiom("数组索引越界，非法的index："+index); } } private class ArrayListIterator implements MyIterator{ private int current = 0; //当前迭代到的索引位置 public boolean hasNext() { return current < size; } public E next() { if(current > size-1){ throw new NoMoreElementInArray(); } return (E) arr[current++]; } public E remove() { checkIndexIllegal(current-1); return (E) MyArrayList.this.remove(--current); } } public MyIterator iterator(){ return new ArrayListIterator(); } public boolean contain(E item){ if(item == null) return false; for (int i = 0; i < size; i++) { if(arr[i] !=null && arr[i].equals(item) ){ return true; } } return false; } public int indexOf(E item){ if(item == null) return -1; for (int i = 0; i < size; i++) { if(arr[i] !=null && arr[i].equals(item) ){ return i; } } return -1; } } ``` --- ### (2) 队列 - 队列是一个有序列表，可以用数组（顺序存储）或链表（链式存储）来实现； - ***遵循先进先出***原则 #### 普通队列与循环队列 - 普通队列 - 数组模拟普通队列的实现思路： 1. 两个成员变量front与rear分别记录队列的队列头和队列尾索引值;front 随着出队而改变，rear随着入队而改变 2. 变量maxSize记录底层维护队列数据的数组的容量 3. 底层维护队列数据的数组 - 普通队列待优化的问题： 1. 数组只能使用一次就不能用了，造成空间的浪费；且容易索引越界。 ```$xslt public class OrdinaryQueue { //底层维护队列数据的数据 private int[] arr; private int maxSize; //底层数组容量 private int front; // 标记队列头索引 private int rear;//标记队列尾索引 public OrdinaryQueue(int size){ maxSize = size; arr = new int[maxSize]; //初始化标记队列头和队列尾索引的两个变量 front = -1; //在首元素索引的前一位； 出队时该值就增加 rear = -1; //尾元素索引; 入队时改值便增加 } public OrdinaryQueue(){ this(10); //默认容量为10 } /** * 队列是否已满 * @return */ public boolean isFull(){ return rear == maxSize-1; } /** * 队列是否为空 * @return */ public boolean isEmpty(){ return front == rear; } /** * 入队 * @param num * @return */ public boolean add(int num){ if(isFull()){ throw new RuntimeException("队列已满！"); } arr[++rear] = num; return true; } /** * 出队 * @return */ public int remove(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } return arr[++front]; } /** * 观察队列首位元素 * @return */ public int peek(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } return arr[front+1]; } /** * 展示队列所有元素 */ public void showQueue(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } int index = front+1; for (; index <= rear ; index++) { System.out.printf("arr[%d],%d",index,arr[index]); } } } ``` - 环形队列 ``` /** * 环形队列 */ public class CircleQueue { private final static int DEFAULT_SIZE = 10; //底层维护队列数据的数据 private E[] arr; private int maxSize; //底层数组容量 private int front; // 标记队列头索引 private int rear;//标记队列尾索引 public CircleQueue(int size){ maxSize = size + 1; //环形队列要一位出来 arr = (E[]) new Object[maxSize]; //初始化标记队列头和队列尾索引的两个变量 front = 0; //首元素下标 rear = 0; //尾元素下标后一位 } public CircleQueue(){ this(DEFAULT_SIZE); } /** * 队列是否已满 * front是首元素下标，rear是尾元素后一位;相邻时数组就已满，因为是环形的，可能front在rear前面，也可能在后面 * @return */ public boolean isFull(){ return (rear + 1) % maxSize == front; } /** * 队列是否为空 * @return */ public boolean isEmpty(){ return front == rear; } /** * 入队 * @return */ public boolean add(E e){ if( isFull() ){ throw new RuntimeException("队列已满！"); } arr[rear] = e; rear = (rear+1) % maxSize ; return true; } /** * 出队 * @return */ public E remove(){ if( isEmpty() ){ throw new RuntimeException("队列为空！"); } E e = arr[front]; front = (front+1) % maxSize; return e; } /** * 查看队首元素 * @return */ public E peek(){ if( isEmpty() ){ throw new RuntimeException("队列为空！"); } return arr[front]; } /** * 返回队列长度 * @return */ public int size(){ return (rear+maxSize-front) % maxSize; } /** * 展示队列所有元素 */ public void showQueue(){ if( isEmpty() ){ throw new RuntimeException("队列为空！"); } for (int i = front; i!=rear ; i = (i+1)%maxSize ) { System.out.printf("arr[%d]=%d; \n",i,arr[i]); } } } ``` - 带头结点和尾结点的单链表 来实现队列结构 > 不带尾结点只带头结点的单链表，只适合在链表头进行增删,时间复杂度为O(1)；而在链表尾或链表中其他位置增删时， 时间复杂度为O(n)； 而要用链表实现队列结构，需要在一端入队，另一端出队，故只带头结点的链表并不适合用来实现队列，需要加上尾结点。 > 在带头结点和尾结点的单链表中，在头结点增删都是O(1),而在尾结点只有删除时O(1);故用此实现栈结构时， 在头结点删除元素，尾结点增加元素，即头结点做队首，尾结点做队尾。 ``` /** * 带头结点和尾结点的单链表（用来实现队列） */ public class TailLinkedList { //头结点 private Node head; //尾结点 private Node tail; private int size; public TailLinkedList(){ head = null; tail = null; size = 0; } private class Node{ E e; Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e,null); } public Node(){ this(null,null); } } public boolean isEmpty(){ return size == 0; } /** * 在尾结点增加 * @return */ public boolean addLast(E e){ if( tail == null ){ //链表为空 tail = new Node(e); head = tail; }else{ //链表不为空 tail.next = new Node(e); tail = tail.next ; } size++; return true; } /** * 在头结点删除 * @return */ public E removeFirst(){ if(head == null){ //链表为空 throw new RuntimeException("没有元素"); } Node delNode = head; head = head.next; if(head == null) tail = null; size-- ; return delNode.e; } /** * 查看头结点元素 * @return */ public E getFront(){ if(isEmpty()){ //链表为空 throw new RuntimeException("没有元素"); } return head.e ; } /** * 查看尾结点元素 * @return */ public E getLast(){ if(isEmpty()){ //链表为空 throw new RuntimeException("没有元素"); } return tail.e; } public int size(){ return size; } } /** * 带头结点和尾结点的单链表来实现队列结构 * @param */ public class LinkedListQueue implements MyQueue { private TailLinkedList linkedList; public LinkedListQueue(){ linkedList = new TailLinkedList(); } public int size() { return linkedList.size(); } public E deQueue() { return linkedList.removeFirst(); } public boolean enQueue(E e) { return linkedList.addLast(e); } public E getFront() { return linkedList.getFront(); } public E getLast() { return linkedList.getLast(); } } ``` - 阻塞队列 > 队列这种数据结构用的比较广泛的就是 阻塞队列与并发队列 > 阻塞队列其实就是在队列的基础上增加了阻塞操作，简单地说，就是在队列为空时从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有数据了才能返回； 如果队列已经满了，那么插入操作就会被阻塞，直到队列中有空闲位置后再插入数据。 > 因此阻塞队列可用于实现一个“生产者-消费者模型”。 > 这种基于阻塞队列实现的“生产者-消费者模型”，可以有效地协调生产和消费的速度。当生产者生产数据的速度过快， 消费者来不及消费时，存储数据的队列很快就满了。这个时候，生产者就会阻塞等待，直到消费者消费了数据，生产者才会被唤醒继续生产。 并且还可以通过协调生产者和消费者的个数，来提高数据的处理效率，比如多配置几个消费者，来应对一个生产者，亦或反之。 > 线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理呢？一般有两种处理策略： 一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时取出排队的请求继续处理。 那如何存储排队的请求呢？先进者先服务，所以队列这种数据结构很适合用来存储排队请求。而队列有基于数组和基于链表的两种实现方式。 那么这两种实现方式对于排队请求又有什么区别呢？ >> 基于链表的实现方式，可以实现一个无限排队的无界队列（unbounded queue）,但可能会导致过多的请求排队等待，请求处理的响应时间过长。 所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。 而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝， 这种方式对响应时间敏感的系统就更加合理。不过，设置一个合理的队列大小，也是很有讲究的——队列太大导致等待的请求太多，太小则会 导致无法充分利用系统资源、发挥最大性能。 > 实际上，对于大部分资源有限的场景，当没有空闲资源时，基本都可以通过队列这种数据结构来实现请求排队。 - 并发队列 > TODO ### (3) 动态数组 > 数组在存储上是顺序结构，在内存上需要一块连续的空间来存储；故可根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，因而称数组支持随机访问，根据索引查找元素的时间复杂度是O(1); - 要包含维护数据的基础数组及该数组的容量，和动态数组中实际保存的元素数量。 - 扩容和缩容机制。通过获得新数组，拷贝老数组的数据过来，并允许JVM回收老数组。 - 基本的CRUD API - 提供一个实现Iterator接口的内部类；用于维护迭代器迭代时下一项的索引；并实现Iterator的三个方法。 ```$xslt public class MyArrayList implements MyList { private final static int DEFAULT_CAPACITY = 10; private E[] arr;//基础数组 private int capacity; //当前基础数组的容量 private int size ; //当前动态数组的长度 public MyArrayList(int initCapacity){ arr = (E[]) new Object[initCapacity]; this.size = 0; } public MyArrayList(){ this(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); //是否需要缩容 return e; } public boolean set(int index, E e) { checkIndexIllegal(index); arr[index] = e; return true; } public E get(int index) { checkIndexIllegal(index); return arr[index]; } public int size() { return size; } /** * 扩容与缩容的处理 * 扩容缩容要注意时间复杂的震荡的问题！ * @param needCapacity 当前需要的存储容量 */ private void ensureCapacity(int needCapacity) { if(needCapacity <= capacity) return; int newCapacity = needCapacity; if( needCapacity<<3 < capacity ) { //容量四倍于所需以上，缩容； newCapacity = capacity >> 2; } E[] newArr = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newArr[i] = arr[i]; } arr = newArr; } /** * 检测参数中的索引是否合法 */ private void checkIndexIllegal(int index) { if(index < 0 || index > size-1){ //抛出自定义异常 throw new IndexOutOfArrayExceptiom("数组索引越界，非法的index："+index); } } private class ArrayListIterator implements MyIterator{ private int current = 0; //当前迭代到的索引位置 public boolean hasNext() { return current < size; } public E next() { if(current > size-1){ throw new NoMoreElementInArray(); } return (E) arr[current++]; } public E remove() { checkIndexIllegal(current-1); return (E) MyArrayList.this.remove(--current); } } public MyIterator iterator(){ return new ArrayListIterator(); } } ``` ### (4) 链表 - 相比数组需要内存中一整块连续的空间来存储，链表则不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。 - 为了将所有的结点“串联”起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点地址。故每个结点分为两块区域——数据域与指针域。 - 针对链表中指定结点的插入和删除操作，只需要考虑相邻结点的指针改变，时间复杂度为O(1)。 - 无法像数组一样，根据首地址和下标，通过寻址公式直接计算出指定索引位置的内存地址值；而是需要一个个结点地遍历，直到找到指定结点，故不支持随机访问，查找操作的时间复杂度是O(n)。 - 常见的链表一般分为单链表，双向链表，循环链表；其中单链表每个结点只有一个指针，双向链表每结点有两个指针分别指向前驱和后继元素；循环链表则是一种特殊的单链表，其末尾元素的指针指向首元素，而普通单链表的指针值为NULL； 对于有序列表，双向链表比单链表的查询效率更高。 --- ##### 一个基础的单链表实例 ``` /** * 基础单链表 */ public class SingleLinkedList{ /** * 头结点 */ private TrueManNode head = new TrueManNode(); public TrueManNode getHead(){ return head; } /** * 添加结点 * @return */ public boolean add(TrueManNode node){ if(isEmpty()) { head.next = node; }else{ TrueManNode temp = head.next; while(true){ if(temp.next == null){ //没有找到，就往后继结点遍历 temp.next = node; break; } temp = temp.next; } } return true; } /** * 删除结点 * @return */ public void remove(TrueManNode node){ TrueManNode temp = head; //指向头结点 while(temp.next!=null){ if(temp.next.no == node.no){ temp.next = temp.next.next; //没有指针指向这个结点，自然便会被gc return; } temp = temp.next; } throw new RuntimeException("没有这个结点"); } /** * 改结点 * @return */ public boolean updateNode(TrueManNode node){ if( isEmpty() ) throw new RuntimeException("链表为空"); TrueManNode temp = head; while(temp.next != null){ if(temp.no == node.no){ temp = node; return true; } } throw new RuntimeException("没有编号"+node.no+"的结点"); } /** * * @return */ public String toString(){ if( isEmpty() ) return "[]"; StringBuilder sb = new StringBuilder("["); TrueManNode temp = head; while (temp.next != null){ temp = temp.next; sb.append(temp.toString()); if(temp.next!=null) sb.append(" "); } sb.append("]"); return sb.toString(); } public boolean isEmpty(){ return head == null || head.next == null; } /** * 获取链表的有效结点个数 * @return 链表长度 */ public int size(){ TrueManNode temp = head.next; //首结点 if(temp == null){ return 0; } int size = 1; while (temp.next != null){ size++; temp = temp.next; } return size; } /** * 翻转当前链表（复习一遍） * @return */ public SingleLinkedList reverse(){ if(size()<=1) return this; //当前表头 head TrueManNode newHead = new TrueManNode(); TrueManNode current = head.next; while(current!=null) { TrueManNode next = current.next; current.next = newHead.next; //修改了当前遍历到的结点的后继元素地址，故要用变量提前记录下更改前的地址值 newHead.next = current; current = next; //最后还原回原链表中的结点地址值，用于原链表的遍历 } //讲新head的内存结点赋值给旧的表头地址变量 head = newHead; return this; } } ``` - 翻转单链表 ``` /** * 翻转链表 * 思路： * 创建一个新链表的表头，顺序遍历原链表，将原链表的每一个结点元素添加到新表头的最前面 */ public static void reverseLink(SingleLinkedList linkedList){ if( linkedList.size()<=1 ) return ; TrueManNode newHead = new TrueManNode(); TrueManNode current = linkedList.getHead().next; //首元素开始，用于遍历原链表的 TrueManNode next = null; while(current!=null){ //尾元素进不来循环 next = current.next; //当前遍历的下一位 current.next = newHead.next; //原来的第一位地址值，由新的第一位指向，变成第二位 newHead.next = current; current = next; //赋一个新的地址值 } linkedList.getHead().next = newHead.next; } ``` - 双向链表 > 单链表的缺点分析： >> 只能往一个方向遍历 >> 删除时需要依靠辅助结点，不能进行自我删除。（需要待删结点的前驱结点指针域指向待删结点的后继元素--使得待删结点不被引用而被gc掉） --- 遍历方式和单链表相同，只是多了一个向前遍历的遍历顺序； 增加也是默认添加到最后，只要要多加一个向前的指针域； 修改相同； 删除，不需要再遍历到前驱元素，直接找到目标元素后，temp.pre.next=temp.next; temp.pre=temp.next.pre; - 单向环形链表（约瑟夫问题） - Josephu问题为: 设编号为1, 2，… n的n个人围坐一圈，约定编号为k (1<=k<=n) 的人从1开始报数，数到m的那个人出列， 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 - 解决思路: 用一个单向循环链表解决：先构成一个带有n个节点的单向环形链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除节点的下一个节点开始数，直到最后一个节点从链表中删除 (注意由于单链表的结点不能进行自我删除，需要依赖前驱元素，故约瑟夫问题中出圈操作需要有一个临时变量记录目标结点的前驱元素) ``` /** * 单向循环链表解决约瑟夫问题 */ public class CircleLinkedList { private Boy first = null; /** * 往空链表加入指定个数的boy * @param num */ public void addBoy(int num){ if(num<1) throw new RuntimeException("加入个数异常"); Boy curBoy = null; for (int i = 1; i <= num; i++) { Boy boy = new Boy(); boy.setNo(i); if(i == 1){ //加入第一个 first = boy; boy.setNext(boy); curBoy = boy; }else{ curBoy.next = boy; first = boy.next; curBoy = boy; } } } /** * 遍历 */ public void showBoys(){ if(first == null) throw new RuntimeException("为空"); Boy curBoy = first; while(true){ System.out.println(curBoy); if(curBoy.next == first) break; //已经遍历到最后一个了 curBoy = curBoy.next; } } /** * 解决约瑟夫问题 * @param startNo 开始数数的boy编号 * @param count 数数的数量(第若干个boy出圈) * @param total 游戏开始前圈中的所有boy个数 */ public void dealJosephusQuestion(int startNo,int count,int total){ if(first==null) throw new RuntimeException("为空"); if(count 栈是一个后进先出的（FILO - First in Last Out）有序列表 > 栈是限制线性表中元素的插入和删除只能在线性表的同一段进行的一种特殊线性表。允许插入和删除 的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。 > 最先放进的元素在栈底，最后放入的元素在栈顶。 ``` /** * 栈结构 * 后进先出 * 数组实现栈 */ public class ArrayStack { //底层维护栈数据的数组 private int[] arr; //栈顶元素索引 private int topIndex = -1 ; private static final int DEFAULT_CAPACITY = 10; public ArrayStack(int size){ arr = new int[size]; } public ArrayStack(){ this(DEFAULT_CAPACITY); } public boolean isFull(){ return arr.length == topIndex+1; } public boolean isEmpty(){ return topIndex <= -1 ; } public boolean push(int num){ if( isFull() ){ throw new RuntimeException("栈满"); } arr[++topIndex] = num; return true; } public int pop(){ if( isEmpty() ) throw new RuntimeException("栈已满"); return arr[topIndex--]; } public int size(){ return topIndex+1; } public void list(){ if(isEmpty()) System.out.println("栈为空"); for (int i = topIndex; i >= 0 ; i--) { System.out.println(arr[i]); } } } ``` --- 用链表来实现栈结构： ``` /** * 链表实现栈结构 * 表头新增（入栈），表尾删除（出栈） */ public class LinkedStack { private Node top = null; public boolean push(int value){ Node node = new Node(value, null); if(top == null){ top = node; }else{ node.next = top; top = node; } return true; } public int pop(){ if(top == null) throw new RuntimeException("栈为空"); int data = top.data; top = top.next; return data; } public void printAll(){ StringBuilder sb = new StringBuilder("Stack: ["); if(top != null) { Node temp = top; while (true){ if(temp == null) break; sb.append(temp.data+" "); temp = temp.next; } } sb.append("]"); } private static class Node{ private int data; private Node next; public int getData(){ return data; } public Node getNext(){ return next; } public Node(){} public Node(int data,Node next){ this.data = data; this.next = next; } } } ``` ## 递归 > 递归就是方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题，同时可以让代码变简洁。 > 递归调用规则：当程序员执行一个方法时，就会开辟一个独立的空间（栈）；每个空间的数据（局部变量）是独立的。 > 递归需要遵守的规则： >> 1. 执行一个方法时，就创建一个新的受保护的独立空间（栈空间） >> 2. 方法的局部变量是独立的，不会互相影响，比如n变量 >> 3. 如果方法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据。 >> 4. 递归必须向退出条件逼近，否则就是无限递归，出现栈内存溢出异常。 >> 5. 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行 完毕或者返回时，该方法也就执行完毕。 递归-迷宫问题 ![递归迷宫图](https://gitee.com/studygo/data-structure/raw/main/imgs/maze.PNG) --- ## 排序算法 > Sort Algorithm 排序是将一组数据,依指定的顺序进行排列的过程. > 排序在内存占用上分为 内排序 与 外排序。 > - 内部排序: 指将需要处理的所有数据都加载到内存中进行排序. > - 外部排序: 数据量过大无法全部加载到内存中,需要借助外部存储(文件等) > 排序分类图: ![排序分类图](https://gitee.com/studygo/data-structure/raw/main/imgs/allsorts.PNG) > 算法的时间复杂度与空间复杂度问题 (略, 理论部分可见搜索引擎...个人体会就是除了专业分析,日常业务看时间复杂度就从循环执行次数看,看空间复杂度就从循环创建新变量--堆内存开辟新空间) #### 冒泡排序 - 通过对待排序序列从前到后,**依次比较相邻元素的值,若发现则逆序交换(替换位置)**, 使值较大的元素逐渐从前移动到后部,就像*水底下的气泡一样逐渐向上冒*. - 注意对冒泡算法的优化: ***如果一趟排序下来没有一个元素进行过交换,就说明队列已经是有序的了***,因此可以在排序前设置一个交换标志flag记录该趟排序中是否进行元素位置交换,若未则停止算法,从而减少不必要的比较. ``` /** * 冒泡排序 */ public class BubbleSort { public static void main(String[] args) { //生成一个指定长度,指定数字范围(小于)的随机数组 int[] nums = ArraysUtil.createRandomArr(100,1000); System.out.println(Arrays.toString(nums)); bubbleSort(nums); System.out.println(Arrays.toString(nums)); } private static void bubbleSort(int[] nums) { int count = 0; for (int i = 0; i < nums.length-1 ; i++) { boolean flag = false; for (int y = 0 ; y < nums.length-1-i ; y++) { if(nums[y]>nums[y+1]){ int temp = nums[y]; nums[y] = nums[y+1]; nums[y+1] = temp; flag = true; } } if( flag ) count++; else { System.out.printf("一共排序了%d趟\n",count); return; } } System.out.printf("一共排序了%d趟",count); } } ``` #### 选择排序 1. 选择排序(selection sort)是一种原地(in-place)排序算法,由于选择操作是*基于索引的且交换操作只在需要时才执行*,所以**选择排序常用于数值较大和长度较小的文件**. 2. 选择排序的优点: - 容易实现 - 原地(in-place)排序,不需要额外的存储空间. 3. 缺点: 扩展性较差 4. 算法思路: - 寻找序列中的最小值 - 用当前位置的值交换最小值 - 依次对所有元素重复上述过程 - 总结: 不断地把序列中的最小/最大值往队列前端替换 5. **该算法之所以被称为选择排序,因为它重复选择最小的元素** ``` /** * 选择排序 */ public class SelectionSort { private static void selectionSort(int[] nums) { for (int i = 0; i < nums.length-1 ; i++) { int min = nums[i]; int minIndex = i; for (int n = i+1; n < nums.length; n++) { if(nums[n] < min){ min = nums[n]; minIndex = n; } } //替换最小值 int temp = nums[minIndex]; nums[minIndex] = nums[i]; nums[i] = temp; } } } ``` #### 插入排序 1. 插入排序的逻辑是,把元素分为已排序和未排序的.每次从未排序的元素中取出第一个,与已排序的元素从头到尾逐一比较,找到插入点,将之后的元素都往后挪一位,腾出位置给该元素. 2. 每次从输入数据中移除一个元素并将其插入已排序序列的正确位置,直到所有输入元素都插入有序序列中. 3. 插入排序是典型的原地排序.经过k次迭代后数组具有性质:前k+1个元素已经排序. 4. 从第一个元素开始,算成已排序序列,第二个元素一直到末尾算成未排序序列.迭代未排序序列的每个元素,不断地与已排序序列的每一个元素比较, 以确定将未排序序列中的每一个元素插入到已排序序列中的正确位置. ``` /** * 插入排序 */ public class InsertionSort { public static void main(String[] args) { int[] nums = ArraysUtil.createRandomArr(200,1000); System.out.println(Arrays.toString(nums)); System.out.println( ArraysUtil.isSort(nums) ); insertionSortCorrect(nums); System.out.println(Arrays.toString(nums)); System.out.println( ArraysUtil.isSort(nums) ); } //理解有误的插入排序(但一样可以排成功,效率低一点) private static void insertionSort(int[] nums) { //迭代未排序序列,与已排序的每一个元素逐步比较 for (int i = 1; i < nums.length; i++) { //未排序序列从第二个元素即索引为1的开始 for (int j = 0 ; j < i ; j++) { if(nums[i] < nums[j]){ int temp = nums[i]; for (int k = i; k > j ; k--) { nums[k] = nums[k-1]; } nums[j] = temp; break; } } } } //正确的插排 private static void insertionSortCorrect(int[] nums) { //迭代未排序序列,与已排序的每一个元素从后到前逐步比较,比较结果符合就交换位置 for (int i = 1; i < nums.length; i++) { //未排序序列从第二个元素即索引为1的开始 for (int j = i ; j > 0 ; j--) { if(nums[j] < nums[j-1]) ArraysUtil.swap(nums,j-1,j); else break; } } } } ``` #### 希尔排序 - 简单插入排序存在一个效率问题: 当需要插入的数是较小的数,而已排好序的有序序列元素太多时,后移交换次数较多,影响效率. - 希尔排序也是一种插入排序,是为了解决简单插入效率问题,而进行分组后再分别插入排序的一种优化算法.又称为"缩小增量排序". - 希尔排序的基本思想是: * 对n个待排序的数列,取一个小于n的整数gap(gap成为"步长"或者"增量"),将待排序的元素分为gap组的子序列,将下标距离为gap的元素归到同一组中(arr[x]就和arr[x+gap]处于一组中) * 分好组后,对各组内的元素进行直接插入排序(该排序完后每一组的元素便都是有序的) * 接着缩小(减半)gap值并重复执行上述分组和排序,不断重复该操作,知道gap为1时,整个原始序列就是有序的了. - 希尔排序思路图: ![希尔排序思路图](https://github.com/studygo2017/data-structure/raw/main/imgs/shellSort.PNG) ``` /** * 希尔排序 */ public class ShellSort { public static void main(String[] args) { int[] nums = ArraysUtil.createRandomArr(200,1000); System.out.println(Arrays.toString(nums)); System.out.println( ArraysUtil.isSort(nums) ); shellSort(nums); System.out.println(Arrays.toString(nums)); System.out.println( ArraysUtil.isSort(nums) ); } private static void shellSort(int[] nums) { // int gap = nums.length/2; for(int gap = nums.length/2; gap>=1 ; gap = gap/2){ //一直到gap为1,才"整合"了每个分组排序后的结果 for (int i = gap; i < nums.length ; i++) { for( int j = i; j>=gap; j-=gap ){ if( nums[j] < nums[j-gap] ){ ArraysUtil.swap(nums,j,j-gap); } } } } } } ``` #### 快速排序 - quick sort是对冒泡排序的一种改进.基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对 这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此大道整个数据变成有序序列. - 划分: 数组A[low...high]被分成两个非空子数组A[low...q]和A[q+...hign],使得A[low...q]中的每一个元素都小于或等于A[q+1...hign]中的元素.在划分过程中需要计算 索引q的位置. - 分而治之: 对两个子数组A[low...q]和A[q+1...hign]递归调用快速排序. - 快速排序流程: 1. 从数列中挑选出一个基准值. 2. 将所有比基准值小的放在基准前面,所有比基准值大的摆在基准值后面(相同的可放在任意一边); 在这个分区推出以后,该基准就处于数列的中间位置. 3. 递归地把"基准值前面地子数列"和"基准值后面的子数列"进行排序. ``` public static void main(String[] args) { int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 }; quickSort(arr, 0, arr.length - 1); System.out.println("排序后:"); for (int i : arr) { System.out.println(i); } } private static void quickSort(int[] arr, int low, int high) { if (low < high) { // 找寻基准数据的正确索引 int index = getIndex(arr, low, high); // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序 //quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议 quickSort(arr, low, index - 1); quickSort(arr, index + 1, high); } } private static int getIndex(int[] arr, int low, int high) { // 基准数据 int tmp = arr[low]; while (low < high) { // 当队尾的元素大于等于基准数据时,向前挪动high指针 while (low < high && arr[high] >= tmp) { high--; } // 如果队尾元素小于tmp了,需要将其赋值给low arr[low] = arr[high]; // 当队首元素小于等于tmp时,向前挪动low指针 while (low < high && arr[low] <= tmp) { low++; } // 当队首元素大于tmp时,需要将其赋值给high arr[high] = arr[low]; } // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置 // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low] arr[low] = tmp; return low; // 返回tmp的正确位置 } ``` #### 归并排序 ``` /** * 归并排序 * 运用了递归 和 分治的思想 * 递归，不停地对数组按中间点进行分割，直到分割成以单个元素为数组的最小构成单元 * 分治，分割完成后，不停的进行排序合并，直到最后全部合并成一个总体是顺序排列的数组 */ public void mergeSort(int[] arr,int left,int right,int[] temp){ if(leftmaxNum){ maxNum = nums[i]; } } return String.valueOf(maxNum).length(); } ``` --- ## 查找算法 ##### 常用的查找有以下四种： 1. 顺序（线性）查找 2. 二分查找/折半查找 3. 插值查找 4. 斐波那契查找 ##### 顺序查找 - （略） 就是遍历数组(不论是不是排好序的数组均可查找) - 更新一种优化的顺序查找 ``` //改造版,免去了每次限制是否索引越界 public static int search2(int[] arr,int key){ if(arr[0] == key) return 0; arr[0] = key; int i = arr.length-1; //末位索引 while(arr[i] == key){ i--; } if(i==0) return -1; return i; } ``` ##### 二分查找 - 只能对已排好序的数组进行二分查找 - 将表中间位置记录的关键字与查找关键字比较，若相等则查找成功； 否则根据中间位置把表分割成左右两个子表，根据比较结果来决定下一步是去左表中二分查找，还是去右表。 - 重复以上过程，若直到子表不存在都未曾找到，则返回-1 --- ``` public static int binarySearch(int[] arr,int num,int left,int right){ if(left>right) return -1; int mid = (left+right) / 2; if(arr[mid]==num) return mid; if(arr[mid]right || findVal < arr[left] || findVal > arr[right]) return -1; int mid = (findVal - arr[left]) / (arr[right] - arr[left]) * right; if (arr[mid] == findVal){ return mid; }else if(arr[mid] > findVal){ return search(arr,left,mid-1,findVal); }else { return search(arr,mid+1,right,findVal); } } } ``` --- ##### 斐波那契查找 ``` public class FibonacciSearch { public static void main(String[] args) { // boolean b = ArraysUtil.serializeRandomArr(25, 100, "./arr.properties"); int[] arr = ArraysUtil.antiSerializationArr("arr", "./arr.properties"); int[] fbncArr = createFibonacciArr2(arr.length); int index = search(arr, fbncArr, 77); if(index>-1){ System.out.println("索引位置为: "+index); System.out.println("arr["+index+"] = "+arr[index]); }else{ System.out.println("数组中未查询到!"); } } /** * 生成指定长度的斐波那契数组 * @param size * @return */ private static int[] createFibonacciArr(int size){ if(size<=2) throw new FibonacciArrSizeException(); int[] arr = new int[size]; arr[0] = 1; arr[1] = 1; int i = 2; while(i=checkLenght) break; } return arr; } public static int search(int[] arr , int[] fibonacciArr, int key){ //原数组末位索引 int n = arr.length-1; //将原数组补齐 int[] newArr = new int[fibonacciArr[fibonacciArr.length - 1]]; ArraysUtil.copyArray(arr,newArr); for (int i = arr.length; i < newArr.length; i++) { newArr[i] = arr[n]; } System.out.println(ArraysUtil.toString(newArr)); int left = 0; int right = newArr.length-1; int k = fibonacciArr.length-1; while(left<=right){ int mid = left + fibonacciArr[k-1] - 1; if(newArr[mid] == key) { return mid>n ? n : mid; }else if(newArr[mid] < key){ left = mid+1; // 第二轮 f[k-2]个元素中,分成左f[k-3],右f[k-4] k = k-2; }else{ right = mid; // 第二轮 f[k-1]个元素中,分成左f[k-2],右f[k-3] k = k-1; } } return -1; } } ``` --- ## 哈希表 - 哈希表（也叫散列表 Hash Table），是根据关键码值（Key Value）而直接进行访问的数据结构。 - 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数。存放记录的数组则叫做散列表。 ``` /** * 一个最简单的hash表实现 */ public class HashNumTable { private int size; //链表个数 private MyLinkedList[] links; public int hashCode(int num){ return num%size; } public boolean add(int num){ int index = hashCode(num); return links[index].add(num); } public int remove(int num){ int index = hashCode(num); return links[index].remove(num); } public boolean contain(int num){ int index = hashCode(num); return links[index].contain(num); } public void list(){ int index = 0; for (MyLinkedList link : links) { System.out.println("index: "+index+" - "+link.toString()); } } } ``` --- ## 树结构的基础部分 - 树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中： 1. 有且仅有一个特定的称为根（Root）的结点 2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2，... , Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree） - 为什么需要树这种数据结构？ 1. 相较数组这种存储方式，优势在于： **通过下表访问元素**,速度快，对于有序数组还可以使用二分查找提高检索速度。 缺点在于如果要检索 具体某个值，或者插入某个值***会整体移动***，效率较低。 2. 链式存储方式的分析，优势在于： 在一定程度上对数组存储方式有优化，比如插入结点只需要链接到链表中即可（删除效率也很好）。 缺点： 在进行检索时，效率依旧不高，需从头结点开始遍历。 3. 而树结构，比如利用二叉排序树（Binary Sort Tree），既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。 - 二叉树的概念 1. 树有很多种，每个结点最多只能有两个子结点的一种形式称为二叉树 2. 二叉树的子结点分为左子节点和右子结点 - 满二叉树： 如果该二叉树的所有叶子结点都在最后一层，并且结点总数为2^n - 1, n为层数，则称之为满二叉树 - 完全二叉树： 如果该二叉树的所有叶子结点都在最后一层或倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续， 则称之为完全二叉树 - 若将树中任一结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。 - 森林： 对树中的每个结点而言，其子树的集合即为森林 - 节选<<大话数据结构>>一书中对树的定义: 树(Tree)是n(n>=0)个结点的有限集.n=0时称为空树.在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的结点; (2)当n>1时,其余结点可分为m(m>0)个 互不相交的有限集T1, T2, ... , Tm, 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree) --- ``` public class BinaryTree { private HeroNode root; //二叉树的根结点 /** * 设置根结点 * @param root */ public void setRoot(HeroNode root){ this.root = root; } /** * 前序遍历（根左右） */ public void preList(){ if(this.root==null){ System.out.println("空树无法遍历"); return; } this.root.preList(); } /** * 中序遍历 左根右 */ public void infixList(){ if(this.root==null){ System.out.println("空树无法遍历"); return; } this.root.infixList(); } /** * 后序遍历 左右根 */ public void postList(){ if(this.root==null){ System.out.println("空树无法遍历"); return; } this.root.postList(); } /** * 后序查找 * @param no * @return */ public HeroNode postSearch(int no){ if(this.root==null){ System.out.println("空树无法遍历"); return null; } return this.root.postSearch(no); } /** * 删除结点 */ public HeroNode delNode(int no){ HeroNode temp = this.root; if(temp==null) { //空树 return null; } //先判断根结点是不是,heroNode的方法只能删除根的子节点 if(temp.no == no){ temp = null; return temp; } return temp.delNode(no); } } ``` ### 顺序二叉树的存储 --- ## 树结构实际应用 ## 多路查找树 ## 图 ## 常用10种算法