线性表基础：顺序与链式存储详解

单链表存储结构是第2章线性表中的一个重要内容，主要关注于线性表在数据结构中的实现方式之一。线性表是一种具有特定顺序关系的数据结构，其特点是元素按线性排列，每个元素都有一个直接前趋和一个直接后继，通常包括开始结点（无前趋）和终端结点（无后继）。线性表可以分为顺序存储结构和链式存储结构。 顺序存储结构中，数据元素在内存中连续存储，通过下标可以直接访问，但插入和删除操作可能需要移动大量元素，效率较低。相反，链式存储结构如单链表，每个节点包含数据域和指针域，数据不再连续，通过指针链接相邻节点。创建链表时，定义一个结点结构类型LNode和头指针类型LinkList，例如： ```c typedef struct LNode { DataType data; // 数据域，存储元素值 struct LNode *next; // 指针域，指向下一个节点 } LNode; typedef LNode *LinkList; // 结点和头指针类型名 LinkList L; // 头指针变量 ``` 分配结点空间使用malloc函数，如`p = (LinkList) malloc(sizeof(LNode))`，而访问和修改节点则通过指针操作，如`p->data = e` 和 `p->next = NULL` 或 `p = p->next`。 单链表的主要优点是插入和删除操作效率高，因为只需要改变指针，无需移动大量数据。然而，查找操作较慢，因为它需要从头开始遍历。对于线性表的ADT（抽象数据类型）定义，包括了数据对象D（元素集合，元素类型为ElemType）和数据关系R（通过序偶<ei-1, ei>表示元素之间的顺序关系）。复杂线性表，如学生入学情况表，可以通过自定义的数据结构来表示，保持一对一的关系，进一步体现了线性表的抽象性和原子性。 总结来说，单链表存储结构是线性表的一种实用形式，适用于需要频繁插入和删除元素，但查找效率较低的应用场景。理解并掌握这种数据结构是深入学习数据结构和算法的基础。