Rangkuman Algoritma dan struktur data

 Assalamualaikum, Hallo. Perkenalkan nama saya Ratih Puspitasari, salah satu mahasiswa Informatika dari Universitas Muhammadiyah Sidoarjo. Saya Lahir di Sidoarjo, 03 April 2001. Saya akan menyampaikan penjelasan singkat tentanf ALGORITMA DAN STRUKTUR DATA yang bersumber dari modul asli UMSIDA. Jika ingin mengenal lebih dalam tentang Universitas saya silahkan akses link berikut :umsida.ac.id atau fst.umsida.ac.id

Semoga bermanfaat, 
ENJOYYYY !!!!!!

MATERI MODUL

STRUKTUR DATA, ARRAY, POINTER, DAN STRUKTUR

A.  Konsep Dasar Struktur Data

Struktur data adalah bagian dari ilmu pemrograman dasar yang mempunyai karakteristik yang terkait dengan sifat dan cara penyimpanan sekaligus penggunaan atau pengaksesn data.

Struktur data bertujuan agar cara merepresentasikan data dalam memebuat program dapat dilakukan secara efisien dalam pengolahan di memori dan pengolahan penyimpanan dari program ke storage juga lebih mudah dilakukan.

B.  Konsep Dasar Array

Array adalah kumpulan elemen-elemen data. Kumpulan elemen tersebut mempunyai susunan tertentu yang teratur. Jumlah elemen terbatas, dan semua elemen mempunyai tipe data yang sama. Jenis – jenis array :

       Array Satu Dimensi

       Struktur array satu dimensi dapat dideklarasikan dengan bentuk umum berupa :

tipe_var nama_var [ukuran];

Dengan :

-          Tipe_var : untuk menyatakan jenis elemen array (misalnya int, char, unsigned).

-          Nama_var : untuk menyatakan nama variabel yang dipakai.

-          Ukuran : untuk menyatakan jumlah maksimal elemen array.

Contoh : float nilai_ujian [5];

Array Dua Dimensi

Tipe data array dua diemnsi biasa digunakan untuk menyimpan, mengolah maupun mendeklarasikan array agar dapatv menyimpan data adalah :

Tipe_var nama_var[ukuran1][ukuran2];

Dimana :

-          Ukuran 1 menunjukkan jumalah/nomor baris.

-          Ukuran 2 menunjukkan jumlah/nomor kolom.

Jumlah elemen yang dimiliki array dua dimensi dapat ditentukan dari hasil perkalian :

Ukuran1 x ukuran2.

Seperti halnya pada array satu dimensi, data array dua dimensi akan ditempatkan pada memori secara berurutan.

Array Multidimensi / Dimensi Banyak

Array berdimensi banyak atau multidimensi terdiri array yang tidak terbatas hanya dua dimensi saja. Bentuk umum pendeklarasian array multidimesni adalah : tipe_var nama_var[ukuran1][ukuran2]…[ukurann];

Contoh : int data_angaka[3][6][6];

Yang merupakan array tiga dimensi

Mengakses Elemen Array :

Dalam Bahasa C++, data array akan disimpan dalam memori pada alokasi yang berurutan.

Elemen pertama biasanya mempunyai. indeks bernilai 0. Contoh :

Float nilai_tes[5];

Jika pada contoh diatas, variabel nilai_tes mempunyai 5 elemen, maka elemen pertama mempunyai indeks sama dengan 0, elemen kedua mempunyai indeks 1, dan seterusnya. Bentuk umum pengaksesan suatu elemen variabel array adalah :

Nama_var[indeks];

Inisialisasi Array :

Array dapat diinisialisasikan secara langsung saat pertama kali dideklarasikan (efisien untuk array berdimensi sedikit).

Contoh : int x[2]={1,2};

Array dapat dideklarasikan terlebih dahulu, baru kemudian diisi elemnya.

Contoh :

Int x[2];

x[0]=1;

x[1]=2;

C.    Konsep Dasar Pointer

Pointer adalah sebuah variabel yang berisi lamat variabel yang lain. Suatu ponter dimaksudkan untuk meunjuk koperatore suatu alamat memori sehingga alamat dari suatu variabel dapat diketahui dengan mudah. Deklarasi pointer :

Operator painter :

Operator ‘&’ : untuk mendapatkan alamat memori operand/variabel pointer.

Operatot ‘*’ : untuk mengakses nilai data operand/variabel pointer.

D.    Konsep Dasar Struktur

Struktur adalah koleksi dari variabel yang dinyatakan dengan sebuah nama, dengan sifat setiap variabel dapat memiliki tipe yang berlainan.

Struktur biasa dipakai untuk mengelompokkan beberapa informasi yang berkaitanmenjadi sebuah satu kesatuan. Contoh sebuah struktur adalah informasi data tanggal, yang berisi tanggal, bulan, dan tahun.

Mendeklarasikan Struktur :

Contoh pendefisinian tipe data struktur adalah :

Struct data_tanggal

{ int tanggal;

Masing – masi tioe dari elemen struktur dapat berlainan. Adapun variabel_struktur1 sampai dengan variabel_struktur M menyatakan bahwa variabel struktur yag dideklarasikan bisa lebih dari satu. Jika ada lebih dari satu variabel, antara variabel struktur dipisahkan dengan tandakoma.

Mengakses Elemen Struktur :

Elemen dari struktur dapat diakses dengan menggunakan bentuk :

Variabel_struktur.nama_field

Antara variabel_struktur dana nama_field dipisahkan dengan operator titik (disebut operator anggota struktur). Contoh berikut merupakan instruksi untuk mengisikan data padafield tanggal :

      tgl_lahir.tang

      gal=30 int

      bulan;

      int tahun;

      };

Yang mendefinisikantipe struktur bernamadata_tanggal, yang terdiri dari tiga buah elemen berupa tanggal, bulan, dan tahun. Bentuk umum dalam mendefinisikan dan mendeklarasikan struktur adalah :

Struct nama_tipe_struktur

{

Tipe

filed1;

Tipe

field2;

Tipe

field3;

}variabel_struktur1….variabel_strukturM;

 TUGAS

1.    Program pangkat dengan array dimensi satu.

Script :

#include<stdio.h>

#include<iostream>

#include<conio.h>

using namespace std;

int main()

{

       int square[100]; // --> Array 1 dimensi dengan tempat yang dipesan sebanyak 100

       int i;

       int k;

      

       //Perhitungan

       for(i=0; i<10; i++) //angka yang ditampilkan 1-10

       {

                   k=i+1;

                   square[i]=k*k;

                   printf("\n Pangkat dari %d adalah %d", k, square[i]);

       }

       _getch();

}

Hasil Output :

LINKED LIST (SENARAI)

Istilah – istilah dalam linked list :

-          Simpul

Simpul terdiri dari dua bagian yaitu :

a.       Bagian data

b.      Bagian pointer yang menunjuk ke simpul berikutnya

-          First/Header

Variabel First/Header berisis alamat (pointer)/acuan (reference) yag menunjuk lokasi simpul pertama linked list, digunakan sebagai awal penelusuran linked list.

-          Nil/Null

Tidak bernilai, digunakan untuk menyatakan tidak mengacu ke manapun.

-          Simpul Terakhr (Last)

Simpul terakhir linked list berari tidak menunjuk simpul berikutnya. Tidak terdapat alamat disimpan di field pointer (bagian kedua dari simpul). Nilai null atau nil disimpan di field pointer di simpul terakhir.

   Jenis – jenis linked list :

         List kosong

List kosong hanya terdiri dari sebuah petujuk elemen yang berisi NULL (kosong), tidak memiliki satu buah elemen pun sehigga hanya berupa penunjuk awal elemn berisi NULL.

List Tunggal

List tuggal adalah list yang elemenya hanya menyimpan informasi elemen setelahnya (next), sehingga jalanya pengaksessan list hanya dapat dilakukan secara maju. List tuggal terbagi menjadi tiga jenis yaitu list tunggal dengan kepala (first), list tunggal kepala (first) dan ekor (tail), serta list tunggal yang berputar.

Gambar 2.2 List Tunggal dengan Kepala dan Ekor, List Tunggal Berputar

List Ganda

List ganda adalah sebuah list yang elemenya menyimpan informasi elemen sebelumnya dan informasi elemen setelahnya, sehingga proses penelusuan list dapat dilakukan secara maju dan mundur. List ganda terbagi menjadi tiga jenis yaitu list ganda engan kepala (first), list ganda dengan kepala (first) dan ekor (tail), serta list ganda yag berputar.

Gambar 2.3 List ganda dengan Kepala, List ganda dengan Kepala dan Ekor

 Operasi Dasar pada Linked List :

IsEmpty : Fungsi ini menentukan apakan linked list kosong atau tidak.

Size : operasi untuk mengirim jumlah elemen di linked list.

Create : operasi untuk penciptaan list baru yang kosong.

Insertfirst : operasi penyisipan simpul sebagai simpul pertama.

Insertafter : operasi untu penyisispan simpul setelah simpul tertentu.

Insertlast : operasi untuk penyisipan simpul sebagai simpul terakhir.

Insertbefore : operasi untuk penyisipan simpul sebelum simpul tertentu.

Deletefirst : operasi penghapusan simpul pertama.

Deleteafter : operasi penghapusan setelah simpul tertentu.

Deletelast : operasi penghapusan simpul terakhir.

TUGAS

1.    Contoh program sisip senarai (linked list).

Script :

#include<iostream>

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

using namespace std;

typedef struct nod

{

       int data;

       struct nod *next;

}NOD, *NODPTR;

void CiptaSenarai (NODPTR *s)

{

       *s = NULL;

}

NODPTR NodBaru(int m)

{

       NODPTR n;

       n = (NODPTR) malloc

       (sizeof(NOD));

       if (n !=NULL)

       {

                   n->data=m;

                   n->next=

                   NULL;

       }

       return n;

}

void SisipSenarai (NODPTR *s, NODPTR t, NODPTR p )

{

       if(p==NULL)

       {

                   t->next=*s;

                   *s=t;

       }

       else

       {

                   t->next=p->next;

                   p->next=t;

       }

}

void CetakSenarai(NODPTR s)

{

       NODPTR ps;

       for (ps=s; ps!=NULL; ps=ps->next)

                   printf("%d -->", ps->data);

                   printf("NULL\n");

}

int main()

{

       NODPTR pel;

       NODPTR n;

      

       CiptaSenarai(&pel);

       n=NodBaru(55);

       SisipSenarai(&pel, n, NULL);

      

       n=NodBaru(75);

       SisipSenarai(&pel, n, NULL);

       CetakSenarai(pel);

       _getch();

}

Hasil Output :

QUEUE (ANTRIAN)

Antrian adalah suatu kumpulan data yang penambahan elemenya hanya bisa dilakukan pada suatu ujung (disebut sisi belakang atau REAR), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut sisi depan atau FRONT). Prinsip yang digunakan dalam antrian ini adalah FIFO (First In First Out) yaitu elemen yang pertama kali masuk akan keluar pertama kalinya.

Penggunaan antrian antara lain simulasi antrian di dunia nyata (antrian pembelian tiket), sistem jaringan computer (pemrosesan banyak paket yang dating dari banyak koneksi pada host, bridge, gateway), dan lain-lain.

Gambar 4.1 Ilustrasi Antrian dengan 8 Elemen

Karakteristrik penting antrian sebagai berikut :

1. Elemen antrian yaitu item-item data yang terdapat dalam antrian.
2. Head/front (elemen terdepan antrian).
3. Tail/rear (elemen terakhir antrian).
4. Jumlah antrian pada antrian (count).
5. Status/kondisi antrian, ada dua yaitu :

-          Penuh

Bila elemen di antrian mencapai kapasitas maksimum antrian. Pada kondisi ini, tidak mungkin dilakukan penambahan ke antrian. Penambahan di elemen menyebabkan kondisi kesalahan Overflow.

-          Kosong

Bila tidak ada elemen antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

Operasi-operasi pokok pada antrian diantaranya adalah :

1. Create Membuat antrian baru.

NOEL(CREATE(Q))=0

            FRONT(CREATE(Q))=tidak terdefinisi

            REAR(CREATE(Q)=tidak terdefinisi

2. IsEmpty Untuk memeriksa apakah antrian sudah penuh atau belum.

ISEMPTY(Q)=True, jika Q adalah queue penuh.

3. IsFull Mengecek apakah antrian sudah penuh atau belum.

ISFULL(Q)=True, jika Q adalah queue penuh.

4. Enqueue/Insert Menambahkan elemen kke dalam antrian, penambahan elemen selalu ditambahkan di dalam elemen paling belakang.

REAR(INSERT(A,Q))=A

ISEMPTY(INSERT(A,Q))=FALSE

Algoritma QINSERT :

a.       IF FRONT = 1 AND REAR = N, OR IF FRONT = REAR +

1, THEN OVERFLOW, RETURN

b.      IF FRONT := NULL, THEN

SET FRONT := 1 AND REAR := 1

ELSE IF REAR = N,

THEN SET REAR := 1

ELSE

SET REAR := REAR+!

c.       SET QUEUE[REAR] := ITEM

d.      RETURN

5. Dequeu/Remove Unttuk menghapus elemen terdepan/pertama dari antrian.

Algoritma QDELETE :

a.       IF FRONT := NULL, THEN UNDERFLOW, RETURN

b.      SET ITEM := QUEUE{FRONT]

c.       [FIND NEW VALUE OF FRONT] IF FRONT = REAR, THEN

SET FRONT := NULL AND REAR

;=NULL ELSE IF FRONT = N, THEN

                  SET FRONT := 1

ELSE

                  SET FRONT := FRONT+!

d.      RETURN

Representasi Queue :

Representasi statis

Queue dengan representasi statis biasanya diimplementasikan dengan menggunakan array. Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka queue dengan representasi statis dalam mengalami kondisi elemen penuh. Ilustrasi queue dengan representasi statis dapat dilihat pada gambar :

Gambar 4.2 Representasi Queue Statis

Representasi dinamis

Queue dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori. Ilustrasi queue dengan representasi dinamis dapat dilihat pada gambar :

Gambar 4.3 Representasi Queue Dinamis

LEMBAR KERJA DAN TUGAS

1. Program Queue Stasis.

#include <queue>

#include <iostream>

#include <conio.h>

using namespace std;

int main()

{

            queue <int> que;

            que.push(10);

            que.push(2);

            que.push(3);

           

            cout<<"Paling depan : "<<que.front()<<endl;

            cout<<"Paling belakang : "<<que.back()<<endl;

           

            que.pop();

            cout<<"10 sudah dikeluarkan"<<endl;

            cout<<"Paling depan : "<<que.front()<<endl;

            cout<<"Paling belakang : "<<que.back()<<endl;

           

            que.push(6);

            cout<<"Angka 6 dimasukkan"<<endl;

            cout<<"Paling depan : "<<que.front()<<endl;

            cout<<"Paling belakang : "<<que.back()<<endl;

           

            _getch();

}

Output :