c++ - 如何理解单向链表的创建

Question

问题

我在理解用 C++ 创建单向链表的教程的代码(不是意思)时遇到了一些困难。

代码

typedef int ElemType;   
struct Node{
    ElemType data;
    Node *next;
};

class LinkList{
private:
    Node *Head;
public:
    LinkList();         
    ~LinkList();
    void CreateList1(int n);
    void CreateList2(int n);
    void ListInsert(int i, int e);
    int ListDelete(int i);
    int GetElem(int i);
    int LocateElem(int e);
    int ListLength();
};

void LinkList::CreateList1(int n) {
    //create a linked list by inserting the element in the head
    Node *p, *s;
    p = Head;
    cout<<"请依次输入"<<n<<"个数据元素值"<<endl;
    for (int i =1; i<n; i++){
        s = new Node;           
        cin>>s->data;
        s->next=p->next;       
        p->next=s;              // what does it mean? I don't get it.
    }
}

void LinkList::CreateList2(int n) {
    //create a linked list by inserting the element in the end
    Node *p, *s;
    p = Head;
    cout << "请依次输入" << n << "个数据元素值" << endl;
    for (int i = 1; i < n; i++) {
        s = new Node;          
        cin >> s->data;
        p->next=s;              
        p=s;                   // what does it mean? I don't get it.
    }
}

注意事项

我不明白的代码片段被注释掉了。任何人都可以用指导性的文字或数字来解释代码吗？提前致谢。

Answer 1

这:[ ] 是一个节点，并且:-> 用于显示节点指向的位置。

第一种情况:

• HEAD 将指向新节点
• 新节点将指向HEAD之前指向的位置

p->next=s;              // what does it mean? I don't get it

It means: HEAD should now point to the new node

---

[HEAD]->

iteration 1:
-------------------------------
s = new Node      : [S1]
s->next = p->next : [S1]->
p->next = s       : [HEAD]->[S1]

iteration 2:
-------------------------------
s = new Node      : [S2]
s->next = p->next : [S2]->[S1]
p->next = s       : [HEAD]->[S2]->[S1]

iteration 3:
-------------------------------
s = new Node      : [S3]
s->next = p->next : [S3]->[S2]
p->next = s       : [HEAD]->[S3]->[S2]->[S1]

第二种情况:

• HEAD 将指向新节点
• 新节点变成HEAD

p=s;              // what does it mean? I don't get it

It means: the new node now also becomes HEAD

---

[HEAD]->

iteration 1:
-------------------------------
s = new Node      : [S1]
p->next = s       : [HEAD]->[S1]
p = s             : [HEAD,S1]               // S1 is the HEAD now

iteration 2:
-------------------------------
s = new Node      : [S2]
p->next = s       : [HEAD,S1]->[S2]
p = s             : [S1]->[HEAD,S2]        // S2 is the HEAD now

iteration 3:
-------------------------------
s = new Node      : [S3]
p->next = s       : [HEAD,S2]->[S3]
p = s             : [S1]->[S2]->[HEAD,S3]  // S3 is the HEAD now