02-2.3.2_2 单链表的查找

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！
谢谢大家！

注意，本节只讨论带头结点的情况

按位查找

GetElem(L, i)按位查找——获取表L中的第 i 个元素的值
具体代码实现：

LNode * GetElem(LinkList L, int i){if(i<0)return NULL;LNode *p;                  //指针p指向当前扫描到的结点int j = 0;                 //当前p指向的是第几个结点p = L;                     //L指向头结点，头结点是第0个结点（不存数据while(p != NULL && j < i){ //循环找到第 i 个结点p = p->next;j++;}return p;
}

平均时间复杂度：$O(n)$
王道书版本：

LNode * GetElem(LinkList L, itn i){int j = 1;LNode *p = L->next;if(i == 0)return i;if(i < 1)return NULL;while(p != NULL && j < i){p = p->next;j++;}return p;
}

封装（基本操作）的好处：
避免重复代码、简洁、易维护
此外，在写代码时还要注意程序的健壮性

按值查找

LocateElem(L, e)按值查找——在表L中查找具有给定关键字值的元素
具体代码实现：

LNode * LocateElem(LinkList L, ElemType e){LNode *p = L->next;//从第一个结点开始查找数据域为e的结点while(p != NULL && p->data != e){p = p->next;}return p;  //找到后返回该结点的指针，否则返回NULL
}

平均时间复杂度：$O(n)$

求表的长度

int length(LinkList L){int len = 0;LNode *p = L;while(p->next != NULL){p = p->next;len++;}return len;
}

时间复杂度：$O(n)$