• 数据结构相关知识点（一）

    一、线性表

    1.什么是线性表？

    线性表，全名为线性存储结构。使用线性表存储数据的方式可以理解理解为：把所有数据按照顺序（线性）的存储结构方式，存储在物理空间。

    2.线性存储结构

    顺序存储结构：数据依次存储在连续的物理空间中（顺序表）；

    链式存储结构：数据分散存储在不同的物理空间中，通过某种指向关系，来维持它们之间的逻辑关系（链表）；

    3.顺序表（数组）

            顺序表，就是顺序存储结构，是线性表的一种。顺序表对数据的物理存储结构有明确的要求:顺序表存储数据时，会提前申请一块足够大小的内存，然后将数据依次存储起来，元素的存储空间在内存中是连续存在的。

            优点：1.内存地址连续，数组元素进行遍历时，速度快。

                       2.根据下标，查找指定位置的元素时，速度快。

            缺点：1.长度固定，使用前余姚提前预估长度。

                       2.插入和删除元素时，时间复杂度相对较高。

        时间复杂度：读的时候是  O（1）   插入和删除的时候是O（n）

    4.链表

            链表，全名是链式存储结构，也是线性表的一种。链表不限制数据的物理存储位置，使用链表存储的数据元素，其物理存储位置是随机的。由于链表节点之间根本无法体现出各数据之间的逻辑关系。

            链表的组成：

                                    数据元素本身，其所在的区域称为数据域；

                                    指向直接后继元素的指针，所在的区域称为指针域；

                                    

            优点：使用链表结构，不需要提前预估长度，可以克服数组需要预先知道数据长度的缺点

                       链表使用不连续的内存空间，可以充分利用计算机内存空间，实现灵活的内存动态管理

            缺点：链表相比于数组会占用更多的空间，因为他不仅要存储数据本身还需要存储指针域。

                       不能随机的读取元素

                       遍历和查找元素更慢了。

    时间复杂度：插入和删除时O（1），遍历查找时O (n); 

    链表又有很多种类：单向链表，双向链表，循环链表，双向循环链表。。。

    5.链表中常见的问题（判断成环，相交）

    判断链表是否有环

    1. Linked.Node node1 = new Linked.Node(1);
    2.  
    3. Linked.Node node2 = new Linked.Node(2);
    4.  
    5. Linked.Node node3 = new Linked.Node(3);
    6.  
    7. Linked.Node node4 = new Linked.Node(4);
    8.  
    9. Linked.Node node5 = new Linked.Node(5);
    10.  
    11.  
    12.  
    13. node1.next = node2;
    14.  
    15. node2.next = node3;
    16.  
    17. node3.next = node4;
    18.  
    19. node4.next = node5;
    20.  
    21. node5.next = node3; // 链表产生环
    方法一：使用Set集合
    1. private static boolean hasCycle(Node node) {
    2.  
    3. // 定义Set集合，保存链表中的所有节点
    4.  
    5. Set nodeSet = new HashSet();
    6.  
    7. // 遍历链表中的每个节点
    8.  
    9. while(node != null) {
    10.  
    11. // 判断Set中是否存在该节点
    12.  
    13. // 如果存在，则代表该链表有环
    14.  
    15. if(nodeSet.contains(node)) {
    16.  
    17. return true; // 链表有环
    18.  
    19. }
    20.  
    21. // 如果不存在，则将节点加入Set集合，用于后续的判断
    22.  
    23. nodeSet.add(node);
    24.  
    25. // 移动链表节点
    26.  
    27. node = node.next;
    28.  
    29. }
    30.  
    31. return false; // 链表无环
    32.  
    33. }
    方法二：快慢指针
    1. private static boolean hasCycle(Node head) {
    2.  
    3.     if (head == null) {
    4.  
    5.         return false;
    6.  
    7.     }
    8.  
    9.  
    10.  
    11.     // 定义快指针和慢指针，从head头节点开始
    12.  
    13.     Node fast = head;
    14.  
    15.     Node slow = head;
    16.  
    17.     while (fast != null && fast.next != null && slow != null) {
    18.     
    19.     fast = fast.next.next; // 快指针移动2步
    20.  
    21.     slow = slow.next; // 慢指针移动1步
    22.  
    23.  
    24.  
    25.     // 判断fast和slow快慢指针指向的内存地址相同，如果相同，则代表碰面相遇
    26.     
    27.         if (fast == slow) {
    28.  
    29.         // 如果碰面，就代表链表有环
    30.     
    31.         return true;
    32.  
    33.         }
    34.  
    35.     }
    36.  
    37.     return false;
    38.  
    39. }

    判断是否相交

    方法一：使用双重循环判断
    1. public static boolean isIntersect1(Linked link1, Linked link2) {
    2.  
    3.     for (Node p = link1.first; p != null; p = p.next) {
    4.  
    5.         for (Node q = link2.first; q != null; q = q.next) {
    6.  
    7.             if (p == q) {
    8.  
    9.                 return true;
    10.  
    11.             }
    12.  
    13.         }
    14.  
    15.     }
    16.  
    17.     return false;
    18.  
    19. }
    方法二：使用双指针判断
    1. public static boolean isIntersect2(Linked link1, Linked link2) {
    2.     // 安全检测
    3.     if (link1 == null || link2 == null) {
    4.         return false;
    5.     }
    6.  
    7.     // p 指向长链表的第一个结点
    8.     // q 指向短链表的第一个结点
    9.     Node p = link1.size() > link2.size() ? link1.first : link2.first;
    10.     Node q = link1.size() > link2.size() ? link2.first : link1.first;
    11.  
    12.     // 求两个链表长度差
    13.     int diff = Math.abs(link1.size() - link2.size());
    14.  
    15.     // p先往后移动diff个结点
    16.     while (diff-- > 0) {
    17.         p = p.next;
    18.     }
    19.  
    20.     // p 和 q 同时往后移动
    21.     while (p != q) {
    22.         p = p.next;
    23.         q = q.next;
    24.     }
    25.  
    26.     // 如果p(q)不为null，则两个链表相交，否则不相交
    27.     if (p != null) {
    28.         return true;
    29.     } else {
    30.         return false;
    31.     }
    32. }

    栈&队列

    1.栈

    什么是栈

            栈（stack）是一种特殊的线性数据集合，只允许在栈顶top进行加入数据（push）贺移动数据（pop），按照后进先出LIFO的规则进行操作，也可以理解为先入后出FILO；

            栈的实现方式：

                    栈的实现结构可以是一维数组或链表来实现，用数组实现的栈叫作顺序栈 ，用链表实现的栈叫作链式栈 。在Java中，顺序栈使用java.util.Stack类实现，链式栈使用java.util.LinkedList类实现。

                    时间复杂度：访问指定元素：O(n)                入栈和出栈：O（1）

    栈的常见操作

    入栈：入栈操作就是把虚拟的元素放入栈中，只允许从栈顶一侧放入元素，新元素将会成为栈顶。

    出栈：出栈操作就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

    队列

    队列是一种线性数据节后，特点类似：行驶车辆的单向隧道

    队列中的元素按照先入先出的规则操作

    队列的出口端叫做队头，队列的入口端叫做队尾

    队列只允许在队头进行出队poll操作（删除）

    队列只允许在队尾进行入队offer操作（添加）

    实现方式

    数组实现的队列叫作顺序队列
    用链表实现的队列叫作链式队列

    时间复杂度

    假设队列中有n个元素。
    ●访问指定元素的时间复杂度是O(n)：最坏情况下，遍历整个队列
    ●插入删除元素的时间复杂度是O(1)：只需要操作队头或队尾元素

  • 相关阅读:
    Postman-APIs是干什么的？
    PostGIS导入shp文件报错：dbf file (.dbf) can not be opened.
    [modern c++] 函数式编程与 std::ref
    【打卡】21天学习挑战赛—RK3399平台开发入门到精通-day9
    3 个常识点必须先了解!0基础入门Python！
    计算机网络(第二弹) --- 网络传输的基本流程最容易理解的讲述
    算法与数据结构【30天】集训营——线性表的定义及特点-顺序表的表示与实现及操作（03）
    RTI connext 初级入门
    Git快速入门一篇文章就够了。Git基础使用。如何将本地的文件上传到Gitee？
    （51单片机）第十三章-STC系列51单片机功能介绍
  • 原文地址：https://blog.csdn.net/qq_61854038/article/details/133700837