Summary before Midterm

Christophorus Wilson Sucahyo

2301869273

LINKED LIST

Pointer

Pointer is used to pass information back and forth between a function and its reference points.

Pointer dapat menyimpan alamat memory dan menyimpan sebuah value.

Ex.

Int *p, a = 10;

p = &a;

*p=3;

Maka di value di variable a akan berubah menjadi 3.

Array

Kita dapat menginisialisasi elemen untuk disimpan di dalam array, menginput elemen melalui program, atau memasukan elemen.

Ex.

Inisialisasi elemen

Int angka[3] = {3, 2, 1};

Input elemen

Int angka[3];

for(int index=0;index<3;index++){
scanf(“%d”, &angka[index]);

}

Memasukan elemen

Int angka1[3] = {3, 2, 1};

Int angka2[3];

for(int i=0;i<3;i++){

angka2[i]=angka1[i];

}

Structure

Structure adalah tipe data yang dibuat sendiri oleh user yang dapat menyimpan banyak tipe data sekaligus.

Ex.

Struct mahasiswa{

Int age;

Char nama[30];

Char nim[10];

Double gpa;

};

mahasiswa y; // artinya sebuah variabel dari struct mahasiswa

mahasiswa array[10]; // artinya sebuah array dari struct mahasiswa berjumlah 10

Nested Structure

Struct mahasiswa{

Int age;

Char nama[30];

Char nim[10];

Double gpa;

};

Struct address[

Struct mahasiswa k;

char alamat[50];

};

Tipe Struktur Data

Array : kumpulan elemen bertipe data sama

Linked List : struktur data yang dinamis dan dapat dimanipulasi dengan mudah

Queue : FIFO  (first in first out). Artinya elemen yang dimasukan pertama akan menjadi yang pertama dikeluarkan juga

Stacks : LIFO (last in first out) / FILO (first in last out). Artinya elemen yang dimasukan pertama akan menjadi yang terakhir keluar dan begitu juga sebaliknya.

Binary Trees : Struktur data berupa kumpulan elemen yang disebut nodes. Setiap node memiliki pointer kiri, pointer kanan, dan sebuah elemen data.

Linked List

Linked list adalah struktur data yang didalamnya terdapat sequence data yang sudah disimpan. Di setiap datanya terdapat penanda yang mengarahkan ke data selanjutnya.

Terdapat method insertion dan deletion linked list.

Single Linked List

Gambar diatas merupakan contoh dari linked list.

Setiap data memiliki 2 space, satu untuk value, satu untuk link menuju ke data selanjutnya.

Di data terakhir akan memiliki link menuju NULL value.

Circular Single Linked List

Bedanya dengan single linked list adalah data terakhir akan memiliki link menuju data pertama.

Double Linked List

Setiap data memiliki link yang menghubungkan data tersebut dengan data selanjutnya dan data sebelumnya.

Circular Double Linked List

Di data terakhir memiliki link yang menghubungkan data tersebut menuju ke data pertama.

STACK AND QUEUE

Stack vs Queue

Keduanya adalah struktur data yang berfungsi untuk menyimpan data secara berurutan. Perbedaannya terdapat pada sifatnya.

Sifat dari Stack adalah LIFO (Last In First Out). Analoginya adalah seperti buku yang ditumpuk, buku yang terakhir kali diletakkan (paling atas)  adalah yang pertama kali diambil.

Sedangkan sifat dari Queue adalah FIFO (First In First Out). Analoginya seperti mengantri di kasir pada umumnya. Orang yang pertama kali masuk adalah yang pertama kali dilayani.

Stack

Stack dapat direpresentasikan menggunakan array dan linked list.

Pada array, terdapat 2 variabel TOP dan MAX. TOP adalah variabel penanda index paling kanan yang berisi. Jadi apabila variabel TOP = NULL , maka berarti array tersebut kosong. Sedangkan MAX adalah total elemen yang dapat disimpan dalam array tersebut.

Sedangkan pada linked list, pointer START digunakan sebagai variabel TOP. Jika TOP = NULL , maka berarti linked list tersebut kosong.

Perbedaan mendasar dari array dan linked list adalah array membutuhkan sebuah nilai pasti untuk menentukan batas dari isi sebuah array, namun linked list tidak membutuhkan nilai apapun karena linked list bersifat dinamis.

Stack Operations

Push()   : memasukkan elemen ke dalam stack

Pop()     : menghapus/menghilangkan elemen dari stack

Top()     : menunjukkan elemen paling atas dari sebuah stack

Infix, Postfix, Prefix

Infix       : (operand) (operator) (operand)

Contoh : 4 + 5 * 8 + 2

Untuk mengubah menjadi bentuk Postfix, maka kita membaca notasi Infix dari kiri ke kanan.

Sedangkan untuk mengubah menjadid bentuk Prefix, maka kita melakukan sebaliknya yaitu kanan ke kiri.

Postfix  : (operand) (operand) (operator)

Contoh : 4 5 8 * + 2 +

Prefix    : (operator) (operand) (operand)

Contoh : + 4 + * 5 8 2

Depth First Search

DFS adalah algoritma untuk mencari sebuah elemen di dalam sebuah graph atau tree. Algoritma ini akan terus berjalan sampai menemukan elemen tersebut sebelum melakukan backtrack (recursive).

Queue

Queue juga dapat diimplementasikan menggunakan array atau linked list.

Pada array, digunakan 2 variabel untuk menandakan index paling depan (FRONT) dan index paling belakang (REAR). Deletion dan Insertion dapat dilakukan di FRONT maupun REAR.

Sedangkan pada linked list, pointer START digunakan sebagai FRONT. Apabila FRONT = REAR = NULL , maka berarti queue tersebut kosong.

Queue Operations

Push()   : memasukkan elemen di index paling belakang

Pop()     : menghapus/menghilangkan elemen dari index paling depan

Front()  : menunjukkan elemen dari index paling depan

Circular Queue

Apabila sebuah array queue sudah penuh dan kita masih memasukkan sebuah data ke dalamnya, akan terjadi overflow dan data tersebut akan tersimpan di luar array.

Oleh karena itu kita membutuhkan Circular Queue dengan menambahkan kondisi apabila index sudah mencapai index max, maka kembali ke index awal.

Breadth First Search

Algoritma untuk mencari elemen di sebuah tree atau graph. Algoritma akan terus berjalan mengunjungi setiap node di setiap level dan node yang bertetangga.                                                                         

HASHING, HASH TABLE AND BINARY TREE

Hashing

Hashing adalah semua method yang digunakan untuk menyimpan dan mengambil key dengan cepat. Di dalam hashing, string diubah menjadi bentuk string yang lebih pendek untuk mewakili string aslinya. Hashing digunakan untuk menjadi index dan mengambil elemen di database karena pencariannya lebih cepat menggunakan hashed key dibandingkan dengan value aslinya.

Distribusi hashing ke dalam sebuah array disebut dengan Hash Table dengan menggunakan fungsi yang disebut dengan Hash Function.

Hash Table

Hash Table adalah array tempat kita menyimpan value asli dari sebuah string. Index dari array tersebut adalah hashed key yang diambil dari value asli string tersebut.

Dari gambar diatas dapat dilihat bahwa apple diletakan di index 0 setelah  melewati proses Hash Function.

Hash Function

Ada beberapa cara untuk mengubah suatu string menjadi sebuah hashed key.

àMid-square

àDivision (paling sering digunakan)

àFolding

àDigit Extraction

àRotating Hash

Collision

Dalam metode penentuan hashed key, dapat terjadi situasi dimana beberapa data memuat hashed key yang sama. Hal ini disebut dengan Collision. Collision dapat diatasi dengan 2 cara.

èLinear Probing

*…%7 karena total elemen yang dapat disimpan adalah 7.

Proses 1 : Elemen 76. 76%7=6. Simpan di index 6.

Proses 2 : Elemen 93. 93%7=2. Simpan di index 2.

Proses 3 : Elemen 40. 40%7=5. Simpan di index 5.

Proses 4 : Elemen 47. 47%7=5. Seharusnya disimpan di index 5, namun karena index 5 telah terisi, maka cek index selanjutnya. Index 6 juga terisi, maka kembali ke index 0. Index 0 kosong, maka disimpan di index 0.

Dst.

Maka dapat disimpulkan bahwa metode linear probing adalah melintasi semua index (berawal dari index yang ditentukan dari hashed key) untuk mencari index yang kosong. Oleh karena itu, apabila terjadi banyak collision, linear probing akan memakan waktu yang lebih lama untuk menemukannya.

è Chaining

 

Asumsikan bahwa index 1, 3, 4, 5 telah terisi dengan elemen diatas. Kemudian elemen selanjutnya terjadi collision dengan elemen yang telah tersimpan.

Jacob memiliki hashed key yang sama dengan John, maka John menunjuk Jacob .

Martha memiliki hashed key yang  sama dengan Janet, maka Janet menunjuk Martha.

Claire memiliki hashed key yang sama dengan Janet dan Martha, maka Martha menunjuk Claire.

Maka dapat disimpulkan bahwa metode Chaining adalah metode yang menggunakan konsep Linked List, yaitu dengan menghubungkan sebuah data yang ada di dalam array dengan data yang mengalami collision.

Binary Tree

Sebuah tree adalah struktur data yang memperlihatkan hubungan antar objek data. Binary tree adalah sebuah tree yang setiap nodenya memiliki paling banyak 2 child nodes.

Struktur data binary tree :

struct tnode {

                char chr;

                struct tnode *left;

                struct tnode *right;
};

BINARY SEARCH TREE

Binary Search Tree (BST)

Binary Search Tree adalah struktur data yang memiliki searching dan sorting yang cepat, serta insertion dan deletion yang mudah.

Untuk node pada BST, node kiri akan bernilai lebih kecil dari parent nodenya sedangkan node kanan akan bernilai lebih besar dari parent nodenya (dengan asumsi bahwa key nya berbeda)

 

Pada BST, terdapat 3 basic operations :

-          find(x) : mencari key x di dalam BST

-          insert(x) : memasukkan key x ke dalam BST

-          remove(x) : menghapus key x dari dalam BST

Operation : Search ( find(x) )

-          Dimulai dari root

-          Jika x lebih kecil dari root, maka cari di subtree kiri

-          Jika x lebih besar dari root, maka cari di subtree kanan

 

Operation : Insertion ( insert(x) )

-          Dimulai dari root

-          Jika x lebih kecil dari value di node, maka lanjutkan pengecekan ke subtree kiri

-          Jika x lebih besar dari value di node, maka lanjutkan pengecekan ke subtree kanan

-          Ulangi (secara rekursif) hingga menemukan node kosong untuk x (x selalu menjadi leaf baru)

 

Operations : Deletion ( remove(x) )

-Jika x berada di leaf, maka node tersebut dapat langsung dihapus

-Jika x berada di node yang memiliki satu child, hapus node tersebut dan pindahkan value dari child ke parent

-Jika x berada di node yang memiliki dua child, maka cari child kanan dari subtree kiri, hapus value x, pindahkan value dari child menuju node x, dan hapus node child. (sebaliknya dapat mencari child kiri dari subtree kanan)

Gambar diatas adalah contoh x yang berada di leaf. Node tersebut dapat langsung dihapus.

Gambar diatas adalah contoh x yang memiliki dua child. Tentukan dulu subtree mana yang ingin kita gunakan. Pada contoh diatas kita menggunakan child kanan dari subtree kiri. Langkah pertama adalah hapus x, kemudian pindahkan nilai dari child node ke parent node.

Source code for application of minimarket concept :
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct node{
char product[20];
int quantity;
int price;
struct node *prev, *next;
}*head=NULL, *tail=NULL;

void input(char product[], int quantity){
struct node *newnode = (struct node*)malloc(sizeof(struct node));
struct node *ptr = head;
strcpy(newnode->product, product);
newnode->quantity = quantity;
newnode->price = rand()%100*1000;
newnode->next=NULL;
newnode->prev=NULL;
if(head==NULL){
head=tail=newnode;
}else if(strcmp(newnode->product, head->product)<0){
newnode->next=head;
head->prev=newnode;
head=newnode;
}else if(strcmp(newnode->product, tail->product)>0){
tail->next=newnode;
newnode->prev=tail;
tail=newnode;
} else{
while(ptr!=NULL){
if(strcmp(newnode->product, ptr->product)>0){
break;
}else ptr=ptr->next;
}
newnode->prev = ptr;
newnode->next = ptr->next;
ptr->next->prev = newnode;
ptr->next = newnode;
}
}

void printbill(){
struct node *ptr = head;
int total=0;
printf("\n\nALPHAMART\n");
while(ptr!=NULL){
int count=rand();
printf("%s, %d x %d = %d\n", ptr->product, ptr->quantity, ptr->price, ptr->price*ptr->quantity);
total+=ptr->price*ptr->quantity;
ptr=ptr->next;
}
printf("Total : %d\n", total);
printf("Thankyou for shopping!\n");
printf("Kindness is free! :)\n");
}

void printdata(){
struct node *ptr = head;
int total=0;
printf("Cart\n");
printf("-------------------------------------------\n");
while(ptr!=NULL){
int count=rand();
printf("%s, %d for %d each\n", ptr->product, ptr->quantity, ptr->price);
ptr=ptr->next;
}
printf("-------------------------------------------\n");
}

void editquantity(char product[], int quantity){
struct node *ptr = head;
int count=0;
while(ptr!=NULL){
if(strcmp(product, ptr->product)==0){
ptr->quantity=quantity;
count=1;
break;
}
ptr=ptr->next;
}
if(count==0){
printf("\nProduct is not found!\n");
}else{
printf("\nQuantity has been changed\n");
}
}

int productchecker(char product[]){
struct node *ptr = head;
int count=0;
while(ptr!=NULL){
if(strcmp(product, ptr->product)==0){
count=1;
break;
}
ptr=ptr->next;
}
return count;
}

void productdeletion(char product[]){
struct node *ptr = head;
if(head==tail && strcmp(head->product, product)==0){
head = NULL;
free(head);
}else if(strcmp(head->product, product)==0){
head=head->next;
head->prev=NULL;
free(head->prev);
}else if(strcmp(tail->product, product)==0){
tail=tail->prev;
tail->next=NULL;
free(tail->next);
}else{
while(ptr!=NULL){
if(strcmp(ptr->product, product)==0){
break;
}
ptr = ptr->next;
}
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
free(ptr);
}
}

int main(){
int menu, quantity, count;
char product[20];
do{
system("cls");
count=0;
printf("WELCOME TO ALPHAMART!\n");
printdata();
printf("Choose the menu below :\n");
printf("1. Purchase\n");
printf("2. Edit\n");
printf("3. Delete a product\n");
printf("4. Exit\n");
printf("Your choice : ");
scanf("%d", &menu);
getchar();
switch(menu){
case 1:
system("cls");
printf("PURCHASE MENU\n");
printf("Type the product name: ");
gets(product);
printf("Type quantity: ");
scanf("%d", &quantity);
input(product, quantity);
printf("\n\nProduct has been added to cart!\n");
printf("Press anything to continue...");
getchar();
getchar();
break;
case 2:
system("cls");
printf("EDIT QUANTITY\n");
if(head==NULL){
printf("\nNo data is available.\n\n");
printf("Press anything to continue...");
getchar();
}else{
printf("Type the product name: ");
gets(product);
count = productchecker(product);
if(count==0){
printf("\nData is not found\n\n");
}else{
printf("New quantity: ");
scanf("%d", &quantity);
editquantity(product, quantity);
getchar();
}
printf("Press anything to continue...");
getchar();
}
break;
case 3:
system("cls");
printf("DELETE PRODUCT\n");
if(head==NULL){
printf("\nNo data is available.\n\n");
}else{
printf("Type the product name: ");
gets(product);
count = productchecker(product);
if(count==0){
printf("\nData is not found\n\n");
}else{
productdeletion(product);
printf("\n\nProduct is deleted\n");
}
}
printf("Press anything to continue...");
getchar();
break;
}

}while(menu!=4);
printbill();
return 0;
}