Review Materi Semester 2 Data Structure
Pointer
Apa itu pointer?
Pointer, seperti nama bahasa inggrisnya, adalah tipe data di bahasa pemprograman c dan c++ dan berperan dalam penyimpnan "address" atau alamat dari suatu data dalam suatu block memori.
Linked List
Apa itu Linked List?
Seperti namanya, Linked list adalah struktur data yang dimodelkan linier, hampir sama dengan Array, well, keduanya adalah struktur data linier. Mereka mungkin terdengar sama, tetapi ada perbedaan di antara mereka.
Apa yang membedakan antara array dan Linked List?
Sementara kita tahu bahwa array disimpan dalam bentuk pada memori yang berdekatan, ini berbeda dalam kasus daftar tertaut, di mana mereka tidak benar-benar menggunakan lokasi yang berdekatan, melainkan, mereka menautkan satu sama lain menggunakan pointer.
Uniknya, Linked list dapat melakukan penambahan dan penghapusan dari elemen apapun di lokasi manapun, asalkan mereka terhubung.
Linked list dapat dibagi menjadi 4 jenis :
1. Singular Linked List
2. Double Linked List
3. Circular Single Linked List
4. Circular Double Linked List
Singular Linked List
Adalah linked list yang paling umum, dimana suatu linked list memiliki ujung pertama node yang bernama head dan memiliki ujung lainnya yang bernama tail, dimana tail akan menunjukan NULL.
Double Linked List
Seperti Linked List, yang membedakan Singular Linked list dengan doubly linked list adalah, Singular linked list hanya memiliki 1 pointer, yang menunjukan node selanjutnya, dimana pada doubly linked list, setiap node memiliki dua pointer, dimana pointer tersebut dapat menunjukkan node selanjutnya, maupun menunjukkan node sebelumnya.
Circular Single Linked List
Hampir mirip dengan singular linked list, yang membedakan singular linked list dengan versi cirularnya adalah, pointer next pada node tail, akan menunjukan addressnya kepada node head, sehingga mereka terhubung dan dapat dikatakan membentuk linkaran.
Circular Doubly Linked List
Seperti Circular Singular Linked List, yang membedakan circular single linked list dengan circular doubly linked list adalah jumlah pointernya, dimana pada node head, terdapat 2 pointer dimana pointer nextnya menunjukkan node selanjutnya, sedangkan pointer previousnya menunjukkan node tail. Sama seperti node headnya, pointer next dari node tail akan menunjukkan node head.
#include <stdio.h>
#include <stdlib.h>
struct Node{
int val;
struct Node* next;
}*head,*tail,*curr, *temp;
void pushmiddle(int val,int a){
curr = (struct Node*)malloc(sizeof(struct Node));
curr->val = val;
curr->next = NULL;
temp = head;
for(int i = 1; i < a; i++){
temp = temp->next;
}
if(temp->next==NULL)
{
printf("ERROR");
}
curr->next=temp->next;
temp->next=curr;
}
void pushhead(int val){
curr = (struct Node*)malloc(sizeof(struct Node));
curr->val = val;
curr->next = NULL;
if(head == NULL)
{
head = tail = curr;
}
else
{
curr->next=head;
head = curr;
}
}
void pushtail(int val)
{
curr = (struct Node*)malloc(sizeof(struct Node));
curr->val = val;
// curr->next = NULL;
if(head == NULL)
{
head = tail = curr;
tail->next=NULL;
}
else
{
tail->next = curr;
curr->next = NULL;
tail = curr;
}
}
void print()
{
curr = head;
while(curr!=NULL){
printf("%d ", curr->val);
curr = curr->next;
}
}
void poptail(){
curr = head;
while(curr->next!=tail)
{
curr = curr->next;
}
free(tail);
tail = curr;
tail->next=NULL;
}
void pophead(){
curr = head;
curr=curr->next;
free(head);
head = curr;
}
void popmiddle(int a)
{
temp = head;
for(int i = 1; i < a-1; i++){
temp=temp->next;
}
curr = temp->next;
temp->next = curr->next;
free(curr);
}
int main()
{
pushtail(10);
pushtail(20);
pushtail(30);
popmiddle(1);
print();
}
Linked List In C
Dari blog saya yang sebelumnya, kita lebih mengenal tentang Linked List, Perbedaan Linked List dengan Array, dan Jenis-Jenis Linked List yang ada. Nah, Sekarang ayo kita mencoba mempraktekkan membuat sebuah singly linked list di salah satu programming languange yang populer, C Programming Languange.#include <stdio.h>
#include <stdlib.h>
struct Node{
int val;
struct Node* next;
}*head,*tail,*curr, *temp;
void pushmiddle(int val,int a){
curr = (struct Node*)malloc(sizeof(struct Node));
curr->val = val;
curr->next = NULL;
temp = head;
for(int i = 1; i < a; i++){
temp = temp->next;
}
if(temp->next==NULL)
{
printf("ERROR");
}
curr->next=temp->next;
temp->next=curr;
}
void pushhead(int val){
curr = (struct Node*)malloc(sizeof(struct Node));
curr->val = val;
curr->next = NULL;
if(head == NULL)
{
head = tail = curr;
}
else
{
curr->next=head;
head = curr;
}
}
void pushtail(int val)
{
curr = (struct Node*)malloc(sizeof(struct Node));
curr->val = val;
// curr->next = NULL;
if(head == NULL)
{
head = tail = curr;
tail->next=NULL;
}
else
{
tail->next = curr;
curr->next = NULL;
tail = curr;
}
}
void print()
{
curr = head;
while(curr!=NULL){
printf("%d ", curr->val);
curr = curr->next;
}
}
void poptail(){
curr = head;
while(curr->next!=tail)
{
curr = curr->next;
}
free(tail);
tail = curr;
tail->next=NULL;
}
void pophead(){
curr = head;
curr=curr->next;
free(head);
head = curr;
}
void popmiddle(int a)
{
temp = head;
for(int i = 1; i < a-1; i++){
temp=temp->next;
}
curr = temp->next;
temp->next = curr->next;
free(curr);
}
int main()
{
pushtail(10);
pushtail(20);
pushtail(30);
popmiddle(1);
print();
}
Stack & Queue
Stack dan Queue adalah sejenis struktur data yang mengimplementasikan logika di dunia nyata, dimana pada konsep programming, konsep data struktur ini dapat dimplementasikan dengan pengunaan Linked List atau Array.
Stack
Pada data struktur Stack, kita dapat membayangkan sebuah stack itu seperti buku yang di tumpuk. Dimana, untuk mencapai buku yang terletak di urutan paling bawah, kita harus terlebih dahulu memindahkan buku yang dari paling atas menuju ke buku sebelum yang paling bawah, baru kita dapat mengambil buku yang paling bawah. Stack menggunakan konsep Last In, First Out (LIFO), dimana data yang terakhir kali masuk ke data struktur Stack akan keluar duluan.
Berikut ini adalah contoh kodingan saya mengenai Stack:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
char sandwich[100][100] = {
" // ",
" // ",
" _______________//__ ",
" .(______________//___).",
" | / |",
" |. . . . . . . / . . .|",
" \ . . . . . ./. . . . /",
" | / ___ | ",
" _.---._ |::......./../...\.:| ",
" _.-~ ~-._ |::::/::\::/:\::::::| ",
" _.-~ ~-._ |::::\::/::::::X:/::| ",
" _.-~ ~---.;:::::::/::\::/:::::| ",
" _.-~ ~\::::::n::::::::::| ",
" .-~ _.;::/::::a::::::::/ ",
" :-._ _.-~ ./::::::::d:::::::| ",
" `-._~-._ _..__.-~ _.-~|::/::::::::::::::| ",
" / ~-._~-._ / .__..--~----.YWWWWWWWWWWWWWWWP' ",
" \_____(_;-._\. _.-~_/ ~).. . \ ",
" /(_____ \`--...--~_.-~______..-+_______) ",
" .(_________/`--...--~/ _/ /\ ",
" /-._ \_ (___./_..-~__.....__..-~./ ",
" `-._~-._ ~\--------~ .-~_..__.-~ _.-~ ",
" ~-._~-._ ~---------' / .__..--~ ",
" ~-._\. _.-~_/ ",
" \`--...--~_.-~ ",
" `--...--~ "
};
struct stacknode{
char in[20];
struct stacknode *next;
}*top;
void pushhead(char insert[20]){
struct stacknode* newnode = (struct stacknode*) malloc(sizeof(struct stacknode));
strcpy(newnode->in,insert);
if(top == NULL)
{
top = newnode;
top->next = NULL;
}
else
{
newnode->next = top;
top = newnode;
}
}
void pophead(){
if(top == NULL)
printf("The Plate is Still Empty");
else
{
struct stacknode* newnode = (struct stacknode*) malloc(sizeof(struct stacknode));
newnode = top;
top = top->next;
free(newnode);
}
}
void printsandwich(){
if(top == NULL)
printf("The Plate is Still Empty");
else
{
struct stacknode* point = (struct stacknode*) malloc(sizeof(struct stacknode));
point = top;
while(point!=NULL)
{
printf("[%s]\n", point->in);
point=point->next;
}
printf("--------------------");
}
}
int main(){
int choice;
do{
system("cls");
char insert[20] = {0};
printf("Sandwich Stacker\n================\n");
printf("1. Add Topping\n");
printf("2. Remove Topping\n");
printf("3. View Sandwich\n");
printf("4. Exit Sandwich Program\n");
printf("[1,2,3,4]>> ");
scanf("%d", &choice);
Sleep(100);
switch(choice){
case 1:{
system("cls");
printf("Please Add a Topping to the Sandwich: ");
getchar();
scanf("%[^\n]", &insert);
getchar();
pushhead(insert);
break;
}
case 2:{
pophead();
break;
}
case 3:{
system("cls");
printsandwich();
printf("\n");
system("pause");
break;
}
}
}while(choice != 4);
system("cls");
for(int i = 0; i < 26; i++){
for(int j = 0; j < 63; j++){
printf("%c", sandwich[i][j]);
Sleep(1);
}
printf("\n");
}
}
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci sementara secara cepat dan cepat. Hashing digunakan sebagai struktur data karena misalnya, jika Anda ingin menemukan jika ada string tertentu yang ada dalam array, kita bisa membuat kunci untuk menghubungkannya dengan sehingga lebih mudah dan lebih efisien untuk melakukan fungsi pencarian untuk itu. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Contoh hashing dalam implementasi kehidupan nyata adalah cryptocurrency.
Meja Hash
Tabel hash adalah struktur data yang terdiri dari tabel dan fungsi untuk memetakan nilai kunci unik untuk setiap baris dan menjadi jumlah lokasi rekaman dalam tabel. Keuntungan dari tabel hash adalah bahwa waktu untuk mengakses lebih cepat karena catatan yang dicari berada di nomor hash dari lokasi penyimpanan.
Kunci Hash
Kunci hash adalah pengidentifikasi yang digunakan untuk pemetaan.
Fungsi Hash
Fungsi Hash adalah Fungsi yang digunakan untuk memproses pemetaan yang mengambil kunci sebagai input, dan kemudian menggunakan input itu untuk menemukan indeks yang diinginkan. Ada banyak cara untuk hash kunci:
Metode Mid-Square
Metode Mid Square menggunakan Nilai ASCII dari string yang dimasukkan. String yang diurai ke int kemudian dikuadratkan. Dengan nilai yang dikuadratkan, kita memilih bit r tengah angka.
Metode Pembagian
Metode ini cukup sederhana, Kunci dalam bilangan bulat yang Anda masukkan dibagi menggunakan modulo, yang menghasilkan sisa divisi, digunakan dalam pengindeksan
Metode Lipat
Metode ini melibatkan pemotongan nomor yang dimasukkan menjadi beberapa bagian. Kemudian, bagian-bagian tersebut ditambahkan bersama-sama untuk menghasilkan kunci yang dapat digunakan untuk menemukan indeks data yang diinginkan.
Metode Ekstraksi Digit
Metode ekstraksi digit menggunakan angka tertentu sebagai kunci, kemudian digit diekstraksi
Contoh: dalam 236747 digit, digit pertama, ketiga dan kelima diekstraksi, maka kita bisa mendapatkan 264 sebagai kunci hash.
Metode Rotasi
Digit yang dimasukkan terbalik. Contoh: 23301 diputar ke 10332, maka itu digunakan sebagai kunci.
Tabrakan adalah suatu kondisi yang terjadi ketika beberapa data memiliki kunci yang sama. Ini masalah karena bisa mengacaukan urutan data yang ingin dimasukkan. Untuk itu, ada dua solusi yang bisa digunakan.
Probing Linier
Linear Probing menggunakan slot array kosong untuk mengisi data kunci hash serupa berikutnya.
Rantai
Metode rantai menggunakan Daftar Tertaut, di mana data kunci hash yang sama dihubungkan berikutnya.
Tree
Tree adalah struktur data non-linear yang mewakili hubungan antara satu node ke yang lain.
Tree Pohon
Node di atas disebut sebagai root.
Garis yang menghubungkan induk ke anak adalah edge.
Node yang tidak memiliki anak disebut daun.
Node yang memiliki orang tua yang sama disebut saudara.
Derajat simpul adalah total sub pohon simpul.
Tinggi / Kedalaman adalah tingkat maksimum node dalam pohon.
Jika ada garis yang menghubungkan p ke q, maka p disebut leluhur q, dan q adalah turunan dari p.
Binary Tree
Pohon biner adalah struktur data hierarkis di mana setiap simpul memiliki paling banyak dua anak yang umumnya disebut anak kiri dan anak kanan.
Setiap node berisi tiga komponen:
Pointer ke subtree kiri
Pointer ke subtree kanan
Elemen data
Node paling atas di pohon disebut root. Pohon kosong diwakili oleh pointer NULL.
Jenis Pohon Biner
Pohon Biner Sempurna
Di mana, Setiap node yang saat ini ada di pohon biner ini, memiliki set lengkap dan kedalaman yang sama dalam hal jumlah anak mereka.
Pohon Biner Lengkap
Pohon biner lengkap adalah pohon biner di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node berada sejauh mungkin.
Pohon Biner miring
Pohon biner yang, setiap simpul memiliki paling banyak 1 simpul anak.
Pohon Biner Seimbang
Pohon biner seimbang adalah pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.
Tugas Pre-UTS "Dreamers Market"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
#include <conio.h>
#include <time.h>
struct node{
char name[31];
long price;
long quantity;
struct node *next, *prev;
}*head = NULL, *tail = NULL, *curr;
void List(){
printf("+==============================================================+\n");
printf("| Your Cart |\n");
if(head==NULL)
{
printf("+==============================================================+\n");
printf("| Empty |\n");
printf("+==============================================================+\n");
}
else
{
int Index = 0;
curr = head;
printf("+====+==============================+===============+==========+\n");
while(curr!=NULL)
{
Index++;
printf("| %-1d. | %-28s | Rp %3ld.000,00 | %-8ld |\n", Index, curr->name, curr->price, curr->quantity);
printf("+====+==============================+===============+==========+\n");
curr = curr->next;
}
}
}
void Out(){
long total = 0;
system("cls");
if(head == NULL){
printf("You don't buy anything, have a nice day!");
}
else
{
List();
curr = head;
while(curr)
{
total += (curr->price*curr->quantity);
curr= curr->next;
}
printf("Your grand total is : Rp %ld.000,00\n", total);
printf("But here is the catch, You don't have to pay for anything!\n");
printf("So your grandtotal is : Rp 0,00, Have a nice day!\n");
printf("KINDNESS IS FREE\n");
system("pause");
}
}
void Remove()
{
if(head == NULL)
{
system("cls");
printf("List Is Empty!\n");
system("pause");
return;
}
int isFound = 0;
char name[30];
long quantity;
do{
getchar();
system("cls");
List();
printf("Please Input Item Name To be : ");
scanf("%[^\n]",name);
curr=head;
while(curr!=NULL){
if(strcmp(name,curr->name)==0){
if (head== curr)head = curr->next;
if (curr->next != NULL)curr->next->prev = curr->prev;
if (curr->prev != NULL)curr->prev->next = curr->next;
free(curr);
return;
}
curr = curr->next;
}
system("cls");
printf("Item not found, pls try again!\n");
system("pause");
}while(isFound==0);
}
void Edit()
{
if(head == NULL)
{
system("cls");
printf("List Is Empty!\n");
system("pause");
return;
}
int isFound = 0;
char name[30];
long quantity;
do{
getchar();
system("cls");
List();
printf("Please Input Item Name To be Edited : ");
scanf("%[^\n]",name);
curr=head;
while(curr!=NULL){
if(strcmp(name,curr->name)==0){
printf("Please input new quantity : ");
scanf("%ld", &quantity);
curr->quantity = quantity;
return;
}
curr = curr->next;
}
system("cls");
printf("Item not found, pls try again!\n");
system("pause");
}while(isFound==0);
}
void Push(char name[], long quantity, long price)
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
strcpy(temp->name,name);
temp->quantity = quantity;
temp->price = price;
temp->next = NULL;
temp->prev = NULL;
if(head==NULL)
head = tail = temp;
else{
if(strcmp(temp->name,head->name)<=0)
{
temp->next = head;
head->prev = temp;
head = temp;
}
else if(strcmp(temp->name,tail->name)>=0)
{
temp->prev = tail;
tail->next = temp;
tail = temp;
}
else
{
curr = head;
while(strcmp(curr->name, temp->name) != 1 && curr->next!=NULL){
curr = curr->next;
}
temp->next = curr;
temp->prev = curr->prev;
temp->next->prev = temp;
temp->prev->next = temp;
}
}
head->prev=tail->next=NULL;
}
int menu(){
int choice;
// printf("\033[0;31m");
printf("Market Application\n");
printf("==================\n");
printf("1.Add Item To Cart\n");
printf("2.Edit Item in Cart\n");
printf("3.Remove Item From Cart\n");
printf("4.Exit From Program\n");
printf("[1-4]>>> ");
scanf("%d", &choice);
return choice;
}
int main()
{
srand(time(NULL));
int choice;
do{
system("cls");
List();
choice = menu();
switch(choice){
case 1:{
system("cls");
List();
char name[30];
long quantity;
long price;
getchar();
printf("Please Input Item Name : ");
scanf("%[^\n]", &name);
printf("Please Input Quantity : ");
scanf("%ld", &quantity);
price = 1+(rand()%100);
Push(name,quantity,price);
break;
}
case 2:{
Edit();
break;
}
case 3:{
Remove();
break;
}
case 4:{
Out();
break;
}
}
}while(choice != 4);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
char sandwich[100][100] = {
" // ",
" // ",
" _______________//__ ",
" .(______________//___).",
" | / |",
" |. . . . . . . / . . .|",
" \ . . . . . ./. . . . /",
" | / ___ | ",
" _.---._ |::......./../...\.:| ",
" _.-~ ~-._ |::::/::\::/:\::::::| ",
" _.-~ ~-._ |::::\::/::::::X:/::| ",
" _.-~ ~---.;:::::::/::\::/:::::| ",
" _.-~ ~\::::::n::::::::::| ",
" .-~ _.;::/::::a::::::::/ ",
" :-._ _.-~ ./::::::::d:::::::| ",
" `-._~-._ _..__.-~ _.-~|::/::::::::::::::| ",
" / ~-._~-._ / .__..--~----.YWWWWWWWWWWWWWWWP' ",
" \_____(_;-._\. _.-~_/ ~).. . \ ",
" /(_____ \`--...--~_.-~______..-+_______) ",
" .(_________/`--...--~/ _/ /\ ",
" /-._ \_ (___./_..-~__.....__..-~./ ",
" `-._~-._ ~\--------~ .-~_..__.-~ _.-~ ",
" ~-._~-._ ~---------' / .__..--~ ",
" ~-._\. _.-~_/ ",
" \`--...--~_.-~ ",
" `--...--~ "
};
struct stacknode{
char in[20];
struct stacknode *next;
}*top;
void pushhead(char insert[20]){
struct stacknode* newnode = (struct stacknode*) malloc(sizeof(struct stacknode));
strcpy(newnode->in,insert);
if(top == NULL)
{
top = newnode;
top->next = NULL;
}
else
{
newnode->next = top;
top = newnode;
}
}
void pophead(){
if(top == NULL)
printf("The Plate is Still Empty");
else
{
struct stacknode* newnode = (struct stacknode*) malloc(sizeof(struct stacknode));
newnode = top;
top = top->next;
free(newnode);
}
}
void printsandwich(){
if(top == NULL)
printf("The Plate is Still Empty");
else
{
struct stacknode* point = (struct stacknode*) malloc(sizeof(struct stacknode));
point = top;
while(point!=NULL)
{
printf("[%s]\n", point->in);
point=point->next;
}
printf("--------------------");
}
}
int main(){
int choice;
do{
system("cls");
char insert[20] = {0};
printf("Sandwich Stacker\n================\n");
printf("1. Add Topping\n");
printf("2. Remove Topping\n");
printf("3. View Sandwich\n");
printf("4. Exit Sandwich Program\n");
printf("[1,2,3,4]>> ");
scanf("%d", &choice);
Sleep(100);
switch(choice){
case 1:{
system("cls");
printf("Please Add a Topping to the Sandwich: ");
getchar();
scanf("%[^\n]", &insert);
getchar();
pushhead(insert);
break;
}
case 2:{
pophead();
break;
}
case 3:{
system("cls");
printsandwich();
printf("\n");
system("pause");
break;
}
}
}while(choice != 4);
system("cls");
for(int i = 0; i < 26; i++){
for(int j = 0; j < 63; j++){
printf("%c", sandwich[i][j]);
Sleep(1);
}
printf("\n");
}
}
Queue
Pada data struktur queue, kita dapat membayangkan suatu antrian pada dunia nyata, misalnya saja kalian sedang mengantri untuk membeli minuman Starbucks, Maka kalian akan mulai mengantri pada barisan yang paling belakang dari suatu antrian.Queue menggunakan konsep First In, First out (FIFO), Dimana, data yang masuk melalui arah satu akan eluar di arah lainnya.
Berikut adalah contoh coding saya pada data struktur Queue ini:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
char name[20];
struct node *next;
struct node *prev;
}*head,*curr,*tail;
void push(char input[20]){
curr=(struct node*)malloc(sizeof(struct node));
strcpy(curr->name,input);
if(head==NULL){
head=tail=curr;
head->prev=NULL;
}
else{
tail->next=curr;
curr->prev=tail;
tail=curr;
}
tail->next=NULL;
}
void pop(){
if(head==NULL){
printf("No queue to clear...\n");
printf("Press enter to continue (ENTER) \n");
getchar();
getchar();
}
else if(head->next==NULL){
free(head);
head=tail=NULL;
}
else{
curr=head;
head=head->next;
head->prev=NULL;
free(curr);
}
}
void printlist(){
curr=head;
printf(" ____ ______________________\n|No. | Queue List |\n|____|______________________|\n");
int t=0;
for(t=0;curr!=NULL;t++){
int len=strlen(curr->name);
printf("| %d. | %s ",t+1,curr->name);
for(int i=0;i<20-len;i++){
printf(" ");
}
printf("|\n");
curr=curr->next;
}
if(t==0)printf("| | No Queue |\n");
printf("|____|______________________|\n");
}
int main(){
int menu=0;
while(menu!=3){
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
printlist();
printf("Welcome to Sushi Tei Queu System, what do you want to do ?\n");
printf("1. Add Queue (Customer) 2. Seat is Ready for customer(Clear one queue) 3. Exit\n");
char input[20]={0};
scanf("%s",input);
while(strcmp(input,"1")!=0&&strcmp(input,"2")!=0&&strcmp(input,"3")!=0){
printf("Sorry, please input a number (1-3) : ");
scanf("%s",input);
}
menu=input[0]-48;
if(menu==1){
char add[20]={0};
printf("Input Customer name : ");
getchar();
scanf("%[^\n]",&add);
while(add[0]=='\0'){
printf("Input item name (Should be filled) :");
getchar();
scanf("%[^\n]",&add);
}
push(add);
}
if(menu==2){
pop();
}
}
printf("Thanks \n");
}
Hashing and Tree
Apa itu Hashing?Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci sementara secara cepat dan cepat. Hashing digunakan sebagai struktur data karena misalnya, jika Anda ingin menemukan jika ada string tertentu yang ada dalam array, kita bisa membuat kunci untuk menghubungkannya dengan sehingga lebih mudah dan lebih efisien untuk melakukan fungsi pencarian untuk itu. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Contoh hashing dalam implementasi kehidupan nyata adalah cryptocurrency.
Meja Hash
Tabel hash adalah struktur data yang terdiri dari tabel dan fungsi untuk memetakan nilai kunci unik untuk setiap baris dan menjadi jumlah lokasi rekaman dalam tabel. Keuntungan dari tabel hash adalah bahwa waktu untuk mengakses lebih cepat karena catatan yang dicari berada di nomor hash dari lokasi penyimpanan.
Kunci Hash
Kunci hash adalah pengidentifikasi yang digunakan untuk pemetaan.
Fungsi Hash
Fungsi Hash adalah Fungsi yang digunakan untuk memproses pemetaan yang mengambil kunci sebagai input, dan kemudian menggunakan input itu untuk menemukan indeks yang diinginkan. Ada banyak cara untuk hash kunci:
Metode Mid-Square
Metode Mid Square menggunakan Nilai ASCII dari string yang dimasukkan. String yang diurai ke int kemudian dikuadratkan. Dengan nilai yang dikuadratkan, kita memilih bit r tengah angka.
Metode Pembagian
Metode ini cukup sederhana, Kunci dalam bilangan bulat yang Anda masukkan dibagi menggunakan modulo, yang menghasilkan sisa divisi, digunakan dalam pengindeksan
Metode Lipat
Metode ini melibatkan pemotongan nomor yang dimasukkan menjadi beberapa bagian. Kemudian, bagian-bagian tersebut ditambahkan bersama-sama untuk menghasilkan kunci yang dapat digunakan untuk menemukan indeks data yang diinginkan.
Metode Ekstraksi Digit
Metode ekstraksi digit menggunakan angka tertentu sebagai kunci, kemudian digit diekstraksi
Contoh: dalam 236747 digit, digit pertama, ketiga dan kelima diekstraksi, maka kita bisa mendapatkan 264 sebagai kunci hash.
Metode Rotasi
Digit yang dimasukkan terbalik. Contoh: 23301 diputar ke 10332, maka itu digunakan sebagai kunci.
Tabrakan adalah suatu kondisi yang terjadi ketika beberapa data memiliki kunci yang sama. Ini masalah karena bisa mengacaukan urutan data yang ingin dimasukkan. Untuk itu, ada dua solusi yang bisa digunakan.
Probing Linier
Linear Probing menggunakan slot array kosong untuk mengisi data kunci hash serupa berikutnya.
Rantai
Metode rantai menggunakan Daftar Tertaut, di mana data kunci hash yang sama dihubungkan berikutnya.
Tree
Tree adalah struktur data non-linear yang mewakili hubungan antara satu node ke yang lain.
Tree Pohon
Node di atas disebut sebagai root.
Garis yang menghubungkan induk ke anak adalah edge.
Node yang tidak memiliki anak disebut daun.
Node yang memiliki orang tua yang sama disebut saudara.
Derajat simpul adalah total sub pohon simpul.
Tinggi / Kedalaman adalah tingkat maksimum node dalam pohon.
Jika ada garis yang menghubungkan p ke q, maka p disebut leluhur q, dan q adalah turunan dari p.
Binary Tree
Pohon biner adalah struktur data hierarkis di mana setiap simpul memiliki paling banyak dua anak yang umumnya disebut anak kiri dan anak kanan.
Setiap node berisi tiga komponen:
Pointer ke subtree kiri
Pointer ke subtree kanan
Elemen data
Node paling atas di pohon disebut root. Pohon kosong diwakili oleh pointer NULL.
Jenis Pohon Biner
Pohon Biner Sempurna
Di mana, Setiap node yang saat ini ada di pohon biner ini, memiliki set lengkap dan kedalaman yang sama dalam hal jumlah anak mereka.
Pohon Biner Lengkap
Pohon biner lengkap adalah pohon biner di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node berada sejauh mungkin.
Pohon Biner miring
Pohon biner yang, setiap simpul memiliki paling banyak 1 simpul anak.
Pohon Biner Seimbang
Pohon biner seimbang adalah pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.
The Binary Tree Search
Binary tree search adalah sebuah data struktur turunan dari Tree data struktur yang berfungsi sebagai penyimpan data secara berurut, dimana setiap node mempunyai anak anak dimana anak kiri dari node memiliki nilai yang lebih kecil dari nilai pada parent dan untuk node kanan, nilainya lebih besar dari node parent.
Berikut iniadalah codingan yang saya buat untuk BST ini:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int number;
struct node *leftChild, *rightChild;
};
int menu()
{
int choice;
printf("Binary Tree Search Program\n");
printf("==========================\n");
printf("1.Add Node\n");
printf("2.Print Node\n");
printf("3.Delete Node\n");
printf("4.Exit Program\n");
printf("==========================\n");
printf(">> ");
scanf("%d", &choice);
return choice;
}
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->number = item;
temp->leftChild = temp->rightChild = NULL;
return temp;
}
struct node* FindNode(struct node* root, int number)
{
if (root == NULL || root->number == number)
return root;
if (root->number < number)
return FindNode(root->rightChild, number);
return FindNode(root->leftChild, number);
}
struct node * FindLeastValue(struct node* node)
{
struct node* current = node;
while (current && current->leftChild != NULL)
current = current->leftChild;
return current;
}
struct node* RemoveNode(struct node* root, int number)
{
if (root == NULL) return root;
if (number < root->number)
root->leftChild = RemoveNode(root->leftChild, number);
else if (number > root->number)
root->rightChild = RemoveNode(root->rightChild, number);
else
{
if (root->leftChild == NULL)
{
struct node *temp = root->rightChild;
free(root);
return temp;
}
else if (root->rightChild == NULL)
{
struct node *temp = root->leftChild;
free(root);
return temp;
}
struct node* temp = FindLeastValue(root->rightChild);
root->number = temp->number;
root->rightChild = RemoveNode(root->rightChild, temp->number);
}
return root;
}
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->leftChild);
printf("%d \n", root->number);
inorder(root->rightChild);
}
}
struct node* AddNode(struct node* node, int number)
{
if (node == NULL) return newNode(number);
if (number < node->number)
node->leftChild = AddNode(node->leftChild, number);
else if (number > node->number)
node->rightChild = AddNode(node->rightChild, number);
return node;
}
int main()
{
int choice;
struct node *root = NULL;
do{
choice = menu();
switch(choice){
case 1:{
int input;
printf("Input Number To Be Added : ");
scanf("%d",&input);
root = AddNode(root,input);
break;
}
case 2:{
inorder(root);
break;
}
case 3:{
int input;
printf("Input Number To Be Deleted : ");
scanf("%d",&input);
root = RemoveNode(root,input);
break;
}
}
}while(choice != 4);
inorder(root);
return 0;
}
Berikut iniadalah codingan yang saya buat untuk BST ini:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int number;
struct node *leftChild, *rightChild;
};
int menu()
{
int choice;
printf("Binary Tree Search Program\n");
printf("==========================\n");
printf("1.Add Node\n");
printf("2.Print Node\n");
printf("3.Delete Node\n");
printf("4.Exit Program\n");
printf("==========================\n");
printf(">> ");
scanf("%d", &choice);
return choice;
}
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->number = item;
temp->leftChild = temp->rightChild = NULL;
return temp;
}
struct node* FindNode(struct node* root, int number)
{
if (root == NULL || root->number == number)
return root;
if (root->number < number)
return FindNode(root->rightChild, number);
return FindNode(root->leftChild, number);
}
struct node * FindLeastValue(struct node* node)
{
struct node* current = node;
while (current && current->leftChild != NULL)
current = current->leftChild;
return current;
}
struct node* RemoveNode(struct node* root, int number)
{
if (root == NULL) return root;
if (number < root->number)
root->leftChild = RemoveNode(root->leftChild, number);
else if (number > root->number)
root->rightChild = RemoveNode(root->rightChild, number);
else
{
if (root->leftChild == NULL)
{
struct node *temp = root->rightChild;
free(root);
return temp;
}
else if (root->rightChild == NULL)
{
struct node *temp = root->leftChild;
free(root);
return temp;
}
struct node* temp = FindLeastValue(root->rightChild);
root->number = temp->number;
root->rightChild = RemoveNode(root->rightChild, temp->number);
}
return root;
}
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->leftChild);
printf("%d \n", root->number);
inorder(root->rightChild);
}
}
struct node* AddNode(struct node* node, int number)
{
if (node == NULL) return newNode(number);
if (number < node->number)
node->leftChild = AddNode(node->leftChild, number);
else if (number > node->number)
node->rightChild = AddNode(node->rightChild, number);
return node;
}
int main()
{
int choice;
struct node *root = NULL;
do{
choice = menu();
switch(choice){
case 1:{
int input;
printf("Input Number To Be Added : ");
scanf("%d",&input);
root = AddNode(root,input);
break;
}
case 2:{
inorder(root);
break;
}
case 3:{
int input;
printf("Input Number To Be Deleted : ");
scanf("%d",&input);
root = RemoveNode(root,input);
break;
}
}
}while(choice != 4);
inorder(root);
return 0;
}
Tugas Pre-UTS "Dreamers Market"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
#include <conio.h>
#include <time.h>
struct node{
char name[31];
long price;
long quantity;
struct node *next, *prev;
}*head = NULL, *tail = NULL, *curr;
void List(){
printf("+==============================================================+\n");
printf("| Your Cart |\n");
if(head==NULL)
{
printf("+==============================================================+\n");
printf("| Empty |\n");
printf("+==============================================================+\n");
}
else
{
int Index = 0;
curr = head;
printf("+====+==============================+===============+==========+\n");
while(curr!=NULL)
{
Index++;
printf("| %-1d. | %-28s | Rp %3ld.000,00 | %-8ld |\n", Index, curr->name, curr->price, curr->quantity);
printf("+====+==============================+===============+==========+\n");
curr = curr->next;
}
}
}
void Out(){
long total = 0;
system("cls");
if(head == NULL){
printf("You don't buy anything, have a nice day!");
}
else
{
List();
curr = head;
while(curr)
{
total += (curr->price*curr->quantity);
curr= curr->next;
}
printf("Your grand total is : Rp %ld.000,00\n", total);
printf("But here is the catch, You don't have to pay for anything!\n");
printf("So your grandtotal is : Rp 0,00, Have a nice day!\n");
printf("KINDNESS IS FREE\n");
system("pause");
}
}
void Remove()
{
if(head == NULL)
{
system("cls");
printf("List Is Empty!\n");
system("pause");
return;
}
int isFound = 0;
char name[30];
long quantity;
do{
getchar();
system("cls");
List();
printf("Please Input Item Name To be : ");
scanf("%[^\n]",name);
curr=head;
while(curr!=NULL){
if(strcmp(name,curr->name)==0){
if (head== curr)head = curr->next;
if (curr->next != NULL)curr->next->prev = curr->prev;
if (curr->prev != NULL)curr->prev->next = curr->next;
free(curr);
return;
}
curr = curr->next;
}
system("cls");
printf("Item not found, pls try again!\n");
system("pause");
}while(isFound==0);
}
void Edit()
{
if(head == NULL)
{
system("cls");
printf("List Is Empty!\n");
system("pause");
return;
}
int isFound = 0;
char name[30];
long quantity;
do{
getchar();
system("cls");
List();
printf("Please Input Item Name To be Edited : ");
scanf("%[^\n]",name);
curr=head;
while(curr!=NULL){
if(strcmp(name,curr->name)==0){
printf("Please input new quantity : ");
scanf("%ld", &quantity);
curr->quantity = quantity;
return;
}
curr = curr->next;
}
system("cls");
printf("Item not found, pls try again!\n");
system("pause");
}while(isFound==0);
}
void Push(char name[], long quantity, long price)
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
strcpy(temp->name,name);
temp->quantity = quantity;
temp->price = price;
temp->next = NULL;
temp->prev = NULL;
if(head==NULL)
head = tail = temp;
else{
if(strcmp(temp->name,head->name)<=0)
{
temp->next = head;
head->prev = temp;
head = temp;
}
else if(strcmp(temp->name,tail->name)>=0)
{
temp->prev = tail;
tail->next = temp;
tail = temp;
}
else
{
curr = head;
while(strcmp(curr->name, temp->name) != 1 && curr->next!=NULL){
curr = curr->next;
}
temp->next = curr;
temp->prev = curr->prev;
temp->next->prev = temp;
temp->prev->next = temp;
}
}
head->prev=tail->next=NULL;
}
int menu(){
int choice;
// printf("\033[0;31m");
printf("Market Application\n");
printf("==================\n");
printf("1.Add Item To Cart\n");
printf("2.Edit Item in Cart\n");
printf("3.Remove Item From Cart\n");
printf("4.Exit From Program\n");
printf("[1-4]>>> ");
scanf("%d", &choice);
return choice;
}
int main()
{
srand(time(NULL));
int choice;
do{
system("cls");
List();
choice = menu();
switch(choice){
case 1:{
system("cls");
List();
char name[30];
long quantity;
long price;
getchar();
printf("Please Input Item Name : ");
scanf("%[^\n]", &name);
printf("Please Input Quantity : ");
scanf("%ld", &quantity);
price = 1+(rand()%100);
Push(name,quantity,price);
break;
}
case 2:{
Edit();
break;
}
case 3:{
Remove();
break;
}
case 4:{
Out();
break;
}
}
}while(choice != 4);
return 0;
}
Komentar
Posting Komentar