BAB I
PENDAHULUAN
AA. Latar belakang
Pemograman dalam struktur data ada beberapa macam. Salah satunya adalah pemograman C++. Dalam pemograman ini biasanya menggunakan variable Array, Struktur dan Linked List
Makalah ini membahas tentang 3 variabel tersebut dimana ketiga variable mempunyai ciri dan umum yang berbeda sesuai dengan tipe file yang di gunakan pembaca. Seperti array yang menggunakan satu dimensi dan dua dimensi serta 3 dimensi dimana sangat berbeda dengan struktur yang menggunakan tingkatan prosedur.
Pemograman ini merupakan pemograman yang berbeda dari pemograman lainnya misalnya VB, Delphi atau Pascal namun perbedaan juga tidak begitu signifikan pada pemograman pascal.
Makalah ini membahas tentang 3 variabel tersebut dimana ketiga variable mempunyai ciri dan umum yang berbeda sesuai dengan tipe file yang di gunakan pembaca. Seperti array yang menggunakan satu dimensi dan dua dimensi serta 3 dimensi dimana sangat berbeda dengan struktur yang menggunakan tingkatan prosedur.
Pemograman ini merupakan pemograman yang berbeda dari pemograman lainnya misalnya VB, Delphi atau Pascal namun perbedaan juga tidak begitu signifikan pada pemograman pascal.
BAB II
STRUKTUR DATA
A. PENGERTIAN
Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.
Dalam teknik pemograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap.
Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.
BB.Daftar struktur data umum
1. Record
Record (basis data) merupakan kumpulan dari elemen-elemen data yang terkait dalam sebuah basis data. Secara ringkas, database dapat dikatakan sebagai sebuah tabe yang memiliki baris alias record dan kolom atau field.
Setiap baris menyatakan elemen-elemen data yang saling berkaitan. Sebagai contoh dalam suatu tabel memiliki kolom nama, alamat, tanggal lahir, pekerjaan. Maka satu record adalah data sau orang yang terdiri atas nama, alamat, tanggal lahir dan pekerjaan.
a. Larik
Larik (B.Inggris: array), dalam ilmu komputer, adalah suatu tipe data terstruktur yang dapat menyimpan banyak data dengan suatu nama yang sama dan menempati tempat di memori yang berurutan (kontigurasi) serta bertipe data sama pula.
Larik dapat diakses berdasarkan indeksnya. Indeks larik umumnya dimulai dari 0 dan ada pula yang dimulai dari angka bukan 0. Pengaksesan larik biasanya dibuat dengan menggunakan perulangan (looping).
ü Larik Satu Dimensi
Larik satu dimensi merupakan jenis larik dasar dan jenis larik yang paling sering digunakan, pemakaian larik satu dimensi terutama dipakai dalam tipe data string (terutama dalam bahasa Bahasa Pemograman C).
ü Larik Dua Dimensi
Larik dua dimensi merupakan tipe larik yang lain. Larik dua dimensi sering dipakai untuk merepresentasikan tabel dan matriks dalam pemrograman.
ü Larik dalam beberapa bahasa pemrograman
1. Bahasa Pascal
Larik dalam bahasa Pascal dapat didefinisikan dengan indeks awal dan indeks akhirnya.
Contoh:
program larik;
var arr: array[1..10] of integer; //larik dengan indeks awal 1 dan indeks akhir 10
begin
arr[1] := 5; //memasukkan nilai ke indeks 1
writeln(arr[i]); //mencetak angka 5
end.
a. Bahasa C
Larik dalam bahasa C selalu dimulai dari indeks 0. Larik dapat didefinisikan secara statik atau dinamik. Jika didefinisikan statik, ukuran larik akan tetap dari awal program hingga akhir program. Jika didefinisikan dinamik, ukuran larik dapat berubah selama program berjalan karena memesan tempat pada memori heap. Proses pemesanan tempat pada memori disebut dengan alokasi. Sedangkan proses pembebasan memori yang sudah dipesan disebut dengan dealokasi
Contoh larik statik:
#include <stdio.h>
int main(){int arr[10]; //indeks awal 0 dan indeks akhir 9
arr[0] = 5;
printf("%d\n", arr[0]);}
Contoh larik dinamik:
#include <malloc.h>
int main(){
int * arr;
arr = (int *) malloc(10 * sizeof(int)); //memesan 10 tempat pada memori
arr[0] = 5;
free(arr); //menghancurkan larik. Memori pada heap dibebaskan
arr = (int *) malloc(5 * sizeof(int)); //memesan 5 tempat baru pada memori
free(arr); //di akhir program jangan lupa untuk menghancurkan larik dinamik.
b. Bahasa Java
Dalam bahasa Java tipe data larik direpresentasikan sebagai sebuah objek khusus. Karena itu pada bahasa Java larik yang dibuat selalu bersifat dinamik. Namun walaupun bersifat dinamik, larik pada bahasa Java tidak perlu dihancurkan karena proes penghancuran dilakukan secara otomatis melalui suatu prosedur yang disebut dengan Pengumpulan Sampah (Inggris: Garbage Collecting).
Sama seperti bahasa C, indeks larik selalu dimulai dari 0.
Contoh:
public class larik { public static void main(String args[]) {
int[] arr = new arr[10];
arr[0] = 5;
System.out.println(arr[0]); } }
c. PHP
Sama seperti di JAVA larik di PHP juga merupakan sebuah object lebih tepatnya lagi map terorder. Ada dua tipe larik di PHP, indexed array (simple array) dan associated array (key=>value array). Di PHP, element larik bisa berupa string, Bilangan, boolean, dan semua tipe data primitive lainnya, termasuk larik juga bisa menjadi element larik lainnya.
Cara medefinisikan larik:
#mendefinisikan array kosong
$larik = array();
Contoh indexed array (simple array):
$jam = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);
$hari = array('senin', 'selasa', 'selasa', 'rabu', 'kamis', 'jumat', 'sabtu');
Contoh associated array:
$bulan = array('1'=>'January', '2'=>'February', '3'=>'Maret', '4'=>'April');
$komponenKalender = array(
'bulan'=> array(1, 2, 3, 4, 5, 6, 7, 8, 9 ,10 , 11, 12),
'hari' => array('senin', 'selasa', 'selasa', 'rabu', 'kamis', 'jumat', 'sabtu'));
2. List ( struktur data )
Pada tutorial ini, akan dibahas mengenai struktur data List, khususnya list linier.
Berdasarkan buku yang saya baca, yaitu(Diktat Struktur Data,oleh Inggriani Liem), list linier adalah sekumpulan elemen bertipe sama (seperti array), yang mempunyai keterurutan tertentu, dan setiap elementnya terdiri dari dua bagian, yaitu informasi elemen dan alamat suksesornya(next elemennya).
Berdasarkan buku yang saya baca, yaitu(Diktat Struktur Data,oleh Inggriani Liem), list linier adalah sekumpulan elemen bertipe sama (seperti array), yang mempunyai keterurutan tertentu, dan setiap elementnya terdiri dari dua bagian, yaitu informasi elemen dan alamat suksesornya(next elemennya).
Keuntungan dari menggunakan list antara lain:
-penggunaan memori yang dinamik, sehingga penggunaan memori dapat diatur untuk menghematnya
-kesederhanaan pada proses insert ataupun delete suatu elemen
-penggunaan memori yang dinamik, sehingga penggunaan memori dapat diatur untuk menghematnya
-kesederhanaan pada proses insert ataupun delete suatu elemen
Alamat elemen pertama dari suatu list L, dapat diacu dengan First(L).
Nilai yang dibawanya dapat diacu dengan info(P)
Nilai yang dibawanya dapat diacu dengan info(P)
Jadi, menurut saya, sebenarnya List tuh sama aja dengan array biasa, tapi alokasi memori dari tiap elemennya adalah secara dinamik dan suksesor dari suatu elemen cukup fleksibel, dapat kita tentukan sendiri.
Berikut ini contoh sederhana, implementasi List di C:
Source code-nya dibagi menjadi 3 file, yaitu file header(.h),implementasi(.c), dan driver-nya(.c)
Source code-nya dibagi menjadi 3 file, yaitu file header(.h),implementasi(.c), dan driver-nya(.c)
Berikut ini adalah source code untuk header-nya
/* by: darkkhuwarizmi
namafile: list1.h
deskripsi: mendefinisikan tipe data list
*/
namafile: list1.h
deskripsi: mendefinisikan tipe data list
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
#define Nil NULL
/* Selektor */
#define info(P) (P)->info
#define next(P) (P)->next
#define First(L) ((L).First)
#define info(P) (P)->info
#define next(P) (P)->next
#define First(L) ((L).First)
typedef int infotype;
typedef struct tElmtlist *address;
typedef struct tElmtlist{
infotype info;
address next;
}ElmtList;
typedef struct tElmtlist *address;
typedef struct tElmtlist{
infotype info;
address next;
}ElmtList;
/* Definisi List */
/* List Kosong : First(L) = Nil */
/* Setiap elemen dengan address P dapat diacu info(P), next(P) */
/* List Kosong : First(L) = Nil */
/* Setiap elemen dengan address P dapat diacu info(P), next(P) */
/* Elemen terakhir list: jika addressnya last, maka Next(last) = Nil */
typedef struct{
address First;
}List;
typedef struct{
address First;
}List;
//Prototipe fungsi-fungsi
void CreateList(List* L);
//membuat list kosong
//membuat list kosong
address Alokasi(infotype x);
//mengalokasikan memori, serta mengisikan x sebagai info-nya
//mengalokasikan memori, serta mengisikan x sebagai info-nya
void Dealokasi(address P);
void InsertFirst(List* L,infotype x);
//menambahkan elemen x list L, sebagai elemen pertama
//menambahkan elemen x list L, sebagai elemen pertama
void DelFirst(List* L,infotype* x);
//menghapus elemen pertama dari list L, dan menyimpan info dari elemen yang dihapus tersebut di x
//menghapus elemen pertama dari list L, dan menyimpan info dari elemen yang dihapus tersebut di x
void printList(List L);
//menampilkan isi dari list
//menampilkan isi dari list
File di atas disimpan dengan nama list1.h
Kemudian, file realisasinya:
Kemudian, file realisasinya:
/* by: darkkhuwarizmi
namafile: list1.c
deskripsi: realisasi dari tipe data list
*/
namafile: list1.c
deskripsi: realisasi dari tipe data list
*/
#include “list1.h”
void CreateList(List* L)
//membuat list kosong
{
First(*L) = Nil;
}
//membuat list kosong
{
First(*L) = Nil;
}
address Alokasi(infotype x)
//mengalokasikan memori, serta mengisikan x sebagai info-nya
{
address temp = Nil;
temp = (address)malloc(sizeof(ElmtList));
if (temp!=Nil){
info(temp) = x;
}
return temp;
}
//mengalokasikan memori, serta mengisikan x sebagai info-nya
{
address temp = Nil;
temp = (address)malloc(sizeof(ElmtList));
if (temp!=Nil){
info(temp) = x;
}
return temp;
}
void Dealokasi(address P){
free(P);
}
free(P);
}
void InsertFirst(List* L,infotype x)
//menambahkan elemen x list L, sebagai elemen pertama
{
address P;
P = Alokasi(x);
if (P!=Nil){
next(P) = First(*L);
First(*L) = P;
}else{
printf(“Tidak dapat menambahkan elemen, Memori penuh!\n”);
}
}
//menambahkan elemen x list L, sebagai elemen pertama
{
address P;
P = Alokasi(x);
if (P!=Nil){
next(P) = First(*L);
First(*L) = P;
}else{
printf(“Tidak dapat menambahkan elemen, Memori penuh!\n”);
}
}
void DelFirst(List* L,infotype* x)
//menghapus elemen pertama dari list L, dan menyimpan info dari elemen yang dihapus tersebut di x
{
address temp = Nil;
temp = First(*L);
(*x) = info(temp);
First(*L) = next(temp); //next(First(*L))
Dealokasi(temp);
//menghapus elemen pertama dari list L, dan menyimpan info dari elemen yang dihapus tersebut di x
{
address temp = Nil;
temp = First(*L);
(*x) = info(temp);
First(*L) = next(temp); //next(First(*L))
Dealokasi(temp);
}
void printList(List L)
//menampilkan isi dari list
{
address P;
P = First(L);
if (P==Nil){
printf(“List Kosong\n”);
}else{
do{
printf(“isi list: %d\n”,info(P));
P = next(P);
}while (P!=Nil);
}
}
//menampilkan isi dari list
{
address P;
P = First(L);
if (P==Nil){
printf(“List Kosong\n”);
}else{
do{
printf(“isi list: %d\n”,info(P));
P = next(P);
}while (P!=Nil);
}
}
file di atas disimpan dengan nama yang sama dengan file headernya, tapi ekstensinya .c, list1.c, dan disimpan pada folder yang sama.
Kemudian program utamanya:
/* by: darkkhuwarizmi
namafile: main_list1.c
deskripsi: main dari tipe data list
*/
namafile: main_list1.c
deskripsi: main dari tipe data list
*/
#include “list1.h”
int main(){
List mylist;
List mylist;
CreateList(&mylist);
int i;
int n,bil;
printf(“Input List\n”);
printf(“Banyak nilai yang akan di-input-kan: “);scanf(“%d”,&n);
for(i=0;i
printf(“Elemen ke-%d: “,i+1);scanf(“%d”,&bil);
InsertFirst(&mylist,bil);
int n,bil;
printf(“Input List\n”);
printf(“Banyak nilai yang akan di-input-kan: “);scanf(“%d”,&n);
for(i=0;i
printf(“Elemen ke-%d: “,i+1);scanf(“%d”,&bil);
InsertFirst(&mylist,bil);
}
printf(“Menampilkan isi list\n”);
printList(mylist);
printList(mylist);
return 0;
}
}
Simpan file di atas dengan nama: main_list1.c atau yg lain jg bisa.
Demikianlah, silahkan jalankan, kalo pake command prompt di windows:
D:\chanz\file sumber C>gcc -c list1.c main_list1.c -Wall
D:\chanz\file sumber C>gcc -o main_list1 list1.o main_list1.o
D:\chanz\file sumber C>main_list1.exe
Input List
Banyak nilai yang akan di-input-kan: 10
Elemen ke-1: 1
Elemen ke-2: 2
Elemen ke-3: 3
Elemen ke-4: 4
Elemen ke-5: 5
Elemen ke-6: 6
Elemen ke-7:7
Elemen ke-8: 324
Elemen ke-9: 234
Elemen ke-10: 32
Menampilkan isi list
isi list: 32
isi list: 234
isi list: 324
isi list: 7
isi list: 6
isi list: 5
isi list: 4
isi list: 3
isi list: 2
isi list: 1
Input List
Banyak nilai yang akan di-input-kan: 10
Elemen ke-1: 1
Elemen ke-2: 2
Elemen ke-3: 3
Elemen ke-4: 4
Elemen ke-5: 5
Elemen ke-6: 6
Elemen ke-7:7
Elemen ke-8: 324
Elemen ke-9: 234
Elemen ke-10: 32
Menampilkan isi list
isi list: 32
isi list: 234
isi list: 324
isi list: 7
isi list: 6
isi list: 5
isi list: 4
isi list: 3
isi list: 2
isi list: 1
3. Stack ( struktur data )
Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri Stack :
- Elemen TOP (puncak) diketahui
- penisipan dan penghapusan elemen selalu dilakukan di TOP
- LIFO
Pemanfaatan Stack :
- Perhitungan ekspresi aritmatika (posfix)
- algoritma backtraking (runut balik)
- algoritma rekursif
Operasi Stack yang biasanya :
- Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack
- Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack
- IsEmpty ()
- IsFull ()
- dan beberapas selektor yang lain
4. Queue
Queue adalah salah satu list linier dari struktur data. Queue beroperasi dengan cara First In First Out (FIFO) elemen pertama masuk merupakan elemen yang pertama keluar. Untuk penyisipan (INSERT) hanya dapat dilakukan pada satu sisi yaitu sisi belakang (REAR), sedangkan untuk penghapusan (REMOVE) pada sisi depan (FRONT) dari list.
Sebagai gambaran, cara kerja queue dapat disamakan pada sebuah antrean di suatu loket dimana berlaku prinsip ‘ siapa yang duluan antre dia yang akan pertama kali dilayani ‘ , sehingga dapat dikatakan prinsip kerja queue sama dengan prinsip sebuah antrean.
Operasi dasar pada Queue
1. CREATE
Adalah suatu operator untuk membentuk dan menunjukkan suatu antrean hampa Q.
Noel ( Create(Q)) = 0
Front (Create(Q))= tidak terdefinisi
Rear (Create(Q)) = tidak terdefinisi
2. ISEMPTY
Adalah operator yang menentukan apakah antrean Q hampa atau tidak. Hasil dari operator ini merupakan tipe data berjenis Boolean.
Isempty (Q) = True , jika Q hampa
= False , jika Q tidak hampa.
3. INSERT
Suatu operator yang menyisipkan elemen ke dalam queue pada bagian belakang (rear)
- REAR (INSERT(A,Q)) = A
- ISEMPTY (INSERT(A,Q)) = FALSE
Algoritma QINSERT
1. if FRONT = 1 and REAR = N , or If FRONT = REAR + 1, then
OVERFLOW, Return
2. if FRONT := NULL, then
set FRONT := 1 and REAR := 1
else if REAR = N , then
set REAR := 1
else
set REAR := REAR + 1
3. set QUEUE [REAR] := ITEM
4. Return
4. REMOVE
Operator yang menghapus elemen bagian depan (FRONT)dari QUEUE
Algoritma QDELETE
1. if FRONT := NULL , then UNDERFLOW , Return
2. set ITEM := QUEUE[FRONT]
3. [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 + 1
4. Return
5. Pohon
Dalam ilmu komputer, sebuah Pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung.
a. Simpul (node)
Sebuah Simpul dapat mengandung sebuah nilai atau suatu kondisi atau menggambarkan sebuah struktur data terpisah atau sebuah bagian pohon itu sendiri. Setiap simpul dalam sebuah pohon memiliki nol atau lebih simpul anak (child nodes), yang berada dibawahnya dalam pohon (menurut perjanjian, pohon berkembang ke bawah, tidak seperti yang dilakukannya di alam). Sebuah simpul yang memiliki anak dinamakan simpul ayah (parent node) atau simpul leluhur (ancestor node) atau superior. Sebuah simpul paling banyak memiliki satu ayah. Tinggi dari pohon adalah panjang maksimal jalan ke sebuah daun dari simpul tersebut. Tinggi dari akar adalah tinggi dari pohon. Kedalaman dari sebuah simpul adalah panjang jalan ke akarnya dari simpul tersebut.
§ Akar (Root nodes)
Simpul yang paling atas dalam pohon adalah akar (root node). Menjadi simpul teratas, simpul akar tidak akan memiliki orang tua. Ini merupakan simpul di mana biasanya merupakan tempat untuk memulai operasi dalam pohon (walaupun beberapa algoritma dimulai dengan daun dan berakhir pada akar). Semua simpul yang lain dapat dicapai dari akar dengan menelusuri pinggiran atau pranala. (Dalam definisi resmi, setiap jalan adalah khas).
Dalam diagram, ini secara khusus di gambar paling atas. Di beberapa pohon, seperti heap, akar memiliki sifat khusus. Setiap simpul dalam sebuah pohon dapat dilihat sebagai akar dari sub pohon yang berakar pada simpul tersebut.
0 komentar:
Posting Komentar
Silahkan berkomentar untuk entri artikel di blog Everythinng about Indonesia ini