Materi Pertemuan 6 Data Structure TREE & BINARY TREE

     Materi Pertemuan 1 COMP6048 – Data Structure

Pointer, Array and Introduction to Data Structure

1. Array

    Array adalah Kumpulan elemen data yang serupa.

    Sifat-sifat array:

• Elemen data ini memiliki tipe data yang sama/sejenis (homogen)
• Elemen-elemen array disimpan di lokasi memori berturut-turut dan direferensikan oleh sebuah indeks
• Indeks Array dimulai dari nol

    Array Declaration & Accessing Array

    Setiap array memiliki dimensi array yang berbeda-beda dan maksimal dimensi yang dapat dimiliki oleh satu variabel adalah 

 

standar merekomendasikan penerapan untuk menerima setidaknya 256 (ISO 14882, B.2), namun mereka mungkin mendukung lebih sedikit atau lebih: 

(Thanks for the information from https://stackoverflow.com/questions/10738267/what-is-the-maximum-number-of-dimensions-allowed-for-an-array-in-c)

• Array Satu Dimensi

Pernyataan:                                   

int arr [5];

int merupakan jenis variabel

ukuran array berikut adalah 5 dengan indeks (0,1,2,3 dan 4)

Mengakses:

arr [0] = 7;

arr [1] = 2;

arr [2] = 13;

arr [3] = 13;

arr [4] = 13;

syntax : 

nama jenis [ukuran];

Sebuah array ukuran N memiliki indeks dari 0 sampai N-1.

             

• Array Dua Dimensi

Pernyataan:

int arr [3] [6];

tipe array berikut adalah integer

memiliki 2 dimensi

dalam array integer 2 dimensi indeks pertama menujukann baris sedangkan indeks ke2 menujukkan kolom

ukuran indeks 1 adalah 4 (0,1,2 dan 3), sedangkan indeks 2 berukuran 6 (0,1,2,3,4 dan 5)

Mengakses:

arr [0] [2] = 2;

arr [2] [1] = 9;

arr [1] [5] = 13;

arr [2] [4] = 10;

    

syntax :

nama jenis [size1] [size2];

Indeks pertama array berkisar antara 0 sampai size1 - 1. 

Indeks kedua array berkisar antara 0 sampai size2 - 1.

• Array Multi Dimensi

Pernyataan:

int arr [4] [3] [7] [10];

tipe array integer

memiliki 4 dimensi

index 1 berukuran 4 (0,1,2 dan 3)

index 2 berukuran 3 (0,1 dan 2)

index 3 berukuran 7 (0,1,2,3,4,5 dan 6)

index 4 berukuran 10 (0,1,2,3,4,5,6,7,8 dan 9)

Mengakses:

arr [0] [2] [2] [9] = 2;

arr [2] [1] [6] [0] = 9;

arr [3] [0] [0] [6] = 13;

arr [2] [1] [3] [8] = 10;

syntax :

nama jenis [size1] [size2] [size3] [...];

Indeks pertama array berkisar

dari 0 sampai ukuran 1 - 1.

Indeks kedua array berkisar

dari 0 sampai ukuran 2 - 1.

Indeks ketiga array berkisar

dari 0 sampai ukuran3 - 1.

dan seterusnya.

        Storing Array Values

Inisialisasi Array

        Contoh:  int marks [5] = {90, 82, 78, 95, 88};

Memasukkan Nilai

        Contoh: int i, marks [10];

                      for(i = 0; i <10; i ++)

                      scanf ("%d", & marks[i]);

Menetapkan Nilai

        Contoh: int i, arr1 [10], arr2 [10];

                      for(i = 0; i <10; i ++)

                      arr2 [i] = arr1 [i];

                      (mengcopy array ke array lain)

       Operations in Array

Ada sejumlah operasi yang bisa dilakukan

pada array :

• Traversal
• Insertion
• Searching
• Deletion
• Merging
• Sorting

2. Pointer

     adalah tipe data yang nilainya mengacu pada nilai lain yang tersimpan di tempat lain dalam                 memori komputer menggunakan alamatnya.

     Dua operator terpenting yang digunakan dengan tipe pointer adalah:

•  & the address operator (menunjukan alamat)
•  * the dereferencing operator (menunjukkan nilai)

Jika kita memiliki deklarasi seperti berikut :

int x;

int *px;

maka x adalah integer dan px adalah pointer ke integer. Jika kita mengatakan:

px = &x;

maka &x mengembalikan alamat x dan menugaskannya sebagai nilai px.

Untuk menetapkan nilai x bisa kita katakan

x = 10;

atau

*px = 10;

Perbedaan antara single pointer dan double pointer : (Thanks for the information from https://www.quora.com/What-is-the-difference-between-the-single-pointer-and-double-pointer)

The concept of pointer can easily be explained with the help of an example:

Value of x=50 adress of x= 120

Adress of y= 130

Adress of z= 140

Now let y= &x and z=&y

Then to print the value of x we can write :

printf(“%d”,x); or printf(“%d”,*y) both of these Will print the value 50

Now since y=&x thus y will store the adress of x

Printf(“%d”,y)=120

And z will store the address of y

z=&y thus printf(“%d',z)=130

Now if you use single pointer

Printf(“%d”,*z)= 120

When you use double pointer than

printf(“%d”,**z)=50

Therefore you could easily see the difference here , variable having single pointer points to the value of another variable whose address it stores whereas variable having double pointer points to the value of another variable whose address is already being stored in some other variable.

Banyak pointer (*) dalam satu variabel adalah (Thanks dor the information from https://stackoverflow.com/questions/10087113/how-many-levels-of-pointers-can-we-have)

The C standard specifies the lower limit:

5.2.4.1 Translation limits

276 The implementation shall be able to translate and execute at least one program that contains at least one instance of every one of the following limits: [...]

279 — 12 pointer, array, and function declarators (in any combinations) modifying an arithmetic, structure, union, or void type in a declaration

The upper limit is implementation specific.

3. Data Structure

    Struktur data adalah susunan data, baik dalam memori komputer maupun pada penyimpanan disk.

    

    Beberapa contoh umum dari struktur data meliputi:

• Arrays
• Linked lists
• Queues
• Stacks
• Binary trees
• Hash tables

  Tipe data structure :

• Array

          Kumpulan elemen data yang serupa

          Elemen data memiliki tipe data yang sama

          Dalam array, User harus memesan terlebih dahulu jumlah array yang akan digunakan

        index berikut harusnya dimulai dari angka 0.

• Linked list

         Struktur data yang sangat dinamis dimana elemen dapat ditambahkan ke atau dihapus dari                   mana saja sesuka hati

         Setiap elemen disebut node.

• Queue

          Unsur yang dimasukkan pertama adalah yang pertama dibawa keluar

          Elemen dalam antrian ditambahkan pada salah satu ujungnya yang disebut bagian belakang                dan dilepas dari ujung yang disebut front.

          menggunakan sistem antrian First in First Out.

• Stacks

          Tumpukan dapat diwakili sebagai array linier

          Setiap stack memiliki variabel TOP yang terkait dengannya

          menggunakan sistem First in Last out 

• Binary Trees

          Struktur data yang didefinisikan sebagai kumpulan elemen yang disebut node

          Setiap node berisi pointer kiri, pointer kanan, dan elemen data.

4. Abstract Data Type

    Abstract Data Type (ADT) adalah tipe data yang disusun sedemikian rupa sehingga spesifikasi            objek dan spesifikasi operasi pada objek dipisahkan dari representasi objek dan pelaksanaan                operasi.

    C / C ++ memiliki konsep yang disebut class dan struct yang membantu programmer dalam                mengimplementasikan tipe data abstrak.

    Contoh :

    Seharusnya kita ingin membuat ADT bilangan natural yang memiliki bilangan bulat sebagai objek      dan beberapa fungsi sebagai operasi.

    struktur nomor

    benda: bilangan bulat x

    fungsi:

    bool is_zero () jika (x == 0) kembali TRUE lagi kembali FALSE

    bool sama (y) jika (x == y) return TRUE else return FALSE

    void set (y) x = y

    void add (y) x = x + y

    int get () kembali x.