Struktur Data : Implementasi Program Pencarian dalam Bahasa C

📋 Daftar Isi

Pencarian Sequensial

Pencarian Sekuensial Pada Data Tidak Terurut (Array)

#include <stdio.h>
#define MAX 100 //ukuran maksimum array
 
void fill_data(int data[], int *size){ //mengisi data
    printf("Input ukuran array (max 100): ");
    scanf("%d", size);
    printf("Input data: ");
    for(int i=0;i<*size;i++){
        scanf("%d",&data[i]);
    }
}
 
int seq_search(int data[], int size, int x){
    for (int i=0;i<size;i++){
        if(data[i]==x) return i;
    }
    return -1;
}
 
void main(){
    int data[MAX];
    int size; //ukuran array
    int x;
    fill_data(data,&size);
    printf("nilai yang mau dicari: ");
    scanf("%d", &x);
    if(seq_search(data,size,x)==-1) printf("tidak ditemukan");
    else printf("ditemukan pada indeks ke-%d",seq_search(data,size,x));
}

Output

Pencarian Sekuensial Pada Data Tidak Terurut (Linked List)

#include <stdio.h>
#include <stdlib.h>
 
struct node{
    int value;
    struct node *next;
};
 
typedef struct node *ptrnode;
 
ptrnode head = NULL;
int jumnode; //jumlah node
 
ptrnode insert(int nilai){
    ptrnode p,q;
    p = (ptrnode)malloc(sizeof(struct node));
    p->value = nilai;
    p->next = NULL;
    if(head==NULL) {
            head=p;
            q=head;
    }
    else {
            q = head;
            while(q->next!=NULL){
                q = q->next;
            }
            q->next = p;
    }
    return(head);
}
 
void isi_data(){
    int k;
    printf("input jumlah node: ");
    scanf("%d",&jumnode);
    for(int j=1;j<=jumnode;j++){
        printf("input data ke-%d :",j);
        scanf("%d", &k);
        head=insert(k);
    }
}
 
int search(int x){ //x adalah nilai yang dicari
    int j = 1;
    ptrnode tmp=head;
    while(tmp != NULL){
        if(x==tmp->value){
            return j;
        }
        else{
            tmp = tmp->next;
            j++;
        }
    }
    return -1; //jika tidak ada yang dicari return -1
}
 
void bersihkan_memori(){
    while(head != NULL){
        ptrnode tmp = head;
        head = head->next;
        tmp->next = NULL;
        free(tmp);
    }
}
 
void main(){
    isi_data();
    int x;
    printf("input nilai yang mau dicari: ");
    scanf("%d",&x);
    if (search(x) == -1) printf("data tidak ditemukan");
    else printf("data ditemukan di node ke-%d",search(x));
    bersihkan_memori();
}

Output:

Pencarian Biner

Pencarian Biner (Array)

#include <stdio.h>
#define MAX 100 //ukuran maksimum array
 
void fill_data(int data[], int *size){ //mengisi data
    printf("Input ukuran array (max 100): ");
    scanf("%d", size);
    printf("Input data ascending: ");
    for(int i=0;i<*size;i++){
        scanf("%d",&data[i]);
    }
}
 
int binary_search(int data[], int size, int x){
    int L = 0;
    int H = size-1;
    int M = -1;
    int index = -1;
 
    while(L<=H){
        M = (L+H)/2;
        if(data[M]==x)return M;
        else{
            if(data[M] < x) L = M + 1;
            else H = M - 1;
        }
    }
    return -1;
}
 
void main(){
    int data[MAX];
    int size; //ukuran array
    int x;
    fill_data(data,&size);
    printf("nilai yang mau dicari: ");
    scanf("%d", &x);
    if(binary_search(data,size,x)==-1) printf("tidak ditemukan");
    else printf("ditemukan pada indeks ke-%d",binary_search(data,size,x));
}

Pencarian Biner (Linked List)

#include <stdio.h>
#include<stdlib.h>
 
struct node{
    int value;
    struct node *next;
};
 
typedef struct node *ptrnode;
 
ptrnode head,tail = NULL;
int jumnode;
 
ptrnode insert(int nilai){
    ptrnode p;
    p = (ptrnode)malloc(sizeof(struct node));
    p->value = nilai;
    p->next = NULL;
    if(head==NULL) {
            head=p;
            tail=head;
    }
    else {
            tail = head;
            while(tail->next!=NULL){
                tail = tail->next;
            }
            tail->next = p;
            tail = p;
    }
    return(head);
}
 
void isi_data(){
    int j,k;
    printf("input jumlah node (data harus urut ascending): ");
    scanf("%d",&jumnode);
    for(j=1;j<=jumnode;j++){
        printf("input data ke-%d :",j);
        scanf("%d", &k);
        head=insert(k);
    }
}
 
ptrnode middle(ptrnode start, ptrnode last){
//untuk mendapatkan node tengah
    if (start == NULL) return NULL;
    ptrnode slow = start;
    ptrnode fast = start -> next;
    while (fast != last){
        fast = fast -> next;
        if (fast != last){
            slow = slow -> next;
            fast = fast -> next;
        }
    }
    return slow;
}
 
ptrnode binarySearch(int x){
    ptrnode start = head;
    ptrnode last = NULL;
    do{
        // temukan node tengah
        ptrnode mid = middle(start, last);
        // jika node tengah NULL
        if (mid == NULL) return NULL;
        // Jika x ditemukan di node tengah
        if (mid -> value == x) return mid;
        // Jika nilai x lebih dari node tengah
        else if (mid -> value < x) start = mid -> next;
        // Jika nilai x kurang dari node tengah
        else last = mid;
    } while (last == NULL || last != start);
    // jika tidak ditemukan
    return NULL;
}
 
void bersihkan_memori(){
    while(head != NULL){
        ptrnode tmp = head;
        head = head->next;
        tmp->next = NULL;
        free(tmp);
    }
}
 
void main(){
    isi_data();
    int x;
    printf("input nilai yang mau dicari: ");
    scanf("%d",&x);
    if(binarySearch(x)==NULL) printf("data tidak ditemukan");
    else printf("data ditemukan");
    bersihkan_memori();
}

Output: