单链表（带头结点）的存储结构与基本操作（c语言）------亲测可用

article/2025/8/25 14:11:44

编程语言：c语言
编译环境：Dev-c++
实现功能：实现功能：单链表（带头结点）结点结构体的定义，单链表（带头结点）初始化、求元素个数、插入元素、删除元素、取元素、打印所有元素、就地逆置、撤销的操作。

    • 结构体定义
    • 初始化
    • 求元素个数
    • 插入元素
    • 删除元素
    • 取元素
    • 打印所有元素
    • 就地逆置
    • 撤销
    • 测试及完整代码

结构体定义

定义如下图结点结构体，很显然单链表是链式存储结构，逻辑上相邻的两个元素，物理地址不一定相邻。

在这里插入图片描述

typedef struct Node     //定义单链表结点结构体 
{DataType data;struct Node *next;
} SLNode;

带头结点单链表结构如下图。

在这里插入图片描述既然涉及到头指针，那当然要区分一下头指针、头结点、首元结点，如下图是带头结点的单链表。

在这里插入图片描述

初始化

算法思想：将头·结点的指针域赋为NULL。
为什么使用**head？
首先声明指针就是地址，头指针即我们定义的结构体变量的地址，指针的指针即存放这个地址的内存单元的地址。因为我们要初始化一个头指针，那么我们就要操作它的地址空间，即使用指针的指针。在这个函数中，我们输入头指针的指针，*head即为取这个头指针，(*head) ->next = NULL即为初始化头指针指向结点结构体的指针域值为NULL。对照带头结点单链表结构图，我们可以很清晰的理解。

void ListInitiate(SLNode **head)                       //初始化
{*head = (SLNode*)malloc(sizeof(SLNode));           //申请头节点 (*head) ->next = NULL;								//置结束标记NULL 
}

求元素个数

算法思想：设置零时指针和计数器，零时指针每移动一位，计数器加一，直到遍历完单链表，返回最终计数值，如下图。

在这里插入图片描述

int ListLength(SLNode *head)							//求当前数据元素个数 
{SLNode *p = head;int size = 0;while(p->next != NULL)								//指针位置移动，size增加 {p = p->next;size++;} return size;}

插入元素

算法思想：设置零时指针，移动后指向第i-1个元素，再进行连接和断链，如下图。

在这里插入图片描述

int ListInsert(SLNode *head,int i,DataType x)		//在第i（0<=i<=size）个位置前插入数据元素值x 
{SLNode *p,*q;int j=-1;p=head;while(p->next!=NULL && j<i-1)                   //定位，使p指向第i-1个元素 {p=p->next;j++;}if(j!=i-1)										//当i的值不合法时则返回 {printf("插入元素位置参数错！"); return 0; }q = (SLNode *)malloc(sizeof(SLNode));          //申请新结点 q->data = x;									//新结点数据域赋值 q->next = p->next;								//插入步骤① p->next = q;									//插入步骤② return 1;}

删除元素

算法思想：设置零时指针，移动后指向第i-1个元素，再进行连接和断链，如下图。

在这里插入图片描述

在这里插入图片描述

int ListDelete(SLNode *head,int i,DataType *x)		//删除第i（0<=i<=size-1）个位置处的数据元素并保存到x中
{SLNode *p,*s;int j=-1;p=head;while(p->next!=NULL && j<i-1)                   //定位，使p指向第i-1个元素 {p=p->next;j++;}if(j!=i-1)										//当i的值不合法时则返回 {printf("插入元素位置参数错！");return 0; }s = p->next;									//指针s指向第i个结点 *x=s->data;										//把指针s所指结点数据域指赋给x p->next = p->next->next;						//删除free(s); return 1;	}

取元素

算法思想：设置零时指针，移动后指向第i-1个元素，再取出下个元素数据域的值。

int ListGet(SLNode *head,int i,DataType *x)			//取第i（0<=i<=size）个位置处的数据元素并保存到x中 ，成功返回1，失败返回0
{SLNode *p;int j=-1;p= head;while(p->next!=NULL && j<i-1)                   //定位，使p指向第i-1个元素 {p=p->next;j++;}if(j!=i-1)										//当i的值不合法时则返回 {printf("插入元素位置参数错！");return 0; }	*x = p->next->data;									//指针p所指第i个结点数据域的值赋给x return 1; }

打印所有元素

算法思想：设置零时指针遍历单链表，每移动一次打印一个值。

void Print(SLNode *head) 								//打印单链表 
{SLNode *p;p=head;while(p->next!=NULL){printf("%d ",p->next->data);p=p->next;}}

就地逆置

算法思想：设置两个零时指针，首先将头结点断链，然后将剩余的元素逆序插到头结点之后，如下图。

在这里插入图片描述

void Reverse(SLNode *head)      					    //单链表就地逆置 
{SLNode *p,*q;p=head->next;head->next=NULL;									//头结点断链 while(p!=NULL)										//将元素逆序插到头结点后面 {q=p;p=p->next;q->next=head->next;head->next=q;}}

撤销

算法思想：释放单链表的结点，需要输入头结点的地址。

void Destory(SLNode **head)                          //撤销单链表  
{SLNode *p,*q;p=*head;while(p!=NULL){q=p;p=p->next;free(q);}*head = NULL;
}

测试及完整代码

我们在Dev-c++创建console application的c项目，并添加三个工程文件：test.c，SLNode.c，SLNode.h。步骤如下：

  • 新建项目，选console application（控制台应用程序）、c项目。

在这里插入图片描述
在这里插入图片描述

  • 给项目添加三个文件，再编译运行。

在这里插入图片描述

  
  
 
运行结果：

在这里插入图片描述

完整代码：

test.c:
#include <stdio.h>
#include"SLNode.h"int main() 
{int i;int x;SLNode *head;ListInitiate(&head);for(i=0;i<10;i++)                                       	  //插入10个元素 {ListInsert(head,i,i*i);		}printf("插入10个元素后单链表表中的元素依次为：");Print(head);printf("\n");ListDelete(head,5,&x);		                                //删除第0个位置处元素printf("删除第5个位置处元素后单链表中的元素依次为：");Print(head);printf("\n");printf("删除的元素为：%d",x);printf("\n");ListGet(head,4,&x);          							printf("取第4个位置处元素元素为：%d",x);printf("\n");Reverse(head);                                               //就地逆置 printf("逆置后单链表中的元素依次为：");Print(head);Destory(&head);return 0;
}

SLNode.h:
#ifndef _SLNODE_H
#define _SLNODE_H
typedef int DataType;typedef struct Node     //定义单链表结点结构体 
{DataType data;struct Node *next;
} SLNode;void ListInitiate(SLNode **head);                      //初始化
int ListLength(SLNode *head);							//求当前数据元素个数 
int ListInsert(SLNode *head,int i,DataType x);		//在第i（0<=i<=size）个位置前插入数据元素值x 
int ListDelete(SLNode *head,int i,DataType *x);		//删除第i（0<=i<=size）个位置处的数据元素并保存到x中
int ListGet(SLNode *head,int i,DataType *x);			//取第i（0<=i<=size）个位置处的数据元素并保存到x中 ，成功返回1，失败返回0
void Print(SLNode *head); 								//打印单链表 
void Reverse(SLNode *head);      					    //单链表就地逆置 
void Destory(SLNode **head);                             //撤销单链表 #endif

SLNode.c:
#include<stdio.h>
#include<malloc.h> 
#include"SLNode.h"void ListInitiate(SLNode **head)                       //初始化
{*head = (SLNode*)malloc(sizeof(SLNode));           //申请头节点 (*head) ->next = NULL;								//置结束标记NULL 
} int ListLength(SLNode *head)							//求当前数据元素个数 
{SLNode *p = head;int size = 0;while(p->next != NULL)								//指针位置移动，size增加 {p = p->next;size++;} return size;} int ListInsert(SLNode *head,int i,DataType x)		//在第i（0<=i<=size）个位置前插入数据元素值x 
{SLNode *p,*q;int j=-1;p=head;while(p->next!=NULL && j<i-1)                   //定位，使p指向第i-1个元素 {p=p->next;j++;}if(j!=i-1)										//当i的值不合法时则返回 {printf("插入元素位置参数错！"); return 0; }q = (SLNode *)malloc(sizeof(SLNode));          //申请新结点 q->data = x;									//新结点数据域赋值 q->next = p->next;								//插入步骤① p->next = q;									//插入步骤② return 1;} int ListDelete(SLNode *head,int i,DataType *x)		//删除第i（0<=i<=size-1）个位置处的数据元素并保存到x中
{SLNode *p,*s;int j=-1;p=head;while(p->next!=NULL && j<i-1)                   //定位，使p指向第i-1个元素 {p=p->next;j++;}if(j!=i-1)										//当i的值不合法时则返回 {printf("插入元素位置参数错！");return 0; }s = p->next;									//指针s指向第i个结点 *x=s->data;										//把指针s所指结点数据域指赋给x p->next = p->next->next;						//删除free(s); return 1;	} int ListGet(SLNode *head,int i,DataType *x)			//取第i（0<=i<=size）个位置处的数据元素并保存到x中 ，成功返回1，失败返回0
{SLNode *p;int j=-1;p= head;while(p->next!=NULL && j<i-1)                   //定位，使p指向第i-1个元素 {p=p->next;j++;}if(j!=i-1)										//当i的值不合法时则返回 {printf("插入元素位置参数错！");return 0; }	*x = p->next->data;									//指针p所指第i个结点数据域的值赋给x return 1; } void Print(SLNode *head) 								//打印单链表 
{SLNode *p;p=head;while(p->next!=NULL){printf("%d ",p->next->data);p=p->next;}} void Reverse(SLNode *head)      					    //单链表就地逆置 
{SLNode *p,*q;p=head->next;head->next=NULL;									//头结点断链 while(p!=NULL)										//将元素逆序插到头结点后面 {q=p;p=p->next;q->next=head->next;head->next=q;}} void Destory(SLNode **head)                          //撤销单链表  
{SLNode *p,*q;p=*head;while(p!=NULL){q=p;p=p->next;free(q);}*head = NULL;
}

  
  
 

总结一下，单链表中初始化操作的时间复杂度是O(1)，其他操作的时间复杂度为O(n)，作为链式存储结构的单链表，操作都涉及到指针，结构体，所以理解这两个知识点就非常重要了。源代码在我的博客资源区，点击文字链接直达👉带头结点单链表的定义及源代码，免费下载。

小僧初来乍到，希望大家多多支持！如有纰漏，欢迎大家在评论区留言，小僧会及时更正，同时，大家如果有疑惑的地方可以把问题写在评论区，小僧看到会回复哟😄！
另外，小僧的公众号上线啦，里面有“实用工具”、“学习资源”以及许多资料，欢迎大家关注一波小僧的公众号👇

在这里插入图片描述
  
  
  
参考：
C语言结构体的定义和使用(超详细)
C语言之结构体（struct）
C语言指针详解
C语言指针详解（经典，非常详细）
《数据结构——使用C语言（第五版）》 ------朱战立


http://chatgpt.dhexx.cn/article/aIS7G4yY.shtml

相关文章

链表OJ归纳总结 ------- C语言

链表OJ归纳总结 ------- C语言

一、移除链表元素 OJ链接https://leetcode.cn/problems/remove-linked-list-elements/submissions/ 1.1. | 解题思路 | 创建一个新的哨兵头节点 guard&#xff0c;创建尾节点 tail&#xff0c;创建 cur 用于遍历原链表数据。 对原链表进行遍历&#xff0c;若 cur->val ! v…
阅读更多...
【链表复习】C++ 链表复习及题目解析 (2)

【链表复习】C++ 链表复习及题目解析 (2)

目录 牛客 CM11 链表分割 牛客 OR36 之链表的回文结构 Leetcode 160. 相交链表 LeetCode 141. 环形链表 LeetCode 138. 复制带随机指针的链表 本文继续延续前文&#xff0c;为大家带来几道经典的链表中等难度的题目。 牛客 CM11 链表分割 现有一链表的头指针 ListNode* p…
阅读更多...
【链表OJ题(三)】链表中倒数第k个结点

【链表OJ题(三)】链表中倒数第k个结点

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录 链表OJ题(三)1. 链表…
阅读更多...
【20230205】链表小结

【20230205】链表小结

链表&#xff08;list&#xff09; 链表是一种通过指针串联在一起的线性结构&#xff0c;每一个节点由两部分组成&#xff0c;一个是数据域一个是指针域&#xff08;存放指向下一个节点的指针&#xff09;&#xff0c;最后一个节点的指针域指向null&#xff0c;链表的入口节点称…
阅读更多...
【链表复习】C++ 链表复习及题目解析 (3)

【链表复习】C++ 链表复习及题目解析 (3)

目录 剑指offer 中的链表题目 JZ6 从尾到头打印链表 JZ18 删除链表的结点 JZ24 反转链表 JZ25 合并两个排序的链表 JZ52 两个链表的第一个公共结点 JZ23 链表中环的入口结点 JZ22 链表中倒数第k 个结点 JZ35 复杂链表的复制 JZ76 删除链表中重复的结点 本次给大家带来…
阅读更多...
【023】C/C++数据结构之链表及其实战应用

【023】C/C++数据结构之链表及其实战应用

C 链表及其实战应用 引言一、链表的概述二、利用链表设计一个学生管理系统2.1、设计主函数main()2.2、实现插入节点2.3、实现链表的遍历2.4、实现链表的查找2.5、实现删除某个节点2.6、实现释放链表2.7、完整代码 总结 引言 &#x1f4a1; 作者简介&#xff1a;专注于C/C高性能…
阅读更多...
KNN分类算法详解

KNN分类算法详解

参考&#xff1a;https://www.cnblogs.com/listenfwind/p/10311496.html https://www.cnblogs.com/listenfwind/p/10685192.html 1. 概述 KNN 可以说是最简单的分类算法之一&#xff0c;同时&#xff0c;它也是最常用的分类算法之一。注意&#xff1a;KNN 算法是有监督学习中的…
阅读更多...
【python代码实现】朴素贝叶斯分类算法

【python代码实现】朴素贝叶斯分类算法

目录 前置知识1、概念2、算法原理2.1、条件概率2.2、全概率2.3、先验概率2.4、后验概率 朴素贝叶斯分类算法1、构建数据集2、分类概率3、条件概率4、先验概率 前置知识 1、概念 上一篇我们讲到的决策树算法&#xff0c;是反映了一种非常明确、固定的判断选择过程&#xff0c;…
阅读更多...
分类算法-KNN(原理+代码+结果)

分类算法-KNN(原理+代码+结果)

KNN&#xff0c;即K最邻近算法&#xff0c;是数据挖掘分类技术中比较简单的方法之一&#xff0c;简单来说&#xff0c;就是根据“最邻近”这一特征对样本进行分类。 1、K-means和KNN区别 K-means是一种比较经典的聚类算法&#xff0c;本质上是无监督学习&#xff0c;而KNN是分…
阅读更多...
伯努利贝叶斯分类算法

伯努利贝叶斯分类算法

贝叶斯分类的核心概念&#xff1a; 我们对某件事情的判断首先有一个概率&#xff0c;这个概率称为先验概率。先验概率时根据经验总结出来的概率值&#xff0c;如果首先没有经验&#xff0c;那么可以将先验概率设置为50%&#xff0c;随着后面事情的发展&#xff0c;再调整先验概…
阅读更多...
【机器学习原理】KNN分类算法

【机器学习原理】KNN分类算法

上一篇&#xff1a;Logistic回归分类算法 文章目录 一、KNN分类算法&#xff1a;用多数表决进行分类1. 用“同类相吸”的办法解决分类问题可视化下的分类问题 2. KNN分类算法的基本方法&#xff1a;多数表决3. 表决权问题4. KNN的具体含义 KNN分类算法原理1. KNN分类算法的基本…
阅读更多...
Python实现分类算法

Python实现分类算法

前言&#xff1a;出自于学校课程数据挖掘与分析布置的实验小作业&#xff0c;案例经典&#xff0c;代码注释较全&#xff0c;供大家参考。 题目&#xff1a; 现有西瓜挑选数据文件&#xff1a;dataset.txt&#xff0c;编程实现朴素贝叶斯算法&#xff0c;并判断有如下特征的瓜…
阅读更多...
贝叶斯分类算法

贝叶斯分类算法

贝叶斯分类是一类分类算法的总称&#xff0c;这类算法均以贝叶斯定理为基础&#xff0c;故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单&#xff0c;也是常见的一种分类方法。这篇文章我尽可能用直白的话语总结一下我们学习会上讲到的朴素贝叶斯分类算法&#…
阅读更多...
基于Python实现五大常用分类算法(原理+代码)

基于Python实现五大常用分类算法(原理+代码)

读&#xff1a; 在机器学习和统计中&#xff0c;分类算法通过对已知类别训练集的计算和分析&#xff0c;从中发现类别规则并预测新数据的类别。分类被认为是监督学习的一个实例&#xff0c;即学习可以获得正确识别的观察的训练集的情况。 实现分类的算法&#xff0c;特别是在具…
阅读更多...
EIGRP综合实验解析

EIGRP综合实验解析

实验要求 1.R1为ISP,只能配置IP地址 2.R1与R2之间为PPP封装&#xff0c;使用CHAP认证&#xff0c;R1为主认证方 3.R2-R8地址为172.16.0.0/16 4.R4的S1/1口带宽为800K。R4到R2环回为非等开销负载均衡 5.保证更新安全&#xff0c;减少路由条目数量 6.R6到达R8环回通过R7进行 7.R2…
阅读更多...
EIGRP协议

EIGRP协议

EIGRP是距离矢量路由协议&#xff0c;但又非距离矢量那样路由完全是别人告诉&#xff0c;而是通过维护3张表自己对比计算后放入路由表。同样会受水平分割影响。 EIGRP建邻居过程 第一步&#xff1a;路由器R1和R2接口配置EIGRP后&#xff0c;在相应接口上向外组播发送Hello包…
阅读更多...
EIGRP总结

EIGRP总结

EIGRP 增强内部网关路由协议 无类别距离矢量IGP协议&#xff1b; 增量更新—仅触发更新&#xff0c;无周期更新----更新量小&#xff08;DV&#xff09;&#xff0c;可靠性高&#xff08;RTP&#xff09;&#xff0c;保活机制&#xff08;hello&#xff09; 复合度量—多个参数…
阅读更多...
EIGRP

EIGRP

EIGRP增强型网关路由协议 基本内容&#xff1a; Cisco私有&#xff1b;无类别距离矢量协议&#xff1b;跨层封装协议&#xff0c;封装于网络层–协议号88&#xff1b;组播更新&#xff1a;224.0.0.10 &#xff1b;支持非等开销负载均衡&#xff1b;增量更新&#xff08;部分更…
阅读更多...
思科EIGRP配置及基本讲解

思科EIGRP配置及基本讲解

思科EIGRP配置及基本讲解 什么是EIGRP EIGRP全称 [增强型内部网关路由选择协议] 是思科自主研发的动态路由选择协议&#xff0c;按类型划分是一款IGP协议&#xff0c;距离矢量协议&#xff0c;是一款基于传闻的协议。 EIGRP是思科的私有协议&#xff0c;直到13年&#xff0c;此…
阅读更多...
EIGRP协议的配置

EIGRP协议的配置

EIGRP(Enhanced Interior Gateway Routing Protocol&#xff0c;增强型内部网关路由协议)是Cisco公司开发的一个平衡混合型路由协议&#xff0c;它融合了距离向量和链路状态两种路由协议的优点&#xff0c;支持IP&#xff0c;IPX和ApplleTalk等多种网络层协议。由于TCP/IP是当今…
阅读更多...
推荐文章

Copyright @ 2022~2023