下载掌阅APP，畅读海量书库
立即打开
上一节讲解了线性表的第一种存储方式——顺序存储结构，下面讲解第二种存储方式——链式存储结构。
链表是指按链式存储结构存储的线性表。链表是指线性表中的结点在内存中随机存放，即存储单元即可以连续也可以不连续。因此为了保持链表各结点逻辑相邻的关系，就需要各结点在存放值的同时还要存放下一个结点（后继结点）的地址。
单链表中结点要用两个区域，一个表示结点数据信息，称为数据域，一个表示当前结点的后继结点的引用，称为地址域，如图2.10所示。
图2.10 单链表结点结构
构成链表的结点定义如下：
因此，以学号和姓名为数据元素的线性表，其单链表首地址为180，则存储结构如图2.11所示。
图2.11 以学号和姓名为数据元素的顺序表存储结构图
作为线性表的一种存储结构，我们关心的是结点的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用图2.12 的形式而不用图2.11 的形式表示。
若第一个结点仅表示链表的起始位置，而无任何值和意义，则称为头结点，如图2.12所示的结点H。
图2.12 带头结点的单链表
单链表的两个优点：
（1）插入、删除时，只要找到对应前驱结点，修改指针即可，无须移动元素。
（2）采用动态存储分配，不会造成内存浪费和溢出。
单链表的三个缺点：
（1）在有些高级语言中，不支持指针，不容易实现。
（2）需要用额外空间存储线性表的关系，存储密度小。
（3）不能随机访问，查找时要从头指针开始遍历，查找元素的时间复杂度较大。
根据图2.1所示的学生表链式存储结构对应的单链表，对该表中数据元素的操作有：查找、插入、删除等。
在链表中查找某位置结点，则从链表头结点位置开始不断向下遍历链表，直到查找到对应位置的结点结束，返回查找结点，否则返回结点不存在。
【例2.3】查找学生链表中第i个位置的数据元素并返回。
图2.13 单链表的查找操作
查找并返回第i个结点过程如图2.13所示。
查找链表的第i个位置的数据元素，其中head为链表头结点，则查找操作流程图如图2.14所示。
图2.14 查找操作流程图
在单链表的位置i插入新结点，有以下操作步骤：
（1）判断i的合法性。
（2）找到插入前位置，如存在则继续，否则结束。
（3）申请新结点、将其前一个位置next域的值（即其后继结点的位置）填入其next域，待插入的值赋予新结点的值域。
（4）插入新结点，将其地址填入前一结点（直接前驱结点）的next域。
（5）表的长度加1。
【例2.4】在学生链表中的第i个位置前插入新结点node。
在第i个位置前插入新结点node，先找到a i-1 结点位置p，再申请新结点node，新结点的地址域指向p的下一结点，再改变p所指结点的地址域，让其指向node结点，如图2.15所示。
图2.15 单链表的插入操作
插入链表的第i个位置的数据元素，其中head为链表头结点，node为要插入的数据结点，curlen为表的长度，则插入操作流程图如图2.16所示。
图2.16 插入操作流程图
在上面查找代码的基础上，增加插入函数void insert(int i, Node* node) ，实现单链表的插入功能，具体如下：
在单链表中删除某位置的结点，有以下三个操作步骤：
（1）找到删除结点直接前驱对应的位置，若存在则继续，否则结束。
（2）若要删除的结点存在则继续，否则结束。
（3）删除对应位置结点，结束。
【例2.5】在学生链表中删除第i个位置的结点。
要删除第i个位置结点，先找到a i-1 结点位置p，在p所指结点的下一结点存在的情况下，p所指结点的地址域改为p所指结点的下一结点的下一结点的地址，如图2.17所示。
图2.17 单链表的删除操作
删除链表的第i个位置的数据元素，其中curlen为链表的长度，则删除操作流程图如图2.18所示。
图2.18 删除操作流程图
在上面插入代码的基础上，增加删除函数Node* Delete(int i) ，实现单链表的删除功能，具体如下：
