Review DatStruct

Linked List

Circular Linked List

• Pengertian dari Circular Linked List adalah suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama) sehingga membentuk sebuah sirkuit. Jadi tidak ada pointer yang menunjuk NULL.

1. Circular Single Linked List: 

• Adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Circular Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.Pengertian:Single : artinya field pointer-nya hanya satu buah saja dan satu arah.Linked List : artinya node-node tersebut saling terhubung satu sama lain.Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

• Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar.

• Deklarasi node dibuat dari struct berikut ini:typedef struct TNode{int data;TNode *next;};

• Pembentukan node baruDigunakan keyword new yang berarti mempersiapkan sebuah node baruberserta alokasi memorinya.TNode *baru;baru = new TNode;baru->data = databaru;baru->next = baru;

    2.  Circular Double Linked List:

• Circular Double Linked List adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut.Double Linked List Circular pointer next dan prev nya menunjuk ke dirinya sendiri secara circular.Pengertian:Double: artinya field pointer-nya terdiri dari dua buah dan dua arah, yaitu prev dan nextLinked List: artinya node-node tersebut saling terhubung satu sama lain.Circular: artinya pointer next dan prev-nya menunjuk ke dirinya sendiri

• Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnyaUntuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke dirinya sendiri.Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.

• Deklarasi nodeDibuat dari struct berikut ini:typedef struct TNode{int data;TNode *next;Tnode *prev;};

• Pembentukan node baruDigunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya.TNode *baru;baru = new TNode;baru->data = databaru;baru->next = baru;baru->prev = baru;

• Doubly 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. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.
• Insert: Insert First, Insert Last, Insert After / Before
• Delete: Delete First, Delete Last, Delete Node

Stack & Queue

A. STACK DENGAN SINGLE LINKED LIST

Stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.

Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.

Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.

Operasi-operasi untuk Stack dengan Linked List

• IsEmpty

Fungsi memeriksa apakah stack yang adamasih kosong.

• Push

Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.

• Pop

Fungsi ini mengeluarkan elemen teratas dari stack.

• Clear

Fungsi ini akan menghapus stack yang ada.

B. QUEUE DENGAN DOUBLE LINKED LIST

Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.

Operasi-operasi Queue dengan Double Linked List

• IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.

• IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.

• EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).

• DeQueue

Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

Hashing & Hash Table

1. Hashing

Dapat diartikan sebagai aktivitas untuk mengubah suatu objek menjadi serangkaian angka/karakter/sejenisnya. Pada contoh sebelumnya, kita melakukan hash pada string menjadi bilangan.

Anda mungkin menyadari bahwa tabel T pada contoh sebelumnya bekerja seperti array. Kita seakan-akan dapat melakukan operasi:

T["gozali"] = 3;
printf("%d\n", T["gozali"]);

Pada ilmu komputer, tabel seperti ini disebut sebagai hash table. Struktur data ini erat kaitannya dengan konsep "key value". Key adalah hal yang menjadi indeks, dan value adalah nilai yang berasosiasi dengannya. Pada contoh permasalahan sebelumnya, nama mahasiswa merupakan key, dan IPK merupakan value.

Fungsi Hashing

Pada bagian sebelumnya, saya memberi contoh fungsi hashing sederhana. Sebenarnya fungsi hashing itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi hashing memiliki kriteria sebagai berikut:

1. Untuk dua buah key yang sama, hasil hashing-nya selalu sama.
2. Memiliki kompleksitas rendah.
3. Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

Hash Function

• Mid-square

• Division (most common)

• Folding

• Digit Extraction

• Rotating Hash

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

 Operasi Pada Hash Tabel

Ø  insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

Ø  find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

Ø  remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

Ø  getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Collision (Tabrakan)

Keterbatasan tabel hash menyebabkan ada dua angka yang jika dimasukkan ke dalam fungsi hash maka menghasilkan nilai yang sama. Hal ini disebut dengan collision.

contoh: Kita ingin memasukkan angka 6 dan 29.

             Hash(6) = 6 % 23 = 6

             Hash(29)= 29 % 23 = 6

Pertama-tama anggap tabel masih kosong. Pada saat angka 6 masuk akan ditempatkan pada posisi indeks 6, angka kedua 29 seharusnya ditempatkan di indeks 6 juga, namun karena indeks ke-6 sudah ditempati maka 29 tidak bisa ditempatkan di situ, di sinilah terjadi collision. Cara penanganannya bermacam-macam :

Collision Resolution Open Addressing

1.      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. Contoh deklarasi program:

struct { ... } node;

node Table[M]; int Free;

/* insert K */

addr = Hash(K);

if (IsEmpty(addr)) Insert(K,addr);

else {

/* see if already stored */

test:

if (Table[addr].key == K) return;

else {

addr = Table[addr].link; goto test;}

/* find free cell */

Free = addr;

do { Free--; if (Free<0) Free=M-1; }

while (!IsEmpty(Free) && Free!=addr)

if (!IsEmpty(Free)) abort;

else {

Insert(K,Free); Table[addr].link = Free;}

}

2.      Quadratic Probing

Penanganannya hampir sama dengan metode linear, hanya lompatannya tidak satu-satu, tetapi quadratic ( 12, 22, 32, 42, … )

3.      Double Hashing

Pada saat terjadi collision, terdapat fungsi hash yang kedua untuk menentukan posisinya kembali.

Collision Resolution Chaining

Ø  Tambahkan key and entry di manapun dalam list (lebih mudah dari depan)

Ø  Kerugian:

-          Overhead pada memory tinggi jika jumlah entry sedikit

Ø  Keunggulan dibandingkan open addressing:

-          Proses insert dan remove lebih sederhana

-          Ukuran Array bukan batasan (tetapi harus tetap meminimalisir collision: buat ukuran tabel sesuai dengan jumlah key dan entry yang diharapkan)

Pengertian Tree

Tree merupakan salah satu bentuk struktur data tidak linear 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. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.

Binary Tree

·         Pengertian Binary Tree

           Binary Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkanhubungan 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 ( disebut subtree).

            Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah binary tree.

       Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.

Istilah pada pohon Binar

a.      Pohon Biner Penuh   (Full Binary Tree)

Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama.

b.      Pohon Biner Lengkap (Complete Binary Tree)

 Hampir sama dengan Pohon BinerPenuh, semua simpul (kecualidaun) memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda.

c.       Pohon Biner Similer

 Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda.

d.      Pohon Biner Ekivalent

 Dua pohon yang memiliki struktur dan informasi yangsama.

e.       Pohon Biner Miring (Skewed Tree)

 Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun.

·         Kunjungan pada pohon Biner

Kunjungan pohon biner terbagi menjadi  3 bentuk binary tree :

1.      Kunjungan secara preorder ( Depth First Order), mempunyai urutan :

a.       Cetak isi simpul yang dikunjungi ( simpul akar ),

b.      Kunjungi cabang kiri,

c.       Kunjungi cabang kanan .

2.      Kunjungan secara inorder ( symetric order), mempunyai urutan :
a.     Kunjungi cabang kiri,

b.    Cetak isi simpul yang dikunjungi (simpul akar),

c.     Kunjungi  cabang kanan .

 

3.      Kunjungan secara postorder, mempunyai urutan :
a.    Kunjungi cabang kiri,

b.    Kunjungi cabang kanan,

c.     Cetak isi simpul yang dikunjungi ( simpul akar ).

·         Aplikasi pohon Biner

Notasi Prefix, Infix dan Postfix

Pada bagian ini akan dibahas tentang bagaimana menyusun sebuah Pohon Binar yang apabila dikunjungi secara PreOrder akan menghasilkan Notasi Prefix,kunjungan secara InOrder menghasilkan Notasi Infix, dankunjungan PostOrder menghasilkan Notasi Postfix.

Program Minimarket:

// Cathleen / 2301867910 / CB-01

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#include<string.h>

char nama[105];

int stok;

unsigned long long int harga;

struct produk{

char nama[105];

int stok;

unsigned long long int harga;

struct produk *prev;

struct produk *next;

} *head = NULL, *tail = NULL, *curr;

void menu(){

printf("April Market\n");

printf("1. Tambahkan produk\n");

printf("2. Mengedit stok produk\n");

printf("3. Hapus produk\n");

printf("4. Melihat data produk\n");

printf("5. Checkout\n");

printf("Pilih: ");

}

void namaProduk(){

do{

printf("Input nama produk: ");

scanf("%[^\n]", nama); getchar();

}

while(strlen(nama) < 1 || strlen(nama) > 100);

}

void stokProduk(){

do{

printf("Input stok produk: ");

scanf("%d", &stok); getchar();

}

while(stok < 1 || stok > 100);

}

unsigned long long int hargaProduk(){

int bawah  = 100;

long long int atas = 999000;

return (rand() % (atas - bawah + 1) + bawah);

}

void push(char nama[105], int stok, double harga){

curr = (struct produk*) malloc(sizeof(struct produk));

strcpy(curr->nama, nama);

curr->stok = stok;

curr->harga = harga;

curr->prev = NULL;

curr->next = NULL;

if(head == NULL){

head = tail = curr;

}

else if(strcmp(curr->nama, head->nama) < 0){

head->prev = curr;

curr->next = head;

head = curr;

}

else if(strcmp(curr->nama, tail->nama) > 0){

tail->next = curr;

curr->prev = tail;

tail = curr;

}

else{

struct produk *temp = head;

while(strcmp(curr->nama, temp->next->nama) > 0){

temp = temp->next;

}

curr->next = temp->next;

temp->next = curr;

curr->prev = temp;

temp->next->prev = curr;

}

}

void pop(char nama[105]){

if(strcmp(nama, head->nama) == 0 && head == tail){

printf("Sukses!\n", curr->nama);

free(head);

head = tail = NULL;

}

else if(strcmp(nama, head->nama) == 0){

curr = head;

head = head->next;

printf("Sukses!\n", curr->nama);

free(curr);

head->prev = NULL;

}

else if(strcmp(nama, tail->nama) == 0){

curr = tail;

tail = tail->prev;

printf("Sukses\n", curr->nama);

free(curr);

tail->next = NULL;

}

else{

curr = head;

while(curr != NULL){

if(strcmp(nama, curr->nama) == 0) 

break;

curr = curr->next;

}

if(curr == NULL) printf("Tidak ditemukan!\n");

else{

curr->next->prev = curr->prev;

curr->prev->next = curr->next;

printf("Sukses!\n", curr->nama);

free(curr);

}

}

}

void edit(char nama[105]){

curr = head;

while(curr != NULL){

if(strcmp(nama, curr->nama) == 0) 

break;

curr = curr->next;

}

if (curr == NULL) printf("Tidak ditemukan!\n");

else{

printf("Edit produk\n");

stokProduk();

curr->stok = stok;

printf("Sukses diubah!\n", curr->nama);

}

}

void add(){

printf("Tambahkan produk\n");

namaProduk();

curr = head;

while(curr != NULL){

if(strcmp(nama, curr->nama) == 0) 

break;

curr = curr->next;

}

if(curr == NULL){

stokProduk();

harga = hargaProduk();

push(nama, stok, harga);

printf("Sukses ditambahkan!\n");

}

else{

printf("Sudah tersedia!\n");

edit(nama);

}

}

void deleteProduk(){

printf("Hapus Produk\n");

namaProduk();

pop(nama);

}

void view(int pilih){

long long int total = 0;

int idx = 0;

if(pilih == 4){

printf("Daftar produk\n");

}

else if(pilih == 5) printf("============================ RECEIPT ============================\n");

printf("|| %3s || %-20s || %3s || %18s || %15s ||\n", "No.", "Nama Produk", "Stok", "Harga", "Total Harga");

curr = head;

while(curr != NULL){

printf("|| %3d. || %-20s || %3d || %-8s %9ld || %-5s %9ld ||\n", idx + 1, curr->nama, curr->stok, "Rp.", curr->harga, "Rp.", curr->stok* curr->harga);

total += curr->stok* curr->harga;

curr = curr->next;

idx++;

}

if(pilih == 4){

printf("==================================================================================\n");

puts("");

printf("Total: Rp. %ld\n", total);

}

else if(pilih == 5){

printf("==================================================================================\n");

puts("");

printf("Total Pembayaran : Rp. %ld\n", total);

printf("Kindness is free\n\n");

}

}

int main(){

int pilih = -1;

do{

system("cls");

menu();

scanf("%d", &pilih); getchar();

switch(pilih){

case 1:

add();

break;

case 2:

if(head == NULL){

printf("Data tidak ditemukan\n");

}

else{

namaProduk();

edit(nama);

}

break;

case 3:

if(head == NULL){

printf("Data tidak ditemukan\n");

}

else deleteProduk();

break;

case 4:

if(head == NULL){

printf("Data tidak ditemukan\n");

}

else view(pilih);

break;

case 5:

view(pilih);

break;

}

if(pilih < 5 && pilih > 0){

getchar();

}

}

while(pilih != 5);

return 0;

}