Belajar Data Structure

ini yang saya catat hanya bagian yang pelajari

1. Pointer

     

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

   untuk simbol pointer ada dua yaitu : - & = Alamat Operator

                                                              - * = Operator Dereferencing

   Untuk mendeklarasikan variabel pointer dapat diberikan seperti di bawah ini:

   ~  data_type *ptr name;

   ~  contoh : - int*pnum;

                     - char *pch;

                     - float *pfnum;

   Dalam setiap pernyataan di atas, variabel penunjuk dinyatakan untuk menunjuk ke variabel dari           tipe data yang ditentukan.

   Meskipun semua petunjuk ini menunjuk ke tipe data yang berbeda, mereka akan menempati       jumlah ruang yang sama dalam memori (tergantung pada platform tempat kode akan dijalankan).

        

  Di C, Anda juga diperbolehkan menggunakan pointer yang menunjuk ke pointer. Pointer pada       gilirannya menunjuk ke data (atau bahkan ke pointer lainnya). Untuk mendeklarasikan pointer ke   pointer, cukup tambahkan tanda bintang * untuk setiap level referensi.

  For Example: 

          int x = 10;

          int *px, **ppx;

          px = &x;

          ppx = &px;

  2.  Linked List 

• Daftar linked list terdiri dari dua jenis:  Single Linked List, Double Linked List
• Linked List VS Array : 

           - Array : Koleksi linear elemen data, Simpan nilai di lokasi memori berurutan, Dapat acak                                  dalam mengakses data

           - Linked List  : Koleksi linear dari node, Tidak menyimpan simpulnya di lokasi memori                                                berurutan, Hanya dapat diakses secara berurutan

             

• Memory Allocation : Dynamic

          - Jika Anda perlu mengalokasikan memori secara dinamis (dalam runtime), Anda dapat                           menggunakan malloc di C / C ++.

          - Untuk membatalkan alokasi, Anda dapat menggunakan free.

          - contoh : 

                     int  *px = (int *)                       malloc(sizeof(int));

     char *pc = (char *)                     malloc(sizeof(char));

     *px = 205;

     *pc = ‘A’;

     printf( “%d %c\n”, *px, *pc );

     free(px);

     free(pc);

• Single Linked List : Insert

         - Untuk menyisipkan nilai baru, pertama-tama kita harus secara dinamis mengalokasikan node               baru dan menetapkan nilai padanya lalu menghubungkannya dengan daftar tertaut yang ada.

         - Misalkan kita ingin menambahkan simpul baru di depan kepala.

    struct tnode *node =

    (struct tnode*) malloc(sizeof(struct        tnode));

     node->value = x;

     node->next  = head;

     head = node;

• Single Linked List : Delete

           - Untuk menghapus nilai, pertama-tama kita harus menemukan lokasi simpul yang                                 menyimpan nilai yang ingin kita hapus, hapus, dan hubungkan daftar yang tertaut lainnya.

           - Misalkan nilai yang ingin kita hapus adalah x dan anggap x ada dalam daftar tertaut dan unik.

           - Ada dua kondisi yang harus kita perhatikan: ~ jika x ada di simpul kepala atau

                                                                                     ~ jika x tidak dalam simpul kepala.

       struct tnode *curr = head;

       // if x is in head node

       if ( head->value == x ) {

       head = head->next;

       free(curr);

       }

       // if x is not in head node, find the            location

       else {

       while ( curr->next->value != x ) curr =       curr->next;

       struct tnode *del = curr->next;

       curr->next = del->next;

       free(del);

       }

 3. Circulan Single List
      
          - Dalam lingkaran, simpul terakhir berisi pointer ke simpul pertama
          - Kita dapat memiliki daftar tertaut tunggal melingkar serta daftar tertaut ganda melingkar.
          - Tidak ada penyimpanan nilai NULL dalam daftar

  4.  Doubly Linked List

            - Double/Doubly linked list or two-way linked list is a linked list data structure with two link,                 one that contain reference to the next data and one that contain reference to the previous                        data.

      struct tnode {

      int value;

      struct tnode *next;

      struct tnode *prev;

      };

      struct tnode *head = 0;

      struct tnode *tail = 0;

 5. Doubly Linked List : Insert

               - Misalkan kita ingin menyisipkan simpul baru di posisi tertentu (setiap lokasi antara kepala           dan ekor)

     struct tnode *a = ??;

     struct tnode *b = ??;

     // the new node will be inserted        between a and b

     struct tnode *node =

     (struct tnode*) malloc(sizeof(struct     tnode));

      node->value  = x;

      node->next  = b;

      node->prev  = a;

      a->next  = node;

      b->prev  = node;

6. Doubly Linked List : Delete

           Ada 4 kondisi yang harus kita perhatikan saat menghapus:

                   -Node yang akan dihapus adalah satu-satunya simpul dalam daftar tertaut.

                   -Node yang akan dihapus adalah head.

                   -Node yang akan dihapus adalah ekor.

                   -Node yang akan dihapus bukan head atau tail. 

           contoh :

                ~ Jika simpul yang akan dihapus adalah satu-satunya simpul:

                   free (head);

                   head = NULL;

                    tail = NULL;

               ~ Jika simpul yang akan dihapus adalah kepala:

                     head = head-> next;

                     free (head-> prev);

                     head-> prev = NULL;

               

                ~ Node yang akan dihapus adalah ekor.

                      tail = tail-> prev;

                      free (tail-> next);

                       tail-> next = NULL;

                 ~ Node yang akan dihapus bukan head atau tail. 

                          struct tnode * curr = head;

                          while (curr-> next-> value! = x) curr = curr-> next;

                           struct tnode * a = curr;

                            struct tnode * del = curr-> next;

                             struct tnode * b = curr-> next-> next;

                              a-> next = b;

                              b-> prev = a;

                              free (del);

7. Circular Doubly Linked List 

           ~ Ini mirip dengan daftar tertaut tunggal melingkar, tetapi total pointer di setiap node di         sini adalah 2 (dua) pointer.

8. Stack Concept 

      ~ Stack adalah struktur data penting yang menyimpan elemen-elemennya secara teratur.

      ~ Analogi:

         Anda pasti melihat tumpukan piring di mana satu piring diletakkan di atas yang lain. Saat Anda           ingin melepas piring, Anda harus melepas pelat paling atas terlebih dahulu. Oleh karena itu,                 Anda dapat menambah dan menghapus elemen (yaitu pelat) hanya di / dari satu posisi yang                 merupakan posisi paling atas.

9. Stack Operations 

  

       ~ push(x)              : tambahkan item x ke bagian atas tumpukan.

       ~ pop()                 : hapus item dari bagian atas tumpukan.

       ~ top()                  : mengungkapkan / mengembalikan item teratas dari tumpukan.

       ~ Note                  : top is also known as peek.

10. Infix, Postfix, and Prefix Notation

       ~ Prefix          : * 4 10

                              : + 5 * 3 4

                              : + 4 / * 6 - 5 2 3 

       ~  Infix           : 4 * 10

                              : 5 + 3 * 4

                              : 4 + 6 * ( 5 - 2) / 3

       ~ Postfix          : 4 10 *

                               : 5 3 4  * +

                               : 4 6 5 2 - * 3 / +

       - Prefix             : operator ditulis sebelum operan

       - Infix               : Operator ditulis di antara operan

       - Postfix           : operator ditulis setelah operan

       ~ Mengapa kita membutuhkan notasi awalan / postfix?

       ~ Notasi awalan dan postfix tidak perlu tanda kurung untuk memprioritaskan prioritas                        operator.

       ~ Prefiks dan postfix jauh lebih mudah bagi komputer untuk mengevaluasi.

11. Depth first Search 

            Visit Order : A,C,B,E,D

12. Queue

         ~ Antrian adalah struktur data penting yang menyimpan elemen-elemennya secara teratur

             Contoh:

                   - Orang bergerak di eskalator. Orang-orang yang naik eskalator akan menjadi orang                                 pertama yang keluar dari eskalator.

                   - Orang-orang menunggu bus. Orang yang berdiri di antrean akan menjadi orang pertama                        yang masuk ke dalam bus

                   - Barang bawaan disimpan di ban berjalan

                   - Mobil berbaris untuk mengisi bensin

                   - Mobil berbaris di jembatan tol

13. Queue Operation 

           ~ push(x)                 : tambahkan item x ke belakang antrian.

           ~ pop()                     :hapus item dari depan antrian.

           ~ front()                   :mengungkapkan / mengembalikan item paling depan dari antrian.

14. Breadth First Search