Rangkuman Mid Semester dan soal Coding
A. Linked list
Apa itu Linked List?
- Linked list adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer. - Rangkaian single linked list tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke null.
Ada beberapa macam dari single linked list yaitu :
1. Single Link List
Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL.
Berikut contoh source code utk singled link list :
#include<stdio.h>
#include<stdlib.h>
struct data
{
int value;
struct data *next;
}tdata, *h, *t;
void pushBelakang(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
t->next = curr;
t = curr;
}
}
void pushDepan(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
curr->next = h;
h = curr;
}
}
void pushTengah(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
struct data *temp = h;
while (temp->next->value < v)
{
temp = temp->next;
}
curr->next = temp->next;
temp->next = curr;
}
}
void push(int v)
{
if (h == NULL) //List Kosong
{
pushDepan(v);
}
else
{
if (v <= h->value)
{
pushDepan(v);
}
else if (v >= t->value)
{
pushBelakang(v);
}
else
{
pushTengah(v);
}
}
}
void popDepan()
{
if (h == NULL)
return;
struct data *c = h;
if (h == t)
h = t = NULL;
else
h = h->next;
free(c);
}
void popBelakang()
{
if (h == NULL)
return;
struct data *c = h;
if (h == t)
h = t = NULL;
else
{
while (c->next != t)
{
c = c->next;
}
free(t);
t = c;
t->next = NULL;
}
}
void pop(int v)
{
if (h == NULL)
return;
struct data *temp = h;
while (temp->value != v)
{
temp = temp->next;
if (temp == NULL)
return;
}
if (temp == h)
{
popDepan();
}
else if (temp == t)
{
popBelakang();
}
else
{
struct data *t = h;
while (t->next != temp)
{
t = t->next;
}
t->next = temp->next;
free(temp);
}
}
void popAll()
{
while (h != NULL)
{
popDepan();
}
}
void printAll()
{
struct data *c = h;
while (c != NULL)
{
printf(" %d ", c->value);
c = c->next;
}
}
int main()
{
h = t = NULL;
push(25);
push(30);
push(5);
push(15);
push(20);
push(50);
push(40);
push(70);
push(0);
printAll();
printf("\n");
pop(0);
pop(70);
pop(40);
pop(100);
printAll();
printf("\n");
popAll();
return 0;
}
2. Double Linked List
Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya.
Contoh dari double linked list :
Contoh code dari double linked list :
#include<stdio.h>
#include<stdlib.h>
struct data
{
int value;
struct data *next;
struct data *prev;
}tdata, *h, *t;
void pushBelakang(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
curr->prev = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
t->next = curr;
curr->prev = t;
t = curr;
}
}
void pushDepan(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
curr->prev = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
curr->next = h;
h->prev = curr;
h = curr;
}
}
void pushTengah(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
curr->prev = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
struct data *temp = h;
while (temp->next->value < v)
{
temp = temp->next;
}
curr->next = temp->next;
curr->prev = temp;
temp->next->prev = curr;
temp->next = curr;
}
}
void push(int v)
{
if (h == NULL) //List Kosong
{
pushDepan(v);
}
else
{
if (v <= h->value)
{
pushDepan(v);
}
else if (v >= t->value)
{
pushBelakang(v);
}
else
{
pushTengah(v);
}
}
}
void popDepan()
{
if (h == NULL)
return;
struct data *c = h;
if (h == t)
h = t = NULL;
else
{
h = h->next;
h->prev = NULL;
}
free(c);
}
void popBelakang()
{
if (h == NULL)
return;
struct data *c = t;
if (h == t)
h = t = NULL;
else
{
t = t->prev;
t->next = NULL;
free(c);
}
}
void pop(int v)
{
if (h == NULL)
return;
struct data *temp = h;
while (temp->value != v)
{
temp = temp->next;
if (temp == NULL)
return;
}
if (temp == h)
{
popDepan();
}
else if (temp == t)
{
popBelakang();
}
else
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
}
void popAll()
{
while (h != NULL)
{
popDepan();
}
}
void printAll()
{
struct data *c = h;
while (c != NULL)
{
printf(" %d ", c->value);
c = c->next;
}
}
int main()
{
h = t = NULL;
//struct data tdata2;
push(25);
push(30);
push(5);
push(15);
push(20);
push(50);
push(40);
push(70);
push(0);
printAll();
printf("\n");
pop(0);
pop(70);
pop(40);
pop(100);
printAll();
printf("\n");
popAll();
return 0;
}
3. Circular Linked List
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :
- Circular Single Linked List
- Circular Double Linked List
B. Hashing and Hashing Tables
- Hasing adalah Transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya.
- Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash table). Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.
- Fungsi hash menyimpan nilai asli atau kunci pada alamat yang sama dengan nilai hash-nya. Pada pencarian suatu nilai pada tabel hash, yang pertama dilakukan adalah menghitung nilai hash dari kunci atau nilai aslinya, kemudian membandingkan kunci atau nilai asli dengan isi pada memori yang beralamat nomor hash-nya. Dengan cara ini, pencarian suatu nilai dapat dilakukan dengan cepat tanpa harus memeriksa seluruh isi tabel satu per satu.
- Hashing adalah cara untuk menyimpan data yang akan kita buat lebih singkat dengan menggunakan key. Dan data tersebut akan disimpan dalam bentuk array. Berikut beberapa jenis hash function yaitu :
1. Mid-Square
2. Fold
3. Rotasi Hash
4. Ekstrasi Digit
5. Divisi ( Paling Umum )
- Selain itu, ada yang disebut dengan collision, collision adalah cara handle ketika hash key yang telah ada sama / sejenis/ tidak unik , maka kita butuh dalam penanganan case ini :
Ada 2 jenis dalam Collision :
1. Chaining
Teknik Chaining merupakan suatu teknik untuk mengatasi collision (bentrokan) dengan cara menggunakan daerah di luar tabel Hash dalam bentuk linier. Bentuk linier ini bisa berupa linked-list atau array. Urutan data pada daerah overflow bisa terurut atau random, tergantung cara penyisipan yang dilakukan.
2. 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
C. Binary Search 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. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Ada 3 jenis dalam melakukan cara untuk penulusuran data pada BST:
PreOrder : Print data, telusur ke kiri, telusur ke kanan
InOrder : Telusur ke kiri, print data, telusur ke kanan
Post Order : Telusur ke kiri, telusur ke kanan, print data
Berikut Source Code utk BST :
#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();
}
D. JAWABAN SOAL DATA STRUCTURE MEMBUAT MENU
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
struct Market{
char name[100];
int quantity;
int price;
struct Market *next,*prev;
}*head,*tail,*curr,*temp;
void pushItem(char name[], int quantity, int price){
curr = (struct Market*)malloc(sizeof(Market));
strcpy(curr->name,name);
curr->quantity = quantity;
curr->price = price;
curr->next = NULL;
curr->prev = NULL;
if(head == NULL){
head = tail = curr;
}
else{
tail->next = curr;
curr->prev = tail;
tail = curr;
}
}
void deleteItem(char name[]){
if(head == NULL){
printf("Your Menu is empty\n");
getchar();
return;
}
curr = head;
while(curr!=NULL){
if(strcmp(curr->name,name)==0)
break;
if(strcmp(curr->name,name)>0){
printf("Your Input not found\n");
getchar();
return;
}
curr = curr->next;
}
if(curr == NULL)
printf("Not Found");
else if(curr == head && !curr->next)
head = NULL;
else if(curr == head){
head->next->prev = NULL;
head = curr->next;
}
else if(curr == tail){
curr->prev->next = NULL;
tail = curr->prev;
}
else{
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
}
free(curr);
}
void deleteMenu(){
char name[50];
int quantity;
int len;
do{
printf("Input item name you want to delete>> ");
scanf("%[^\n]", name);getchar();
len = strlen(name);
}while(len < 1);
curr = head;
while(curr!= NULL){
if(strcmp(curr->name,name)==0)
break;
curr = curr->next;
}
if(curr = NULL){
printf("Not Found");
getchar();
return;
}
deleteItem(name);
printf("Succesfully deleted");
getchar();
}
void edit(char name[],int quantity,int price,int upqty){
curr = head;
while(strcmp(curr->name,name) != 0){
curr = curr->next;
if(curr == NULL){
printf("There's no word exist'");getchar();
return;
}
}
strcpy(curr->name,name);
curr->quantity = upqty;
curr->price = price;
}
void CheckOut(){
if(head == NULL){
printf("Your Menu is empty");
getchar();
return;
}
curr = head;
int index = 0;
int total = 0;
printf("-------------------------------------------------------------------------------------\n");
printf("| List Menu |\n");
printf("|-----------------------------------------------------------------------------------|\n");
printf("| No | Item Name | Qty | Price | Total |\n");
printf("-------------------------------------------------------------------------------------\n");
while(curr != NULL){
printf("= %3d = %-35s = %6d = Rp.%7d = Rp. %11d =\n",++index,curr->name,curr->quantity,curr->price, curr->quantity*curr->price);
total += curr->quantity*curr->price;
curr = curr->next;
}
printf("------------------------------------------------------------------------------------");
printf("|-----------------------------Discount---------------------------|= Rp. %11d =\n", total);
puts("--------------------------------------------------------------------------------------");
printf("=------------------------------Total------------------------------= Free =\n");
printf("-----------------------Kindness is Free!!-------------------------------------------");
getchar();
}
void printList(){
if(head==NULL){
printf("Your menu is empty\n");
getchar();
return;
}
curr = head;
int index = 0;
printf("-------------------------------------------------------------------\n");
printf("| List Menu |\n");
printf("|-----------------------------------------------------------------|\n");
printf("| No | Item Name = Qty = Price |\n");
printf("-------------------------------------------------------------------\n");
while(curr!= NULL){
printf("| %3d | %-35s | %6d | Rp.%7d |\n",++index,curr->name,curr->quantity,curr->price);
curr = curr->next;
}
printf("|-----------------------------------------------------------------|");
}
void popHead(){
curr = head;
head = curr->next;
free(curr);
}
void popAll(){
curr = head;
while(head != NULL){
popHead();
}
}
int main(){
int choice;
char name[100];
int quantity;
int price;
int len;
int upqty;
do{
system("cls");
printf("Market Menu!!\n\n");
printf("1. View List\n");
printf("2. Add New Item on List\n");
printf("3. Edit Quantity Item on List\n");
printf("4. Delete Item on List");
printf("5. Checkout Item\n");
printf("6. Exit\n");
printf("Choose >> ");
scanf("%d",&choice);getchar();
printf("\n\n");
if(choice == 1){
printList();
getchar();
}
else if(choice == 2)
{
do{
printf("Input Item Name[1..100]: ");
scanf("%[^\n]",name);getchar();
len = strlen(name);
}while(len < 1 || len > 100);
do{
printf("Input %s quantity >> ",name);
scanf("%d", &quantity);getchar();
}while(quantity < 1);
printf("\n");
price = rand() % 79999 + 15000;
pushItem(name,quantity,price);
printf("Add Item Successful!\n");
printf("Press Enter to continue...");
getchar();
}
else if(choice == 3)
{
printf("Input Item Name you want to edit: ");
scanf("%[^\n]",name);getchar();
printf("Input Update Quantity: ");
scanf("%d",&upqty);getchar();
edit(name,quantity,price,upqty);
}
else if(choice == 4)
{
deleteMenu();
}
else if(choice == 5){
CheckOut();
}
else if(choice == 6){
popAll();
system("cls");
printf("List Menu successfully deleted!");
getchar();
}
}while(choice!=6);
}
