Struktur dan Pengurutan Data
Assalammu'alaikum, saya Ulfah Malihatin S. Dari prodi Informatika fakultas Teknik Universitas Muhammadiyah Sidoarjo. Berikut adalah rangkuman mengenai Struktur Data beserta Sorting Data.
Struktur Data adalah sebuah bagian dari ilmu pemrograman dasar yang mempunyai karakteristik yang terkait dengan sifat dan cara penyimpanan sekaligus penggunaan atau pengaksesan data.
Array adalah kumpulan elemen-elemen data. Kumpulan elemen tersebut mempunyai susunan tertentu yang teratur.
Jenis – jenis Array:
a. Array Satu Dimensi
Dideklarasikan:
tipe_var nama_var [ukuran];
Dengan:
- Tipe_var : untuk menyatakan jenis elemen array(misalnya inti, char, unsigned).
- Nama_var : untuk menyatakan nama variabel yang dipakai.
- Ukuran : untuk menyatakan jumlah maksimal elemen array.
Contoh :
#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();
}
b. Array Dua Dimensi
Digunakan untuk menyimpan, mengolah maupun menampilkan satu data dalam bentuk tabel atau matriks. Dideklarasikan:
tipe_var nama_var [ukuran1] [ukuran2];
Dimana :
- Ukuran 1 menunjukkan jumlah/nomor baris.
- Ukuran 2 menunjukkan jumlah/nomor kolom.
Jumlah elemen yang dimiliki Array:
Ukuran 1 x ukuran 2.
Seperti halnya pada array satu dimensi, data array dua dimensi akan ditempatkan pada memori secara berurutan.
Bentuk umum pendeklarasian array multidimensi adalah:
tipe_var nama_var [ukuran1] [ukuran2]...[ukuran n];
Pointer adalah sebuah variabel yang berisi alamat variabel yang lain.
Operator pointer:
Operator ‘&’ : Untuk mendapatkan alamat memori operand / variabel pointer.
Operator ‘*’ : Untuk mengakses nilai data operand / variabel pointer.
Contoh:
#include <stdio.h>
#include <iostream>
#include <conio.h>
using namespace std;
//cetak p dan *p
int main(void)
{
int v=7, *p;//untuk mengakses nilai data
p = &v;//untuk mendapatkan alamat memori
cout<<endl;
cout<<endl;
cout<<"Nilai *p = "<<*p;
cout<<endl;
cout<<endl;
cout<<"Alamatnya = "<<p;
-getch();
}
Struktur adalah koleksi dari variabel yang dinyatakan dengan sebuah nama, dengan sifat setiap variabel dapat memiliki tipe yang berlainan.
Mendeklarasikan Struktur :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
using namespace std;
#define MAX 10 //-->mx untuk nilai
struct dtnilai //-->Prosedur structur
{
char nim[12];
char nama[20];
double nilai[MAX];
};
void main()
{
struct dtnilai data;
int i,jml;
char strnilai[5],strjum[5];
printf("NIM : ");
gets(data.nim);
cout<<endl;
printf("Nama : ");
gets(data.nama);
cout<<endl;
printf("Jumlah Test : ");
gets(strjum);
jml=atoi(strjum);
cout<<endl;
for(i=0;i<jml;i++)
{
printf("Nilai Test %d : ",i+1);
gets(strnilai);
data.nilai[i]=atof(strnilai);
}
cout<<endl;
printf("================================================\n");
cout<<endl;
printf("DATA MAHASISWA YANG TELAH DIINPUTKAN : \n");
cout<<endl;
printf("NIM : %s\n",data.nim);
cout<<endl;
printf("NAMA : %s\n",data.nama);
cout<<endl;
for(i=0;i<jml;i++)
{
printf("Nilai Test %d : %1f\n", i+1, data.nilai[i]);
}
_getch();
}
LINKED LIST (SENARAI)
Linked List adalah objek atau elemen yang dihubungka satu dengan lainnya sehingga membentuk satu list. Syarat linked list adalah harus dapat diketahui alamat simpul pertama atau biasa dipakai variabel First/Start/Header.
Contoh Program sisip senarai
#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();
}
Operasi Dasar Pada Linked List :
IsEmpty : Fungsi ini menentukan apakah Linked List kosong atau tidak.
Size : Opersi untuk mengirim jumlah elemen di Linked List.
Create : Operasi untuk penciptaan List baru yang kosong.
Insertfirst : Operasi untuk penyisipan simpul sebagai simpul pertama.
Insertlast : Operasi untuk penyisipan simpul sebagai simpul terakhir.
Insertbefore : Operasi untuk penyisipan simpul sebelum simpul tertentu.
Deletefirst : Operasi penghapusan simpul pertama.
Deleteafter : Operasi untuk penghapusan setelah simpul tertentu.
Deletelast : Operasi penghapusan simpul terakhir.
STACK(TUMPUKAN)
Stack adalah kumpulan elemen-elemen yang tersimpan dalam suatu tumpukan.
Karakteristik penting stack sebagai berikut:
1. Elemen stack yaitu item-item data di elemen stack
2. TOP (elemen puncak dari stack)
3. Jumlah elemen pada stack
4. Status/kondisi stack, yaitu:
Stack memiliki operasi-operasi pokok sebagai berikut :
• Push : Untuk menambahkan item pada tumpulkan paling atas.
Void Push (item Type x, Stack *S)
{
If (Full (S))
Printf(“Stack FULL);
Else
{
S->Item[S->Count]=x;
++(S->count);
}
}
• POP : Untuk mengambil item teratas
Int Pop (stack S, itemType x)
{
If(Empty (S))
Printf(“Stack Kosong “);
Else
{
--(S->Count);
X=s->item(s->Count);
}
}
• Clear : Untuk mengosongkan stack
Void initializeStack (Stack S)
{
S->Count=0;
}
• Is Empty : Untuk memeriksa apakah stack kosong
Int Empty (Stack*S)
{
Return (S->Count==0);
}
• IsFull : Untuk memeriksa apakah stack sudah penuh
Int Full (Stack S)
{
Return (S->Count==MAXSTACK);
}
QUEUE(Antriaan)
ntrian adalah suatu kumpulan data yang penambahan elemennya 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).
Operasi – operasi pokok pada antrian diantranya 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 kosong.
3. IsFull ->mengecek apakah antrian sudah penuh atau belum.
ISFULL(Q) = True, jika Q adalah queue penuh.
4. Enqueue/Insert -> menambahkan elemen kedalam Antrian, penambahan elemen selalu ditambahkan di 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+1
c. SET QUEUE[REAR] := ITEM
d. RETURN
5. Dequeue/Remove ->untuk 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+1
d. RETURN
REKURSIF
Fungsi rekursif adalah suatu fungsi yang memanggil dirinya sendiri, artinya fungsi tersebut dipanggil didalam tubuh fungsi itu sendiri. Contoh menghitung nilai factorial.
Contoh prgram bilangan genap:
#include <iostream>
#include <conio.h>
using namespace std;
void odd (int a);
void even(int a);
void main(void)
{
int i;
do
{
cout<<"Masukkan Bilangan 1 - 9 (0 untuk keluar) : \n";
cin>>i;
odd(i);
cout<<endl;
} while (i!=0);
_getch();
}
void odd(int a)
{
if ((a%2) !=0) cout << "Bilangan GANJIL \n";
else
even (a);
}
void even(int a)
{
if ((a%2) ==0) cout << "Bilangan GENAP \n";
else
odd (a);
}
SORTING (PENGURUTAN)
Beberapa algoritma metode pengurutan dan prosedurnya sebagai berikut :
1. Bubble Sort
Bubble sort adalah suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya. Apabila elemen sekarang > elemen berikutnya , maka posisinya ditukar. Kalau tidak , tidak perlu ditukar.
Algoritma Bubble Sort :
1. i = 0
2. selama ( i < N-1) kerjakan baris 3 sampai 7
3. j = N-1
4. selama ( j >= i ) kerjakan baris 5 sampai 7
5. jika ( Data [j – 1] > Data [j]) maka tukar data [j – 1] dengan Data [j]
6. j = j-1
7. i = i+ 1
Prosedur yang menggunakan metode gelembung :
Void BubbleSort()
{
int i,j;
for(i=1;i<Max-1;i++)
for(j=Max-1;j>=i;j++)
if(Data[j-1] > Data[j])
Tukar(& Data [j-1], &Data [j]);
}
2. Selection Sort
Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.
Algoritma seleksi dapat dituliskan sebagai berikut :
1. i=0
2. selama (i < N-1) kerjakan baris 3 sampai dengan 9
3. k = i
4. j = i + 1
5. selama ( j < N ) kerjakan baris 6 dan 7
6. jika (Data[k] > Data [j]) maka k = j
7. j = j + 1
8. Tukar Data[i] dengan Data [k]
9. I = i+1
Dibawah ini merupakan prosedur yang menggunakan metode seleksi :
Void SelectionSort()
{
int i,j,k;
for(i=0; i<Max-1;i++)
{
k = i;
for(j=i+1; j< Max; j++)
if(Data [k] > Data [j])
k = j;
Tukar(&Data[j], &Data [k]);
}
}
. Merger Sort
Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer.
1. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)
2. Untuk kasus n>1, maka :
a. DIVIDE : bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.
b. CONQUER : secara rekursif , terapkan algoritma D-and-C pada masing-masing bagian
c. MERGE : gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.
Untuk pengetahuan lebih jangan lupa kunjungi
Struktur dan Pengurutan Data
Reviewed by Sheraphine
on
04.44
Rating: 5