亲宝软件园·资讯

展开

C++ 单链表

雪芙花 人气:0

单链表的实现(从入门到熟练)

概念和结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构

数据元素的逻辑顺序是通过链表中的指针链 接次序实现的

图示:

image-20220318195224112

注意:

链表结构在逻辑上为连续的,但是物理上(内存中)不一定连续

链表节点都是在堆上申请出来的,申请空间按一定策略分配

结构种类

链表具有多种结构:单向\双向,带头\不带头,循环\非循环

实际上最常用的是:无头单向非循环链表,带头双向循环链表

链表的实现

注意:这里实现的是无头单向非循环链表

增删查改接口

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

节点结构体创建

typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next; 
}SListNode;

节点开辟

对于链表来说,每需要空间就需要进行开辟,这里我们将之封装成一个函数,便于后续调用直接使用(开辟的同时进行赋值)

参考代码:

//链表节点开辟
SLTNode* BuySListNode(SLTDateType x)
{
	//动态分配一个节点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		//分配失败则打印错误信息并结束进程
		perror("newnode fail:");
		exit(-1);
	}
	//成功则进行赋值
	newnode->data = x;
	newnode->next = NULL;
	//返回节点地址,以便后续操作
	return newnode;
}

数据打印

注意:

1.对于不带头的链表来说,打印数据不需要修改链表首节点地址(故只要传链表指针)

2.用循环遍历链表,每打印数据,需要指向下一个节点

3.依靠尾节点的址域为NULL来结束循环

代码:

//链表数据打印
void SListPrint(SLTNode* phead)//一级指针接收一级指针(打印不需改变指针本身内容)
{
	//创建一个寻址指针
	SLTNode* cur = phead;
	while (cur!=NULL)//后续还有节点
	{
		//打印数据并指向下一个节点
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//最后打印空指针
	printf("NULL\n");
	return;
}

链表尾插数据

代码:

//链表尾插数据
void SListPushBack(SLTNode** pphead, SLTDateType x)//二级指针接收一级指针(尾插存在需改变链表指针本身内容)
{
	//避免传入错误(直接报错便于找到错误位置)
	assert(pphead);
	//接收新节点的地址
	SLTNode* newnode=BuySListNode(x);
	//头节点为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾节点
		SLTNode* tail = *pphead;//创建寻址节点
		//两个及以上节点的情况
		while (tail->next != NULL)
		{
			//指向下一个节点
			tail = tail->next;	
		}
		//找到了
		tail->next = newnode;
	}
	return;
}

注意代码中的assert的作用:

头删

注意:

代码:

//链表前删数据
void SListPopFront(SLTNode** pphead)
{
	//避免传入错误(直接报错便于找到错误位置)
	assert(pphead);
	//链表为空的情况
	if (*pphead == NULL)
	{
		return;
	}
	//创建指针保存第二个节点地址
	SLTNode* next = (*pphead)->next;
	//释放当前头结点空间
	free(*pphead);
	//更新头结点数据
	*pphead = next;
	return;
}

链表数据查找

注意:

代码:

//链表数据查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	//创建寻址指针
	SLTNode* cur = phead;
	while (cur!=NULL)
	{
		if (cur->data == x)//找到数据符合节点
		{
			return cur;//返回节点地址(好处:以便后续再寻找或修改)
		}
		else
		{
			//找下一个节点
			cur = cur->next;
		}
	}
	//未找到数据符合节点
	return NULL;
}

链表pos位置前插数据

注意:

代码:

//链表pos位置往前插入(较难)(还有在pos位置之后插入,简单点)
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	//避免传入错误(直接报错便于找到错误位置)
	assert(pphead);
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	//首结点符合的情况
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		//创建寻址指针
		SLTNode* cur = *pphead;
		while (cur !=NULL)
		{
			if (cur->next!= pos)
			{
				cur = cur->next;//找到下一节点
			}
			else // 找到对应空间
			{
				cur->next = newnode;
				newnode->next = pos;
				return;//结束寻找(否则会一直插入,造成死循环)
			}
		}
	}
	//未找到则什么也不干
	return;
}

链表pos位置后插数据

注意:

ps:一定要注意修改链接节点址域的先后,避免地址的丢失

代码:

//链表pos位置往后插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
	return;
}

链表pos位置数据删除

注意:

参考代码:

//链表pos位置删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//避免传入错误(直接报错便于找到错误位置)
	assert(pphead);
	assert(pos);
	//头结点符合的情况
	if (*pphead == pos)
	{
		*pphead = (*pphead)->next;
		free(pos);
	}
	else
	{
		//创建寻址指针
		SLTNode* cur = *pphead;
		while (cur != NULL)
		{
			if (cur->next != pos)
			{
				cur = cur->next;//找到下一节点
			}
			else // 找到对应空间
			{
				SLTNode* next = cur->next->next;
				free(cur->next);
				cur->next = next;
				return;//结束寻找
			}
		}
	}
	//未找到则什么也不干
	return;
}

链表节点释放

注意:

参考代码:

//链表节点释放
void SListDestory(SLTNode** pphead)
{
	//避免传入错误(直接报错便于找到错误位置)
	assert(pphead);
	//遍历释放
	SLTNode* cur = *pphead;
	while (cur)
	{
		//保存下一个地址
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//置空
	*pphead = NULL;
	return;
}

链表与顺序表区别

链表的优缺点

优点

缺点

顺序表的优缺点

优点

缺点

加载全部内容

相关教程
猜你喜欢
用户评论