Rangkuman setengah semester dan soal coding

Apa itu Linked List

Linked list adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan).

Macam- Macam Linked List yang akan dibahas kali ini:

1.Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL. Berikut source code linked list;
struct data
{
 int angka;
 struct data *next;
}*head,*tail,*curr;

void pushdpn(int a){
 curr = (struct data*) malloc(sizeof(struct data));
 curr->angka = a;
 
 if (head==NULL)
 {
  head=tail=curr;
  tail->next=NULL;
 }
 else
 {
  curr->next=head;
  head=curr;
 }
}
void pushblkg(int a)
{
 curr=(struct data*) malloc (sizeof(struct data));
 curr->angka=a;
 
 if (head==NULL)
 {
  head=tail=curr;
  tail->next=NULL;
 }
 
 else
 {
  tail->next=curr;
  tail=curr;
  tail->next=NULL;
 }
}
void pop(int a){
 curr=head;
 if (curr->angka==a)
 {
         if (head!=NULL)
        {
          curr=head;
          head=head->next;
          free(curr);
        }
 }
 else
 {
  while (curr->next->angka!=a)
  {
   curr=curr->next;
  }
  struct data *temp;
  temp=curr->next;
  curr->next=temp->next;
  free(temp);
 }
}
void cetak()
{
 curr=head;
 while(curr!=NULL)
 {
  printf("%d ", curr->angka);
  curr=curr->next;
 }
}
int main (){
 pushdpn(10);
 pushblkg(100);
 pushblkg(40);
 pushdpn(200);
 pop(100);
 cetak();
 
 
 return 0;
}

2. Circular Single Linked List 

 Merupakan suatu linked list dimana tail(node terakhir) menunjuk ke head (node pertama). Jadi, tidak ada pointer yang menunjuk ke NULL.

3. Circular double Linked List 

Hampir sama dengan Circular Single Linked list, akan tetapi ada 2 pointer di setiap nodes.

4. Double Linked List 

 Merupakan suatu linked list yang memiliki dua variabel pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tail juga menunjuk ke NULL.

Apa itu Hashing

Hashing adalah cara untuk menyimpan data dimana data kita akan dibuat lebih singkat dengan menggunakan key. Biasa nya data nya bisa disimpan dalam bentuk array.Ada beberapa jenis hash function
a. Mid-square

b. Divisi (paling umum)

c. Fold

d. Ekstraksi Digit

e. Rotasi Hash

Untuk collision adalah cara handle ketika hash key kita sama sehingga tidak unik lagi, makanya kita butuh penanganan kejadian seperti ini. Ada 2 jenis penanganan collision;
1. Linear Probing

Pada saat terjadi collision, maka akan mencari posisi yang kosong di bawah tempat terjadinya collision, jika masih penuh terus ke bawah, hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong berarti HashTable sudah penuh

2. Chaining

Tambahkan key and entry di manapun dalam list (lebih mudah dari depan)

Kerugian:   Overhead pada memory tinggi jika jumlah entry sedikit

Keunggulan dibandingkan open addressing:

-          Proses insert dan remove lebih sederhana

-          Ukuran Array bukan batasan (tetapi harus tetap meminimalisir collision: buat ukuran tabel sesuai dengan jumlah key dan entry yang diharapkan)

Binary Tree

Binary Search Tree adalah binary tree yang sudah di sort atau diurutkan

Bagian sub kiri tree mengandung element yang lebih kecil daripada yang tersimpan di variabel x
Bagian sub kanan tree mengandung element yang lebih besar daripada yang tersimpan di variabel x

3 operasi dalam binary tree search adalah
1. Find key(x)

Anggaplah kata kunci nya adalah variabel x:
I. Kita mulai dari akar
II. Jika root berisi X maka pencarian berhasil dihentikan.
III. Jika X kurang dari kunci root, maka cari secara rekursif pada sub pohon kiri, jika tidak cari secara rekursif pada sub pohon kanan.

2. Insert key (x) pakai metode rekursif

Anggaplah kata kunci nya adalah variabel x:

I. Mulailah dari akar

II. Jika X kurang dari kunci simpul maka masukkan X ke sub pohon kiri,  jika tidak masukkan X ke sub pohon kanan

III. Ulangi sampai kami menemukan simpul kosong untuk meletakkan X  (X akan selalu menjadi daun baru)

3. Remove key (x)

Ada 3 kasus yang harus dipertimbangkan:

I. Jika kunci ada di daun, hapus saja simpul itu.

II. Jika kunci ada di simpul yang memiliki satu anak, hapus simpul itu dan sambungkan anaknya

 ke induknya

III.  Jika kunci ada di simpul yang memiliki dua anak, temukan anak paling kanan dari sub pohon kirinya (simpul P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih anak paling kiri dari sub pohon kanannya)

Soal coding AprilMarket with double linked list source code:

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

struct data{
char nama[101];
int jumlah;
long long int harga;
struct data *next, *prev;
}*head=NULL,*tail=NULL,*curr=NULL;

void pushdpn(char namaI[],int jumlahI,long long int hargaI){
curr=(struct data*) malloc(sizeof(struct data));

strcpy(curr->nama,namaI);
curr->jumlah=jumlahI;
curr->harga=hargaI;

if (head==NULL)
{
head=tail=curr;
}
else
{
curr->next=head;
head->prev=curr;
head=curr;
}
tail->next=head->prev=NULL;
}

void pushblkg(char namaI[],int jumlahI,long long int hargaI){
curr=(struct data*) malloc(sizeof(struct data));
strcpy(curr->nama,namaI);
curr->jumlah=jumlahI;
curr->harga=hargaI;
if (head==NULL)
{
head=tail=NULL;
}
else
{
tail->next=curr;
curr->prev=tail;
tail=curr;
}
head->prev=tail->next=NULL;
}

void push(char namaI[],int jumlahI, long long int hargaI)
{
curr = (struct data*)malloc(sizeof(struct data));

strcpy(curr->nama,namaI);
curr->jumlah=jumlahI;
curr->harga=hargaI;

if (head==NULL)
{
head=tail=curr;
}

else if (strcmp(curr->nama,head->nama)<0)
{
pushdpn(namaI,jumlahI,hargaI);
}
else if (strcmp(curr->nama,tail->nama)>0)
{
pushblkg(namaI,jumlahI,hargaI);
}
else
{
struct data*temp;
temp=head;

while (strcmp(temp->next->nama,curr->nama)<0)
{
temp=temp->next;
}

curr->next = temp->next;
temp->next->prev=curr;
temp->next=curr;
curr->prev=temp;
}
}

void edit(char namaI[],int jumlahI, long long int hargaI)
{
struct data *search=head;
while (search!=NULL)
{
if (strcmp(search->nama,namaI)==0)
{
search->jumlah=jumlahI;
search->harga=hargaI;
break;
}
search=search->next;
}
}

void popdpn()
{
curr =head;
head=head->next;
free (curr);
head->prev=NULL;
}

void popblkg(){
curr=tail;
tail=tail->prev;
free(curr);
tail->next=NULL;
}

void pop(char namaI[]){

if(strcmp(head->nama,namaI)==0)
{
popdpn();

}

else if (strcmp(tail->nama,namaI)==0)
{
popblkg();

}
else
{
struct data *temp = head;
int val=0;
val = strcmp(temp->next->nama,namaI);
while(val!=0)
{
temp=temp->next;
}
curr=temp->next;
temp->next=curr->next;
curr->next->prev=temp;
free(curr);
}
}


void cetak(){
curr=head;
if (curr==NULL)
{
printf("No Data\n");
}
else
{
printf("| %-10s | %-3s | %-10s | %-10s |\n","Nama Barang", "Jumlah Barang", "Harga","Total");
printf("-----------------------------------------------------------------\n");
while(curr!=NULL)
{
long long int total=curr->jumlah*curr->harga;
printf("| %-11s | %-13d | %-10lld | %-10lld |\n",curr->nama,curr->jumlah,curr->harga,total);
curr=curr->next;
}
}
printf("-----------------------------------------------------------------\n");
printf("Grand Total= Kindness is Free\n") ;
puts("");
}

int n=0;

//opsi tampilan

void menu(){
printf("Welcome to Aprilmarket\n");
printf("------------------------\n");
printf("1. Add Item\n");
printf("2. Edit Item Quantity\n");
printf("3. Delete Item\n");
printf("4. Print the bill\n");
printf("5. Exit\n");
printf("Your choice: ");
scanf("%d",&n);getchar();
}
void add(){
char NamaInput[101];
int jumlah=0;
long long int harga=0;
printf("Masukkan nama barang: ");
scanf("%[^\n]",NamaInput); getchar();
puts("");
printf("Masukkan jumlah yang dibeli: ");
scanf("%d",&jumlah);
getchar();
harga=(rand()%100)*1000;
push(NamaInput,jumlah,harga);
printf("Barang berhasil ditambahkan!\n\n");
}
void ganti(){
char NamaInput[101];
int jumlah=0;
long long int harga=0;
printf("Masukkan nama barang yang diedit: ");
scanf("%[^\n]",NamaInput); getchar();
puts("");
printf("Masukkan jumlah barang yang diedit: ");
scanf("%d",&jumlah);
getchar();
harga=(rand()%100)*1000;
edit(NamaInput,jumlah,harga);
printf("Barang berhasil diedit!\n\n");
}
void buang(){
char NamaInput[101];
printf("Masukkan nama barang: ");
scanf("%[^\n]",NamaInput); getchar();
puts("");
pop(NamaInput);
printf("Barang berhasil dihapus!\n\n");
}


int main(){
srand(time(0));
do{
menu();
if (n==1)
{
add();
}
else if (n==2)
{
ganti();
}
else if (n==3)
{
buang();
}
else if (n==4)
{
cetak();
n=5;
}
}while(n!=5);


return 0;
}