Linked
List:
Hampir
sama seperti arrays, linked list merupakan data struktur bersifat linear. Tapi
bedanya linked list menggunakan pointer. Dalam arti linked list terdiri dari
zona/nodes yang mempunyai data dan referensi
|
No.
|
Linked List
|
Array
|
|
1.
|
Setiap elemen linked list terdiri dari 2 bagian, data dan
pointer address.
|
Setiap elemen array hanya berisi data saja.
|
|
2.
|
Pengalokasian ruang memori dilakukan tanpa pendeklarasian
sebelumnya dan terbatas pada jumlah ruang memori yang tersisa (dapat
dipakai).
|
Pengalokasian ruang memori terbatas pada jumlah ruang yang
dideklarasikan sebelumnya.
|
Ada
3 macam linked list: Circular Singly, Circular Doubly dan Doubly Linked List
·
Circular
single ini berulang dari node akhir ke node pertama, dan tidak ada nilai NULL
dalam list ini
·
Circular
Doubly Linked List sama seperti singly tapi ada 2 referensi
·
Doubly
Linked list merupakan linked list 2 arah dimana node satu memegang referensi ke
node 2 dan sebaliknya juga
Untuk membuat linked list butuh pakai data struct
struct basket{
char
Name[109];
int quant;
int price;
basket
*next,*prev;
} *head, *tail, *curr; ->merupakan linked list kita yang harus
di declare
Hashing
adalah bentuk data struktur yang menggunakan Hash Function yang digunakan untuk
memetakan sebuah value dengan kunci tertentu supaya dapat di akses lebih cepat.
Dalam
arti Hashing adalah cara untuk menrubah nilai kunci menjadi range index di
array. Hashing juga merupakan cara untuk melakukan program search lebih efektif
dibandingkan binary search dan linear search
Hash
function adalah proses yang merubah kunci dan memetakannya menjadi
panjang tertentu menjadi hash value, maka menjadi hash key.
Hash
value adalah versi kecil pada string karakter awal. Dengan digital signature
dan hash value dikirim ke receiver. Receiver lalu menggunakan hash function
yang sama dan dibanding dengan pesan yant tadi. Jika hash valuesnya sama maka
akan menampilkan error.
Ini contoh dari geeksforgeeks.com menggunakan chaining
// CPP program to implement hashing with chaining
#include<bits/stdc++.h>
using
namespace
std;
class
Hash
{
int BUCKET;
// No. of buckets
// Pointer to an array containing
buckets
list<int> *table;
public:
Hash(int V);
// Constructor
// inserts a key into hash table
void insertItem(int x);
// deletes a key from hash table
void deleteItem(int key);
// hash function to map values to
key
int hashFunction(int x) {
return (x %
BUCKET);
}
void displayHash();
};
Hash::Hash(int b)
{
this->BUCKET = b;
table = new list<int>[BUCKET];
}
void
Hash::insertItem(int key)
{
int index =
hashFunction(key);
table[index].push_back(key);
}
void
Hash::deleteItem(int key)
{
// get the hash index of key
int index = hashFunction(key);
// find the key in (inex)th list
list <int> :: iterator i;
for (i = table[index].begin();
i
!= table[index].end(); i++) {
if (*i ==
key)
break;
}
// if key is found in hash table, remove it
if (i != table[index].end())
table[index].erase(i);
}
// function to display hash table
void
Hash::displayHash() {
for (int i = 0; i
< BUCKET; i++) {
cout << i;
for (auto x :
table[i])
cout << "
--> "
<< x;
cout << endl;
}
}
// Driver program
int
main()
{
// array that contains keys to be mapped
int a[] = {15, 11, 27, 8, 12};
int n = sizeof(a)/sizeof(a[0]);
// insert the keys into the hash table
Hash h(7); // 7 is count of buckets
in
//
hash table
for (int i = 0; i
< n; i++)
h.insertItem(a[i]);
// delete 12 from hash table
h.deleteItem(12);
// display the Hash table
h.displayHash();
return 0;
}
Tree merupakan salah Satu bentuk Struktur Data tidak linier Yang
menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara
elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan
Satu elemen khusus. Yang disebut root Dan Node lainnya terbagi menjadi
Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut
subtree).
Istilah-istilah umum dalam tree.
·
Parent : predecssor satu level di atas suatu
node.
·
Child : successor satu level di bawah suatu
node.
·
Sibling : node-node yang memiliki parent yang
sama dengan suatu node.
·
Subtree : bagian dari tree yang berupa suatu
node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
·
Size : banyaknya node dalam suatu tree.
·
Height : banyaknya tingkatan/level dalam suatu
tree.
·
Root : satu-satunya node khusus dalam tree
yang tak punya predecssor.
·
Leaf : node-node dalam tree yang tak memiliki
seccessor.
·
Degree : banyaknya child yang dimiliki suatu
node.
Pohon biner atau Binary Tree adalah
pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree
dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut,
maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua
anak/child.
Berikut adalah contoh kode Tree yang aku temukan di Internet
//header file
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
//pendeklarasian
struct sebuah tree awal
struct Node{
int data;
Node *kiri;
Node *kanan;
};
//fungsi untuk
menambahkan node baru
void tambah(Node **root, int databaru)
{
//jika root masih kosong
if((*root) == NULL)
{
//pembuatan node baru
Node *baru;
//pengalokasian memori dari node yang telah
dibuat
baru = new Node;
//inisialisasi awal node yang baru dibuat
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
printf("Data
bertambah!");
}
//jika data yang akan dimasukkan lebih kecil
daripada elemen root, maka akan diletakkan di node sebelah kiri.
else if(databaru<(*root)->data)
tambah(&(*root)->kiri, databaru);
//jika data yang akan dimasukkan lebih besar
daripada elemen root, maka akan diletakkan di node sebelah kanan
else if(databaru>(*root)->data)
tambah(&(*root)->kanan, databaru);
//jika saat dicek data yang akan dimasukkan
memiliki nilai yang sama dengan data pada root
else if(databaru == (*root)->data)
printf("Data
sudah ada!");
}
//fungsi yang
digunakan untuk mencetak tree secara preOrder
void preOrder(Node *root)
{
if(root != NULL){
printf("%d
", root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
//fungsi yang
digunakan untuk mencetak tree secara inOrder
void inOrder(Node *root)
{
if(root != NULL){
inOrder(root->kiri);
printf("%d
", root->data);
inOrder(root->kanan);
}
}
//fungsi yang
digunakan untuk mencetak tree secara postOrder
void postOrder(Node *root)
{
if(root != NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf("%d
", root->data);
}
}
//fungsi utama
int main()
{
//deklarasikan variabel
int pil, data;// c;
Node *pohon; //*t;
pohon = NULL; //inisialisasi node pohon
//perulangan do-while
do
{
system("cls"); //bersihkan layar
printf("\t#PROGRAM
TREE C++#");
printf("\n\t==================");
printf("\nMENU");
printf("\n----\n");
printf("1.
Tambah\n");
printf("2. Lihat
pre-order\n");
printf("3. Lihat
in-order\n");
printf("4. Lihat
post-order\n");
printf("5.
Exit\n");
printf("Pilihan
: ");
scanf("%d", &pil);
switch(pil)
{
//jika pil bernilai 1
case 1 :
printf("\nINPUT
: ");
printf("\n-------");
printf("\nData
baru : ");
scanf("%d", &data);
//panggil fungsi untuk menambah node yang berisi
data pada tree
tambah(&pohon, data);
break;
//jika pil bernilai 2
case 2 :
printf("\nOUTPUT
PRE ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara
preOrder
preOrder(pohon);
else
printf("Masih
kosong!");
break;
//jika pil bernilai 3
case 3 :
printf("\nOUTPUT
IN ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara
inOrder
inOrder(pohon);
else
printf("Masih
kosong!");
break;
//jika pil bernilai 4
case 4 :
printf("\nOUTPUT
POST ORDER : ");
printf("\n------------------\n");
if(pohon!=NULL)
//panggil fungsi untuk mencetak data secara
postOrder
postOrder(pohon);
else
printf("Masih
kosong!");
break;
}
_getch();
}while(pil != 5); //akan diulang jika input tidak samadengan 5
return EXIT_FAILURE;
}
