数据结构：单链表增、删、查、改的实现1.概念2.形式 3.实现步骤 4.完整代码 5.总结

Posted on by hackdl

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("NULLn");
}

 

        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
#include
#include
#include

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("NULLn");
}

// 单链表尾插
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.总结

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

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

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

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: