基于链表的分词器反向输出

谁践踏了优雅 2022-10-06 14:54 34阅读 0赞

# 背景 #

前段时间参加了某大厂的面试，面试过程中要求将输入的字符串分词后反向输出，例如：输入“I am a handsome boy.”，期望输出结果为：“boy handsome a am I.”，前提条件：不允许使用字符串的split()方法。由于实现过程中，输入的字符串长度不一定，因此通过初始化数组来实现存在一定的越界问题，因此采用链表来实现。

# 实现流程 #

整个实现流程分为以下几步：替换--分词--反向输出。具体流程图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21fc29waGlh_size_16_color_FFFFFF_t_70][]

# 代码实现 #

链表定义：AnalyzersLinkedList.java

class Node {
        String data;
    
        Node next;
    
        public Node(String data) {
            this.data = data;
            this.next = null;
        }
    }
    
    public class AnalyzersLinkedList {
    
        public Node first;
    
        public Node last;
    
        public boolean isEmpty() {
            return first == null;
        }
    
        public void print() {
            Node current = first;
            while (current != null) {
                System.out.println("" + current.data + "");
                current = current.next;
            }
            System.out.println();
        }
    
        public void insert(String data) {
            Node newNode = new Node(data);
            if (this.isEmpty()) {
                first = newNode;
            } else {
                last.next = newNode;
            }
            last = newNode;
        }
    }

由于链表中存储部分，因此节点内容中只存储分词结果。

链表反向输出

class ReverseAnalyzersLinkedList extends AnalyzersLinkedList {
        public void reversePrint() {
            Node current = first;
            Node before = null;
            System.out.println("反转后的数据为:");
            while (current != null) {
                last = before;
                before = current;
                current = current.next;
                before.next = last;
            }
            current = before;
            while (current != null) {
                String data = current.data;
                current = current.next;
                if (current == null) {
                    System.out.print(data.replace(' ', '.'));
                } else {
                    System.out.print(data);
                }
            }
            System.out.println();
        }
    }

主方法：

ReverseAnalyzersLinkedList list = new ReverseAnalyzersLinkedList();
    String original = "I am a handsome boy.";
    System.out.println("原始数据为：");
    System.out.println(original);
    // 将句中的结束符替换为空格
    String endString = original.replace('.', ' ');
    while (endString.length() > 0) {
        int index = endString.indexOf(' ');
        String data = endString.substring(0, index + 1);
        endString = endString.substring(index + 1);
        list.insert(data);
    }
    list.reversePrint();

由于实际应用中，字符串中的符号可能不止，因此可以考虑将符号替换即可。

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21fc29waGlh_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21fc29waGlh_size_16_color_FFFFFF_t_70]: /images/20221005/f6d2f75ca83a44bb8088567613b6a7ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21fc29waGlh_size_16_color_FFFFFF_t_70 1]: /images/20221005/169227c583bf45b789cccd1e556e8c6c.png