单链表的查找（按位查找与按值查找）

文章目录按位查找带头结点代码平均时间复杂度O(n)不带头结点代码按值查找带头结点平均时间复杂度O(n)查找结构类型不带头结点按位查找获取表L中第 i 个位置的元素的值。带头结点代码// (带头结点按位查找返回第 i 个元素带头结点LNode*GetElem(LinkList L,inti){if(i0)returnNULL;LNode*p;// 指针p指向当前扫描到的结点intj0;// 当前p指向的是第几个结点pL;// L 指向头结点头结点是第 0 个结点不存数据while(p!NULLji){pp-next;j;}returnp;// 返回第 i 个结点的指针}① 为什么 if(i 0) 而不是 if(i 1)在用户层面的ListInsert和ListDelete中位序i必须≥ 1因为用户不关心头结点。但这里的GetElem是一个底层辅助函数它允许调用者传入i 0。当i0时循环条件j 0不成立直接跳过循环return p返回头结点的地址。用途如果上层函数需要“修改头结点的next”就可以直接调用GetElem(L, 0)拿到头结点指针。平均时间复杂度O(n)不带头结点代码// (不带头结点) 按位查找返回第 i 个结点的指针若不存在则返回 NULLLNode*GetElem(LinkList L,inti){// 1. 不带头结点没有第 0 个结点位序必须从 1 开始if(i1)returnNULL;// 2. p 直接指向第一个数据结点位序为 1LNode*pL;intj1;// 计数器从 1 开始表示当前 p 指向位序 1// 3. 循环向后移动直到 p 指向第 i 个结点while(p!NULLji){pp-next;j;}// 4. 如果 p 为 NULL说明 i 超过了链表长度否则 p 就是目标结点returnp;}按值查找在表 L 中查找具有给定关键字值得元素。带头结点// 按值查找找到数据域 e 的结点LNode*LocateElem(LinkList L,inte){LNode*pL-next;// 直接跳过不存数据的头结点直接从第一个数据结点开始遍历// 从第 1 个结点开始查找数据域为 e 的结点while(p!NULLp-data!e){// 防止空指针 数据匹配pp-next;// 指针后移继续遍历}returnp;// 找到后返回该结点指针否则返回 NULL}平均时间复杂度O(n)查找结构类型// 定义学生结构体typedefstruct{intid;// 学号唯一关键字charname[20];// 姓名floatscore;// 成绩}Student;// 定义链表节点数据域为 Student 结构体typedefstructLNode{Student data;// 数据域是结构体structLNode*next;}LNode,*LinkList;// 按学号 id 查找学生节点带头结点LNode*LocateElem(LinkList L,inttarget_id){LNode*pL-next;// 跳过带头结点的头结点while(p!NULLp-data.id!target_id){// 只比较 id 字段pp-next;}returnp;}不带头结点// 不带头结点 按值查找返回第一个匹配结点的指针// 参数说明L 是头指针直接指向第一个数据结点e 是待查找的值LNode*LocateElem(LinkList L,inte){// 不带头结点时L 可能为 NULL空表直接返回 NULL// 虽然 while 循环能处理 NULL但显式写出能提高可读性if(LNULL)returnNULL;// p 直接指向第一个数据结点而不是 L-nextLNode*pL;// 条件防止 p 变成 NULL 后访问 p-datawhile(p!NULLp-data!e){pp-next;}// 找到返回指针没找到返回 NULLreturnp;}