Rangkuman Linked List,Hash,Binary,BST
Linked list merupakan Merupakan
suatu struktur data pengembangan dari konsep ADT (Abstrak Data Type) yang
bersifat dinamis. Linked List dapat dimanfaatkan secara effektif sesuai dengan
keperluan. Linked List juga dapat benar – benar dihapus / dibersihkan dari memory.Linked
List sebenarnya merupakan suatu typedata tersendiri.
Linked list minimal mempunyai 2 element itu adalah data dan
pointer untuk menunjukkan ke list berikutnya.
Doubly Linked list : Linked list dengan menggunakan pointer, dimana setiap
node memiliki 3 field, yaitu: 1 field pointer yang menunjuk ke pointer
berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya dan field yang
berisi data dari node tersebut. Pointer next dan prev-nya menunjuk ke null.
Circular
doubly Linked List merupakan
Doubly Linked List yang pointer next dan prev-nya menunjuk ke dirinya sendiri
secara circular.
Circular Single Linked List merupakan Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.
1.Push depan artinya kita menambahkan sebuah data pada bagian
depan atau samping kiri program.
Void pushDepan(int y){
curr
=(struct data*)malloc(sizeof(structdata));
curr->x=y;
if(head==NULL){
head=tail=curr;
}else{
curr->next=head;
head=curr;
}
tail->next=NULL;
}
2.Push Belakang artinya kita menambahkan sebuah data pada
bagian belakang atau samping kanan program.
Void pushBelakang(int y){
curr
=(struct data*)malloc(sizeof(structdata));
curr->x=y;
if(head==NULL){
head=tail=curr;
}else{
tail->next=curr;
tail=curr;
}
tail->next=NULL;
}
4.Pop Depan artinya kita menghaps atau delete sebuah data pada
bagian depan atau sebelah kiri.
Void popDepan(){
if(head!=NULL){
//node sisa 1
if(head==tail){
free(head);
head=NULL;
}else{
curr=head;
head=head->next;
free(curr);
}
}
}
5.Pop Belakang artinya kita meghapus atau delete sebuah data pada
bagian belakang atau sebelah kanan.
Void popBelakang(){
if(head!=NULL){
//node sisa 1
if(head==tail){
free(head);
head=NULL;
}else{
curr=head;
while(curr->next!=tail){
curr=curr->next;
}
free(tail);
tail=curr;
tail->next=NULL;
}
}
}
Hashing adalah mengubah
suatu string menjadi suatu bilangan dengan suatu fungsi. Misalkan kita
memiliki string "abca", dan fungsi f yang memetakan string ke
bilangan bulat berikut:
f(S) = (
(banyaknya 'a')*1 +
(banyaknya 'b')*2 +
(banyaknya 'c')*3 +
... +
(banyaknya 'z')*26
) mod 1000000
Artinya:
f("abca") = (2*1 + 1*2 + 1*3 + 0*4 + 0*5 + ... + 0*26) mod
1000000
= 7
Kita berhasil mengubah string "abca" menjadi sebuah angka, yaitu 7. Hal ini juga akan dilakukan untuk setiap nama mahasiswa dalam setiap operasi; sebelumnya di-hash terlebih dahulu. Dengan demikian, direct addressing table dapat kembali digunakan! Kini kompleksitas untuk setiap operasi adalah O(K), dengan K adalah kompleksitas menghitung nilai hash melalui fungsi hashing. Untuk contoh di atas, K = panjang string. Jika panjang setiap string cukup kecil, setiap operasi bisa dianggap O(1).
- Hashing
Dapat diartikan sebagai aktivitas untuk mengubah suatu objek menjadi
serangkaian angka/karakter/sejenisnya. Seperti contoh kita
melakukan hash pada string menjadi bilangan.
T["stefanus"] = 3;
printf("%d\n", T["stefanus"]);
Collision
dapat menggunakan teknik :
- Closed
hashing
Contoh
teknik yang digunakan adalah linear/quadratic probing. Saya tidak
menjelaskan bagian ini karena menurut saya kurang cocok digunakan saat
kompetisi.
- Open
hashing
Idenya
sederhana. Kita dapat mengganti array pada direct addressing
table menjadi "array of linked list". Misalnya "array of
linked list" ini bernama T. Setiap elemen pada linked list T[i]
menyimpan sejumlah pasangan key dan value untuk memiliki
nilai hash key berupa i.
Ketika kita hendak menyimpan suatu nilai ke T[i] dan terjadi collision (sudah ada isinya), kita cukup tambahkan elemen baru pada T[i].
Ketika kita hendak menyimpan suatu nilai ke T[i] dan terjadi collision (sudah ada isinya), kita cukup tambahkan elemen baru pada T[i].
Binary Tree adalah struktur data non-linear yang mewakili hubungan hierarkis di
antara objek data. Beberapa hubungan pohon dapat diamati dalam struktur
direktori atau hierarki organisasi.
- 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.
- Tree expression prefix :
char s[MAXN];
int T = 0;
void f(struct tnode *curr) {
if
( is_operator(s[T]) ) {
T++; curr->left = newnode(s[T]);
f(curr->left);
T++; curr->right = newnode(s[T]);
f(curr->right);
}
}
}
- Tree expression
postfix transversal :
void postfix(struct tnode *curr) {
if
( curr->left != 0 ) postfix(curr->left);
if
( curr->right != 0 ) postfix(curr->right);
printf( “%c“, curr->chr );
printf( “%c“, curr->chr );
}
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.
Binary Search Tree memiliki beberapa operasi misalnya :
- Searching : Pencarian
dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive
maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan
melakukan identifikasi root node. Bila root node null maka key yang dicari
tidak ada. Sebaliknya bila root tersebut exist, maka langkah selanjutnya ialah
membandingkan nilai key dengan node root tersebut. Bila nilai root node sama
seperti key yang dicari, maka nilai root node tersebut akan dikembalikan
sebagai hasil. Bila nilai key lebih kecil dari node, maka pencarian diarahkan
ke subtree di sisi kiri dari node, proses ini dilakukan terus berulang hingga
key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah
selanjutnya ialah memilih subtree di sisi kanan node tersebut. Dalam kasus
terburuk, pencarian ini akan mencapai ujung subtree terjauh dari root, atau
setara dengan tinggi dari tree tersebut.
- Insertion Proses
insertion (memasukkan suatu data) dilakukan mulai secara bersamaan dengan
proses pencarian data. Bila key tidak sesuai dengan nilai yang ada di root,
pencarian dilakukan ke subtree kanan atau kiri. Hingga berada pada node luar,
untuk kemudian dilakukan penambahan data key baru. Dengan kata lain dilakukan
proses pemeriksaan root dan secara recursive memasukkan suatu node baru di sisi
kiri bila nilainya lebih kecil, atau di sisi kanan bila nilainya lebih besar
(atau bisa juga sama besar) dibandingkan dengan nilai dari root tersebut.
Deletion : Terdapat beberapa aturan dasar yang perlu diperhatikan
dalam langkah menghapus suatu node, yakni.
1. Bila node tersebut tidak memiliki child, node tersebut dapat langsung
dihapus
2. Bila node tersebut memiliki child, maka node (parent) tersebut dihapus
dan child dari node tersebut menggantikan posisi dari node parent
3.Bila node tersebut memiliki dua children, maka langkah pertama yang
dilakukan ialah mengganti nilai node parent dengan salah satu child, hapus
nilai node parent awal, secara recursive hapus nilai node child yang telah
digunakan untuk mengganti nilai node parent sebelumnya, kemudian lakukan
seperti pada kasus pertama atau kedua
Minimarket Coding :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
struct item{
char name [101];
int quantity;
struct item*next;
struct item*prev;
}*head=NULL,*tail,*curr;
void add(char name2[],int quantity2){
struct item* curr = (struct item*) malloc(sizeof(struct item));
curr -> quantity = quantity2;
strcpy (curr -> name, name2);
curr -> next = NULL;
curr -> prev = NULL;
if (head == NULL){
head = tail = curr;
}
else if (strcmp (name2, head -> name) <= 0){
curr -> next = head;
head -> prev = curr;
head = curr;
}
else if (strcmp (name2, tail -> name) >= 0){
curr -> prev= tail;
tail -> next = curr;
tail = curr;
}
else {
struct item*temp = (struct item*) malloc(sizeof(struct item));
temp = head;
do{
temp = temp -> next;
}while (temp != NULL && strcmp (temp -> name,name2) <= 0);
temp -> prev -> next = curr;
curr-> prev = temp -> prev;
curr -> next = temp;
temp -> prev = curr;
}
}
void Title(){
printf("--------------------------------------------------\n");
printf("||Minimarket Wadidaw Stefanus Putranto Wawawaw||\n");
printf("--------------------------------------------------\n");
}
void Input(struct item *temp){
long long int price;
if(temp!=NULL){
for(int i=0; ; i++){
printf("|| %11d || %27s || %11d || Kindness is Free ||\n",i+1,temp->name,temp->quantity);
printf("===================================================================================\n");
puts(" ");
printf("Thanks for Shopping in ||Minimarket Wadidaw Stefanus Putranto Wawawaw||");
puts(" ");
temp=temp->next;
}
}
}
void display(){
struct item *temp =head;
if(head == NULL){
printf("No Data Please Input first\n");
}else{
printf("===================================================================================\n");
printf("|| %11s || %27s || %10s || %17s ||\n","No","Name Item","Quantity","Price");
printf("===================================================================================\n");
Input(temp);
}
}
void Delete(){
char deletename[101];
int quantity;
printf("Input Product Name to Delete: ");
scanf("%s",&deletename);
struct item*temp=head;
while (temp) {
if (strcmp(temp -> name, deletename) == 0) {
quantity = 1;
break;
}
temp = temp -> next;
}
if (quantity == 1){
//kondisi dihapus adalah data satu-satunya di list
if(temp == head && head == tail) {
head = tail = NULL;
free(temp);
}
//kondisi dihapus adalah head
else if(temp == head) {
head = head->next;
head->prev = NULL;
free(temp);
}//kondisi dihapus adalah tail
else if(temp == tail) {
tail = tail->prev;
tail->next = NULL;
free(temp);
}
//kondisi dihapus ditengah
else {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
printf("======================\n");
printf("Item has been deleted\n");
printf("======================\n");
puts(" ");
}
}
void freedata() {
struct item* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
head = tail = NULL;
}
int main (){
int ch;
while (ch !=5 ){
Title();
printf ("1. Add Item\n");
printf ("2. Display Item List\n");
printf ("3. Delete Item\n");
printf ("4. Change Quantity\n");
printf ("5. Exit\n");
printf ("Please choose: ");
scanf ("%d", &ch);
system ("cls");
if (ch == 1) {
char Itemname[101];
int Itemquantity;
item price;
printf ("Input Item name: ");
scanf ("%s",&Itemname);
printf ("Input quantity: ");
scanf ("%d", &Itemquantity);
add(Itemname, Itemquantity);
system ("cls");
}
else if (ch == 2){
display();
}
else if (ch == 3) {
printf("======================\n");
printf("Input Name Corectly!!\n");
printf("======================\n");
Delete();
}
else if (ch == 4) {
char delname[101];
int count;
printf ("Input Name Item: ");
scanf ("%s", delname);
struct item* temp = head;
while (temp) {
if (strcmp(temp -> name, delname) == 0) {
count = 1;
break;
}
temp = temp -> next;
}
if (count == 1) {
printf("Edit quantity of \"%s\" : ", temp -> name);
scanf("%d", &temp -> quantity);
} else {
printf("Please Input Item Corectly\n");
}
system ("cls");
}
}
freedata();
return 0;
}
Minimarket Coding :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
struct item{
char name [101];
int quantity;
struct item*next;
struct item*prev;
}*head=NULL,*tail,*curr;
void add(char name2[],int quantity2){
struct item* curr = (struct item*) malloc(sizeof(struct item));
curr -> quantity = quantity2;
strcpy (curr -> name, name2);
curr -> next = NULL;
curr -> prev = NULL;
if (head == NULL){
head = tail = curr;
}
else if (strcmp (name2, head -> name) <= 0){
curr -> next = head;
head -> prev = curr;
head = curr;
}
else if (strcmp (name2, tail -> name) >= 0){
curr -> prev= tail;
tail -> next = curr;
tail = curr;
}
else {
struct item*temp = (struct item*) malloc(sizeof(struct item));
temp = head;
do{
temp = temp -> next;
}while (temp != NULL && strcmp (temp -> name,name2) <= 0);
temp -> prev -> next = curr;
curr-> prev = temp -> prev;
curr -> next = temp;
temp -> prev = curr;
}
}
void Title(){
printf("--------------------------------------------------\n");
printf("||Minimarket Wadidaw Stefanus Putranto Wawawaw||\n");
printf("--------------------------------------------------\n");
}
void Input(struct item *temp){
long long int price;
if(temp!=NULL){
for(int i=0; ; i++){
printf("|| %11d || %27s || %11d || Kindness is Free ||\n",i+1,temp->name,temp->quantity);
printf("===================================================================================\n");
puts(" ");
printf("Thanks for Shopping in ||Minimarket Wadidaw Stefanus Putranto Wawawaw||");
puts(" ");
temp=temp->next;
}
}
}
void display(){
struct item *temp =head;
if(head == NULL){
printf("No Data Please Input first\n");
}else{
printf("===================================================================================\n");
printf("|| %11s || %27s || %10s || %17s ||\n","No","Name Item","Quantity","Price");
printf("===================================================================================\n");
Input(temp);
}
}
void Delete(){
char deletename[101];
int quantity;
printf("Input Product Name to Delete: ");
scanf("%s",&deletename);
struct item*temp=head;
while (temp) {
if (strcmp(temp -> name, deletename) == 0) {
quantity = 1;
break;
}
temp = temp -> next;
}
if (quantity == 1){
//kondisi dihapus adalah data satu-satunya di list
if(temp == head && head == tail) {
head = tail = NULL;
free(temp);
}
//kondisi dihapus adalah head
else if(temp == head) {
head = head->next;
head->prev = NULL;
free(temp);
}//kondisi dihapus adalah tail
else if(temp == tail) {
tail = tail->prev;
tail->next = NULL;
free(temp);
}
//kondisi dihapus ditengah
else {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
printf("======================\n");
printf("Item has been deleted\n");
printf("======================\n");
puts(" ");
}
}
void freedata() {
struct item* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
head = tail = NULL;
}
int main (){
int ch;
while (ch !=5 ){
Title();
printf ("1. Add Item\n");
printf ("2. Display Item List\n");
printf ("3. Delete Item\n");
printf ("4. Change Quantity\n");
printf ("5. Exit\n");
printf ("Please choose: ");
scanf ("%d", &ch);
system ("cls");
if (ch == 1) {
char Itemname[101];
int Itemquantity;
item price;
printf ("Input Item name: ");
scanf ("%s",&Itemname);
printf ("Input quantity: ");
scanf ("%d", &Itemquantity);
add(Itemname, Itemquantity);
system ("cls");
}
else if (ch == 2){
display();
}
else if (ch == 3) {
printf("======================\n");
printf("Input Name Corectly!!\n");
printf("======================\n");
Delete();
}
else if (ch == 4) {
char delname[101];
int count;
printf ("Input Name Item: ");
scanf ("%s", delname);
struct item* temp = head;
while (temp) {
if (strcmp(temp -> name, delname) == 0) {
count = 1;
break;
}
temp = temp -> next;
}
if (count == 1) {
printf("Edit quantity of \"%s\" : ", temp -> name);
scanf("%d", &temp -> quantity);
} else {
printf("Please Input Item Corectly\n");
}
system ("cls");
}
}
freedata();
return 0;
}
Comments
Post a Comment