线性表之带表头结点的单链表存储结构

零、无关内容

在数据结构中，线性表是一种基础且常用的数据结构，它允许高效地进行数据存储和访问。线性表的实现方式多样，其中单链表因其灵活性和简洁性而受到广泛应用。而在单链表的基础上，增加一个特殊的节点——表头节点，可以进一步简化链表的操作，特别是在处理插入、删除等操作时能够统一处理边界条件，提升代码的健壮性和可读性。

1、单链表的基础结构

单链表由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据元素，指针域则用于存储下一个节点的地址，从而将各个节点串联起来。在普通单链表中，我们通常维护一个指向链表第一个节点的指针（头指针），通过头指针可以遍历整个链表。然而，这种设计在处理链表头部的操作时略显不便，因为需要特殊处理链表为空和只有一个节点的情况。

2、引入表头节点的优势

为了解决上述问题，带表头节点的单链表在链表的最前端添加了一个特殊的节点，即表头节点。该节点不存储任何数据元素，其指针域指向链表的第一个实际节点。这样，无论链表是否为空，或者链表长度如何变化，始终存在一个固定的“首节点”供操作使用。这一改变使得链表的操作更加统一，无需再考虑链表为空的边界条件，简化了代码实现。

3、表头节点的设计

在设计带表头节点的单链表时，首先创建一个头节点，其指针域初始化为NULL，表示一个空链表。当插入第一个数据节点时，将头节点的指针域指向该数据节点，随着链表的增长，新的数据节点不断被插入到链表的适当位置，但头节点始终不变。在进行链表遍历时，通常从头节点的下一个节点开始，因为头节点本身不包含有效数据。

4、操作示例：插入与删除

使用带表头节点的单链表进行插入和删除操作时，可以统一从头节点开始处理，无需区分操作发生在链表哪个位置。例如，在链表头部插入一个节点，只需将新节点的指针域指向头节点的指针域所指向的节点，然后将头节点的指针域更新为新节点的地址即可。类似地，删除操作也是先找到待删除节点的前驱节点，然后调整前驱节点的指针域，指向待删除节点的下一节点，最后释放待删除节点。

5、应用场景与优化

带表头节点的单链表不仅简化了操作，还适用于那些需要频繁在链表头部进行操作的场景，如栈和队列的实现。在某些情况下，还可以通过在表头节点中维护额外信息（如链表长度）来进一步优化性能，虽然这会牺牲一些空间效率。

综上所述，带表头节点的单链表提供了一种灵活且高效的线性表实现方式。通过引入一个不存储数据的表头节点，可以统一处理链表操作中的边界条件，简化代码实现，并提高代码的健壮性和可读性。这种设计在实际应用中，尤其是在需要频繁进行头部操作的场景下，表现出了显著的优势。

一、什么是带表头的单链表

在单链表中，因为头结点没有直接前驱结点，所以在进行插入和删除操作时，需要特殊的处理。为了简化操作，在单链表之前添加一个空的头结点，实际的元素结点从第二个结点开始，由此称为带表头的单链表。

二、各个功能实现

（一）初始化

带表头单链表的初始化是指：构造一个仅带有一个表头结点的空单链表。

1、算法步骤

（1）为表头结点申请动态空间
（2）设置头结点的直接后继结点，即第一个数据结点为 $NULL$，即构造了一个空链表
（3）链表长度置 $0$

2、算法代码

// 带表头单链表的初始化
Status Init(HeaderSingleList* list)
{
	list->head = malloc(sizeof(Node));
	if (!list->head)
	{
		return Error;
	}
	list->head->link = NULL;
	list->n = 0;
	return OK;
}

（二）插入

带表头单链表的每个节点都有直接前驱结点，所以在进行插入操作时无需特殊化处理，简化了插入操作。

1、算法步骤

（1）判断所要插入的位置是否越界
（2）为新节点 $newNode$ 申请动态空间，并给结点数据段赋值
（3）找到要插入位置的前一个结点 $beforeNode$
（4）将 $newNode$ 的后继结点赋值为 $beforeNode->link$ ，$beforeNode$ 结点的后继结点赋值为 $newNode$
（5）表长++

2、算法代码

// 带表头单链表的插入
Status Insert(HeaderSingleList* list, int i, int value)
{
	// 如果插入的位置越界，则返回错误
	if (i < -1 || i > list->n - 1)
	{
		return Error;
	}
	Node* newNode = malloc(sizeof(Node));
	Node* before = list->head;
	for (int j = 0; j <= i; j++)
	{
		before = before->link;
	}
	
	newNode->value = value;
	newNode->link = before->link;
	before->link = newNode;
	
	list->n++;
}

（三）删除

带表头单链表的每个节点都有直接前驱结点，所以在进行删除操作时无需特殊化处理，简化了删除操作。

1、算法步骤

（1）替换link
（2）释放删除的空间

2、算法代码

void Delete(HeaderSingleList* list, int i)
{
	if (list->n == 0)
	{
		return Error;
	}
	if (i < 0 || i >list->n - 1)
	{
		return Error;
	}
	Node* beforeNode = list->head;
	Node* deleteNode = NULL;
	// 找到要删除节点的前一个结点
	for (int j = 0; j < i; j++)
	{
		beforeNode = beforeNode->link;
	}
	// 此时的 beforNode 是所要删除结点的前一个结点
	deleteNode = beforeNode->link;					// 要删除的结点deleteNode 为 beforNode 的下一个结点
	beforeNode->link = deleteNode->link;			// 将要删除结点的前一个结点的 link 指向 要删除结点的下一个结点
	free(deleteNode);
	printf("调用了 Delete(\%d) 函数\n", i);
	list->n--;
}

三、全部代码

#include 
#define ElemType int
#define Error 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int Status;

// 结点结构体
typedef struct node
{
	ElemType value;
	struct node* link;

}Node;

// 单链表结构体
typedef struct headerSingleList
{
	Node* head;
	int n;
}HeaderSingleList;


// 带表头单链表的初始化
Status Init(HeaderSingleList* list)
{
	list->head = malloc(sizeof(Node));
	if (!list->head)
	{
		return Error;
	}
	list->head->link = NULL;
	list->n = 0;
	return OK;
}

// 带表头单链表的插入
Status Insert(HeaderSingleList* list, int i, int value)
{
	// 如果插入的位置越界，则返回错误
	if (i < -1 || i > list->n - 1)
	{
		return Error;
	}
	Node* newNode = malloc(sizeof(Node));
	Node* before = list->head;
	for (int j = 0; j <= i; j++)
	{
		before = before->link;
	}
	
	newNode->value = value;
	newNode->link = before->link;
	before->link = newNode;
	
	list->n++;
}

void Delete(HeaderSingleList* list, int i)
{
	if (list->n == 0)
	{
		return Error;
	}
	if (i < 0 || i >list->n - 1)
	{
		return Error;
	}
	Node* beforeNode = list->head;
	Node* deleteNode = NULL;
	// 找到要删除节点的前一个结点
	for (int j = 0; j < i; j++)
	{
		beforeNode = beforeNode->link;
	}
	// 此时的 beforNode 是所要删除结点的前一个结点
	deleteNode = beforeNode->link;					// 要删除的结点deleteNode 为 beforNode 的下一个结点
	beforeNode->link = deleteNode->link;			// 将要删除结点的前一个结点的 link 指向 要删除结点的下一个结点
	free(deleteNode);
	printf("调用了 Delete(\%d) 函数\n", i);
	list->n--;
}

void GetValue(HeaderSingleList* list, int i, int* value)
{
	printf("调用了 GetValue() 函数\n");
	Node* node = list->head;
	for (int j = 0; j < i; j++)
	{
		node = node->link;
	}
	*value = node->value;
}

// 单链表的销毁
void Destory(HeaderSingleList* list)
{
	printf("调用了 Destory() 函数\n");
	Node* node = list->head;
	while (list->head)
	{
		node = node->link;
		free(list->head);
		list->head = node;
	}
}

void PrintAllValue(HeaderSingleList* list)
{
	if (list->n == 0) {
		return Error;
	}
	Node* node = list->head->link;
	while (node)
	{
		printf("%d -> ", node->value);
		node = node->link;
	}
	printf("NULL\n\n");

}


int main()
{
	HeaderSingleList* list = malloc(sizeof(HeaderSingleList));
	Init(list);
	Insert(list, -1, 4);
	Insert(list, -1, 3);
	Insert(list, -1, 2);
	Insert(list, -1, 1);
	Insert(list, -1, 0);

	PrintAllValue(list);
	Delete(list, 1);
	PrintAllValue(list);
	Destory(list);
	PrintAllValue(list);

}