数据结构与算法 完整版单链表(附GIF)

简介: 因为博主认为单链表是非常重要的数据结构,能够熟练使用单链表的话后面的数据结构会越学越轻松,所以博主就把这篇博客做的细致一点,不是很好懂的地方做成 gif 动画,希望大家能理解期中代码的含义学习链表的最好方法:

  因为博主认为单链表是非常重要的数据结构,能够熟练使用单链表的话后面的数据结构会越学越轻松,所以博主就把这篇博客做的细致一点,不是很好懂的地方做成 gif 动画,希望大家能理解期中代码的含义

学习链表的最好方法:

画图,必须是自己画图

下面给出博主的代码,相信大家仔细看的话是能看懂的.

部分细节在做 gif 时顾及不到,不要见怪了,主要是思想


#include<stdlib.h>
#include<stdio.h>
typedef struct _LinkList {
  int data; //数据域
  struct _LinkList *next; //指针域
  int length; //用来描述单链表中的元素的个数
}LinkList, LinkNode;
// 实现单链表的构建、数据添加(头插法和尾插法)、数据删除(包含了数据查找),数据的修改(包含了数据查找)、遍历的算法设计;
//单链表的初始化
bool initList(LinkList *Lq) {
  Lq->next = NULL;  //让指针域指向空,为了防止以外的错误
  if (!Lq) return false;
  Lq->data = -93501122;   //初始化头结点的数据域,
  Lq->length = 0;
  return true;
}
//显示页面
void menue() {
  printf("****************************************************************\n");
  printf("*********请选择你要进入的模块*********\n");
  printf("**1.使用头插法添加元素(最后输出的顺序与输入的顺序是相反的!**\n");
  printf("-----------------------------------\n");
  printf("**2.使用尾插法添加元素(最后输出的顺序与输入的顺序是相同的!**\n");
  printf("-----------------------------------\n");
  printf("**3.删除单链表中的元素\n");
  printf("-----------------------------------\n");
  printf("**4.修改单链表中的元素\n");
  printf("-----------------------------------\n");
  printf("**5.清屏,在现实欢迎界面\n");
  printf("-----------------------------------\n");
  printf("**0.退出程序");
  printf("****************************************************************\n\n\n");
}
//单链表的数据添加--->头插法
bool addList_font(LinkList *Lq, LinkNode *node) {
  if (!node) return false;  //如果之前的 node 分配地址失败的话,直接返回
  node->next = Lq->next;
  Lq->next = node;
  Lq->length++;
  return true;
}
//单链表的数据添加--->尾插法
bool addList_last(LinkList *Lq, LinkNode *node) {
  if (!node) return false;  //表示在分配给 node 空间的时候分配失败,那么我们后续的代码也就没了执行的必要
  LinkList *last = Lq;  //用来执行我们最后一个元素
  while (last->next) last = last->next;
  node->next = NULL;
  last->next = node;
  Lq->length++;
  return true;
}
//遍历
void Pint_add(LinkList *Lq) {
  LinkList *temp = Lq->next;
  printf("现在单链表一共有 %d 个元素,它们依次是: ",Lq->length);
  while (temp) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("\n");
  return;
}
//数据删除,先进行查找,如果找到要删除的元素就进行删除并且返回被删除的元素是第几个元素
bool list_del(LinkList *Lq, int element, int *index) {
  LinkNode *temp, *sq;  //temp是用来查询的 sq是用来删除的
  int i = 0;
  temp = Lq;
  sq = temp->next;
  if (Lq->next == NULL) return false;//如果链表里只有一个头结点,那么我们就直接返回
  while (sq) {  //当跳出循环时,要么没有找到我们要删除的元素,要么就是已经删除了我们要删除的元素返回了。
    if (sq->data == element && sq->next != NULL) {//当找到了要删除的元素而且该元素不是最后一个元素
      temp->next = sq->next;
      *index = i;
      Lq->length--;
      free(sq);
      sq->next = NULL;
      return true;
    } else if (sq->data == element && sq->next == NULL) {//找到了要删除的元素,并且该元素是最后一个元素
      temp->next = NULL;
      *index = i;
      Lq->length--;
      free(sq);
      sq->next = NULL;
      return true;
    } else {//在循环的时候没有找到,所以我们继续寻找
      temp = temp->next;
      sq = sq->next;
      i++;
    }
  }
  return false;
}
//数据修改
bool mov_del(LinkList *Lq, int oldelement,int newelement, int *index) {
  LinkList *temp;
  temp = Lq->next;  //让temp指向第一个节点
  while (temp) {  //当跳出循环时,要么是成功修改了要修改的值,返回是单链表的第几个元素,要么是没找到要修改的值
    if (temp->data == oldelement) {//找到了我们就修改它
      temp->data = newelement;
      return true;
    } else {//没找到,temp指向下一个节点再次寻找
      temp = temp->next;
    }
  }
  return false;
}
int main(void) {
  //单链表的创建
  LinkList *Lq = (LinkList*)malloc(sizeof(LinkList)); //给最初的 头结点分配一份空间
  LinkNode *node = NULL;
  int num=0;  //添加或删除元素的个数
  int element = 0;//删除元素的值,要修改元素的值
  int index=0;  //用来提示被删除元素是第几个元素,或者提示要被修改了的元素是第几个元素。
  int newelement = 0; //要修称为的新值
  int choice = 0; //用来选择进入那个模块
  //单链表的初始化
  if (initList(Lq)) {
    printf("单链表初始化成功!\n");
  } else {
    printf("单链表初始化失败!\n");
  }
  menue();
  while (1) {
    printf("请输入你想要进入的模块: ");
    scanf("%d", &choice);
    if (choice > 5 || choice < 0) { //判断用户的输入是否合法,如果输入不合法,那么就提示用户重新输入。
      printf("输入的值不合法!  请重新选择\n");
      continue;
    }
    switch (choice) { //进入我们对应的分支语句
    case 0: 
      //退出本程序
      return 0;
    case 1:
      //数据添加--->头插法
      printf("欢迎使用 头插法插入元素!! 请输入你想要添加的元素个数:  ");
      scanf("%d", &num);
      for (int i = 0; i < num; i++) {
        node = (LinkNode*)malloc(sizeof(LinkNode)); 
        //给我们要写入的结点分配空间这样才能把我们要添加的元素连接上去
        printf("请输入你要添加的元素的值: ");
        scanf("%d", &node->data);
        if (addList_font(Lq, node)) { //进入子函数
          printf("添加元素 %d 成功\n", node->data);
        } else {
          printf("添加元素失败!\n");
        }
      }
      Pint_add(Lq); //遍历
      break;
    case 2:
      //数据添加--->尾插法
      printf("欢迎使用 尾插法插入元素!!     请输入你想要添加的元素个数:  ");
      scanf("%d", &num);
      for (int i = 0; i < num; i++) {
        node = (LinkNode*)malloc(sizeof(LinkNode));
        //给我们要写入的结点分配空间这样才能把我们要添加的元素连接上去
        printf("请输入你要添加的元素的值: ");
        scanf("%d", &node->data);
        if (addList_last(Lq, node)) { //进入子函数
          printf("添加元素 %d 成功\n", node->data);
        } else {
          printf("添加元素失败!\n");
        }
      }
      Pint_add(Lq); //遍历
      break;
    case 3:
      //数据删除,先进行查找,如果找到要删除的元素就进行删除并且返回被删除的元素是第几个元素
      printf("请输入你想要删除的元素: ");
      scanf("%d", &element);
      if (list_del(Lq, element, &index)) {  //进入子函数,传入的参数依次是 单链表 要删除的元素 索引值
        printf("删除元素成功,该元素在单链表中是第 %d 个元素:\n ", index + 1);
      } else {
        printf("删除失败,单链表里没有该元素! \n");
      }
      Pint_add(Lq);
      break;
    case 4:
      //数据修改
      index = 0;  //先将我们的索引值置空
      printf("请输入你想要修改的元素: ");
      scanf("%d", &element);
      printf("请输入你想要修改称为的值: ");
      scanf("%d", &newelement);
      if (mov_del(Lq, element, newelement, &index)) { //进入子函数进行修改我们的单链表的值
        printf("修改元素成功,该元素在单链表中是第 %d 个元素:\n ", index);
      } else {
        printf("修改失败,单链表里没有该元素! \n");
      }
      Pint_add(Lq);
      break;
    case 5:
      system("cls");  //将屏幕清空 
      menue();  //显示欢迎界面,方便用户操作
      Pint_add(Lq); //显示现在单链表内的元素,方便用户观看
      break;
    }
  }
  //释放资源
  free(Lq);
  free(node);
  Lq = NULL;
  node = NULL;
  system("pause");
  return 0;
}
#include<stdlib.h>
#include<stdio.h>
typedef struct _LinkList {
  int data; //数据域
  struct _LinkList *next; //指针域
  int length; //用来描述单链表中的元素的个数
}LinkList, LinkNode;
// 实现单链表的构建、数据添加(头插法和尾插法)、数据删除(包含了数据查找),数据的修改(包含了数据查找)、遍历的算法设计;
//单链表的初始化
bool initList(LinkList *Lq) {
  Lq->next = NULL;  //让指针域指向空,为了防止以外的错误
  if (!Lq) return false;
  Lq->data = -93501122;   //初始化头结点的数据域,
  Lq->length = 0;
  return true;
}
//显示页面
void menue() {
  printf("****************************************************************\n");
  printf("*********请选择你要进入的模块*********\n");
  printf("**1.使用头插法添加元素(最后输出的顺序与输入的顺序是相反的!**\n");
  printf("-----------------------------------\n");
  printf("**2.使用尾插法添加元素(最后输出的顺序与输入的顺序是相同的!**\n");
  printf("-----------------------------------\n");
  printf("**3.删除单链表中的元素\n");
  printf("-----------------------------------\n");
  printf("**4.修改单链表中的元素\n");
  printf("-----------------------------------\n");
  printf("**5.清屏,在现实欢迎界面\n");
  printf("-----------------------------------\n");
  printf("**0.退出程序");
  printf("****************************************************************\n\n\n");
}
//单链表的数据添加--->头插法
bool addList_font(LinkList *Lq, LinkNode *node) {
  if (!node) return false;  //如果之前的 node 分配地址失败的话,直接返回
  node->next = Lq->next;
  Lq->next = node;
  Lq->length++;
  return true;
}
//单链表的数据添加--->尾插法
bool addList_last(LinkList *Lq, LinkNode *node) {
  if (!node) return false;  //表示在分配给 node 空间的时候分配失败,那么我们后续的代码也就没了执行的必要
  LinkList *last = Lq;  //用来执行我们最后一个元素
  while (last->next) last = last->next;
  node->next = NULL;
  last->next = node;
  Lq->length++;
  return true;
}
//遍历
void Pint_add(LinkList *Lq) {
  LinkList *temp = Lq->next;
  printf("现在单链表一共有 %d 个元素,它们依次是: ",Lq->length);
  while (temp) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("\n");
  return;
}
//数据删除,先进行查找,如果找到要删除的元素就进行删除并且返回被删除的元素是第几个元素
bool list_del(LinkList *Lq, int element, int *index) {
  LinkNode *temp, *sq;  //temp是用来查询的 sq是用来删除的
  int i = 0;
  temp = Lq;
  sq = temp->next;
  if (Lq->next == NULL) return false;//如果链表里只有一个头结点,那么我们就直接返回
  while (sq) {  //当跳出循环时,要么没有找到我们要删除的元素,要么就是已经删除了我们要删除的元素返回了。
    if (sq->data == element && sq->next != NULL) {//当找到了要删除的元素而且该元素不是最后一个元素
      temp->next = sq->next;
      *index = i;
      Lq->length--;
      free(sq);
      sq->next = NULL;
      return true;
    } else if (sq->data == element && sq->next == NULL) {//找到了要删除的元素,并且该元素是最后一个元素
      temp->next = NULL;
      *index = i;
      Lq->length--;
      free(sq);
      sq->next = NULL;
      return true;
    } else {//在循环的时候没有找到,所以我们继续寻找
      temp = temp->next;
      sq = sq->next;
      i++;
    }
  }
  return false;
}
//数据修改
bool mov_del(LinkList *Lq, int oldelement,int newelement, int *index) {
  LinkList *temp;
  temp = Lq->next;  //让temp指向第一个节点
  while (temp) {  //当跳出循环时,要么是成功修改了要修改的值,返回是单链表的第几个元素,要么是没找到要修改的值
    if (temp->data == oldelement) {//找到了我们就修改它
      temp->data = newelement;
      return true;
    } else {//没找到,temp指向下一个节点再次寻找
      temp = temp->next;
    }
  }
  return false;
}
int main(void) {
  //单链表的创建
  LinkList *Lq = (LinkList*)malloc(sizeof(LinkList)); //给最初的 头结点分配一份空间
  LinkNode *node = NULL;
  int num=0;  //添加或删除元素的个数
  int element = 0;//删除元素的值,要修改元素的值
  int index=0;  //用来提示被删除元素是第几个元素,或者提示要被修改了的元素是第几个元素。
  int newelement = 0; //要修称为的新值
  int choice = 0; //用来选择进入那个模块
  //单链表的初始化
  if (initList(Lq)) {
    printf("单链表初始化成功!\n");
  } else {
    printf("单链表初始化失败!\n");
  }
  menue();
  while (1) {
    printf("请输入你想要进入的模块: ");
    scanf("%d", &choice);
    if (choice > 5 || choice < 0) { //判断用户的输入是否合法,如果输入不合法,那么就提示用户重新输入。
      printf("输入的值不合法!  请重新选择\n");
      continue;
    }
    switch (choice) { //进入我们对应的分支语句
    case 0: 
      //退出本程序
      return 0;
    case 1:
      //数据添加--->头插法
      printf("欢迎使用 头插法插入元素!! 请输入你想要添加的元素个数:  ");
      scanf("%d", &num);
      for (int i = 0; i < num; i++) {
        node = (LinkNode*)malloc(sizeof(LinkNode)); 
        //给我们要写入的结点分配空间这样才能把我们要添加的元素连接上去
        printf("请输入你要添加的元素的值: ");
        scanf("%d", &node->data);
        if (addList_font(Lq, node)) { //进入子函数
          printf("添加元素 %d 成功\n", node->data);
        } else {
          printf("添加元素失败!\n");
        }
      }
      Pint_add(Lq); //遍历
      break;
    case 2:
      //数据添加--->尾插法
      printf("欢迎使用 尾插法插入元素!!     请输入你想要添加的元素个数:  ");
      scanf("%d", &num);
      for (int i = 0; i < num; i++) {
        node = (LinkNode*)malloc(sizeof(LinkNode));
        //给我们要写入的结点分配空间这样才能把我们要添加的元素连接上去
        printf("请输入你要添加的元素的值: ");
        scanf("%d", &node->data);
        if (addList_last(Lq, node)) { //进入子函数
          printf("添加元素 %d 成功\n", node->data);
        } else {
          printf("添加元素失败!\n");
        }
      }
      Pint_add(Lq); //遍历
      break;
    case 3:
      //数据删除,先进行查找,如果找到要删除的元素就进行删除并且返回被删除的元素是第几个元素
      printf("请输入你想要删除的元素: ");
      scanf("%d", &element);
      if (list_del(Lq, element, &index)) {  //进入子函数,传入的参数依次是 单链表 要删除的元素 索引值
        printf("删除元素成功,该元素在单链表中是第 %d 个元素:\n ", index + 1);
      } else {
        printf("删除失败,单链表里没有该元素! \n");
      }
      Pint_add(Lq);
      break;
    case 4:
      //数据修改
      index = 0;  //先将我们的索引值置空
      printf("请输入你想要修改的元素: ");
      scanf("%d", &element);
      printf("请输入你想要修改称为的值: ");
      scanf("%d", &newelement);
      if (mov_del(Lq, element, newelement, &index)) { //进入子函数进行修改我们的单链表的值
        printf("修改元素成功,该元素在单链表中是第 %d 个元素:\n ", index);
      } else {
        printf("修改失败,单链表里没有该元素! \n");
      }
      Pint_add(Lq);
      break;
    case 5:
      system("cls");  //将屏幕清空 
      menue();  //显示欢迎界面,方便用户操作
      Pint_add(Lq); //显示现在单链表内的元素,方便用户观看
      break;
    }
  }
  //释放资源
  free(Lq);
  free(node);
  Lq = NULL;
  node = NULL;
  system("pause");
  return 0;
}

如果看完代码感觉还是不好的话,可以观看博主做的 gif (可能不是很标准,但是博主就是这样理解的)


插入(头插法)


我们插入3个数 1 2 3


bool addList_font(LinkList *Lq, LinkNode *node) {
  if (!node) return false;  //如果之前的 node 分配地址失败的话,直接返回
  node->next = Lq->next;
  Lq->next = node;
  Lq->length++;
  return true;
}


插入1

20191118222438940.gif


插入2:

20191118222748910.gif

插入3:


image.gif

所以大家能理解为什么使用 头插法 遍历出来的顺序是与我们输入的顺序相反的了吧。


插入(尾插法)

我们插入3个数 1 2 3


bool addList_last(LinkList *Lq, LinkNode *node) {
  if (!node) return false;  //表示在分配给 node 空间的时候分配失败,那么我们后续的代码也就没了执行的必要
  LinkList *last = Lq;  //用来执行我们最后一个元素
  while (last->next) last = last->next;
  node->next = NULL;
  last->next = node;
  Lq->length++;
  return true;
}


插入 1:image.gif


插入2:


image.gif


插入3:

删除

删除我们也分为两个部分


  • 删除的元素是最后一个元素
  • 删除的元素不是最后一个元素
![bool list_del(LinkList *Lq, int element, int *index) {
  LinkNode *temp, *sq;  //temp是用来查询的 sq是用来删除的
  int i = 0;
  temp = Lq;
  sq = temp->next;
  if (Lq->next == NULL) return false;//如果链表里只有一个头结点,那么我们就直接返回
  while (sq) {  //当跳出循环时,要么没有找到我们要删除的元素,要么就是已经删除了我们要删除的元素返回了。
    if (sq->data == element && sq->next != NULL) {//当找到了要删除的元素而且该元素不是最后一个元素
      temp->next = sq->next;
      *index = i;
      Lq->length--;
      free(sq);
      sq->next = NULL;
      return true;
    } else if (sq->data == element && sq->next == NULL) {//找到了要删除的元素,并且该元素是最后一个元素
      temp->next = NULL;
      *index = i;
      Lq->length--;
      free(sq);
      sq->next = NULL;
      return true;
    } else {//在循环的时候没有找到,所以我们继续寻找
      temp = temp->next;
      sq = sq->next;
      i++;
    }
  }
  return false;
}

删除的元素是最后一个元素(太大了只能上传较差的,要看完整的请看我的百度网盘):

20191118233131579.gif

删除的元素不是最后一个元素:


image.gif


修改

bool mov_del(LinkList *Lq, int oldelement,int newelement, int *index) {
  LinkList *temp;
  temp = Lq->next;  //让temp指向第一个节点
  while (temp) {  //当跳出循环时,要么是成功修改了要修改的值,返回是单链表的第几个元素,要么是没找到要修改的值
    if (temp->data == oldelement) {//找到了我们就修改它
      temp->data = newelement;
      return true;
    } else {//没找到,temp指向下一个节点再次寻找
      temp = temp->next;
    }
  }
  return false;
}

修改比较简单就做一个就行了:image.gif


因为 gif 上传大小有限制,所以想看完整的视频可以点击我的百度网盘进行观看

希望大家能掌握单链表

如果觉得博主做的博客有用的话别忘了点赞加评论哦


目录
相关文章
|
4月前
【数据结构】单链表(长期维护)(1)
【数据结构】单链表(长期维护)(1)
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
49 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
28 1
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
39 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
23 0
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
712 6
|
2月前
|
存储
数据结构--单链表
数据结构--单链表