上海闵行网站建设公司,怎么注册晋江网站做的,丽水市建设监理协会网站在哪里,广州市天河区发布链表 介绍单向链表节点结构创建节点插入节点删除节点遍历链表尾部插入查找节点链表反转示例程序程序1程序2 介绍
链表是一种常见的数据结构#xff0c;用于存储一系列线性数据。与数组不同#xff0c;链表中的元素在内存中不必是连续存放的#xff0c;而是通过指针将每个元… 链表 介绍单向链表节点结构创建节点插入节点删除节点遍历链表尾部插入查找节点链表反转示例程序程序1程序2 介绍
链表是一种常见的数据结构用于存储一系列线性数据。与数组不同链表中的元素在内存中不必是连续存放的而是通过指针将每个元素节点链接在一起。链表有很多种类型例如单向链表、双向链表和循环链表。这里我们主要介绍单向链表。
单向链表
单向链表由一系列节点组成每个节点包含两个部分
数据部分存储节点的实际内容。指针部分存储指向下一个节点的指针。
节点结构
在 C 语言中我们可以通过定义一个结构体来表示链表的节点
struct Node {int data; // 数据部分struct Node* next; // 指针部分
};创建节点
可以通过动态内存分配函数 malloc 来创建新节点
#include stdio.h
#include stdlib.h// 定义节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node));if (!newNode) {printf(内存分配失败\n);exit(1);}newNode-data data;newNode-next NULL;return newNode;
}插入节点
我们可以在链表的头部或尾部插入节点。以头部插入为例
// 头部插入
void insertAtHead(struct Node** head, int data) {struct Node* newNode createNode(data);newNode-next *head;*head newNode;
}删除节点
删除链表中的节点也很常见。假设我们要删除值为 key 的节点
void deleteNode(struct Node** head, int key) {struct Node* temp *head;struct Node* prev NULL;// 如果头节点本身就是要删除的节点if (temp ! NULL temp-data key) {*head temp-next;free(temp); // 释放内存return;}// 搜索要删除的节点while (temp ! NULL temp-data ! key) {prev temp;temp temp-next;}// 如果没找到要删除的节点if (temp NULL) return;// 断开链接并释放内存prev-next temp-next;free(temp);
}遍历链表
遍历链表可以通过循环来实现
void printList(struct Node* head) {struct Node* current head;while (current ! NULL) {printf(%d - , current-data);current current-next;}printf(NULL\n);
}尾部插入
尾部插入与头部插入类似我们需要找到链表的最后一个节点然后将新节点添加到末尾。
// 尾部插入
void insertAtTail(struct Node** head, int data) {struct Node* newNode createNode(data);if (*head NULL) {*head newNode;return;}struct Node* temp *head;while (temp-next ! NULL) {temp temp-next;}temp-next newNode;
}查找节点
查找链表中的某个节点返回其位置或者指针
struct Node* searchNode(struct Node* head, int key) {struct Node* current head;while (current ! NULL) {if (current-data key) {return current;}current current-next;}return NULL; // 未找到
}链表反转
反转链表是一个经典的问题可以通过迭代的方式实现
void reverseList(struct Node** head) {struct Node* prev NULL;struct Node* current *head;struct Node* next NULL;while (current ! NULL) {next current-next; // 暂存下一个节点current-next prev; // 反转当前节点的指针prev current; // 移动 prev 指针current next; // 移动 current 指针}*head prev;
}示例程序
程序1
#include stdio.h
#include stdlib.hstruct Node {int data;struct Node* next;
};struct Node* createNode(int data) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node));if (!newNode) {printf(内存分配失败\n);exit(1);}newNode-data data;newNode-next NULL;return newNode;
}void insertAtHead(struct Node** head, int data) {struct Node* newNode createNode(data);newNode-next *head;*head newNode;
}void deleteNode(struct Node** head, int key) {struct Node* temp *head;struct Node* prev NULL;if (temp ! NULL temp-data key) {*head temp-next;free(temp);return;}while (temp ! NULL temp-data ! key) {prev temp;temp temp-next;}if (temp NULL) return;prev-next temp-next;free(temp);
}void printList(struct Node* head) {struct Node* current head;while (current ! NULL) {printf(%d - , current-data);current current-next;}printf(NULL\n);
}int main() {struct Node* head NULL;insertAtHead(head, 1);insertAtHead(head, 2);insertAtHead(head, 3);printf(Created Linked List: );printList(head);deleteNode(head, 2);printf(Linked List after deletion of 2: );printList(head);return 0;
}输出结果
程序2
#include stdio.h
#include stdlib.h// 定义节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node));if (!newNode) {printf(内存分配失败\n);exit(1);}newNode-data data;newNode-next NULL;return newNode;
}// 头部插入
void insertAtHead(struct Node** head, int data) {struct Node* newNode createNode(data);newNode-next *head;*head newNode;
}// 尾部插入
void insertAtTail(struct Node** head, int data) {struct Node* newNode createNode(data);if (*head NULL) {*head newNode;return;}struct Node* temp *head;while (temp-next ! NULL) {temp temp-next;}temp-next newNode;
}// 删除节点
void deleteNode(struct Node** head, int key) {struct Node* temp *head;struct Node* prev NULL;if (temp ! NULL temp-data key) {*head temp-next;free(temp);return;}while (temp ! NULL temp-data ! key) {prev temp;temp temp-next;}if (temp NULL) return;prev-next temp-next;free(temp);
}// 查找节点
struct Node* searchNode(struct Node* head, int key) {struct Node* current head;while (current ! NULL) {if (current-data key) {return current;}current current-next;}return NULL;
}// 反转链表
void reverseList(struct Node** head) {struct Node* prev NULL;struct Node* current *head;struct Node* next NULL;while (current ! NULL) {next current-next;current-next prev;prev current;current next;}*head prev;
}// 打印链表
void printList(struct Node* head) {struct Node* current head;while (current ! NULL) {printf(%d - , current-data);current current-next;}printf(NULL\n);
}int main() {struct Node* head NULL;insertAtHead(head, 1);insertAtHead(head, 2);insertAtHead(head, 3);printf(初始链表: );printList(head);// 测试尾部插入insertAtTail(head, 4);printf(尾部插入 4 后的链表: );printList(head);// 测试删除节点deleteNode(head, 2);printf(删除节点 2 后的链表: );printList(head);// 测试查找节点struct Node* foundNode searchNode(head, 3);if (foundNode) {printf(找到节点 3\n);} else {printf(未找到节点 3\n);}// 测试反转链表reverseList(head);printf(反转后的链表: );printList(head);return 0;
}输出结果
