2-2线性表（链表）1

线性表是一种常见的数据结构，它是由n（n≥0）个相同类型元素构成的有限序列。在本节中，我们将深入探讨线性表的链式存储结构，特别是单链表。 链式存储结构与顺序存储结构不同，它允许元素在内存中的位置不连续，而是通过指针链接起来。这样做的好处是能够灵活地处理动态变化的元素数量，因为链式存储不需要预先分配连续的内存空间。 单链表是线性表的一种链式实现，每个节点包含两部分：数据域和指针域。数据域用于存储元素值，而指针域则指向链表中的下一个节点。如果链表中的最后一个节点的指针域为空，那么这个节点就是尾结点。如果链表只有一个节点，那么这个节点既是头结点也是尾结点。 在C语言中，我们可以使用结构体来定义单链表的节点。例如，定义一个名为`LNode`的结构体类型，其中包含一个整型数据元素`ElemType`和一个指向`LNode`类型的指针`next`，如下所示： ```c typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; } LNode, *LinkList; ``` 这里，`LNode`是结构体类型，`LinkList`是结构体指针类型。我们可以用`LinkList`类型的指针`head`来表示链表的头指针，其他指针如`p`和`L`可以作为辅助指针使用。 创建链表节点通常需要使用`malloc`函数来动态分配内存。例如，创建一个新的节点并初始化其数据域和指针域： ```c p = (LinkList)malloc(sizeof(LNode)); if (p != NULL) { p->data = some_value; p->next = NULL; // 初始化指针域为NULL } ``` 在单链表中，为了方便操作，通常会添加一个特殊的头结点，其数据域无意义，指针域指向链表的第一个实际元素。这样，即使链表为空，头指针`head`也不会为`NULL`，使得操作更统一。 单链表的主要操作包括创建（拉链）、遍历、插入和删除。创建链表时，可以采用头插法（从链尾向链头创建）或尾插法（从链头向链尾创建）。遍历链表通常通过辅助指针逐个访问节点。插入和删除操作需要找到合适的节点，并更新前后节点的指针。 插入节点时，需要分配新节点，设置其数据域和指针域，然后修改前后节点的指针。删除节点时，需要找到待删除节点的前驱节点，然后更新前驱节点的指针以跳过被删除节点。 单链表是一种高效且灵活的数据结构，特别适合处理动态变化的数据集。通过熟练掌握单链表的创建、遍历、插入和删除等操作，可以有效地利用链式存储结构解决各种编程问题。