C Academy · Pelajaran

Penelusuran dan Pencarian

Telusuri list.

Penelusuran dan Pencarian adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.

Menelusuri daftar

Penelusuran berarti mengunjungi setiap simpul secara berurutan. Anda mulai dari kepala dan mengikuti penunjuk next hingga mencapai NULL.

Hampir setiap algoritma daftar dibangun berdasarkan penelusuran sederhana ini.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

Pola penelusuran

Perulangan standar menggunakan penunjuk yang bergerak, yaitu p: inisialisasikan ke head, lanjutkan selama p bukan NULL, dan majukan dengan p = p->next.

Jangan pernah mengubah head itu sendiri saat menelusuri, atau awal daftar akan hilang.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) { printf("%d ", p->value); p = p->next; }
    printf("\n");
    return 0;
}

Menghitung simpul

Untuk menemukan panjang daftar, telusuri daftar dan naikkan penghitung untuk setiap simpul.

Ini adalah operasi O(n) karena jumlahnya tidak disimpan di mana pun.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("length = %d\n", length(head));
    return 0;
}

Menjumlahkan nilai

Penelusuran memungkinkan Anda menggabungkan data. Di sini, kita menjumlahkan semua nilai bilangan bulat dalam daftar.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(5);
    head->next = make(10);
    int sum = 0;
    for (struct Node *p = head; p; p = p->next) sum += p->value;
    printf("sum = %d\n", sum);
    return 0;
}

Mencari nilai

Untuk menemukan suatu nilai, telusuri daftar dan bandingkan setiap simpul. Kembalikan simpul tersebut (atau posisinya) saat menemukan kecocokan, atau tandai kegagalan jika mencapai akhir daftar.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *find(struct Node *head, int v) {
    for (struct Node *p = head; p; p = p->next)
        if (p->value == v) return p;
    return NULL;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    printf("found 2: %d\n", find(head, 2) != NULL);
    printf("found 9: %d\n", find(head, 9) != NULL);
    return 0;
}

Menemukan posisi

Terkadang Anda menginginkan indeks kecocokan, bukan simpulnya. Simpan penghitung saat menelusuri dan kembalikan nilainya ketika nilai tersebut ditemukan.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int index_of(struct Node *head, int v) {
    int i = 0;
    for (struct Node *p = head; p; p = p->next, i++)
        if (p->value == v) return i;
    return -1;
}

int main(void) {
    struct Node *head = make(7);
    head->next = make(8);
    printf("%d\n", index_of(head, 8));
    return 0;
}

Mengakses simpul ke-n

Daftar tertaut tidak memiliki pengindeksan langsung. Untuk mencapai posisi n, Anda harus melangkah sebanyak n kali dari kepala.

Itulah sebabnya akses acak berkompleksitas O(n), sedangkan pada larik berkompleksitas O(1).

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *at(struct Node *head, int n) {
    struct Node *p = head;
    for (int i = 0; i < n && p; i++) p = p->next;
    return p;
}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    head->next->next = make(30);
    printf("%d\n", at(head, 2)->value);
    return 0;
}

Menemukan simpul terakhir

Untuk mendapatkan ekor, telusuri hingga p->next bernilai NULL. Simpul tersebut adalah simpul terakhir.

Berhati-hatilah terhadap daftar kosong, yang membuat head itu sendiri bernilai NULL.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    struct Node *p = head;
    while (p->next) p = p->next;
    printf("last = %d\n", p->value);
    return 0;
}

Menemukan nilai maksimum

Dengan menggabungkan pencarian dan agregasi, Anda dapat menemukan nilai terbesar dengan melacak nilai terbaik sementara selama penelusuran.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(3);
    head->next = make(9);
    head->next->next = make(5);
    int best = head->value;
    for (struct Node *p = head->next; p; p = p->next)
        if (p->value > best) best = p->value;
    printf("max = %d\n", best);
    return 0;
}

Penelusuran rekursif

Daftar juga dapat ditelusuri secara rekursif: proses simpul saat ini, lalu lakukan rekursi pada next.

cara ini elegan, tetapi menggunakan ruang tumpukan yang sebanding dengan panjang daftar, sehingga iterasi lebih aman untuk daftar yang sangat panjang.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void print_rec(struct Node *p) {
    if (!p) { printf("\n"); return; }
    printf("%d ", p->value);
    print_rec(p->next);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    print_rec(head);
    return 0;
}

Menangani daftar kosong

Setiap fungsi penelusuran harus menangani daftar kosong (head == NULL) dengan baik.

Perulangan standar sudah melakukannya: kondisi p != NULL langsung bernilai salah, sehingga isi perulangan tidak pernah dijalankan.

#include <stdio.h>

struct Node { int value; struct Node *next; };

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = NULL;
    printf("empty length = %d\n", length(head));
    return 0;
}

Pemeriksaan Singkat

Uji pemahaman Anda tentang biaya penelusuran daftar.

Ringkasan

Anda telah mempelajari cara menelusuri dan mencari dalam daftar:

Pola penelusuran: mulai dari head, lakukan perulangan selama bukan NULL, dan majukan dengan p = p->next.
Penghitungan, penjumlahan, dan pencarian nilai maksimum semuanya dibangun berdasarkan penelusuran.
Pencarian membandingkan setiap simpul; akses berdasarkan indeks berkompleksitas O(n).
Penelusuran dapat dilakukan secara rekursif, tetapi iterasi lebih aman untuk daftar panjang; selalu tangani kasus daftar kosong.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Penelusuran dan Pencarian” gratis?

Ya — teks lengkap “Penelusuran dan Pencarian” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Penelusuran dan Pencarian”?

Telusuri list. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C Academy?

Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Penelusuran dan Pencarian” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke C Academy