【图解】数据结构代码领背-05

01

在单链表中按值查找结点

在顺序线性表中，我们学习了查找其中的元素是对线性表进行遍历，一个一个地去查看其中的元素。那在链式线性表中是否也如此呢，答案是肯定的。链表中查找元素，也是遍历整个链表，查看其中的数据域与要寻找的元素是否相同。

01

图例

但是稍微有不一样的地方是，顺序表中各元素物理存储位置也是相邻的，所以下一个内存单元也存储着下一个元素，如图1所示。

图1

所以，指针指向下一个存储单元，就能访问下一个数据元素。但链表不同，链表中两个逻辑上相邻的数据元素，在物理存储空间中不一定相邻（图2）。

图2

所以我们要借助结点的指针域，根据当前访问结点的指针域中存储的下一个结点的地址，去访问下一个结点，即p = p->next。

02

代码

下面我们来看代码：

03

总结

根据我们之前的介绍，我们可以把整个代码思路总结为3步：

1.设置工作指针：设置指针负责指向要访问结点的指针域，并根据指针域移动指向下一个结点；

2.循环比较数据：将给定数据与每个结点的数据域进行比较，相同则退出循环，返回结点指针；否则，继续访问下一个结点；

3.返回相应指针：找到相应的结点，则返回指向该结点的指针；否则，返回NULL。

整体看下来代码并不是很难，而且一句话就可以很轻松的记住：设指针（*p = L->next），遍链表（p = p->next），返结点（return p）。

02

在单链表中按序号查找结点值

那学习了在单链表中按值查找结点，那按序号查找结点值其实并没有太大的区别。因为链表不像数组有天然的下标，所以所谓的序号也只是，我们人为的在链表外部为链表的结点进行排序。

01

代码

下面我们来看代码：

02

总结

很容易看出，这段代码与上面的基本无异，主要附加了一个计数工具，用来认为的为链表中的结点设置序号。

可以说这两个操作的代码，相比于之前都不是很难，只要对链表的定义与访问有着很好的了解，就能够非常轻松地写出来。