C语言：数据结构链表基本操作（增、删、改、查、遍历）_c语言 链表的增删改查

一、数据结构-链表介绍

链表：在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由一系列节点（链表中每一个元素称为节点/结点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

链表可以分为单向链表和双向链表两种形式。在单向链表中，每个节点只保存指向下一个节点的指针，而在双向链表中，每个节点同时保存指向上一个节点和下一个节点的指针。

二、链表操作

• 插入：在链表的任意位置插入一个节点；
• 删除：从链表中删除一个节点；
• 查找：在链表中查找指定的数据；
• 修改：修改链表中节点的数据；
• 遍历：按照顺序依次访问链表中的每个节点。

三、创建和释放

1. 创建节点

// 创建一个新节点
Node* createNode(ElemType data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if(newNode != NULL)
	{
		newNode -> data = data; // 设置数据
		newNode -> next = NULL; // 新节点的下一个节点为空
	}
	return newNode;
}

2. 创建空链表

// 创建一个空链表
linkedList* createLinkedList()
{
	linkedList* list = (linkedList*)malloc(sizeof(linkedList));
	if(list != NULL)
	{
		list -> head = NULL; // 头指针为空
		list -> length = 0; // 链表长度为0
	}
	return list;
}

3. 释放空间

// 释放链表的内存
void freeLinkedList(linkedList* list)
{
	if(list == NULL)
		return;
		
	Node* current = list -> head;
	while(current != NULL)
	{
		Node* temp = current;
		current = current -> next;
		free(temp); // 释放节点内存
	}
	free(list); // 释放链表内存
}

四、链表操作各部分代码实现

1. 插入

// 在链表的指定位置插入节点
void insertNode(linkedList* list, int pos, ElemType data)
{
	if(list == NULL || pos < 0 || pos > list -> length)
		return;
		
	Node* newNode = createNode(data); // 创建新节点
	if(newNode == NULL)
		return;
		
	if(pos == 0)
	{
		newNode -> next = list -> head; // 将新节点插入到链表头部
		list -> head = newNode; // 更新头指针
	}
	else
	{
		Node* current = list -> head;
		for(int i =0; i < pos - 1; i++) // 找到插入位置的前一个节点
		{
			current = current -> next;
		}
		newNode -> next = current -> next; // 新节点指向原来位置的节点
		current -> next = newNode; // 前一个节点指向新节点
	}
	list -> length ++; // 链表长度加 1
}

2. 删除

// 删除链表的指定位置的节点
void deleteNode(linkedList* list, int pos)
{
	if(list == NULL || pos < 0 || pos >= list -> length) 
		return;
	
	Node* temp;
	if(pos == 0)
	{
		temp = list -> head; // 保存头节点
		list -> head = list -> head -> next; // 更新头指针
	}
	else
	{
		Node* current = list -> head;
		for(int i = 0; i < pos - 1; i++) // 找到要删除节点的前一个节点
		{
			current = current -> next;
		}
		temp = current -> next; // 保存要删除的节点
		current -> next = temp -> next; // 前一个节点指向要删除节点的下一个节点
	}
	free(temp); // 释放节点内存
	list -> length--; // 链表长度减1
}

3. 修改

// 查找链表中指定数据的位置
int findNode(linkedList* list, ElemType data)
{
	if(list == NULL)
		return -1;
	
	Node* current = list -> head;
	int pos = 0;
	
	while(current != NULL) // 遍历链表
	{
		if(current -> data == data) // 找到数据相同的节点
			return pos;
		current = current -> next;
		pos++;
	}
	return -1; // 数据不存在
}

4. 查找

// 查找链表中指定数据的位置
int findNode(linkedList* list, ElemType data)
{
	if(list == NULL)
		return -1;
	
	Node* current = list -> head;
	int pos = 0;
	
	while(current != NULL) // 遍历链表
	{
		if(current -> data == data) // 找到数据相同的节点
			return pos;
		current = current -> next;
		pos++;
	}
	return -1; // 数据不存在
}

5. 遍历

// 遍历，打印链表的所有节点数据
void printLinkedList(linkedList* list)
{
	if(list == NULL)
		return;
	
	Node* current = list -> head;
	while(current != NULL)
	{
		printf("%d ",current -> data);
		current = current -> next;
	}
	printf("\n");
}

五、完整代码

#include <stdio.h>
#include <stdlib.h>
 
typedef int ElemType;
 
// 定义链表节点
typedef struct Node{
	ElemType data;
	struct Node* next;
}Node; 
 
// 定义链表结构
typedef struct{
	Node* head; // 头指针
	int length; // 链表长度
}linkedList;
 
// 创建一个新节点
Node* createNode(ElemType data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if(newNode != NULL)
	{
		newNode -> data = data; // 设置数据
		newNode -> next = NULL; // 新节点的下一个节点为空
	}
	return newNode;
}
 
// 创建一个空链表
linkedList* createLinkedList()
{
	linkedList* list = (linkedList*)malloc(sizeof(linkedList));
	if(list != NULL)
	{
		list -> head = NULL; // 头指针为空
		list -> length = 0; // 链表长度为0
	}
	return list;
}
 
// 在链表的指定位置插入节点
void insertNode(linkedList* list, int pos, ElemType data)
{
	if(list == NULL || pos < 0 || pos > list -> length)
		return;
		
	Node* newNode = createNode(data); // 创建新节点
	if(newNode == NULL)
		return;
		
	if(pos == 0)
	{
		newNode -> next = list -> head; // 将新节点插入到链表头部
		list -> head = newNode; // 更新头指针
	}
	else
	{
		Node* current = list -> head;
		for(int i =0; i < pos - 1; i++) // 找到插入位置的前一个节点
		{
			current = current -> next;
		}
		newNode -> next = current -> next; // 新节点指向原来位置的节点
		current -> next = newNode; // 前一个节点指向新节点
	}
	list -> length ++; // 链表长度加 1
}
 
// 删除链表的指定位置的节点
void deleteNode(linkedList* list, int pos)
{
	if(list == NULL || pos < 0 || pos >= list -> length) 
		return;
	
	Node* temp;
	if(pos == 0)
	{
		temp = list -> head; // 保存头节点
		list -> head = list -> head -> next; // 更新头指针
	}
	else
	{
		Node* current = list -> head;
		for(int i = 0; i < pos - 1; i++) // 找到要删除节点的前一个节点
		{
			current = current -> next;
		}
		temp = current -> next; // 保存要删除的节点
		current -> next = temp -> next; // 前一个节点指向要删除节点的下一个节点
	}
	free(temp); // 释放节点内存
	list -> length--; // 链表长度减1
}
 
// 更新链表的指定位置的节点数据
void updateNode(linkedList* list, int pos, ElemType data)
{
	if(list == NULL || pos < 0 || pos >= list -> length) 
		return;
		
	Node* current = list -> head;
	for(int i = 0; i < pos; i++) // 找到要更新的节点
	{
		current = current -> next;
	}
	current -> data = data; // 更新节点数据
}
 
// 查找链表中指定数据的位置
int findNode(linkedList* list, ElemType data)
{
	if(list == NULL)
		return -1;
	
	Node* current = list -> head;
	int pos = 0;
	
	while(current != NULL) // 遍历链表
	{
		if(current -> data == data) // 找到数据相同的节点
			return pos;
		current = current -> next;
		pos++;
	}
	return -1; // 数据不存在
}
 
// 遍历，打印链表的所有节点数据
void printLinkedList(linkedList* list)
{
	if(list == NULL)
		return;
	
	Node* current = list -> head;
	while(current != NULL)
	{
		printf("%d ",current -> data);
		current = current -> next;
	}
	printf("\n");
}
 
// 释放链表的内存
void freeLinkedList(linkedList* list)
{
	if(list == NULL)
		return;
		
	Node* current = list -> head;
	while(current != NULL)
	{
		Node* temp = current;
		current = current -> next;
		free(temp); // 释放节点内存
	}
	free(list); // 释放链表内存
}
 
int main()
{
	linkedList* list = createLinkedList(); // 创建一个链表
	insertNode(list, 0, 10);
	insertNode(list, 1, 20);
	insertNode(list, 2, 30);
	
	printLinkedList(list);
	
	updateNode(list, 1, 25);
	
	printLinkedList(list);
	
	deleteNode(list, 2);
	printLinkedList(list);
	
	int pos = findNode(list, 30);
	printf("pos = %d\n", pos);
	
	freeLinkedList(list);
	
	return 0;
}