在C语言中,链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。链表的基本操作包括创建、插入、删除和遍历等。
下面是一个简单的链表节点结构体定义:
- struct Node {
- int data;
- struct Node* next;
- };
其中,data表示节点中的数据元素,next是指向下一个节点的指针。
- 创建链表:
链表的创建通常是通过定义一个指向链表头节点的指针,然后逐个添加节点来实现的。例如:
- struct Node* head = NULL; // 定义指向链表头节点的指针,初始化为空
- struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
- new_node->data = 1; // 设置节点中的数据元素
- new_node->next = NULL; // 设置节点的指针为空
- head = new_node; // 将头指针指向新节点
- 插入节点:
链表的插入操作通常是在链表的末尾或指定位置插入新节点。在链表末尾插入节点的操作比较简单,只需要将新节点的指针指向原链表的最后一个节点的指针即可。例如:
- struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
- new_node->data = 2; // 设置节点中的数据元素
- new_node->next = NULL; // 设置节点的指针为空
- if (head == NULL) { // 如果链表为空,将新节点设置为头节点
- head = new_node;
- } else { // 否则,将新节点插入到链表末尾
- struct Node* last = head;
- while (last->next != NULL) { // 遍历找到链表的最后一个节点
- last = last->next;
- }
- last->next = new_node; // 将最后一个节点的指针指向新节点
- }
要在指定位置插入节点,需要先找到插入位置的前一个节点,然后将前一个节点的指针指向新节点,新节点的指针指向下一个节点。例如:
- struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
- new_node->data = 3; // 设置节点中的数据元素
- new_node->next = NULL; // 设置节点的指针为空
- struct Node* prev = head; // 定义指向插入位置前一个节点的指针
- struct Node* curr = head->next; // 定义指向插入位置的指针,初始化为头节点的下一个节点
- while (curr != NULL && curr->data < 20) { // 遍历找到插入位置的前一个节点和插入位置的节点
- prev = curr;
- curr = curr->next;
- }
- prev->next = new_node; // 将前一个节点的指针指向新节点
- new_node->next = curr; // 将新节点的指针指向插入位置的节点(如果存在)
- 删除节点:
删除节点需要找到需要删除的节点,然后将前一个节点的指针指向下一个节点。例如:
- struct Node* delete_node = head; // 定义指向要删除节点的指针,初始化为头节点
- struct Node* prev = NULL; // 定义指向要删除节点前一个节点的指针
- struct Node* curr = head; // 定义指向要删除节点后一个节点的指针
- while (curr != NULL && curr != delete_node) { // 遍历找到要删除的节点和它前后的节点
- prev = curr;
- curr = curr->next;
- }
- if (prev == NULL) { // 如果要删除的是头节点
- head = delete_node->next; // 将头指针指向要删除节点的下一个节点
- } else { // 如果要删除的是中间节点或尾节点
- prev->next = delete_node->next; // 将前一个节点的指针指向要删除节点的下一个节点
- }
- free(delete_node); // 释放要删除的节点的内存空间
- 遍历链表:
遍历链表通常是通过定义一个指针指向链表头节点,然后循环遍历每个节点的数据元素。例如:
- struct Node* curr = head; // 定义指向当前节点的指针,初始化为头节点
- while (curr != NULL) { // 循环遍历每个节点
- printf(“%d “, curr->data); // 输出当前节点的数据元素
- curr = curr->next; // 将当前节点的指针指向下一个节点
- }
以上是链表的基本操作,链表的其他操作还包括反转链表、查找元素等。
- 反转链表:
反转链表需要定义一个指针指向当前节点,另一个指针指向下一个节点,然后将两个指针交换位置,直到两个指针相遇为止。例如:
- struct Node* reverse_list(struct Node* head) {
- struct Node* prev = NULL; // 定义指向当前节点前一个节点的指针
- struct Node* curr = head; // 定义指向当前节点的指针,初始化为头节点
- struct Node* next = NULL; // 定义指向当前节点后一个节点的指针
- while (curr != NULL) { // 遍历链表
- next = curr->next; // 将当前节点的指针指向下一个节点
- curr->next = prev; // 将当前节点的指针指向前一个节点
- prev = curr; // 将当前节点的前一个节点指针指向当前节点
- curr = next; // 将当前节点的指针指向下一个节点
- }
- return prev; // 返回反转后的链表头节点指针
- }
- 查找元素:
查找元素需要遍历链表,直到找到目标元素或遍历到链表末尾为止。例如:
- int search(struct Node* head, int target) {
- struct Node* curr = head; // 定义指向当前节点的指针,初始化为头节点
- while (curr != NULL) { // 遍历链表
- if (curr->data == target) { // 如果当前节点的数据元素等于目标元素
- return 1; // 返回1表示找到目标元素
- }
- curr = curr->next; // 将当前节点的指针指向下一个节点
- }
- return 0; // 返回0表示未找到目标元素
- }