AI 助理
备案控制台
开发者社区 人工智能 文章 正文

超硬核讲解数据结构与算法之线性表（三）

2022-05-23 112
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 超硬核讲解数据结构与算法之线性表

2.5.3. 有环链表入口问题


同样看下面这段代码，完成需求：

//测试类
public class Test {
  public static void main(String[] args) throws Exception {
    Node<String> first = new Node<String>("aa", null);
    Node<String> second = new Node<String>("bb", null);
    Node<String> third = new Node<String>("cc", null);
    Node<String> fourth = new Node<String>("dd", null);
    Node<String> fifth = new Node<String>("ee", null);
    Node<String> six = new Node<String>("ff", null);
    Node<String> seven = new Node<String>("gg", null);
    //完成结点之间的指向
    first.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = fifth;
    fifth.next = six;
    six.next = seven;
      //产生环
    seven.next = third;
    //查找环的入口结点
    Node<String> entrance = getEntrance(first);
    System.out.println("first链表中环的入口结点元素为："+entrance.item);
  }
  /**
  * 查找有环链表中环的入口结点
  * @param first 链表首结点
  * @return 环的入口结点
  */
  public static Node getEntrance(Node<String> first) {
    return null;
  }
  //结点类
  private static class Node<T> {
    //存储数据
    T item;
    //下一个结点
    Node next;
    public Node(T item, Node next) {
      this.item = item;
      this.next = next;
    }
  }
}


需求：


请完善Test类中的getEntrance方法，查找有环链表中环的入口结点。


当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口。证明这一结论牵涉到数论的知识，这里略，只讲实现。


47b47c72aeb84abebfee1a9c863bfada.png

354b38b34ab44bf59636738dc9bccb45.png

1d1d586a1fee4e5494802792520d5cda.png

代码：

/**
* 查找有环链表中环的入口结点
* @param first 链表首结点
* @return 环的入口结点
*/
public static Node getEntrance(Node<String> first) {
  Node<String> slow = first;
  Node<String> fast = first;
  Node<String> temp = null;
  while(fast!=null && fast.next!=null){
  fast = fast.next.next;
  slow=slow.next;
  if (fast.equals(slow)){
    temp = first;
    continue;
  }
  if (temp!=null){
    temp=temp.next;
    if (temp.equals(slow)){
      return temp;
    }
  }
}
return null;
}

2.6.循环链表


循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。

cce4f2f7fb5a4f53932ad48a41434e9f.png

循环链表的构建：

public class Test {
  public static void main(String[] args) throws Exception {
    //构建结点
    Node<Integer> first = new Node<Integer>(1, null);
    Node<Integer> second = new Node<Integer>(2, null);
    Node<Integer> third = new Node<Integer>(3, null);
    Node<Integer> fourth = new Node<Integer>(4, null);
    Node<Integer> fifth = new Node<Integer>(5, null);
    Node<Integer> six = new Node<Integer>(6, null);
    Node<Integer> seven = new Node<Integer>(7, null);
    //构建单链表
    first.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = fifth;
    fifth.next = six;
    six.next = seven;
    //构建循环链表,让最后一个结点指向第一个结点
    seven.next = first;
  }
}


2.7.约瑟夫问题


问题描述：


传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏 。


问题转换：


41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。


1.编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；

2.自退出那个人开始的下一个人再次从1开始报数，以此类推；

3.求出最后退出的那个人的编号。


图示：


c4ef6ac780d040819c05bd785a102f7b.png

解题思路：


1.构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；


2.使用计数器count，记录当前报数的值；


3.遍历链表，每循环一次，count++；


4.判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；


代码:

public class Test {
  public static void main(String[] args) throws Exception {
    //1.构建循环链表
    Node<Integer> first = null;
    //记录前一个结点
    Node<Integer> pre = null;
    for (int i = 1; i <= 41; i++) {
      //第一个元素
      if (i==1){
        first = new Node(i,null);
        pre = first;
        continue;
      }
      Node<Integer> node = new Node<>(i,null);
      pre.next = node;
      pre = node;
      if (i==41){
        //构建循环链表，让最后一个结点指向第一个结点
        pre.next=first;
      }
    }
    //2.使用count，记录当前的报数值
    int count=0;
    //3.遍历链表，每循环一次，count++
    Node<Integer> n = first;
    Node<Integer> before = null;
    while(n!=n.next){
      //4.判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；
      count++;
      if (count==3){
        //删除当前结点
        before.next = n.next;
        System.out.print(n.item+",");
        count=0;
        n = n.next;
      }else{
        before=n;
        n = n.next;
      }
    }
    /*打印剩余的最后那个人*/
    System.out.println(n.item);
  }
}

三、栈

3.1.栈概述


3.1.1.生活中的栈


存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如我们现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈。

image.png


3.1.2.计算机中的栈


我们把生活中的栈的概念引入到计算机中，就是供数据休息的地方，它是一种数据结构，数据既可以进入到栈中，又可以从栈中出去。


栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。


我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。


053184715b7e46da9cc62b82be0524df.png

3.2.栈的实现


3.2.1 栈API设计


image.png


3.2.2.栈代码实现

// 栈代码
import java.util.Iterator;
public class Stack<T> implements Iterable<T>{
  //记录首结点
  private Node head;
  //栈中元素的个数
  private int N;
  public Stack() {
    head = new Node(null,null);
    N=0;
  }
  //判断当前栈中元素个数是否为0
  public boolean isEmpty(){
    return N==0;
  }
  //把t元素压入栈
  public void push(T t){
    Node oldNext = head.next;
    Node node = new Node(t, oldNext);
    head.next = node;
    //个数+1
    N++;
  }
  //弹出栈顶元素
  public T pop(){
    Node oldNext = head.next;
    if (oldNext==null){
      return null;
    }
    //删除首个元素
    head.next = head.next.next;
    //个数-1
    N--;
    return oldNext.item;
  }
  //获取栈中元素的个数
  public int size(){
    return N;
  }
  @Override
  public Iterator<T> iterator() {
    return new SIterator();
  }
  private class SIterator implements Iterator<T>{
  private Node n = head;
  @Override
  public boolean hasNext() {
    return n.next!=null;
  }
  @Override
  public T next() {
    Node node = n.next;
    n = n.next;
    return node.item;
  }
}
  private class Node{
    public T item;
    public Node next;
    public Node(T item, Node next) {
      this.item = item;
      this.next = next;
    }
  }
}
//测试代码
public class Test {
  public static void main(String[] args) throws Exception {
    Stack<String> stack = new Stack<>();
    stack.push("a");
    stack.push("b");
    stack.push("c");
    stack.push("d");
    for (String str : stack) {
      System.out.print(str+" ");
    }
    System.out.println("-----------------------------");
    String result = stack.pop();
    System.out.println("弹出了元素："+result);
    System.out.println(stack.size());
  }
}

3.3.案例


3.3.1 括号匹配问题


问题描述:


给定一个字符串，里边可能包含"()"小括号和其他字符，请编写程序检查该字符串的中的小括号是否成对出现。


例如：


“(上海)(长安)”：正确匹配

“上海((长安))”：正确匹配

“上海(长安(北京)(深圳)南京)”:正确匹配

“上海(长安))”：错误匹配

“((上海)长安”：错误匹配


示例代码：


public class BracketsMatch {
  public static void main(String[] args) {
    String str = "(上海(长安)())";
    boolean match = isMatch(str);
    System.out.println(str+"中的括号是否匹配："+match);
  }
  /**
  * 判断str中的括号是否匹配
  * @param str 括号组成的字符串
  * @return 如果匹配，返回true，如果不匹配，返回false
  */
  public static boolean isMatch(String str){
    return false;
  }
}


请完善 isMath方法。


分析：


1.创建一个栈用来存储左括号

2.从左往右遍历字符串，拿到每一个字符

3.判断该字符是不是左括号，如果是，放入栈中存储

4.判断该字符是不是右括号，如果不是，继续下一次循环

5.如果该字符是右括号，则从栈中弹出一个元素t；

6.判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号

7.循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配


bbcad0b2c02142aa8f8c680a5e184f0e.png

代码实现：

public class BracketsMatch {
  public static void main(String[] args) {
    String str = "(fdafds(fafds)())";
    boolean match = isMatch(str);
    System.out.println(str + "中的括号是否匹配：" + match);
  }
  /**
  * 判断str中的括号是否匹配
  *
  * @param str 括号组成的字符串
  * @return 如果匹配，返回true，如果不匹配，返回false
  */
  public static boolean isMatch(String str) {
    //1.创建一个栈用来存储左括号
    Stack<String> chars = new Stack<>();
    //2.从左往右遍历字符串，拿到每一个字符
    for (int i = 0; i < str.length(); i++) {
      String currChar = str.charAt(i) + "";
      //3.判断该字符是不是左括号，如果是，放入栈中存储
      if (currChar.equals("(")) {
        chars.push(currChar);
      } else if (currChar.equals(")")) {//4.判断该字符是不是右括号，如果不是，继续下一次循环
        //5.如果该字符是右括号，则从栈中弹出一个元素t；
        String t = chars.pop();
        //6.判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号
        if (t == null) {
          return false;
        }
      }
    }
    //7.循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配
    if (chars.size() == 0) {
      return true;
    } else {
      return false;
    }
  }
}


3.3.2.逆波兰表达式求值问题


逆波兰表达式求值问题是我们计算机中经常遇到的一类问题，要研究明白这个问题，首先我们得搞清楚什么是逆波兰表达式？要搞清楚逆波兰表达式，我们得从中缀表达式说起。


中缀表达式：


中缀表达式就是我们平常生活中使用的表达式，例如：1+3*2,2-(1+3)等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。


中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作。


逆波兰表达式(后缀表达式)：


逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后。


image.png

需求：


给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果。

public class ReversePolishNotation {
  public static void main(String[] args) {
    //中缀表达式3*（17-15）+18/6的逆波兰表达式如下
    String[] notation = {"3", "17", "15", "-", "*","18", "6","/","+"};
    int result = caculate(notation);
    System.out.println("逆波兰表达式的结果为："+result);
  }
  /**
  * @param notaion 逆波兰表达式的数组表示方式
  * @return 逆波兰表达式的计算结果
  */
  public static int caculate(String[] notaion){
    return -1;
  }
}


完善caculate方法，计算出逆波兰表达式的结果。


分析：


1.创建一个栈对象oprands存储操作数

2.从左往右遍历逆波兰表达式，得到每一个字符串

3.判断该字符串是不是运算符，如果不是，把该该操作数压入oprands栈中

4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2

5.使用该运算符计算o1和o2，得到结果result

6.把该结果压入oprands栈中

7.遍历结束后，拿出栈中最终的结果返回


c8f946e552ae4468adc5b76332210305.png

代码实现：

public class ReversePolishNotation {
  public static void main(String[] args) {
    //中缀表达式3*（17-15）+18/6的逆波兰表达式如下
    String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};
    int result = caculate(notation);
    System.out.println("逆波兰表达式的结果为：" + result);
  }
  /**
  * @param notaion 逆波兰表达式的数组表示方式
  * @return 逆波兰表达式的计算结果
  */
  public static int caculate(String[] notaion) {
    //1.创建一个栈对象oprands存储操作数
    Stack<Integer> oprands = new Stack<>();
    //2.从左往右遍历逆波兰表达式，得到每一个字符串
    for (int i = 0; i < notaion.length; i++) {
      String curr = notaion[i];
      //3.判断该字符串是不是运算符，如果不是，把该该操作数压入oprands栈中
      Integer o1;
      Integer o2;
      Integer result;
      switch (curr) {
      case "+":
        //4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2
        o1 = oprands.pop();
        o2 = oprands.pop();
        //5.使用该运算符计算o1和o2，得到结果result
        result = o2 + o1;
        //6.把该结果压入oprands栈中
        oprands.push(result);
        break;
      case "-":
        //4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2
        o1 = oprands.pop();
        o2 = oprands.pop();
        //5.使用该运算符计算o1和o2，得到结果result
        result = o2 - o1;
        //6.把该结果压入oprands栈中
        oprands.push(result);
        break;
      case "*":
        //4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2
        o1 = oprands.pop();
        o2 = oprands.pop();
        //5.使用该运算符计算o1和o2，得到结果result
        result = o2 * o1;
        //6.把该结果压入oprands栈中
        oprands.push(result);
        break;
      case "/":
        //4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2
        o1 = oprands.pop();
        o2 = oprands.pop();
        //5.使用该运算符计算o1和o2，得到结果result
        result = o2 / o1;
        //6.把该结果压入oprands栈中
        oprands.push(result);
        break;
        default:
        oprands.push(Integer.parseInt(curr));
        break;
      }
    }
    //7.遍历结束后，拿出栈中最终的结果返回
    Integer result = oprands.pop();
    return result;
  }
}

四、队列

队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。


0d30cbd240b642699fe84cea51d85610.png

4.1.队列的API设计


image.png

4.2.队列的实现

// 队列代码
import java.util.Iterator;
public class Queue<T> implements Iterable<T>{
  //记录首结点
  private Node head;
  //记录最后一个结点
  private Node last;
  //记录队列中元素的个数
  private int N;
  public Queue() {
    head = new Node(null,null);
    last=null;
    N=0;
  }
  //判断队列是否为空
  public boolean isEmpty(){
    return N==0;
  }
  //返回队列中元素的个数
  public int size(){
    return N;
  }
  //向队列中插入元素t
  public void enqueue(T t){
    if (last==null){
      last = new Node(t,null);
      head.next=last;
    }else{
      Node oldLast = last;
      last = new Node(t,null);
      oldLast.next=last;
    }
    //个数+1
    N++;
  }
  //从队列中拿出一个元素
  public T dequeue(){
    if (isEmpty()){
      return null;
    }
    Node oldFirst = head.next;
    head.next = oldFirst.next;
    N--;
    if (isEmpty()){
    last=null;
    }
    return oldFirst.item;
  }
  @Override
  public Iterator<T> iterator() {
    return new QIterator();
  }
  private class QIterator implements Iterator<T>{
  private Node n = head;
  @Override
  public boolean hasNext() {
    return n.next!=null;
  }
  @Override
  public T next() {
    Node node = n.next;
    n = n.next;
    return node.item;
  }
}
  private class Node{
    public T item;
    public Node next;
    public Node(T item, Node next) {
      this.item = item;
      this.next = next;
  }
}
}
//测试代码
public class Test {
  public static void main(String[] args) throws Exception {
    Queue<String> queue = new Queue<>();
    queue.enqueue("a");
    queue.enqueue("b");
    queue.enqueue("c");
    queue.enqueue("d");
    for (String str : queue) {
      System.out.print(str+" ");
    }
    System.out.println("-----------------------------");
    String result = queue.dequeue();
    System.out.println("出列了元素："+result);
    System.out.println(queue.size());
  }
}


文章标签：
API
算法
存储
关键词：
数据结构线性表
算法线性表
数据结构与算法线性表
超硬核算法
超硬核数据结构与算法线性表
白大锅
目录
相关文章
孤影过客
|
6月前
|
存储 C语言
数据结构中的线性表链式存储介绍及其基本操作
链式存储是线性表的一种重要存储方式，它通过节点和指针的结构，实现了灵活的动态存储管理。本文介绍了单向链表的基本操作，并提供了相应的C语言代码示例。理解和掌握链表的操作对学习和应用数据结构具有重要意义。希望这篇博客能帮助你更好地理解线性表的链式存储。
孤影过客
142 2
小强在此
|
2月前
|
存储 Java
数据结构第二篇【关于java线性表（顺序表）的基本操作】
数据结构第二篇【关于java线性表（顺序表）的基本操作】
小强在此
46 6
椰椰椰耶
|
2月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
椰椰椰耶
27 1
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二（5）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
25 0
Codelinghu
|
2月前
01（数据结构考研）线性表相关操作代码
01（数据结构考研）线性表相关操作代码
Codelinghu
87 0
Codelinghu
|
2月前
|
存储 C语言
数据结构之线性表的初始化及其操作
数据结构之线性表的初始化及其操作
Codelinghu
49 0
杀死一只知更鸟debug
|
3月前
|
存储 Java
java数据结构，线性表顺序存储（数组）的实现
文章介绍了Java中线性表顺序存储（数组）的实现。线性表是数据结构的一种，它使用数组来实现。文章详细描述了线性表的基本操作，如增加、查找、删除、修改元素，以及其他操作如遍历、清空、求长度等。同时，提供了完整的Java代码实现，包括MyList接口和MyLinearList实现类。通过main函数的测试代码，展示了如何使用这些方法操作线性表。
杀死一只知更鸟debug
51 0
lge101058
|
6月前
|
存储 测试技术
【数据结构】操作受限的线性表，栈的具体实现
【数据结构】操作受限的线性表，栈的具体实现
lge101058
75 5
lge101058
|
6月前
|
存储 测试技术
【数据结构】操作受限的线性表，队列的具体实现
【数据结构】操作受限的线性表，队列的具体实现
lge101058
51 4
sky_qiyi
|
6月前
|
存储 算法
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
sky_qiyi
49 0

热门文章

最新文章

  • 1
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 2
    基于OHCI的USB主机 —— UFI数据结构2
  • 3
    初学python数据结构-切片
  • 4
    数据结构示例——堆排序过程
  • 5
    【数据结构】链表的学习和介绍
  • 6
    数据结构：栈
  • 7
    数据结构之第七章、队列(Queue)
  • 8
    数据结构成神篇1-初学数据结构
  • 9
    数据结构和算法(二叉搜索树)
  • 10
    408数据结构真题2015-41
  • 1
    【Paddle】PCA线性代数基础 + 领域应用：人脸识别算法（1.1w字超详细：附公式、代码）
    119
  • 2
    BASE64的算法说明
    69
  • 3
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    115
  • 4
    理解并应用机器学习算法：决策树
    145
  • 5
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    426
  • 6
    【机器学习】为什么K-means算法使用欧式距离度量？
    413
  • 7
    【机器学习】描述K-means算法的步骤
    153
  • 8
    【机器学习】K-means和KNN算法有什么区别？
    652
  • 9
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    58
  • 10
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    61

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks售前咨询