您现在的位置是：首页 >其他 >数据结构：单链表增、删、查、改的实现网站首页其他

数据结构：单链表增、删、查、改的实现

元清加油 2024-06-17 06:01:02
简介数据结构：单链表增、删、查、改的实现

1.概念

链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表
中的 指针链接 次序实现的 。

2.形式 

我们使用链表一般都是创建一个结构体。

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

 

3.实现步骤 

        3.1动态申请一个结点

// 动态申请一个结点
SLTNode* BuyLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

        3.2 单链表打印

// 单链表打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL
");
}

 

        3.3单链表尾插和头插

// 单链表尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
	//assert(*pphead); // 链表为空，可以尾插

	SLTNode* newnode = BuyLTNode(x);

	// 1、空链表
	// 2、非空链表
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

// 单链表的头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);  // 链表为空，pphead也不为空，因为他是头指针plist的地址
	//assert(*pphead); // 不能断言，链表为空，也需要能插入
	SLTNode* newnode = BuyLTNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

 

        3.4单链表尾删和头删

// 单链表的头删
void SLPopFront(SLTNode** pphead)
{
	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
	assert(*pphead); // 链表为空，不能头删。

	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);

}

// 单链表的尾删
void SLPopBack(SLTNode** pphead)
{
	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
	assert(*pphead); // 链表为空，不能头删

	// 没有节点(空链表)

	// 暴力检查
	//assert(*pphead);

	// 一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		// 多个节点
		SLTNode* tail = *pphead;
		// 找尾
		while (tail->next->next)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

 

        3.5单链表查找

// 单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{

	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

 

        3.6 在pos之前插入和之后插入

// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//assert(*pphead);

	if (*pphead == pos)
	{
		SLPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

// 在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

        3.7删除pos位置的值和pos位置之后的值

// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
	}
}

// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

 

4.完整代码 

        4.1  SList.h

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>

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

// 动态申请一个结点
SLTNode* BuyLTNode(SLTDataType x);

// 单链表打印
void SLTPrint(SLTNode* phead);

// 单链表的头插
void SLPushFront(SLTNode** pphead, SLTDataType x);

// 单链表尾插
void SLPushBack(SLTNode** pphead, SLTDataType x);

// 单链表头删
void SLPopFront(SLTNode** pphead);

// 单链表的尾删
void SLPopBack(SLTNode** pphead);

// 单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x);

// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

// 在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);

// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);

// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos);

          4.1  SList.c

#include"SList.h"

// 动态申请一个结点
SLTNode* BuyLTNode(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 SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL
");
}

// 单链表尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
	//assert(*pphead); // 链表为空，可以尾插

	SLTNode* newnode = BuyLTNode(x);

	// 1、空链表
	// 2、非空链表
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

// 单链表的头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);  // 链表为空，pphead也不为空，因为他是头指针plist的地址
	//assert(*pphead); // 不能断言，链表为空，也需要能插入
	SLTNode* newnode = BuyLTNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

// 单链表的头删
void SLPopFront(SLTNode** pphead)
{
	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
	assert(*pphead); // 链表为空，不能头删。（当然你还可以用温柔的检查）

	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);

}

// 单链表的尾删
void SLPopBack(SLTNode** pphead)
{
	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
	assert(*pphead); // 链表为空，不能头删

	// 没有节点(空链表)

	// 暴力检查
	//assert(*pphead);

	// 一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		// 多个节点
		SLTNode* tail = *pphead;
		// 找尾
		while (tail->next->next)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

// 单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
	//assert(phead);

	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//assert(*pphead);

	if (*pphead == pos)
	{
		SLPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

// 在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
	}
}

// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

5.总结

我们上次说的顺序表的问题，用链表就可以很好的解决

但是链表也有不足顺序表的地方，例如顺序表可以使用下标很快的访问数据，链表则不可。

所以我们要具体内容具体分析，来用哪一个

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐