C语言：数据结构链表基本操作（增、删、改、查、遍历）
成为你的Bug 2024-10-16 11:35:02 阅读 97
一、数据结构-链表介绍
链表：在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由一系列节点（链表中每一个元素称为节点/结点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。
链表可以分为单向链表和双向链表两种形式。在单向链表中，每个节点只保存指向下一个节点的指针，而在双向链表中，每个节点同时保存指向上一个节点和下一个节点的指针。
二、链表操作
插入：在链表的任意位置插入一个节点；删除：从链表中删除一个节点；查找：在链表中查找指定的数据；修改：修改链表中节点的数据；遍历：按照顺序依次访问链表中的每个节点。
三、创建和释放
1. 创建节点
<code>// 创建一个新节点
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;
}
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。