C语言实题讲解快速掌握单链表下

简介

单链表是常见的一种数据结构，可以存储任意数量的数据，并且可以高效的进行插入、删除和查找操作。本篇文章将介绍如何使用C语言实现单链表，以及如何应对在实现单链表时所遇到的常见问题。

实现过程

数据结构设计

为了实现单链表，我们需要设计一个数据结构来存储节点信息，一般包含两个成员，一个是数据域，用来存储实际的数据，另一个是指针域，用来存储下一个节点的地址。以下是一个基本的节点定义：

struct ListNode{
  int data;
  struct ListNode *next;
};

创建链表

创建一个单链表就相当于创建一个空的链表头节点，可以用以下代码实现：

struct ListNode *head = NULL;
head = (struct ListNode*)malloc(sizeof(struct ListNode));
if(NULL == head){
  printf("内存分配错误！");
}
head->next = NULL;

插入节点

单链表的插入操作包括两个部分，一个是创建一个新的节点并把要插入的值存储在数据域里面，另一个是把这个节点插入到链表中，具体实现如下：

struct ListNode *insert(struct ListNode *head, int i, int value){
  struct ListNode *newNode = NULL;
  // 遍历到第i个节点的前一个节点
  for(int j = 0; j < i-1 && NULL != head; j++){
    head = head->next;
  }
  // 创建新节点并存储数据
  newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
  if(NULL == newNode){
    printf("内存分配错误！");
  }
  newNode->data = value;
  // 把新节点插入到链表中
  newNode->next = head->next;
  head->next = newNode;
  return head;
}

删除节点

单链表的删除操作需要指定要删除的节点的地址以及其前一个节点的地址，实现如下：

struct ListNode *delete(struct ListNode *head, struct ListNode *node){
  // 遍历到要删除的节点的前一个节点
  while(head->next != node && NULL != head){
    head = head->next;
  }
  // 删除节点并重新链接链表
  if(NULL != head){
    head->next = node->next;
    free(node);
    node = NULL;
  }
  return head;
}

示例说明

示例1

现在我们需要创建一个包含10个元素的单链表，代码如下：

#include <stdio.h>
#include <stdlib.h>

struct ListNode{
  int data;
  struct ListNode *next;
};

struct ListNode *create_list(){
  struct ListNode *head = NULL;
  head = (struct ListNode*)malloc(sizeof(struct ListNode));
  if(NULL == head){
    printf("内存分配错误！");
  }
  head->next = NULL;
  struct ListNode *p = head;
  for(int i = 0; i < 10; i++){
    struct ListNode *newNode = NULL;
    newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(NULL == newNode){
      printf("内存分配错误！");
    }
    newNode->data = i;
    p->next = newNode;
    p = p->next;
  }
  return head;
}

int main(){
  struct ListNode *head = create_list();
  struct ListNode *p = head->next;
  while(NULL != p){
    printf("%d ", p->data);
    p = p->next;
  }
  return 0;
}

程序会输出：0 1 2 3 4 5 6 7 8 9。

示例2

现在我们需要在单链表中删除元素为5的节点，代码如下：

#include <stdio.h>
#include <stdlib.h>

struct ListNode{
  int data;
  struct ListNode *next;
};

struct ListNode *create_list(){
  struct ListNode *head = NULL;
  head = (struct ListNode*)malloc(sizeof(struct ListNode));
  if(NULL == head){
    printf("内存分配错误！");
  }
  head->next = NULL;
  struct ListNode *p = head;
  for(int i = 0; i < 10; i++){
    struct ListNode *newNode = NULL;
    newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(NULL == newNode){
      printf("内存分配错误！");
    }
    newNode->data = i;
    p->next = newNode;
    p = p->next;
  }
  return head;
}

struct ListNode *delete(struct ListNode *head, struct ListNode *node){
  while(head->next != node && NULL != head){
    head = head->next;
  }
  if(NULL != head){
    head->next = node->next;
    free(node);
    node = NULL;
  }
  return head;
}

int main(){
  struct ListNode *head = create_list();
  struct ListNode *p = head->next;
  while(NULL != p){
    if(p->data == 5){
      head = delete(head, p);
    }
    p = p->next;
  }
  p = head->next;
  while(NULL != p){
    printf("%d ", p->data);
    p = p->next;
  }
  return 0;
}

程序会输出：0 1 2 3 4 6 7 8 9。可以看到，元素为5的节点已经被删除了。