MAKALAH STRUKTUR DATA

 

KATA PENGANTAR

Puji syukur kepada Tuhan yang Maha Esa kiranya telah diberikan kesehatan dan pembelajaran sehingga penyusunan makalah ini telah selesai berkat pertolongan Tuhan dan kerja keras.Dan kepada Bapak Dosen Algoritma saya mengucap syukur sebesar besarnya kiranya telah diberikan pelajaran algoritma hingga kami dapat berpikir dengan matang karena penyusunan makalah ini kami bias bekerja sama antara sesama mahasiswa hingga kami dapat berbagi ilmu.

            Semoga makalah ini dapat berguna pada pada teman-teman mahasiswa tanpa doa teman-teman mungkin makalah ini belum selesai.Saya berterima kasih atas bantuannya tanpa kalian mungkin makalah ini tidak selesai.

            Mungkin makalah ini jauh diatas sempurna,jadi kami mohon maaf jika ada kesalahan penulisan atau kurang berkenan dihati saudara kami mohon maaf atas kesalahan tersebut. Dan semoga makalah ini membuat ilmu kita bertambah,kami berterimakasih kepada Bapak dosen algoritma beserta teman-teman mahasiswa.

 

            PENULIS

SUDARSONO SIHATANG

DAFTAR  ISI

Kata Pengantar………………………………………………………………………………….……….1

Daftar Isi…………………………………………………………………………………………………….2

BAB I

DATA DAN STRUKTUR DATA

1.Pengertian Data……………………………………………………………………………………….4

2.Pengertian Struktur Data…………………………………………………………………..…….8

            2.1.Pembuatan Struktur Data………………………………………………………….9

BAB II

ARRAY

1.Pengertian Array………………………………………………………………………….…………11

2.Karakteristik Array………………………………………………………………………………….11

            2.1.Deklarasi Array…………………………………………………………………………11

            2.2.Jenis Array………………………………………………………………………………..11

            2.3.Operasi Dasar Pada Array………………………..……………………………….15

Kesimpulan…………………………………………………………….………………………………….18

BAB I

DATA DAN STRUKTUR DATA

1.PENGERTIAN 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 simbol.

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:

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

Objek data mengacu kumpulan elemen, D (domain).

Representasi data : Suatu mapping dari struktur data ‘d’ ke suatu set ke struktur data ‘e’ (d===e) misal bolean di representasikan dalam 0 dan 1.

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

Tipe data sederhana terbagi menjadi dua, yaitu:

 Data sederhana tunggal.        Misalnya : Integer, real / float, Boolean dan character.

 Data sederhana majemuk.     Misalnya : String.

1.TIPE DATA SEDERHANA TUNGGAL

INTEGER:

Anggota dari himpunan bilangan :

{..., -(n+1), -n, ..., -2, -1, 0, 1, 2, ..., n, n+1, ...}

Operasi dasar yaitu : penjumlahan, pengurangan, perkalian, pembagian dan perpangkatan

REAL

Data numerik yang bukan termasuk integer, digolongkan dalam jenis data real.   Ditulis menggunakan titik desimal (atau koma desimal).  Dimasukkan ke dalam memori komputer memakai sistem floating point,  disebut Scientific Notation. 

Penyajiannya terdiri dari : mantissa (pecahan) dan eksponen.

Contoh :

Di dalam sistem desimal, 123000 = 0.123 * 10⁶

di sini 0.123 adalah mantissa atau pecahan, sedangkan 6 adalah eksponennya.

Secara umum suatu bilangan real X dituliskan M * R^E

di sini : M dijadikan pecahan, R adalah radixnya dan E merupakan eksponennya.

BOOLEAN

Disebut juga jenis data logical.  Anggota { true atau false}.

 Operator Logika, yaitu : AND, OR, NOT

 Operator AND akan menghasilkan nilai true, jika kedua operand bernilai true.

 Operator OR akan menghasilkan nilai true, jika salah satu operand bernilai true

 Operator NOT merupakan “precedence” dari operator AND dan OR.

Dalam suatu ekspresi yang tidak menggunakan tanda kurung, operator NOT harus dievaluasi sebelum operator AND dan OR.

B. Operator Relasional, yaitu : >, <, >=, <=, <> dan =

            Contoh : 6  < 8 = True

                   9  < 8 = False

KARAKTER

Elemen dari suatu himpunan yang terdiri atas bilangan, abjad dan simbol khusus.

(0,1,...,8,9, A, B, ..., Y,Z, +, -,*,Ö, ...}

Ada banyak skema yang digunakan untuk merepresentasikan karakter dalam storage. Pada umumnya skema yang paling banyak digunakan adalah :

1. Extended Binary Coded Decimal Interchange (EBCDIC)

            Digunakan kode 8 bit untuk menyatakan sebuah karakter. Jika dihitung, kemungkinan kombinasi seluruhnya : 2⁸ = 256.

2. American Standard Code for Information Interchange (ASCII)

            Digunakan kode 7 bit untuk menyatakan sebuah karakter. Jika dihitung, kemungkinan kombinasi seluruhnya : 2⁷ = 128.

2.TIPE DATA MAJEMUK

STRING

Barisan hingga karakter yang dibentuk oleh suatu kumpulan dari karakter.

Karakter yang digunakan untuk membentuk suatu string disebut alfabet. Dalam penulisannya, suatu string berada dalam tanda “aphosthrope”.

Contoh :

Misal diberikan himpunan alfabet A = {C,D,1}.

String yang dapat dibentuk dari alfabet di atas di antaranya : ‘CD1’,’CDD’,’DDC’,’CDC1’,... dan sebagainya, termasuk “null string” atau “empty string”

Himpunan tak hingga dari string yang dibentuk oleh alfabet A disebut VOCABULARY, Notasi : V_A  atau A*

Jika suatu string dibentuk dari alfabet {0,1}, maka string yang terbentuk disebut dengan “Bit String”.

OPERASI	Operator
Jumlah karakter dalam string	LENGTH
Gabungan 2 buah string	CONCAT
Sub bagian dari string	SUBSTR
Menyisipkan string ke dalam string yang lain	INSERT
Menghapus karakter dalam string	DELETE

LENGTH

Nilai dari operasi ini adalah suatu integer yang menunjukkan panjang dari suatu string .

Notasi : LENGTH(S) = N (integer)

                di sini S = String, N = integer

CONCAT

Operasi ini bekerja terhadap dua string dan hasilnya merupakan resultan dari kedua string tersebut.

Jika S₁ dan S₂ masing-masing adalah suatu string, maka bentuk operasi CONCATENATION dinotasikan dengan : CONCAT(S₁, S₂).

Contoh :          

Misal S₁ = ‘a₁a₂ ... a_N’ dan  S₂  =‘b₁b₂ ... b_M’

Maka CONCAT(S₁,S₂) = ‘a₁a₂ ... a_Nb₁b₂ ... b_M’

String S₁ = "Sistem"

String S₂ = "Informasi"

CONCAT(S₁, S₂)= "SistemInformasi"

LENGTH(CONCAT(S₁, S₂)) = 15

LENGTH(S₁)  + LENGTH(S₂) = LENGTH(CONCAT(S₁, S₂))

            6              +                  9           =                     15

                                    15                    =                     15

SUBSTR

Operasi ini adalah operasi membentuk string baru, yang merupakan bagian dari string yang diketahui.

Notasi :            SUBSTR(S, i, j)

di sini : S = string yang diketahui

                     i dan j = integer

                  i = posisi awal substring 1 £  i  £  LENGTH(S)

                  j = banyak karakter yang diambil

                  0 £  j  £  LENGTH(S) dan 0 £  i+j-1  £  LENGTH(S)

INSERT

Operasi ini adalah untuk menyisipkan suatu string ke dalam string lain.

Bentuk umumnya adalah : 

INSERT(S₁,S₂,i). S₁  dan S₂ masing-masing adalah suatu string dan i adalah posisi awal S₂ pada S₁.

Contoh :          

Misalkan : S₁  = ‘a₁a₂ ... a_N’

                    S₂  = ‘b₁b₂ ... b_M’

                    INSERT(S₁, S₂,3) = ‘a₁a₂b₁b₂ ... b_Ma₃a₄... a_N’

String S₁ = "Sistem"

String S₂ = "Informasi"

INSERT(S₁,S₂,4) = “SisInformasitem”

INSERT(S₂,S₁,4) = “InfSistemormasi”

DELETE

Operasi ini digunakan untuk menghapus sebagian karakter dalam suatu string.

Bentuk umumnya adalah :

DELETE(S,i,j) ® menghapuskan sebagian karakter dalam string S, mulai dari posisi i dengan panjang j.

Contoh :          

Diberikan string S = ‘a₁a₂ ... a_N’

DELETE(S,3,4) = ‘a₁ a₂ a₇a₈ ... a_N’

String S  = "Sistem Informasi"

            i = 4, j = 9

            DELETE(S,i,j) = “Sismasi”

            DELETE(S,j,i) = “Sistem Imasi”

String S = “SistemInformasi”

            DELETE(S, 4, 5) = “Sisformasi”

            DELETE(S, 5, 4) = “Sistformasi”

2. PENGERTIAN 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  :

 Struktur data sederhana, misalnya array dan Record.

Struktur data majemuk, yang terdiri :

 Linier               : Stack, Queue, serta List dan Multilist

 Non Linier       : Pohon Biner dan Graph

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 :

 ADT , Array , Struk

 List linier (Linked List) dan variasinya

 Multilist

 Stack (Tumpukan)

 Queue (Antrian)

 Tree ( Pohon )

 Graph ( Graf )

2.1 PEMBUATAN STRUKTUR DATA

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

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

Menunjukan mekanisme kerja operasi-operasi.

Objek data integer ditambah operasi (+ , - , * , / , mod ,cell , floor , < , >) dan operasi-operasi lain yang memanipuasi objek data integer menyatakan struktur data.

Struktur data = Objek data + { Operasi manipulasi }.

Tahap pembuatan struktur data adalah :

 Tahap pertama         : Spesifikasi

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

Spesifikasi dapat dilakukan dengan dua cara, yaitu :

-          Spesifikasi secara formal

-          Spesifikasi secara informal

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 atau invariant pada struktur data itu.

Tahap ketiga : Pemrograman

Pemrograman terstruktur adalah penerjemahan menjadi pernyataan di bahasa pemrograman tertentu. Prosesnya terdiri dari :

Deklarasi yang mendefinisikan objek-objek data dan hubungannya…

Pembuatan prosedur / rutin untuk operasi-operasi dasar yang menjaga invariant pada struktur data itu .

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, record, 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 :

Nama  : Identifier tipe data

Domain           : Domain / himpunan semesta nilai di tipe data

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

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

BAB II

ARRAY

1. PENGERTIAN

            Array atau larik di definisikan sebagai pemesanan alokasi memory berurutan.definisi ini kurang tepat, 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

 Mepunyai batasan dari pemesanan alokasi memori (bersifat statis)

 Mempunyai tipe data sama (bersifat homogen)

 Dapat diakses secara acak.

2.1. DEKLARASI ARRAY

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

 Type data array

 Nama variable array

 Subkrip / index array.

Contoh deklarasi dari array adalah sebagai berikut :

int A[5] ; artinya variabel A adalah kumpulan data sebanyak 5 bilangan bertipe

integer.

2.2. JENIS ARRAY

1.ARRAY DIMENSI SATU

Deklarasi         : Type_Data Nama_Variabel [index]

Rumus untuk menentukan jumlah elemen dalam array adalah :

	n p (Index Array) i = 1

 

p = Perkalian dari index sebelumnya (untuk arraybdimensi dua dan tiga).

PEMETAAN (MAPPING) ARRAY DIMENSI SATU KE STORAGE

Rumus             :  @A[i] = B + (i – 1) * L

Dimana           :  @A[i]            :  Posisi array yang dicari

                                    B          :  Posisi awal index di memori computer

                                    i           :  Subkrip atau index array yang di cari

                                    L          :  Ukuran atau besar memori suatu tipe data

Contoh bentuk Array menggunakan c++

include<iostream>

using namespace std;

void main(void)

{

      int x[10]={0,1,2,3,4,5,6,7,8,9};

      int *px;

      int i;

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

      {

      px=&x[i]; // membaca alamat dari x

      cout<<x[i] << " " <<*px<<" "<<px<<endl;

      }

      {

            cout<<"1.NAMA               :SUDARSONO"<<endl;

            cout<<"2.NIM                :2010140119"<<endl;

            cout<<"3.SEMESTER           :IIIA"<<endl;

            cout<<"4.TANGGAL PRAKTIKUM  :23-03-2011"<<endl;

}

#include<iostream>

#include<conio.h>

using namespace std;

void main(void)

{

      int billy [5] = {16,2,77,40,12017};

      int n, result=0;

      for( n=0 ; n<5 ; n++ )

            {

            result += billy[n];

            }

            cout<<"Outputnya:"<<endl;

            cout<<result<<endl<<endl;

            cout<<"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:"<<endl;

            cout<<"Nama              : SUDARSONO SIHOTANG:"<<endl;

            cout<<"SEMESTER          : IIIA:"<<endl;

            cout<<"Tanggal praktikum : kamis-1/04/2011:"<<endl;

            cout<<"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:"<<endl;

            getch();

}

2.ARRAY DIMENSI DUA

Deklarasi         : Type_Data Nama_Variabel [index1] [index2]

            Menentukan jumlah elemen dalam array dimensi dua :

	n p (Index Array) i = 1

 

p = Perkalian dari statemen sebelumnya

PEMETAAN (MAPPING) ARRAY DIMENSI DUA KE STORAGE

Terbagi dua cara pandang (representasi) yang berbeda :

·         Secara kolom per kolom (coloumn major order / CMO)

	@M[i][j] = M[0][0] + {(j – 1) * K + (i – 1)} * L

 

·         Secara baris per baris (row major order / RMO)

	@M[i][j] = M[0][0] + {(i – 1) * N + (j – 1)} * L

 

Keterangan     :

@M[i][j] = Posisi array yang di cari, M[0][0 = Posisi alamat awal index array, i = Baris, j = Kolom, L = Ukuran memory type data, K = Banyaknya elemen per kolom, N = Banyaknya elemen per baris.

3. ARRAY DIMENSI TIGA

Adalah suatu array yang setiap elemennya merupakan tipe data array juga yang merupakan array dimensi dua.

Contoh :

Penyajian data mengenai banyaknya mahasiswa dari 20 perguruan tinggi di Jakarta, berdasarkan tingkat (1 sampai 5), dan jenis kelamin (pria atau wanita). Misalkan array tersebut dinamakan MHS. Ambil subskrip pertama, tingkat = 1, 2, ..., 5; subskrip kedua, jenis kelamin (pria = 1, wanita = 2), dan subskrip ketiga, perguruan tinggi adalah K = 1, 2, ..., 20. Jadi MHS(4,2,17) menyatakan jumlah mahasiswa tingkat 4, wanita, dari perguruan tinggi 17.

CROSS SECTION (Penampang Array Berdimensi-2)

Adalah pengambilan salah satu subskrip.

Misal :            Baris               =          tetap/konstan

           Kolom =          berubah-ubah (*)

Contoh :        B(*,4) =          semua elemen pada kolom ke-4.

                        B(2,*) =          semua elemen pada baris ke-2.

Pengertian cross-section pada array dimensi banyak, adalah sama seperti pada array dimensi dua.

Misal :

MHS(4,*,17)    =          jumlah mahasiswa tingkat 4 dari perguruan tinggi 17 (masing-masing untuk pria dan wanita).

MHS(*,*, 3)    =          jumlah mahasiswa untuk masing-masing tingkat, pria dan wanita, dari perguruan tinggi 3.

2.3. OPERASI DASAR PADA ARRAY

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 :

 Operasi terhadap satu elemen / posisi dari array

 Operasi terhadap array sebagai keseluruhan

Dua operasi paling dasar terhadap satu elemen / posisi adalah

 Penyimpanan nilai elemen ke posisi tertentu di array

 Pengambilan nilai elemen dari posisi tertentu di array

Operasi-operasi dasar terhadap array secara keseluruhan adalah :

 Operasi penciptaan

 Operasi penghancuran

 Operasi pemrosesan traversal

 Operasi pencarian (table look-up)

 Operasi sorting

.2.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

2.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

2.3.3. PEMROSESAN TRANSVERSAL

Operasi pemrosesan transversal adalah pemrosesan mengolah seluruh elemen secara sistematik.

2.3.4. PENCARIAN DI ARRAY (table look-up)

Pencarian di array (table look-up) adalah proses pencarian suatu nilai di array. Klasifikasi pencarian di array adalah :

1)      Pencarian sekuen (sequential searching),yaitu:

                                i.            Tanpa Boolean, terbagi:

·         Tanpa sentinen

·         Dengan sentinen

                              ii.            Menggunakan boolean

2)      Pencarian secara biner / dikotom (binary = dichotomy searching).

2.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. 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

• Tidak efisien dalam penggunaan memori

• Menyiakan banyak waktu komputasi

• 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.

KESIMPULAN

Struktur data merupakan salah satu bahan dasar pembuatan program. Pemakaian struktur data yang tepat di dalam proses pemrograman, akan menghasilkan algoritma yang jelas dan tepat sehingga menjadikan program secara keseluruhan lebih sederhana. Array merupakan bagian dari struktur data yaitu termasuk kedalam struktur data sederhana yang dapat di definisikan sebagai pemesanan alokasi memory sementara pada komputer. Apabila kita membuat program dengan data yang sudah kita ketahui batasnyamaka kita menggunakan Array (type data statis), namun apabila datanya belum kita ketahui batasnya maka gunakan pointer (type data dinamis).