程序员经验分享-hwhale

链表中的递归

2023-12-23

我一直在练习链表并想在其上实现递归，尽管在某些情况下我能够有效地实现它，但在其他情况下我却惨败。我想知道一种进行递归的方法，以便不必使用“while”来遍历链接列表，我已经使用递归来遍历数组，但是当我想在这种情况下做类似的事情时它失败。

我在实现递归方面没有太多经验，并且想在这种方法中应用它以获得更多经验，但至少它通过一遍又一遍地执行它帮助我更多地理解链表。谢谢。

class Node {
    // Accept arguments (the second one could be optional)
    constructor(data, next) {
        this.data = data; 
        this.next = next;

    }
    lastNode() { // new method that uses recursion
        return this.next?.lastNode() || this;
    }
}
class ListRecurse {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    add(data) {
        let newNode = new Node(data); // No second argument. It has a default value
        if (this.head === null) {
            this.head = newNode;
        } else {
            // The lastNode implementation uses recursion:
            this.head.lastNode().next = newNode;
        }
        this.size ++;
        return this; // to allow chaining
    }
    insertAdd(data, index) {
        if (index < 0 || index > this.size) {
            return null;
        }
        let newNode = new Node(data);
        let current = this.head;
        let prev;
        if (index === 0) {
            newNode.next = current;
            this.head = newNode;
        }
        else {
            for (let i = 0; i < index; i++) {
                prev = current;
                current = current.next;
            }
            this.head.lastNode().next = current;
            prev.next = newNode;
        }
        this.size++;
        return this;
    }
    Print() {
        if (!this.size) {
            return null;
        }
        let current = this.head;
        let result = "";
        while(current) {
            result += current.data += "=>";
            current = current.next;
        }
        result += "X";
        return result;
        }
    DeletexData(data) {
           let current = this.head;
           let prev = null;
           if (this.head === null) {
               return null;
           }
           else if (current.data === data) {
               if(!prev) {
                   this.head = this.head.next;
               }
               else
               prev.next = current.next
           }
           return this.SearchDelete(data)
           }
    SearchDelete (data) {
            let current = this.head;
            let prev = null;
            while(current != null) {
                if (current.data === data) {
                    if (!current.next) prev.next = null
                else prev.next = current.next
                    this.size--;
                    return data;
                    }
                prev = current;
                current = current.next;
            }
        return null;
        }
    DeleteLastNode() {
        let current = this.head;
        if (current === null) {
            return 1
        }
        else if (current.next === null) {
            this.head = null;
        }
        else return this.LastNode()
        };
    LastNode() {
        let current = this.head;
        while (current.next.next != null) {
            current = current.next;
        }
        current.next = null;
        this.size--;
    }
    Search(data) {
        let current = this.head;
        if (current === null) {
            return null;
        }
        else 
        return this.RainbowSix(data)
    }
    RainbowSix(data) {
        let current = this.head; 
        while (current) {
            if (current.data === data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }
    Size(){
        return this.size
    }
}
let list = new ListRecurse();
list.add(1).add(2).add(3).add(44).add(66);
list.insertAdd(33,0)
list.DeleteLastNode()
console.log(list.Search(3))
console.log(list.Size())
console.log(list.Print())
console.log(list);

这可能有帮助，也可能没有帮助。它建议采用一种截然不同的方式来构建列表。

这个想法是，递归虽然偶尔与面向对象 (OO) 系统一起使用，但它与函数式编程 (FP) 的联系更为紧密。因此，如果您要在列表上使用递归，您不妨将其与 FP 列表一起使用。

创建和操作列表是 FP 的优势之一，我们可以更简单地编写您的代码。我们创建一个仅包含一项的列表，42通过致电const list1 = ins (42) (null)。我们在前面加上17通过致电const list2 = ins (17) (list1)。或者我们可以像这样编写整个链：

const list3 = ins (1) (ins (2) (ins (3) (ins (4) (ins (5) (null)))))

与您的代码有很多差异，但最基本的差异之一是它将列表视为不可变对象。我们的代码都不会change一个列表，它只会创建一个具有更改后的属性的新列表。

这是什么ins可能看起来像：

const ins = (data) => (list) => 
  ({data, next: list})

我们可以选择将其写为(data, list) => ...代替(data) => (list) => ...。这只是个人风格偏好的问题。

但基本结构是列表是

  • a value
  • followed by either
    • 另一个清单
    • or null

以下是这些想法的实现：

const ins = (data) => (list) => 
  ({data, next: list})

const del = (target) => ({data, next}) =>
  target == data ? next : next == null ? {data, next} : {data, next: del (target) (next)}  

const delLast = ({data, next}) =>
  next == null ? null : {data, next: delLast (next)}

const size = (list) => 
  list == null ? 0 : 1 + size (list.next)

const search = (pred) => ({data, next}) => 
  pred (data) ? {data, next} : next != null ? search (pred) (next) : null

const fnd = (target) => 
  search ((data) => data == target)

const print = ({data, next}) => 
  data + (next == null ? '' : ('=>' + print (next)))    

const list1 = ins (1) (ins (2) (ins (3) (ins (44) (ins (66) (null)))))
const list2 = ins (33) (list1)
const list3 = delLast (list2)

console .log (fnd (3) (list3))
console .log (size (list3))
console .log (print (list3))
console .log (list3)
.as-console-wrapper {max-height: 100% !important; top: 0}

请注意，所有这些函数（除了ins and find是直接递归的。他们都自称。和find只是将递归工作委托给search.

试图描述所有这些功能有点太多了，但让我们看一下其中两个。print是一个简单的函数。

const print = ({data, next}) => 
  data + (next == null ? '' : ('=>' + print (next)))

我们通过包含数据和后跟以下两件事之一来构建输出字符串：

  • 一个空字符串，如果next is null
  • '=>'加上递归print呼吁next， 否则。

del是一个稍微复杂一些的函数：

const del = (target) => ({data, next}) =>
  target == data
    ? next 
    : next == null 
      ? {data, next: null} 
      : {data, next: del (target) (next)}

我们测试当前数据是否是我们要删除的目标。如果是，我们只需返回存储为的列表next.

如果没有，我们检查是否next一片空白。如果是，我们返回当前列表（的副本）。如果不是，那么我们返回一个由当前数据形成的新列表，并递归调用以从存储为的列表中删除目标next.

如果您想了解更多有关这些想法的信息，您可能需要搜索“缺点列表”（这里的“缺点”不是“优点”的反义词，而是与“构造”某些东西有关。）

我使用的术语与那里最常用的术语不同，但想法大致相同。如果您遇到这些条款car and cdr，它们相当于我们的data and next， 分别。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

javascript

recursion

LinkedList

链表中的递归 的相关文章