ARTICLE · 1392621
【数据结构C语言版·源码·视频】1.2 线性表的链式存储结构:单链表——动态存储与灵活的结点连接
关于本系列课程

与顺序表不同,链表不需要使用连续的存储空间,而是通过指针将分散存储的结点连接起来。单链表是链式存储结构中最基本的形式,也是理解动态内存分配和指针操作的重要基础。
本节通过 C 语言逐步实现单链表的创建、插入、删除、查找和遍历等操作,重点掌握结点结构设计、指针连接关系及链表操作过程中指针的变化。
数据存储结构可以分为两大类,一类是顺序存储,一类是链式存储。顺序存储的典型结构就是数组,链式存储的典型结构就是链表。由顺序存储结构和链式存储结构,又可以构造出其他结构,比如索引存储结构。
线性表的链式存储结构,结点在存储位置上不再要求相邻,可任意分布,所以需要额外存储结点之间的关系,否则无法由物理结构恢复到逻辑结构。

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

将线性表映射到链式存储结构中,每个结点独立存储,每个结点之间的关系通过指针关联,这就构成了链表。
在链表中,因为只有一条链,从头到尾,所以称为单链表。链表由一个或者多个结点链接而成,所谓链接就是指针指向下一个结点。链表中的每个结点,既包含了数据域,又包含了指针域。数据域存储的是数据元素本身,指针域存储的是元素之间的关系。
在单链表中,常常设置一个头结点,头结点的数据域不会装载数据。头指针指向头结点,头结点后面的第一个元素常称为首元结点,头结点在单链表的应用中起着非常大的作用。
特别说明:在链式存储结构的示意图中,常常用箭头表示指针指向,在实际的内存结构中,不可能存在这种箭头,这些箭头只是为了方便读者理解各个结点之间的关系。更深入地说,计算机压根不知道用户存储的是什么结构,计算机只能根据指针逐个查询结点。
下面将线性表由逻辑结构映射到物理结构,就需要定义数据类型(C语言为例)
typedef struct{double coefficient;int exponent;}ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LinkNode;
在这个结构体类型定义中,定义的是结点的数据类型,它包含了一个数据域data和一个指针域next。数据域存储的是数据元素,它的数据类型根据操作对象确定(这里以一元多项式求和为例),指针域存储结点之间的关系,通过指针可以找到下一个结点。
由单链表的特性可知,单链表只能从头向后遍历,不能向数组一样可以随机存取。但是单链表可以不受内存限制,不需要申请连续内存空间。
1、单链表的头插法

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

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

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

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















































































