Modul Struktur Data
STRUKTUR DATA Pertemuan 1 s.d 8
Sasaran: Meningkatkan: pemahaman pengetahuan tentang teori dasar struktur data dan penanganan data serta pembuatan algoritma dan penggunaan strukturd dalam pemrograman Materi : 1. Konsep dan Definisi - Tipe dan definisi - Operasi Data 2. Stack dan Queue - Operasi dan aplikasi Stack - Operasi dan aplikasi Queue dan Deque 3. Linked List - Konsep pointer dari Linked List - Operasi pointer dari Linked List - Jenis Linked List Single dan Double 4. Tree dan Graph - Terminologi, karakteristik dan struktur hirarkhi Tree - Terminologi, Representasi dan Traversal dari Graph
Halaman 1
Modull Struktur Datta
Konsep dan Definisi Definiisi Data Adalah h fakta ataau kenyataaan tercataat mengen nai suatu o obyek Pengeertian dataa ini men nyiratkan suatu nillai bisa daalam benttuk konsttanta atau u variab bel
Tipe D Data Tipe Daata
Sedeerhana
Reaal
Terstrukttur
Ordinal
String
Flat
Integerr
Record
Double
Characteer
array
Boolean n
File
Set
Tipe daata sederhaana: Hanya dimungkinnkan untukk menyimpan satu nilaai dalam saatu variabeel m yaaitu: Ada 5 macam, 1. bilaangan bulatt (integer) 2. bilaangan real presisi p tungggal bilaangan real presisi p gannda 3. karaakter 4. tak bertipe (unnsign) 5. booolean (operrator logik))
Halaman 2
Modul Struktur Data
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 nama variabel[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;
Halaman 3
Modul Struktur Data
nama_mhs tanggal
info_mhs
data_tanggal
bulan
tahun
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 }; enum manusia jenis_kelamin; Bila jenis_kelamin diisi pria maka nilai jenis kelamin=0 dan sebaliknya bila diisi wanita nilai jenis_kelamin=1 Halaman 4
Modull Struktur Datta
5. Fille Filee merupak kan organ nisasi darii sejumlah h record seejenis. Maasing‐masiing record d terrdiri dari ssatu atau leebih field d dan field terdiri darii satu atau u lebih karrakter.
File e Re ecord Field Charr
Record
Field C Char
Tipe d data Pointter Variabel pointerr berisi alaamat dari suatu obyek lain (yaaitu obyek k yang ditu unjuk oleh h pointerr tersebutt) Bentuk k umum: tipe *nama a_ponter Contoh h: in nt *pa; paa = &x; ( ‘&’ berartii alamat) Artinya poin nter pa meenunjuk allamat x
Algoritm ma dan Pem mrogram man
Perm masalahan nnya adalaah bagaim mana suatu u masalah h dapat d diselesaikaan dengan n algo oritma yan ng tepat. Dasaar‐dasar A Algoritma: elementerr; dan Statement S Statement S kontrol Stateement elementer terdiri dari: Asignment A t (X=5, X=Y Y) Compariso C n Arithmatic A c Statemen nt Halaman 5
Modul Struktur Data
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 Halaman 6
Modul Struktur Data
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; Halaman 7
Modul Struktur Data
}
} else { printf(“\n\r
stack
kosong”); }
Soal: buat fungsi PUSH 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 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”); }
Soal: buat prosedur DELETE - Cek F < R - F = F + 1 - X = Q[F] - If (f=N) { F=0 ; R= 0 } Halaman 8
Modul Struktur Data
STRUKTUR DATA Pertemuan 9 s.d 18
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: Linier Singly Linked List 1000 H
Record1 2100 H
Record2 2100 H
1000 H 2100 H
Linier Doubly Linked List Halaman 9
Modul Struktur Data
FIRST = 1100 H
NIL
A100 H
1100 H
1100 H
NIL A100 H
Circular Singly Linked List FIRST
A100 H
B100 H A100 H
C100 H
C100 H B100 H
Circular Doubly Linked List HEAD = B100 H
A100 H
A100 H B100 H
B100 H
B100 H A100 H
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 Halaman 10
Modul Struktur Data
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; Halaman 11
Modul Struktur Data
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); } } }
Halaman 12
Modul Struktur Data
Circular Doubly Linked List Kondisi kosong : head‐>right = head; head‐>left = head; H
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 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”); } }
simpul);
Halaman 13
Modul Struktur Data
Circular Doubly Linked List Kondisi kosong: Head ‐> right = head; Head ‐> left = head; Head
Kondisi isi: Record‐1: head‐>right; Record head tidak berisi data; Head
Head
void insert_tengah(void) { struct simpul *p, *q; p = (struct simpul *) malloc(sizeof(struct 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”); } }
simpul);
Halaman 14
Modul Struktur Data
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:
Level 1
A
B
C
C
D
F J
G K
H
Level 2 I
Level 3
L
Level 4
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 ,, 1 D ,, 3 Struktur pohon yang terkenal adalah struktur pohon Biner, dimana setiap simpul maksimum derajatnya adalah 2.
Halaman 15
Modul Struktur Data
A
B
D
C
E
G
F
H
I
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 Halaman 16
Modul Struktur Data
+
*
/
D
**
A
B
E
C
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 +
Halaman 17
