有序链表顺序搜索算法实现 - SeqSearch 函数详解

有序链表顺序搜索算法实现 - SeqSearch 函数详解

假设有一个有序表用单链表表示，其结点和链表结构体定义如下：

typedef struct snode{
        KeyType key;
        DataType data;
        struct snode* link;
}SNode;

typedef struct linkedlist{
        SNode * first;
}LinkedList;

请设计一个方法 SeqSearch，实现对有序表的顺序搜索。若搜索成功则 SeqSearch 返回 TRUE，否则返回 FALSE。

BOOL SeqSearch(LinkedList* list, KeyType key)
{
    SNode* p = list->first;
    while(p != NULL && p->key < key)
    
    {
        p = p->link;
    }
    if(p == NULL || p->key > key)
    {
        return FALSE;
    }
    else
    {
        return TRUE;
    }
}

**注：**本题假设有序表按照关键字升序排列。

代码解释：

1. 初始化指针： SNode* p = list->first; 将指针 p 指向链表的头结点 first。
2. 循环遍历： while(p != NULL && p->key < key) 循环遍历链表，直到遇到以下两种情况：
   • p == NULL： 指针 p 指向空结点，表示链表中不存在目标关键字。
   • p->key >= key： 指针 p 所指结点的关键字大于或等于目标关键字，此时退出循环。
3. 判断搜索结果： if(p == NULL || p->key > key) 检查退出循环的原因：
   • p == NULL： 目标关键字不存在，返回 FALSE。
   • p->key > key： 目标关键字不存在，返回 FALSE。
   • 否则： 目标关键字存在，返回 TRUE。

总结： 该 SeqSearch 函数通过顺序遍历链表的方式查找目标关键字，并根据遍历结果返回 TRUE 或 FALSE 表示搜索成功与否。

优化建议：

• 由于链表是有序的，可以考虑使用二分查找算法来提高搜索效率。
• 可以添加错误处理机制，例如当链表为空时，直接返回 FALSE。
• 可以根据实际需求添加其他功能，例如返回找到的目标结点指针。