数据结构详解：单链表的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;
}
热门推荐
冬季开启一场公路旅行，国道219路线攻略
南京明城墙：系统性保护中探寻墙与人的连接
在南京，春风十里不如一颗广东菠萝
菠萝的上市时间是什么时候？菠萝的种植和储存方法有哪些？
羧甲司坦片药理机制
“群龙”聚首岭南水乡！顺德杏坛“百龙闹江”仪式感满满
挑选植发医生：技巧与指南
老款奔驰E200机械增压版钥匙电池更换教程
海陵岛旅行指南：避雷精选住宿与热门景点解析
赛乐特的不良反应及用药注意事项
继承财产分割房子怎么分
古代官员俸禄制度的演变与影响
如何合理分配个人与社会责任
马关：最长国道G219线上最美休闲驿站
心理学教你优雅说不：告别"老好人"
职场达人教你优雅说不：无效社交
华山医院专家揭秘：孩子高效学习的黄金时段
美国教育机构推荐：培养孩子良好心理素质的8个实用方法
舒馨幼儿园营养餐：孩子成长的秘密武器
《奥特曼 新世代群星》：赛罗奥特曼的全新篇章
APN 设置指南：优化您的移动网络连接
红细胞偏高有什么症状
血红蛋白正常值是多少 血红蛋白偏高是什么原因
卸任约两周 美国前总统拜登与知名艺人经纪公司签约
猫奴必看！日本10 大猫岛推荐，被猫咪围绕的感觉太治愈！
人这一辈子，一定要去一趟塔什库尔干！
妙佑医疗推荐：宿醉后的最佳解救方案
平安夜防宿醉小妙招，你get了吗？
椰子水解酒真的有用吗？科学解读来了
如何正确地向佛菩萨“许愿”