数据结构详解：单链表的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;
}
热门推荐
城乡居民基本养老保险按什么档次交好？
腊梅小苗：从选购到栽培的全方位指南
耙耙柑挑选指南：从外观到口感，全面解析如何选购优质水果？
戴望舒笔下的雨后天晴：一首清新优美的自然赞歌
电子胎压计的使用方法是什么？怎样确保胎压测量的准确性？
双十一教你辨别鹅绒被真伪！
匈牙利vs波兰：谁家的鹅绒被更值得买？
石家庄必打卡！动物园、植物园、抱犊寨全攻略
牙结石：形成原因、预防方法和治疗选择的完整指南
口腔清洁只靠刷牙太天真！善用牙间刷、牙线棒护牙一把罩
夫妻离婚孩子归男方抚养费怎么算
朱元璋：从放牛娃到开国皇帝的逆袭之路
朱元璋的军事才能：从乞丐到皇帝的逆袭之路
南京故宫：朱元璋时期的皇家典范
长期居家，亲子关系更紧张？心理专家来支招：亲子沟通有技巧
未成年人保护 | 你知道不同年龄段的未成年人都受哪些法律保护吗？
《我的世界》单方块生存：从一块方块开始的生存挑战
《我的世界》单方块生存模式：最具挑战性的生存玩法
登顶珠峰60年：从壮举到商业，不变的探索精神
珠穆朗玛峰：徒步者的天堂还是地狱？
冬季运动损伤预防与处理全攻略
狐仙与人类的爱情：跨越种族的真挚情感
国光剧团《狐仙：无尽之爱》：一段跨越三世的人妖之恋
Windows原来还有个LTSB优等生，却被LTSC光芒覆盖它存在
从两审终审到三审甚至四审终审，详解民事诉讼流程、注意及新变化
五种冲突类型及其应对策略
畅游北京什刹海：无需预约，免费体验全攻略！
畅游北京什刹海：无需预约，免费体验全攻略！
北京除故宫国博等已全面取消预约要求，还有哪些省市取消预约
中科院揭示甲流病毒传播关键：NS片段作用揭秘