Judul:Implementasi List Linear dalam Bahasa C Mata Kuliah: PI1043 Struktur Data Penulis: Tjokorda Agung Budi Wirayuda, ST, MT Program Studi Diploma 3 Teknik Informatika IT Telkom Bandung

Overview Dalam pertemuan sebelumnya telah dibahas mengenai mekanisme koleksi yang dapat digunakan untuk menampung sekumpulan elemen dengan tipe yang sama seperti array. Beberapa kelemahan dalam menggunakan array antara lain: alokasi memori yang bersifat statis, kemungkinan terjadinya kondisi sparse sehingga kita perlunya mengetahui lokasi-lokasi yang belum terisi, proses operasi penghapusan elemen yang perlu melakukan pergeseran elemen lain untuk menjaga keterurtan. Untuk materi kali ini akan diperkenalkan sebuah struktur data yang dikenal dengan List Linear. List linier adalah sekumpulan elemen bertipe sama yang mempunyai keterurutan tertentu. Dimana list linear menawarkan beberapa keuntungan seperti : alokasi memori yang dinamis, komputasi yang lebih ringkas apabila melakukan perubahan pada elemen (terutama operasi insert dan delete). Tentu saja kemudahan yang ditawarkan akan sangat bermanfaat apabila kita memahami logika dan implementasi dari List Linear. Implementasi List Linear dalam bahasa C dapat dikatakan “gampang-gampang sulit” dimana konsep dasar yang wajib dipahami adalah penggunaan pointer untuk mengacu pada data-data yang bersifat dinamis (saya sendiri mengalami banyak kesulitan dalam implementasinya )

List Linear List Linear adalah sekumpulan elemen-elemen yang memiliki tipe yang sama, dimana setiap elemen akan terdiri dari 2 bagian yaitu: type ElmtList : <Info: Infotype, Next: address> Info : variabel bertipe InfoType dimaan tipe ini telah terdefinisi dan digunakan untuk menyimpan data Next : menyimpan Address dari elemen selanjutnya (dalam C implementasinya adalah sebuah pointer)

Dari gambar ilustrasi sebuah List Linear dapat dilihat ada 2 buah bagian penting yaitu: Elemen dan List itu sendiri. Implementasi dari List adalah sebuah pointer (@) yang mengacu pada elemen pertama dari sebuah List, terkadang disebut juga dengan HEAD.

Keterurutan dan relasi antar elemen dilakukan melalui mekanisme akses address. Untuk lebih meningkatkan pemahaman terhadap konsep Modular maka dalam implementasi dari List, kita akan lakukan dengan menerapkan ADT.

Implementasi List Linear Dalam Bahasa C Misalkan kita ambil contoh kasus ADT mahasiswa yang telah diberikan sebelumnya. {silahkan anda baca lagi definisi dari ADT Mahasiswa yang telah difefinisikan}

Penulisan File Header Tahap pertama adalah membangun Element List dimana elemen terdiri dari InfoType dan Address. Berikut adalah kode yang dituliskan pada file header untuk mendefinisikan TYPE dan PRIMITIF yang akan kita gunakan: Kode Keterangan //Definisi Boolean typedef enum {false=0,true=1} boolean;

Mendefinisikan tipe boolean agar dapat digunakan

typedef struct Mahasiswa{ //Definisi Data Mahasiswa char Nim[20]; float NilaiMentah; char Nama[20]; char Indeks; }InfoType;

Mendefinisikan InfoType dengan menggunakan keyword typedef

//Definisi Element dan alias untuk pointer ke Element typedef struct Element { InfoType Data; struct Element *Next; }*ElementPtr;

Mendefinisikan element, perhatikan bahwa kita menyatakan bahwa Next adalah pointer yang akan digunakan untuk mengacu ke sebuah elemen Dalam kode ini kita mendefinisikan 1 tipe bentukan baru yaitu Elemen kemudian memberikan alias untuk pointer yang mengacunya dengan nama ElementPtr untuk memudahkan dalam penulisan kode selanjutnya

//Definisi List typedef struct var { ElementPtr Head; }List;

Kita definisikan sebuah list dengan mengatur bahwa sebuah list direpresentasikan oleh sebuah element pointer yang dikenal dengan HEAD. Tipe var hanya digunakan untuk temporary definisi dan nanti akan kita gunakan aliasnya yaitu List

/*Kita sekarang memiliki 3 tipe bentukan yaitu InfoType, Element dan List maka kita harus mendefiniskan PRIMITIF untuk 3 tipe bentukan

tersebut */ //=======InfoType primitif========== InfoType entriInfoType(); void setNama(InfoType *temp); void setNim(InfoType *temp); void setNilaiMentah(InfoType *temp); void setIndeks(InfoType *temp, char indeks); char getIndeks(InfoType temp); char* getNama(InfoType *temp); float getNilaiMentah(InfoType temp); char* getNim(InfoType *temp); void displayInfo(InfoType temp); //==================================

//======Element Primitif============ //PRIMITIF untuk membuat sebuah element ElementPtr createElementV(); ElementPtr createElement(InfoType a); //===================================

//=======List Primitif========= void createList(List *l); boolean isEmpty(List *l); ElementPtr First(List *l); ElementPtr Next(ElementPtr P); void insertFirstPtr(List *l,ElementPtr P); void insertFirst(List *l,InfoType a); void insertAfterPtr(ElementPtr Prv, ElementPtr P); void insertLastPtr(List *l, ElementPtr P); void insertLast(List *l, InfoType a); ElementPtr searchingV1(List *l, char *Nim); void deleteFirstPtr(List *l, ElementPtr P); void deleteFirst(List *l, InfoType a); void deleteAfter(ElementPtr Prv, ElementPtr P); void deleteLastPtr(List *l, ElementPtr Last ); void concat(List *l1,List *l2); void viewList(List *l); //Prototype pengamanan memory void safefree(void **pp); //=============================

Ada beberapa Primitif yang belum akan diimplementasikan pada kode ini, kita hanya fokus kepada proses Insert dan viewList saja dulu

Note: Pembangunan Primitif yang akan digunakan sangat tergantung pada skenario kasus yang dihadapi, semua tergantung pula akan seberapa jauh anda memiliki visi ke depan dalam pengembangan program sehingga dapat merancang program secara efektif dan efisien

Setelah mendefinisikan File Header maka tahap selanjutnya adalah menuliskan kode implementasi dari file header yang ada, namun kali ini kita akan membangun Program Utama terlebih dahulu dengan asumsi bahwa semua implementasi yang ada sudah benar (hal ini akan sangat membantu kita dalam merancang sebuah program secara efektif dan efisien).

Penulisan Program Utama Misalkan kita akan membangun sebuah program untuk melakukan testing terhadap fungsi/mekanisme Insert dan menambahkan mekanisme pencarian terhadap data (sama dengan program dengan array). Misalkan program yang akan kita bangun akan memiliki tampilan sebagai berikut:

Kode #include <stdio.h> #include <stdlib.h> #include "adtmhslist.h" void pencarian(List *l); int main(int argc, char *argv[]) { int pil=0; List l; InfoType a; createList(&l); do{ printf("PROGRAM DATA MAHASISWA \n"); printf("1. Entri Data Diawal \n"); printf("2. Entri Data Diakhir \n"); printf("3. Entri Data Ditengah \n"); printf("4. Cari Data Mahasiswa \n"); printf("5. List Mahasiswa \n"); printf("6. Keluar \n"); printf("Masukkan Pilihan anda [1-6]: "); scanf("%d",&pil); switch(pil){ case 1: insertFirst(&l,entriInfoType()); break; case 2: insertLast(&l,entriInfoType()); break; case 3: puts("Under Construction");//viewList(&l); break; case 4: pencarian(&l); break; case 5: viewList(&l); break; case 6: break; default: pil=0;break; } } while (pil!=6); system("PAUSE"); return 0; } void pencarian(List *l){ char cari[20]; ElementPtr P; fflush(stdin); printf("Masukkan nim yang dicari :"); gets(cari); P=searchingV1(l,cari);

if (P==NULL) { puts("Data tidak ditemukan"); } else {puts("Data ditemukan"); puts("Informasinya:"); displayInfo(P->Data); }

Penulisan Implementasi File Header Perancangan PRIMITIF sangat tergantung dari pola pikir programmer dalam menyelesaikan suatu masalah, pada kesempatan ini kita akan memberikan berbagai batasan dan asumsi agar kita memiliki pemahaman yang sama terhadap mekanisme PRIMITIF yang ada.

Implementasi Primitif InfoType Perhatikan kode pada penulisan File Header, disana kita temukan bahwa sebuah InfoType akan memiliki PRIMITIF sebagai berikut (kita akan lengkapi dengan Initial State dan Final State serta kode implementasi). Note: Nilai yang terkandung pada Indeks bergantung pada NilaiMentah sehingga perlu disediakan mekanisme konversi dari NilaiMentah ke Indeks

//=======Implementasi InfoType primitif========== /* Bagian awal tentu saja menerapkan set dan get , disini dilakukan sedikit perubahan pada mekanisme set dimana set akan dilakukan langsung pada InfoType tidak lagi menggunakan variabel bantuan */ //Prototype subrutin private char prosesIndeks(InfoType *temp); //subrutin private char prosesIndeks(InfoType *temp) { /*I.S : InfoType temp terdefinisi dan informasi NilaiMentah telah ada F.S : Mengembalikan nilai Indeks dalam char sesuai aturan penilaian */ float dt; char dt1; dt=temp->NilaiMentah; if (dt>75) dt1='A'; else if (dt>60) dt1='B'; else if (dt>50) dt1='C'; else dt1='E'; return dt1; }

//PRIMITIF set void setNama(InfoType *temp) { /*I.S : InfoType temp terdefinisi dan masih kosong F.S : Informasi Nama dari InfoType temp terentri dan disimpan*/ fflush(stdin); gets(temp->Nim); fflush(stdin); } void setNim(InfoType *temp) { /*I.S : InfoType temp terdefinisi dan masih kosong F.S : Informasi Nim dari InfoType temp terentri dan disimpan*/ fflush(stdin); gets(temp->Nama); fflush(stdin); } void setNilaiMentah(InfoType *temp) { /*I.S : InfoType temp terdefinisi dan masih kosong F.S : Informasi NilaiMentah dari InfoType temp terentri dan disimpan*/ scanf("%f",&temp->NilaiMentah); setIndeks(temp,prosesIndeks(temp)); } void setIndeks(InfoType *temp, char indeks) { /*I.S : InfoType temp terdefinisi dan masih kosong F.S : Informasi Indeks dari InfoType temp terentri dan disimpan*/ temp->Indeks=indeks; } //PRIMITIF get char getIndeks(InfoType temp) { /*I.S : InfoType temp terdefinisi dan telah berisi data F.S : Mengembalikan Informasi Indeks dari InfoType temp */ return temp.Indeks; } char* getNama(InfoType *temp) { /*I.S : InfoType temp terdefinisi dan telah berisi data F.S : Mengembalikan Informasi Indeks dari InfoType temp */ return temp->Nama; } float getNilaiMentah(InfoType temp) { /*I.S : InfoType temp terdefinisi dan telah berisi data F.S : Mengembalikan Informasi Indeks dari InfoType temp */ return temp.NilaiMentah; } char* getNim(InfoType *temp) { /*I.S : InfoType temp terdefinisi dan telah berisi data F.S : Mengembalikan Informasi Indeks dari InfoType temp */ return temp->Nim; } InfoType entriInfoType() {/*I.S: - F.S: Tercipta sebuah info Type yang telah berisi data */ InfoType temp; printf("Masukkan Nim:");

setNim(&temp); printf("Masukkan nama:"); setNama(&temp); printf("Masukkan Nilai:"); setNilaiMentah(&temp); return temp; } void displayInfo(InfoType temp) {/*I.S: InfoType temp telah terdefinisi dan berisi data F.S: Menampilam informasi yang dari temp ke layar */ printf("NIM : %s \n",getNim(&temp)); printf("NAMA : %s \n",getNama(&temp)); printf("Nilai : %2.f \n",getNilaiMentah(temp)); printf("Indeks : %c \n",getIndeks(temp)); } //==================================================================

Dengan membangun PRIMITIF untuk InfoType seperti yang telah didefinisikan diatas maka apabila kita ingin menggenerate sebuah InfoType maka kita dapat memanggil fungsi InfoType entriInfoType(), misalkan pada contoh kode program utama dalam pemanggilan mekanisme Memasukkan Data Di Awal, kita tinggal memanggil

Hal yang sama kita lakukan apabila ingin menampilkan informasi dari sebuah InfoType kita tinggal panggil prosedure void displayInfo(InfoType temp), yang dipanggil pada program utama sub-rutin pencarian

Implementasi Primitif Element Element terdiri atas InfoType dan Adress, disini kita akan menyediakan 2 buah mekanisme “generate” Element yaitu:

ElementPtr createElement(InfoType a); ElementPtr createElementV(); //=======Implementasi Element Primitif=============== ElementPtr createElement(InfoType a) {/*I.S: InfoType a telah terdefinisi F.S: Tercipta sebuah elemen dimana Data yang dimiliki sama dengan data pada InfoType a */ ElementPtr temp=(ElementPtr)malloc(sizeof(Element)); if (temp==NULL) {printf("Gagal Alokasi Memori");} temp->Next=NULL;

void insertFirst(List *l,InfoType a) insertFirst(&l,entriInfoType());

void displayInfo(InfoType temp) displayInfo(P->Data);

temp->Data=a; return temp; } ElementPtr createElementV() {/*I.S: InfoType belum terdefinisi F.S: Tercipta sebuah elemen dimana dengan meminta user untuk mengentrikan data dengan memanggil entriInfoType() */ createElement(entriInfoType()); }

Perbedaan pada kedua sub-rutin untuk menghasilkan sebuah elemen ada pada parameter yang digunakan, pada prosedur ElementPtr createElementV(); informasi data InfoType diasumsikan belum terdefinisi dan belum ada variabel yang disiapkan sehingga secara otomatis akan membuat Element dengan memanggil prosedur ElementPtr createElement(InfoType a) dengan memanfaatkan prosedure entriInfoType();

Implementasi Primitif List Pada kesempatan ini hanya akan diberikan contoh untuk implementasi primitif list sesuai dengan kebutuhan pada program yang akan dibuat. Adapu PRIMITIF yang akan diimplementasikan meliputi:

void createList(List *l); boolean isEmpty(List *l); ElementPtr First(List *l); ElementPtr Next(ElementPtr P); void insertFirstPtr(List *l,ElementPtr P); void insertFirst(List *l,InfoType a); void insertAfterPtr(ElementPtr Prv, ElementPtr P); void insertLastPtr(List *l, ElementPtr P); void insertLast(List *l, InfoType a); ElementPtr searchingV1(List *l, char *Nim); PRIMITIF void createList(List *l); ILUSTRASI

ALGORITMA Procedure createList(Input/Output: List L) {I.S : - F.S :list siap digunakan/ list kosong } FIRST(L) <- Nil KODE C void createList(List *l){ l->Head=NULL; }

Set Head dari list menjadi NULL

PRIMITIF boolean isEmpty(Input List *l); ILUSTRASI

ALGORITMA Function isEmpty(List L) -> Boolean {I.S : terdefinisi list L F.S : membalikkan nilai TRUE bila list kosong dan FALSE bila tidak kosong } If FIRST(L)=Nil

TRUE ELSE

FALSE KODE C boolean isEmpty(List *l){ if (l->Head==NULL) return true; else return false; return true; } PRIMITIF ElementPtr First(List *l); ILUSTRASI

ALGORITMA Function First(L) -> Address {I.S: - F.S: membalikan alamat dari element pertama dari sebuah List }

L->Head KODE C ElementPtr First(List *l){ return l->Head; } PRIMITIF ElementPtr Next(ElementPtr P); ILUSTRASI

P Return this address

@ @

l Return this address

@

List Kosong = FALSE

List Kosong = TRUE

ALGORITMA Function Next(P) -> Address {I.S: - F.S: membalikan alamat selanjutnya dari element P }

P->Next KODE C ElementPtr Next(ElementPtr P){ return P->Next; } PRIMITIF void insertFirstPtr(List *l,ElementPtr P); ILUSTRASI

Kasus Untuk List Kosong: Kondisi Akhir

Tahap 2

Tahap 1

P

Tahap 1 : Mengatur NEXT dari P ke element pertama List, memastikan bahwa NEXT P adalah Nill

Tahap 2: Mengatur HEAD dari List ke P

Note : pada Tahap 2 link dari HEAD yang awalnya Nill akan berpindah ke P

Kasus Untuk List Tidak Kosong: Kondisi Awal

@

P

Kasus Untuk List Kosong: Kondisi Awal

P

ALGORITMA Procedure insertFirstPtr(Input/Output List L, Input Address P) { I.S: Terdefinisi List L mungkin kosong, terdapat Elemen dengan address P F.S: P menjadi elemen pertama dalam List L } NEXT(P) <- FIRST(L) FIRST(L) <- P KODE C void insertFirstPtr(List *l,ElementPtr P){ if (isEmpty(l)==true)//berarti list masih kosong { printf("Insert Ke List Kosong \n"); } else // berarti list udah ada isinya { printf("Insert Ke List Tidak Kosong \n"); P->Next=l->Head; } l->Head=P; printf("%p \n",l->Head); //Untuk menampilkan address head } PRIMITIF void insertFirst(List *l,InfoType a); ILUSTRASI Sama dengan insertFirstPtr hanya berbeda pada masalah pengisian InfoType ke dalam Elemen

ALGORITMA procedure insertFirst(Input/Output List L,Input InfoType a) { I.S: Terdefinisi List L mungkin kosong, terdapat InfoType a F.S: InfoType a dimasukkan ke dalam P dan P menjadi elemen pertama List L } Kamus Lokal: Adress P Alokasi(P); insertFirstPtr(L,P) KODE C void insertFirst(List *l,InfoType a){

Kasus Untuk List Tidak Kosong: Kondisi Akhir

Tahap 2

Tahap 1

@

P

Tahap 1 : Mengatur NEXT dari P ke element pertama List Tahap 2: Mengatur HEAD dari List ke P

Note : pada Tahap 2 link dari HEAD akan berpindah ke P

Info Empty

Data InfoType dimasukkan ke dalam Elemen P P->Data = InfoType

ElementPtr P; P=createElement(a); insertFirstPtr(l,P); } PRIMITIF void insertAfterPtr(ElementPtr Prv, ElementPtr P); ILUSTRASI

ALGORITMA procedure insertAfter(Input/Output Address Prev, P) { I.S: Terdefinisi List L mungkin kosong, terdapat InfoType a F.S: InfoType a dimasukkan ke dalam P dan P menjadi elemen pertama List L } NEXT(P) <- NEXT(Prev) NEXT(Prev) <-P KODE C void insertAfterPtr(ElementPtr Prv, ElementPtr P){ P->Next=Next(Prv); Prv->Next=P; } PRIMITIF void insertLastPtr(List *l, ElementPtr P) ILUSTRASI

Prev

@

P Tahap1

Tahap2

Kondisi Akhir

Tahap 1 : Mengatur NEXT dari P ke element NEXT dari Prev Tahap 2: Mengatur NEXT dari Prev ke P

Prev

@

P

Kondisi Awal

ALGORITMA procedure insertLastPtr(input/output List L, Address P) { I.S: Terdefinisi List L mungkin kosong, terdapat Elemen dengan address P F.S: Element P menjadi element terakhir dari List L } Kamus Lokal : Address Last IF (isEmpty(L)==True) insertFirstPtr(L,P) ELSE {Traversal untuk menuju elemen Akhir, dimana berhenti ketika NEXT(LAST) adalah NULL} LAST <-FIRST(L) WHILE (NEXT(LAST)<>Nil) do LAST <- NEXT(LAST) insertAfterPtr (LAST,P) KODE C void insertLastPtr(List *l, ElementPtr P){ ElementPtr Last; //cek kondisi list apakah kosong atau tidak if (isEmpty(l)==true)//list kosong maka lakukan insert First insertFirstPtr(l,P); else //melakukan iterasi untuk menemukan element terakhir { Last=First(l); while (Last->Next!=NULL) Last=Next(Last); insertAfterPtr(Last,P); } } PRIMITIF void insertLast(List *l, InfoType a); ILUSTRASI ALGORITMA Procedure insertLast(Input/Output List L, InfoType a) { I.S: Terdefinisi List L mungkin kosong, terdapat InfoType a F.S: InfoType a masuk ke dalam data Element P dan Element P menjadi

Last?? Ya

@

P

Kondisi Akhir Last?? Tidak

Tahap1: Mencari posisi Last Tahap2: memenggil insertAfterPtr

Last?? @

P

Kondisi Awal

element terakhir dari List L } Kamus Lokal: Address P Alokasi(P) P->Data=a insertLastPtr(L,P) KODE C void insertLast(List *l, InfoType a){ ElementPtr P; P= createElement(a); insertLastPtr(l,P); } PRIMITIF ElementPtr searchingV1(List *l, char *Nim) ILUSTRASI

ALGORITMA function searchingV1(Input List L, char *Nim)->Address { I.S: Terdefinisi List L mungkin kosong, terdapat data nim yang dicari F.S: Mengembalikan Adress elemen yang dicari bila ada dan Nil bila tidak ada } Kamus Lokal: Address P Boolean status=FALSE IF (isEmpty(L)==TRUE) -> Nil ELSE {Lakukan traversal pencarian pada list} P=FIRST(L) REPEAT IF (P->Data.NIM == Nim) status==TRUE ELSE P <- NEXT(P) UNTIL (status==TRUE) || (P==NULL)

@

Kondisi Akhir

yy zz xx

P P P

Cek apakah P>Data.Nim sama dengan yang dicari, bila tidak loncat kalo bisa

Cek apakah P>Data.Nim sama dengan yang dicari, bila tidak loncat kalo bisa

@

Kondisi Awal

yy zz xx

Cari=”XX”

Cek apakah P>Data.Nim sama dengan yang dicari, bila tidak loncat kalo bisa

P KODE C ElementPtr searchingV1(List *l, char *Nim){ ElementPtr P; boolean status; status=false; puts("Mulai melakukan Pencarian"); if (isEmpty(l)==true){//list kosong jangan lakukan pencarian puts("List Kosong"); return NULL; } else { P= First(l); do{ //bandingkan NIM yang dicari dengan data yang ada printf("%p \n",P); if (strcmp(Nim,P->Data.Nim)==0){ status=true; puts("Found"); } else P=Next(P); } while ((status==false)&&(P!=NULL)); } return P; } PRIMITIF ILUSTRASI

ALGORITMA Procedure viewList(Input List L) { I.S : List L terdefinisi dan mungkin kosong F.S : Informasi pada Elemen dari L ditampilkan } Kamus Lokal: Address P P <-FIRST(L) WHILE (P<>Nil) INFO(P) P <- NEXT(P)

@

Kondisi Akhir

yy zz xx

P P P

Tampilkan info P dan loncat kalo bisa

Tampilkan info P dan loncat kalo bisa

Tampilkan info P dan loncat kalo bisa

KODE C void viewList(List *l){ //iterasi dari awal dan tampilkan printf("Melihat isi list \n"); ElementPtr P; P=First(l); while (P!=NULL){ displayInfo(P->Data); P=Next(P); } }