AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

一步一步教你从零开始写C语言链表

2023-09-08 97
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一步一步教你从零开始写C语言链表

为什么要学习链表？


链表主要有以下几大特性：


1、解决数组无法存储多种数据类型的问题。


2、解决数组中，元素个数无法改变的限制(C99的变长数组，C++也有变长数组可以实现)。


3、数组移动元素的过程中，要对元素进行大范围的移动，很耗时间，效率也不高。


先来感性的认识一下链表,我们先来认识下简单的链表:

640.png

从这幅图我们得出以下信息:


这个简单链表的构成：


头指针(Header)，若干个节点(节点包括了数据域和指针域)，最后一个节点要指向空。


实现原理：头指针指向链表的第一个节点，然后第一个节点中的指针指向下一个节点，然后依次指到最后一个节点，这样就构成了一条链表。


接下来看看链表的数据结构:

struct  list_node
{
  int data ; //数据域，用于存储数据
  struct list_node *next ; //指针，可以用来访问节点数据，也可以遍历，指向下一个节点
};

那么如何来创建一个链表的一个节点呢？


我们写个程序演示一下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  list_node
{
  int data ; 
  struct list_node *next ;
};
typedef struct list_node list_single ;  
int main(void)
{
  list_single *node = NULL ;          //1、首先，当然是定义一个头指针
  node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
  if(node == NULL){
    printf("malloc fair!\n");
  }
  memset(node,0,sizeof(list_single)); //3、清一下
  node->data = 100 ;            //4、给链表节点的数据赋值
  node->next = NULL ;                 //5、将链表的指针域指向空
  printf("%d\n",node->data);
  free(node);
  return 0 ;
}

   那么，这仅仅只是创建一个链表中的一个节点，为了好看，我们把创建节点封装成函数，以后想创建多少个节点，我们就可以反复调用一个函数来创建，会很方便:

list_single *create_list_node(int data)
{
  list_single *node = NULL ;
  node = (list_single *)malloc(sizeof(list_single));
  if(node == NULL){
    printf("malloc fair!\n");
  }
  memset(node,0,sizeof(list_single));
  node->data = 100 ;
  node->next = NULL ;
  return node ;
}

接下来在程序上完成的程序:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  list_node
{
  int data ; 
  struct list_node *next ;
};
typedef struct list_node list_single ;  
list_single *create_list_node(int data)
{
  list_single *node = NULL ;
  node = (list_single *)malloc(sizeof(list_single));
  if(node == NULL){
    printf("malloc fair!\n");
  }
  memset(node,0,sizeof(list_single));
  node->data = data;
  node->next = NULL ;
  return node ;
}
int main(void)
{
  int data = 100 ;
  list_single *node_ptr = create_list_node(data); //创建一个节点
  printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
  printf("node_ptr->next=%d\n",node_ptr->next);  
  free(node_ptr);
  return 0 ;
}

执行结果 ：

640.jpg

这样我们就完成一个链表节点的创建了，那么它现在的样子如下图：


链表的结构里，数据存储了100，因为这个链表只有一个节点，所以它的指针域指向了NULL。

640.jpg

上面只是建立一个单链表的基本雏形，接下来咱们再来增加一点难度。如果创建多个单链表节点，实现单链表的增删改查？把单链表应用起来。

1、首先定义一个单链表的数据结构

640.png

创建节点函数原型可定义如下：

struct list *create_node(int data) ;

如何创建单链表的节点，主要分以下步骤:

(1)给当前的每个节点的数据结构配置定量的空间大小

ep : struct list *node = malloc(sizeof(struct list));

(2)清节点数据(由于结构体变量在未初始化的时候，数据是脏的)

ep : memset(node,0,sizeof(struct list));

(3)给节点初始化数据

ep : node->id = data ;

(4)将该节点的指针域设置为NULL

ep : node->next = NULL ;

2、单链表的尾插：

尾插节点函数原型可定义如下：

640.png

如何将当前链表和新的节点相连接？只要实现：

header->next = new

尾插流程如下：


(1)获取当前节点的位置，也就是访问头节点

ep : struct list *p = header ;

(2)判断是否为最后一个节点，如果不是，移动到下一个节点，如果是，将数据插入尾部。

ep : while(NULL != p->next) p = p->next ;
        p->next = new ;

3、单链表的头插

640.png

很好理解，头插就是把新的节点插在原来的节点和原来节点的下一个节点之间的一个节点。如图，新的节点插在头节点和节点1。

所以可以推出头插流程如下：

(1)获取当前节点的位置，也就是访问头节点

ep : struct list *p = header ;

(2)新的节点的下一个节点设置为原来头节点的下一个节点(第一个节点)

ep : new->next = p->next ;

(3)原来的头节点的下一个节点设置为现在新插入的头节点

ep : p->next = new ;

4、单链表的遍历

640.png

如图为一条单向链表的模型，看图知道该链表由头节点和若干个节点组成，最后一个节点(尾节点)为NULL 。

从图中可以得出信息，如果我们要打印出各个节点的数据，要考虑以下问题：

(1)需要打印头节点吗？(头节点肯定是不用打印的，因为这是我们为了操作方便而设置的一个节点)。

(2)这条链表有多少个节点我们怎么知道？(通过判断该链表是否已经到达了尾节点，标志就是NULL)

那么可以得到流程如下：

(1)获取当前节点的位置，也就是访问头节点

ep : struct list *p = header ;

(2)由于头节点我们不需要去打印它，这时候，初始化打印的节点需要从第一个节点开始。

ep : p = p->next ;

(3)判断是否为最后一个节点，如果不是，先打印第一个节点的数据(1)，然后移动到下一个节点(2),重复这两个步骤。

  如果是最后一个节点，直接打印数据即可。

while(NULL != p->next){ printf("node:%d\n",p->data) ; p = p->next ;}
    printf("node:%d\n",p->data);

   当然还可以一句代码解决，这样就达到了先偏移，后取数据。

while(NULL != p->next){ p = p->next ; printf("node:%d\n",p->data) ; }

5、单链表的删除

删除节点的函数原型可定义如下：

int detele_list_node(struct list *pH , int data);

单向链表的删除要考虑两种情况，一种的普通节点的删除(当然，头节点不能算)

还有一种是尾节点的前一个节点的删除情况，注意，删除完节点还需要释放对应节点的内存空间。

640.png

640.png

删除节点的设计流程：

(1)先定义两个指针，一个表示当前的节点，另一个表示当前节点的上一个节点。

ep : struct list *p = header ;  //当前节点
         struct list *prev = NULL ; //当前节点的上一个节点

(2)遍历整个链表，同时保存当前节点的前一个节点

ep : while(NULL != p->next)
        { 
          //保存了当前的节点的前一个节点
          prev = p ;  
          //保存当前偏移的节点
          p = p->next ; 
          return 0 ;
        }

(3)在遍历的过程中查找要删除的数据

 ep : while(NULL != p->next)
        { 
          //保存了当前的节点的前一个节点
          prev = p ;  
          //保存当前偏移的节点
          p = p->next ; 
          //查找到了数据
          if(p->id == data)
          {
          }
          return 0 ;
        }

(4)查找到了数据后，分两种情况删除

ep : 普通节点的删除
        if(p->id == data)
        {
            prev->next = p->next ;
            free(p);
        }
    ep : 考虑尾节点的下一个节点为NULL的节点删除
        if(p->id == data)
        {
            if(p->next == NULL)
            {
                prev->next = NULL ;
                free(p);
            }
        }

6、单链表的逆序

640.png

逆序步骤：

640.jpg

单链表的基本操作流程咱们基本搞懂了，下面写一个程序，这将会变得非常非常的简单。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct slist
{
  int id ;
  struct slist *next ;      
}L;
//创建一个节点 
L *create_node(int data)
{
  //给每个节点分配结构体一样的空间大小 
  L *p = malloc(sizeof(L));
  if(NULL == p)
  {
    printf("malloc error!\n");
    return NULL ;
  }
  //由于结构体在未初始化的时候一样是脏数据，所以要清 
  memset(p,0,sizeof(L));
  //初始化第一个节点 
  p->id = data ; 
  //将节点的后继指针设置为NULL 
  p->next = NULL ;
}
//链表的尾插 
void tail_insert(L *pH , L *new)
{
  //获取当前的位置 
  L *p = pH ; 
  //如果当前位置的下一个节点不为空 
  while(NULL != p->next)
  {
    //移动到下一个节点 
    p = p->next ;
  }
  //如果跳出以上循环，所以已经到了NULL的这个位置
  //此时直接把新插入的节点赋值给NULL这个位置 
  p->next = new ;
}
//链表的头插 
void top_insert(L *pH , L *new)
{
  L *p = pH ;
  new->next = p->next ;
  p->next = new ;
}
//链表的遍历 
void Print_node(L *pH)
{
  //获取当前的位置 
  L *p = pH ;
  //获取第一个节点的位置 
  p = p->next ;
  //如果当前位置的下一个节点不为空 
  while(NULL != p->next)
  {
    //(1)打印节点的数据 
    printf("id:%d\n",p->id);
    //(2)移动到下一个节点,如果条件仍为真，则重复(1)，再(2) 
    p = p->next ;
  }
  //如果当前位置的下一个节点为空，则打印数据
  //说明只有一个节点 
  printf("id:%d\n",p->id);
}
//删除链表中的节点 
int detele_list_node(L * pH , int data)
{
  //获取当前头节点的位置 
  L *p = pH ;
  L *prev = NULL;
  while(NULL != p->next)
  {
    //保存当前节点的前一个节点的指针 
    prev = p ;
    //然后让当前的指针继续往后移动 
    p = p->next ;   
    //判断，找到了要删除的数据  
    if(p->id == data)
    {
      //两种情况，一种是普通节点，还有一种是尾节点
      if(p->next != NULL)  //普通节点的情况 
      {
        prev->next = p->next ;
        free(p);
      }
      else //尾节点的情况 
      {
        prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空 
        free(p); 
      }
      return 0  ;
    }
  }
  printf("没有要删除的节点\n");
  return -1 ;
}
void trave_list(L * pH)
{
  //保存第一个节点的位置 
  L *p = pH->next;
  L *pBack;
  int i = 0 ;
  if(p->next == NULL || p == NULL)
    return ;
  while(NULL != p->next) //遍历链表 
  {
    //保存第一个节点的下一个节点 
    pBack = p->next ; 
    //找到第一个有效节点,其实就是头指针的下一个节点 
    if(p == pH->next) 
    {
      //第一个有效节点就是最后一个节点，所以要指向NULL 
      p->next = NULL ; 
    } 
    else
    {
      /*
      new->next = p->next ;
      p->next = new ;
      */
      p->next = pH->next ; //尾部连接 
    }
    pH->next = p ; //头部连接 
    p = pBack ; //走下一个节点 
  }
  top_insert(pH,p); //插入最后一个节点 
}
int main(int argc , char **argv) 
{
  //创建第一个节点 
  int i ;
  L *header = create_node(0); 
  for(i = 1 ; i < 10 ; i++)
  {
    tail_insert(header,create_node(i));
  }
  Print_node(header);
  detele_list_node(header,5);
  putchar('\n');
  Print_node(header);
  putchar('\n');
  trave_list(header);
  Print_node(header);
  return 0 ;
}

运行结果：

640.jpg

当然，单链表存在一定的弊端，就是查找数据和删除数据的时候比较麻烦，而双链表的出现就是为了解决它的弊端：

双链表的引入是为了解决单链表的不足：

(1)双链表可以往前遍历，也可以往后遍历，具有两个方向

双链表的节点 = 有效数据 + 两个指针(分别指向前一个节点和后一个节点)

双向链表的图形结构描述:

640.png

struct double_list                                   struct double_list
{                                                            {
    数据域;                  ep :------->                   int data ;
    指针域(前向指针) ;                                   struct double_list *prev ;
    指针域(后向指针) ;                                   struct double_list *next ;
};                                                             };

1、双向链表的创建

struct list *create_node(int data) ;

创建步骤(与单链表类似，就是多了一个指针):

(1)给节点申请空间：

ep : struct double_list *p = malloc(sizeof(struct double_list));

(2)初始化数据域

ep : p->data = data ;

(3)初始化指针域

ep : p->prev = NULL ; 
        p->next = NULL ;

2、双向链表的尾插

双向链表尾插节点的函数可以定义如下：

void double_list_tail_insert(struct double_list *header , struct double_list *new) ;

尾插图示操作：


尾插的步骤：


(1)找到链表的尾节点

ep : 和单链表差不多
        DL *p = header ;
        while(NULL != p->next)
            p = p->next ;

(2)将新的节点连接到尾节点的后面成为新的节点

  1.原来的next指针指向新节点的首地址。           

p->next = new ;

  2.新节点的prev指针指向原来的尾节点的首地址。

new->prev = p;

3、双向链表的头插

双向链表头插节点的函数可以定义如下：

void double_list_top_insert(struct double_list *header , struct double_list *new) ;

640.jpg

4、双向链表的遍历

4.1 正向遍历

void double_list_for_each(DL *header)

   步骤：和单链表完全一致，没什么好写的。


4.2 反向遍历

void double_list_for_each_nx(DL *header)

   步骤：(1)和单链表一样，先循环找到最后一个节点的地址

         (2)再依靠prev指针循环往前移动

            2.1 先打印最后一个数据

ep : printf("%d ",p->data);

            2.2 向前循环遍历        

ep : p = p->prev ;

判断条件：

header->prev != p->prev,

            header保存的是头节点的地址,

            header->prev保存的是头节点的prev的地址,

            header->next保存的是头节点的next的地址,

            头节点在创建的时候:

header->prev = NULL ;
             header->next = NULL ;

            所以这个条件这样写header->prev = NULL也是对的。

5、双向链表节点的删除

假设需要删除节点1：    

   首先:

   (1)获取当前节点的地址： 

ep : p = header;

   (2)遍历所有的节点，找到要删除的节点：

ep : 
        while(NULL != p->next)
        {
            p = p->next ;
            if(p->data == data)
            {
            }
        }

   (3)找到要删除的数据以后，需要做判断，判断两种情况，这和单链表差不多

   3.1 如果找到当前节点的下一个节点不为空

   3.1.1    

       那就把当前节点的prev节点指向要删除的这个节点的prev

       因为当前的prev节点保存的是要删除的上一个节点的指针 

p->next->prev = p->prev ;

   3.1.2    

       然后将当前节点的prev指针(也就是上一个节点的指针)指向当前节点(要删除的)的下一个节点:

p->prev->next = p->next ;

   3.1.3    

       最后释放删除指针的空间： 

free(p);

   3.2 如果找到当前节点的下一个节点为空

   3.2.1  

   直接把当前指针(要删除的节点)的prev指针(保存着当前指针的上一个节点的地址)的下一个next指针设置为空。

p->prev->next = NULL ;

   3.2.2

   将删除的指针的空间释放:

free(p);

   看来，双链表学起来比单链表容易多了！确实啊，多了一个方向，操作起来就更加容易了，但是多了一个方向，一维多了一个指针，相比增加了一定的复杂度，但是，只要牢记prev指针和next指针的指向，那么，手画一图，代码即可写出！

下面给一个案例实现一下双向链表：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//创建一个双链表的数据结构
typedef struct __double_list
{
  int data ;
  struct __double_list *prev ;
  struct __double_list *next ;
}DL ; 
//创建双向链表并插入一个节点 
DL *create_dl_node(int data)
{
  DL *p = malloc(sizeof(DL));
  if(NULL == p)
  {
    printf("create dl node fair!\n");
    return NULL ;
  }
  //初始化数据 
  p->data = data ;
  //初始化指针 
  p->next = NULL ;
  p->prev = NULL ;
}
//双向链表的尾插 
void double_list_tail_insert(DL *header , DL *new)
{
  //取得当前节点的地址 
  DL *p = header ;
  //找到链表的尾节点 
  while(NULL != p->next)
  {
    //找不到接着找 
    p = p->next ;
  }
  //找到了尾节点，指向新节点的首地址 
  p->next = new ;
  //新节点的prev指针指向原来的尾节点的首地址。
  new->prev = p;
}
//双向链表的头插(也就是插在两个节点之间的插入方式)
void double_list_top_insert(DL *header , DL *new)
{
  //新节点的next指针指向原来的节点一的地址
  new->next = header->next ; 
  //判断当前节点的下一个节点的地址是否为空
  if(NULL != header->next) 
    header->next->prev = new ; //节点1的prev指针指向新节点的地址 
  header->next = new ;
  new->prev = header ;
}
//双向链表的正向遍历 
void double_list_for_each(DL *header)
{
  DL *p = header ;
  while(NULL != p->next)
  {
    p = p->next ;
    printf("%d ",p->data);
  }
}
//双向链表的反向遍历 
void double_list_for_each_nx(DL *header)
{
  DL *p = header ;
  //先找到尾节点
  while(NULL != p->next)
  {
    p = p->next ; 
  } 
  //已经找到了尾节点，向前遍历，注意，遍历到头节点之前
  //限制条件: != 头结点 
  while(NULL != p->prev)
  {
    printf("%d ",p->data);
    p = p->prev ;
  }
}
//双向链表节点的删除
int double_list_delete_node(DL *header , int data)
{
  //取得当前节点 
  DL *p = header;
  //遍历所有的节点 
  while(NULL != p->next)
  {
    p = p->next ;
    //找到了对应要删除的数据了 
    if(p->data == data)
    {
      //一样存在两种情况
      //(1)当前节点的下一个节点不为空
      if(p->next != NULL)
      {
        //那就把当前节点的prev节点指向要删除的这个节点的prev
        //因为当前的prev节点保存的是要删除的上一个节点的指针 
        p->next->prev = p->prev ;
        //还要指定它的next节点 
        p->prev->next = p->next ;
        free(p);
      }
      //(2)当前节点的下一个节点为空 
      else
      {
        //把 
        p->prev->next = NULL ;
        free(p); 
      }
      return 0 ;
    }
  }
  printf("\n没有找到对应要删除的节点，或者节点已经被删除！\n");
  return -1 ; 
} 
int main(void)
{
  int i ;
  DL *header = create_dl_node(0);
  for(i = 0 ; i < 10 ; i++)
  {
    //双向链表的尾插 
    //double_list_tail_insert(header,create_dl_node(i));
    //双向链表的头插 
    double_list_top_insert(header,create_dl_node(i));
  }
  //双向链表的正向遍历 
  printf("双向链表的正向遍历:");
  double_list_delete_node(header,5);
  double_list_for_each(header);
//  double_list_delete_node(header,9);
  double_list_delete_node(header,5);
  putchar('\n');
  printf("双向链表的反向遍历:");
  double_list_for_each_nx(header);
  return 0 ;
}

运行结果：

640.jpg

文章标签：
C语言
存储
C++
关键词：
链表c语言
C语言链表
morixinguan
目录
相关文章
ephemerals__
|
20天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
48 4
c的前世今生
|
1月前
|
存储 缓存 C语言
C语言：链表和数组有什么区别
C语言中，链表和数组是两种常用的数据结构。数组是一种线性结构，元素在内存中连续存储，通过下标访问，适合随机访问且大小固定的情况。链表由一系列不连续的节点组成，每个节点存储数据和指向下一个节点的指针，适用于频繁插入和删除操作的场景，链表的大小可以动态变化。
c的前世今生
24 2
石小浪♪
|
1月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装，包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
石小浪♪
27 0
石小浪♪
|
1月前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装，包括节点的创建、链表的初始化、数据的插入和删除，以及链表的打印等功能。
石小浪♪
17 1
石小浪♪
|
1月前
|
C语言
C语言结构体链式结构之有头单链表
文章提供了一个C语言实现的有头单链表的完整代码，包括创建链表、插入、删除和打印等基本操作。
石小浪♪
23 1
ephemerals__
|
20天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
39 0
石小浪♪
|
1月前
|
测试技术 C语言
单链表之无头链表(C语言版)
本文详细介绍了使用C语言实现无头单链表的方法，包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除，以及链表的打印等功能。文章通过具体的代码示例，展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除，以及如何清空和销毁链表。
石小浪♪
33 0
单链表之无头链表(C语言版)
倔强的石头_
|
5月前
|
存储 缓存 前端开发
【数据结构/C语言】深入理解 双向链表
【数据结构/C语言】深入理解 双向链表
倔强的石头_
40 0
石小浪♪
|
1月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表，并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现，以及一个示例程序来演示这些操作。
石小浪♪
25 0
小徐在进步
|
2月前
|
存储 C语言
C语言程序设计核心详解 第九章 结构体与链表概要详解
本文档详细介绍了C语言中的结构体与链表。首先，讲解了结构体的定义、初始化及使用方法，并演示了如何通过不同方式定义结构体变量。接着，介绍了指向结构体的指针及其应用，包括结构体变量和结构体数组的指针操作。随后，概述了链表的概念与定义，解释了链表的基本操作如动态分配、插入和删除。最后，简述了共用体类型及其变量定义与引用方法。通过本文档，读者可以全面了解结构体与链表的基础知识及实际应用技巧。
小徐在进步
49 3