数据结构详解：单链表的C语言实现
创作时间:
作者:
@小白创作中心
数据结构详解：单链表的C语言实现
引用
CSDN
1.
https://blog.csdn.net/zpz979994367/article/details/145786722
单链表是数据结构中一种常见的线性表实现方式，它通过指针将数据元素串联起来，具有动态分配内存、插入删除效率高等特点。本文将从单链表的基本概念出发，详细介绍其在C语言中的实现方法，包括初始化、插入、删除、遍历和销毁等基本操作，并给出完整的代码示例。
一、什么是单链表
单链表是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含两个部分：
- 数据域：存储数据元素。
- 指针域：存储指向下一个节点的指针。
对应的C语言结构为：
typedef struct node{
int data;
struct node *next;
}Node;
单链表的特点是每个节点只指向下一个节点，最后一个节点指向NULL，表示链表的结束。
二、单链表的优缺点
优点
- 动态内存分配，不需要预先知道数据量。
- 插入和删除操作效率高，时间复杂度为O(1)。
缺点
3. 访问元素要从头节点开始遍历，时间复杂度为O(n)。
4. 需要额外的内存空间存储指针。
三、单链表的基本操作
3.1 初始化链表
初始化链表，主要是创建链表头节点。
Node* initList()
{
Node *head = (Node*)malloc(sizeof(Node));
if(NULL == head)
{
perror("malloc error:");
return NULL;
}
head->data = 0;
head->next = NULL;
return head;
}
3.2 插入节点（头插法，尾插法，指定位置插入）
(1) 头插法
每次都在链表头之后插入节点，步骤：
- 创建新节点，
- 新节点 next 指向原先头节点的 next，
- 头节点 next 指向新节点。
int insertHead(Node* L, ElemType elem)
{
Node *node = (Node*)malloc(sizeof(Node));
if(NULL == node)
{
perror("malloc error:");
return -1;
}
node->data = elem;
node->next = L->next;
L->next = node;
return 0;
}
(2) 尾插法
首先要获取尾部节点，然后再插入新节点。
//获取尾节点
Node* get_tail(Node *L)
{
Node *p = L;
while(p->next != NULL)
{
p = p->next;
}
return p;
}
//尾部插入
Node* insertTail(Node *tail, ElemType elem)
{
Node *node = (Node*)malloc(sizeof(Node));
if(NULL == node)
{
perror("malloc error:");
return NULL;
}
node->data = elem;
tail->next = node;
node->next = NULL;
return node;
}
(3) 指定位置插入
首先需要找到指定位置的前驱节点，然后按头插法的步骤插入节点。
int insertNode(Node *L, int pos, ElemType elem)
{
//判断制定位置是否溢出
int length = listLength(L); //链表长度
if(pos < 0 || pos >= length)
{
printf("pos 指定位置超出范围\n");
return -1;
}
//获取指定节点的前驱节点
Node *pre = L;
int i = 0;
while(i < pos)
{
pre = pre->next;
i++;
if (pre == NULL) //超出
{
return -1;
}
}
//插入新节点
Node *node = (Node*)malloc(sizeof(Node));
if(NULL == node)
{
perror("malloc error:");
return -1;
}
node->data = elem;
node->next = pre->next;
pre->next = node;
return 0;
}
3.3 删除节点
步骤：
- 找到要删除节点的前置节点 p
- 用指针 q 记录要删除的节点
- 通过改变 p 的后继节点实现删除
- 释放删除节点的空间
int deleteNode(Node *L, int pos)
{
//判断制定位置是否溢出
int length = listLength(L); //链表长度
if(pos < 0 || pos >= length)
{
printf("pos 指定位置超出范围\n");
return -1;
}
//获取指定节点的前驱节点
Node *pre = L;
int i = 0;
while(i < pos)
{
pre =pre->next;
i++;
if (pre == NULL)
{
return -1;
}
}
Node *q = pre->next;
pre->next = q->next;
free(q);
return 0;
}
3.4 遍历节点
void listNode(Node* L)
{
Node *p = L->next; //头节点的下一个节点开始
while(p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
3.5 销毁节点
void freeList(Node *L)
{
Node *p = L->next;
Node *q;
while(p != NULL)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
}
四、完整代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElemType;
typedef struct node{
ElemType data;
struct node *next;
}Node;
/*****************************************************************
* 函数功能 : 链表长度
* 参数 : L(in)链表
* 返回值 : 链表长度
******************************************************************/
int listLength(Node *L)
{
int len = 0;
Node *p = L->next;
while(p != NULL)
{
p = p->next;
len++;
}
return len;
}
/*****************************************************************
* 函数功能 : 初始化链表
* 参数 : void
* 返回值 : 成功：头节点指针，失败：NULL
******************************************************************/
Node* initList()
{
Node *head = (Node*)malloc(sizeof(Node));
if(NULL == head)
{
perror("malloc error:");
return NULL;
}
head->data = 0;
head->next = NULL;
return head;
}
/*****************************************************************
* 函数功能 : 头插法
* 参数 : L(in)链表
* 参数 ：elem(in)元素值
* 返回值 : 成功：0，失败：-1
******************************************************************/
int insertHead(Node* L, ElemType elem)
{
Node *node = (Node*)malloc(sizeof(Node));
if(NULL == node)
{
perror("malloc error:");
return -1;
}
node->data = elem;
node->next = L->next;
L->next = node;
return 0;
}
/*****************************************************************
* 函数功能 : 遍历
* 参数 : L(in)链表
* 返回值 : void
******************************************************************/
void listNode(Node* L)
{
Node *p = L->next;
while(p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
/*****************************************************************
* 函数功能 : 获取尾部结点
* 参数 : L(in)链表
* 返回值 : 尾结点指针
******************************************************************/
Node* get_tail(Node *L)
{
Node *p = L;
while(p->next != NULL)
{
p = p->next;
}
return p;
}
/*****************************************************************
* 函数功能 : 尾插法
* 参数 : tail(in)原尾结点指针
* 参数 ：elem(in)插入元素值
* 返回值 : 成功：新尾结点指针，失败：NULL
******************************************************************/
Node* insertTail(Node *tail, ElemType elem)
{
Node *node = (Node*)malloc(sizeof(Node));
if(NULL == node)
{
perror("malloc error:");
return NULL;
}
node->data = elem;
tail->next = node;
node->next = NULL;
return node;
}
/*****************************************************************
* 函数功能 : 指定位置插入
* 参数 : *L(in)链表
* 参数 : pos(in)指定位置
* 参数 ：elem(in)插入元素值
* 返回值 : 成功：0，失败：-1
******************************************************************/
int insertNode(Node *L, int pos, ElemType elem)
{
//判断制定位置是否溢出
int length = listLength(L); //链表长度
if(pos < 0 || pos >= length)
{
printf("pos error\n");
return -1;
}
//获取指定节点的前驱节点
Node *pre = L;
int i = 0;
while(i < pos)
{
pre = pre->next;
i++;
if (pre == NULL) //超出
{
return -1;
}
}
//插入新节点
Node *node = (Node*)malloc(sizeof(Node));
if(NULL == node)
{
perror("malloc error:");
return -1;
}
node->data = elem;
node->next = pre->next;
pre->next = node;
return 0;
}
/*****************************************************************
* 函数功能 : 删除节点
* 参数 : *L(in)链表
* 参数 : pos(in)指定位置
* 返回值 : 成功：0，失败：-1
******************************************************************/
int deleteNode(Node *L, int pos)
{
//判断制定位置是否溢出
int length = listLength(L); //链表长度
if(pos < 0 || pos >= length)
{
printf("pos error\n");
return -1;
}
//获取指定节点的前驱节点
Node *pre = L;
int i = 0;
while(i < pos)
{
pre =pre->next;
i++;
if (pre == NULL)
{
return -1;
}
}
if(pre->next == NULL)
{
printf("要删除的位置错误\n");
return -1;
}
Node *q = pre->next;
pre->next = q->next;
free(q);
return 0;
}
/*****************************************************************
* 函数功能 : 释放链表
* 参数 : L(in)链表
* 返回值 : void
******************************************************************/
void freeList(Node *L)
{
Node *p = L->next;
Node *q;
while(p != NULL)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
}
int main(int argc, char const *argv[])
{
//初始化
Node *list = initList();
printf("%d\n", listLength(list));
//头插法
insertHead(list, 0);
insertHead(list, 11);
insertHead(list, 22);
printf("%d\n", listLength(list));
listNode(list);
//尾插法
Node *tail = get_tail(list);
tail = insertTail(tail, 33);
tail = insertTail(tail, 44);
printf("%d\n", listLength(list));
listNode(list);
//指定插入
insertNode(list, -1, 15); //超出范围
insertNode(list, 5, 15); //超出范围
insertNode(list, 4, 15);
printf("%d\n", listLength(list));
listNode(list);
//删除节点
deleteNode(list, -1);//超出范围
deleteNode(list, 6);//超出范围
deleteNode(list, 5);
printf("%d\n", listLength(list));
listNode(list);
//销毁
freeList(list);
printf("%d\n", listLength(list));
listNode(list);
system("pause");
return 0;
}
热门推荐
马云：功过交织的商业传奇
如何通过项目管理PMP认证考试
探秘陕历博：一次穿越千年的历史文化之旅，好玩吗？
大豆需肥规律深度解析与高效施肥技术指南
光线强弱对钓鱼的影响，以鲫鲤草青为例分析
三国志战略版高效开荒指南：三势吕阵容开荒策略解析
《使命召唤》系列：FPS游戏的标杆与创新之旅
安装3500多个模组，在RTX5090的加持下，《上古卷轴5》焕然一新
SC食品生产许可现场核查指南
Modbus协议中浮点数的格式与换算
芝商所“删档”部分黄金合约！贵金属交易规则突变，交易者如何闯关新副本？
神秘果的功效与作用：从提味增鲜到降尿酸
癫痫病科普|服用抗癫痫药物的五大防治关键
强直阵挛性发作（癫痫大发作）的诊断和治疗
驾乘险能赔多少？一文详解驾乘险赔付机制
征信知识 十问十答
H3C交换机端口状态查看指南
消炎杀菌最强的中草药
水电插座布局全攻略：从规划到施工的实用指南
Nature子刊：改变脂肪的代谢途径后，其能和肿瘤细胞竞争营养物质，抑制肿瘤生长
《老子》古本探秘：从傅奕本到北大收藏本
粮库数字化：重塑粮食储存与管理的新篇章
卖房贷款计算：房产交易的财务规划
AI 浪潮下，程序员如何顺势而为，重塑自身职业价值？
埃隆·马斯克的11句金言：70岁后的人生指南
世界无童工日‖关爱未成年人，对非法雇用童工说“不”
金融科技创新都有什么
国家版减肥指南来了，每天就这么吃！
“不想上班”到“满血复活”：如何打败职业倦怠？
足坛传奇：历史巅峰时期的十大巨星