链表问题

Question

我正在尝试自学c++，我真的很困惑链表。我一直在阅读课本和上网，但我真的很困惑它们是如何工作的。我在网上找到了一个练习，我一直想弄明白，但我没有任何进展。

下面是list.h文件:

struct node 
{
    int val;
    struct node *next;
};
int length(struct node *);
void push(struct node **, int); //add to front of list
void append(struct node **, int); //add to rear of list
void print(struct node *, int);

我有一个困难的时间试图编写长度，push和append函数

Answer 1

链表就是一串Node类串在一起，每个类都有一个指针，该指针的地址是列表中下一个Node类的地址。

如果你这样想的话，它很简单:

Coliru: http://coliru.stacked-crooked.com/a/5e71c5e31b58673c

#include <iostream>
//Proper encapsulation is not included for terseness and clarity
class Node {
public:
    int num;
    Node* next;
    Node(int n) :
        num(n),
        next(nullptr) {
    };
    ~Node() {}
};
int main() {
    Node a(0);
    Node b(1);
    Node c(2);
    Node d(3);
    Node e(4);
    //String the nodes together, linking like metal chainlinks
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    //Can you see how the "link" actually works here?
    //Each Node's "next" pointer points to the next node.
    std::cout << "Node a: " << a.num << std::endl;
    std::cout << "Node b: " << a.next->num << std::endl;
    std::cout << "Node c: " << a.next->next->num << std::endl;
    std::cout << "Node d: " << a.next->next->next->num << std::endl;
    std::cout << "Node e: " << a.next->next->next->next->num << std::endl;
    //What if I were to point e to the start of a?
    e.next = &a;
    std::cout << "Node e->next: " << e.next->num << std::endl;
    //It's node a!
    //Node e.next is now accessible through the linked list:
    std::cout << "Node e->next = a.next->next->next->next->next: " << a.next->next->next->next->next->num << std::endl;
    //Usually people just use a for loop for this type of stuff.
    //Let's use a lambda function to write one right here:
    auto index_func = [](Node* head, size_t index) {
        Node* current = head;
        Node* next = head->next;
        for (int i = 0; i < index; ++i) {
            if (next != nullptr) {
                //Hey, look at the pointers fly!
                current = next;
                next = current->next;
            } else {
                std::cout << "Whoops, we hit a null pointer before we got to our index!" << std::endl;
                break;
            }
        }
        return current->num;
    };
    //This is the same as finding the 6th node in the list (but since it's zero-indexing it's [5])
    std::cout << index_func(&a, 5) << std::endl;
    //We can also continue to do this:
    std::cout << index_func(&a, 499) << std::endl;
    //This is me accessing the 500th element, which, since our back links to our head node, it's the 4th node, d.
    return 0;   
}

你可能可以想象，如果我们决定在a或e之间插入Node，我们可以用链表做的其他恶作剧只是重新分配指针。

Answer 2

void push(struct node **list, int newVal) { //add to front of list
  struct node* firstNode = *list;
  struct node* newNode = (struct node*) malloc(sizeof(struct node));
  if (newNode == NULL) abort();
  newNode->val = newVal;
  newNode->next = firstNode;
  *list = newNode;
}
void append(struct node **list, int newVal){ //add to rear of list
  if (*list == NULL) {
    push(list, newVal);
    return;
  }
  /* Locate last node in list*/
  struct node* curNode = *list;
  while (curNode->next != NULL) 
    curNode = curNode->next;
  /* Add a new node at the end of the list */
  struct node* newNode = (struct node*) malloc(sizeof(struct node));
  if (newNode == NULL) abort();
  newNode->val = newVal;
  newNode->next = NULL;
  curNode->next = newNode;
}