当前位置: 首页 > article >正文

数据结构——单链表list

前言:大家好😍,本文主要介绍数据结构——单链表

目录

一、单链表

二、使用步骤

1.结构体定义

2.初始化

3.插入

3.1 头插

3.2 尾插 

3.3 按位置插

 四.删除

4.1头删

4.2 尾删

4.3 按位置删

4.4按值删

五 统计有效值个数 

六 销毁1

销毁2

七 查找

八 打印


一、单链表

概念:单链表逻辑上相邻,物理上不一定相邻的链式存储结构

所以一个结点不仅仅要保存自身的数据,还要保存自己下一个连接结点的地址

所以每一个结点需要俩个域:一个数据域,一个指针域

二、使用步骤

1.结构体定义

typedef int Elem_Type;
struct Node
{
	Elem_Type data;//数据域 存储有效数据
	struct Node* next;//指针域  存下一个有效结点的地址
};

typedef struct Node Node;
typedef struct Node* pNode;
struct Node:定义了一个 结构体 Node,它包含两个成员:
Elem_Type data;: 数据域,用于存储节点中的数据。由于 Elem_Type 被定义为 int,所以这里的 data 可以存储一个整数。
struct Node* next;: 指针域,用于存储指向下一个节点的地址。这样,每个节点都可以通过 next 指针链接到下一个节点,形成链表。
typedef struct Node Node;:为结构体 Node 创建了一个别名 Node,这样在代码中可以直接 使用 Node 来声明这种类型的变量
typedef struct Node* pNode;:定义了一个 pNode 类型,它实际上是 指向 Node 结构体的指针类型。这通常用于表示链表的头指针或遍历链表时的指针变量。

2.初始化

//初始化
void Init_List(struct Node* head)
{
	assert(head != NULL);
	if (NULL == head)
	{
		exit(EXIT_FAILURE);
	}
	head->next = nullptr;
}
  • 参数 head 是指向 Node 结构体的指针。

  • 初始化链表:head->next = nullptr;head 节点的 next 指针设置为 nullptr,表示链表为空,即没有其他节点。

3.插入

3.1 头插

bool Insert_head(struct Node* head, Elem_Type val)
{
	assert(head != NULL);
	if (NULL == head)
	{
		exit(EXIT_FAILURE);
	}

	Node* pnewnode=(Node*)malloc(sizeof(Node));
	if (NULL == pnewnode)
		exit(1);
	pnewnode->data = val;

	pnewnode->next = head->next;
	head->next = pnewnode;
}

  Node* pnewnode = (Node*)malloc(sizeof(Node));:使用 malloc 函数分配内存以创建一个新的 Node 结构体实例,并将其地址赋给指针 pnewnode

  1. pnewnode->data = val;:将传入的数据 val 存储在新节点的 data 成员中。

  2. pnewnode->next = head->next;:将新节点的 next 指针指向当前头节点的下一个节点,即链表的第二个节点。

  3. head->next = pnewnode;:将头节点的 next 指针指向新节点,这样新节点就成为了链表的第一个节点。

3.2 尾插 

bool Insert_tail(struct Node* head, Elem_Type val)
{
	assert(head != NULL);
	if (NULL == head)
	{
		exit(EXIT_FAILURE);
	}
	Node* pnewnode = (Node*)malloc(sizeof(Node));
	if (NULL == pnewnode)
		exit(1);
	pnewnode->data = val;

	Node* p = head;
	while (p->next != NULL)
	{
		p = p->next;
	}
	 
	//pnewnode->next = head->next;
	//head->next = pnewnode;
	pnewnode->next = p->next;
	p->next = pnewnode;

	return true;
} 

3.3 按位置插

bool Insert_pos(struct Node* head, Elem_Type val, int pos)
{
	assert(head != NULL);
	assert(pos >= 0 && pos <= Get_Length(head));

	Node* pnewnode = (Node*)malloc(sizeof(Node));
	if (NULL == head)
	{
		exit(1);
	}

	pnewnode->data = val;

	Node* p = head;
	for (int i = 0; i < pos; i++)
		p = p->next;

	//pnewnode->next = head->next;
     //head->next = pnewnode;
	pnewnode->next = p->next;
	p->next = pnewnode;

	return true;
}

 

 四.删除

4.1头删

bool Del_head(struct Node* head)
{
	assert(head != NULL);

	 
	if (Is_Empty(head))
		return false;

	Node* p = head->next;
	head->next = p->next;

	free(p);
	p = NULL;
	return true;
}

4.2 尾删

bool Del_tail(struct Node* head)
{
	assert(head != NULL);


	if (Is_Empty(head))
		return false;

	Node* p = head;
	while (p->next->next != NULL)
		p = p->next;

	Node* q = p->next;
	p->next = q->next;

	free(p);
	p = NULL;
	return true;
}

4.3 按位置删

//8.按值删(删除值val出现的第一次的地方)
bool Del_val(struct Node* head, Elem_Type val)
{
	//0.assert
	assert(head != NULL);

	//0.5 判断链表是否是空链表
	if (Is_Empty(head))
		return false;

	//1.调用Search函数,查找当前值val是否存在,用临时指针q接收
	Node* q = Search(head, val);
	if (q == NULL)
	{
		return false;
	}

	//2.申请临时指针p,让指针p停留在指针q指向节点的上一个节点
	Node* p = head;
	for ( ; p->next != q; p = p->next);

	//3.跨越指向
	p->next = q->next;

	//4.释放
	free(q);
	q = NULL;

	return true;
}

4.4按值删

bool Del_val(struct Node* head, Elem_Type val)
{
	//0.assert
	assert(head != NULL);

	//0.5 判断链表是否是空链表
	if (Is_Empty(head))
		return false;

	//1.调用Search函数,查找当前值val是否存在,用临时指针q接收
	Node* q = Search(head, val);
	if (q == NULL)
	{
		return false;
	}

	//2.申请临时指针p,让指针p停留在指针q指向节点的上一个节点
	Node* p = head;
	for ( ; p->next != q; p = p->next);

	//3.跨越指向
	p->next = q->next;

	//4.释放
	free(q);
	q = NULL;

	return true;
}

五 统计有效值个数 

int Get_Length(struct Node* head)
{
	int count = 0;
	for (Node* p = head->next; p != NULL; p = p->next)
	{
		count++;
	}

	return count;
}

六 销毁1

//11.销毁1(需要辅助节点参与进来)
void Destroy1(struct Node* head)
{
	//只要不是空链表,则头删一次,直到链表为空
	/*while (!Is_Empty(head))
	{
		Del_head(head);
	}*/

	while (head->next != NULL)
	{
		Node* q = head->next;
		head->next = q->next;
		free(q);
		q = NULL;
	}
}

销毁2

//12.销毁2(不需要辅助节点参与进来)
void Destroy2(struct Node* head)
{
	//0.assert  head  

	//1.申请指针p,让其保存辅助节点的指针域
	Node* p = head->next;//p有可能为NULL, 有可能不空

	//2.申请指针q,先不给q赋值
	Node* q = NULL; //因为p有可能是NULL,所以不能现在直接把p->next给到q

	//3.反复通过p和q打配合,去销毁后续节点
	while (p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}

	//4.节点全部销毁完毕,别忘了把辅助节点的指针域置空
	head->next = NULL;//这一行代码可以帮助,下一次启用的时候,辅助节点不用初始化了

}

七 查找

//9.查找(查找值val出现的第一次的地方)
struct Node* Search(struct Node* head, Elem_Type val)
{
	//0.assert

	for (Node* p = head->next; p != NULL; p = p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}

	return NULL;
}

八 打印

//15.打印
void Show(struct Node* head)
{
	//assert

	for (Node* p = head->next; p != NULL; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");

}


http://www.kler.cn/a/588998.html

相关文章:

  • 【软考-架构】11.3、设计模式-新
  • 从技术创新到全球布局:MOVA割草机器人以尖端科技定义智能园艺
  • windows上清理docker
  • NET进行CAD二次开发之二
  • django 运行时仅显示500 但是不提示其他内容 如何令其显示更多错误信息
  • pycharm环境创建
  • 群体智能优化算法-䲟鱼优化算法 (Remora Optimization Algorithm, ROA,含Matlab源代码)
  • Mysql与ElasticSearch间的数据同步场景模拟
  • MySQL数据库(数据库操作)4
  • Vue.js 中的计算属性、监听器与方法:区别与使用场景
  • 系统架构设计师—论文解析—论文写作技巧
  • How to install cangjie on Linux mint 22.1
  • python和devops
  • 在 macOS 上优化 Vim 用于开发
  • 论文阅读笔记——ADALORA: ADAPTIVE BUDGET ALLOCATION FOR PARAMETER-EFFICIENT FINE-TUNING
  • 五种最新优化算法(ALA、AE、DOA、GOA、OX)求解多个无人机协同路径规划(可以自定义无人机数量及起始点),MATLAB代码
  • SpringBoot中的定时任务实现方式有哪些?
  • Flutter:签名板封装
  • 沐数科技数据开发岗笔试题2025
  • 《C#上位机开发从门外到门内》3-2::Modbus数据采集系统