链表基础1——无头结点单向非循环链表的基本操作（c语言实现）_无头节点单向链表

目录

结点

头指针

无头结点单向不循环链表

链表的基本操作

一，创建新结点

二，尾部插入一个元素

三，头部插入一个元素

四，删除最后一个结点

五，删除第一个元素

六，查找特定值的结点

七，在pos位置前插入一个元素

八，删除pos位置的元素

九，在pos位置后插入一个元素

十，在pos位置后面删除一个元素

十一，打印链表

完整操作

---

结点

在C语言中，单链表的结点通常是一个结构体，它包含一个数据域用于存储数据，以及一个指针域用于指向链表中的下一个结点。

下面是一个简单的单链表结点的定义：

typedef int SLTDataType;
 
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

SLTNode是“Singly Linked List Node”的缩写，它表示单链表中的结点。

在“SLTNode”这个缩写中，中间的“T”通常代表“Type”或者“Node”的缩写。在这里，“T”更是为了强调这是一个特定的类型（Type）或者是一个结点（Node）的表示。

在这段代码中，首先定义了一个新的数据类型别名 SLTDataType，它实际上就是 int 类型。这样做的好处是，如果将来需要改变链表中存储的数据类型，只需要修改 SLTDataType 的定义即可，而不需要修改链表中所有使用这种数据类型的地方。

接着定义了一个结构体 SListNode，这个结构体代表单链表中的一个结点。

结构体中包含两个成员：

1. data：类型为 SLTDataType（也就是 int），用于存储该结点的数据。
2. next：类型为指向 SListNode 类型的指针，用于指向链表中的下一个结点。

最后，为这个结构体类型定义了一个别名 SLTNode。在后续的代码中，可以使用 SLTNode 来代替 struct SListNode，使得代码更加简洁。

这样定义单链表的结点之后，就可以方便地创建和操作链表了。

头指针

头指针是一个指针，它指向链表或链表中的第一个节点。

在链表中，每个节点包含一个数据项和一个指向下一个节点的指针。

通过头指针，我们可以访问链表中的第一个节点，然后可以通过节点的指针访问下一个节点，以此类推。使用头指针，我们可以对链表进行插入、删除、查找等操作。

头指针在确定线性表中第一个元素对应的存储位置时非常有用，它一般用于处理数组、链表、队列等数据结构。在链式存储中，只要不是循环链表，就一定存在头指针。单链表可以用头指针的名字来命名，头指针指向第一个节点

无头结点单向不循环链表

链表的基本操作

一，创建新结点

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//分配内存
	if (newnode == NULL)//如果内存分配失败
	{
		perror("malloc fail");
		return NULL;
	}
//给新结点赋值
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

这段代码定义了一个名为 BuySLTNode 的函数，用于创建一个新的单链表节点，并将新节点的数据部分初始化为传入的参数 x，同时将其 next 指针初始化为 NULL。

二，尾部插入一个元素

//这里的尾部不一定要是链表的尾部，也可以是链表任何一个结点的后面那个位置
//在这里思考时，我们是假设pphead是头指针的地址，来进行设计的
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
 
	SLTNode* newnode = BuySLTNode(x);
//链表为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else//链表不为空
	{
		// 找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)//寻找最后一个结点
		{
			tail = tail->next;
		}
//现在tail是最后一个结点
		tail->next = newnode;//将旧的尾节点的next指向新结点，让新结点变成新的尾结点
	}
}

这段代码定义了一个函数 SLTPushBack，用于在单链表的尾部添加一个新的节点。函数接收两个参数：一个指向头节点指针的指针 pphead 和一个要添加到链表中的数据类型 x。

需要注意的是，它假设 pphead 指向的是头节点的指针，而不是头节点本身。

这意味着，如果链表为空，*pphead 将会被设置为新节点的地址；如果链表非空，则不会改变头节点的地址，只是链表的长度会增加。

三，头部插入一个元素

//这里的头部不仅仅是指链表的头部，也可以是任何一个结点的前面位置
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//判断pphead是不是为空
 
	SLTNode* newnode = BuySLTNode(x);//创建新结点
	newnode->next = *pphead;//使新结点变成第一个结点
	*pphead = newnode;//使头指针指向第一个结点
}

这段代码定义了一个函数 SLTPushFront，用于在单链表的头部插入一个新的节点。函数接收两个参数：一个指向头节点指针的指针 pphead 和一个要插入到链表中的数据类型 x。

这个函数实现了在单链表头部插入节点的功能。无论链表是空的还是有元素的，都能正确工作。在链表为空的情况下，新节点将成为唯一的节点，并且头节点指针 *pphead 将指向这个新节点。在链表非空的情况下，新节点将被插入到原来头节点的前面，成为新的头节点。

需要注意的是，SLTPushFront 函数假设 pphead 指向的是头节点的指针的地址，因此它可以直接修改头节点指针的值。

如果 pphead 指向的是头节点本身而不是其地址，那么函数将无法修改链表的头节点，因为传递的是头节点值的一个副本。在这个实现中，通过传递指针的指针，我们确保了可以修改头节点指针本身。

四，删除最后一个结点

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//*phead为空的话，结点都不存在，你还删个锤子啊
 
//这里要分多种情况处理
	// 1、只有一个节点
 
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else	// 2、多个节点
	{
	
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)//寻找倒数第二个结点
		{
			tail = tail->next;//往后走
		}
 
		free(tail->next);//释放最后一个结点
		tail->next = NULL;//使得倒数第二个结点成为最后一个结点
	}	
}

这段代码定义了一个函数 SLTPopBack，用于删除单链表的尾部节点，并释放其占用的内存。函数接收一个指向头节点指针的指针 pphead 作为参数。

需要注意的是，这个 SLTPopBack 函数假设链表至少有一个节点。如果链表为空（即 *pphead 为 NULL），则函数的行为是未定义的，因为会尝试解引用一个空指针。在实际应用中，你可能希望在函数开始处添加一个检查，以确保链表不为空，或者至少确保 pphead 不为 NULL。此外，如果链表只有一个节点，该函数也能正确工作，因为第一个 if 语句会处理这种情况。

另外，这个函数的实现方式假设了链表至少有两个节点才调用 SLTPopBack。如果链表只有一个节点，应该由调用者确保不会调用这个函数，或者应该在函数内部进行更严格的检查以避免潜在的错误。

五，删除第一个元素

void SLTPopFront(SLTNode** pphead)
{
 
	assert(pphead);
	assert(*pphead);//如果*pphead为空，那么结点不存在，不能删除啊
 
 
	SLTNode* first = *pphead;
	*pphead = first->next;//将第二个结点变成第一个结点
	free(first);//删除旧的第一个结点
}

这段代码定义了一个函数 SLTPopFront，用于删除单链表的头部节点，并释放其占用的内存。函数接收一个指向头节点指针的指针 pphead 作为参数。

这个函数实现了在单链表头部删除节点的功能。

无论链表是只有一个节点还是有多个节点，它都能正确工作。在删除头部节点后，链表的头节点将变为原来的第二个节点（如果存在的话），或者链表将变为空（如果原来只有一个节点）。

需要注意的是，这个函数假设链表至少有一个节点。如果链表为（即 *pphead 为 NULL），则函数行为是未定义的，因为会尝试解引用一个空指针。

在实际应用中，你应该在调用 SLTPopFront 之前确保链表不为空，或者在函数内部添加额外的检查来处理空链表的情况。

六，查找特定值的结点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)//首先我们要确保cur不是空的，才能确保能找到元素
	{
		if (cur->data == x)//找到了
		{
			return cur;
		}
 
		cur = cur->next;//下一个
	}
 
	return NULL;
}

这段代码定义了一个函数 SLTFind，用于在单链表中查找一个具有特定数据值的节点。函数接收两个参数：一个指向链表头节点的指针 phead 和一个要查找的数据值 x。

这个函数通过遍历链表来查找具有特定数据值的节点。

如果找到匹配的节点，则返回该节点的地址；否则返回 NULL。

这个查找过程的时间复杂度是 O(n)，其中 n 是链表的长度，因为在最坏的情况下，可能需要遍历整个链表。

七，在pos位置前插入一个元素

// pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
//不用assert(*pphead)是因为如果*pphead为空也不影响插入，只影响删除
 
if (pos == *pphead)
	{
		SLTPushFront(pphead, x);//头插法
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

这段代码定义了一个函数 SLTInsert，用于在单链表的指定位置 pos 之前插入一个新的节点，新节点的数据值为 x。

函数接收三个参数：一个指向头节点指针的指针 pphead，一个指向链表中某个节点的指针 pos，以及要插入的新节点的数据值 x。

这个函数实现了在单链表指定位置插入新节点的功能。它首先检查插入位置是否为链表头部，如果是，则调用专门的头部插入函数。如果不是头部，则找到插入位置的前一个节点，并在该位置插入新节点。

需要注意的是，这个函数假设 pos 指向的节点确实存在于链表中，并且 pos 不是 NULL。如果 pos 不指向链表中的有效节点，则函数的行为是未定义的。

在实际应用中，你应该在调用 SLTInsert 之前确保 pos 指向的节点是链表中的一个有效节点。

八，删除pos位置的元素

// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	//assert(*pphead);
 
	if (*pphead == pos)//pos位置刚好是第一个结点的位置
	{
		SLTPopFront(pphead);//我们可以使用删除第一个结点的代码
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;//往后找
		}
 
		prev->next = pos->next;//使得pos的前一个位置的结点和pos后面一个位置的结点相连
		free(pos);//删除这个位置的元素
 
		//pos = NULL;//这个是无用的，因为它是个副本啊，设置了也没有用
	}
}

这段代码定义了一个函数 SLTErase，用于在单链表中删除指定位置的节点 pos。

函数接收两个参数：一个指向头节点指针的指针 pphead 和一个指向要删除节点的指针 pos。

这个函数实现了在单链表中删除指定位置节点的功能。它首先检查要删除的节点是否为链表头部，如果是，则调用专门的头部删除函数。如果不是头部，则找到要删除节点的前一个节点，并更新其 next 指针来跳过要删除的节点。最后，释放要删除节点的内存。

需要注意的是，这个函数假设 pos 指向的节点确实存在于链表中，并且 pos 不是 NULL。如果 pos 不指向链表中的有效节点，则函数的行为是未定义的。

在实际应用中，你应该在调用 SLTErase 之前确保 pos 指向的节点是链表中的一个有效节点。

九，在pos位置后插入一个元素

// pos后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;//使得新结点和pos后面一个结点相连
	pos->next = newnode;//断掉pos和之前后面一个结点的关系
//使得pos后面一个结点是新结点
}

这段代码定义了一个函数 SLTInsertAfter，用于在单链表中指定节点 pos 的后面插入一个新的节点，新节点的数据值为 x。函数接收两个参数：一个指向链表中某个节点的指针 pos 和要插入的新节点的数据值 x。

这个函数实现了在单链表中指定节点后面插入新节点的功能。它假设 pos 指向的节点确实存在于链表中，并且 pos 不是 NULL。如果 pos 不指向链表中的有效节点，则函数的行为是未定义的。在实际应用中，你应该在调用 SLTInsertAfter 之前确保 pos 指向的节点是链表中的一个有效节点。

这个函数没有处理头节点插入的特殊情况，因为从函数参数和逻辑上看，它假设 pos 是链表中的一个非头节点。如果需要处理头节点插入的情况，你需要修改函数逻辑或者在调用这个函数之前先检查 pos 是否为头节点，并相应地处理。

十，在pos位置后面删除一个元素

// pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//我们要确保pos后面有元素才能去删除它
 
 
	SLTNode* del = pos->next;
//使得pos和pos后面第二个元素建立联系，断掉pos和pos后面第一个元素的联系
	pos->next = del->next;
	free(del);//删除pos后面的
	//del = NULL;
}

这段代码定义了一个函数 SLTEraseAfter，用于在单链表中删除指定节点 pos 后面的节点。函数接收一个参数：一个指向链表中某个节点的指针 pos。

需要注意的是，虽然 del = NULL; 这行代码在函数内部将 del 设置为 NULL，但这并不会影响到函数外部的任何指针。

因为 del 只是一个局部变量，它的改变不会影响到函数外部的变量。这行代码主要是为了在函数内部避免使用已经被释放的 del 指针，从而防止潜在的错误。

这个函数实现了在单链表中删除指定节点后面节点的功能。它假设 pos 指向的节点确实存在于链表中，并且 pos 后面确实有另一个节点。如果 pos 不指向链表中的有效节点，或者 pos 是链表的最后一个节点，则函数的行为是未定义的。在实际应用中，你应该在调用 SLTEraseAfter 之前确保 pos 指向的节点是链表中的一个有效节点，并且它不是链表的最后一个节点。

十一，打印链表

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while (cur->next != NULL)
	//while(cur != NULL)
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//cur++;
	}
	printf("NULL\n");
}

完整操作

typedef int SLTDataType;
 
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
 
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while (cur->next != NULL)
	//while(cur != NULL)
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//cur++;
	}
	printf("NULL\n");
}
 
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
 
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}
 
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
 
	SLTNode* newnode = BuySLTNode(x);
 
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
 
		tail->next = newnode;
	}
}
 
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
 
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
 
 
void SLTPopBack(SLTNode** pphead)
{
	// 暴力检查
	assert(pphead);
	assert(*pphead);
 
	// 温柔的检查
	//if (*pphead == NULL)
	//	return;
 
	// 1、只有一个节点
	// 2、多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		// 找尾
		//SLTNode* prev = NULL;
		//SLTNode* tail = *pphead;
		//while (tail->next != NULL)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}
 
		//free(tail);
		//tail = NULL;
 
		//prev->next = NULL;
 
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
 
		free(tail->next);
		tail->next = NULL;
	}	
}
 
void SLTPopFront(SLTNode** pphead)
{
	// 暴力检查
	assert(pphead);
	assert(*pphead);
 
	// 温柔的检查
	//if (*pphead == NULL)
	//	return;
 
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}
 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
 
		cur = cur->next;
	}
 
	return NULL;
}
 
// pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
 
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
 
// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	//assert(*pphead);
 
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}
 
// pos后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
 
// pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
 
	//SLTNode* del = pos->next;
	//pos->next = pos->next->next;
	//free(del);
	//del = NULL;
 
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}