4

我试图了解它们是如何工作的，但我遇到了很多困难。是否有人愿意直观地解释它们，或者提供他们认为对刚开始接触该主题的人有用的资源？

所以假设我有这个：

struct node
{
   int nodeNum;
   nodes *next;
}

要创建“头”节点，我会执行以下操作：node *head = new node;这样我的链表现在看起来像在此处输入图像描述. 分配后：

head->nodeNum = 10;
head->next = NULL;

我们有在此处输入图像描述。现在，如果我想写一个插入节点的函数，我可以写：

void insert(node *previousNode, int num)
{
    previousNode = new node;
    previousNode->nodeNum = num;
    previousNode->next = NULL;
}

所以如果我要这样做，比如说，insert(head, 20);我的新列表看起来像在此处输入图像描述？

如果一切正确，我如何使用此信息从列表中搜索和/或删除节点？例如，遍历节点并不像所描述的那样直观head = head->next;。这是如何运作的？

您可以提供任何使该主题更易于理解的建议都会很棒。感谢大家的帮助！

4

6 回答 6

3

您的插入功能无法正常工作；它只是创建一个新节点而不将其添加到列表中，并在函数返回时丢失它（导致内存泄漏）：

head -> 10 -> NULL     becomes    head -> 10 -> NULL
                                  (lost)  20 -> NULL

相反，它应该将列表的旧尾部链接到新节点，并在旧节点之后插入新节点：

void insert(node * prev, int num) {
    node * new_node = new node;
    new_node->nodeNum = num;
    new_node->next = prev->next;  // add the old tail after the new node
    prev->next = new_node;        // add the new node after the old node
}

insert(head, 20); // insert 20 after the head
// head -> 10 -> NULL   becomes    head -> 20 -> 10 -> NULL

如何使用此信息从列表中搜索和/或删除节点？

要进行迭代，您需要维护自己的指向正在查看的元素的指针；这从 开始head，然后跟随next指针直到它到达末尾（即为next空）：

for (node * n = head; n; n = n->next) {
    if (n->nodeNum == 20) {
        std::cout << "Found node 20!\n";
        break;
    }
}

要从单链表中删除一个节点，您需要一个指向该节点之前的指针以更新其next指针：

void remove_next(node * prev) {
    if (prev->next) {
        node * next = prev->next->next;  // Get the tail after the removed node
        delete prev->next;
        prev->next = next;               // Add the tail after the remaining node
    }
}

remove_next(head);
// head -> 20 -> 10 -> NULL    becomes    head -> 10 -> NULL
于 2012-11-28T12:08:32.370 回答
3

你的问题在这里：

void insert(node *previousNode, int num)
{
previousNode = new node;
previousNode->nodeNum = num;
previousNode->next = NULL;
}

insert(head, 20);

这就是这段代码的作用： previousNode = new node;创建一个指向节点的指针并将该指针分配给previousNode。PreviousNode 最初是一个复制头，现在它指向新的东西。您现在将值分配给新节点。换句话说，插入的这种实现不会插入。

你想做的更像是：

void better_insert(node *previousNode, int num)
{
    node *post_node = new node;    #create a brand new pointer to a brand new node
    post_node->nodeNum = num;      #give it a number
    post_node->next = previousNode->next; #we want previousNode to be behind new node
    previousNode->next = post_node;     
}

它的作用是：在创建一个新节点并用新指针指向它之后，我们给它一个数字。接下来是理清指针指向的位置......

假设我们在链表中挥动一些节点。所有小写​​字母都是指针，好吗？

a->next = b

现在说我们希望节点x在 之后a，并且有数字 10... 我们调用 `better_insert(a, 10)

post_node指向一个新节点（我们的节点 x），并被分配 10.cool...

我们想要：

a->next = x
x->next = b

我们有：

a->next = b
x->next = null

该函数的最后两行只是随机播放内容，直到符合要求

所以更详细...

我们有：

a->next = b
x->next = null

所以我们叫：

post_node->next = previousNode->next; #we want previousNode to be behind new node

现在我们有： a->next = b x->next = b

现在我们调用：

previousNode->next = post_node;

我们最终得到：

a->next = x
x->next = b

或者换句话说：

a->next = x
a->next->next = b
于 2012-11-28T12:11:56.507 回答
2

您需要在代码中使用更多变量。一个insert操作修改两个节点。需要将前一个节点更改为指向新节点，并且需要创建新节点并使其指向前一个节点之后的节点（可能为NULL，也可能不是NULL）。

void insert(node *previousNode, int num)
{
    node *newnode = new node;
    newnode->nodeNum = num;
    newnode->next = previousNode->next;
    previousNode->next = newnode;
}

要遍历列表，您需要跟踪“当前节点”，您可以将其从一个节点更改为下一个节点：

while (currentNode != 0) {
    do_something_with(currentNode);
    currentNode = currentNode->next;
}

当然，如果do_something_with删除该节点，那么之后您将无法继续前进。此外，要从单链表中删除一个节点，您需要一个指向它之前的节点的指针。因此，在这种情况下，您的循环可能会跟踪两个节点，当前节点和先前节点，而不仅仅是一个节点。

于 2012-11-28T12:09:33.730 回答
1

您使用的术语让您感到困惑。希望这个类比不会让你更加困惑。从本质上讲，将链表想象成一组可怕的门口，一旦你进入一个门口，它就会在你身后关闭，你只能看到那个房间里的东西或去下一个房间。从这个走廊的外面，你只知道入口在哪里，不知道里面是什么。

所以，从你的链表结构之外，你所知道的只是入口，一些指针ll_node *head;。里面head是一些数据和指向链表中下一个节点的指针。遍历该链表就像从走廊的入口开始，head一次进入一个走廊，直到找到您要查找的节点一样简单。

ll_node *current_location = head;
while (current_location != NULL)
{
   // if we are at the node that you were hoping to reach, exit.
   if (current_location->nodeNum == target_data_im_looking_for)
   {
      break;
   }
   // this isn't the node you're looking for, go to the next one.
   current_location = current_location->next;
}

类似地，插入节点应该遍历到链表的末尾（直到current_location->next == NULL），并将最后一个元素的 next 指针替换为ll_node您创建的新元素的内存位置。我不会为你实现它，所以你有机会学习，但这里有足够的东西可以到达你想去的地方。

于 2012-11-28T12:06:48.930 回答
1

通常，链表的节点不包含其编号。它通常由一个数据和一个指向下一个节点的指针组成。此外，您应该让您的代码没有拼写错误。

typedef Data int;

struct node
{
   Data data; // some Data
   node *next;   // pointer to the next node
}

通常，您也不希望在指定节点之后出现新节点，而是希望列表。void insert(node *previousNode, int num)签名建议您在某个指定的前一个节点之后想要新节点。

从技术上讲，您可以通过三种方式将新节点添加到列表中。到列表的开头或结尾或中间的某个位置。添加到开头是最快和最简单的。

void insert(Data num)
{
    node* tmp = new node;  //make a new node
    tmp->data = num;       //fill in data
    tmp->next = head;      //set the next element of new one to be the current head
    head = tmp;            //set new element as the head
}

这样，您就可以在列表前面放置一个新元素。你总是从头到尾遍历一个单向链表。

void print_all()
{
   node* current = head;      // start at head
   while(current != NULL){    // while element exists
     cout << current->data << ' ';   //print its data
     current = current->next; //move to the next one
   }
}

当您有带有数据框和箭头的图片时，很容易理解node* next。

这是初学者。您需要修改insert函数以处理列表最初为空的特殊情况。即head == NULL。

此外，我强烈鼓励您尝试以面向对象的方式实现它。编写class List使用struct node.

class List {
  private:
    node* head;
  public:
    List();
    void insert(data);
    void print_all();
}

尝试实现这些功能。根据我的经验，当你以这种方式做事时，它有助于组织你对数据结构和容器的思考，而且它更像是 C++ 的方式来做这样的事情。

于 2012-11-28T12:14:27.357 回答
0

在您上面提到的列表中，您的信息很少，即 nodeNum。你应该在其中保留更多的离子化。例如，在值为 nodeNum = 10 的节点上，应该有一些您想从该节点获取的其他信息。所以当用户调用

node* search(node *head,int num){
      node *temp = head;//copy node reference into temp variable
      while (temp != NULL){
            if (temp->nodeNum == num){
               return temp;
            }
            temp = temp->next;
      }

}

您可以使用 node 获取该节点中的数据

 res = search(head,10);

用于删除

bool delete(node *head,int num){
      node *temp = head;//copy node reference into template
      node *prev = NULL;
      bool isDelete = false;
      while (temp != NULL){
            if (temp->nodeNum == num){
               break;
            }else
               prev = temp;
               temp = temp->next;
            }
      }
      if (temp != NULL){
          prev-> next = temp->next;//maintain list
          delete temp;
          isDelete = true;
      }
      return  isDelete;
}
于 2012-11-28T12:17:22.683 回答