C++实现单链表：头插法与尾插法详解

"本文主要介绍了在C++编程中创建单链表的两种基本方法：头插法和尾插法。这两种方法都是通过动态内存分配创建新的节点，并将它们连接成链表。" 在C++中，单链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表的创建通常涉及两个关键步骤：内存分配和节点链接。以下是头插法和尾插法的具体实现： 1. 头插法建表： 头插法的特点是新创建的节点始终被插入到链表的开头，使得输入数据的顺序与链表中的节点顺序相反。在C++中，首先创建一个表头节点，然后不断读取数据，生成新节点，将其数据域赋值，接着将新节点插入到表头之前，最后更新表头的next指针指向新节点。代码中定义了一个名为`create_LinkList`的函数，用于实现这个过程。 ```cpp LNode* create_LinkList(void) { int data; LNode* head, * p; head = (LNode*)malloc(sizeof(LNode)); head->next = NULL; while (1) { scanf("%d", &data); if (data == 32767) break; p = (LNode*)malloc(sizeof(LNode)); p->data = data; p->next = head->next; head->next = p; } return head; } ``` 在这个函数中，32767被用作读取数据的结束标志。当读取到这个值时，循环终止，链表创建完成。 2. 尾插法建表： 尾插法则是在链表的末尾添加新节点，保持输入数据的顺序与链表顺序一致。这种方法需要维护一个指向当前尾节点的指针。同样，我们定义一个`create_LineList`函数来实现这个过程。 ```cpp LNode* create_LineList(void) { int data; LNode* head, * p, * q; head = p = (LNode*)malloc(sizeof(LNode)); p->next = NULL; while (1) { scanf("%d", &data); if (data == 32767) break; q = (LNode*)malloc(sizeof(LNode)); q->data = data; q->next = p->next; p->next = q; p = q; // 更新尾指针 } return head; } ``` 在这个函数中，`p`指针始终指向链表的最后一个已插入节点，新节点`q`插入后，`p`更新为`q`，以保持对尾节点的跟踪。 总结来说，C++中的单链表创建涉及动态内存管理，包括`malloc()`函数用于分配节点空间，以及指针操作来构建链式结构。头插法和尾插法的区别在于插入节点的位置，头插法适用于不需要保持输入顺序的情况，而尾插法则可以保留输入顺序。在实际应用中，根据具体需求选择合适的方法。