向我说明带有Node Class的LinkedList类,就像你对一个5岁的人一样

Question

我目前正在使用数据结构和算法类,结果证明它非常适合链接列表的概念.不幸的是,我的教授不是解释代码的最佳人选.我搜索了许多网站,试图了解如何构建一个链表,并能够在主要调用它,但由于某种原因,它只是不坚持.据说我有以下代码,我做错了吗？如何在数据中插入数字以及如何从一个节点移动到另一个节点？如何在main中调用节点类并打印出数据值？请向我解释一下,我是一个5岁的孩子.我正在使用C++代码块.谢谢

#include <iostream>

using namespace std;

class LinkedList
{

    class Node
    public:
    {
        Node (int data, Node *n);
        int data;
        Node *next;
    };
        Node *head;
    };


int main()
{

    LinkedList::Node NodeObj;
    NodeObj.data = 5;
    cout <<NodeObj.data;
    return 0;
}

Answer 1

一个很好的教程是:http://www.zentut.com/c-tutorial/c-linked-list/

从编程的角度来看,通常您的LinkedList类会有一些方法来处理您询问的事情,例如:

• 添加 - 在链接列表的末尾创建一个新条目
• InsertAfter(Node*n) - 在列出的列表中的指定节点之后创建一个新条目
• 删除(节点*n) - 从链接列表中删除指示的节点
• Count() - 返回链表中节点数的计数
• Get(long i) - 返回指向链表中第i个条目的指针
• 查找(某种类型的标准) - 返回指向匹配节点的指针
• 销毁 - 删除链接列表中的所有节点

然后你的主线只是调用这些方法来利用链表(对象封装的整个点).请注意,实例化了一个LinkedList对象,它实例化并管理Node对象.

因此,如果您从一些输入数组(inArray)中存储10个数字,则可以执行以下操作:

Node* n;
llObj = new LinkedList;
For (i=0; i<=9; i++) {
    n = llObj.add();
    n.data = inArray[i];
}

要逐步浏览链接列表,您可以执行以下操作:

For (i=0; i<=llObj.Count(); i++) {
    n = llObj.get(i);
    n.data = n.data + 1;
}

但是,如果您从下面的代码示例中自己编写一个.get()方法,您将看到上面的代码非常低效,并且不是从主线代码单步执行整个链表的理想方法.

要找到数字6:

n = llObj.find(6);

等等.通常,链接列表不会仅存储一个数据值,例如在您的示例中,而是存储结构或对象.因此,像Find这样的方法变得更有用,因为您可以创建查看结构或对象中各种字段的Find方法.

Add方法只遍历列出的列表中的所有现有条目,直到找到最后一个条目,然后创建一个新条目,并将前一个条目链接到现在新的最后一个条目.

Node* LinkedList::add() {
    void *n = NULL;
    if (head != NULL) {
        // one or more Nodes do exist
        // first loop until we find the last-most node who's n.next == NULL
        n = head;
        while (n.next != NULL) n = n.next;
        // found the last node, now allocate a new Node, and store a pointer to it in the formerly last node's .next property
        n.next = new Node;
        n = n.next;
        // IMPORTANT: ensure this new last Node's .next is forced to be null
        n.next = NULL;
    }
    else
    {
        // the header is NULL, so there is no first node yet
        // allocate a new Node and store a pointer to it in the LinkedList header
        head = new Node;
        n = head;
        // IMPORTANT: ensure this first Node's .next is forced to be null
        n.next = NULL;  
    {
    return n;
}

注意While循环...这是关键的链表遍历机制.该循环检查当前节点的.next字段...如果它具有非NULL指针,则循环通过将该.next指针复制到循环指针n来循环,并再次测试.一旦循环找到一个节点,其中.next为NULL,则找到最后一个节点,循环退出,其中n包含指向最后一个节点的指针.

另请注意有关LinkedList类的.head属性的If语句.当链表为空时,总是必须做一些特殊的代码来计算.有几种方法可以处理; 我选择了使用最少数据内存的那个.

删除节点意味着只在链表中"跳过它".我们遍历列出的列表,直到找到要删除的列表,我们只是将其.next属性"移回"前一个条目的.next指针.链接列表维基百科条目中有一个好的图像:

一个代码示例:

void LinkedList::remove(Node* nodeToRemove) {
    // do nothing if we've been given a NULL pointer
    if (nodeToRemove == NULL) return;
    Node *n;
    if (nodeToRemove == head) {
        // the node to remove is the very first node, so set the head
        // to the contents of the first node's .next property
        head = n.next;
        delete n;
        return;
    }

    // need to find the indicated node; the following loop locates the
    // node that is immediately before the node to be removed; note too
    // that we have to test for the end of the linked list because the
    // caller may have provided a bad pointer value
    n = head;
    while (n.next != NULL && n.next != nodeToRemove) n = n.next;
    if (n.next == NULL) return;  // reached end of linked list without finding the node
    // good, the node immediately before the node to remove has been found!
    Node* r = n.next;   // this is inefficient code but want to make it very clear to newbies
    n.next = r.next;
   delete r;
}

请注意,我们还必须对LinkedList标头做一些特殊的逻辑.请原谅我在代码中使用了返回的事实; 许多挑剔的贴纸会认为是禁忌.还要注意在上面的代码中,我们不需要做特殊的逻辑来考虑链表的结尾,只是它的开头.如果要删除的节点是链表中的最后一个节点(并且其r.next因此== NULL),那么"n.next = r.next"代码行只会将NULL移回一个位置.链表,这正是我们想要的.

您现在应该能够弄清楚如何在我提到的LinkedList类中创建所有其他方法.

===============================

我确实喜欢别人的回答,不幸的是他删除了.对于一个5岁的人来说,一个链表确实很像寻宝游戏.在Treasure Hint中,您必须亲自前往每个位置以获取下一个位置的线索.在链表中,您必须访问节点的位置以查找下一个节点的位置地址.一个完美的类比,以及首先提供它的回答者的荣誉.