Review Materi Data Structure Sebelum Ujian Mid Semester 2020

WILSON NATHANIEL PRAYUDI - 2301863212

I. Pointer And Array Review & Introduction To Data Structure

Data Structure

Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.

Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) ataupun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.

Array
Array adalah sekumpulan variable yang bertipe data sama yang dibedakan oleh indeks. Suatu Array mempunyai jumlah komponen yang banyaknya tetap. Banyaknya komponen dalam suatu larik ditunjukan oleh suatu indek untuk membedakan variabel yang satu dengan variabel yang lainnya. Dalam bahasa C, index dari array dimulai dengan 0 (zero).

Variabel array dalam Borland C++, dapat digolongkan menjadi Dua buah dimensi:

·         Array Satu Dimensi

·         Array Dua Dimensi

1.     Array Satu Dimensi

Sebelum digunakan, variabel array perlu dideklarasikan terlebih dahulu. Cara mendeklarasikan variabel array sama seperti deklarasi variabel yang lainnya, hanya saja diikuti oleh suatu indek yang menunjukan jumlah maksimum data yang disediakan.

Bentuk Umum pendeklarasian array : Tipe-Data Nama_Variabel[Ukuran];
Keterangan    :
Type Data      : Untuk menyatakan type data yang digunakan.
Ukuran            : Untuk menyatakan jumlah maksimum elemen array.

2.    Array Dua Dimensi

Array dimensi dua tersusun dalam bentuk baris dan kolom, dimana indeks pertama menunjukan baris dan indeks kedua menunjukan kolom. Array dimensi dua dapat digunakan seperti pendatan penjualan, pendataan nilai dan lain sebagainya.

Bentuk Umum pendeklarasian Array:
Tipe-Data Nama_Variabel[index-1][index-2];
Keterangan    :
Type Data      : Untuk menyatakan type data yang digunakan.
Index-1          : Untuk menyatakan jumlah baris
Index-2          : Untuk menyatakan jumlah kolom

Contoh Penulisannya : int penjualan[3][3]

Inisialisasi Array
Inisialisasi adalah memberikan nilai awal terhadap suatu variabel. Bentuk pendefinisian suatu array dapat dilihat dari contoh berikut :
Tipe_data nama_array[jml_elemen] = { nilai array };

Contoh Penulisannya : float nilai [2][3]={{3,5,7},{2,4,6}}

POINTER

Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Alamat ini merupakan lokasi dari obyek lain (biasanya variabel lain) di dalam memori. Contoh, jika sebuah variabel berisi alamat dari variabel lain, variabel pertama dikatakan menunjuk ke variabel kedua. Seperti halnya variabel yang lain, variabel pointer juga harus dideklarasikan terlebih dahulu sebelum digunakan.

Bentuk Umum : Tipe_data *nama_pointer;

 Operator Pointer ada dua, yaitu :

·         Operator &

Operator & bersifat unary (hanya memerlukan satu operand saja).

Operator & menghasilkan alamat dari operandnya.

·         Operator  *

Operator * bersifat unary (hanya memerlukan satu operand saja).

Operator * menghasilkan nilai yang berada pada sebuah alamat.

Operasi Pointer

·         Operasi Penugasan

Suatu variable pointer seperti halnya variable yang lain, juga bisa mengalami operasi penugasan. Nilai dari suatu variable pointer dapat disalin ke variable pointer yang lain.

·         Operasi Aritmatika

Suatu variabel pointer hanya dapat dilakukan operasi aritmatika dengan nilai integer saja. Operasi yang biasa dilakukan adalah operasi penambahan dan pengurangan. Operasi penambahan dengan suatu nilai menunjukkan lokasi data berikutnya (index selanjutnya) dalam memori. Begitu juga operasi pengurangan.

·         Operasi Logika

Suatu pointer juga dapat dikenai operasi logika.

II. Linked List

Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.

Sebuah linked list yang hanya memiliki 1 penghubung ke node lain disebut sebagai single linked list.

Di dalam sebuah linked list, ada 1 pointer yang menjadi gambaran besar, yakni pointer HEAD yang menunjuk pada node pertama di dalam linked list itu sendiri.

Sebuah linked list dikatakan kosong apabila isi pointer head adalah NULL.

Beberapa operasi yang biasanya ada di dalam sebuah linked list adalah:

1.     Push

Push merupakan sebuah operasi insert dimana di dalam linked list terdapat 2 kemungkinan insert, yaitu insert melalui depan (pushDepan) ataupun belakang (pushBelakang). Operasi pushDepan berarti data yang paling baru dimasukkan akan berada di depan data lainnya, dan sebaliknya pushBelakang berarti data yang paling baru akan berada di belakang data lainnya.

Representasinya adalah sebagai berikut:

·        pushDepan: 5, 3, 7, 9 maka hasilnya adalah: 9 ->7 ->3 -> 5 -> NULL

·        pushBelakang: 5, 3, 7, 9 maka hasilnya adalah: 5 ->3 ->7 ->9 -> NULL

2.     Pop

Pop, kebalikan dari push, merupakan operasi delete, dimana di dalam linked list memiliki 2 kemungkinan delete, yaitu melalui depan (popDepan) dan melalui belakang (popBelakang). PopDepan berarti data yang akan dihapus adalah data paling depan, dan popBelakang berarti data yang akan dihapus adalah data paling belakang (akhir).

Dalam penerapan code single linked list, umumnya hanya digunakan pointer head sebagai pointer yang menunjuk pada linked list. Namun dalam pembahasan artikel ini akan digunakan 1 pointer tambahan, yakni TAIL untuk menunjuk data terakhir di dalam linked list dalam mempermudah proses pembahasan.

III. Stack & Queue

Stack

Stack adalah salah satu struktur data yang memiliki sistem kerja Last In First Out (LIFO), yang terakhir masuk pertama keluar. Dapat di ilustrasikan seperti sebuah tumpukan buku, ketika mengambil sebuah buku di dalam tumpukan itu maka harus diambil satu persatu dari buku yang paling atas dari tumpukan buku tersebut. Sebuah stack hanya dapat ditambahkan dan dikurangi elemennya hanya dari satu sisi yakni elemen atasnya atau biasa disebut Top Of Stack.

Fungsi dalam Stack:

Fungsi init: fungsi yang digunakan untuk inisialisasi atau membuat stack baru yang masih kosong.

Fungsi full: digunakan untuk mengetahui stack penuh atau tidak.

Fungsi empty: digunakan untuk mengetahui stack kosong atau tidak.

Fungsi clear: digunakan untuk mengosongkan stack. Stack dianggap kosong apabila                puncak stack berada pada posisi -1.

Fungsi push: digunakan untuk menambahkan data ke dalam stack. Penambahan data             tidak bisa dilakukan apabila stack sudah penuh. Urutan perintahnya adalah:         menambahkan nilai top dan menambahkan data pada posisi nilai top. Jika dalam    Linked List menggunakan method addLast

Fungsi pop: digunakan untuk mengeluarkan data teratas stack dengan syarat bahwa              stack tidak kosong. Urutan perintahnya adalah : menghapus data pada posisi nilai   top dan menurunkan nilai top. Jika dalam Linked List menggunakan method     removeLast

Queue

Queue adalah kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Berbeda dengan stack yang bersifat LIFO maka queue bersifat FIFO(First In First Out), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.

Fungsi dalam Queue:

Fungsi init : digunakan untuk membuat queue baru atau kosong, yaitu dengan         memberi nilai awal (head) dan nilai akhir (tail) dengan -1.

Fungsi full: digunakan untuk mengetahui apakah queue sudah penuh atau belum.   Dilakukan dengan memeriksa nilai akhir (tail) apakah sudah sama dengan maksimal         queue.

Fungsi empty: digunakan untuk mengetahui apakah queue masih kosong atau tidak.               Dilakukan dengan memeriksa nilai akhir (tail) bernilai -1 atau tidak.

Fungsi enqueue : digunakan untuk menambahkan elemen ke dalam queue.

Fungsi dequeue : digunakan untuk mengambil elemen dari queue, dengan cara      memindahkan semua elemen satu langkah ke posisi depannya sehingga elemen yang         paling depan tertimpa.

Fungsi clear : digunakan untuk menghapus semua elemen dalam queue. Ada dua   cara yang bisa digunakan, yaitu menuliskan fungsi seperti inisialisasi atau   memanggil fungsi remove sampai queue kosong.

IV. Hashing And Hash Tables, Trees & Binary Tree

Hashing

Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan  data dan penghapusan data dapat dilakukan dengan cepat.

Hash Table

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.

Binary Tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.

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.

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

V. Binary Search Tree

Binary Search Tree

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list

Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut:

§  Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.

§  Semua data dibagian kanan sub-tree dari node t selalu lebih besar atausama dengan data dalam node t.

Tugas :

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//Wilson Nathaniel Prayudi - 2301863212
void menu()
{
    printf("========================");
    printf("\n     Wilson Market");
    printf("\n========================");
    printf("\n1. Beli Barang");
    printf("\n2. Edit Barang");
    printf("\n3. Hapus Barang");
    printf("\n4. Keluar");
    printf("\n\nMasukan Pilihan: \n");
}
struct data
{
char item[100];
int qty;
int price ;
struct data* next;
struct data* prev;
}*head = NULL, *tail = NULL;

void insert()
{
    int qty;
    int price;
    char item[100];
    printf("Nama Barang: ");
    scanf(" %[^\n]", &item); getchar();
    printf("Type qty: ");
    scanf("%d", &qty);getchar();
    price = item[0] * 100;
struct data* node = (struct data*) malloc(sizeof(struct data));
node->qty = qty;
strcpy(node->item, item);
node->price = price;
node->next = NULL;
node->prev = NULL;

if(head == NULL) {
head = tail = node;
}
else {
tail->next = node;
node->prev = tail;
tail = node;
}
}

void editNode()
{
    int flag = -1;
    char item[100];
    int qty;
    printData();
    printf("Barang Yang Ingin Diubah: ");
    scanf(" %[^\n]", &item);

    struct data *temp = head;
while(temp != NULL) {
if(strcmp(temp->item, item)==0) {
flag = 1;
break;
}
temp = temp->next;
}
if(flag == 1){

        printf("Input Qty Baru: ");
        scanf("%d", &qty);
        temp->qty = qty;

        printf("Barang Berhasil Diubah\n\n\n");
}
else{
        printf("Barang Tidak Ada Di List\n\n\n");
        editNode();
}
}
void deleteNode() {

char item[100];
int flag = -1;
    printData();
    printf("Barang Yang Ingin Dihapus: ");
    scanf(" %[^\n]", &item);
struct data *temp = head;
while(temp != NULL) {
if((strcmp(temp->item, item)==0)){
            flag = 1;
break;
}
temp = temp->next;
}
    if(flag == 1){
        
        if(temp == head && head == tail) {
            head = tail = NULL;
            free(temp);
        }
       
        else if(temp == head) {
            head = head->next;
            head->prev = NULL;
            free(temp);
        }
        else if(temp == tail) {
            tail = tail->prev;
            tail->next = NULL;
            free(temp);
        }

        else {
            temp->prev->next = temp->next;
            temp->next->prev = temp->prev;
            free(temp);
        }
        printf("Barang Berhasil Dihapus\n\n\n");
    }
    else{
        printf("Barang Tidak Ada Di List\n\n\n");
        deleteNode();
    }
}
void checkOut(){
    int total = 0;
    struct data* temp = head;
if(temp == NULL){
        printf("List Kosong\n\n");
}
else{
            printf("%10s%10s%15s\n", "Barang", "Qty", "Harga");
            while(temp != NULL) {
            printf("%10s%10d%10d%10d\n", temp->item, temp->qty, temp->price, temp->price*temp->qty);
            total += temp->price * temp->qty;
            temp = temp->next;
        }
        printf("%15s    Rp.%3.d\n\n", "TOTAL ",total);
        printf("         Kindness Is Free");
    }

}
void freeAll() {
struct data* temp;
while(head != NULL) {
temp = head;
head = head->next;
free(temp);
}

head = tail = NULL;
}
void printData() {
struct data* temp = head;
if(temp == NULL){
        printf("List Kosong!\n");
}
else{
            while(temp != NULL) {
            printf("Barang: %s\n", temp->item);
            printf("Qty: %d\n", temp->qty);
            temp = temp->next;
        }
    }
}
int main()
{
    int pilih;
    char get;
    do
{
        menu();
        scanf("%d", &pilih);
        switch(pilih)
{
            case 1: insert();
                    break;
            case 2: editNode();
                    break;
            case 3: deleteNode();
                    break;
            case 4: checkOut();
                    printf("\n     Press and Enter Any Key To Exit\n");
                    scanf("%s", &get);
                    pilih = 5; getchar();
        }
    }while(pilih!=5);
return 0;

}