夜雨聆风学习资料网

ARTICLE · 1392621

【数据结构C语言版·源码·视频】1.2 线性表的链式存储结构:单链表——动态存储与灵活的结点连接

【数据结构C语言版·源码·视频】1.2 线性表的链式存储结构:单链表——动态存储与灵活的结点连接

关于本系列课程

本系列为《数据结构(C语言版)》开源实践课程,围绕数据结构的核心知识体系,以 C 语言为基础,采用逐行代码实现与视频讲解相结合的方式,对各类数据结构及其典型算法进行系统讲解。
课程配套提供完整的 C 语言源码,涵盖数据结构的基本定义、存储结构、核心操作及典型算法实现,帮助学习者从理论理解逐步过渡到代码实践。
本课程教学案例曾获得计算机领域“101计划”核心课程高级研修班暨全国高校计算机类专业教学改革研讨会教学案例征集特等奖,以及第八届CCF开源创新大赛“开源案例教学赛”三等奖。
课程源码已在 GitHub 开源,欢迎学习、交流与使用:
GitHub:https://github.com/phdlisl/datastructure-edu

与顺序表不同,链表不需要使用连续的存储空间,而是通过指针将分散存储的结点连接起来。单链表是链式存储结构中最基本的形式,也是理解动态内存分配和指针操作的重要基础。

本节通过 C 语言逐步实现单链表的创建、插入、删除、查找和遍历等操作,重点掌握结点结构设计、指针连接关系及链表操作过程中指针的变化。

数据存储结构可以分为两大类,一类是顺序存储,一类是链式存储。顺序存储的典型结构就是数组,链式存储的典型结构就是链表。由顺序存储结构和链式存储结构,又可以构造出其他结构,比如索引存储结构。‍‍‍‍‍‍‍‍‍‍‍

线性表的链式存储结构,结点在存储位置上不再要求相邻,可任意分布,所以需要额外存储结点之间的关系,否则无法由物理结构恢复到逻辑结构。‍‍‍‍‍‍‍‍‍‍‍‍

还是以两个多项式求和为例,抽取操作对象:系数和指数,作为二元组。所有的二元组构成一个线性表,每个二元组作为一个结点,每个结点存在一对一的关系。‍‍

将线性表映射到链式存储结构中,每个结点独立存储,每个结点之间的关系通过指针关联,这就构成了链表。‍‍‍‍‍‍‍‍‍‍‍

在链表中,因为只有一条链,从头到尾,所以称为单链表。链表由一个或者多个结点链接而成,所谓链接就是指针指向下一个结点。链表中的每个结点,既包含了数据域,又包含了指针域。数据域存储的是数据元素本身,指针域存储的是元素之间的关系。‍‍‍‍‍

在单链表中,常常设置一个头结点,头结点的数据域不会装载数据。头指针指向头结点,头结点后面的第一个元素常称为首元结点,头结点在单链表的应用中起着非常大的作用。‍‍

特别说明:在链式存储结构的示意图中,常常用箭头表示指针指向,在实际的内存结构中,不可能存在这种箭头,这些箭头只是为了方便读者理解各个结点之间的关系。更深入地说,计算机压根不知道用户存储的是什么结构,计算机只能根据指针逐个查询结点。‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

下面将线性表由逻辑结构映射到物理结构,就需要定义数据类型(C语言为例)‍‍‍‍‍

typedef struct{double coefficient;int exponent;}ElemType;typedef struct LNode{  ElemType data;struct LNode *next;}LinkNode;

在这个结构体类型定义中,定义的是结点的数据类型,它包含了一个数据域data和一个指针域next。数据域存储的是数据元素,它的数据类型根据操作对象确定(这里以一元多项式求和为例),指针域存储结点之间的关系,通过指针可以找到下一个结点。‍‍‍‍‍‍‍‍‍‍‍

由单链表的特性可知,单链表只能从头向后遍历,不能向数组一样可以随机存取。但是单链表可以不受内存限制,不需要申请连续内存空间。‍

1、单链表的头插法

带头结点的单链表,利用头插法插入结点的时候,新结点的指针域先指向首元结点,然后将头指针改向新结点,新结点成为新的首元结点。这个顺序一定不能颠倒,否则原来的链无法找到。‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

2、单链表的尾插法‍‍‍

单链表的尾插法插入结点比较简单,只要找到尾结点,将新结点插入到尾结点的后面,就完成了结点插入。‍‍‍‍‍‍‍‍‍‍‍

3、单链表删除结点

删除结点的时候,就是将被删除结点的前驱结点的指针指向被删除结点的后继结点。需要注意的是,被删除结点需要有一个指针p指向,否则从链上摘除之后就找不到了。‍‍‍‍‍‍‍‍‍‍‍‍

祝你学习愉快。如果有疑问,请在评论区留言。

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料