用C语言实现单链表的基本操作(附有完整代码)

简介: 用C语言实现单链表的基本操作(附有完整代码)

导语:

无论是顺序存储结构还是链式存储结构,在内存中进行存放元素的时候,不仅需要存放该元素的相关信息,还需要存放该元素和其他元素之间的关系,而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系,不需要额外的信息去表达元素和元素之间的关系,而对于链式存储这种非顺序存储的结构,需要额外附加指针去表示这种关系。


单链表

每个结点除了存放数据元素外,还要存储指向下一个节点的指针。

单链表的特点:

优点:不要求大片连续空间,改变容量方便

缺点:不可随机存取,要耗费一定空间存放指针


定义:

typedef struct LNode {
  int data;
  struct LNode* next;//指针指向下一个节点,指针的类型为节点类型;
}*LinkNode;//声明*LinkNode为结构体指针类型


除了上述这种方法外,我们还可以先先声明LinkNode为结构体类型,在使用该类型的时候,将对应的变量定义为指针即可。

单链表分为带头结点和不带头结点,我们一般主要学习带头结点的。


初始化操作:

在所有的操作之前,我们首先需要建立一个空的单链表,那么首先需要做的就是分配头结点。

void InistLinkNode(LinkNode& L) {
  L = (LNode*)malloc(sizeof(LNode));//分配头结点
  L->next = NULL;
}

头插法:

“头插法”顾名思义就是将元素插入到头结点之后,插入一次好像和我们通常所讲的插入没什么区别,但多次这样插到头结点之后,也就是“第一个真正的节点”,那么是不是会产生一种现象,它最终的存储数据和我们所插入时的顺序是相反的。

void InsertLinkNode(LinkNode& L) {
  LNode* s;
  int x,Length;
  printf("请输入你要插入的元素个数:");
  scanf("%d", &Length);
  printf("请输入你要插入的元素:\n");
  for (int j = 0; j < Length; j++) {
    s = (LNode*)malloc(sizeof(LNode));//每插入一个元素之前,都需要给它分配节点空间
    scanf("%d", &x);
    s->data = x;
    s->next = L->next;
    L->next = s;
  }
} 

通过程序验证以下:

尾插法:

“尾插法”顾名思义就是将元素插入到表尾,也就是我们普通的插入,那么怎么要找到表尾的位置呢?在顺序表中,我们完全可以利用它顺序存储结构的天然特性,通过下标即可以找到,但是单链表是没有办法的,我们只有两种方式,要么循环遍历,要么尝试在表尾的地方做个标记。


那么那种方法是好的呢?


答案是第二种!循环遍历的方式,如果只插入一个元素看似没什么问题,但如果多次的重复遍历循环无疑增加了时间复杂度,这显然不是好的方法。


第二个方法就不存在时间复杂度的问题,只需要在表尾位置做个标记,使它永远指向表尾即可。

void TailInsertLinkNode(LinkNode& L) {
  LNode* s,*r;
  int x,Length;
  r = L;//r为表尾指针
  printf("请输入你要插入的元素个数:");
  scanf("%d", &Length);
  printf("请输入你要插入的元素:\n");
  for (int j = 0; j < Length; j++) {
    s = (LNode*)malloc(sizeof(LNode));
    scanf("%d", &x);
    s->data = x;
    r->next = s;
    r = s;//s为当前的表尾指针,将他的值赋值给r----使r永远指向表尾
  }
  printf("\n");
  r->next = NULL;
}


删除第i个元素:

既然要删除某个元素,那么首先我们需要保证这个元素是非NULL,其次,我们还需要保证它前面的那个节点也是非NULL,为什么呢?因为如果将该元素从链表中删除后,只有前面节点非NULL的情况下,才可以实现后续元素和前面子表的连接。

void DeleteLinkNode(LinkNode& L) {
  int x, j = 0,e;
  printf("请输入你要删除的元素位序:\n");
  scanf("%d", &x);
  LNode*p = L;
  while (p != NULL && j < x - 1) {//寻找要删除元素前的元素
    p = p->next;
    j++;
  }
  if (p == NULL)
  {
    printf("不存在我们要删除的元素!");
  }
  if (p->next == NULL)//判断该要删除的节点是否为NULL
  {
    printf("不存在我们要删除的元素!");
  }
  LNode* q = p->next;//q为我们要删除的节点
  e = q->data;
  p->next = q->next;
  free(q);//需要及时的将删除了的元素空间进行释放
}


其他的基本操作都是很常规化的,这里就不单独的进行解释了,需要注意的点,我会在文章结尾部分的完整代码的注释中展出。

在第i个位置插入:

void IncreaseLinkNode(LinkNode& L) {
  printf("请输入你要插入的元素和位序:(元素和位序之间用逗号隔开)\n");
  int x, j = 0, e;
  scanf("%d,%d",&e, &x);
  LNode* s = L, * r= (LNode*)malloc(sizeof(LNode));
  while (j < x-1  && s != NULL) {
    j++;
    s = s->next;
  }
  r->data = e;
  r->next = s->next;
  s->next = r;
}


如下所示的代码顺序不能发生改变,否则会出现无法和后面的节点;

r->next = s->next;
s->next = r;

完整代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode* next;
}*LinkNode;
//初始化
void InistLinkNode(LinkNode& L) {
  L = (LNode*)malloc(sizeof(LNode));//分配头结点
  L->next = NULL;
}
//头插法
void InsertLinkNode(LinkNode& L) {
  LNode* s;
  int x,Length;
  printf("请输入你要插入的元素个数:");
  scanf("%d", &Length);
  printf("请输入你要插入的元素:\n");
  for (int j = 0; j < Length; j++) {
    s = (LNode*)malloc(sizeof(LNode));
    scanf("%d", &x);
    s->data = x;
    s->next = L->next;
    L->next = s;
  }
} 
//尾插法
void TailInsertLinkNode(LinkNode& L) {
  LNode* s,*r;
  int x,Length;
  r = L;
  printf("请输入你要插入的元素个数:");
  scanf("%d", &Length);
  printf("请输入你要插入的元素:\n");
  for (int j = 0; j < Length; j++) {
    s = (LNode*)malloc(sizeof(LNode));
    scanf("%d", &x);
    s->data = x;
    r->next = s;
    r = s;
  }
  printf("\n");
  r->next = NULL;
}
//输出单链表
void PrintLinkNode(LinkNode& L)
{
  LNode* s=L->next;
  printf("单链表元素如下:\n");
  while (s != NULL) {
    printf("%d", s->data);
    s =s->next;
  }
  printf("\n");
}
//求线性表长度
void lengthLinkNode(LinkNode& L)
{
  LNode* s = L->next;
  int n=0;
  while (s != NULL) {
    n++;
    s = s->next;
  }
  printf("单链表长度为:%d",n);
  printf("\n");
}
//取第i个元素
void GetElemLinkNode(LinkNode& L) {
  printf("请输入你要查找的元素位序:\n");
  int i, j = 0;
  LNode* s=L;
  scanf("%d", &i);
  while (j < i && s != NULL) {
    j++;
    s = s->next;
  }
  if (s == NULL) {
    printf("不存在我们要查找的元素!");
  }
  else {
    printf("元素位序为%d的元素是%d",i, s->data);
  }
  printf("\n");
}
//删除第i个元素
void DeleteLinkNode(LinkNode& L) {
  int x, j = 0,e;
  printf("请输入你要删除的元素位序:\n");
  scanf("%d", &x);
  LNode*p = L;
  while (p != NULL && j < x - 1) {
    p = p->next;
    j++;
  }
  if (p == NULL)
  {
    printf("不存在我们要删除的元素!");
  }
  if (p->next == NULL)
  {
    printf("不存在我们要删除的元素!");
  }
  LNode* q = p->next;
  e = q->data;
  p->next = q->next;
  free(q);
}
//在第i个位置插入
void IncreaseLinkNode(LinkNode& L) {
  printf("请输入你要插入的元素和位序:(元素和位序之间用逗号隔开)\n");
  int x, j = 0, e;
  scanf("%d,%d",&e, &x);
  LNode* s = L, * r= (LNode*)malloc(sizeof(LNode));
  while (j < x-1  && s != NULL) {
    j++;
    s = s->next;
  }
  r->data = e;
  r->next = s->next;
  s->next = r;
}
//查找位序
void SearchLinkNode(LinkNode &L) {
  int x,j=1;
  LNode* p=L->next;
  printf("请输入你要查找的元素:\n");
  scanf("%d", &x);
  while (p != NULL && p->data != x) {
    p = p->next;
    j++;
  }
  if (p == NULL) {
    printf("您要查找的元素不存在!");
  }
  else {
    printf("你要查找的元素%d的位序为%d", x, j);
  }
}
int main() {
  LinkNode L;
  InistLinkNode(L);
  /*InsertLinkNode(L);*/
  TailInsertLinkNode(L);
  PrintLinkNode(L);
  lengthLinkNode(L);
  GetElemLinkNode(L);
  IncreaseLinkNode(L);
  PrintLinkNode(L);
  DeleteLinkNode(L);
  PrintLinkNode( L);
  SearchLinkNode(L);
}

输出:


相关文章
|
9天前
|
安全 C语言
在C语言中,正确使用运算符能提升代码的可读性和效率
在C语言中,运算符的使用需要注意优先级、结合性、自增自减的形式、逻辑运算的短路特性、位运算的类型、条件运算的可读性、类型转换以及使用括号来明确运算顺序。掌握这些注意事项可以帮助编写出更安全和高效的代码。
21 4
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解
这份二叉排序树习题集涵盖了二叉搜索树(BST)的基本操作,包括构建、查找、删除等核心功能。通过多个具体示例,如构建BST、查找节点所在层数、删除特定节点及查找小于某个关键字的所有节点等,帮助读者深入理解二叉排序树的工作原理与应用技巧。此外,还介绍了如何将一棵二叉树分解为两棵满足特定条件的BST,以及删除所有关键字小于指定值的节点等高级操作。每个题目均配有详细解释与代码实现,便于学习与实践。
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现,帮助读者理解和掌握二叉树的基本操作与应用。
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
26天前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。
|
21天前
|
C语言
C语言里的循环链表
C语言里的循环链表
|
23天前
|
存储 Serverless C语言
【C语言基础考研向】11 gets函数与puts函数及str系列字符串操作函数
本文介绍了C语言中的`gets`和`puts`函数,`gets`用于从标准输入读取字符串直至换行符,并自动添加字符串结束标志`\0`。`puts`则用于向标准输出打印字符串并自动换行。此外,文章还详细讲解了`str`系列字符串操作函数,包括统计字符串长度的`strlen`、复制字符串的`strcpy`、比较字符串的`strcmp`以及拼接字符串的`strcat`。通过示例代码展示了这些函数的具体应用及注意事项。
|
26天前
|
存储 C语言
C语言程序设计核心详解 第十章:位运算和c语言文件操作详解_文件操作函数
本文详细介绍了C语言中的位运算和文件操作。位运算包括按位与、或、异或、取反、左移和右移等六种运算符及其复合赋值运算符,每种运算符的功能和应用场景都有具体说明。文件操作部分则涵盖了文件的概念、分类、文件类型指针、文件的打开与关闭、读写操作及当前读写位置的调整等内容,提供了丰富的示例帮助理解。通过对本文的学习,读者可以全面掌握C语言中的位运算和文件处理技术。
|
26天前
|
存储 C语言
C语言程序设计核心详解 第七章 函数和预编译命令
本章介绍C语言中的函数定义与使用,以及预编译命令。主要内容包括函数的定义格式、调用方式和示例分析。C程序结构分为`main()`单框架或多子函数框架。函数不能嵌套定义但可互相调用。变量具有类型、作用范围和存储类别三种属性,其中作用范围分为局部和全局。预编译命令包括文件包含和宏定义,宏定义分为无参和带参两种形式。此外,还介绍了变量的存储类别及其特点。通过实例详细解析了函数调用过程及宏定义的应用。
|
1月前
|
Linux C语言
C语言 多进程编程(三)信号处理方式和自定义处理函数
本文详细介绍了Linux系统中进程间通信的关键机制——信号。首先解释了信号作为一种异步通知机制的特点及其主要来源,接着列举了常见的信号类型及其定义。文章进一步探讨了信号的处理流程和Linux中处理信号的方式,包括忽略信号、捕捉信号以及执行默认操作。此外,通过具体示例演示了如何创建子进程并通过信号进行控制。最后,讲解了如何通过`signal`函数自定义信号处理函数,并提供了完整的示例代码,展示了父子进程之间通过信号进行通信的过程。