0
Materi Struktur Data
Posted by Yoshua_Brilliant
on
00.13
MATERI LENGKAP STRUKTUR DATA
Konsep dan Definisi
Definisi Data
Adalah fakta ataau kenyataan tercataat
mengennai suatu oobyek
Pengertian data ini menyiratkan suatu nilai bisa dalam
bentuk konstanta atau variabel
Tipe data sederhana:
Hanya dimungkinkan untuk menyimpan satu nilai dalam
satu variabel
Ada 5 macam, yaaitu:
1. bilangan bulat (integer)
2. bilangan real presisi tunggal bilangan real presisi ganda
3. karakter
4. tak bertipe (unnsign)
5. boolean (operator logik)
Tipe data terstrukrur
Adalah tipe data dimana satu variabel dapat menyimpan lebih dari satu nilai data. Masing‐masing nilai data disebut komponen.
Ada 5 macam, yaitu:
1. Data String
Data yang berisi sederetan karakter dimana banyaknya karakter bisa berubah- ubah sesuai kebutuhan
Bentuk umum : char namavariabel[
ukuran]
Contoh : char nama[30]
2. Larik (array)
dimana variabel larik hanya bisa menyimpan 1tipe data saja
Bentuk umum : Tipe data namavariabel[
ukuran]
Contoh : float X[5]
int datax[10]
3. Record
terdiri dari beeberapa variabel dimana masing‐masing variabel bisa
mempunyai tipe yang berbeda
Bentuk umum :
struct nama_tipe_struct
{
tipe field‐1;
tipe field‐2;
...................
tipe field‐n;
} var_ struct
Contoh :
struct data_tanggal
{
int tanggal;
int bulan;
int tahun;
}
struct data_mhs
{
char nama[25];
struct data_tanggal;
} info_mhs;
4. Set (himpunan)
Memungkinkan suatu lokasi memori ditempati oleh satu atau lebih variabel
yang tipenya bisa berlainan.
1. union
Bentuk umum:
Union nama_union;
Contoh:
union
{
unsigned int data_int;
unsigned char data_char[20];
} bil_x;
2. enumerius
merupakan himpunan dari konstanta integer yang diberi nama
Bentuk umum:
enum nama_enum
{
konstanta_1, jonstanta_2;
konstanta_n;
} var_1, var_2;
Contoh:
enum manusia { pria, wanita };
enu
5. File
File merupakan organisasi dari sejumlah record sejenis. Masing‐masing record terdiri dari satu atau lebih field dan field terdiri darii satu atau
lebih karakter.
Tipe data Pointer
Variabel pointer berisi alamat dari suatu obyek lain (yaitu obyek yang ditunjuk oleh pointer tersebut)
Bentuk umum
tipe *nama_ponter
Contohh:
innt *pa;
paa = &x; ( ‘&’ berartii alamat)
Artinya pointer "pa" menunjuk alamat x
Algoritmma dan Pemrogramman
Statement kontrol terdiri dari:
- Alternatif
- Pengulangan
- Percabangan
Statement elementer:
a. assignment
Untuk memberikan nilai ke variabel yang telah diseklarasikan. Bentuk
pernyataannya adalah
Contoh: total = 100;
b. comparison
Untuk keperluan pengambilan keputusan diperlukan operator relasi seperti > , < dll. , operasi aritmatik, operator Boolean.
c. statement I/O
Untuk memasukkan nilai ke komputer menggunakan: scanf(), getch()
Untuk mengeluarkan nilai menggunakan: printf(), puts()
STACK DAN QUEUE
Stack (tumpukan) dan Queue (antrian) merupakan alokasi memory dalam bentuk array 1 dimensi atau lebih.
Aplikasi penggunaan array adalah :
- Stack (tumpukan)
- Queue (antrian)
- Dequeue (antrian 2 pintu)
Pada Stack berlaku konsep LIFO (Last In First Out),
Pada Queue berlaku konsep FIFO (First In First Out), atau FCFS (First Come First Serve)
Pemilihan ke 3 cara tersebut disesuaikan dengan permasalahan yang ada:
STACK
Adalah suatu list yang penambahan (insert) atau penghapusan (deletion),
elemennya dilakukan di satu ujung (Top)
Ada 3 kondisi pada stack, yaitu :
Awal Top = 0
Kosong Top = 0
Penuh Top = N
Proses yang dapat dilakukan pada stack adalah :
1. push: untuk memasukkan data ke dalam Stack
Langkah yang diperlukan : cek apakah Top < N bila ya, tambahkan top dengan 1, isikan data ke stack
2. pop: mengeluarkan (delete) data dari Stack
Langkah yang diperlukan : cek apakah Top masih > 0, Bila ya, copy data ke suatu variabel, kurangkan Top dengan 1
Algoritma PUSH dan POP
#include <stdio.h>
void push(void);
void pop(void);
int x, top;
int s[5], N=5;
main()
{
char pilih;
clrBarloop;
{
clrscr();
gotoxy(25,7); puts(“coba stack”) ;
gotoxy(25,10); puts(“1. push”);
gotoxy(25,13); puts(“2. pop”);
gotoxy(25,16); puts(“3. exit”);
gotoxy(25,19); prinyf(“Pilih :”);
scanf(“ %x “, &pilih);
switch(pilih)
{
case 1: printf(“\n masukkan data x =;
scanf(“ “); push(); getch(); break;
case 2: pop(); getch(); break;
case 3: exit(0);
}
goto clrBaarloop;
}
}
void pop(void)
{
If (top > 0)
{
x = s[top];
pritf (“\n\r x = %d top = %d”, x, top);
top = top – 1;
2. Linier Doubly Linked List
3. Circular Singly Linked List
4. Circular Doubly Linked List
LINIER SINGLY LINKED LIST
Ada 2 bagian utama dari record Linier Singly Linked List, yaitu:
1. bagianyang berisi data/info ; dan
2. bagian yang berusu record next
Deklarasi record baru:
struct simpul *p;
p = (struct simpul *) malloc (sizeof simpul));
Proses yang dapat dilakukan adalah:
- insert record baru
- delete record
Insert:
- awal
- tengah
- akhir
Delete:
- awal
- tengah
- akhir
format record :
struct simpul {
char nama[20];
struct simpul *link;
}
void insert_awal(void)
{
struct simpul *p;
P = (struct simpul *) malloc(sizeof(struct simpul));
strcpy(p-> nama, nama); *strcpy=string Copy
if (first != NULL) * != tidak sama dgn
{
p->link = first;
first = p;
printf(“\n sisip awal”);
}
else
{
p->link = NULL;
first = p;
printf(“\n create file”);
}
}
void insert_tengah(void)
{
struct simpul *p , *q, *k;
p = (struct simpul *) malloc(sizeof(struct simpul));
strcpy(p->nama, nama);
if (first != NULL)
{
q = first;
while (q-> nama < nama)
{
k = q;
q = q->link;
}
p->link = q;
k->link = p;
printf(“\n sisip tengah “);
}
else
{
insert_awal()}
}
}
void delete_awal(void)
{
struct simpul *p;
if (first != NULL)
{
p = first;
first = first->link;
p->link = NULL;
strcpy(nama,p->nama);
free(p);
printf(“\n nama = % s”,nana);
}
else
{
printf(“\n list kosong“);
}
}
void delete_akhir(void)
{
struct simpul *p, *q;
if (first !=NULL)
{
p = first;
While (p->link != NULL)
{
q = p;
p = p->link;}
q->link = NULL;
strcpy(nama, q->nama);
printf(“\n nama =5s “, nama);
free(p);
}
}
}
Circular Doubly Linked List
Kondisi kosong :
head‐>right = head;
head‐>left = head;
Kondisi isi:
Record‐1 : head‐>right
Record head tidak berisi data
void insert_tengah(void)
{
struct simpul *p, *q;
p = (struct simpul *) malloc(sizeof(struct simpul);
strcpy(p->nama,nama);
if (head->right) != head) {
q = head-> right;
while (q->nama < nama) {
q = q->right;
}
p->right = q
p->left = q->left;
q->left->right = p;
q->left = p;
printf(“ \n sisip tengah”);
} else {
p->right = head;
p->left = heat;
head->right = p;
head->left = p;
printf(“ \n create file”);
}
}
Circular Doubly Linked List
Kondisi kosong:
Head ‐> right = head;
Head ‐> left = head;
Kondisi isi:
Record‐1: head‐>right;
Record head tidak berisi data;
void insert_tengah(void)
{ struct simpul *p, *q;
p = (struct simpul *) malloc(sizeof(struct simpul);
strcpy(p->nama,nama);
if (head->right) != head){
q = head-> right;
while (q->nama < nama) {
q = q->right;
}
p->right = q
p->left = q->left;
q->left->right = p;
q->left = p;
printf(“sisip tengah”);
} else {
p->right = head;
p->left = heat;
head->right = p;
head->left = p;
printf(“create file”); }
}
}
STRUKTUR DATA NON‐LINIER
Terdiri dari :
- Struktur Pohon
- Graph
STRUKTUR POHON
Definisi dari pohon adalah:
Susunan dari satu atau lebih simpul (node) yang terdiri dari satu simpul sebagai
akar (root) dan sisanya membentuk subtree dari akar.
Gambar pohon secara umum adalah sebagai berikut:
Akar dari pohon ini adalah A
Satu simpul berisi:
- data atau info
- alamat simpul yang dihubungkan dengan link
Jumlah subtree dari satu simpul disebut derajat (degree)
- A berderajat 3
- B berderajat 1
- D berderajat 3
Struktur pohon yang terkenal adalah struktur pohon Biner, dimana setiap simpul
maksimum derajatnya adalah 2.
Proses dalam struktur data akan mudah digambarkan bila diketahui:
n = jumlah simpul
k = derajat pohon
maka :
Jumlah link = n . k
Jumlah null‐link = n (k‐1) +1
Jumlah non‐zero link = n‐1
Dari pohon biner diatas terlihat :
n = 9
k = 2
maka :
jumlah link = 9 . 2 = 18
jumlah null‐link = 9 . (2 – 1) +1 = 10
jumlah non‐zero link = 9 – 1 = 8
Penelusuran Pohon Biner
Adalah suatu ide untuk melakukan penelusuran (traversing) atau kunjungan
(visiting) masing‐masing simpul sebanyak 1 kali.
Penelusuran ini akan menghasilkan urutan linier dari informasi
Ada 3 cara penelusuran, yaitu
- inorder
- preorder
- postorder
Penelusuran inorder:
- Telusuri subtree kiri dalam inorder
- Proses simpul akar
- Telusuri subtree kanan dalam inorder
Hasil penelusuran dari pohon di atas adalah :
A / B ** C * D + E
Penelusuran Preorder:
- Proses simpul akar
- Telusuri subtree kiri dalam Preorder
- Telusuri subtree kanan dalam
Preorder
Lihat gambar di atas maka hasil penelusuran Preorder adalah:
+ * / A ** B C D E
Penelusuran Postoeder:
- Telusuri subtree kiri dalam postorder- Telusuri subtree kanan dalam postoeder
- Proses simpul akar
Hasil penelusuran dari pohon di atas adalah:
A B C ** / D * E +
4. Set (himpunan)
Memungkinkan suatu lokasi memori ditempati oleh satu atau lebih variabel
yang tipenya bisa berlainan.
1. union
Bentuk umum:
Union nama_union;
Contoh:
union
{
unsigned int data_int;
unsigned char data_char[20];
} bil_x;
2. enumerius
merupakan himpunan dari konstanta integer yang diberi nama
Bentuk umum:
enum nama_enum
{
konstanta_1, jonstanta_2;
konstanta_n;
} var_1, var_2;
Contoh:
enum manusia { pria, wanita };
enu
5. File
File merupakan organisasi dari sejumlah record sejenis. Masing‐masing record terdiri dari satu atau lebih field dan field terdiri darii satu atau
lebih karakter.
Tipe data Pointer
Variabel pointer berisi alamat dari suatu obyek lain (yaitu obyek yang ditunjuk oleh pointer tersebut)
Bentuk umum
tipe *nama_ponter
Contohh:
innt *pa;
paa = &x; ( ‘&’ berartii alamat)
Artinya pointer "pa" menunjuk alamat x
Algoritmma dan Pemrogramman
Permasalahannya adalah
bagaimana suatu masalah
dapat diselesaikaan dengan algoritma yang
tepat.
Dasar‐dasar Algoritma:
Statement elementer; dan
Statement kontrol
Statement
elementer terdiri dari:
Asignmentt (X=5, X=YY)
Comparison
Arithmatic Statemennt Statement kontrol terdiri dari:
- Alternatif
- Pengulangan
- Percabangan
Statement elementer:
a. assignment
Untuk memberikan nilai ke variabel yang telah diseklarasikan. Bentuk
pernyataannya adalah
Contoh: total = 100;
b. comparison
Untuk keperluan pengambilan keputusan diperlukan operator relasi seperti > , < dll. , operasi aritmatik, operator Boolean.
c. statement I/O
Untuk memasukkan nilai ke komputer menggunakan: scanf(), getch()
Untuk mengeluarkan nilai menggunakan: printf(), puts()
STACK DAN QUEUE
Stack (tumpukan) dan Queue (antrian) merupakan alokasi memory dalam bentuk array 1 dimensi atau lebih.
Aplikasi penggunaan array adalah :
- Stack (tumpukan)
- Queue (antrian)
- Dequeue (antrian 2 pintu)
Pada Stack berlaku konsep LIFO (Last In First Out),
Pada Queue berlaku konsep FIFO (First In First Out), atau FCFS (First Come First Serve)
Pemilihan ke 3 cara tersebut disesuaikan dengan permasalahan yang ada:
STACK
Adalah suatu list yang penambahan (insert) atau penghapusan (deletion),
elemennya dilakukan di satu ujung (Top)
Ada 3 kondisi pada stack, yaitu :
Awal Top = 0
Kosong Top = 0
Penuh Top = N
Proses yang dapat dilakukan pada stack adalah :
1. push: untuk memasukkan data ke dalam Stack
Langkah yang diperlukan : cek apakah Top < N bila ya, tambahkan top dengan 1, isikan data ke stack
2. pop: mengeluarkan (delete) data dari Stack
Langkah yang diperlukan : cek apakah Top masih > 0, Bila ya, copy data ke suatu variabel, kurangkan Top dengan 1
Algoritma PUSH dan POP
#include <stdio.h>
void push(void);
void pop(void);
int x, top;
int s[5], N=5;
main()
{
char pilih;
clrBarloop;
{
clrscr();
gotoxy(25,7); puts(“coba stack”) ;
gotoxy(25,10); puts(“1. push”);
gotoxy(25,13); puts(“2. pop”);
gotoxy(25,16); puts(“3. exit”);
gotoxy(25,19); prinyf(“Pilih :”);
scanf(“ %x “, &pilih);
switch(pilih)
{
case 1: printf(“\n masukkan data x =;
scanf(“ “); push(); getch(); break;
case 2: pop(); getch(); break;
case 3: exit(0);
}
goto clrBaarloop;
}
}
void pop(void)
{
If (top > 0)
{
x = s[top];
pritf (“\n\r x = %d top = %d”, x, top);
top = top – 1;
}
else { printf(“\n\r stack kosong”); }
}
Aplikasi stack antara lain :
1. Dalam sistem operasi, pada saat aktivitas call dan return
2. Pada proses kompilasi, untuk melakukan pengecekan kelengkapan pasangan
tanda kurung, kurung kotak, dll.
QUEUE (antrian)
Prinsip: FIFO (First In First Out) atau FCFS (First Come First Serve)
Ada 2 macam pointer, yaitu: F(Front) dan R(Rear)
Untuk pengambilan data menggunakan pointer F sedang untuk pemasukkan data
Untuk pengambilan data menggunakan pointer F sedang untuk pemasukkan data
menggunakan pointer R
Bila kondisi kosong F=0 dan R=0 sedang kondisi penuh R=N maka syarat
antrian adalah:
F <= R
Proses yang dapat dilakukan adalah:
1. INSERT, untuk memasukkan ke antrian;
2. DELETE, untuk mengeluarkan data dari antrian.
Kondisi yang perlu diperhatikan adalah kondisi penuh tapi kosong yaitu F=R=N
Subroutine insert:
void insert(void)
{
if ( R< N )
{
R = R+ 1;
Q[R] = x;
printf(“ R = %d x = %d “, R, x);
}
else
printf(“antrian penuh”);
}
Linked List
Pengelolaan memori secara dinamis artinya tidak perlu mengalokasikan memori
lebih awal secara fixed.
Pengelolaan memori secara dinamis dapat dilakukan:
alokasi memori; dan dealokasi memori
Alokasi memori:
void * malloc ( jumlah byte )
Dealokasi memori:
void free(void *nama_pointer)
contoh:
char *ptr;
ptr = (char *) malloc(500 * sizeof (char));
free(ptr);
Ada 2 bagian pada setiap record Linked List, yaitu: bagian data atau info; dan bagian alamat record next
Ada 4 macam proses yaitu:
1. Linier Singly Linked List
1. Linier Singly Linked List
2. Linier Doubly Linked List
3. Circular Singly Linked List
4. Circular Doubly Linked List
LINIER SINGLY LINKED LIST
Ada 2 bagian utama dari record Linier Singly Linked List, yaitu:
1. bagianyang berisi data/info ; dan
2. bagian yang berusu record next
Deklarasi record baru:
struct simpul *p;
p = (struct simpul *) malloc (sizeof simpul));
Proses yang dapat dilakukan adalah:
- insert record baru
- delete record
Insert:
- awal
- tengah
- akhir
Delete:
- awal
- tengah
- akhir
format record :
struct simpul {
char nama[20];
struct simpul *link;
}
void insert_awal(void)
{
struct simpul *p;
P = (struct simpul *) malloc(sizeof(struct simpul));
strcpy(p-> nama, nama); *strcpy=string Copy
if (first != NULL) * != tidak sama dgn
{
p->link = first;
first = p;
printf(“\n sisip awal”);
}
else
{
p->link = NULL;
first = p;
printf(“\n create file”);
}
}
void insert_tengah(void)
{
struct simpul *p , *q, *k;
p = (struct simpul *) malloc(sizeof(struct simpul));
strcpy(p->nama, nama);
if (first != NULL)
{
q = first;
while (q-> nama < nama)
{
k = q;
q = q->link;
}
p->link = q;
k->link = p;
printf(“\n sisip tengah “);
}
else
{
insert_awal()}
}
}
void delete_awal(void)
{
struct simpul *p;
if (first != NULL)
{
p = first;
first = first->link;
p->link = NULL;
strcpy(nama,p->nama);
free(p);
printf(“\n nama = % s”,nana);
}
else
{
printf(“\n list kosong“);
}
}
void delete_akhir(void)
{
struct simpul *p, *q;
if (first !=NULL)
{
p = first;
While (p->link != NULL)
{
q = p;
p = p->link;}
q->link = NULL;
strcpy(nama, q->nama);
printf(“\n nama =5s “, nama);
free(p);
}
}
}
Circular Doubly Linked List
Kondisi kosong :
head‐>right = head;
head‐>left = head;
Kondisi isi:
Record‐1 : head‐>right
Record head tidak berisi data
void insert_tengah(void)
{
struct simpul *p, *q;
p = (struct simpul *) malloc(sizeof(struct simpul);
strcpy(p->nama,nama);
if (head->right) != head) {
q = head-> right;
while (q->nama < nama) {
q = q->right;
}
p->right = q
p->left = q->left;
q->left->right = p;
q->left = p;
printf(“ \n sisip tengah”);
} else {
p->right = head;
p->left = heat;
head->right = p;
head->left = p;
printf(“ \n create file”);
}
}
Circular Doubly Linked List
Kondisi kosong:
Head ‐> right = head;
Head ‐> left = head;
Kondisi isi:
Record‐1: head‐>right;
Record head tidak berisi data;
void insert_tengah(void)
{ struct simpul *p, *q;
p = (struct simpul *) malloc(sizeof(struct simpul);
strcpy(p->nama,nama);
if (head->right) != head){
q = head-> right;
while (q->nama < nama) {
q = q->right;
}
p->right = q
p->left = q->left;
q->left->right = p;
q->left = p;
printf(“sisip tengah”);
} else {
p->right = head;
p->left = heat;
head->right = p;
head->left = p;
printf(“create file”); }
}
}
STRUKTUR DATA NON‐LINIER
Terdiri dari :
- Struktur Pohon
- Graph
STRUKTUR POHON
Definisi dari pohon adalah:
Susunan dari satu atau lebih simpul (node) yang terdiri dari satu simpul sebagai
akar (root) dan sisanya membentuk subtree dari akar.
Gambar pohon secara umum adalah sebagai berikut:
Akar dari pohon ini adalah A
Satu simpul berisi:
- data atau info
- alamat simpul yang dihubungkan dengan link
Jumlah subtree dari satu simpul disebut derajat (degree)
- A berderajat 3
- B berderajat 1
- D berderajat 3
Struktur pohon yang terkenal adalah struktur pohon Biner, dimana setiap simpul
maksimum derajatnya adalah 2.
Proses dalam struktur data akan mudah digambarkan bila diketahui:
n = jumlah simpul
k = derajat pohon
maka :
Jumlah link = n . k
Jumlah null‐link = n (k‐1) +1
Jumlah non‐zero link = n‐1
Dari pohon biner diatas terlihat :
n = 9
k = 2
maka :
jumlah link = 9 . 2 = 18
jumlah null‐link = 9 . (2 – 1) +1 = 10
jumlah non‐zero link = 9 – 1 = 8
Penelusuran Pohon Biner
Adalah suatu ide untuk melakukan penelusuran (traversing) atau kunjungan
(visiting) masing‐masing simpul sebanyak 1 kali.
Penelusuran ini akan menghasilkan urutan linier dari informasi
Ada 3 cara penelusuran, yaitu
- inorder
- preorder
- postorder
Penelusuran inorder:
- Telusuri subtree kiri dalam inorder
- Proses simpul akar
- Telusuri subtree kanan dalam inorder
Hasil penelusuran dari pohon di atas adalah :
A / B ** C * D + E
Penelusuran Preorder:
- Proses simpul akar
- Telusuri subtree kiri dalam Preorder
- Telusuri subtree kanan dalam
Preorder
Lihat gambar di atas maka hasil penelusuran Preorder adalah:
+ * / A ** B C D E
Penelusuran Postoeder:
- Telusuri subtree kiri dalam postorder- Telusuri subtree kanan dalam postoeder
- Proses simpul akar
Hasil penelusuran dari pohon di atas adalah:
A B C ** / D * E +
