草庐IT

C语言链表详解（通俗易懂）

杯浅 2023-04-18 原文

文章目录

前言

线性表是实际中广泛应用的重要数据结构，本文用通俗易懂的方法讲解它。

一、什么是线性表？

首先，我们了解下“线性表”的基本概念：

  • 全名为“线性存储结构”，使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。
  • 是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、队列…

二、顺序表：

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储数据。

  2. 动态顺序表：使用动态开辟的数组存储。

扩容方法：动态开辟一块新的空间（一般为原空间的两倍），将原空间的数据拷贝到新的空间，然后让array指针指向新的空间并且释放旧空间。

对比以上两者：

区别：

  • 静态顺序表和动态顺序表唯一不同的是，静态顺序表在创建顺序表的时候容量已经确定，不可以更改，而动态顺序表的容量是由malloc函数动态开辟，当容量不够用时可以增加容量capacity。

优缺点：

  • 静态顺序表创建空间时为静态开辟，不用malloc函数，代码相对简单（一点点），不存在内存泄露问题。
  • 动态顺序表，动态开辟空间，使用相对灵活，相比于静态开辟空间也可以少空间浪费。

动态顺序表代码演示：初始化、插入数据和检查容量

//初始化顺序表
void SeqList_Init(SeqList* ps)
{
	SLDataType* tmp = (SLDataType*)malloc(5 * sizeof(SLDataType));
	if (tmp == NULL)
	{
		perror(malloc);
		exit(-1);
	}
	ps->arr = tmp;
	ps->size = 0;
	ps->capacity = 5;
}
//检查容量
void Check_Capacity(SeqList* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, 2*ps->capacity* sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror(realloc);
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = 2 * ps->capacity;
		printf("扩容成功\n");
	}
}
//插入数据
void SeqList_Insert(SeqList* ps, SLDataType pos)
{
	assert(ps);
	Check_Capacity(ps);//检查容量
	SLDataType num = 0;
	printf("请输入需要写入的值:>");
	scanf("%d", &num);
	if (ps->size == 0 || pos == ps->size)
	{
		ps->arr[pos] = num;
	}	
	SLDataType end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = num;
	ps->size++;
}
//头部插入数据
void SeqList_PushFront(SeqList* ps)
{
	SeqList_Insert(ps, 0);
}
//尾部插入数据
void SeqList_PushBack(SeqList* ps)
{
	SeqList_Insert(ps, ps->size);
}

三、链表：

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

下图为单链表的逻辑结构类型：

注意：

  1. 链式结构在逻辑上是连续的，但在物理上不一定连续
  2. 现实中结点一般都是在堆上申请出来的
  3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可连续，也可能不连续

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

  1. 单向或者双向：

  1. 带头和不带头：

  2. 循环和不循环：

    经过以上三种可以有2^3=8种类型。

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

  • 无头单向链表和带头双向循环链表：

这边通过单链表头部和尾部插入数据代码帮大家理解过程：

//创建结点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//头插数据
void SListPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);//读取新建的结点
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾插数据
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);//读取新建的结点
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	SListNode* tail = *pphead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newnode;
}

四、顺序表和链表对比：

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持不支持
任意位置插入或删除元素可能搬移元素，效率低只需修改指针指向
插入动态顺序表，空间不够需要扩容没有容量概念
应用场景元素高效存储+频繁访问任意位置插入和删除
缓存利用率高低

总结

以上就是今天要讲的顺序表和链表的内容啦，如果本篇博客对你有所帮助的话，请给博主一个三连哦！

易懂通俗spanclasstoken链表c语言数据结构c++

有关C语言链表详解（通俗易懂）的更多相关文章

  1. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  2. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  3. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

    ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  4. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  5. ruby - 有人可以解释一下在 Ruby 中注入(inject)的真实、通俗易懂的用法吗？ - 2

    我正在学习Ruby，遇到了inject。我正处于理解它的风口浪尖，但当我是那种需要真实世界的例子来学习一些东西的人时。我遇到的最常见的例子是人们使用inject来添加一个(1..10)范围的总和，我不太关心这个。这是一个任意的例子。在实际程序中我会用它做什么？我正在学习，所以我可以继续使用Rails，但我不必有一个以Web为中心的示例。我只需要一些我可以全神贯注的目标。谢谢大家。 最佳答案 inject有时可以通过它的“其他”名称reduce更好地理解。它是一个对Enumerable进行操作(迭代一次)并返回单个值的函数。它有许多有

  6. ruby - 如何保持我不常用的编程语言技能 - 2

    关闭。这个问题是off-topic.它目前不接受答案。想改进这个问题吗？Updatethequestion所以它是on-topic用于堆栈溢出。关闭11年前。Improvethisquestion我不经常使用ruby​​-通常它加起来相当于每两个月或更长时间编写一次脚本。我的大部分编程都是使用C++进行的，这与ruby​​有很大不同。由于我与ruby​​之间的差距如此之大，我总是忘记语言的基本方面(比如解析文本文件和其他简单的东西)。我想每天练习一些基本的东西，我想知道是否有一些我可以订阅的网站，并且会向我发送当天的Ruby问题或类似的东西。有人知道这样的站点/Internet服务吗？

  7. ruby-on-rails - 如果特定语言环境中缺少翻译，如何配置 i18n 以使用 en 语言环境？ - 2

    如果特定语言环境中缺少翻译，如何配置i18n以使用en语言环境翻译？当前已插入翻译缺失消息。我正在使用RoR3.1。 最佳答案 找到相似的question这里是答案:#application.rb#railswillfallbacktoconfig.i18n.default_localetranslationconfig.i18n.fallbacks=true#railswillfallbacktoen,nomatterwhatissetasconfig.i18n.default_localeconfig.i18n.fallback

  8. ruby-on-rails - 如何通过 URL 更改语言环境？ - 2

    在我的双语Rails4应用程序中，我有一个像这样的LocalesController:classLocalesController用户可以通过此表单更改其语言环境:deflocale_switcherform_tagurl_for(:controller=>'locales',:action=>'change_locale'),:method=>'get',:id=>'locale_switcher'doselect_tag'set_locale',options_for_select(LANGUAGES,I18n.locale.to_s)end这有效。但是，目前用户无法通过URL更改

  9. ruby - 一种语言如何被自身解释(如 Rubinius)？ - 2

    我使用Ruby编程已经有一段时间了，现在只使用Ruby的标准MRI实现，但我一直对我经常听到的其他实现感到好奇。前几天我在读有关Rubinius的文章，这是一个用Ruby编写的Ruby解释器。我试着在不同的地方查找它，但我很难弄清楚这样的东西到底是如何工作的。我在编译器或语言编写方面从来没有太多经验，但我真的很想弄明白。一门语言究竟如何才能被自己解释？编译中是否有一个我不明白这有意义的基本步骤？有人可以像我是个白痴一样向我解释这个吗(因为无论如何这都不会太离谱) 最佳答案 它比你想象的要简单。Rubinius并非100%用Ruby编

  10. ruby-on-rails - ruby 真的是一种完全面向对象的语言吗？ - 2

    Ruby是完全面向对象的语言。在ruby​​中，一切都是对象，因此属于某个类。例如5属于Objectclass1.9.3p194:001>5.class=>Fixnum1.9.3p194:002>5.class.superclass=>Integer1.9.3p194:003>5.class.superclass.superclass=>Numeric1.9.3p194:005>5.class.superclass.superclass.superclass=>Object1.9.3p194:006>5.class.superclass.superclass.superclass.su

随机推荐