C语言数据结构之链表

这篇具有很好参考价值的文章主要介绍了C语言数据结构之链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C语言数据结构之链表,C语言数据结构,数据结构,c语言,链表,后端,开发语言

C语言数据结构之链表,C语言数据结构,数据结构,c语言,链表,后端,开发语言

前言 \color{maroon}{前言} 前言

在上一篇博客中我们提到,线性表包括顺序表和链表,顺序表在上篇博客中已经介绍,本篇博客介绍一下另一种线性表——链表

1.链表的概念及结构

概念:链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

C语言数据结构之链表,C语言数据结构,数据结构,c语言,链表,后端,开发语言

  • 链表的结构跟⽕⻋⻋厢相似,淡季时⻋次的⻋厢会相应减少,旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉或者加上,不会影响其他⻋厢,每节⻋厢都是独⽴存在的。

  • ⻋厢是独⽴存在的,且每节⻋厢都有⻋⻔。想象⼀下这样的场景,假设每节⻋厢的⻋⻔都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾?

  • 最简单的做法:每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。

  • 在链表⾥,每节“⻋厢”是什么样的呢?

C语言数据结构之链表,C语言数据结构,数据结构,c语言,链表,后端,开发语言

  • 与顺序表不同的是,链表⾥的每节"⻋厢"都是独⽴申请下来的空间,我们称之为“结点/节点” (顺序表申请的空间是连续的,一次性申请下来的)

  • 节点的组成主要有两个部分:当前节点要保存的数据和保存下⼀个节点的地址(指针变量)。

  • 图中指针变量 plist 保存的是第⼀个节点的地址,我们称 plist 此时“指向”第⼀个节点,如果我们希望 plist “指向”第⼆个节点时,只需要修改 plist 保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下⼀个节点的位置?

链表中每个节点都是独⽴申请的(即需要插⼊数据时才去申请⼀块节点的空间),我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点

结合前⾯学到的结构体知识,我们可以给出每个节点对应的结构体代码:
假设当前保存的节点为整型:

struct ListNode
{
	int data;              //节点储存的数据
	struct ListNode* next; //指向节点的下一个节点
};
  • 当我们想要保存⼀个整型数据时,实际是向操作系统申请了⼀块内存,这个内存不仅要保存整型数据,也需要保存下⼀个节点的地址(当下⼀个节点为空时保存的地址为空)

  • 当我们想要从第⼀个节点⾛到最后⼀个节点时,只需要在前⼀个节点拿上下⼀个节点的地址(下⼀个节点的钥匙)就可以了。

我们以打印链表数据为例,看看是怎么拿到链表每一个数据的

C语言数据结构之链表,C语言数据结构,数据结构,c语言,链表,后端,开发语言

注意 : \color{red}{注意:} 注意:

1.链式机构在逻辑上是连续的,在物理结构上不⼀定连续

2.节点⼀般是从堆上申请的

3.从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续

2.链表的分类

链表的结构⾮常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构:

C语言数据结构之链表,C语言数据结构,数据结构,c语言,链表,后端,开发语言

虽然有这么多的链表的结构,但是我们实际中最常⽤还是两种结构:单链表和双向带头循环链表

1.⽆头单向⾮循环链表:结构简单,⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构,如哈希桶、图的邻接表等等。
2.带头双向循环链表:结构最复杂,⼀般⽤在单独存储数据。实际中使⽤的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使⽤代码实现以后会发现结构会带来很多优势,实现反⽽简单了,后⾯我们代码实现了就知道了。

3.无头单向非循环链表的实现

test.c

#include "Simple_List.h"

void menu()
{
	printf("******************************************\n");
	printf("***************   请选择   ***************\n");
	printf("******  1.PushFront     2.PushBack  ******\n");
	printf("******  3.Insert        4.PopFront  ******\n");
	printf("******  5.PopBack       6.Del       ******\n");
	printf("******  7.Modify        8.Print     ******\n");
	printf("******            0.Exit            ******\n");
	printf("******************************************\n");
}

int main()
{
	int pos = 0;
	int input = 0;
	int value = 0;

	ListNode* head = NULL;

	do 
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你要头插的值>:");
			scanf("%d", &value);
			Push_Front_List(&head, value);
			break;
		case 2:
			printf("请输入你要尾插的值>:");
			scanf("%d", &value);
			Push_Back_List(&head, value);
			break;
		case 3:
			printf("请输入你要插入的位置和要插入的值>:");
			scanf("%d %d", &pos, &value);
			Insert_List(&head, pos, value);
			break;
		case 4:
			Pop_Front_List(&head);
			break;
		case 5:
			Pop_Back_List(&head);
			break;
		case 6:
			printf("请输入你要删除的值>:");
			scanf("%d", &pos);
			Del_List(&head, pos);
			break;
		case 7:
			printf("请输入你要修改的位置和要修改的值>:");
			scanf("%d %d", &pos, &value);
			Modify_List(head, pos, value);
			break;
		case 8:
			Print_List(head);
			break;
		case 0:
			Destroy(&head);
			printf("链表销毁成功\n");
			break;
		default:
			printf("选择错误,请重新选择\n");
			break;
		}
	} while (input);
	return 0;
}

Simple_List.c

#include "Simple_List.h"


//打印链表数据
void Print_List(ListNode* phead)
{
	ListNode* cur = phead;

	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


//创建新节点
void Buy_Node(ListNode** ptr) //传二级指针是因为只传一级指针的话,我们改变形参不能改变实参的地址
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));

	if (tmp == NULL) //可能开辟空间不成功
	{
		perror("Buy_Node");
		return;
	}

	*ptr = tmp;
}


//头插
void Push_Front_List(ListNode** phead, LDatatype val)
{
	assert(phead); //phead要解引用,不能为空

	ListNode* newnode = NULL; 
	Buy_Node(&newnode); //插入一个新的数据需要先创建一个新节点插入到链表
	newnode->data = val;
	newnode->next = *(phead);
	*phead = newnode; //因为是头插一个节点,所以头指针要指向新的节点
}


//尾插
void Push_Back_List(ListNode** pphead, LDatatype val)
{
	assert(pphead); //phead要解引用,不能为空

	ListNode* newnode = NULL;
	Buy_Node(&newnode);
	newnode->data = val;
	newnode->next = NULL;

	ListNode* tail = *pphead;
	if (*(pphead) == NULL) //当链表为空时,头指针也为空,尾插需要把新节点地址给予头指针
	{
		*(pphead) = newnode;
		return;
	}

	while (tail->next != NULL) //找到最后一个节点,将新节点插入
	{
		tail = tail->next;
	}
	tail->next = newnode;
}


//寻找指定的的节点的地址
void Find_Ptr_List(ListNode** pphead, LDatatype pos,ListNode** pcur,ListNode** pfront)
{
	assert(pphead && pcur && pfront && *pphead); //这些指针需要解引用,不能为空
	
	*pcur = *pfront = *pphead;
	
	while (*pcur != NULL) // 这样的目的是,如果*pcur找到了指定数据的节点,*pfront就是*pcur的上一个节点
	{
		if ((*pcur)->data == pos) //先判断再让*pcur多走一步的原因是:可能头节点就是指定的数据,先走一步会漏掉判断
			break;
		if (*pcur == *pfront) // 让*pcur比*pfront多走一步,即*pcur = (*pfront)->next
			*pcur = (*pcur)->next;
		else
		{
			*pcur = (*pcur)->next;
			*pfront = (*pfront)->next;
		}
	}
}


//在指定数据的节点前插入数据
void Insert_List(ListNode** pphead,LDatatype pos,LDatatype val)
{
	ListNode* newnode = NULL;
	Buy_Node(&newnode);

	ListNode* cur = NULL;
	ListNode* front = NULL;
	Find_Ptr_List(pphead, pos, &cur, &front);

	if (cur == NULL) //说明整个链表已经判断完了,也没有找到指定数据
	{
		printf("找不到该位置\n");
		return;
	}

	if (cur == front) //说明指定数据就是头节点,直接头插
	{
		Push_Front_List(pphead, val);
		return;
	}

	front->next = newnode; //指定数据不是头节点的其他情况
	newnode->data = val;
	newnode->next = cur;
}


//头删
void Pop_Front_List(ListNode** pphead)
{
	assert(pphead && *pphead); //这些指针需要解引用,不能为空

	ListNode* front = *pphead;
	*pphead = (*pphead)->next; //头删后头指针需要指向新的头节点
	free(front);
	front = NULL;
}


//尾删
void Pop_Back_List(ListNode** pphead)
{
	assert(pphead && *pphead); //这些指针需要解引用,不能为空

	ListNode* tail = NULL;
	tail = *pphead;

	ListNode* front = NULL;
	front = *pphead;

	while (tail->next != NULL) 
	{
		if (front == tail) //让tail多走一步,即tail = front->next;
		{
			tail = tail->next;
		}
		else
		{
			tail = tail->next;
			front = front->next;
		}
	}

	if (front == tail) //说明链表只有一个数据,直接执行头删
	{
		Pop_Front_List(pphead);
		return;
	}

	front->next = NULL; //链表不止一个数据的情况,就需要把tail节点去掉
	free(tail); //找不到cur对应的实参所以不用置空,只需要释放空间即可
}


//删除指定数据
void Del_List(ListNode** pphead, LDatatype pos)
{
	assert(pphead); //pphead需要解引用,不能为空

	ListNode* cur = *pphead;
	ListNode* front = *pphead;

	Find_Ptr_List(pphead, pos, &cur, &front);

	if (cur == NULL) //说明链表遍历完了还没有找到指定数据
	{
		printf("找不到该位置\n");
		return;
	}

	if (cur == front) //说明头节点就是指定的数据,直接头删
	{
		Pop_Front_List(pphead);
		return;
	}

	front->next = cur->next; //头节点不是指定的数据的其他情况
	free(cur); //找不到cur对应的实参所以不用置空,只需要释放空间即可
}


//修改指定数据
void Modify_List(ListNode* phead, LDatatype pos, LDatatype val)
{
	assert(phead); //phead需要解引用,不能为空

	while (phead != NULL) //遍历链表寻找指定数据,再修改
	{
		if (phead->data == pos)
		{
			phead->data = val;
			return;
		}
		phead = phead->next;
		
	}

	if (phead == NULL) //遍历完链表还未找到指定数据
		printf("找不到该位置\n");
}


//销毁链表
void Destroy(ListNode** phead)
{
	while((*phead)!=NULL)
	{
		ListNode* cur = *phead; //销毁需要先记录下这个节点,如果直接销毁会找不到后面的节点
		*phead = (*phead)->next;
		free(cur);
		cur = NULL; //这里要销毁cur,而不是*phead,销毁*phead后面节点就找不到了
	}
}

Simple_List.h

#include <stdio.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>

typedef int LDatatype;     //链表储存的数据类型

typedef struct ListNode
{
	LDatatype data;        //节点储存的数据
	struct ListNode* next; //指向节点的下一个节点
}ListNode;

void Print_List(ListNode* phead);

void Push_Front_List(ListNode** phead, LDatatype val);

void Push_Back_List(ListNode** pphead, LDatatype val);

void Insert_List(ListNode** pphead, LDatatype pos, LDatatype val);

void Pop_Front_List(ListNode** pphead);

void Pop_Back_List(ListNode** pphead);

void Del_List(ListNode** pphead, LDatatype pos);

void Destroy(ListNode** phead);

void Modify_List(ListNode* phead, LDatatype pos, LDatatype val);

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

test.c

#include "Complex_List.h"

void menu()
{
	printf("****************************************\n");
	printf("************     请选择     ************\n");
	printf("******  1.PushFront   2.PushBack  ******\n");
	printf("******  3.Insert      4.PopFront  ******\n");
	printf("******  5.PopBack     6.Erase     ******\n");
	printf("******  7.Print       0.Exit      ******\n");
	printf("****************************************\n");
}

int main()
{
	int input = 0;
	int value = 0;
	int pos = 0;

	ListNode* plist = NULL;
	Init_List(&plist);

	do
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你要头插的值>:");
			scanf("%d", &value);
			Push_Front_List(plist, value);
			break;
		case 2:
			printf("请输入你要尾插的值>:");
			scanf("%d", &value);
			Push_Back_List(plist, value);
			break;
		case 3:
			printf("请输入你要插入的位置和要插入的值>:");
			scanf("%d %d", &pos, &value);
			Insert_List(plist, pos, value);
			break;
		case 4:
			Pop_Front_List(plist);
			break;
		case 5:
			Pop_Back_List(plist);
			break;
		case 6:
			printf("请输入你要删除的值>:");
			scanf("%d", &pos);
			Erase_List(plist, pos);
			break;
		case 7:
			Print_List(plist);
			break;
		case 0:
			Destroy_List(&plist);
			printf("销毁链表成功\n");
			break;
		default:
			printf("选择错误,请重新选择\n");
			break;
		}
	} while (input);
	return 0;
}

Complex_List.c

#include "Complex_List.h"


//创建新节点
ListNode* Buy_Newnode()
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));

	return newnode;
}


//打印链表数据
void Print_List(ListNode* phead)
{
	assert(phead); //phead需要解引用,不能为空

	ListNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


//初始化链表
void Init_List(ListNode** pphead) //要改变实参的地址,需要二级指针
{
	(*pphead) = Buy_Newnode();
	(*pphead)->next = (*pphead);
	(*pphead)->prev = (*pphead);
	(*pphead)->data = 0;
}


//销毁链表
void Destroy_List(ListNode** pphead)
{
	ListNode* phead = (*pphead);
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	*pphead = NULL;
}


//头插
void Push_Front_List(ListNode* phead,LDataType val)
{
	ListNode* newnode = Buy_Newnode();

	if (newnode == NULL) //有可能空间开辟失败
	{
		perror("Fail: Push_Front_List\n");
		return;
	}

	ListNode* headnext = phead->next;
	newnode->prev = phead; //头插是插入哨兵节点后面
	newnode->next = headnext;
	newnode->data = val;
	phead->next = newnode;
	headnext->prev = newnode;
}


//尾插
void Push_Back_List(ListNode* phead, LDataType val)
{
	ListNode* newnode = Buy_Newnode();

	if (newnode == NULL) //有可能开辟空间失败
	{
		perror("Fail: Push_Back_List\n");
		return;
	}

	ListNode* tail = phead->prev;
	newnode->next = phead; //尾删就是删除哨兵节点前一个节点,因为是循环链表
	newnode->prev = tail;
	newnode->data = val;
	phead->prev = newnode;
	tail->next = newnode;
}


//寻找指定数据节点
ListNode* Find_Ptr_List(ListNode* phead, LDataType pos)
{
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		if (cur->data == pos)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}


//在指定数据前面插入数据
void Insert_List(ListNode* phead, LDataType pos, LDataType val)
{
	ListNode* tmp = Find_Ptr_List(phead, pos);

	if (tmp == NULL)
	{
		printf("找不到该位置\n");
		return;
	}

	ListNode* dest = tmp;
	ListNode* last = dest->prev;

	ListNode* newnode = Buy_Newnode();

	newnode->prev = last;
	newnode->next = dest;
	newnode->data = val;
	last->next = newnode;
	dest->prev = newnode;
}


//头删
void Pop_Front_List(ListNode* phead)
{
	if (phead->next == phead) //如果哨兵节点的next是它自己,那么就代表链表为空,不进行删除
		return;

	ListNode* head = phead->next; //头删是删除哨兵节点下一个节点
	phead->next = head->next;
	head->next->prev = phead;
	free(head);
}


//尾删
void Pop_Back_List(ListNode* phead)
{
	if (phead->prev == phead) //如果哨兵节点的prev是它自己,那么就代表链表为空,不进行删除
		return;

	ListNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
}


//删除指定数据
void Erase_List(ListNode* phead, LDataType pos)
{
	ListNode* tmp = Find_Ptr_List(phead, pos);

	if (tmp == NULL)
	{
		printf("找不到该位置\n");
		return;
	}

	ListNode* dest = tmp;
	ListNode* last = dest->prev;
	ListNode* next = dest->next;
	last->next = next;
	next->prev = last;
	free(dest);
}

Complex_List.h

#include <stdio.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>

typedef int LDataType;     //节点储存的数据类型

typedef struct ListNode
{
	struct ListNode* prev; //指向节点的上一个节点
	struct ListNode* next; //指向节点的下一个节点
	LDataType data;        //节点储存的数据
}ListNode;

void Print_List(ListNode* phead);

void Init_List(ListNode** phead);

void Push_Front_List(ListNode* phead, LDataType val);

void Push_Back_List(ListNode* phead, LDataType val);

void Insert_List(ListNode* phead, LDataType pos, LDataType val);

void Pop_Front_List(ListNode* phead);

void Pop_Back_List(ListNode* phead);

void Erase_List(ListNode* phead, LDataType pos);

void Destroy_List(ListNode** pphead);

通过对比代码,我们发现带头双向循环链表的实现要比无头单向非循环链表的实现简单不少,因为带头双向循环链表哨兵位和循环的设定可以很大程度上方便我们的头插尾插,头删尾删等接口。

5.顺序表和链表的对比

C语言数据结构之链表,C语言数据结构,数据结构,c语言,链表,后端,开发语言文章来源地址https://www.toymoban.com/news/detail-855531.html

到了这里,关于C语言数据结构之链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】线性表之链表

    上一篇文章讲述了线性表中的顺序表,这篇文章讲述关于链表的定义、类别、实现、多种不同链表的优缺点和链表与顺序表的优缺点。 关于上一篇文章的链接:线性表之顺序表 链表是一种物理存储结构上 非连续、非顺序 的存储结构,数据元素的逻辑顺序是通过链表中的指针

    2024年02月05日
    浏览(44)
  • C++数据结构之链表(详解)

    主要参考文章地址 01.链表基础知识 | 算法通关手册 (itcharge.cn)) 本次内容是对链表的总结,可以看了上面的文章之后。 在看我下面的内容,做一个简短的复习,且本内容的代码均用C++实现,而参考资料的代码则为python。 每一个标题都有一个完整的链接,也可以点击下面的链

    2024年02月15日
    浏览(63)
  • 数据结构之链表练习与习题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言 2.习题解析 2.1习题一 2.2习题二 2.3习题三 2.4习题四 2.

    2024年02月05日
    浏览(39)
  • C/C++数据结构之链表题目答案与解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言  2.题目解析 2.1 移除链表元素 2.2反转链表 2.3链表的中

    2024年02月05日
    浏览(50)
  • 【023】C/C++数据结构之链表及其实战应用

    💡 作者简介:专注于C/C++高性能程序设计和开发,理论与代码实践结合,让世界没有难学的技术。包括C/C++、Linux、MySQL、Redis、TCP/IP、协程、网络编程等。 👉 🎖️ CSDN实力新星,社区专家博主 👉 🔔 专栏介绍:从零到c++精通的学习之路。内容包括C++基础编程、中级编程、

    2024年02月08日
    浏览(48)
  • 数据结构之链表 - 超详细的教程,手把手教你认识并运用链表

    顺序表只适合静态的查找和更新,不适合插入和删除元素, 因为在ArrayList中插入和删除元素时,由于需要将后序元素往前后者往后移动,所以时间复杂度会相当高,能达到O(N)。 为了解决这一问题,java 引入了 LinkedList(链表)。 链表是一种 逻辑上连续,物理上不连续 的存储结

    2024年02月09日
    浏览(43)
  • C语言数据结构--链表

    顺序表的问题及思考 问题: 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有

    2024年02月05日
    浏览(36)
  • C语言数据结构——链表

    目录 前言 一、什么是链表 1.1链表的结构和概念 1.2 链表的分类 二、无头单向非循环链表 2.1 创建结构体 2.2 动态申请一个节点 2.3 单链表打印 2.4 单链表尾插/尾删 2.4.1 单链表尾插  2.4.2 单链表尾删 2.5 单链表头插/头删 2.5.1 头插 2.5.2 头删 2.6 单链表查找 2.7 单链表中间插入/中

    2024年02月16日
    浏览(46)
  • 数据结构:链表(Python语言实现)

    链表分为单链表、双链表、循环单链表和循环双链表。 本文以单链表为例,用python创建一个单链表数据结构,同时定义链表节点的增加、删除、查询和打印操作。 创建一个名为Node的节点类,节点类里面包含2个属性和1个方法。 分别为data数据域属性和next指针域属性。 has_va

    2024年02月16日
    浏览(48)
  • C语言数据结构-双向链表

    带头链表的头结点,实际是\\\"哨兵位\\\",哨兵位节点不存储任何有效元素,只是站在这里\\\"放哨的\\\". 哨兵位的意义:遍历循环链表避免死循环. 笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现 代码位置出错 ,导致写的代码的含义不符合预期. 所以说思路一定要清晰

    2024年02月04日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包