跳至主要內容

数据结构

TenSoFlow...大约 7 分钟数据结构数据结构

数据结构

第01章 简介

程序 = 数据结构(Data Structure) + 算法

这个公式对计算机科学的影响程度足以类似于物理学中爱因斯坦的质能方程。
数据结构是一种组织和存储数据的方式。以便能够有效地访问和修改数据。数据结构是计算机科学中的一个重要概念，它关注如何组织和管理数据，以便能够高效地执行各种操作，如搜索、排序、插入和删除等。

第02章 基本结构

数据元素不是孤立存在的，他们之间存在着某种关系，数据元素相互之间的关系称为结构。数据结构是带结构的数据元素的集合。

数据结构分为线性结构和非线性结构。
线性结构：线性表，栈和队列，串，数组和广义表
非线性结构：树，图

第03章 基本概念和术语

数据
是能够输入计算机且能被计算机处理的各种符号的集合。包括数值型的数据如整数实数等以及非数值型的数据如文字图像图形声音等。
数据元素
是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。也简称为元素，或记录，结点或顶点。如一名学生的基本信息包括姓名，性别，年龄，住址，出生日期。由这五项组成的一个整体就叫做数据元素。
数据项
构成数据元素的不可分割的最小单位
如学生基本信息中的姓名，性别，年龄，住址，出生日期中的性别这项就叫数据项。
数据对象
是性质相同的数据元素的集合，是数据的一个子集。
例如整数的数据对象是集合N = 0 1 -1 2 -2 ......

第04章 算法和算法分析

算法就是对特定问题求解方法和步骤的一种描述，它是指令的有限序列。

算法的五个特性：输入 输出 有穷性 确定性 可行性

算法的设计要求：正确性 可读性 健壮性 高效性

第05章 链表

概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。只根据文字描述还是比较抽象的，直接上图来观察：

运行方式

图中的phead指针中存放的是第一个结点的地址，那么根据指着地址我们就可以找到这个结构体，又因为这个结构体中存放了下一个结构体的地址，所以又可以找到第二个结构体，循环往复就可以找到所有的结点，直到存放空地址的结构体。图中的箭头实际上是不存在的，这里只是为了能够方便理解。

Java标准库中的链表

Java标准库中内置了一个双向链表LinkedList类。

Java手写链表

// 代表链表的节点
class ListNode<T> {
    // 链表中的数据
    T val;
    // 链表的下一个节点
    ListNode<T> next;
    // 构造方法为数据赋值
    public ListNode(T val) {
        this.val = val;
    }
}

class ListNodeUtil {
    // 数组转链表
    public static ListNode<Integer> getListNodeByArray(int[] arr) {
        if (arr == null || arr.length == 0) { 
            return null; 
        }
        ListNode<Integer> head = new ListNode<>(arr[0]);
        ListNode<Integer> temp = head;
        for (int i = 1; i < arr.length; i++) {
            temp.next = new ListNode<>(arr[i]);
            temp = temp.next;
        }
        return head;
    }

    // 打印链表数据
    public static void printListNode(ListNode<Integer> head) {
        ListNode<Integer> current = head;
        while (current != null) {
            System.out.printf("%d ",current.val);
            current = current.next;
        }
    }

    // 得到链表的长度
    public static int getListNodeLength(ListNode<Integer> head) {
        ListNode<Integer> current = head;
        int res = 0;
        while(current != null) {
            res++;
            current = current.next;
        }
        return res;
    }

    // 查找链表中是否包含指定值
    public static boolean contains(ListNode<Integer> head, int value) {
        ListNode<Integer> current = head;
        while(current != null) {
            if (current.val == value) return true;
            current = current.next;
        }
        return false;
    }

    // 在链表末尾插入一个新节点
    public static ListNode<Integer> insertAtEnd(ListNode<Integer> head, int value) {
        ListNode<Integer> newNode = new ListNode<>(value);
        if (head == null) {
            return newNode;
        }
        ListNode<Integer> temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        return head;
    }

    // 在链表的指定位置插入一个新节点
    public static ListNode<Integer> insertAtPosition(ListNode<Integer> head, int value, int position) {
        ListNode<Integer> newNode = new ListNode<>(value);
        if (position == 0) {
            newNode.next = head;
            return newNode;
        }
        ListNode<Integer> current = head;
        for (int i = 0; i < position - 1 && current != null; i++) {
            current = current.next;
        }
        if (current != null) {
            newNode.next = current.next;
            current.next = newNode;
        }
        return head;
    }

    // 删除链表中值等于特定值的节点
    public static ListNode<Integer> deleteNode(ListNode<Integer> head, int value) {
        if (head == null) {
            return null;
        }
        if (head.val == value) {
            return head.next;
        }
        ListNode<Integer> current = head;
        while (current.next != null && current.next.val != value) {
            current = current.next;
        }
        if (current.next != null) {
            current.next = current.next.next;
        }
        return head;
    }

    // 获取链表中第 n 个节点的数据
    public static Integer getNthNode(ListNode<Integer> head, int n) {
        ListNode<Integer> current = head;
        for (int i = 0; i < n && current != null; i++) {
            current = current.next;
        }
        return (current != null) ? current.val : null;
    }

}
/**
 * @Description: TODO
 * @author: 曹卫民
 * @date: 2024-10-10
 **/
public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        ListNode<Integer> head = ListNodeUtil.getListNodeByArray(arr, 0);
        ListNodeUtil.printListNode(head);
        System.out.println();
    }
}

例题

天晴了，雨停了，我又觉得我行了!​ 😎

相交链表

例题链接：160 - 相交链表(LeetCode)open in new window

题解

我们需要做的事情是让两个链表同时从较短链表的头结点位置。 为此，我们必须消除两个链表的长度差。

  1. 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
  2. 如果 pA 到了末尾，则 pA = headB 继续遍历
  3. 如果 pB 到了末尾，则 pB = headA 继续遍历
  4. 比较长的链表指针指向较短链表head时，长度差就消除了
  5. 如此，只需要将最短链表遍历两次即可找到位置

怎么理解呢？

假设长的链表为A长度为a短的为B长度为b

PA开始指向A ，PB开始指向B

先同时走b步PB到达尾部把PB指向A的开头此时PA在A链表的a-b处的位置

然后继续走a-b步PA走到尾部把PA指向B的开头此时PB在A中距离尾部的位置是a-(a-b)=b

那么此时就消除了两个链表的长度差

如果还不明白则通过下图理解

代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

删除链表的中间节点

例题链接：2095 - 删除链表的中间节点(LeetCode)open in new window

题解

可以采用快慢指针的方法。慢指针一次移动一位，快指针一次移动二位，这样当快指针走到尾时。慢指针刚好走到链表的中间。

代码

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head.next == null) {
            head = head.next;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode temp = null;
        while(fast != null && fast.next != null) {
            temp = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        temp.next = temp.next.next;
        return head;
    }
}

移除链表元素

例题链接：203 - 移除链表元素(LeetCode)open in new window

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const newHead = new ListNode(0)
    newHead.next = head
    let temp = newHead
    while (temp.next !== null) {
        temp.next.val === val ? temp.next = temp.next.next : temp = temp.next
    }
    return newHead.next
};

雨停了，天晴了，看了评论原来不是我行了! 😤

0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.15.8
世界上最贵的东西，往往是免费的。比如阳光、空气、陪伴和爱。
Copyright © 2024 TenSoFlow