Tìm kiếm

/* Dạng 1: trả về con trỏ tới nút, hoặc NULL nếu không thấy. */
Node *list_tim(const List *l, int gia_tri)
{
    for (Node *p = l->head; p != NULL; p = p->next)
        if (p->data == gia_tri)
            return p;

    return NULL;
}

/* Dạng 2: trả về chỉ số, hoặc -1 nếu không thấy. */
long list_vi_tri(const List *l, int gia_tri)
{
    long i = 0;

    for (const Node *p = l->head; p != NULL; p = p->next, ++i)
        if (p->data == gia_tri)
            return i;

    return -1;
}

/* Dạng 3: chỉ hỏi có hay không. */
int list_co(const List *l, int gia_tri)
{
    return list_tim(l, gia_tri) != NULL;
}

/* Tìm nút đầu tiên có data bằng gia_tri.
   Nếu ra_truoc khác NULL thì ghi vào đó con trỏ tới nút đứng trước,
   hoặc NULL nếu nút tìm được chính là nút đầu.
   Trả về nút tìm được, hoặc NULL. */
Node *list_tim_kem_truoc(const List *l, int gia_tri, Node **ra_truoc)
{
    Node *truoc = NULL;

    for (Node *p = l->head; p != NULL; truoc = p, p = p->next)
        if (p->data == gia_tri) {
            if (ra_truoc != NULL) *ra_truoc = truoc;

            return p;
        }

    if (ra_truoc != NULL) *ra_truoc = NULL;

    return NULL;
}

/* Trả về nút đầu tiên mà khop trả về khác 0.
   ctx được truyền nguyên vẹn cho khop, để mang dữ liệu phụ. */
Node *list_tim_neu(const List *l,
                   int (*khop)(int data, void *ctx),
                   void *ctx)
{
    if (l == NULL || khop == NULL) return NULL;

    for (Node *p = l->head; p != NULL; p = p->next)
        if (khop(p->data, ctx))
            return p;

    return NULL;
}

#include <stdio.h>

#include "list.h"

static int la_chan(int data, void *ctx)
{
    (void)ctx;

    return data % 2 == 0;
}

static int lon_hon(int data, void *ctx)
{
    return data > *(const int *)ctx;      /* ctx mang ngưỡng */
}

int main(void)
{
    List l;

    list_khoi_tao(&l);

    int nguon[] = { 7, 3, 12, 5, 20, 9 };

    for (size_t i = 0; i < sizeof nguon / sizeof nguon[0]; ++i)
        if (list_them_cuoi(&l, nguon[i]) != 0) { list_huy(&l); return 1; }

    list_in(&l);

    Node *a = list_tim_neu(&l, la_chan, NULL);

    printf("so chan dau tien : %d\n", a ? a->data : -1);

    int nguong = 10;
    Node *b = list_tim_neu(&l, lon_hon, &nguong);

    printf("so dau tien > 10 : %d\n", b ? b->data : -1);

    printf("vi tri cua 5     : %ld\n", list_vi_tri(&l, 5));
    printf("vi tri cua 99    : %ld\n", list_vi_tri(&l, 99));

    list_huy(&l);

    return 0;
}

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

typedef struct Node { int data; struct Node *next; } Node;

#define N 2000000
#define LAN 20

int main(void)
{
    int  *a   = malloc(N * sizeof *a);
    Node *dau = NULL, *cuoi = NULL;

    if (a == NULL) return 1;

    for (size_t i = 0; i < N; ++i) {
        a[i] = (int)i;

        Node *n = malloc(sizeof *n);

        if (n == NULL) return 1;

        n->data = (int)i;
        n->next = NULL;

        if (cuoi) cuoi->next = n; else dau = n;

        cuoi = n;
    }

    /* Tìm phần tử cuối, tức trường hợp xấu nhất, lặp LAN lần */
    clock_t t0 = clock();
    long long tim_thay = 0;

    for (int k = 0; k < LAN; ++k)
        for (size_t i = 0; i < N; ++i)
            if (a[i] == N - 1) { ++tim_thay; break; }

    double giay_a = (double)(clock() - t0) / CLOCKS_PER_SEC;

    t0 = clock();

    for (int k = 0; k < LAN; ++k)
        for (Node *p = dau; p; p = p->next)
            if (p->data == N - 1) { ++tim_thay; break; }

    double giay_l = (double)(clock() - t0) / CLOCKS_PER_SEC;

    printf("mang      : %.3f s\n", giay_a);
    printf("danh sach : %.3f s\n", giay_l);
    printf("cham hon  : %.1f lan  (tim thay %lld lan)\n",
           giay_l / giay_a, tim_thay);

    free(a);

    for (Node *p = dau; p; ) { Node *t = p->next; free(p); p = t; }

    return 0;
}