初阶数据结构:链表

发布时间:2024年01月20日

1. 引子:什么是链表

经过学习与练习,已经掌握了顺序表的相关知识并且能够自我实现。在这一过程中,通过对其结构的实现,发现顺序表的尾部插入删除数据效率很高,可是,在头部与随机插入的场景下效率低下而且存在扩容消耗等一些问题。而有这样一种数据结构可以很好的解决顺序表存在的这些问题,将琐碎的系统空间充分利用,任意位置的插入删除效率都很高。此种数据结构称为链表,接下来进行对其的学习。

2. 简单数据结构:链表

2.1 链表简介与功能分析

简介:

链表,正如其名,存储其中的数据在物理上是离散的,各个数据间使用一条 “链子” 串联而成(记录下一元素地址的指针)。链表的具体结构存在数种,以是否带头是否能双向访问是否循环,这三个特点被简单分为六种,下面,我们先进行其中一种,带头单向不循环链表进行学习。

单向带头不循环链表结构图:
在这里插入图片描述

功能分析模块:

数据存储方式:

  1. 动态开辟malloc的一块块小内存块。
  2. 存储信息为数据值,与记录下一个结点的指针
    以上两点创建的结点结构体

数据管理方式:

  1. 增(头插,尾插,随机插入):push_front,push_back,insert,insertafter
  2. 删(头删,尾删,随机删除):pop_front,pop_back,erase,eraseafter
  3. 改(指定数据的修改):modify
  4. 查(指定数据的查询):find

2.2 单链表的实现

2.2.1 单链表:存储数据的结构体

链表结点的构建:

typedef int ListDataType;

typedef struct ListNode
{
	ListDataType val;
	//声明类型的过程中不能直接使用typedef后的名字
	struct ListNode* next;
}ListNode;

2.2.2 单链表:结点创建与链表数据清理

结点创建:

在这里插入图片描述

ListNode* BuyNewNode(ListDataType val)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	newnode->val = val;
	newnode->next = NULL;

	return newnode;
}

链表销毁:

过程演示:

在这里插入图片描述

//链表销毁
void ListDestroy(ListNode** PPhead)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;

	ListNode* cout = Phead;

	if (Phead != NULL)
	{
		while (Phead->next != NULL)
		{
			Phead = Phead->next;
			free(cout);
			cout = Phead;
		}

		free(Phead);

		*PPhead = NULL;
	}
}

注:Phead为list的一份值拷贝,因此要想能够改变list(链表头)的值,传参是我们应该采用二重指针传址传参。

在这里插入图片描述

2.2.2 单链表插入数据与删除

头插,头删:

头插过程演示:

链表为空时头插:
在这里插入图片描述

链表不为空时头插:
在这里插入图片描述

头删过程演示:

在这里插入图片描述

//头插
void ListPush_Front(ListNode** PPhead, ListDataType val)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;

	ListNode* newnode = BuyNewNode(val);

	if (Phead == NULL)
	{
		*PPhead = newnode;
	}
	else
	{
		ListNode* next = Phead;
		newnode->next = Phead;
		*PPhead = newnode;
	}
}


//头删
void ListPop_Front(ListNode** PPhead)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);

	ListNode* next = Phead->next;
	
	free(Phead);
	*PPhead = next;
}

尾插,尾删:

//尾插
void ListPush_Back(ListNode** PPhead, ListDataType val)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	
	ListNode* end_node = Phead;
	while (end_node != NULL && end_node->next != NULL)
	{
		end_node = end_node->next;
	}

	ListNode* newnode = BuyNewNode(val);
	if (end_node == NULL)
	{
		*PPhead = newnode;
	}
	else//end_node->next == NULL
	{
		end_node->next = newnode;
	}

}

//尾删
void ListPop_Back(ListNode** PPhead)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);

	ListNode* end_node = Phead;
	//特殊情况
	if (end_node->next == NULL)
	{
		free(end_node);
		*PPhead = NULL;
	}
	else//end_node->next != NULL
	{
		//逻辑短路
		while (end_node->next->next != NULL)
		{
			end_node = end_node->next;
		}

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

随机插入与删除:

在指定结点(pos)之前插入:

void ListInsert(ListNode** PPhead, ListNode* pos, ListDataType val)
{
	//不考虑结点不存在的情况
	//与ListFind模块配合使用
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);
	assert(pos);
	
	//复用头插
	if (pos == Phead)
	{
		ListPush_Front(PPhead, val);
	}
	else
	{
		ListNode* search = Phead;
		//寻找pos结点
		while (search->next != pos)
		{
			search = search->next;
		}
		
		//插入
		ListNode* newnode = BuyNewNode(val);
		ListNode* next = search->next;
		
		search->next = newnode;
		newnode->next = next;
	}
}

在指定结点(pos)之后插入:

void ListInsertAfter(ListNode* pos, ListDataType val)
{
	//结点不能为NULL
	assert(pos);

	ListNode* next = pos->next;

	ListNode* newnode = BuyNewNode(val);

	pos->next = newnode;
	newnode->next = next;
}

删除指定结点(pos)之后的结点:

void ListEraseAfter(ListNode* pos)
{
	assert(pos);
	assert(pos->next);

	ListNode* next = pos->next;
	pos->next = pos->next->next;

	free(next);

	next = NULL;

	pos->next = next;
}

删除指定结点(pos):

void ListErase(ListNode** PPhead, ListNode* pos)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);
	assert(pos);
	
	//头删
	if (pos == Phead)
	{
		ListPop_Front(PPhead);
	}
	else
	{
		ListNode* search = Phead;
		while (search->next != pos)
		{
			search = search->next;
		}

		ListNode* next = search->next->next;

		free(search->next);
		search->next = next;
	}
}

2.2.3 单链表查询与修改

元素查询:

ListNode* ListFind(ListNode** PPhead, ListDataType val)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);

	ListNode* search = Phead;
	while (search != NULL && search->val != val)
	{
		search = search->next;
	}

	return search;
}

数据修改:

void ListModify(ListNode* Node, ListDataType val)
{
	assert(Node);

	Node->val = val;
}

链表元素打印:

void ListPrint(ListNode* Phead)
{
	while (Phead != NULL)
	{
		printf("%d->", Phead->val);
		Phead = Phead->next;
	}
	printf("NULL\n");
}
文章来源:https://blog.csdn.net/qq_71806743/article/details/135681137
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。