Data Structure Summary 2 Semester

Summary Pembelajaran 2 Semester

Pemrograman Bahasa C

            

Pada awal Pengenalan bahasa C kita diperkenalkan 3 tipe data dasar yaitu :

• Char --> scanf("%c")

                 Char merupakan tipe data yang menyimpan 1 karakter 

• Integer --> scanf("%d")

                 Integer merupakan tipe data yang menampung angka bulat

• Float --> scanf("%f") 

                 Float merupakan tipe data yang menampung angka pecahan

Selain itu kita juga diperkenalkan beberapa Program Control. 

yang pertama yaitu Repetition (pengulangan) dimana program akan mengulang terus apabila syaratnya terpenuhi. contoh :

• While : suatu kondisi di cek terlebih dahulu, lalu perintah dijalankan

            while (x == 0){

                         printf ("hello world/n");

                    }

• Do-while : suatu perintah dijalankan dahulu, lalu dicek kondisinya 

            do {

                      printf("hello world/n");

              } while (x == 0);

• For : program akan mengulang perintah sampai jumlah yang ditentukan tercapai

           for (i=0; i<x; i++){

                printf("hello world/n");

             }

selain itu juga kita dikenalkan dengan Selection (pemilihan) dimana terdapat beberapa perintah yang apabila ingin dijalankan, salah satu kondisi harus terpenuhi. Contoh :

• If  : perintah akan dijalankan apabila syarat terpenuhi

          if (x == 0){

          printf("hello world");

}

• If-else : apabila syarat pada perintah di awal (if) tidak terpenuhi, program akan menjalankan perintah kedua (else)

          if(x == 0){

          printf("hello world");

}else printf("hey world");

• Switch-case : perintah yang dijalankan adalah perintah yang syaratnya terpenuhi

           switch(x){

                     case ('0') : printf("hello world");

                     case ('1') : printf("hey world");

                     default : printf("unknown");

}


Array

Array adalah kumpulan elemen yang mempunyai tipe data yang sama dan elemennya dapat diakses secara berurutan sampai jumlah elemen yang telah ditentukan. contoh:

      char x[10];

diatas merupakan contoh deklarasi array 1 dimensi. apabila berdimensi 2 atau lebih bisa seperti ini:

     char x[10][10];

Pointer

Pointer merupakan penunjuk alamat variable yang menyimpan sebuah value, dan kita dapat merubah value dari alamat yang dituju tersebut. Pointer dapat dilakukan menggunakan beberapa operator seperti:

• * --> operator penunjuk
• & --> operator dari alamat suatu variable yang ditunjuk

Linked List

Linked List adalah sekumpulan node yang saling dihubungkan oleh sebuah pointer. Sebuah rangkaian Linked List selalu diawali dengan sebuah head untuk menunjukkan alamat awal dan diakhiri dengan pointer yang mengarah ke Null. Disebut Single karena pointernya hanya memiliki satu arah dan bukan dua arah atau bolak-balik.

Single Linked list pada umumnya terdapat dua macam, Circular dan Non- Circular.




Berikut adalah ilustrasi single linked list Non-Circular :




Berikut adalah ilustrasi single linked list Circular :

Dengan kata lain, Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri.





Double Linked List adalah rangkaian Linked List yang memiliki 2 arah pointer yang merujuk pada Next Node (Node Sesudahnya) dan Prev Node (Node Sebelumnya). Sama halnya dengan Single Linked List, Double Linked List juga terdapat 2 macam yaitu Non-Circular dan Circular.



Berikut adalah ilustrasi double linked list Non-Circular :




Berikut adalah ilustrasi double linked list Circular :






OPERASI PADA DOUBLE LINKED LINK

Double linked list memiliki beberapa operasi dasar pada list:

1. INSERT FIRST
Penyisipan di awal list, sehingga pointer tail juga akan berpindah ke elemen baru.


2. INSERT LAST
Penyisipan di akhir list, sehingga pointer tail juga akan berpindah ke elemen baru.



3. INSERT AFTER/BEFORE
Penyisipan after/before kurang lebih sama satu sama lain. Pada kasus di atas berlaku juga insert before 3.



                                                   Gambar 1 : After


                                                       Gambar 2 : Before

4. DELETE FIRST
Penghapusan di awal list, pointer head akan berpindah ke node selanjutnya, sementara node awal akan di dealokasi.



5. DELETE LAST
Penghapusan di akhir list, pointer tail akan berpindah ke node sebelumnya, sementara node akhir akan di dealokasi.



6. DELETE NODE
Penghapusan node dengan data tertentu, pada kasus di atas yaitu delete node 2.

A. Hashing Table

            

              Hash Table adalah struktur data yang menyimpan data secara asosiatif. Dalam tabel hash, data disimpan dalam format array, di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat jika kita mengetahui indeks dari data yang diinginkan.

Dengan demikian, itu menjadi struktur data di mana operasi penyisipan dan pencarian sangat cepat terlepas dari ukuran data. Tabel hash menggunakan array sebagai media penyimpanan dan menggunakan teknik hash untuk menghasilkan indeks di mana elemen yang akan dimasukkan atau harus ditempatkan dari.

              Hashing adalah teknik untuk mengubah rentang nilai-nilai kunci menjadi rentang indeks array. Kita akan menggunakan operator modulo untuk mendapatkan rentang nilai kunci. Pertimbangkan contoh tabel hash ukuran 20, dan item berikut ini harus disimpan. Item dalam format (kunci, nilai).

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

Struktur dan Fungsi pada Hash Tabel

          Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

         Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

            k(x) = fungsi pembangkit field kunci (1)

            h(x) = hash function (2)

B. BINARY TREE

       Pohon yang unsurnya paling banyak memiliki 2 anak disebut Binary Tree (Pohon Binary). Karena setiap elemen dalam Binary Tree hanya dapat memiliki 2 anak, kami biasanya menamai mereka anak kiri dan kanan.

       

Binary Tree terdiri dari beberapa bagian :

• Data
• Pointer to left child
• Pointer to right child

Tipe-tipe Binary Tree

1. PERFECT Binary Tree : adalah binary tree dimana setiap levelnya berada di depth yang sama.

                                      

      2. COMPLETE Binary Tree :  adalah binary tree yang setiap levelnya, kecuali kemungkinan yang terakhir, telah   lengkap terisi,  dan semua node sejauh mungkin dibiarkan. Pohon biner sempurna adalah pohon biner lengkap.

     3. SKEWED Binary Tree : adalah binary tree dimana setiap nodenya memiliki paling banyak 1 anak.

     4. BALANCED Binary Tree : adalah binary tree dimana tidak ada daun yang lebih jauh dari akar dibandingkan dengan daun yang lain.

Mengimplementasikan Binary Tree

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Hashing Table and Binary Tree

HASHING TABLE AND BINARY TREE

HASHING TABLE AND BINARY TREE

A. Hashing Table

            

              Hash Table adalah struktur data yang menyimpan data secara asosiatif. Dalam tabel hash, data disimpan dalam format array, di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat jika kita mengetahui indeks dari data yang diinginkan.

Dengan demikian, itu menjadi struktur data di mana operasi penyisipan dan pencarian sangat cepat terlepas dari ukuran data. Tabel hash menggunakan array sebagai media penyimpanan dan menggunakan teknik hash untuk menghasilkan indeks di mana elemen yang akan dimasukkan atau harus ditempatkan dari.

              Hashing adalah teknik untuk mengubah rentang nilai-nilai kunci menjadi rentang indeks array. Kita akan menggunakan operator modulo untuk mendapatkan rentang nilai kunci. Pertimbangkan contoh tabel hash ukuran 20, dan item berikut ini harus disimpan. Item dalam format (kunci, nilai).

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

Struktur dan Fungsi pada Hash Tabel

          Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

         Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

            k(x) = fungsi pembangkit field kunci (1)

            h(x) = hash function (2)

B. BINARY TREE

       Pohon yang unsurnya paling banyak memiliki 2 anak disebut Binary Tree (Pohon Binary). Karena setiap elemen dalam Binary Tree hanya dapat memiliki 2 anak, kami biasanya menamai mereka anak kiri dan kanan.

       

Binary Tree terdiri dari beberapa bagian :

• Data
• Pointer to left child
• Pointer to right child

Tipe-tipe Binary Tree

1. PERFECT Binary Tree : adalah binary tree dimana setiap levelnya berada di depth yang sama.

                                      

      2. COMPLETE Binary Tree :  adalah binary tree yang setiap levelnya, kecuali kemungkinan yang terakhir, telah   lengkap terisi,  dan semua node sejauh mungkin dibiarkan. Pohon biner sempurna adalah pohon biner lengkap.

     3. SKEWED Binary Tree : adalah binary tree dimana setiap nodenya memiliki paling banyak 1 anak.

     4. BALANCED Binary Tree : adalah binary tree dimana tidak ada daun yang lebih jauh dari akar dibandingkan dengan                                                             daun yang lain.

Mengimplementasikan Binary Tree

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Single Linked List

Single Linked List adalah sekumpulan node yang saling dihubungkan oleh sebuah pointer. Sebuah rangkaian Single Linked List selalu diawali dengan sebuah head untuk menunjukkan alamat awal dan diakhiri dengan pointer yang mengarah ke Null. Disebut Single karena pointernya hanya memiliki satu arah dan bukan dua arah atau bolak-balik.

Single Linked list pada umumnya terdapat dua macam, Circular dan Non- Circular.




Berikut adalah ilustrasi single linked list Non-Circular :




Berikut adalah ilustrasi single linked list Circular :

Dengan kata lain, Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri.





Double Linked List adalah rangkaian Linked List yang memiliki 2 arah pointer yang merujuk pada Next Node (Node Sesudahnya) dan Prev Node (Node Sebelumnya). Sama halnya dengan Single Linked List, Double Linked List juga terdapat 2 macam yaitu Non-Circular dan Circular.



Berikut adalah ilustrasi double linked list Non-Circular :




Berikut adalah ilustrasi double linked list Circular :






OPERASI PADA DOUBLE LINKED LINK

Double linked list memiliki beberapa operasi dasar pada list:

1. INSERT FIRST
Penyisipan di awal list, sehingga pointer tail juga akan berpindah ke elemen baru.


2. INSERT LAST
Penyisipan di akhir list, sehingga pointer tail juga akan berpindah ke elemen baru.



3. INSERT AFTER/BEFORE
Penyisipan after/before kurang lebih sama satu sama lain. Pada kasus di atas berlaku juga insert before 3.



                                                   Gambar 1 : After


                                                       Gambar 2 : Before

4. DELETE FIRST
Penghapusan di awal list, pointer head akan berpindah ke node selanjutnya, sementara node awal akan di dealokasi.



5. DELETE LAST
Penghapusan di akhir list, pointer tail akan berpindah ke node sebelumnya, sementara node akhir akan di dealokasi.



6. DELETE NODE
Penghapusan node dengan data tertentu, pada kasus di atas yaitu delete node 2.