Materi Struktur Organisasi Data Lengkap
Hay sahabat blogger, gimana kabarnya nih ? masih pada sehat kan ? pasti kalian semua yang melihat artikel ini, ingin sekali belajar dasar teori dari Strutur Organisasi Data. Nah, disini aku udh nyiapin semua materinya yang kalian butuhkan untuk belajar Struktur Organisasi Data dengan lengkap, menurutku sih hehehe, kalau ada yg kurang lengkap kalian bisa berikan komentar agar aku bisa update kembali materinya. Tanpa panjang lebar yukk kita langsung saja ke materinya :D.
1. ARRAY
Array adalah suatu struktur yang terdiri dari sejumlah elemen yang memiliki tipe data
yang sama. Elemen-elemen array tersusun secara sekuensial dalam memori komputer.
Array dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi
(multi dimensi).
A. Array Satu Dimensi
Array Satu dimensi tidak lain adalah kumpulan elemen-elemen identik yang tersusun
dalam satu baris. Elemen-elemen tersebut memiliki tipe data yang sama, tetapi isi dari
elemen tersebut boleh berbeda.
Bentuk umum:
<tipe data> NamaArray[n] = {elemen0, elemen1, elemen2,.....,n};
n = jumlah elemen
Contoh Program:
1.
2.
B. Array Dua Dimensi
Array dua dimensi sering digambarkan sebagai sebuah matriks, merupakan perluasan
dari array satu dimensi. Jika array satu dimensi hanya terdiri dari sebuah baris dan
beberapa kolom elemen, maka array dua dimensi terdiri dari beberapa baris dan
beberapa kolom elemen yang bertipe sama sehingga dapat digambarkan sebagai
berikut:
Pendeklarasian array dua dimensi hampir sama dengan pendeklarasian array satu
dimensi, kecuali bahwa array dua dimensi terdapat dua jumlah elemen yang terdapat di
dalam kurung siku dan keduanya boleh tidak sama.
Elemen array dua dimensi diakses dengan menuliskan kedua indeks elemennya dalam
kurung siku seperti pada contoh berikut:
1.
2.
Beberapa array memiliki tiga dimensi, seperti nilai dalam tiga dimensi ruang, seperti koordinat x, y, dan z dalam koordinat ruang.
tipe_elemen_array nama_array[ukuran1][ukuran2]...[ukuranN];
misal: double data_angka[2][3][4];
2. LINKED LIST
Pengertian Linked List
Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara
sekuensial, saling bersambungan, dinamis dan terbatas adalah senarai berkait (linked list).
Suatu senarai berkait (linked list) adalah suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen struktur atau class yang berisi data. Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Senarai berkait lebih efisien di dalam melaksanakan penyisipan-penyisipan dan penghapusan-penghapusan. Senarai berkait juga menggunakan alokasi penyimpanan secara dinamis, yang merupakan penyimpanan yang dialokasikan pada runtime. Karena di dalam banyak aplikasi, ukuran dari data itu tidak diketahui pada saat kompile, hal ini bisa merupakan suatu atribut yang baik juga. Setiap node akan berbentuk struct dan memiliki satu buah field bertipe struct yang sama, yang berfungsi sebagai pointer. Dalam menghubungkan setiap node, kita dapat menggunakan cara first-create-first-access ataupun first-create-last-access. Yang berbeda dengan deklarasi struct sebelumnya adalah satu field bernama next, yang bertipe struct tnode. Hal ini sekilas dapat membingungkan. Namun, satu hal yang jelas, variabel next ini akan menghubungkan kita dengan node di sebelah kita, yang juga bertipe struct tnode. Hal inilah yang menyebabkan next harus bertipe struct tnode.
infotype
Ã
sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list next à address dari
elemen berikutnya (suksesor) .
Jika
L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat
diacu dengan notasi : first
(L)
Sebelum digunakan harus dideklarasikan terlebih dahulu :
#define First(L) (L)
Elemen yang diacu oleh P dapat dikonsultasi informasinya
dengan notasi : info(P)deklarasi #define
info(P) P->info next(P)deklarasi #define next(P) P->next
Beberapa Definisi :
1. List l adalah list
kosong, jika First(L) = Nil
2. Elemen
terakhir dikenali, dengan salah satu cara adalah karena Next(Last) = Nil Nil adalah pengganti Null, perubahan
ini dituliskan dengan #define Nil Null
Single linked list adalah apabila hanya ada satu pointer yang menghubungkan setiap node (satu arah “next”).
1. Single Linked List non Circular
Pembuatan struct bernama tnode berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari tnode.
Deklarasi node dengan struct:
Asumsikan kita memiliki sejumlah node yang selalu menoleh ke sebelah dalam arah yang sama. Atau, sebagai alat bantu, kita bisa mengasumsikan beberapa orang yang bermain kereta api. Yang belakang akan memegang yang depan, dan semuanya menghadap arah yang sama. Setiap pemain adalah node. Dan tangan pemain yang digunakan untuk memegang bahu pemain depan adalah variabel next. Sampai di sini, kita baru saja mendeklarasikan tipe data dasar sebuah node. Selanjutnya, kita akan mendeklarasikan beberapa variabel pointer bertipe struct tnode. Beberapa variabel tersebut akan kita gunakan sebagai awal dari linked list, node aktif dalam linked list, dan node sementara yang akan digunakan dalam pembuatan node di linked list. Berikan nilai awal NULL kepada mereka. Deklarasi node untuk beberapa keperluan, seperti berikut ini:
struct tnode *head=NULL, *curr=NULL, *node=NULL;
Dengan demikian, sampai saat ini, telah dimiliki tiga node. Satu sebagai kepala (head), satu sebagai node aktif dalam linked list (curr) dan satu lagi node sementara (node). Untuk mempermudah pengingatan, ingatlah gambar anak panah yang mengarah ke kanan. Head akan berada pada pangkal anak panah, dan node-node berikutnya akan berbaris ke arah bagian anak panah yang tajam.
Apabila diperhatikan, setiap node memiliki petunjuk untuk node sebelahnya. Node terakhir akan diberikan nilai NULL. Dengan demikian, setiap node kebagian jatah.
Berikut adalah penjelasan kode-kode pembuatan singly linked list tersebut. Pertama-tama, akan dibuat perulangan dari 0 sampai 4, yang dimaksudkan untuk membuat lima buah node yang masing-masing field data nya berisikan nilai dari 0 sampai 4. Pembuatan node dilakukan dengan fungsi malloc().
Setelah itu, perlu dibuat node dan penghubung. Pertama-tama, akan diuji apakah head bernilai NULL. Kondisi head bernilai NULL hanya terjadi apabila belum dimiliki satu node pun. Dengan demikian, node tersebut akan dijadikan sebagai head. Node aktif (curr), juga kita dapat dari node tersebut. Kalau head tidak bernilai NULL alias telah dimiliki satu atau lebih node, yang pertama dilakukan adalah menghubungkan pointer next dari node aktif (curr) ke node yang baru saja dibuat. Dengan demikian, baru saja dibuat penghubung antara rantai lama dengan mata rantai baru. Atau, dalam permainan kereta api, pemain paling depan dalam barisan lama akan menempelkan tangannya pada bahu pemain yang baru bergabung. Node aktif (curr) kemudian dipindahkan ke node yang baru dibuat.
2. Single Linked List Circular
Hampir sama dengan single linked list non circular, bahwa dibutuhkan sebuah kait untuk menghubungkan node-node data yang ada, dimana pada node terakhir atau tail yang semula menunjukkan NULL diganti dengan menunjuk ke kepala atau head. Dimana inisialisasi senarai berkait tunggal sirkular menggunakan struc adalah sebagai berikut:
Deklarasi Single Linked List Circular:
Menambah node dan membuat tail dari single linked list circular
Deklarasi penambahan node baru:
Void main(){
node = new tnode;
tail = new tnode;
node->next = head->next;
head->next = node;
tail = node;
}
Menyisipkan Node baru
Deklarasi
menyisipkan node baru menggunakan sintak berikut:
Void main()
{
node = new tnode;
node->next = head->next;
head->next = node;
}Menghapus Node dari Single Linked List Circular
Deklarasi menghapus node dari single linked list circular, menggunakan sintaks berikut:
Void main()
{
hapus = new tnode;
if( head != tail)
{
hapus = head;
head = head->next;
tail->next = head;
delete hapus;
}else
{
head = NULL;
tail = NULL;
}
}
b. Double Linked List (Senarai berkait ganda)
Double Linked List adalah elemen-elemen yang dihubungkan
dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau
belakang. Elemen double linked list terdiri dari tiga bagian :
1.
Bagian data informasi2. Pointer next yang menunjuk ke elemen berikutnya
3. Pointer prev yang menunjuk ke elemen sebelumnya
Double Linked List non Circular
Setiap
node pada linked list mempunyai field yang berisi data dan pointer ke node
berikutnya dan ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer
next dan prev akan menunjuk ke nilai NULL. Selanjutnya, pointer prev akan
menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node selanjutnya
pada list.
Deklarasi
node dibuat dari struct berikut ini :typedef struct TNode{
int data;
Tnode *next;
Tnode *prev;
};
Deklarasi Pointer Penunjuk Kepala
Double Linked List
Manipulasi linked list tidak bisa
dilakukan langsung ke node yang dituju, melainkan harus
melalui node pertama dalam linked list. Deklarasinya sebagai berikut:
Function untuk mengetahui kosong tidaknya DLLNC
int isEmpty(){
if(head
== NULL) return 1; else return 0;
}
Penambahan data di depan
Penambahan node baru akan dikaitkan di ode paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head-nya. Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.
Fungsi Menambah Di Depan
void insert Depan (int databaru){ TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
baru->prev = NULL;
if(isEmpty()==1){
head=baru;
head->next
= NULL;
head->prev = NULL;
}
else {
baru->next = head;
head->prev = baru;
head = baru;
}
cout<<”Data masuk\n”;
}
Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.
Fungsi penambahan Node ke belakang :
Ilustrasi Penambahan Node di
Belakang
Fungsi untuk menghapus node terbelakang
Ilustrasi Penghapusan Node
Menghapus Node Double Linked List
Tidak
diperlukan pointer bantu yang mengikuti pointer hapus yang berguna untuk
menunjuk ke NULL. Karena pointer hapus sudah bisa menunjuk ke pointer
sebelumnya dengan menggunakan elemen prev ke node sebelumnya, yang akan diset
agar menunjuk ke NULL setelah penghapusan dilakukan.
Fungsi Menghapus Semua Elemen
Double Linked List Circular
Double
Linked List Circular (DLLC) adalah linked list dengan menggunakan pointer,
dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer
sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut
dengan pointer next dan pre-nya menunjuk ke dirinya sendiri secara circular.
Ilustrasi DLLC
Setiap
node pada linked list mempunyai field yang berisi data dan pointer ke node
berikutnya dan ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer
next dan prev akan menunjuk ke dirinya sendiri. Jika sudah lebih dari satu
node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan
menunjuk ke node sesudahnya.
Deklarasi dan Node baru DLLC
Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya.
TNode *baru;
baru
= new TNode; baru->data = databaru; baru->next = baru; baru->prev =
baru;
Penambahan
data di depan
Penambahan
node baru akan dikaitan di node paling
depan, namun pada saat pertama kali (data masih kosong), maka penambahan
data dilakukan pada head nya. Pada prinsipnya adalah mengkaitkan data baru
dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head
akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer
bantu.
void insertDepan(int databaru){
TNode *baru, *bantu;
baru = new TNode;
baru->data
= databaru;
baru->next = baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
head->next
= head;
head->prev = head;
}
else {
}
bantu
= head->prev;
baru->next = head;
head->prev = baru;
head = baru;
head->prev =
bantu;
bantu->next = head;
cout<<"Data
masuk\n";
}
Penambahan data
di belakang
Penambahan
data dilakukan di belakang, namun pada saat pertama kali data langsung
ditunjuk pada head-nya. Penambahan di belakang
lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan
data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.
void insertBelakang (int databaru){
Tnode *baru, *bantu;
baru
= new Tnode;
baru->data = databaru;
baru->next
= baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
head->next
= head;
head->prev = head;
}
else{
bantu=head->prev;
bantu->next = baru;
baru->prev = bantu;
baru->next = head;
head->prev = baru;
}
Cout<<”Data masuk\n”;
}
Function untuk menampilkan isi linked list
void tampil(){
TNode
*bantu; bantu = head; if(isEmpty()==0){
do{
cout<<bantu->data<<"
"; bantu=bantu->next;
}while(bantu!=head);
cout<<endl;
} else cout<<"Masih kosong\n";
}
Function untuk menghapus node terbelakang
void hapusDepan (){
TNode *hapus,*bantu; int d;
if (isEmpty()==0){ if(head->next != head){
hapus = head;
d
= hapus->data; bantu = head->prev; head = head->next; bantu->next =
head; head->prev = bantu; delete hapus;
} else {
d
= head->data; head = NULL;
}
cout<<d<<" terhapus\n";
} else cout<<"Masih kosong\n";
}
Function untuk menghapus node terbelakang
3. STACK
Stack (tumpukan) dan queue (antrian)
sebenarnya adalah sebuah cara dalam mengorganisasikan data-data yang dimiliki.
Ibarat seseorang yang menyimpan buku-bukunya, ada yang disusun dengan cara
ditumpuk, ada juga yang dijejerkan di dalam lemari.
Deklarasi stack
dalam program
Sebuah stack di
dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru, di
dalam Bahasa C, biasa disebut struct.
Sebuah struktur data dari sebuah stack setidaknya
harus mengandung dua buah variabel, yakni variabel TOP yang akan berguna sebagai penanda bagian atas tumpukan dan ARRAY DATA dari yang akan menyimpan
data-data yang dimasukkan ke dalam stack tersebut.
Berikut adalah syntax untuk
mendeklarasikan struktur data dari sebuah stack
menggunakan Bahasa C:
dimana,
nilai MAX didefinisikan sebagai jumlah tumpukan maksimum yang dapat disimpan
dalam stack. Setelah strukutr data
dari stack didefinisikan dengan syntax di atas, maka setelah itu dapat
dibuat variabel-variabel baru yang mengacu pada tipe data Stack di atas, misalkan membuat sebuah variabel bernama tumpukan yang bertipe Stack:
Dalam tulisan ini,
sebuah stack didefinisikan dengan array berukuran MAX + 1, maksudnya
adalah agar elemen array ke-0 tidak
digunakan untuk menyimpan data, melainkan hanya sebagai tempat „singgah‟
sementara untuk variabel TOP. Sehingga, jika TOP berada pada elemen array ke-0, berarti stack tersebut dalam kondisi kosong (tidak ada data yang disimpan).
Berikut adalah ilustrasi dari sebuah stack
kosong dengan ukuran nilai MAX = 6:
Operasi-operasi
dasar dalam stack
Sebuah stack setidaknya memiliki lima buah
operasi-operasi dasar, yakni:
a.
Prosedur createEmpty
Prosedur ini
berfungsi untuk mengosongkan stack dengan
cara meletakkan TOP ke posisi ke-0. Berikut adalah deklarasi prosedur
createEmpty dalam Bahasa C:
void createEmpty()
{
tumpukan.TOP = 0;
}
b.
Prosedur push
Prosedur
ini berfungsi untuk memasukkan sebuah
nilai/ data ke dalam stack. Sebelum
sebuah nilai/ data dimasukkan ke dalam stack,
prosedur ini terlebih dahulu akan menaikkan posisi TOP satu level ke atas.
Misalkan kondisi stack masih kosong
(TOP = 0), lalu prosedur push akan menaikkan posisi TOP satu level ke atas,
yakni ke posisi 1 (TOP = 1), baru setelah itu data dimasukkan ke dalam array pada indeks ke-1 (yakni indeks
dimana TOP berada). Berikut adalah deklarasi prosedur push dalam Bahasa C:
void push(int x)
{
tumpukan.TOP = tumpukan.TOP + 1; tumpukan.data[tumpukan.TOP]
= x;
}
Pada deklarasi
prosedur push di atas, prosedur memiliki sebuah parameter formal yang bernama „x‟ yang bertipe integer. Parameter formal „x‟ ini berguna untuk menerima
kiriman nilai dari program utama (void main()) yakni berupa sebuah bilangan integer yang akan dimasukkan ke dalam stack. Sebelum nilai pada variabel „x‟ dimasukkan ke dalam stack, terlebih dahulu posisi TOP dinaikkan satu level, baru setelah itu nilai pada variabel „x‟ dimasukkan ke dalam array data pada indeks dimana TOP itu berada.
Prosedur POP
Prosedur
ini berfungsi untuk mengeluarkan/
menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai TOP
satu level ke bawah. Misalkan TOP berada pada indeks ke-5, maka ketika akan
mengeluarkan/ menghapus data pada posisi paling atas (pada posisi TOP),
prosedur ini akan menurunkan posisi TOP ke indeks array ke-4. Berikut deklarasi prosedur pop dalam Bahasa C:
void pop()
{
tumpukan.TOP =
tumpukan.TOP - 1;
}
Fungsi IsEmpty
Fungsi
ini berfungsi untuk melakukan pengecekan terhadap stack, apakah stack tersebut
kosong atau tidak. Jika stack tersebut kosong (artinya, TOP
berada pada posisi 0), maka fungsi akan mengembalikan nilai 1 (true), tetapi jika stack tersebut tidak kosong/ berisi (artinya, TOP tidak berada pada
posisi 0), maka fungsi akan mengembalikan nilai 0 (false). Berikut deklarasi fungsi IsEmpty dalam Bahasa C:
Fungsi IsFull
Fungsi
ini berfungsi untuk melakukan pengecekan terhadap stack, apakah stack tersebut
penuh atau tidak. Jika stack tersebut penuh (artinya, TOP
berada pada posisi MAX), maka fungsi akan mengembalikan nilai 1 (true), tetapi jika stack tersebut tidak penuh (artinya, TOP tidak berada pada posisi
MAX), maka fungsi akan mengembalikan nilai 0 (false). Berikut deklarasi fungsi IsFull dalam Bahasa C:
Contoh program implementasi stack
Berikut adalah contoh kode program dalam Bahasa
C yang mengimplementasikan konsep stack.
Pada program ini, user disuguhi
beberapa menu utama yang akan dipilih oleh user.
Menu pertama, “Cek kondisi stack” akan melakukan pengecekan terhadap kondisi stack. Menu kedua, “Tambah data” akan
melakukan pengisian sebuah nilai ke dalam stack.
Menu ketiga, “Keluarkan isi stack”, akan menampilkan semua isi stack dan akan mengosongkan stack. Menu keempat, “Kosongkan stack”,
akan melakukan pengosongan stack, dan
menu kelima, “Keluar”, akan menghentikan eksekusi program (selesai menggunakan
program).
4. QUEUE
Kaidah
utama dalam konsep queue adalah FIFO
yang merupakan singkatan dari First In
First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan,
maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.
Analoginya sama dengan antrian di sebuah loket pembelian tiket kereta, orang
yang datang lebih dahulu, maka akan dilayani terlbih dahulu, dan akan selesai
lebih dulu dari orang-orang yang datang setelahnya. Gambar di bawah ini
mengilustrasikan kerja sebuah queue:
Deklarasi queue
dalam program
Sebuah
queue di dalam program komputer
dideklarasikan sebagai sebuah tipe bentukan baru, di dalam Bahasa C, biasa
disebut struct. Sebuah struktur data
dari sebuah queue setidaknya harus
mengandung dua tiga variabel, yakni variabel HEAD yang akan berguna sebagai penanda bagian depan antrian,
variabel TAIL yang akan berguna
sebagai penanda bagian belakang antrian dan ARRAY DATA dari yang akan menyimpan data-data yang dimasukkan ke
dalam queue tersebut. Berikut adalah syntax untuk mendeklarasikan struktur
data dari sebuah queue menggunakan
Bahasa C:
typedef struct
{
int HEAD, TAIL;
int data[max+1];
}Queue;
dimana,
nilai MAX didefinisikan sebagai jumlah tumpukan maksimum yang dapat disimpan
dalam queue. Setelah strukutr data
dari queue didefinisikan dengan syntax di atas, maka setelah itu dapat
dibuat variabel-variabel baru yang mengacu pada tipe data Queue di atas, misalkan membuat sebuah variabel bernama antrian yang bertipe Queue:
Queue antrian;
Dalam
tulisan ini, sebuah queue didefinisikan
dengan array berukuran MAX + 1,
maksudnya adalah agar elemen array ke-0
tidak digunakan untuk menyimpan data, melainkan hanya sebagai tempat „singgah‟
sementara untuk variabel HEAD dan TAIL. Sehingga, jika HEAD dan TAIL berada
pada elemen array ke-0, berarti queue tersebut dalam kondisi kosong
(tidak ada data yang disimpan). Berikut adalah ilustrasi dari sebuah queue kosong dengan ukuran nilai MAX =
6:
Operasi-operasi dasar dalam queue
Pada
dasarnya, operasi-operasi dasar pada queue
mirip dengan operasi-operasi dasar pada stack.
Perbedaannya hanya pada prosedur push dan pop saja. Pada queue, prosedur yang berfungsi untuk memasukkan data/ nilai ke
dalam antrian adalah enqueue,
sedangkan prosedur untuk mengeluarkan data/ nilai dari antrian adalah dequeue.
a.
Prosedur createEmpty
Sama
pada stack, prosedur ini berfungsi
untuk mengosongkan queue dengan cara
meletakkan HEAD dan TAIL pada indeks array
ke-0. Berikut deklarasi prosedur createEmpty pada queue dalam Bahasa C:
void createEmpty()
{
antrian.HEAD = 0;
antrian.TAIL = 0;
}
b. Prosedur enqueue
Prosedur
ini digunakan untuk memasukkan sebuah
data/ nilai ke dalam queue. Sebelum
sebuah data/ nilai dimasukkan ke dalam queue,
maka prosedur ini terlebih dahulu melakukan pengecekan terhadap posisi HEAD dan
TAIL. Jika posisi HEAD dan TAIL masih berada pada indeks ke-0 (artinya queue masih kosong), maka prosedur ini
akan menempatkan HEAD dan TAIL pada indeks ke-1 terlebih dahulu, baru setelah
itu memasukkan data/ nilai ke dalam array
data queue. Namun, jika posisi
HEAD dan TAIL tidak berada pada posisi ke-0, maka posisi TAIL yang akan
dinaikkan satu level. Jadi, pada proses enqueue, TAIL-lah yang berjalan seiring
masuknya data baru ke dalam antrian, sedangkan HEAD akan tetap pada posisi
ke-1. Berikut deklarasi prosedur enqueue dalam Bahasa C:
void enqueue(int x)
{
if ((antrian.HEAD ==
0) && (antrian.TAIL == 0))
{
antrian.HEAD = 1;
antrian.TAIL = 1;
}
else
{
antrian.TAIL =
antrian.TAIL + 1;
}
antrian.data[antrian.TAIL]
= x;
}Pada deklarasi prosedur enqueue di atas, prosedur memiliki sebuah parameter formal yang bernama „x‟ yang bertipe integer. Parameter formal „x‟ ini berguna untuk menerima kiriman nilai dari program utama (void main()) yakni berupa sebuah bilangan integer yang akan dimasukkan ke dalam queue. Gambar di bawah ini mengilustrasikan proses enqueue ke dalam sebuah queue yang masih kosong.
c.
Prosedur dequeue
Prosedur
ini digunakan untuk mengeluarkan atau
membuang sebuah data/ nilai yang paling awal masuk (yang berada pada posisi
HEAD, yakni yang paling depan dari antrian) ke dalam queue. Pekerjaan yang dilakukan oleh prosedur ini adalah menaikkan
nilai HEAD satu level. Jadi, setiap satu kali data dikeluarkan, maka posisi
HEAD naik bertambah satu level. Misalkan HEAD berada pada indeks ke-1, maka
ketika akan mengeluarkan/ menghapus data pada posisi paling depan (pada posisi
HEAD), prosedur ini akan menaikkan posisi HEAD ke indeks array ke-2. Berikut deklarasi prosedur pop dalam Bahasa C:
void Dequeue(){
if (q.head > q.tail) { q.head
= 0;
q.tail = 0;
}
q.head = q.head + 1;
}
d.
Fungsi IsEmpty
Sama
seperti fungsinya pada stack, fungsi
ini berfungsi untuk melakukan pengecekan terhadap queue, apakah queue tersebut
kosong atau tidak. Jika queue tersebut kosong (artinya, HEAD dan
TAIL berada pada posisi 0, atau bisa juga ketika HEAD > TAIL), maka fungsi
akan mengembalikan nilai 1 (true),
tetapi jika queue tersebut tidak
kosong/ berisi (artinya, HEAD dan TAIL tidak berada pada posisi 0), maka fungsi
akan mengembalikan nilai 0 (false).
Berikut deklarasi fungsi IsEmpty dalam Bahasa C:
int IsEmpty()
{
if ((antrian.HEAD> antrian.TAIL) || (antrian.HEAD == 0)
&& (antrian.TAIL == 0))
return 1; else
return 0;
}
e.
Fungsi IsFull
Fungsi
ini berfungsi untuk melakukan pengecekan terhadap queue, apakah queue tersebut
penuh atau tidak. Jika queue tersebut penuh (artinya, TAIL
berada pada posisi MAX), maka fungsi akan mengembalikan nilai 1 (true), tetapi jika queue tersebut tidak penuh (artinya, TAIL tidak berada pada posisi
MAX), maka fungsi akan mengembalikan nilai 0 (false). Berikut deklarasi fungsi IsFull dalam Bahasa C:
2.
Contoh program implementasi queue
Berikut adalah contoh kode program dalam Bahasa C yang
mengimplementasikan konsep queue.
Pada program ini, user akan
menginputkan data satu per satu, kemudian setelah selesai menginputkan data ke
dalam queue, maka program akan
menampilkan semua isi queue.
5. SORTING
Pengurutan data dalam struktur data sangat penting terutama untuk data yang bertipe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun). Pengurutan (Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak
|
3 9 6
|
21 10 1 13
|
Ascending
|
1 3 6
|
9 10 13 21
|
Descending
|
21 13
|
10 9 6 3 1
|
Deklarasi Array Sorting
Mendeklarasikan array secara global:
int data[100];
int n; //untuk jumlah data
Fungsi Tukar 2 Buah Data:
void tukar (int a, int b) {
int tmp;
tmp = data [a] ; data [a] = data [b] ; data [b] = tmp ;
BUBBLE SORT
Merupakan metode sorting termudah, diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar, jika pengurutan ascending. Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar, jika pengurutan descending. Algoritma ini seolah-olah
menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Gambar 1. Proses ke-1 Algoritma Bubble Sort
Pada gambar di atas, pengecekan dimulai dari data yang paling akhir, kemudian dibandingkan dengan data di depannya, jika data di depannya lebih besar maka akan ditukar.
Gambar 2. Proses ke-2 Algoritma Bubble Sorting
Pada proses ke-2, pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasting sudah paling kecil.
Gambar 3. Proses ke-3 Algoritma Bubble Sorting
Gambar 4. Proses ke-4 Algoritma Bubble Sorting
Gambar 5. Proses ke-5 Algortima Bubble Sorting
Sintaks program fungsi Bubble Sort
void bubble sort () {
for (int i = 1; i<n; i++) {
for (int j = n-1; j>=1; j--) {
if (data [j] < data [j-1]) tukar (j, j-1); // ascending
}
}
Dengan prosedur di atas, data terurut naik (ascending), untuk urut turun (descending) silahkan ubah bagian:
if (data [j] < data [j-1] )
Menjadi:
if (data [j] > data [j-1])
tukar (j, j-1);
Algoritma Bubble Sorting mudah dalam sintaks, tetapi lebih hemat dibandingkan dengan algoritma sorting yang lain.
EXCHANGE SORT
Sangat mirip dengan Bubble Sort, dan banyak yang mengatakan Bubble Sort sama dengan Exchange Sort. Perbedaan ada dalam hal bagaimana membandingkan antar elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot). Sedangkan Bubble Sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
Sintaks program fungsi Exchange Sorting
void exchange sort ()
{
for (int i=0; i<n-1; i++) {
for (int j=(i+1); j<n; j++) { if (data [i] < data[j])
tukar(i,j); //descending
}
}
}
SELECTION SORT
Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen- elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembandingan saja, pertukaran data secara fisik terjadi pada akhir proses.
Gambar 7. Proses Algoritma Selection Sorting
Sintaks program fungsi Selection Sorting
void selection_sort () {
for (int i=0; i<n-1; i++) { pos = i;
for (int j=i+1; j<n; j++) {
if (data[j] < data[pos]) pos = j; //ascending
}
If (pos != i) tukar(pos, i);
}
}
INSERT SORT
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (di-insert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
Gambar 9. Proses Algoritma Insertion Sorting
Sintaks program fungsi Insertion Sort
void insertion_sort () { int temp;
for(int i=1; i<n; i++) { temp = data[i];
j = i-1;
while (data[j]>temp && j>=0) { data[j+1] = data[j];
j--;
}
Data[j+1] = temp;
}
}
Program lengkapnya: (PERCOBAAN LATIHAN)
#include <stdio.h> #include <conio.h>
int data[10], data2[10]; int n;
void tukar (int a, int b) { int t;
t = data[b]; data[b] = data[a]; data[a] = t;
}
void bubble_sort () {
for (int i=1; i<n; i++) {
for (int j=n-1; j>=i; j--) {
if (data[j] < data[j-1])
tukar(j, j-1);
}
}
printf (“bubble sort selesai!\n”);
}
void exchange_sort () {
for (int i=0; i<n-1; i++) {
for (int j = (i+1); j<n; j++) { if (data [i] > data[j])
tukar (i, j);
}
}
printf (“exchange sort selesai!\n”);
}
void selection_sort () { int pos, i, j;
for (i=0; i<n-1; i++) { pos = i;
for (j = i+1; j<n; j++) {
if (data [j] < data[pos]) pos = j;
}
if (pos != i) tukar (pos, i);
}
printf (“selection sort selesai!\n”);
}
void insertion_sort () { int temp, i, j;
for (i=1; i<n; i++) {
temp = data[i]; j = i-1;
while (data[j] > temp && j>=0) { data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
printf(“insertion sort selesai!\n”);
}
void Input () {
printf (“Masukkan jumlah data = ”); scanf (“%d”, &n);
for(int i=0; i<n; i++) {
printf (“Masukkan data ke-%d = ”, (i+1)); scanf (“%d”, &data[i]);
data2[i] = data[i];
}
}
void AcakLagi () {
for (int i=0; i<n; i++) { data[i] = data2[i];
}
printf (“Data sudah teracak!\n”);
}
void Tampil () {
printf (“Data : ”);
for (int i=0; i<n; i++) { print (“%d ”, data[i]);
}
printf (“\n”);
}
void main() { clrscr();
int pil; do {
clrscr ();
printf (“1. Input Data\n”); printf(“2. Bubble Sort\n”); printf(“3. Exchange Sort\n”); printf(”4. Selection Sort\n”); printf(“5. Tampilkan Data\n”); printf(“6. Acak\n”);
printf(“7. Exit”);
printf(“Pilihan = ”); scanf(“%d”, &pil); switch(pil) {
case 1: Input(); break;
case 2: bubble_sort(); break; case 3: exchange_sort(); break; case 4: selection_sort(); break; case 5: Tampil(); break;
case 6: AcakLagi(); break;
}
getch();
}
while (pil!=7);
}
0 komentar :
Posting Komentar