数据结构详解：单链表的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;
}
热门推荐
WordPress性能优化：8个实用技巧提升网站速度
钱凯港开港：中国与南美洲贸易的新篇章
新手小白跟着DeepSeek一起学习电脑配件——主板
南美洲五种最危险的动物
《难哄》里的温以凡，金庸笔下的包惜弱
如何培养孩子独立思考能力
比特币暴涨暴跌的逻辑
国家对独生子女家庭的六大优惠政策
为什么有些人自我效能感特别强？
美国运动医学学会【ACSM】整理的运动员指南：营养与运动表现（上）
皮肤干燥瘙痒？6种营养素助你改善皮肤状况
游戏通关后，为什么会陷入抑郁？
清朝的发型需要经常剃，皇帝都怎么剃头？不怕理发师趁机行刺吗？
新规之下，混凝土试块如何制作？
PPT模板背景音乐去除攻略：3个方法教你轻松删除自带背景乐！
做产品时如何确定需求量
孔子：东方智慧的奠基人与儒家思想的光辉
我国城市发展由“外延扩张”转向“内涵提升”
2024年A股退市盘点报告：近九成退市企业来自主板，“面值退”成退市主力军
服务器网络连接的基础概念与步骤解析，助你轻松掌握信息传输技术
怎么算安全期和危险期
怀孕周期较短的动物是哪些
黄金枫的栽培技巧，成功的关键
动火作业安全风险评估分析
瘦脖子的最快方法
秋季月季嫁接方法
AI 直播：个性化用户体验的新追求
孤独摇滚！：一部关于音乐与友情的暖心动画
今起三环内公交道公休日放开，“缓堵作用明显！”
苯磺酸氨氯地平片与苯磺酸左氨氯地平片哪个好