Rangkuman Materi
Rangkuman Materi
Pembahasan Mengenai Linked List
Linked list merupakan struktur data yang memiliki urutan record data lainnya.
Di dalam linked list, terdapat elemen data lainnya yang biasanya disebut dengan node. di dalam elemen data tersebut, terdapat head dan tail, head merupakan elemen yang terdapat pada linked list yang berada diposisi pertama, sedangkan tail merupakan kebalikan dari head,yang memiliki arti elemen terakhir yang terdapat dalam linked list.
Linked list merupakan salah satu fungsi yang dapat digunakan untuk menyimpan data, sama seperti array. Tetapi yang membedakannya adalah array bersifat statis dan linked list bersifat dinamis. Statis yang dimaksud adalah memori yang akan dipakai harus dipesan dibagian awal, sedangkan linked list yang memiliki sifat dinamis adalah kita bisa pesan secara bebas sesuai kebutuhan dan lebih efektif
Jenis - Jenis Linked List :
1. Single Linked List
Merupakan Linked list yang terdapat head dan tail, dan field pada tail biasanya menunjuk ke Null.
Contoh Single Linked List :
2. Double Linked List
Merupakan Linked list yang memiliki dua variabel pointer, yang dimana setiap head and tail menunjuk ke Null.
3. Circular Linked List
Merupakan Linked List yang tailnya menunjuk ke head, dan tidak ada pointer yang mengarah ke null.
Stack and Queue
1. Stack
Stack dalam bahasa Indonesia memiliki arti tumpukan. Sedangkan Stack dalam struktur data memiliki arti sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Stack menggunakan prinsip LIFO (Last In First Out) yang dimana data data yang dimasukan akan menumpuk dan jika dikeluarkan yang dikeluarkan adalah data terakhir yang dimasukan.
2. Queue
Queue dalam bahas Indonesia memiliki arti antrian. Yang dimana dalam struktur data memiliki arti suatu struktur data yang tersusun seperti antrian dimana ia menggunakan prinsip FIFO (First In First Out) kebalikan dari dari stack yang dimana data data yang masuk pertama akan menjadi data yang keluar pertama.
Hash Table & Binary Tree
Hash Table
Hash Table adalah struktur data yang mempunyai tabel dan fungsi yang berguna untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Berikut adalah contohnya yang saya ambil dari geeksforgeeks;
Operasi Pada Hash Tabel :
- Insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
- Find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
- Remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
- GetIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
Berikut kode yang saya dapatkan dari tutorialspoint.com :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 20
struct DataItem {
int data;
int key;
};
struct DataItem* hashArray[SIZE];
struct DataItem* dummyItem;
struct DataItem* item;
int hashCode(int key) {
return key % SIZE;
}
struct DataItem *search(int key) {
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
void insert(int key,int data) {
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
hashArray[hashIndex] = item;
}
struct DataItem* delete(struct DataItem* item) {
int key = item->key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key) {
struct DataItem* temp = hashArray[hashIndex];
//assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp;
}
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
void display() {
int i = 0;
for(i = 0; i<SIZE; i++) {
if(hashArray[i] != NULL)
printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
else
printf(" ~~ ");
}
printf("\n");
}
int main() {
dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
dummyItem->data = -1;
dummyItem->key = -1;
insert(1, 20);
insert(2, 70);
insert(42, 80);
insert(4, 25);
insert(12, 44);
insert(14, 32);
insert(17, 11);
insert(13, 78);
insert(37, 97);
display();
item = search(37);
if(item != NULL) {
printf("Element found: %d\n", item->data);
} else {
printf("Element not found\n");
}
delete(item);
item = search(37);
if(item != NULL) {
printf("Element found: %d\n", item->data);
} else {
printf("Element not found\n");
}
}
Binary Tree
Pohon biner atau binary tree adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.
Binary Search Tree
Apa itu Binary Serach Tree ? Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node.
Ada beberapa cara dalam menggunakan search tree :
- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Berikut saya lampirkan gambarnya :
Berikut saya lampirkan contoh codingan yang saya ambil dari mahircoding.com :
#include <stdio.h>
#include <stdlib.h>
//inisialisasi struct
struct data{
int number;
//pointer untuk menampung percabangan kiri dan kanan
data *left, *right;
}*root;
//fungsi push untuk menambah data
void push(data **current, int number){
//jika pointer current kosong maka akan membuat blok data baru
if((*current)==NULL){
(*current) = (struct data *)malloc(sizeof data);
//mengisi data
(*current)->number=number;
(*current)->left = (*current)->right = NULL;
//jika tidak kosong, maka akan dibandingkan apakah angka yang
//ingin dimasukkan lebih kecil dari pada root
//kalau iya, maka belok ke kiri dan lakukan rekursif
//terus menerus hingga kosong
}else if(number < (*current)->number){
push(&(*current)->left, number);
//jika lebih besar, belok ke kanan
}else if(number >= (*current)->number){
push(&(*current)->right, number);
}
}
//preOrder : cetak, kiri, kanan
void preOrder(data **current){
if((*current)!=NULL){
printf("%d -> ", (*current)->number);
preOrder(&(*current)->left);
preOrder(&(*current)->right);
}
}
//inOrder : kiri, cetak, kanan
void inOrder(data **current){
if((*current)!=NULL){
inOrder(&(*current)->left);
printf("%d -> ", (*current)->number);
inOrder(&(*current)->right);
}
}
//postOrder : kiri, kanan, cetak
void postOrder(data **current){
if((*current)!=NULL){
postOrder(&(*current)->left);
postOrder(&(*current)->right);
printf("%d -> ", (*current)->number);
}
}
//searching data
void search(data **current, int number){
//jika pointer current memiliki data
if((*current)!=NULL){
//cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
if(number<(*current)->number){
search(&(*current)->left,number);
//jika lebih besar, maka belok ke kanan
}else if(number>(*current)->number){
search(&(*current)->right,number);
//jika sama dengan, maka angka ketemu
}else{
printf("Found : %d", (*current)->number);
}
//jika tidak ada data lagi (not found)
}else{
printf("Not Found.");
}
}
void main(){
push(&root, 11);
push(&root, 22);
push(&root, 13);
push(&root, 15);
push(&root, 9);
inOrder(&root);
printf("\n");
preOrder(&root);
printf("\n");
postOrder(&root);
printf("\n");
search(&root,91);
getchar();
}
Berikut saya berikan Source code saya mengenai Dreamers Market :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#include<time.h>
struct node{
int nilai;
int harga;
char nama[100];
struct node *next;
struct node *prev;
}*head;
node *makeNode(int a, char arr[], int b);
struct node *pushHead(int a, char arr[]);
struct node *freeAll();
long long int randomPrice();
void print();
void cls();
void menu();
struct node *popHead();
node *makeNode(int a, char arr[], int b){
node *temp = (node*)malloc(sizeof(node));
temp->nilai = a;
temp->harga = b;
strcpy(temp->nama , arr);
temp->next=NULL;
temp->prev=NULL;
return temp;
}
struct node *pushHead(int a, char arr[], int b){
node *temp = makeNode(a,arr,b);
if(head==NULL){
head = temp;
}
else{
head->prev = temp;
temp->next = head;
head = temp;
}
return head;
}
struct node *freeAll(){
if(head==NULL){
return head;
}
else{
popHead();
}
}
struct node *deleteData(char arr[]){
node *curr = head;
if(head==NULL){
return head;
}
else{
while(strcmp(arr,curr->nama)!=0){
curr = curr->next;
}
if(curr->prev == NULL){
head = curr->next;
}
if(curr->next != NULL){
curr->next->prev = curr->prev;
}
if(curr->prev != NULL){
curr->prev->next = curr->next;
}
free(curr);
}
}
void print(){
node *curr = head;
if(head==NULL){
printf("No Data...");getchar();
cls();
menu();
}
while(curr!=NULL){
printf("Nama: %s\n", curr->nama);
printf("Qty: %d\n", curr->nilai);
printf("Harga: %d\n", curr->harga);
printf("Total Harga: %d\n", curr->harga * curr->nilai);
printf("\n");
curr = curr->next;
}
}
struct node *popHead(){
if(head==NULL){
return head;
}
else{
node *tbd = head;
head = head->next;
free(tbd);
return head;
}
}
void cls(){
for(int i=0; i<30; i++){
printf("\n");
}
}
long long int randomPrice(){
long lower = 100;
long upper = 999000;
return (rand() % (upper-lower+1) + lower);
}
void menu(){
printf("Dreamers Market\n");
printf("=====================\n");
printf("1. Masukkan Nama Barang\n");
printf("2. Delete Barang\n");
printf("3. Edit Kuantitas\n");
printf("4. Check Out\n");
printf("5. Exit\n");
printf("Menu yang dipilih: ");
int a=0;
int harga=0;
do{
scanf("%d", &a);getchar();
if(a<1 || a>10){
printf("Salah Memasukkan Data\n");getchar();
cls();
menu();
}
if(a==1){
cls();
char name[100];
int nilai;
printf("Input Nama Barang: ");
scanf("%[^\n]", name);getchar();
printf("Input Qty: ");
scanf("%d", &nilai);
harga = randomPrice();
pushHead(nilai , name, harga);
cls();
menu();
}
if(a==2){
cls();
printf("Input Barang yang ingin di delete (Case Sensitive): ");
char b[100];
scanf("%[^\n]", b);getchar();
deleteData(b);
cls();
menu();
}
if(a==3){
cls();
printf("Input Nama Barang Yang Ingin diedit: ");
}
if(a==4){
cls();
print();
printf("Kindness is Free!\n\n");
printf("Press Enter to Continue...");getchar();
cls();
menu();
}
if(a==5){
freeAll();
cls();
}
}while(a!=10);
}
int main(){
menu();
}
Comments
Post a Comment