Struktur Data

PENGENALAN STRUKTUR DATA

DISUSUN OLEH

NAMA                                                                                                   NPM
RAMAD WIDODO                                                                           18111726
CITRA AYU RIMA MELATI                                                          11111671

JAENAL MUHAMAD YAMIN                                                       18111333                   

KELAS                       : 1KA18

MATA KULIAH       : ALGORITMA PEMROGRAMAN 2 C

TUGAS                       : PENGENALAN STRUKTUR DATA

UNIVERSITAS GUNADARMA
2012

 

Daftar Isi

Daftar Isi         …………………………………………………………  i

BAB I STRUKTUR DATA………………………………………………          1

1.PENGENALAN STRUKTUR DATA………………………………….          1

1.1        Struktur………………………………………...…………………          1

1.2        Data…………………………………………………………….. 1

1.3        Struktur Data……………………………………………………            2

1.4        Pembuatan Struktur Data……………………………………… 2

BAB II  Pengenalan linear List………………………………………… 4

1.Pengenalan Linear List………………………………………………  4

   BAB III PENGENALAN ARRAY…………………………………   5

1.      Pengertian Array…………………………………………………… 5

2.      Karakteristik Array………………………………………………… 5

3.1Deklarasi Array………………………………………………… 5

3.2  Jenis Array……………………………………………………  5

3.3. Operasi dasar pada aray……………………………………… 6

3.3.1. Penciptaan dan penghancuran…………………………  6

3.3.2. Penyimpanan dan pengambilan nilai………………….  7

3.3.3. Pemrosesan transversal………………………………… 7

3.4. Pengurutan Array………………………………………………            7

3.5 Keunggulan dan kelemahan array………………………………           8

BAB IV Pengenalan Linked list…………………………………………           9

1. Linked list ……………………………………………………………            9

4.1 operasi dasar pada linked list……………………………………… 9

4.2 menghapus suatu node pada linked list……………………………            9

4.3 menyisipkan suatu node kedalam likend list………………………            10

BAB V STACK………………………………………………………… 11

1.STACK……………………………………………………………       11

5.1  Prinsip Stack …………………………………………………     11

5.2   Operasi pada stack…………………………………………..

BAB VI  Queue……………………………………………………….   13

1.Queue ……………………………………………………………..      13

6.1  Operasi dasar pada Antrean ………………………………………         13

 

BAB I

STRUKTUR DATA

1.PENGENALAN STRUKTUR DATA

Sebelum mengenal lebih jauh apa itu struktur data. Sebaiknya kita harus tahu dahulu apa itu struktur dan data itu sendiri. 

1.1  Struktur

suatu susunan dan hubungan antara tiap bagian serta posisi dalam menjalankan kegiatan operasional untuk mencapai tujuan.

1.2  Data

Data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau ymbol.Pengertian data ini menyiratkan suatu nilai yang bisa dinyatakan dalam bentuk konstanta  / variable.

Konstanta digunakan untuk menyatakan nilai tetap sedangkan variable digunakan dalam program untuk menyatakan nilai yang dapat berubah-ubah selang eksekusi berlangsung.

Ada empat istilah data, yaitu:

1.      Tipe data adalah jenis atau macam data di dalam suatu variable dalam bahasa pemrograman.

2.      Objek data mengacu kumpulan elemen (domain).

3.      Representasi data : Suatu mapping dari struktur data) misalnya bolean di representasikan dalam 0 dan 1.

4.      Struktur data biasa dipakai untuk mengelompokan beberapa  informasi yang terkait menjadi sebuah kesatuan.

            Tipe data sederhana terbagi menjadi dua, yaitu:                  

1.      Data sederhana tunggal.     Misalnya : Integer, real , Boolean dan character.

2.      Data sederhana majemuk.  Misalnya : String.

1.3  Struktur Data

Struktur data adalah suatu koleksi / kelompok data yang dapat di karakteristikan oleh organisasi serta operasi yang di definisikan terhadapnya.Dalam teknik pemrograman,struktur data berarti tata letak 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.

Struktur data meliputi  :

1.      Struktur data sederhana, misalnya array.

2.      Struktur data majemuk, yang terdiri dari

Linier: Stack, Queue, serta List dan link list.

 Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang   lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana.

Struktur data standar yang biasanya digunakan dibidang informatika adalah :

1.      Array

2.      List linier (Linked List)

3.       List

4.      Stack (Tumpukan)

5.      Queue (Antrian)

1.4  Pembuatan Struktur Data

Untuk membuat menjadi struktur data, kita harus melakukan dulu aktivitas terhadap objek data, yaitu :

1.      Mendeskkripsikan kumpulan operasi sah yang diterapkan ke elemen-elemen objek data.

2.      Menunjukan mekanisme kerja operasi-operasi.

Tahap pembuatan struktur data adalah :

1.      Tahap pertama : Spesifikasi

Pendeskripsian / spesifikasi struktur data menyatakan apa yang dapat dilakukan struktur data, bukan cara penerapannya. Pendeskripsian ini melibatkan konvensi matematika untuk menyatakan sifat-sifat struktur data yang dikehendaki.

2.      Tahap kedua : Implementasi

Implementasi menyatakan cara penerapan struktur data dengan struktur data yang telah ada.Implementasi struktur data adalah proses pendefinisian tipe data abstrak sehingga semua operasi dapat dieksekusi computer. Implementasi struktur penyinpanan item-item data serta algoritma-algoritma untuk implementasi operasi-operasi sehingga menjamin terpenuhinya karakteristik struktur data, relasi item-item data

3.       Tahap ketiga : Pemrograman

Pemrograman terstruktur adalah penerjemahan menjadi pernyataan di bahasa pemrograman tertentu.

        Sesuai dengan relasi yang didefinisikan di spesifikasi perancangan harus memilih tipe-tipe data yang telah ada untuk merepresentasikan struktur data.Struktur data di bangun menggunakan fasilitas pembentukan atau pembuatan struktur data yang disediakan bahasa seperti array dan sebagainya atau yang telah di buat seperti stack, queue, atau himpunan menggunakan linked list.

Pembuatan struktur data adalah pembentukan tipe data lengkap yang mempunyai empat property berikut :

1.      Nama               : Identifier tipe data

2.      Domain            : Domain / himpunan semesta nilai di tipe data

3.      Konstanta (penyebutan anggota-anggotanya) : Cara penyebutan anggota-anggota tipe data

4.      Operasi-operasi terhadap tipe data itu (operator): Daftar operasi terhadap anggota tipe data sehingga kelakuan objek data sesuai spesifikasi.

BAB II

Pengenalan linear List

1.         Linear list adalah suatu struktur data yang merupakan himpunan terurut dari satuan data atau dari record.

Elemen yang terdapat dalam daftar disebut simpul/node.

Daftar disebut Linear karena elemen nampak seperti baris, bahwa setiap simpul (kecuali simpul pertama dan terakhir) selalu memiliki elemen penerus langsung (suksesor) dan elemen pendahulu langsung (predesor).

Misalnya didefinisikan suatu linear list A yang terdiri atas T buah elemen sebagai berikut :

A=[ a1,a2,……………, aT ]

Jika T = 0 , maka A dikatakan sebagai “Null List” (list hampa).

Suatu elemen dapat dihapus (delete) dari sembarang posisi pada linear list .

Suatu elemen baru dapat dimasukkan (insertion) kedalam list dan dapat menempati sembarang posisi pada list tersebut.

Jadi suatu linear list dapat berkurang atau bertambah setiap saat

Contoh : file merupakan linier list yang elemen-elemennya berupa record.

 

 BAB III

PENGENALAN ARRAY

1.      Pengertian Array

Array atau larik di definisikan sebagai pemesanan alokasi memory berurutan tetapi tidak selalu demikian. karena terjadi kerancuan antara struktur data dan representasinya. Memang benar array hampir selalu di implementasikan menggunakan memory berurutan tapi tidak selalu demikian.

Semua elemem array bertipe sama. Array cocok untuk organisasi kumpulan data homogen yang ukuran atau jumlah elemen maksimumnya telah diketahui dari awal. Homogen adalah bahwa setiap elemen dari sebuah array tertentu haruslah mempunyai tipe data yang sama.

2.      Karakteristik Array

Array mempunyai karakteristik sebagai berikut :

1.      Mepunyai batasan dari pemesanan alokasi memori (bersifat statis)

2.      Mempunyai tipe data sama (bersifat homogen)

3.      Dapat diakses secara acak

3.1  Deklarasi Array

Ada tiga hal yang harus di ketahui dalam mendeklarasikan array, yaitu :

1.      Type data array

2.      Nama variable array

3.      Subkrip / index array.

3.2  Jenis Array

1.      Array dimensi satu

Deklarasi         : Type_Data Nama_Variabel [index]

2.      Array dimensi dua

Deklarasi         : Type_Data Nama_Variabel [index1] [index2]

3.      Array dimensi tiga

Deklarasi         : type_Data Nama_Variabel [index1][index2][index3]

4.      Triangular array (array segitiga)

Triangular array dapat merupakan Upper Triangular (seluruh elemen di bawah diagonal utama = 0), ataupun Lower Triangular (seluruh elemen di atas diagonal utama = 0).

5.      Sperse(array jarang)

Suatu array yang sangat banyak elemen nol-nya.

3.3. Operasi dasar pada aray

Operasi terhadap elemen di array dilakukan dengan pengaksesan langsung. Nilai

di masing-masing posisi elemen dapat diambil dan nilai dapat disimpan tanpa melewati

posisi-posisi lain.

Terdapat dua tipe operasi, yaitu :

1. Operasi terhadap satu elemen / posisi dari array

2. Operasi terhadap array sebagai keseluruhan

Dua operasi paling dasar terhadap satu elemen / posisi adalah

1. Penyimpanan nilai elemen ke posisi tertentu di array

2. Pengambilan nilai elemen dari posisi tertentu di array

Operasi-operasi dasar terhadap array secara keseluruhan adalah :

1. Operasi penciptaan

2. Operasi penghancuran

3. Oparasi pemrosesan traversal

4. Operasi pencarian (table look-up)

5. Operasi sorting

3.3.1. Penciptaan dan penghancuran

Operasi penciptaan biasa disebut inisialisasi.

Operasi ini untuk mempersiapkan struktur data untuk operasi-operasi berikutnya.

Operasi penghancuran menyatakan ketidak berlakuan struktur data atau membebaskan memory, menyerahkan memory ke manajemen memory agar dapat di pergunakan keperluan lain.

Operasi penghancuran penting terutama bila struktur data di implementasikan secara dinamis menggunakan pointer

3.3.2. Penyimpanan dan pengambilan nilai

Biasanya bahasa pemrograman menyediakan sintaks tertentu untuk penyimpanan dan pengambilan nilai elemen pada posisi tertentu di array.

Contoh :

A[10] = 78, berarti penyimpanan nilai 78 ke posisi ke-10 dari array A

C = A[10], berarti pengambilan nilai elemen posisi ke-10 dari array A

3.3.3. Pemrosesan transvesal

Operasi pemrosesan transversal adalah pemrosesan mengolah seluruh elemen secara sistematik.

3.4. Pengurutan Array

            Pengurutan atau sorting adalah proses yang paling sering di lakukan dalam  pengolahan data.pengurutan di bedakan menjadi dua, yaitu :

1. Pengurutan internal

Pengurutan dilakukan terhadap sekumpulan data di media memory internal komputer dimana data dapat di akses elemennya secara langsung.

2. Pengurutan eksternal

Pengurutan data di memory sekunder. Biasanya data bervolume besar sehingga tidak mampu dimuat semuanya di memori utama.

3.5 Keunggulan dan kelemahan array

Keunggulan array adalah sebagai berikut :

1. Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat diacu secara langsung tanpa melalui elemen-elemen lain.
2. Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemen-

elemen tetangga, baik elemen pendahulu atau elemen penerus 3

3. Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga,

maka penggunaan penyimpanannya sangat efisien.

Kelemahan array adalah sebagai berikut :

Array mempunyai fleksibilitas rendah, sehingga tidak cocok untuk berbagai aplikasi  karena array mempunyai batasan sebagai berikut :

1. Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen

adalah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain

2. Kebanyakan bahasa pemrograman mengimplementasikan array statik yang sulit

diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi

terus-menerus, maka representasi statis

1.      Tidak efisien dalam penggunaan memori

2.       Menyiakan banyak waktu komputasi

3.      Pada suatu aplikasi, representasi statis tidak dimungkinkan

Bila penambahan dan pengurangan terjadi terus menerus, maka representasi statis (array):

1. Tidak efisien dalam penggunaan memory
2. Menyiakan banyak waktu komputasi
3. Pada suatu aplikasi, representasi statis tidak di mungkinkan.

BAB IV

Pengenalan Linked list

1.   Linked list (one  way  list) adalah suatu  kumpulan elemen  data (yang  disebut sebagai node) dimana  urutannya ditentukan  oleh  suatu pointer.

q  Setiap elemen  (node) dari  suatu linked list terdiri atas dua bagian, yaitu:

Ø  INFO berisi informasi tentang elemne data yang bersangkutan.

Ø  NEXT (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya     yang dituju.

4.1 OPERASI  DASAR PADA LINKED LIST

Ada beberapa  aturan yang didefinisikan pada operasi didalam linked list yaitu:

Ø Jika P adalah  suatu variabel pointer, maka nilainya  adalah alamat atau lokasi dari variabel lain yang  dituju.

Ø Operasi yang  didefinisikan  pada  suatu variabel pointer adalah:

1.                   Test apakah  sama dengan NULL

2.                   Test untuk kesamaan denganvariabel pointer lain

3.                   Menetapkan  sama dengan NULL

4.                   Menetapkan menuju ke node lain

 Notasi yang didefinisikan sehubungan dengan operasi diatas  adalah

1. NODE (P), artinya node yang  ditunjuk oleh pointer P
2. INFO (P), artinya  nilai INFO dari node yang ditunjuk pointer  P
3. NEXT (P), artinya  hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer

4.2 MENGHAPUS  SUATU NODE DARI LINKED LIST (REMOVE)

1. Untuk menghapus  node  dalam linked list digunakan procedure FREENODE.
2. Jika Q adalah suatu variabel  pointer, maka FREENODE (Q) akan  menyebabkan node  yang  ditunjuk oleh variabel poinnter Q dihapus  dalam linked list.

4.3 MENYISIPKAN  SUATU NODE KEDALAM LINKED LIST

1.      Untuk menyisipkan node dalam linked list digunakan procedure GETNODE

2. Jika NEW adalah suatu variabel pointer, maka GETNODE (NEW) akan menyebabkan node yang  ditunjuk oleh  variabel pointer NEW disisipkan kedalam linked list.

3.      Perhatikan linked list berikut:

Procedure Getnode (NEW)

            If Avail = Null

            Then out-of-free-space

(a)    else begin

Getnode := Avail

(b)   Avail := Next (Avail)

(c)          Next (Getnode) := Null;

End;

Algoritma menyisipkan sebuah node :

(a)        Getnode (NEW)

(b)        Info (NEW) := Name;

(c)          Q := Next (P)

(d)         Next (P) := NEW

(e)          Next (NEW) := Q

BAB V

STACK

1.         STACK adalah suatu bentuk khusus dari linear list di mana operasi  penyisipan  dan penghapusan atas elemen-elemennya hanya dapat dilakukan pada satu sisi saja yaitu posisi akhir dari list. Posisi ini disebut puncak atau disebut sebagai “TOP(S)”.

5.1     Prinsip Stack

Prinsip stack sebagai berikut :

1.   Prinsip Stack adalah LIFO ( Last In First Out ) atau Terakhir masuk pertama keluar.

2.   Setiap elemen tidak dapat dikeluarkan (POP keluar) sebelum semua elemen diatasnya dikeluarkan.

3.   Elemen teratas (puncak) dari stack dinotasikan sebagai TOP(S)

Misal diberikan stack S sebagai berikut :

S= [ S2,S2,………, ST ] è maka TOP(S) = ST

4.   Untuk menunjukkan  jumlah elemen suatu stack digunakan notasi NOEL(S).

Dari stack diatas  maka NOEL(S) = T.

NOEL(S) menghasilkan nilai integer.

5.2  Operasi pada stack

1.      CREATE (STACK)

2.      ISEMPTY (STACK)

3.      PUSH (ELEMEN, STACK)

4.      POP (STACK)

Keterangan :

1.      CREATE(S)

Operator ini berfungsi untuk membuat sebuah stack kosong (menjadi hampa) dan didefinisikan bahwa

      NOEL (CREATE (S)) = 0 dan

TOP (CREATE(S)) = null / tidak terdefinisi

2.      ISEMPTY(S)

Operator ini berfungsi  untuk menentukan apakah suatu stack adalah stack kosong (hampa) atau tidak . Operasinya akan bernilai boolean dengan definisi sebagai berikut :

ISEMPTY(S) = true, jika S adalah stack kosong atau NOEL(S) = 0

                                  False, jika S bukan stack kosong atau NOEL(S) ¹ 0

Catatan : ISEMPTY(CREATE(S)) = true

3.      PUSH(E,S)

1.      Operator ini berfungsi untuk menambahkan satu elemen ke dalam stack . Notasi yang digunakan adalah  PUSH(E,S)

                  Artinya : menambahkan elemen E ke dalam stack S

2.      Elemen yang baru masuk ini akan menempati posisi TOP jadi TOP(PUSH(E,S)) = E

3.      Akibat dari operasi ini jumlah elemen dalam stack akan bertambah, artinya NOEL (S) menjadi lebih besar atau stack menjadi tidak kosong (ISEMPTY(PUSH(E,S)) = false )

4.      POP(S)

1.      Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack, notasinya POP(S)

2.      Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi TOP.

3.      Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang 1 dan elemen pada posisi TOP akan berubah.

4.      Operator ini tidak dapat digunakan pada stack kosong, artinya POP(CREATE(S)) = error condition dan

5.      POP(PUSH(E,S)) = S

6.      Catatan : TOP(PUSH(E,S)) = E

              BAB VI

Queue

1.   Queue

Adalah suatu bentuk khusus dari linear list dengan operasi penyisipan (insertion) hanya pada salah satu sisi ( Rear/ belakang) dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya (Front/ depan) dari list.

Antrean   Q  = [ Q1, Q2, Q3,……….., QT]

            Front(Q) = bagian depan dari antrean Q

            Rear(Q)  = bagian belakang dari antrean Q

            Noel(Q)  = Jumlah elemen di dalam antrean ( berharga integer)

            Jadi :  Front(Q) = QT

                      Rear(Q) = Q1

                      Noel(Q) = T

Antrean beroperasi secara FIFO ( First In First Out) yang pertama masuk, yang pertama keluar.

6.1  Operasi dasar pada Antrean :

1.      CREATE(Q)

Operator untuk membentuk suatu antrean hampa

Q = [,…….,]

NOEL(CREATE(Q)) = 0

FRONT(CREATE(Q)) = tidak didefinisikan

REAR(CREATE(Q)) = tidak didefinisikan

2.      ISEMPTY(Q)

Operator yang menentukan apakah antrean Q hampa atau tidak.

Operand dari operator ISEMPTY adalah antrean.

Hasilnya bertipe data Boolean

ISEMPTY(Q) =TRUE   jika Q adalah antrean hampa (NOEL(Q) = 0)

                              FALSE jika Q bukan antrean kosong (NOEL(Q) ¹ 0)

3.      INSERT(E,Q)

Operator yang menyisipkan elemen E ke dalam antrean Q

Catt :          Elemen Q ditempatkan pada bagian belakang antrean dan antrean menjadi lebih panjang

Q = [ A, B, C, D]

REAR(INSERT(E,Q)) = E

FRONT(Q) = A

NOEL(Q) = 5

ISEMPTY(INSERT(E,Q)) = FALSE

4.      REMOVE(Q)

Operator yang menghapus elemen bagian depan dari antrean Q dan antrean menjadi lebih pendek

Jika   NOEL(Q) = 0 maka

REMOVE(Q) = ERROR ( UNDERFLOW)