单链表的插入与遍历.

### 单链表的插入与遍历 #### 知识点概述 本篇文章将详细介绍单链表的基本概念、插入操作及遍历操作，并通过具体的C++代码实现来帮助读者更好地理解这些概念。单链表是一种常见的线性数据结构，每个元素包含一个指向下一个元素的指针，使得数据元素按顺序链接起来。 #### 单链表基本概念 在计算机科学中，链表（Linked List）是一种由节点组成的数据结构，每个节点包含两部分：存储实际数据的数据域和指向列表中下一个节点的地址域（即指针）。单链表是其中最简单的一种形式，其特点在于每个节点只包含一个指针域，用于指向列表中的下一个节点。 #### 单链表节点定义 ```cpp typedef struct LNode { char* data; struct LNode* next; } LinkList; ``` 上述代码定义了一个名为`LNode`的结构体类型，它有两个成员变量：`data`用于存储数据，`next`用于存储指向下一个节点的指针。 #### 单链表的插入操作 插入操作是指将新节点插入到单链表中的特定位置。根据不同的需求，可以有多种插入方式： - **头部插入**：将新节点插入到链表的头部。 - **尾部插入**：将新节点插入到链表的尾部。 - **中间插入**：将新节点插入到链表的指定位置。 本例中提供了两种插入方式：头部插入和尾部插入。头部插入相对简单，只需调整头指针即可；而尾部插入则需要遍历整个链表找到最后一个节点，然后将其指针指向新节点。 ```cpp LinkList* addList(LinkList* head, char* value, bool pos) { LinkList* u = (LinkList*)malloc(sizeof(LinkList)); u->data = value; u->next = NULL; if (pos) { // pos=1 表示尾部插入 if (head == NULL) return u; LinkList* p = head; while (p->next) p = p->next; p->next = u; return head; } else { // pos=0 表示头部插入 u->next = head; return u; } } ``` #### 单链表的遍历操作 遍历操作是指按照一定的顺序访问链表中的每一个节点。对于单链表来说，通常是从头节点开始，沿着每个节点的指针域依次访问直到达到链表末尾。遍历操作常用于显示链表中的所有元素或者对链表进行其他处理。 ```cpp void printList(LinkList* tempList) { while (tempList) { cout << tempList->data << endl; tempList = tempList->next; } } ``` 在上述代码中，`printList`函数实现了对单链表的遍历并打印每个节点的数据域。 #### 主函数示例 我们通过主函数`main`来演示如何创建一个单链表，向其中添加数据以及遍历该链表。 ```cpp void main() { LinkList* head; head = (LinkList*)malloc(sizeof(LinkList)); head = 0; // 初始化为空 char* text; for (int i = 0; i < 2; i++) { text = (char*)malloc(sizeof(char*)); cin >> text; head = addList(head, text, 1); // 尾部插入 } printList(head); } ``` 这段代码首先初始化一个空链表`head`，然后通过循环输入两次数据并将它们以尾部插入的方式添加到链表中。最后调用`printList`函数打印链表的所有元素。 ### 总结 本文介绍了单链表的基本概念、插入操作和遍历操作，并通过具体的代码示例进行了实现。单链表作为一种常用的数据结构，在计算机程序设计中有着广泛的应用。理解并掌握这些基础知识有助于进一步学习更复杂的数据结构和算法。