单链表的查找

单链表的按位查找(带头结点)：获取表L中第i个位置的元素的值，平均时间复杂度O(n)

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

typedef struct LNode{  //LNode:结点
    int data;  //数据域：每个结点存放一个数据元素
    struct LNode *next;  //指针域：指针指向下一个结点
}LNode,*LinkList;  //typedef struct LNode *LinkList;  要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点

//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
    (*L)=(LNode *)malloc(sizeof(LNode));  //分配一个头结点,并使得头指针*L指向这个头结点
    if((*L) == NULL){  //内存不足，分配失败
        return false;
    }
    (*L)->data=0;  //头结点不存储数据
    (*L)->next=NULL;  //头结点之后暂时还没有结点
    return true;
}

//按位查找，返回第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;
}

int main(){
    
    LinkList L;  //等价于LNode *L;  声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
    InitList(&L);  //初始化一个空表
    
    //...后续代码
    
    LNode * a=GetElem(&L, 3);
}

单链表的按值查找(带头结点)：在表L中查找具有给定关键字值的元素,平均时间复杂度O(n)

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

typedef struct LNode{  //LNode:结点
    int data;  //数据域：每个结点存放一个数据元素
    struct LNode *next;  //指针域：指针指向下一个结点
}LNode,*LinkList;  //typedef struct LNode *LinkList;  要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点

//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
    (*L)=(LNode *)malloc(sizeof(LNode));  //分配一个头结点,并使得头指针*L指向这个头结点
    if((*L) == NULL){  //内存不足，分配失败
        return false;
    }
    (*L)->data=0;  //头结点不存储数据
    (*L)->next=NULL;  //头结点之后暂时还没有结点
    return true;
}

//按值查找，找到数据域==e的结点(带头结点)
LNode * LocateElem(LinkList *L,int e){
    
    LNode *p =(*L)->next;
    
    //从第1个结点开始查找数据域为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;
}

int main(){
    
    LinkList L;  //等价于LNode *L;  声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
    InitList(&L);  //初始化一个空表
    
    //...后续代码
    
    LNode * a=LocateElem(&L, 3);  //找到数据域为3的结点，并返回
    
    int b=Length(&L);  //返回表的长度
}