本文数据结构讲解参考书目：
通过网盘分享的文件：数据结构 C语言版.pdf
链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码: ze8e
上一节我讲了线性表中顺序表的定义以及常用的算法，那么这节我将继续讲解顺序表中的链式结构以及常见的算法。
目录
线性表的链式表示和实现
1.单链表的定义和表示
线性表链式存储结构的特点是：用一 组任意的存储单元存储线性表的数据元素（这组存储单
元可以是连续的，也可以是不连续的）。 因此，为了表示每个数据元素ai与其直接后继数据元素
ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直
接后继的信息（即直接后继的存储位置）。 这两部分信息组成数据元素ai的存储映像，称为结点。
它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称
为指针域。指针域中存储的信息称作指针或链。n个结点(a,(1<=i<=n) 的存储映像）链结成一
个链表，即为线性表。
(a1, a2;··, an)
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、
双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用
千实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。
2.单链表的逻辑状态
由上述可见，单链表可由 头指针唯一确定，在C语言中可用 “结构指针” 来描述。
注：（1)这里定义的是单链表中每个结点的 存储结构，它包括两部分：存储结点的数据
域 data, 其类型 用通用类型标识符 ElemType 表示；存储后继结点位置
的指针域 next, 其类型为指向结点的指针类型 LNode *。
(2) 为了提高程序的可读性，在此对同一结构体指针类型起了两个名称，LinkList 与
LNode* , 两者本质上是等价的。通常习惯上 用 LinkList 定义单链表，强调定义的是某个单链
喊＇ 表的头指针；用 LNode *定义指向单链表中任意结点的指针变量。例如，若定义 LinkList L,
惩明 则 L 为单链表的头指针，若定义 LNode*p, 则p 为指向单链表中某个结点的指针，用*p 代表
该结点。当然也可以使用定义 LinkListp, 这种定义形式完全等价于 LNode*p。
(3) 单链表是由表头指针唯一确定，因此 单链表可以用头指针 的名宇来命名。若头
指针名是L, 则简称该链表为 表L。
(4) 注意区分指针变量和结点变量两个 不同的概念，若定义 LinkListp 或 LNode*p,
则 p 为指向某 结点的指针变量，表示该结点的地址；而*p 为对应的结点变量，表示该结
点的名称。
一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点
说明：
(I) 首元结点是指链表中存储第一个数据元素a1 的结点。
(2) 头结点是 在首元结点之前附设的 一个结点，其指针域指向首元结点。头结点的
喊＇ 数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。
(3) 头指针 是指向链表中第一个结点的指针 。 若链表设有头结点，则头指针所
指结点为线性表的头结点；若链表不设头 结 点，则头指针所指结点为该线性表的首
元结点。
3.带头结点的单链表
单链表基本操作的实现
1.单链表的初始化
【算法步骤】
(1)生成新结点作为头结点，用头指针L 指向头结点。
(2)头结点的指针域置空。
【算法描述】
Status InitList(LinkList &L)
｛//构造一个空的单链表L
L=new LNode; //生成新结点作为头结点， 用头指针L指向头结点
1->next=NULL; //头结点的指针域置空
return OK;
}2.单链表的取值
和顺序表不同， 链表中逻辑相邻的结点并没有存储在物理相邻的单元中,这样 ,根据给定的
结点位置序号i在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结
点出发，顺着链域 next 逐个结点向下访问。
【算法步骤］
1.用指针p指向首元结点，用八故计数器初值赋为1。
2.从首元结点开始依次顺着链域 next 向下访问， 只要指向当前结点的指针 p 不为空
(NULL), 并且没有到达序号为I的结点，则循环执行以下操作：
•p指向下一个结点；
• 计数器j相应加1。
3.出循环时， 如果指针p为空， 或者计数器j大于i, 说明指定的序号i值不合法（i大于
表长n或i小于等于0), 取值失败返回ERROR; 否则取值成功， 此时j=i时，p所指的结点就
是要找的第l个结点，用参数e保存当前结点的数据域， 返回OK。
［算法描述】
Status GetElem(LinkList L,int i,ElemType &e)
{//在带头结点的单链表L中根据序号l.获取元素的值，用e返回L中第l.个数据元素的值
p=L->next;j=l; //初始化，p指向首元结点，计数器］初值赋为1
while(p&&j<i) //顺链域向后扫描，直到p为空或p指向第l.个元素
p=p->next; //p指向下一个结点
++j; //计数器j相应加1
if(!p!lj>i)return ERROR; //八值不合法 i>n或i,s;o
e=p->data; //取第i个结点的数据域
return OK;
}单链表取值算法的平均时间复杂度为O(n)。
3.单链表的按值查找
链表中按值查找的过程和顺序表类似，从链表的首元结点出发， 依次将结点值和给定值e进
行比较， 返回查找结果 。
【算法步骤】
1.用指针p指向首元结点 。
2.首元结点开始依次顺着链域next向下查找， 只要指向当前结点的指针p不为空， 并且
p所指结点的数据域不等于给定值e, 则循环执行以下操作： p指向下一个结点 。
3.返回p。 若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
【算法描述】
LNode *LocateELem(LinkList L, Elemtype e)
｛//在带头结点的单链表L中查找值为e的元素
p=L->next; //初始化，p指向首元结点
while(p && p->data!=e) //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p=p->next; //p指向下一个结点
return p; //查找成功返回值为e的结点地址p, 查找失败p为NULL
}平均时间复杂度为 O(n)
4.单链表的插入
假设要在单链表的两个数据元素a和b之间插入一个数据元素X, 已知p为其单链表存储结
构中指向结点a 的指针。
【算法步骤］
1.查找结点ai-1 并由指针p指向该结点。
2.生成一个新结点*s。
3.将新结点*s 的数据域置为 e。
4.将新结点*s 的指针域指向结点aio
5.将结点*p 的指针域指向新结点*s。
【算法描述】
Status Listinsert(LinkList &L,int i,ElemType e)
｛//在带头结点的单链表L中第i个位置插入值为e的新结点
p=L;j=O;
while ( p && ( j<i-1))
{p=p->next;++j;}
if (!p ||j>i-1) return ERROR;
s= new LNode;
s->data= e;
s->next=p->next;
p->next=s;
return OK;
}5.单链表的删除
要删除单链表中指定位置的 元素，同插入元素一样， 首先应该找到该位置的 前驱结点。
如图所示，在单链表中 删除元素b时，应该首
先找到其前驱结点a。为了在单链表中实现元素a、
b和c之 间逻辑关系的变化，仅需修改结点 a中的
指针域即可。假设p为指向结点a的指针 ，则修改指针的语句为：
p->next = p->next->next;
［算法步骤】
1.查找结点 ai-1 并由指针p指向该 结点。
2.临时保存待删除结点ai的地址在q中 ，以备释放。
3.结点*p的指针域指向ai的直接后继结点。
4.释放结点ai的空间。
【算法描述】
Status ListDelete(LinkList &L,int i)
｛//在带头结点的单链表L中，删除第l个元素
p=L;j=O;
while((p->next) && (j<i-1)) //查找第i-1个结点，p指向该结点
{p=p->next; ++j;}
f (! (p->next) 11 (j>i-1)) return ERROR; //当心n或区1时，删除位置不合理
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放删除结点的空间
return OK;
}6.创建单链表
Ⅰ.前插法创建单链表
前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结
点，读入 相应的数据元素值，然后将新结点插入到头结点之后。
【算法步骤】
1.创建一个只有头结点的空链表。
2.根据待创建链表包括的元素个数n, 循环n次执行以下操作：
• 生成一个新结点*p;
• 输入元素值赋给新结点*p的数据域；
• 将新结点*p插入到头结点之后。
［算法描述］
void CreateList_H(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带表头结点的单链表1
L=new LNode;
L->next=NULL;
for(i=O;i<n;++i)
p=new LNode;
cin>>p->data;
p->next=L->next;L->next=p;
}
}
时间复杂度为O(n)。
Ⅱ.后插法创建单链表
后插法是通过将新结点逐个插入到链表的尾部来创建链表。 同前插法一样， 每次申请一个新
结点， 读入相应的数据元素值。 不同的是， 为了使新结点能够插入到表尾， 需要增加一个尾指针
r指向链表的尾结点。
【算法步骤】
1.创建一个只有头结点的空链表。
2.尾指针r初始化， 指向头结点。
3.根据创建链表包括的元素个数n, 循环n次执行以下操作：
• 生成一个新结点*p;
• 输入元素值赋给新结点*p 的数据域；
• 将新结点*p 插入到尾结点*r之后；
• 尾指针r指向新的尾结点*p。
【算法描述】
void CreateList_R(LinkList &L,int n)
｛//正位序输人n个元素的值， 建立带表头结点的单链表L
L=new LNode;
L->next=NULL;
r=L;
for(i=O;i<n;++i)
p=new LNode;
cin>>p->data;
p->next=NULL; r->next=p;
r=p;
}
}时间复杂度亦为O(n)
————由于博主还是大三的在读生，时间有限，每天会不定时更新一些学习经验和一些32的项目，如果喜欢就点点关注吧，大佬们！！！！————
标签：结点,单链,线性表,next,链表,算法,数据结构,指针 From： https://blog.csdn.net/qq_74267366/article/details/142024254