在C语言中,链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。链表的基本操作包括创建、插入、删除和遍历等。

下面是一个简单的链表节点结构体定义:

  1. struct Node {
  2. int data;
  3. struct Node* next;
  4. };

其中,data表示节点中的数据元素,next是指向下一个节点的指针。

  1. 创建链表:

链表的创建通常是通过定义一个指向链表头节点的指针,然后逐个添加节点来实现的。例如:

  1. struct Node* head = NULL; // 定义指向链表头节点的指针,初始化为空
  2. struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
  3. new_node->data = 1; // 设置节点中的数据元素
  4. new_node->next = NULL; // 设置节点的指针为空
  5. head = new_node; // 将头指针指向新节点
  1. 插入节点:

链表的插入操作通常是在链表的末尾或指定位置插入新节点。在链表末尾插入节点的操作比较简单,只需要将新节点的指针指向原链表的最后一个节点的指针即可。例如:

  1. struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
  2. new_node->data = 2; // 设置节点中的数据元素
  3. new_node->next = NULL; // 设置节点的指针为空
  4. if (head == NULL) { // 如果链表为空,将新节点设置为头节点
  5. head = new_node;
  6. } else { // 否则,将新节点插入到链表末尾
  7. struct Node* last = head;
  8. while (last->next != NULL) { // 遍历找到链表的最后一个节点
  9. last = last->next;
  10. }
  11. last->next = new_node; // 将最后一个节点的指针指向新节点
  12. }

要在指定位置插入节点,需要先找到插入位置的前一个节点,然后将前一个节点的指针指向新节点,新节点的指针指向下一个节点。例如:

  1. struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
  2. new_node->data = 3; // 设置节点中的数据元素
  3. new_node->next = NULL; // 设置节点的指针为空
  4. struct Node* prev = head; // 定义指向插入位置前一个节点的指针
  5. struct Node* curr = head->next; // 定义指向插入位置的指针,初始化为头节点的下一个节点
  6. while (curr != NULL && curr->data < 20) { // 遍历找到插入位置的前一个节点和插入位置的节点
  7. prev = curr;
  8. curr = curr->next;
  9. }
  10. prev->next = new_node; // 将前一个节点的指针指向新节点
  11. new_node->next = curr; // 将新节点的指针指向插入位置的节点(如果存在)
  1. 删除节点:

删除节点需要找到需要删除的节点,然后将前一个节点的指针指向下一个节点。例如:

  1. struct Node* delete_node = head; // 定义指向要删除节点的指针,初始化为头节点
  2. struct Node* prev = NULL; // 定义指向要删除节点前一个节点的指针
  3. struct Node* curr = head; // 定义指向要删除节点后一个节点的指针
  4. while (curr != NULL && curr != delete_node) { // 遍历找到要删除的节点和它前后的节点
  5. prev = curr;
  6. curr = curr->next;
  7. }
  8. if (prev == NULL) { // 如果要删除的是头节点
  9. head = delete_node->next; // 将头指针指向要删除节点的下一个节点
  10. } else { // 如果要删除的是中间节点或尾节点
  11. prev->next = delete_node->next; // 将前一个节点的指针指向要删除节点的下一个节点
  12. }
  13. free(delete_node); // 释放要删除的节点的内存空间
  1. 遍历链表:

遍历链表通常是通过定义一个指针指向链表头节点,然后循环遍历每个节点的数据元素。例如:

  1. struct Node* curr = head; // 定义指向当前节点的指针,初始化为头节点
  2. while (curr != NULL) { // 循环遍历每个节点
  3. printf(“%d “, curr->data); // 输出当前节点的数据元素
  4. curr = curr->next; // 将当前节点的指针指向下一个节点
  5. }

以上是链表的基本操作,链表的其他操作还包括反转链表、查找元素等。

  1. 反转链表:

反转链表需要定义一个指针指向当前节点,另一个指针指向下一个节点,然后将两个指针交换位置,直到两个指针相遇为止。例如:

  1. struct Node* reverse_list(struct Node* head) {
  2. struct Node* prev = NULL; // 定义指向当前节点前一个节点的指针
  3. struct Node* curr = head; // 定义指向当前节点的指针,初始化为头节点
  4. struct Node* next = NULL; // 定义指向当前节点后一个节点的指针
  5. while (curr != NULL) { // 遍历链表
  6. next = curr->next; // 将当前节点的指针指向下一个节点
  7. curr->next = prev; // 将当前节点的指针指向前一个节点
  8. prev = curr; // 将当前节点的前一个节点指针指向当前节点
  9. curr = next; // 将当前节点的指针指向下一个节点
  10. }
  11. return prev; // 返回反转后的链表头节点指针
  12. }
  1. 查找元素:

查找元素需要遍历链表,直到找到目标元素或遍历到链表末尾为止。例如:

  1. int search(struct Node* head, int target) {
  2. struct Node* curr = head; // 定义指向当前节点的指针,初始化为头节点
  3. while (curr != NULL) { // 遍历链表
  4. if (curr->data == target) { // 如果当前节点的数据元素等于目标元素
  5. return 1; // 返回1表示找到目标元素
  6. }
  7. curr = curr->next; // 将当前节点的指针指向下一个节点
  8. }
  9. return 0; // 返回0表示未找到目标元素
  10. }