首页 > 其他分享 >003——单链表

003——单链表

时间:2024-09-08 13:23:16浏览次数:13  
标签:Node LinkList 结点 单链 链表 003 地址 指针

1.链式存储的特点

逻辑(通过指针实现)上相邻,物理上可相邻可不相邻

2.结点(节点都可以)

4(&8)

8(&6)

6(&1)

1(&9)

9(NULL)

4后面存上8的地址 8后面存上6的地址 6后面存上1的地址 1后面存上9的地址 9后面存上空地址

也就是说,在链表中,需要存储:数据本身+下一个数据的地址,大体结构如下:

数据域

        指针域

(下一个节点的地址)

而上面列表所构成的整体也被称作结点(Node)

而后面的代码示例的数据类型我们均以int为例,方便理解

typedef struct Node {
	int data;		    //该节点的数据
	struct Node* next;		
}Node,*LinkList;

这里有几个需要注意的小点:

小细节

①为什么是struct Node* next;而不是int* next;

        因为在我们的指针域中,存储的是下一个结点的地址,而不是下一个数据的地址。因为在结点中既包含数据又包含指针域,只有这样才能将一个又一个的结点串起来。

        要是这么说不能够理解,我们也可以换一种想法,此时我们的示例中只有一个数据,要是该链表再复杂一些,有100个数据,难道我们要定义100个指针吗?显然是不可能的,而存储下一个结点则可以有效避免这个问题。

②Node和*LinkList之间的联系

LinkList等价于Node*,我们可以看下面声明的两个变量

LinkList p;
Node* q;

这里的p和q都是结构体指针,他们的类型相同,而LinkList* x则是一个二级指针,等价于Node** x

③为什么使用*LinkList

为了增强代码的可读性,关于这一点我们稍后会去重点强调

④一个结点占多少字节

typedef struct Node {
	int data;		    //该节点的数据
	struct Node* next;		
}Node,*LinkList;

还是以这个为例分析(64位系统)

int 型变量占4个字节,因为struct Node* next;    是一个指针,只要是指针,无论这个指针是什么类型,都是占8个字节,所以一共占12个字节

⑤由结点组成的链表在内存中是什么样的

以下面这个为例:

4(&8)

8(&6)

6(&1)

1(NULL)

注意:0x表示该数是十六进制,本身没有数值含义 

从图中可以看出,他们的物理位置是不相邻的,但是逻辑上通过指针相邻。但是图中还有一个问题,头节点如何表示?

这个时候我们用Node *L去指向头结点。

注意,在本质上,L是指针的名字,而不是链表的名字,而为了方便称呼,我们需要给链表起名,而为了增强程序的可读性,所以我们在定义结构体的时候,多一个*LinkList,所以我们在这里做一些小改动。这也就回答了③为什么使用*LinkList的问题

在这里我们又引入了几个新的概念

3.头指针

保存结点中第一个结点的地址的指针(上个案例中L是头指针),并以头指针的名字命名整个链表

4.首元结点

链表中第一个保存实际数据的结点

在我们对该链表进行修改时回存在一个问题:如果在4的前面 插入数据会使头结点发生改变 ,所以我们可以在4的前面添加一个不保存数据的结点,而头指针的位置也随之改变

而我们给这个不存实际数据(或者称作脏数据)的元素也起一个名字:头结点 

5.头结点(可有可无)

不过这两种方法(带头结点和不带头结点)都是可以的。如果是带头结点的链表,头结点的指针域保存首元结点的地址,数据与不用(也就是浪费掉的),目的是使得首元结点的操作与后面的结点统一起来。

知识点补充

如果我们申请一块空间但是没有赋值,但是这块空间也是有数据的

注意头指针、头结点、首元结点的关系

头指针指向头结点× (需要前提条件:是否有头结点)

头指针指向首元结点×

6.具体操作(代码)

6.1初始化一个空链表(带头结点)


//初始化一个带头结点的空链表
LinkList InitLinkList() {
	Node* s = (Node*)malloc(sizeof(Node));//申请头结点
	if (s == NULL) {
		printf("空间分配失败\n");
	}
	else {
		//s->data	脏数据,不用管
		s->next = NULL;
	}
	return s;
}

int main() {
	LinkList L = NULL;
	L = InitLinkList();
}

(不带头结点)


int main() {
	LinkList L = NULL;
}

6.2增删改查

标签:Node,LinkList,结点,单链,链表,003,地址,指针
From: https://blog.csdn.net/immnature/article/details/141933185

相关文章

  • 【数据结构】单链表专题
    链表的概念及结构概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其他车......
  • 数据结构基础讲解(二)——线性表之单链表专项练习
    本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e 上一节我讲了线性表中顺序表的定义以及常用的算法,那么这节我将继续讲解顺序表中的链式结构以及常见的算法。数据......
  • VUE0003:Naive UI库:滑动条,单选,多选组件
    1,滑动条,单选,多选组件 <template><n-scrollbarclass="show-scrollbar"><n-spaceclass="map-setting"vertical><n-spacestyle="flex-flow:row;align-items:center;"><n-textclass=&q......
  • 国产芯片CW32L010兼容代替STM8S003
     CW32L010是基于eFlash的单芯片低功耗微控制器,集成了主频高达48MHz的ARM®Cortex®-M0+内核,ZUI高主频能够达到48MHz、高速嵌入式存储器(多至64K字节FLASH和多至4K字节SRAM)以及一系列全面的增强型外设和I/O口,并且集成高精度模拟数字转换器(ADC)。 所有型号都提供全套的通信接口(二......
  • 国产芯片CW32L010兼容代替STM8S003
    CW32L010是基于eFlash的单芯片低功耗微控制器,集成了主频高达48MHz的ARM®Cortex®-M0+内核,ZUI高主频能够达到48MHz、高速嵌入式存储器(多至64K字节FLASH和多至4K字节SRAM)以及一系列全面的增强型外设和I/O口,并且集成高精度模拟数字转换器(ADC)。所有型号都提供全套的通信接口......
  • BUSANA 7003 – Business Analytics Project
    BUSANA7003–BusinessAnalyticsProject–Semester2,2024FinalProjectBackground.YouarestartinganewjobasaBusinessAnalystatAQRAssetManagement,aglobalinvestmentmanagementfirmfocusedonquantitativeinvestmentstrategies.Yourfirst......
  • 数据结构——单链表查询、逆序、排序
    1、思维导图2、查、改、删算法//快慢排序法找中间值intmid_link(Link_t*plink){Link_Node_t*pfast=plink->phead;Link_Node_t*pslow=pfast;intm=0;while(pfast!=NULL){pfast=pfast->pnext;++m;if(m%......
  • MySQL 2003 - Can’t connect to MySQL server on ' '(10060)
    2003-Can’tconnecttoMySQLserveron''(10060) 一般是以下几个原因造成的:1.网络不通畅2.mysql服务未启动3.防火墙未开放端口4##云服务器的安全组规则未设置  一般是以下几个原因造成的:1.网络不通畅:【mysql-u-p,看看能不能登陆】2.mysql服务未启动:【mysql-u-p,......
  • 代替STM32L010 STM32G030 CMS8S6990 STM8S003的芯片CW32L010
    CW32L010作为一款可以代替STM32L010STM32G030CMS8S6990STM8S003部分型号可以兼容的芯片,其功能上能够和它们相匹配,并且在功能更优秀,其芯片特点在于超低功耗,高精度ADC和主频最高可达到48MHz。CW32L010是基于eFlash的单芯片低功耗微控制器,集成了主频高达48MHz的ARM®Cort......
  • FNCE20003 Introductory Personal Finance
    FNCE20003Introductory Personal FinanceASSIGNMENTS 1and2Semester2,2024Administrative mattersTask: Bothassignmentsinthis subject relateto one scenario (see nextpage).That is, all ofthe facts will applyto both assignments, bu......