一、单链表的定义
单链表是线性表的链式存储结构。它通过一组任意的存储单元来存储数据元素,为了建立元素间的关系,每个结点除了存放自身数据(data)外,还需存放指向后继结点的指针(next)。
单链表结点声明如下:
typedef struct LNode {
ElemType data; // 数据域
struct LNode* next; // 指针域
} LNode, *LinkList;
注意代码中的类型含义:使用 LNode* 时强调这是一个结点;使用 LinkList 时强调这是一个单链表。
由于单链表元素在内存中离散分布,不支持随机存取,查找特定元素时需从表头开始遍历。引入头结点通常能简化操作逻辑:无论链表是否为空,头指针始终指向头结点,这使得对第一个数据结点的操作与其他位置的操作保持一致,且空表与非空表的处理逻辑可以统一。
二、单链表的基本操作
1. 初始化
带头结点的初始化需申请一块内存作为头结点,并将 next 置为 NULL。
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (!L) return false;
L->next = NULL;
return true;
}
不带头结点的初始化则直接将头指针设为 NULL。
2. 判空
对于带头结点的链表,若头结点的 next 为 NULL,则说明链表为空。
bool Empty(LinkList L) {
return L->next == NULL;
}
3. 求表长
遍历链表统计数据结点个数,直到遇到 NULL。
int Length(LinkList L) {
int len = 0;
LNode* p = L;
(p->next != ) {
p = p->next;
len++;
}
len;
}




