Algoritma dan Struktur Data

Ramos Somya, S.Kom., M.Cs.

Penggunaan record dalam jumlah yang banyak alokasimemory konvensional tidak bisa diandalkan.

Misal kita akan bekerja dengan file yang menyimpansangat banyak record, di mana setiap record jugamemiliki banyak field.- Menampilkan record- Menambahkan record- Menghapus record- Mengurutkan record

Dibutuhkan suatu rantai data yang panjang dan salingberhubungan.

Rantai data tersebut harus mampu menampung semuadata yang kita miliki.

Penggunaan array saja jelas tidak bisa, karena kitabekerja dengan barisan data heterogen.

Penggunaan Struct (Array of Struct) juga belummencukupi.

Kita tidak mungkin akan melakukan alokasi dan dealokasibeberapa kali di dalam program untuk mengoptimasipenggunaan memory.

Solusi yang lebih baik adalah menggunakan linked list,baik singly (single) linked list ataupun doubly (double)linked list.

Secara teori, linked list adalah sejumlah node yangdihubungkan secara linier dengan bantuan pointer.

Untuk implementasi Linked List, kita harus memahamiStruct terlebih dahulu.

Penggunaan struct memungkinkan kita bekerja dengan satu record yang memiliki banyak field.

#include <stdio.h>int main(){

struct Test{

int x;char c;

};struct Test test1;test1.x = 10;test1.c = ‘A’;printf(“Isi dari test1.x: %d\n”,test1.x);printf(“Isi dari test1.c: %c\n”,test1.c);return 0;}

Struct dengannama Test

Struct adalah salah satu dasarpenggunaan linked list.Apabila pemahaman akan structsudah baik, maka penggunaan linked list akan semakin mudah.

Memesan memory secara konvensional misal chars[10000], namun sayangnya, kita akan kehilangankebebasan untuk mendealokasikan memory yang sudahtidak terpakai.

Pengalokasian memory secara dinamis dapat dilakukandengan salah satu fungsi alokasi memory yaitu malloc().

Sementara, lawannya, dealokasi memory , dapat dilakukan dengan memanggil fungsi free().

Fungsi ini dideklarasikan di dalam header stdlib.h.Dengan demikian, jangan lupa untuk meng-includeheader tersebut.

Fungsi ini ini akan meminta memory sebanyak size bytes,dan apabila sukses, pointer ke lokasi memory yangdipesan akan dikembalikan.

Apabila gagal, fungsi ini akan mengembalikan NULL.

void *malloc(size_t size);

Fungsi ini dideklarasikan di dalam header stdlib.h.Dengan demikian, jangan lupa untuk meng-includeheader tersebut.

Fungsi ini akan membebaskan memory teralokasi yangditunjuk oleh variabel ptr.

void free(void *ptr);

Sebagai contoh, kita akan mengalokasikan array ofcharacter sejumlah 50000 buah secara dinamis.

kita memesan memory sejumlah 50000 kali ukuran char dan kita melakukan typecasting ke bentuk char *.

#include <stdio.h>#include <stdlib.h>int main(){char *s = (char *) malloc (50000 * sizeof (char));free(s);return 0;}

#include <stdio.h>#include <stdlib.h>int main(){

struct Test{

int x;char c;

};struct Test * test1 = (struct Test*) malloc (sizeof (struct Test));

test1 -> x = 10;test1 -> c = ‘A’;printf(“Isi dari test1->x: %d\n”,test1->x);printf(“Isi dari test1->c: %c\n”,test1->c);free(test1);return 0;}

1

2

3

1. Seperti contoh terdahulu, kita mendeklarasikan StructTest.

2. Kita memesan memori secara dinamis yang akandigunakan oleh struct test1. Kita memesan sejumlahukuran Struct Test, dan hasilnya akan digunakan untukmenyimpan test1.

3. Apabila sebelumnya kita menggunakan notasi titikuntuk mengakses field, maka dalam pengalokasiandinamis ini, kita menggunakan notasi ->.

Secara teori, linked list adalah sejumlah node yangdihubungkan secara linier dengan bantuan pointer.

Dikatakan singly (single) linked apabila hanya ada satupointer yang menghubungkan setiap node.

Setiap node akan berbentuk struct dan memiliki satubuah field bertipe struct yang sama, yang berfungsisebagai pointer.

Kita akan mulai dengan deklarasi struct untuk node.

variabel next ini akan menghubungkan kita dengan nodedi sebelah kita, yang juga bertipe struct tnode.

Hal inilah yang menyebabkan next harus bertipe structtnode.

struct tnode{

int x;struct tnode *next;

}

Selanjutnya, kita akan mendeklarasikan beberapavariabel pointer bertipe struct tnode.

Beberapa variabel tersebut akan kita gunakan sebagaiawal dari linked list, node aktif dalam linked list, dan nodesementara yang kita gunakan dalam pembuatan node dilinked list. Berikan nilai awal NULL kepada mereka.

struct tnode *head=NULL, *curr=NULL,*node=NULL;

Node yang dibuat pertama akan menjadi head. Node-node yang dibuat setelahnya akan menjadi node-node pengikut.

int i;for (i=0; i<5; i++){

node = (struct tnode *)malloc (sizeof(struct tnode));node -> x = i;if (head == NULL){

head = node;curr = node;

} else{

curr -> next = node;curr = node;

}}

kita membuat perulangan dari 0 sampai 4,yang dimaksudkan untuk membuat lima buahnode yang masing-masing field x nya berisikannilai dari 0 sampai 4. Pembuatan nodedilakukan dengan fungsi malloc().Setelah itu, kita perlu membuat node danpenghubung. Pertama-tama, kita akanmenguji apakah head bernilai NULL. Kondisihead bernilai NULL hanya terjadi apabila kitabelum memiliki satu node pun. Dengandemikian, node tersebut akan kita jadikansebagai head. Node aktif (curr), juga kitadapat dari node tersebut.

Sekarang, bagaimana kalau head tidakbernilai NULL alias kita telah memiliki satuatau lebih node? Yang pertama kita lakukanadalah menghubungkan pointer next darinode aktif (curr) ke node yang baru sajakita buat.Dengan demikian, kita baru sajamembuat penghubung antara rantai lamadengan mata rantai baru

curr -> next = NULL; Menghubungkan pointer next untuk mata rantai terakhir ke NULL.

curr = head;while (curr != NULL){

printf(“%d “, curr -> x);curr = curr -> next;

}printf(“\n”);

Pertama-tama, kita meletakkan node aktif (curr) ke posisi head. Setelah itu, kita akan pindahkan kunjungi satu per satu node dengan memindahkan node aktif (curr) ke posisi sebelahnya.Semua kunjungan tersebut akan kita lakukan apabila node aktif (curr) tidakmenemui NULL

#include <stdio.h>#include <stdlib.h>int main(){struct tnode{int x;struct tnode *next;};struct tnode *head=NULL,*curr=NULL, *node=NULL;int i;for (i=0; i<5; i++){node = (struct tnode *)malloc (sizeof(struct tnode));node -> x = i;

if (head == NULL){head = node;curr = node;}else{curr -> next = node;curr = node;}}

curr -> next = NULL;curr = head;while (curr != NULL){printf(“%d “, curr -> x);curr = curr -> next;}printf(“\n”);return 0;}