链表 | 第5课（查找元素）

写一个 C 函数，在指定的单链表中查找一个指定的 key ‘x’. 如果 x 存在返回 true 否则返回 false.

bool search(Node *head, int x) 

例如, 如果 key 是 15 ，链表是 14->21->11->30->10, 那么函数会返回 false. 如果 key 是 14, 函数就返回 true.

迭代方案

2) 初始一个结点指针, current = head.
3) 如果 current 不为 NULL 就继续循环
    a) current->key 等于要搜索的 key 返回 true.
    b) current = current->next
4) 返回 false 

下面是迭代方案的算法。

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

/* 链表结点 */
struct Node
{
    int key;
    struct Node* next;
};

/* 指向头结点的指针和一个整数, 在链表头部加入一个新结点. */
void push(struct Node** head_ref, int new_key)
{
    /* 分配结点 */
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));

    /* 指定 key  */
    new_node->key  = new_key;

    /* 把新结点连接到老链表 */
    new_node->next = (*head_ref);

    /* 新结点变成头结点 */
    (*head_ref)    = new_node;
}

/* 判断 x 是否在链表里 */
bool search(struct Node* head, int x)
{
    struct Node* current = head;  // 初始 current
    while (current != NULL)
    {
        if (current->key == x)
            return true;
        current = current->next;
    }
    return false;
}

/* 测试程序*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
    int x = 21;

    /* Use push() to construct below list
     14->21->11->30->10  */
    push(&head, 10);
    push(&head, 30);
    push(&head, 11);
    push(&head, 21);
    push(&head, 14);

    search(head, 21)? printf("Yes") : printf("No");
    return 0;
}

输出:
Yes

递归方案

bool search(head, x)
1) 如果头结点为 NULL, 返回 false.
2) 如果头结点的 key 等于 x, 返回 true;
2) 否则返回 search(head->next, x) 

下面是递归算法的实现.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/* Link list node */
struct Node
{
    int key;
    struct Node* next;
};

/* 指向头结点的指针和一个整数, 在链表头部加入一个新结点. */
void push(struct Node** head_ref, int new_key)
{
    /* 分配结点 */
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));

    /* 指定 key  */
    new_node->key  = new_key;

    /* 把新结点连接到老链表 */
    new_node->next = (*head_ref);

    /* 新结点变成头结点 */
    (*head_ref)    = new_node;
}

/* 判断 x 是否在链表里 */
bool search(struct Node* head, int x)
{
    // 递归结束条件
    if (head == NULL)
        return false;

    // 如果 key 在头结点, 返回 true
    if (head->key == x)
        return true;

    // 递归剩下的列表
    return search(head->next, x);
}

/* 测试程序*/
int main()
{
    /* 开始空链表 */
    struct Node* head = NULL;
    int x = 21;

    /* 使用 push() 构造链表
     14->21->11->30->10  */
    push(&head, 10);
    push(&head, 30);
    push(&head, 11);
    push(&head, 21);
    push(&head, 14);

    search(head, 21)? printf("Yes") : printf("No");
    return 0;
}

输出:
Yes