首页 > 其他分享 >链表（C 语言）

链表（C 语言）

时间：2024-11-07 13:18:55浏览次数：7  
标签：pphead ListNode 语言 next 链表 phead 节点

目录

一、链表的概念

链表是一种顺序表，它由一个一个的节点组成，该节点中存储着该节点的数据 val 和下一个结点的位置 next。最后一个节点的 next 指向NULL。

1. 链表的结构

链表的逻辑结构是连续的，但是物理结构通常是不连续的。因为在逻辑上，好像每个节点都是链接在一起的。
在这里插入图片描述
但是实际上，只是 next 存储了下一个结点的地址。
在这里插入图片描述

2. 链表的分类

链表通过是否带哨兵位头节点、是否循环还有单向和双向三个标准分为 8 种。

哨兵位头节点：不用来存储数据，仅占位，相当于一个站岗的士兵。有了它就不用判断是不是第一次插入数据。
在这里插入图片描述

循环：尾节点的 next 指向头节点，形成一个环。
在这里插入图片描述

双向：当前节点既有下一个节点的地址，也有上一个节点的地址。
在这里插入图片描述

3. 链表的优势

相比于顺序表，链表具有以下优势：
（1）不需要扩容，不会造成空间的浪费
因为链表插入数据时就申请一个节点，容量刚好。
（2）插入删除数据时不需要移动数据，只需要把新的节点链接进去或者把旧的节点解开释放即可。

二、链表的实现

不管是什么类型的链表，它的基本结构都是一个节点，该节点至少需要数据的值和下一个节点的地址两个成员。

不管是顺序表也好，链表也罢，无非就是增删查改。实现的功能都是一样的，只是使用的方法不同。

下面先实现一个最基本的无头单项非循环链表，然后再实现一个带头双向循环链表。当你完成第一个链表的实现再去看第二个链表时，你会觉得非常简单。等你这两个链表都能实现的时候，你会发现链表也就这样。

1. 无头单项非循环链表的实现

老样子，分成三个文件：头文件、方法实现文件和测试文件。

头文件：ListNode.h

// 头文件
#include <stdio.h>

// 无头单向非循环链表

// 类型声明
typedef int DataType;

// 节点结构声明
typedef struct ListNode
{
	DataType val;  // 数据
	struct ListNode* next;  // 下一个结点的位置
}ListNode;

// 方法

// 获得节点
ListNode* BuyNode(DataType data);

// 头插
void ListPushFront(ListNode** pphead, DataType data);

// 头删
void ListPopFront(ListNode** pphead);

// 尾插
void ListPushBack(ListNode** pphead, DataType data);

// 尾删
void ListPopBack(ListNode** pphead);

// 查找
ListNode* ListFind(ListNode** pphead, DataType data);

// 插入
void ListInsert(ListNode* pos, DataType data);

// 删除
void ListErase(ListNode* pos);

// 打印链表
void ListPrint(const ListNode** pphead);

// 销毁链表
void ListDestory(ListNode** pphead);

方法实现文件：ListNode.c

// 头文件
#include "ListNode.h"
#include <assert.h>
#include <stdlib.h>

// 方法

// 获得节点
ListNode* BuyNode(DataType data)
{
	// 申请节点
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == new_node)
	{
		perror("BuyNode::malloc: ");
		exit(-1);
	}
	// 赋值
	new_node->val = data;
	new_node->next = NULL;
	// 返回
	return new_node;
}

// 头插
void ListPushFront(ListNode** pphead, DataType data)
{
	assert(pphead);
	// 获得新节点
	ListNode* new_node = BuyNode(data);
	// 链接
	new_node->next = *pphead;
	*pphead = new_node;
}

// 头删
void ListPopFront(ListNode** pphead)
{
	assert(pphead);
	// 空表
	if (NULL == *pphead)
	{
		printf("Empty List!\n");
		exit(-1);
	}
	// 删除
	ListNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

// 尾插
void ListPushBack(ListNode** pphead, DataType data)
{
	assert(pphead);
	// 获得新节点
	ListNode* new_node = BuyNode(data);
	// 头插判断
	if (NULL == *pphead)
	{
		*pphead = new_node;
	}
	else  
	{
		// 找尾
		ListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		// 链接
		tail->next = new_node;
	}
}

// 尾删
void ListPopBack(ListNode** pphead)
{
	assert(pphead);
	// 空表
	if (NULL == *pphead)
	{
		printf("Empty List!\n");
		exit(-1);
	}
	// 头删判断
	if (NULL == (*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		// 找尾前节点
		ListNode* pre_tail = *pphead;
		while (pre_tail->next->next)
		{
			pre_tail = pre_tail->next;
		}
		// 释放尾
		free(pre_tail->next);
		// 新尾后置空
		pre_tail->next = NULL;
	}
}

// 查找
ListNode* ListFind(ListNode** pphead, DataType data)
{
	assert(pphead);
	ListNode* cur = *pphead;
	while (cur)
	{
		// 找到了
		if (cur->val == data)
			return cur;
		// 下一个
		cur = cur->next;
	}
	// 没找到
	return NULL;
}

// 插入
void ListInsert(ListNode* pos, DataType data)
{
	assert(pos);
	// 申请新节点
	ListNode* new_node = BuyNode(data);
	// 链接
	new_node->next = pos->next;
	pos->next = new_node;
}

// 删除
void ListErase(ListNode* pos)
{
	assert(pos);
	// 记录删除位
	ListNode* del = pos->next;
	// 链接
	pos->next = pos->next->next;
	// 删除
	free(del);
}

// 打印链表
void ListPrint(const ListNode** pphead)
{
	assert(pphead);
	// 打印
	const ListNode* cur = *pphead;
	while (cur)
	{
		printf("%d ", cur->val);
		// 下一个节点
		cur = cur->next;
	}
	printf("\n");
}

// 销毁链表
void ListDestory(ListNode** pphead)
{
	assert(pphead);
	// 销毁
	ListNode* cur = *pphead;
	while (cur)
	{
		// 存储下一个节点
		ListNode* next = cur->next;
		// 删除当前节点
		free(cur);
		// 下一个节点
		cur = next;
	}
	// 置空
	*pphead = NULL;
}

测试文件：test.c

// 头文件
#include "ListNode.h"

// 头插头删测试
void test1()
{
	ListNode* phead = NULL;
	// 头插
	int i = 0;
	for (i = 0; i < 5; ++i)
	{
		ListPushFront(&phead, i);
	}
	ListPrint(&phead);
	// 头删
	for (i = 0; i < 5; ++i)
	{
		ListPopFront(&phead);
		printf("头删 %d 次: ", i+1);
		ListPrint(&phead);
	}
	// 销毁链表
	ListDestory(&phead);
}

// 尾插尾删测试
void test2()
{
	ListNode* phead = NULL;
	// 尾插
	int i = 0;
	for (i = 0; i < 5; ++i)
	{
		ListPushBack(&phead, i);
	}
	ListPrint(&phead);
	// 尾删
	for (i = 0; i < 5; ++i)
	{
		ListPopBack(&phead);
		printf("尾删 %d 次: ", i+1);
		ListPrint(&phead);
	}
	// 销毁
	ListDestory(&phead);
}

// 插入删除查找测试
void test3()
{
	ListNode* phead = NULL;
	// 尾插
	int i;
	for (i = 1; i <= 5; ++i)
	{
		ListPushBack(&phead, i);
	}
	ListPrint(&phead);
	// 在每个数据后面插入 9
	for (i = 1; i <= 5; ++i)
	{
		// 找位置
		ListNode* pos = ListFind(&phead, i);
		// 在后面插入 9
		ListInsert(pos, 9);
	}
	ListPrint(&phead);
	// 删除 9
	for (i = 1; i <= 5; ++i)
	{
		// 找位置
		ListNode* pos = ListFind(&phead, i);
		// 在后面插入 9
		ListErase(pos);
	}
	ListPrint(&phead);
	// 销毁
	ListDestory(&phead);
}

int main()
{
	// 头插头删测试
	printf("头插头删测试:\n");
	test1();
	// 尾插尾删测试
	printf("\n\n尾插尾删测试:\n");
	test2();
	// 插入删除查找测试
	printf("\n\n插入删除查找测试:\n");
	test3();

	return 0;
}

程序测试结果：
在这里插入图片描述

1.1 代码说明

1. 为什么使用二级指针？
首先，只要是插入操作，当插入第一个节点的时候需要改变头节点的指向，那么只有传入头节点的指针才能改变它的值。删除也是一个道理，当删除最后一个节点时，需要把头节点置空，也需要二级指针。所以这里已经有六个函数需要传递二级指针了，那么干脆把所有函数都设计成传递二级指针，这样既方便又统一。

2. 为什么需要对 pphead 断言？
这里要知道 pphead 是什么，它是头节点指针的地址。这个头节点指针是一定存在的，所以它的地址一定不是 NULL。

3. 为什么 ListInsert() 和 ListErase() 都是在给定位置之后插入删除？
如果在给定位置之前进行插入删除，需要遍历链表，找到前一个位置，这样就消耗了时间。而在给定位置之后插入删除，只需要链接上或者断开链接释放即可。

4. 尾插尾删需要进行判断
尾插需要判断是否是第一次插入，因为第一次插入需要改变头节点的位置。若不是第一次插入就需要寻找尾节点，然后再进行插入。
尾删需要判断是否是最后一个节点，因为删除完最后一个节点需要把头节点置空。若不是最后一个节点，需要找到尾节点的前一个节点，然后进行删除。

2. 带头双向循环链表的实现

有了前面无头单项不循环链表的基础，现在来实现这个带头双向循环链表那就是 so easy！这个新链表的节点在原来的基础上增加了一个 pre 指针，指向前一个节点。由于哨兵位头节点初始状态 pre 和 next 都指向自己，所以该链表的头节点需要使用一个函数来初始化并返回。令人最兴奋的是，该表的尾插和尾删都不要判断，而且所有函数都可以只传一级指针。

头文件：ListNode.h

// 头文件
#include <stdio.h>

// 带头双向循环链表

// 类型声明
typedef int DataType;

// 链表节点声明
typedef struct ListNode
{
	DataType val;  // 数据
	struct ListNode* pre;  // 前一个节点的地址
	struct ListNode* next;  // 下一个节点的地址
}ListNode;

// 方法

// 获得哨兵位头节点
ListNode* ListCreate();

// 获得新节点
ListNode* BuyNode(DataType data);

// 头插
void ListPushFront(ListNode* phead, DataType data);

// 头删
void ListPopFront(ListNode* phead);

// 尾插
void ListPushBack(ListNode* phead, DataType data);

// 尾删
void ListPopBack(ListNode* phead);

// 插入
void ListInsert(ListNode* pos, DataType data);

// 删除
void ListErase(ListNode* pos);

// 打印
void ListPrint(const ListNode* phead);

// 查找
ListNode* ListFind(const ListNode* phead, DataType data);

// 销毁
void ListDestory(ListNode* phead);

方法实现文件：ListNode.c

// 头文件
#include "ListNode.h"
#include <stdlib.h>
#include <assert.h>

// 方法

// 获得哨兵位头节点
ListNode* ListCreate()
{
	// 申请新节点
	ListNode* phead = BuyNode(0);
	// 初始化
	phead->next = phead->pre = phead;
	phead->val = 0;
	// 返回
	return phead;
}

// 获得新节点
ListNode* BuyNode(DataType data)
{
	// 申请新节点
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == new_node)
	{
		perror("ListCreate::malloc: ");
		exit(-1);
	}
	// 初始化
	new_node->next = new_node->pre = NULL;
	new_node->val = data;
	// 返回
	return new_node;
}

// 头插
void ListPushFront(ListNode* phead, DataType data)
{
	assert(phead);
	// 获得新节点
	ListNode* new_node = BuyNode(data);
	// 前后链接
	ListNode* next = phead->next;
	new_node->next = next;
	next->pre = new_node;
	new_node->pre = phead;
	phead->next = new_node;
}

// 头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	// 空表
	if (phead->next == phead)
	{
		printf("Empty List!\n");
		exit(-1);
	}
	// 存储下一个节点
	ListNode* next = phead->next->next;
	// 删除头节点
	free(phead->next);
	next->pre = phead;
	phead->next = next;
}

// 尾插
void ListPushBack(ListNode* phead, DataType data)
{
	assert(phead);
	// 申请新节点
	ListNode* new_node = BuyNode(data);
	// 链接
	ListNode* tail = phead->pre;
	tail->next = new_node;
	new_node->pre = tail;
	new_node->next = phead;
	phead->pre = new_node;
}

// 尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	// 空表
	if (phead->next == phead)
	{
		printf("Empty List!\n");
		exit(-1);
	}
	// 存储尾前节点
	ListNode* new_tail = phead->pre->pre;
	free(phead->pre);
	new_tail->next = phead;
	phead->pre = new_tail;
}

// 插入
void ListInsert(ListNode* pos, DataType data)
{
	// 申请新节点
	ListNode* new_node = BuyNode(data);
	// 链接
	ListNode* pre = pos->pre;
	pre->next = new_node;
	new_node->pre = pre;
	new_node->next = pos;
	pos->pre = new_node;
}

// 删除
void ListErase(ListNode* pos)
{
	// 链接前后
	ListNode* pre = pos->pre;
	pre->next = pos->next;
	pos->next->pre = pre;
	// 释放当前结点
	free(pos);
}

// 打印
void ListPrint(const ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		// 下一个节点
		cur = cur->next;
	}
	printf("\n");
}

// 查找
ListNode* ListFind(const ListNode* phead, DataType data)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		// 找到了
		if (cur->val == data)
			return cur;
		// 下一个节点
		cur = cur->next;
	}
	// 没找到
	return NULL;
}

// 销毁
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		// 存储下一个节点
		ListNode* next = cur->next;
		// 删除当前节点
		free(cur);
		// 下一个节点
		cur = next;
	}
	// 释放哨兵位头节点
	free(phead);
}

测试文件：test.c

// 头文件
#include "ListNode.h"

// 头插头删测试
void test1()
{
	// 创建链表
	ListNode* phead = ListCreate();
	// 头插
	int i = 0;
	for (i = 0; i < 5; ++i)
	{
		ListPushFront(phead, i);
	}
	ListPrint(phead);
	// 头删
	for (i = 0; i < 5; ++i)
	{
		ListPopFront(phead);
		printf("头删 %d 次: ", i + 1);
		ListPrint(phead);
	}
	// 销毁
	ListDestory(phead);
	phead = NULL;
}

// 尾插尾删测试
void test2()
{
	ListNode* phead = ListCreate();
	// 尾插
	int i;
	for (i = 0; i < 5; ++i)
	{
		ListPushBack(phead, i);
	}
	ListPrint(phead);
	// 尾删
	for (i = 0; i < 5; ++i)
	{
		ListPopBack(phead);
		printf("尾删 %d 次: ", i+1);
		ListPrint(phead);
	}

	// 销毁
	ListDestory(phead);
	phead = NULL;
}

// 插入删除查找测试
void test3()
{
	// 创建链表
	ListNode* phead = ListCreate();
	// 尾插
	int i;
	for (i = 0; i < 5; ++i)
	{
		ListPushBack(phead, i);
	}
	ListPrint(phead);
	// 插入
	for (i = 0; i < 5; ++i)
	{
		ListNode* pos = ListFind(phead, i);
		ListInsert(pos, 9);
	}
	ListPrint(phead);
	// 删除
	for (i = 0; i < 5; ++i)
	{
		ListNode* pos = ListFind(phead, i);
		ListErase(pos);
	}
	ListPrint(phead);
	// 销毁
	ListDestory(phead);
	phead = NULL;
}

int main()
{
	 头插头删测试
	//test1();
	 尾插尾删测试
	//test2();
	// 插入删除查找测试
	test3();

	return 0;
}

程序测试结果：
在这里插入图片描述

2.1 代码说明

1. 所有函数都只传一级指针
因为有哨兵位头节点的存在，不管是增删查改哪个功能都只需要一级指针。只是销毁链表需要在外头置空。

2. 尾插和尾删不需要检查和找尾
即使表中没有数据节点，但是还存在哨兵位头节点。且它的前一个就是尾节点，不需要寻找。

3. ListInsert() 和 ListErase() 函数可以在当前位置之前进行操作
由于该链表是双向的，不需要遍历寻找前一个节点。所以可以删除当前位置的节点和在当前节点的前面插入节点。

三、链表和顺序表的区别

在这里插入图片描述
上面的图片是偷课件的，下面作者用自己的理解来说明一下：
（1）顺序表是使用数组实现的，在内存中的存储是连续的。而链表是通过申请一个个节点链接在一起的，物理上是不连续的（极低概率的就不要来抬杠了）。
（2）顺序表支持随机访问，时间复杂度为O(1)；而链表不支持随机访问，需要从头节点开始寻找，时间复杂度为O(N)。
（3）顺序表在插入元素的时候可能会触发增容，可能会造成空间浪费；链表没有增容这个说法，每次插入都申请一个新的节点，需要多少就申请多少，不存在浪费。
（4）顺序表在插入和删除元素时，时间复杂度最高为O(N)，最低为O(1)，分别对应头插头删和尾插尾删，平均时间复杂度为O(N)。而链表其实也和顺序表差不多，头插头删为O(1)，尾插尾删为O(N)，平均时间复杂度也是O(N)。但是由于顺序表存在增容，所以链表还是优于顺序表。
（5）顺序表的缓存利用率远高于链表。

关于缓存利用率这个概念，大家就只能自己下去了解一下了，我只能偷张图来帮助大家。
在这里插入图片描述

四、链表总结

其实在写完带头双向循环链表的时候，大家心中肯定在想，这个 3 层 buff 的表这么牛逼，为什么还要使用无头单项非循环链表。这是因为出面试题的时候使用的链表基本上是后者，如果给你前者，那么题目就会变得很简单。再者，无头单项非循环链表是一些复杂数据结构的子结构，一般不单独使用。

而带头双向循环链表可以根据使用场景来使用。

标签：pphead,ListNode,语言,next,链表,phead,节点
From： https://blog.csdn.net/weixin_70742989/article/details/143493747

相关文章

  • c语言中函数体中的变量声明不能使用和形参相同的变量名
     001、[root@PC1test]#lstest.c[root@PC1test]#cattest.c#include<stdio.h>intmax(inta,intb)//创建一个名为max的函数{intk=100;if(a>b){returna;}......
  • 【译】编程语言未来十年
    译注：最近逛Medium，发现了一篇对编程语言的的文章，作者有些观点值得学习，所以搬运过来翻译给博客园的观众们看看。原标题：最新的Tiobe指数对编程的未来有何展望？原文地址：https://medium.com/gitconnected/what-does-the-latest-tiobe-index-say-about-the-future-of-programming-c......
  • Go语言切片（Slice）的一些有趣特性
    切片类似数组的引用。更改底层数组中的元素会修改切片的元素。更改切片的元素同样会修改其底层数组中的元素，和它共享底层数组的切片都会观测到这些修改。点击查看代码packagemainimport"fmt"funcmain(){ names:=[4]string{ "John", "Paul", "George", "Ri......
  • 【C语言】实战-力扣题库：回文链表
    题目描述给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。提示：链表中节点数目在范围[1,105] 内0<=Node.val<=9进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？问题分析O(1)的时间复杂度---跟n......
  • 【C语言】分支和循环详解（下）猜数字游戏
    与诸君共进步！！！！！文章目录1.随机数的生成2.猜数字小游戏的实现1.随机数的生成掌握了前⾯学习的这些知识，我们就可以写⼀些稍微有趣的代码了，⽐如：写⼀个猜数字游戏游戏要求：电脑⾃动⽣成1~100的随机数玩家猜数字，猜数字的过程中，根据猜测数据的⼤⼩给出⼤了或⼩了的......
  • lanqiaoOJ 1110：小王子单链表 ← 数组模拟实现
     【题目来源】https://www.lanqiao.cn/problems/1110/learning/【题目描述】小王子有一天迷上了排队的游戏，桌子上有标号为1-10的10个玩具，现在小王子将他们排成一列，可小王子还是太小了，他不确定他到底想把哪个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排......
  • bert自然语言处理框架
    探索BERT：自然语言处理的新纪元在人工智能和自然语言处理（NLP）的浩瀚星空中，BERT（BidirectionalEncoderRepresentationsfromTransformers）无疑是近年来最耀眼的星辰之一。自2018年由GoogleAILanguage团队提出以来，BERT不仅重新定义了NLP任务的处理方式，还极大地推动了该领域的边......
  • C语言---文件操作万字详细分析（6）
    文件操作到这里，C语言所有知识点，就告已段落了，虽然知识点到这里结束了，但我想，我们的编程之路也可能刚刚开始，这些知识，是我们在创造伟大事物时，必不可少的基础，是我们未来财富自由之路，必不可少的垫脚之石。相信大家会变得越来越牛逼！不废话了，Let’sstart!一、文件指......
  • C语言数据结构--详细讲解算法复杂度
    C语言数据结构-算法复杂度前言一、时间复杂度1.大O渐进表示法2时间复杂度的计算二、空间复杂度1.什么是空间复杂度2时间复杂度的计算总结前言我们都清楚计算机存储和组织数据是通过数据结构来实现的。当计算机对这些数据结构中的数据进行遍历等操作时，这个过程就......
  • 2个月搞定计算机二级C语言——真题（9）解析
    1.前言本篇我们讲解2个月搞定计算机二级C语言——真题92.程序填空题2.1题目要求2.2提供的代码#include<stdio.h>doublef1(doublex){returnx*x;}doublef2(doublex,doubley){returnx*y;}/**********found**********/__1__fun(int......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99