数据结构详解：单链表的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 冷光美白：效果、安全性和价格全方位对比
超声洁牙 vs 手工洁牙，哪个更适合你？
定期洗牙：维护口腔健康的必要选择
洗牙真的能拯救你的牙周病吗？
武术首登青奥舞台，新型武术体系闪耀国际
2023年广东新增49万常住人口，珠三角贡献超八成
冬季皇冠轿车保养全攻略
2023年广东人口增量居首，珠三角经济活力带动人口集聚
2023年珠三角GDP增1.82万亿元，四城引领区域发展新跨越
山火来袭，这些自救知识能救命！
洛杉矶山火频发，谁才是幕后黑手？
圣塔安娜风与洛杉矶山火：气候变化下的“魔鬼之手”
洛杉矶山火后的生态重建之路
醋酸美白牙齿，小心伤牙釉质！
白醋清洁牙齿，小心变“蜂窝牙”
醋美白牙齿，小心变“蜂窝牙”
醋真的毁牙？专家揭秘真相
醋洗牙？牙医：别拿牙齿开玩笑
民事诉讼简易程序：四大环节确保纠纷快速解决
从面包到胃药：酸与盐反应的生活应用全解析
三星堆文物展：46件一级文物揭秘3000年前古蜀文明
闵行区少体校推荐：在家改善下肢循环的运动指南
静脉曲张怎么办？教你几招改善下肢血液循环
血管专家推荐：三个穴位按摩改善下肢血液循环
大年三十，全家齐上阵，年夜饭DIY大赛
轻松养好富贵竹：环境、浇水、修剪和病虫害防治指南
自制酸碱指示剂：红萝卜皮和紫甘蓝的新用途