C语言数据结构——链表

(图像由AI生成) 

0.前言

在计算机科学中,数据结构是存储和组织数据的一种方式,它不仅影响数据的存储,也影响数据的检索和更新效率。C语言,作为一种经典的编程语言,提供了灵活的方式来处理数据结构,其中链表是最基本且重要的一种。

1.链表的概念及结构

1.1概念

链表(Linked List)是一种在物理上非连续、非顺序的数据结构,由一系列节点(Node)组成。链表的每个节点由两部分构成:一是存储数据元素的数据域,二是存储下一个节点地址的指针域。这种结构允许在不重新整理整个数据结构的情况下,有效地插入和删除节点。

1.2结构特点

  1. 动态存储管理:链表的大小不是在编译时确定的,而是在运行时通过申请内存来构建的,这意味着它可以根据需要动态地扩展或缩减。
  2. 节点构成:链表的每个节点通常是一个对象或结构体,包含至少两个元素:
    • 数据域:存储数据值。
    • 指针域:指向列表中下一个节点的指针。
  3. 头指针:链表通过一个外部引用(通常是一个指针)来访问,这个引用指向链表的第一个节点,称为头指针。如果链表为空,头指针指向NULL。
  4. 尾节点:链表的最后一个节点指向NULL,这标志着链表的结束。

1.3链表与数组的比较

  • 存储分配:数组在内存中占用连续空间,而链表由一系列非连续的节点组成。
  • 大小灵活性:数组的大小在定义时固定,而链表的大小可以动态变化。
  • 内存利用:链表可以更有效地管理内存,因为它只需要根据实际需要分配内存。
  • 插入和删除效率:在链表中插入或删除节点通常更快,因为不需要移动其他元素(除非是数组实现的链表)。

2.链表的分类

按照单双向性、是否循环、以及是否带头节点,链表可以被分为以下八种主要类型:

  1. 单向不循环不带头链表

    • 特点:最基本的链表形式,每个节点只有一个指向下一个节点的指针,尾节点指向NULL,不含额外的头节点。
    • 用途:简单的数据存储和遍历操作。
  2. 单向不循环带头链表

    • 特点:类似于基本的单向链表,但增加了一个不存储实际数据的头节点,头节点的指针指向第一个实际数据节点。
    • 用途:简化某些链表操作,特别是插入和删除操作。
  3. 单向循环不带头链表

    • 特点:单向链表的尾节点指向链表的第一个节点,形成一个闭环。
    • 用途:适用于需要循环访问数据的场景。
  4. 单向循环带头链表

    • 特点:单向循环链表,但有一个额外的头节点,头节点的指针指向第一个实际数据节点。
    • 用途:循环链表操作的简化,尤其在处理循环链表的起始和终止条件时。
  5. 双向不循环不带头链表

    • 特点:每个节点有两个指针,分别指向前一个和后一个节点,尾节点的后向指针指向NULL,没有头节点。
    • 用途:方便的双向遍历,易于节点的前后插入和删除。
  6. 双向不循环带头链表

    • 特点:双向链表加上一个头节点,头节点的前向指针通常指向NULL,后向指针指向第一个实际节点。
    • 用途:简化插入、删除操作,尤其是在链表头部的操作。
  7. 双向循环不带头链表

    • 特点:双向链表中的尾节点指向第一个节点,第一个节点的前向指针指向尾节点,形成一个双向闭环,不含头节点。
    • 用途:复杂的双向循环遍历,常用于需要频繁正反向操作的场景。
  8. 双向循环带头链表

    • 特点:在双向循环链表的基础上增加了头节点,头节点的前向指针指向尾节点,后向指针指向第一个实际节点。
    • 用途:在需要循环遍历的同时,简化链表头部和尾部的操作。

在深入探讨链表的不同分类后,我们将先集中讨论单链表的实现与操作。单链表,作为链表家族中最简单的成员,提供了对链表基本概念的清晰理解。我们将详细介绍单链表(单向不带头不循环链表)的实现方法和各种操作函数。

3.单链表(单向不带头不循环链表)

单链表是一种基础的数据结构,由一系列节点(Node)组成。每个节点包含一个数据域和一个指向下一个节点的指针域。

3.1单链表的实现

我们先来看一下单向不带头不循环链表的具体实现,包括3个文件:头文件SList.h、源文件SList.c和test.c.

//SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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

//打印
void SLTPrint(SLTNode* phead);
//获取新节点
SLTNode* BuyNewNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos);
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在pos位置之前插入x
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//销毁
void SLTDestroy(SLTNode** pphead);



//SList.c
#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

//打印
void SLTPrint(SLTNode* phead)
{
	//assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//获取新节点
SLTNode* BuyNewNode(SLTDataType x)
{
	SLTNode* pnewnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (pnewnode == NULL)
	{
		assert(0);
		return NULL;
	}
	pnewnode->data = x;
	pnewnode->next = NULL;
	return pnewnode;

}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* pnewnode = BuyNewNode(x);
	if (*pphead == NULL)
	{
		*pphead = pnewnode;
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next != NULL)
		{
			pcur = pcur->next;
		}
		pcur->next = pnewnode;
	}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* pnewnode = BuyNewNode(x);
	if (*pphead == NULL)
	{
		*pphead = pnewnode;
	}
	else
	{
		pnewnode->next = *pphead;
		*pphead = pnewnode;
	}
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	//链表为空
	if (*pphead == NULL)
	{
		return;
	}
	//链表只有一个节点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//链表有多个节点
	else
	{
		while (pcur->next->next != NULL)
		{
			pcur = pcur->next;
		}
		free(pcur->next);
		pcur->next = NULL;
	}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	if (pcur == NULL)
	{
		return;
	}
	else
	{
		*pphead = pcur->next;
		free(pcur);
	}
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没找到
	return NULL;
}
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* pnewnode = BuyNewNode(x);
	pnewnode->next = pos->next;
	pos->next = pnewnode;

}
//删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	SLTNode* pcur = pos->next;
	//pos之后没有节点
	if (pcur == NULL)
	{
		return;
	}
	//pos之后有节点
	else
	{
		pos->next = pcur->next;
		free(pcur);
	}
}
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if(pos==*pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
	}
}
//在pos位置之前插入x
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);//链表不为空
	SLTNode* pnewnode = BuyNewNode(x);
	//pos为头节点
	if (*pphead == pos)
	{
	/*	pnewnode->next = *pphead;
		*pphead = pnewnode;*/
		SLTPushFront(pphead, x);
	}
	//pos不为头结点
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pnewnode->next = pos;
		pcur->next = pnewnode;
	}
}
//销毁
void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		*pphead = pcur->next;
		free(pcur);
		pcur = *pphead;
	}
}



//test.c
#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

void SListTest01()
{
	printf("SListTest01()\n");
	SLTNode* node1 = BuyNewNode(1);
	SLTPushBack(&node1, 2);
	SLTPushBack(&node1, 3);
	SLTPushBack(&node1, 4);
	SLTPushBack(&node1, 5);
	SLTPrint(node1);
	SLTPushFront(&node1, 0);
	SLTPrint(node1);
	SLTNode* ToFind = SLTFind(node1, 0);
	if(ToFind)
	{
		printf("Find it!\n");
	}
	else
	{
		printf("Not Find!\n");
	}
	SLTInsertAfter(ToFind, 500);
	SLTPrint(node1);
	SLTInsertBefore(&node1, ToFind, 100);
	SLTPrint(node1);
	SLTErase(&node1, ToFind);
	SLTPrint(node1);
}
void SListTest02()
{
	printf("SListTest02()\n");
	SLTNode* node1 = BuyNewNode(1);
	SLTPushBack(&node1, 2);
	SLTPushBack(&node1, 3);
	SLTPushBack(&node1, 4);
	SLTPushBack(&node1, 5);
	SLTPrint(node1);
	SLTPopBack(&node1);
	SLTPrint(node1);
	SLTPopFront(&node1);
	SLTPrint(node1);
	SLTNode* ToFind = SLTFind(node1, 3);
	SLTEraseAfter(ToFind);
	SLTPrint(node1);
	SLTDestroy(&node1);
	SLTPrint(node1);

}
int main()
{
	SListTest01();
	SListTest02();
	return 0;
}

3.2单链表函数详解

在单链表的实现中,以下是关键的数据类型定义和各个函数的实现原理与作用:

3.2.1数据类型定义
  1. typedef int SLTDataType;

    • 定义 SLTDataType 作为链表节点存储的数据类型,这里设为整型(int)。
  2. typedef struct SListNode { SLTDataType data; struct SListNode* next; } SLTNode;

    • 定义单链表的节点结构 SLTNode,包含数据(data)和指向下一个节点的指针(next)。
3.3.2函数详解
  1. 打印链表(SLTPrint

    • 参数:头节点指针 phead
    • 功能:遍历链表,打印每个节点的数据值。
    • 实现:使用循环遍历链表,直到遇到 NULL 结束。
  2. 获取新节点(BuyNewNode

    • 参数:节点数据 x
    • 功能:创建并返回一个新的链表节点。
    • 实现:分配内存,初始化数据和指针。
  3. 尾插(SLTPushBack

    • 参数:头节点指针的指针 pphead,节点数据 x
    • 功能:在链表尾部插入一个新节点。
    • 实现:找到链表的最后一个节点,将其 next 指向新节点。
  4. 头插(SLTPushFront

    • 参数:头节点指针的指针 pphead,节点数据 x
    • 功能:在链表头部插入一个新节点。
    • 实现:新节点的 next 指向原头节点,然后更新头节点。
  5. 尾删(SLTPopBack

    • 参数:头节点指针的指针 pphead
    • 功能:删除链表的最后一个节点。
    • 实现:找到倒数第二个节点,将其 next 设置为 NULL
  6. 头删(SLTPopFront

    • 参数:头节点指针的指针 pphead
    • 功能:删除链表的第一个节点。
    • 实现:将头节点指针更新为第二个节点。
  7. 查找(SLTFind

    • 参数:头节点指针 phead,要查找的数据 x
    • 功能:查找链表中数据为 x 的节点。
    • 实现:遍历链表,比较节点数据。
  8. 指定位置后插入(SLTInsertAfter

    • 参数:目标节点指针 pos,节点数据 x
    • 功能:在指定节点之后插入新节点。
    • 实现:新节点的 next 指向 posnext,然后 posnext 指向新节点。
  9. 指定位置后删除(SLTEraseAfter

    • 参数:目标节点指针 pos
    • 功能:删除指定节点之后的节点。
    • 实现:将 posnext 指向要删除节点的 next
  10. 指定位置删除(SLTErase

    • 参数:头节点指针的指针 pphead,要删除的节点指针 pos
    • 功能:删除指定的节点。
    • 实现:找到 pos 的前一个节点,更新其 next 指针。
  11. 指定位置前插入(SLTInsertBefore

    • 参数:头节点指针的指针 pphead,目标节点指针 pos,节点数据 x
    • 功能:在指定节点之前插入新节点。
    • 实现:遍历链表找到 pos 的前一个节点,执行插入操作。
  12. 销毁链表(SLTDestroy

    • 参数:头节点指针的指针 pphead
    • 功能:销毁整个链表,释放所有节点。
    • 实现:遍历链表,释放每个节点的内存。
3.2.3test.c运行结果

继单链表之后,我们将转向更为复杂的双向链表。双向链表(双向带头循环链表)不仅在节点结构上比单链表复杂,其操作也更为多样。通过比较这两种链表类型,我们可以更好地理解链表作为一种数据结构的灵活性和多功能性。

4.双向链表(双向带头循环链表)

双向链表是一种常见的线性数据结构,与单链表不同,它每个节点有两个指针域,一个指向前一个节点,一个指向后一个节点,因此可以从前往后或从后往前遍历链表。本文将详细介绍双向带头循环链表的实现以及双向链表的各种常用操作函数。

4.1双向链表的实现

我们先来看一下双向带头循环链表的具体实现,包括3个文件:头文件List.h、源文件List.c和test.c.

//List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

void LTPrint(LTNode* phead);//打印
void LTInit(LTNode** pphead);//初始化(通过传参)
LTNode* LTInit2();//初始化(通过返回值)
void LTDestroy(LTNode** pphead);//销毁
LTNode* BuyLTNode(LTDataType x);//创建新节点
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsertBefore(LTNode* pos, LTDataType x);//在pos位置之前插入x
void LTInsertAfter(LTNode* pos, LTDataType x);//在pos位置之后插入x
void LTRemove(LTNode* pos);//删除pos位置的节点
void LTCheckNode(LTNode* phead);//打印有效节点个数



//List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("head->");
	while(cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
//初始化(通过传参的方式)
void LTInit(LTNode** pphead)
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	if(*pphead == NULL)
	{
		assert(0);
		return;
	}
	(*pphead)->data = -1;
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}
//初始化(通过返回值的方式)
LTNode* LTInit2()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if(phead == NULL)
	{
		assert(0);
		return NULL;
	}
	phead->data = -1;
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//销毁
void LTDestroy(LTNode** pphead)
{
	LTNode* cur = (*pphead)->next;
	while(cur != *pphead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(*pphead);
	*pphead = NULL;
}
//创建新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if(newnode == NULL)
	{
		assert(0);
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* ptail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	newnode->next = phead;
	newnode->prev = ptail;
	ptail->next = newnode;
	phead->prev = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* ptail = phead->prev;
	if(ptail == phead)
	{
		return;
	}
	LTNode* prev = ptail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(ptail);
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* next = phead->next;
	newnode->next = next;
	newnode->prev = phead;
	next->prev = newnode;
	phead->next = newnode;

}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* next = phead->next;
	if(next == phead)
	{
		return;
	}
	LTNode* nextnext = next->next;
	phead->next = nextnext;
	nextnext->prev = phead;
	free(next);

}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while(cur != phead)
	{
		if(cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;

}
//在pos位置之前插入x
void LTInsertBefore(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	newnode->next = pos;
	newnode->prev = prev;
	prev->next = newnode;
	pos->prev = newnode;
}
//在pos位置之后插入x
void LTInsertAfter(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* next = pos->next;
	LTNode* newnode = BuyLTNode(x);
	newnode->next = next;
	newnode->prev = pos;
	next->prev = newnode;
	pos->next = newnode;
}
//删除pos位置的节点
void LTRemove(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
//打印有效节点个数
void LTCheckNode(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	int count = 0;
	while(cur != phead)
	{
		count++;
		cur = cur->next;
	}
	printf("有效节点个数为:%d\n", count);
}



//test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test01()
{
	printf("test01()\n");
	LTNode* plist = NULL;
	LTInit(&plist);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
}
void test02()
{
	printf("test02()\n");
	LTNode* plist = LTInit2();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTNode* toFind = LTFind(plist, 2);
	if (toFind)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}
	LTInsertAfter(toFind, 5);
	LTInsertBefore(toFind, 6);
	LTPrint(plist);
	LTRemove(toFind);
	LTPrint(plist);
	LTCheckNode(plist);
}
int main()
{
	test01();
	test02();
	return 0;
}

4.2双向链表函数详解

4.2.1数据类型定义

在双向链表的实现中,我们使用了以下数据类型的定义:

typedef int LTDataType;
typedef struct ListNode {
    LTDataType data;
    struct ListNode* prev;
    struct ListNode* next;
} LTNode;
  • LTDataType:链表节点存储的数据类型,这里使用整数作为示例。
  • LTNode:链表节点的结构体,包含数据域 data,前驱指针 prev 和后继指针 next。这三个部分组成了链表节点的基本结构。
4.2.2 函数详解

以下是双向链表实现中的各个函数的详细介绍:

1. 初始化链表

void LTInit(LTNode** pphead);
  • 参数:头节点指针的指针 pphead
  • 功能:初始化链表,创建一个头节点,使其 nextprev 指向自身,形成循环链表。这个函数用于链表的初始化操作。

2. 创建新节点

LTNode* BuyLTNode(LTDataType x);
  • 参数:节点存储的数据 x
  • 返回值:新节点的指针。
  • 功能:创建一个新节点,为其分配内存并设置数据域为 x,前驱和后继指针为空。这个函数用于创建待插入的新节点。

3. 插入节点到尾部

void LTPushBack(LTNode* phead, LTDataType x);
  • 参数:头节点指针 phead,要插入的数据 x
  • 功能:在双向链表的尾部插入一个新节点,更新尾节点的指针。这个函数用于在链表尾部添加新元素。

4. 删除尾部节点

void LTPopBack(LTNode* phead);
  • 参数:头节点指针 phead
  • 功能:删除双向链表的尾部节点,更新尾节点的指针,并释放内存。这个函数用于删除链表尾部的元素。

5. 插入节点到头部

void LTPushFront(LTNode* phead, LTDataType x);
  • 参数:头节点指针 phead,要插入的数据 x
  • 功能:在双向链表的头部插入一个新节点,更新头节点的指针。这个函数用于在链表头部添加新元素。

6. 删除头部节点

void LTPopFront(LTNode* phead);
  • 参数:头节点指针 phead
  • 功能:删除双向链表的头部节点,更新头节点的指针,并释放内存。这个函数用于删除链表头部的元素。

7. 查找节点

LTNode* LTFind(LTNode* phead, LTDataType x);
  • 参数:头节点指针 phead,要查找的数据 x
  • 返回值:找到的节点的指针,如果未找到则返回 NULL
  • 功能:在双向链表中查找存储特定数据 x 的节点。这个函数用于查找链表中的元素。

8. 在指定节点之前插入新节点

void LTInsertBefore(LTNode* pos, LTDataType x);
  • 参数:要插入的位置节点 pos,要插入的数据 x
  • 功能:在双向链表中的指定节点 pos 之前插入一个新节点,更新前驱和后继节点的指针。这个函数用于在指定位置之前

9. 在指定节点之后插入新节点

void LTInsertAfter(LTNode* pos, LTDataType x);
  • 参数:要插入的位置节点 pos,要插入的数据 x
  • 功能:在双向链表中的指定节点 pos 之后插入一个新节点,更新前驱和后继节点的指针。这个函数用于在指定位置之后插入新元素。

10. 删除指定节点

void LTRemove(LTNode* pos);
  • 参数:要删除的节点 pos
  • 功能:从双向链表中删除指定节点 pos,更新前驱和后继节点的指针,并释放内存。这个函数用于删除链表中的特定元素。
4.2.3test.c运行结果

5.结语

在本篇博客中,我们详细介绍了C语言中的链表数据结构,包括单向链表和双向链表。我们从链表的基本概念和结构开始,然后分别讨论了不同类型的链表,包括单向不带头不循环链表和双向带头循环链表。通过学习链表的实现和操作,我们可以更好地理解数据结构和算法的基本原理,为编程和问题解决提供强大的工具。希望本篇博客能够帮助你更深入地理解链表,并在编程中应用它们。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/354675.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

OkHttp完全解读

一&#xff0c;概述 OkHttp作为android非常流行的网络框架&#xff0c;笔者认为有必要剖析此框架实现原理&#xff0c;抽取并理解此框架优秀的设计模式。OkHttp有几个重要的作用&#xff0c;如桥接、缓存、连接复用等&#xff0c;本文笔者将从使用出发&#xff0c;解读源码&am…

iOS 文件分割保存加密

demo只是验证想法&#xff0c;没有做很多异常处理 默认文件是大于1KB的&#xff0c;对于小于1KB的没有做异常处理demo中文件只能分割成2个&#xff0c;可以做成可配置的N个文件分割拼接还可以使用固定的二进制数据&#xff0c;拼接文件开头或结尾 不论哪种拼法&#xff0c;目的…

牛客周赛30

思路&#xff1a;先把x, y除以最大公约数变成最小值&#xff0c;然后同时乘以倍数cnt&#xff0c;只记录两个数都在[l,r]间的倍数。 代码&#xff1a; int gcd(int a,int b){return b ? gcd(b, a % b) : a; }void solve(){int x, y, l, r;cin >> x >> y >>…

两两交换链表中的结点---链表OJ

https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked 1、递归 创建newhead = head->next,然后将head->next->next作为递归参数,返回值用head->next接收;递归结束条件是:没有结点或者只有一…

Python代码耗时统计

time模块 在代码执行前后各记录一个时间点&#xff0c;两个时间戳相减即程序运行耗时。这种方式虽然简单&#xff0c;但使用起来比较麻烦。 time.time() 函数返回的时间是相对于1970年1月1日的秒数 import timestart time.time() time.sleep(1) end time.time() print(f&…

洛谷 P2150 [NOI2015] 寿司晚宴

P2150 [NOI2015] 寿司晚宴 约定&#xff1a; n ≤ 500 n \leq 500 n≤500 题意 给定 2 → n 2 \rightarrow n 2→n 共 n − 1 n-1 n−1 个数字&#xff0c;现在两个人想分别取一些数字&#xff08;不一定全取完&#xff09;&#xff0c;如果他们两人取的数字中存在&#xf…

05. java线程基础

05. java线程基础 01. 线程相关概念 1. 程序 ​ 是为完成特定任务、用某种语言编写的一组指令的集合。简单来说&#xff1a;就是我们写的代码 2. 进程 进程是指运行中的程序&#xff0c;比如我们使用微信&#xff0c;就启动了一个进程&#xff0c;操作系统会为该进程分配内…

【代码随想录】LC 242. 有效的字母异位词

文章目录 前言一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 前言 本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记&#xff0c;如有侵权&#xff0c;立即删除。 一、题目 1、原题链接 242. 有效的字母异位词 2、题目描述 二、解题…

一文理清楚-Docker 容器如何工作

Docker 容器如何工作 集装箱什么是虚拟机&#xff1f;虚拟化如何运作&#xff1f;什么是容器&#xff1f;什么是 Docker&#xff1f;总结 五星上将麦克阿瑟曾经说过&#xff1a;在docker面前&#xff0c;虚拟机就是个弟弟 集装箱 《盒子&#xff1a;集装箱如何让世界变得更小&…

剑指offer——删除链表的节点

题目描述&#xff1a;给定单向链表的头指针和一个要删除的节点的值&#xff0c;定义一个函数删除该节点。返回删除后的链表的头节点。 数据范围&#xff1a; 0 <链表节点值 < 10000 0 <链表长度 < 10000 示例1&#xff1a; 输入&#xff1a;{2,5,1,9}&#xff…

1.28寒假集训

A: 解题思路&#xff1a; 移项就好v mv / (M - m) 下面是c代码&#xff1a; #include<iostream> using namespace std; int main() {int t;double M,m,v;cin >> t;while(t ! 0){cin >> M >> m >> v;printf("%.2lf\n",(m * v) / (M…

数据库之 基础概念、安装mysql、sql语句基础

数据库之 基础概念、安装mysql、sql语句基础 【一】存储数据的演变过程&#xff1a; 文件存储&#xff1a; 初始阶段随意存放数据到文件&#xff0c;格式任意。目录规范引入&#xff1a; 软件开发使用目录规范&#xff0c;限制数据位置&#xff0c;建立专门文件夹。本地数据存…

Linux报 “no route to host” 异常 ping: sendmsg: No route to host

公司有台服务器迁移机房后跟另一台服务器相互ping不通&#xff0c;但是两台服务器都能上网能ping其他机器&#xff0c;其他机器都能ping通这两台服务器。检查两台服务器没有防火墙规则拦截&#xff0c;交换机上也没检查到acl过滤。 下图是迁移机房的服务器ping截图 下图是nfs服…

分布式空间索引了解与扩展

目录 一、空间索引快速理解 &#xff08;一&#xff09;区域编码 &#xff08;二&#xff09;区域编码检索 &#xff08;三&#xff09;Geohash 编码 &#xff08;四&#xff09;RTree及其变体 二、业内方案选取 三、分布式空间索引架构 &#xff08;一&#xff09;PG数…

腾讯云幻兽帕鲁4核16G14M服务器性能测评和价格

腾讯云幻兽帕鲁服务器4核16G14M配置&#xff0c;14M公网带宽&#xff0c;限制2500GB月流量&#xff0c;系统盘为220GB SSD盘&#xff0c;优惠价格66元1个月&#xff0c;277元3个月&#xff0c;支持4到8个玩家畅玩&#xff0c;地域可选择上海/北京/成都/南京/广州&#xff0c;腾…

通讯录项目(终)

Start And Stick 上一期我们将通讯录的项目的基本功能已经实现&#xff0c;这一篇文章我们将对通讯录进行完善。 目录 Start And Stick 上期回顾&#xff1a; 上期必要代码&#xff1a; 数据打印&#xff1a; 代码讲解&#xff1a; 头部插入数据&#xff1a; 代码讲解&…

27.1K Star,优雅的JSON 数据可视化工具

Hi&#xff0c;骚年&#xff0c;我是大 G&#xff0c;公众号「GitHub指北」会推荐 GitHub 上有趣有用的项目&#xff0c;一分钟 get 一个优秀的开源项目&#xff0c;挖掘开源的价值&#xff0c;欢迎关注。 想自己之前做 APP 开发会访问后端数据&#xff0c;这个数据就是 JSON …

【网络基础】网络协议传输层UDP和TCP

UDP 解包和分用 解包&#xff08;解析数据包&#xff09; 捕获数据包&#xff1a;首先&#xff0c;接收端的网络栈捕获UDP数据包。检查目的端口&#xff1a;接收端检查数据包头部的目的端口&#xff0c;以确定哪个应用程序应该接收该数据包。验证校验和&#xff1a;接收端可能…

【排序5】基数排序:数字的组织与整理艺术

&#x1f3a1;基数排序 &#x1f38a;1、基本思想&#x1f38a;2、基本步骤&#x1f38a;3、代码示例&#x1f38a;4、特性总结 &#x1f38a;1、基本思想 基数排序&#xff08;Radix Sort&#xff09;是一种非比较排序算法&#xff0c;它根据数字的每一位来对元素进行排序。它…

2024年数学建模美赛C题(预测 Wordle)——思路、程序总结分享

1: 问题描述与要求 《纽约时报》要求您对本文件中的结果进行分析&#xff0c;以回答几个问题。 问题1&#xff1a;报告结果的数量每天都在变化。开发一个模型来解释这种变化&#xff0c;并使用您的模型为2023年3月1日报告的结果数量创建一个预测区间。这个词的任何属性是否会…