Bab 1 Pointer dan Array Pointer Dalam bab ini kita akan membahas konsep dasar dari pointer. Pointer berisi alamat dari variabel
Bentuk deklarasi dari pointer menggunakan tanda bintang ( * ) contoh: int *countPtr;
countPtr merupakan sebuah pointer bertipe int * ( sebuah pointer yang menunjuk pada int ). Sama halnya jika kita ingin mendeklarasikan pointer yang menunjuk pada float, maka deklarasinya menjadi float *countPtr;
contoh : #include <stdio.h> #include
void main(){ int a; float b; int *p; float *q; p = &a; q = &b;
}
clrscr(); printf(“%d\n”,*p); printf(“%f\n”,*q); getch();
q p
b a
Struktur Data
Page 1 of 34
Array Array merupakan himpunan dari beberapa data yang bertipe sama. Karakteristik dari array adalah : 1. tipe datanya homogen ( sama ) 2. alokasi memorinya bersifat statis 3. random access 4. penempatan secara logic maupun fisik sama Cara mendeklarasikan array adalah sebagai berikut int arr1[5];
Kita mendeklarasikan sebuah array dengan identifier arr1 yang masing-masing elemennya memiliki tipe data int.
float arr2[5] = { 1.5, 2.6, 3.7, 4.8, 5.9 };
Mendeklarasikan sebuah array dengan identifier arr2 yang masing-masing elemennya bertipe float dan langsung diinisialisasi ( diberi nilai awal ).
int arr3[] = { 1,2,3 };
Pada bagian ini kita mendeklarasikan arr3 tanpa menyebutkan berapa jumlah elemennya dengan cara mengosongkan angka di dalam tanda [] dan kemudian langsung diinisialisasi. Maka secara otomatis array tersebut akan berukuran 3 elemen.
pada saat mendeklarasikan sebuah array tanpa memberi nilai di dalam tanda [], harus selalu diinisialisasi. Jika mendeklarasikan array dengan cara tersebut tanpa diinisialisasi akan menghasilkan error.
int arr4[5] = {0};
Pada pendeklarasian di atas arr4 dideklarasikan sebagai sebuah array berukuran 5 elemen dan bertipe int dan semua elemennya diinisialisasi dengan nilai 0.
Struktur Data
Page 2 of 34
Hubungan Pointer dan Array Misalkan kita mendeklarasikan sebagai berikut int a; int arr[5];
Di sini a dideklarasikan sebagai variabel integer sedangkan arr dideklarasikan sebagai array dari integer. int *p;
Lalu kita mendeklarasikan variabel pointer yang bertipe ( int * ) yang berarti bahwa sebuah pointer yang akan menunjuk ke suatu nilai integer. Jika kita ingin menunjuk variable a maka p=&a;
Jika kita ingin menunjuk arr (suatu array) maka tidak menggunakan tanda & p=arr;
Dengan statement di atas maka pointer p akan menunjuk pada elemen pertama dari arr (alamat dari arr[0] ). Hal ini boleh dituliskan sebagai berikut p=&arr[0];
Untuk mencetak seluruh isi elemen dari array dapat melalui pointer maupun array. #include<stdio.h> #include int arr[5]={5,6,7,8,9}; int *p=arr; void main(){ int i; clrscr(); for(i=0;i<5;i++){ printf(“Cetak melalui array: %d ”,arr[i]); printf(“Cetak melalui pointer: %d\n”,*(p+i)); } getch(); }
Struktur Data
Page 3 of 34
Passing Array ke Fungsi void cetakarray(int arr[],int n){ int i; for(i=0;i
void cetakarray(int *arr,int n){ int i; for(i=0;i
Pada passing array ke fungsi pada header fungsi, parameter untuk array dari integer boleh dituliskan pula seperti di atas. ( lihat hubungan array dan pointer ) Perbedaan yang mendasar dari array dan pointer adalah array adalah suatu pointer konstan yang menunjuk pada elemen pertama, dan tidak bias dipindahkan. Sedangkan pointer dapat dibuat menunjuk pada elemen pertama dan dapat dipindah-pindah. int arr[5]; int *p; int i; p = arr; for(i=0;i<5;i++){ printf(“%d ”,*p); p++; } for(i=0;i<5;i++){ printf(“%d “,*arr); arr++; // ERROR – arr adalah pointer konstan }
Struktur Data
Page 4 of 34
p
arr
int a; float *p; p = &a;
Perhatikan potongan program di atas. Statement-statement di atas apakah menghasilkan error. Jelaskan alasanmu !
Struct Struct adalah merupakan tipe data yang dapat didefinisikan sendiri isinya di mana merupakan gabungan beberapa tempat penampung (variabel) data yang dapat berbeda tipe datanya. contoh : struct orang { char nama[31]; int berat; int tinggi; };
//lebihkan satu untuk karakter null
Kemudian kita dapat membuat suatu variable bertipe struct orang struct orang var;
atau dapat ditulis juga seperti berikut ini struct orang { char nama[31]; int berat; int tinggi; } var;
Struktur Data
//lebihkan satu untuk karakter null
Page 5 of 34
Pada program ini kita dapat menggunakan variable var yang bertipe struct orang sebagai berikut #include<stdio.h> #include struct orang { char nama[31]; int berat; int tinggi; } var; void main(){ strpcy(var.nama,”boboho”); var.tinggi = 120; var.berat = 200;
}
printf(“Nama saya %s tinggi saya %d dan berat saya %d”, var.nama, var.tinggi, var.berat ); getch();
Cara passing sebuah struct ke fungsi #include<stdio.h> #include struct orang { char nama[31]; int berat; int tinggi; } var; void cetak(struct orang p ){ printf(“Nama saya %s tinggi saya %d dan berat saya %d”, p.nama, p.tinggi, p.berat ); } void main(){ strpcy(var.nama,”boboho”); var.tinggi = 120; var.berat = 200; cetak(var); getch(); }
Pada program di atas pada saat pemanggilan fungsi cetak mengirimkan parameter berupa var bertipe struct orang. Di dalam fungsi akan diterima oleh p kemudian dicetak.
Struktur Data
Page 6 of 34
Hal ini kurang efektif karena pada saat pemanggilan fungsi dilakukan pengcopyan struct yang cukup besar, berbeda dengan pengiriman data atomic seperti int, float, char, long, double, dan sebagainya. Dalam hal ini kita dapat menggunakan pointer. Perhatikan contoh di bawah ini. #include<stdio.h> #include struct orang { char nama[31]; int berat; int tinggi; } var; void cetak(struct orang *p){ printf(“Nama saya %s tinggi saya %d dan berat saya %d”, p->nama, p->tinggi, p->berat ); } void main(){ strpcy(var.nama,”boboho”); var.tinggi = 120; var.berat = 200; cetak(&var); }
getch();
Program di atas nilai yang di-passing ke fungsi adalah alamat dari var. Kemudian akan langsung ditunjuk oleh sebuat pointer p yang bertipe struct orang *. Untuk mengakses nilai variable nama yang ditunjuk pointer p dengan cara p->nama, demikian pula dengan variable lainnya.
p->n = n;
identik dengan
(*p).n = n;
tidak boleh dituliskan *p.n ( tanpa kurung ), dikarenakan presedensi dari . lebih tinggi daripada * maka seakan-akan dievaluasi sebagai *(p.n). Hal ini akan menyebabkan error.
Karena nilai yang di-passing hanya alamat memori saja. Maka tidak terjadi pengcopyan value dari caller ( pemanggil fungsi ) dengan callee ( yang dipanggil ) sehingga hal ini akan meningkatkan efisiensi.
Struktur Data
Page 7 of 34
Bab 2 Linked list Linked list adalah sejumlah node (simpul) yang dihubungkan secara linier dengan bantuan pointer. Linked list erat kaitannya dengan struct. deklarasi linked list struct node { int n; struct node *next; }; struct node *head=NULL, *tail,*curr;
n
n
n
n
next
next
next
next
head
tail
Kenapa harus menggunakan linked list ? Untuk menampung data lebih dari satu, kita dapat menggunakan array dalam program kita. Tapi array memesan memori secara statis, misalkan int arr[5];
Maka arr akan memesan tempat untuk menampung 5 buah integer. Bagaimana jika suatu saat program membutuhkan tempat untuk menampung lebih dari 5 buah integer. Mungkin bisa saja kita memesan lebih seperti 100 buah elemen array, ataupun 1000 buah elemen array, namun hal itu jelas menggunakan memory resource yang berlebihan dan belum tentu semuanya dipergunakan. Untuk itu berkembang lah konsep linked list, di mana node-node yang ada saling berhubungan satu sama lain. Pointer head dirancang untuk selalu menunjuk ke node yang paling depan sedangkan pointer tail dirancang untuk selalu menunjuk ke node yang paling terakhir. Untuk node yang ditunjuk tail ( node terakhir ) next nya adalah NULL. Struktur Data
Page 8 of 34
Pada pemrograman menggunakan linked list, programmer akan mengalokasikan memori secara eksplisit. Dan programmer harus meng-dealokasikan semua memori yang dipesannya. Jika tidak maka akan mengakibatkan “memory leak”. Untuk itu kita perlu membuat fungsi untuk meng-dealokasikan semua memory yang di pesan. void clear(void){ curr=head; while(curr!=NULL){ head=head->next; free(curr); curr=head; } }
Pastikan anda membuat fungsi clear() ini dan ditempatkan di bagian akhir program. Fungsi ini akan meng-dealokasikan semua memory yang dialokasi sebelumnya dari head sampai tail.
void main(){ //mulai program … … … clear(); // membebaskan semua memori ( dealokasi ) }
Fungsi untuk menambahkan node baru ke suatu linked list adalah cukup mudah. Fungsi dapat dilihat sebagai berikut. void insert ( int n ){ curr = (struct node *)malloc(sizeof(struct node)); curr->n = n;
}
if ( head == NULL ) { head =tail = curr; } else { tail->next = curr; tail = curr; } tail ->next = NULL;
Kita akan membahas bagian per bagian dari fungsi di atas. curr = (struct node *)malloc(sizeof(struct node)); curr->n = n; Struktur Data
Page 9 of 34
malloc digunakan untuk dan akan ditunjuk oleh yang ditunjuk oleh curr. malloc digunakan untuk dan akan ditunjuk oleh yang ditunjuk oleh curr.
}
mengalokasi memori sebesar ukuran struct node ( byte(s) ) pointer curr. Kemudian nilai n akan di varibel n dari node mengalokasi memori sebesar ukuran struct node ( byte(s) ) pointer curr. Kemudian nilai n akan di varibel n dari node
if ( head == NULL ) { head =tail = curr; } else { tail->next = curr; tail = curr; } tail ->next = NULL;
Jika head == NULL pada saat head masih NULL atau belum ada data, maka head=tail=curr head
tail
n
next
curr Jika head tidak NULL maka curr akan ditempatkan di belakang tail ( insert dari belakang ). Berarti setiap penambahan data akan ditempatkan di paling akhir. Dan selalu ingat bahwa pada single linked list, tail->next selalu NULL, menyatakan bahwa setelah node yang ditunjuk tail tidak ada node lagi. contoh : #include <stdio.h> #include void main(){ clrscr(); insert(9); insert(8); insert(7);
}
curr=head; while(curr !=NULL ){ printf(“%d “,curr->n); curr=curr->next; } clear();
Struktur Data
Page 10 of 34
Pada program di atas akan menginsert node baru secara berurutan dengan nilai 9,8,7 kemudian akan menge-set curr mulai dari head selama tidak NULL akan dicetak, setiap looping curr digeser ke next nya. Pada sebelum akhir dari program dipanggil fungsi clear untuk meng-dealokasikan semua memory yang sudak dialokasi sebelumnya dengan malloc. Modifikasilah fungsi insert di atas sehingga setiap kali dilakukan insert node baru, maka data-data dalam linked list harus selalu urut secara ascending
Modifikasilah fungsi insert di atas sehingga setiap kali dilakukan insert node baru, maka data-data dalam linked list harus selalu urut secara descending
Linked list yang baru saja dibahas adalah Single Linked List dari suatu node hany memiliki satu pointer penunjuk ( pointer next pada contoh di atas ). Sekarang kita akan lebih mendalami dan membahas bagaimana membuat Double Linked List. struct node { int n; struct node *next, *prev; }; struct node *head=NULL, *tail,*curr;
Perhatikan ada penambahan pada deklarasi, yaitu pointer prev Untuk fungsi clearnya sama. Tetapi untuk insertnya ada beberapa tambahan void insert ( int n ){ curr = (struct node *)malloc(sizeof(struct node)); curr->n = n;
}
if ( head == NULL ) { head =tail = curr; } else { tail->next = curr; curr->prev = tail; tail = curr; } tail ->next = NULL; head->prev = NULL;
// tambahkan baris berikut
//tambahkan baris berikut
Sehingga kita dapat mencetak data-data dari node-node pada linked list dari head ke tail maupun dari tail ke head.
Struktur Data
Page 11 of 34
mencetak dari head ke tail curr = head; while ( curr != NULL ){ printf(“%d “,curr->n); curr=curr->next; }
mencetak dari tail ke head curr = tail; while ( curr != NULL ){ printf(“%d “,curr->n); curr=curr->prev; }
Jangan lupa untuk menambahkan fungsi clear() juga sebelum akhir program. Circular Linked List Circular linked list dibagi lagi menjadi dua, yaitu Circular Single Linked List dan Circular Double Linked List. Konsep utama nya adalah tail ->next = head;
head->prev = tail;
Jadi pada program di atas hanya perlu memodifikasi sedikit. void insert ( int n ){
}
… … tail -> next = head;
//ubah pada bagian akhir fungsi insert
Untuk fungsi-fungsi lengkapnya dari Linked List dapat dilihat di lampiran halaman belakang.
Struktur Data
Page 12 of 34
Bab 3 Stack dan Queue Stack Dalam bab ini kita akan mempelajari tentang konsep stack. Stack ini menggunakan konsep LIFO ( Last In First Out ), di mana data yang terakhir kali masuk adalah yang pertama kali keluar.
push
pop
push Digunakan untuk menambahkan data ke dalam stack. pop Digunakan untuk mengeluarkan data dari stack. isEmpty Digunakan untuk mengecek apakah stack kosong. Jika kosong akan mengembalikan nilai 1 dan 0 jika tidak. isFull Digunakan untuk mengecek apakah stack penuh. Jika kosong akan mengembalikan nilai 1 dan 0 jika tidak. create Membuat stack baru
Struktur Data
Page 13 of 34
Deklarasi stack dapat dilakukan baik menggunakan array maupun linked list. Pertama-tama kita buat stack dengan menggunakan array terlebih dahulu. Misalkan kita membuat stack dari integer. #define MAXSIZE 5 int stack[MAXSIZE]; int top=-1;
Deklarasi di atas mendeklarasikan stack sebagai suatu array dengan jumlah elemennya 5. Dalam nilai top adalah index paling atas dari stack. Di sini nilai -1 menyatakan belum ada data.
4 3 2 1 0 top
Kondisi awal dari stack. top bernilai -1 menandakan stack kosong. int isEmpty(void){ return (top==-1); }
Kondisi pada saat stack penuh adalah jika top bernilai MAXSIZE-1. int isFull(void){ return (top==MAXSIZE-1); }
void create(void){ top=-1; }
Struktur Data
Page 14 of 34
Fungsi create digunakan untuk mengosongkan stack, dengan cara memberi nilai pada top dengan -1. void push ( int n ) { top++; stack[top]=n; }
Fungsi push digunakan untuk menambahkan sebuah integer ke dalam stack. Fungsi pop digunakan untuk mengeluarkan data dari stack. int pop ( int *n ) { if ( ! isEmpty() ){ *n = stack[top]; top--; return 1; } return 0; }
atau int pop (void) { if ( ! isEmpty() ){ top--; return stack[top-1]; } return -1; }
Struktur Data
Page 15 of 34
contoh : #include <stdio.h> #include #define MAX 5 int stack[5]; int top=-1; int isEmpty(void){ return (top==-1); } int isFull(void){ return (top==MAX-1); } void push(int n){ if(!isFull()){ top++; arr[top]=n; } } int pop(int *n){ if(!isEmpty()){ *n = arr[top]; top--; return 1; } return 0; } void main(){ int i,n; clrscr(); printf(“Masukkan 5 buah angka\n”); for(i=0;i<5;i++){ printf(“angka ke-%d : “,i+1); scanf(“%d”,&n); push(n); } printf(“pop sampai habis. Tekan sembarang tombol\n”); printf(“Hasil pop = “); while( ! isEmpty() ){ pop(&n); printf(“%d”,n); } }
Struktur Data
Page 16 of 34
Implementasi Stack dengan Linked List #include <stdio.h> #include #include <malloc.h> struct node { int data; struct node *prev; } *top=NULL, *curr; void push(int e){ curr=(struct node *)malloc(sizeof(struct node)); curr->data=e; if(top==NULL){ top=curr; top->prev=NULL; }else{ curr->prev=top; top=curr; } } int pop(void){ int hasil=top->data; curr=top; top=top->prev; free(curr); curr=top; return hasil; } //PENGGUNAAN DALAM VOID MAIN void main(){ int n,i,tmp; clrscr(); printf(“Ingin push berapa angka : “); scanf(“%d”,&n); for(i=0;i
}
//pop semua printf(“Hasil pop: “); while(top!=NULL){ tmp = pop(); printf(“%d “,tmp); } getch();
Struktur Data
Page 17 of 34
Aplikasi Stack Salah satu penggunaan stack yang akan dibahas dalam bab ini adalah pengubahan infix menjadi postfix. Pada operasi perhitungan yang dilakukan computer misalkan computer mendapat input 5+2
Maka computer akan mengkonversi ke dalam bentuk postfix sebelum dievaluasi 52+
INFIX 5+2 (5+2)*8 5+2*8 (5+2)*(8-1)/2
POSTFIX 52+ 52+8* 528*+ 52+81-*2/
Algoritma pengubahan infix menjadi postfix dengan bantuan stack 1. jika operand langsung tulis hasil di postfix 2. jika operator jika stack kosong, push while operator <= operator top dan tidak kosong dan operator top bukan ‘(‘ pop end while push operator ke dalam stack 3. jika ‘(‘ push ke dalam stack 4. jika ‘)’ pop sampai ketemu ‘(‘ 5. jika ekspresi habis pop semua #include <stdio.h> #include char infix[100]; char postfix[100]; char stack[100]; int top=-1; void push(char c){ if(!isFull()){ top++; stack[top]=c; } } int pop(char *c){ if(!isEmpty()){ *c=stack[top]; top--; return 1; } return 0; }
Struktur Data
Page 18 of 34
int isEmpty(void){ return (top==-1); } int isFull(void){ return (top==99); } int prec(char c){ switch(c){ case ‘(‘: case ‘)’: return 3; case ‘*’: case ‘/: return 2; case ‘+’: case ‘-‘: return 1; default: return 0; } } void getpostfix(char *input,char *output){ char temp; int i,j=0; for(i=0;input[i];i++){ switch(input[i]){ case ‘(‘: push(‘(‘); break; case ‘)’: while(pop(&temp)){ if(temp==’(‘) break; output[j]=temp; j++; } break; case ‘+’: case ‘-‘: case ‘*’: case ‘/’: while(prec(input[i])<=prec(stack[top])&&!isEmpty()&&stack[top]!=’(‘){ pop(&temp); output[j]=temp; j++; } push(input[i]); break; default: output[j]=input[i]; j++;
}
} } while(!isEmpty()){ pop(&temp); output[j]=temp; j++; }
Struktur Data
Page 19 of 34
void main(){ clrscr(); printf(“Masukkan ekspresi (infix): “); scanf(“%s”,infix);
}
getpostfix(infix,postfix); printf(“Hasil Postfix: %s“,postfix); getch();
Evaluasi suatu ekspresi postfix #include <stdio.h> #include float stack[100]; int top=-1; void push(float c){ top++; stack[top]=c; } float pop(void){ top--; return stack[top+1]; } int evaluation(char *postfix,float *hasil){ int i; float x,y,z; for(i=0;postfix[i];i++){ if(postfix[i]>=’0’ && postfix[i]<=’9’){ push(postfix[i]-‘0’); }else{ y= pop(); x= pop(); switch(postfix[i]){ case ‘+’: z=x+y; break; case ‘-’: z=x-y; break; case ‘*’: z=x*y; break; case ‘/’: z=x/y; break; } push(z); } } if(top==0){ *hasil=stack[top]; return 1; } return 0; }
Struktur Data
Page 20 of 34
void main(){ char input[100]; float result; clrscr(); printf(“Masukkan postfix: “); scanf(“%s”,input); if(evaluation(input,&result)==1){ printf(“hasil = %.2f”,result); }else{ printf(“input tidak valid.”); } getch(); }
Queue Menggunakan konsep FIFO ( First In First Out ), di mana data yang pertama masuk adalah data yang pertama kali keluar. struct node { int data; struct node *next; } *head=NULL, *tail, *curr;
Buat fungsi enqueue dan dequeue void enqueue (int n){ curr=(struct node *)malloc(sizeof(struct node)); curr->data=n; if(head==NULL){ head=tail=curr; }else{ tail->next=curr; tail=curr; } tail->next=NULL; } int dequeue(void){ int hasil=head->data; curr=head; head=head->next; free(curr); curr=head; return hasil; }
Struktur Data
Page 21 of 34
Buat fungsi createnew void createnew(void){ curr=head; while(curr!=NULL){ head=head->next; free(curr); curr=head; } head=tail=curr=NULL; }
Implementasi dalam program #include <stdio.h> #include void main(){ int i; clrscr(); printf(“\nenqueue semua\n\n”); for(i=0;i<20;i++){ enqueue(i*2); }
}
printf(“\ndequeue semua\n\n”); i = dequeue(); while(head!=NULL){ printf(“%d\n”,i); i = dequeue(); } getch();
Implementasi Queue dengan Array #define MAX 5 int queue[MAX]; int front=0, rear=-1; int isEmpty(void){ return (front>rear); } int isFull(void){ return (rear==MAX-1); } void enqueue(int e){ if(!isFull()){ rear++; queue[rear]=e; } }
Struktur Data
Page 22 of 34
void dequeue(int *e){ int i; if(!isEmpty()){ *e = queue[front]; for(i=front;i
Circular Queue front kondisi kosong
0 rear
1
(rear+1)%MAX=front
5
Kondisi penuh 2 4
(rear+2)%MAX=front
3
Menggunakan array untuk implementasi Circular Queue #define MAX 6 int queue[MAX]; int front=0, rear=MAX-1 int isEmpty(void){ return ((rear+1)%MAX==front); } int isFull(void){ return ((rear+2)%MAX==front); } void enqueue(int e){ if(!isFull()){ rear = (rear+1) % MAX; queue[rear]=e; } }
Struktur Data
Page 23 of 34
void dequeue(int *e){ if(!isEmpty()){ *e = queue[front]; front = (front+1)%MAX; } }
Priority Queue Pada queue ini setiap node selain menampung data juga menampung nilai prioritasnya, pada saat dequeue, data yang keluar adalah node dengan nilai prioritas tertinggi atau terendah. Contoh implementasi priority queue dengan linked list di mana data yang keluar adalah yang prioritasnya tertinggi. Di sini kita akan menggunakan fungsi insert untuk menambah node, tetapi akan dimodifikasi sedikit, sehingga setiap data yang diinsert akan urut. struct node { int data; int prioritas; struct node *next; } *head=NULL, *tail, *curr; void enqueue(int data,int prioritas){ struct node *p; curr=(struct node *)malloc(sizeof(struct node)); curr->data=data; curr->prioritas=prioritas; if (head==NULL){ head=tail=curr; }else{ if(prioritas > head->prioritas ){ curr->next=head; head=curr; }else if (prioritas < tail->prioritas ){ tail->next=curr; tail=curr; }else{ for(p=head;p->next->prioritas>prioritas;p=p->next); curr->next=p->next; p->next=curr; } } tail->next=NULL; } void dequeue(int *e){ if(head!=NULL){ *e = head->data; curr=head; head=head->next; free(curr); } } Struktur Data
Page 24 of 34
Bab 4 Tree Dalam bab ini kita mempelajari struktur data yang sangat penting, tree. Dalam konsep tree kita mengorganisasikan data di mana berhubungan oleh cabangcabangnya. Tree adalah kumpulan dari satu atau lebih node yang memiliki 1. terdapat node yang disebut root ( akar ) 2. dan memiliki cabang-cabang node
BINARY TREE Setiap node hanya boleh memiliki anak maksimal 2 node, boleh 0 atau 1 struct node { int data struct node *left,*right; } *root=NULL; void insertleft(struct node *z,int e){ struct node *p; p = (struct node*)malloc(sizeof(struct node)); p->data=e; p->left=p->right=NULL; if ( z == NULL ){ z = p; }else{ z->left=p; } } void insertright(struct node *z,int e){ struct node *p; p = (struct node*)malloc(sizeof(struct node)); p->data=e; p->left=p->right=NULL; if ( z == NULL ){ z = p; }else{ z->right=p; } } Struktur Data
Page 25 of 34
Pada fungsi delete, jika salah satu node di delete maka semua node turunannya akan di delete juga. void del (struct node *p){ if(p==NULL) return; del(p->left); del(p->right); free(p); p=NULL; }
Jika ingin menghapus semua tree dapat dengan cara menghapus root. Pada contoh selanjutnya akan menggunakan multiple linked list, di mana setiap node akan mencatat pula siapa parentnya. struct node { int data; struct node *left,*right,*parent; } *root=NULL;
Pada fungsi terdapat sedikit perubahan sebagai berikut. void insertleft(struct node *z,int e){ struct node *p; p = (struct node *)malloc(sizeof(struct node)); p->data=e; p->left=p->right=NULL; if(z==NULL){ z=p; z->parent=NULL; }else{ z->left=p; p->parent=z; } } void insertright(struct node *z,int e){ struct node *p; p = (struct node *)malloc(sizeof(struct node)); p->data=e; p->left=p->right=NULL; if(z==NULL){ z=p; z->parent=NULL; }else{ z->right=p; p->parent=z; } }
Struktur Data
Page 26 of 34
Bab 5 Binary Search Tree Ini merupakan pengembangan dari binary tree, tetapi disini 1. node kiri ( left ) selalu lebih kecil dari parentnya 2. node kanan ( right ) selalu lebih besar dari parentnya
8 5
3
12
6
9
15
struct node { int data; struct node *left,*right; } *root=NULL; void insert(struct node **p, int e){ if ((**p) == NULL){ (*p) = (struct node*)malloc(sizeof(struct node)); (*p)->data=e; (*p)->left=(*p)->right=NULL; } else if ( e < (*p)->data ) insert(&((*p)->left), e); else if ( e > (*p)->data ) insert(&((*p)->right), e); } void del(struct node *p){ if(p==NULL) return; del(p->left); del(p->right); free(p); p=NULL; }
Struktur Data
Page 27 of 34
Traversal Order Inorder void inorder ( struct node *p ){ if(p==NULL) return; inorder(p->left); printf(“%d “,p->data); inorder(p->right); }
Preorder void preorder ( struct node *p ){ if(p==NULL) return; printf(“%d “,p->data); preorder(p->left); preorder(p->right); }
Postorder void postorder ( struct node *p ){ if(p==NULL) return; postorder(p->left); postorder(p->right); printf(“%d “,p->data); }
Struktur Data
Page 28 of 34
Lampiran Single Linked List Deklarasi linked listnya struct node { int n; struct node *next; }; struct node *head=NULL, *tail,*curr;
Kemudian kita buat pointer penunjuk head, tail, dan curr. Fungsi clear digunakan untuk membebaskan semua memory yang dialokasi denga perintah malloc. ( dealokasi ) void clear(void){ curr=head; while(curr!=NULL){ head=head->next; free(curr); curr=head; } }
Fungsi Insert digunakan untuk menambahkan data pada linked list. Fungsi ini dibedakan lagi oleh letak penempatan data yang baru masuk. Data dapat ditempatkan di : 1. depan sebelum head 2. belakang setelah tail 3. depan sebelum curr 4. belakang setelah curr insert before head void insert ( int n ){ curr = (struct node *)malloc(sizeof(struct node)); curr->n = n;
}
if ( head == NULL ) { head =tail = curr; } else { curr->next = head; head = curr; } tail ->next = NULL;
Struktur Data
Page 29 of 34
insert after tail void insert ( int n ){ curr = (struct node *)malloc(sizeof(struct node)); curr->n = n;
}
if ( head == NULL ) { head =tail = curr; } else { tail->next = curr; tail = curr; } tail ->next = NULL;
insert before curr void insert ( int n ){ struct node *p, *temp; p = (struct node *)malloc(sizeof(struct node)); p->n = n;
}
if ( head == NULL ) { head =tail = curr = p; } else if(curr==head){ p->next=curr; head=curr=p; }else{ for(temp=head;temp->next != curr; temp=temp->next ); temp->next = p; p->next = curr; curr=p; } tail ->next = NULL;
insert after curr void insert ( int n ){ struct node *p, *temp; p = (struct node *)malloc(sizeof(struct node)); p->n = n;
}
if ( head == NULL ) { head =tail = curr = p; } else if( curr == tail ){ curr->next=p; tail=p; }else{ p->next = curr->next; curr->next = p; curr=p; } tail ->next = NULL;
Struktur Data
Page 30 of 34
Fungsi deletenode digunakan untuk menghapus node dari linked list yang ditunjuk oleh curr. Biasanya curr akan diset menunjuk node head setelah penghapusan. void deletenode(void){ struct node *p; if ( curr==head ) head=head->next; else if ( curr == tail ){ for(p=head;p->next != tail; p=p->next ); tail = p; }else{ for(p=head;p->next != curr; p=p->next ); p->next=curr->next; } free(curr); tail->next=NULL; }
Double Linked List Deklarasi linked listnya struct node { int n; struct node *next, *prev; }; struct node *head=NULL, *tail,*curr;
Kemudian kita buat pointer penunjuk head, tail, dan curr. Fungsi clear digunakan untuk membebaskan semua memory yang dialokasi denga perintah malloc. ( dealokasi ) void clear(void){ curr=head; while(curr!=NULL){ head=head->next; free(curr); curr=head; } }
Fungsi Insert digunakan untuk menambahkan data pada linked list. Fungsi ini dibedakan lagi oleh letak penempatan data yang baru masuk. Data dapat ditempatkan di : 1. depan sebelum head 2. belakang setelah tail 3. depan sebelum curr 4. belakang setelah curr
Struktur Data
Page 31 of 34
insert before head void insert ( int n ){ curr = (struct node *)malloc(sizeof(struct node)); curr->n = n;
}
if ( head == NULL ) { head =tail = curr; } else { curr->next = head; head->prev = curr; head = curr; } tail ->next = NULL; head ->prev = NULL;
insert after tail void insert ( int n ){ curr = (struct node *)malloc(sizeof(struct node)); curr->n = n;
}
if ( head == NULL ) { head =tail = curr; } else { tail->next = curr; curr->prev=tail; tail = curr; } tail ->next = NULL; head->prev = NULL;
insert before curr void insert ( int n ){ struct node *p; p = (struct node *)malloc(sizeof(struct node)); p->n = n;
}
if ( head == NULL ) { head =tail = curr = p; } else if(curr==head){ p->next=curr; head=curr=p; }else{ curr->prev->next = p; p->prev=curr->prev; curr->prev = p; p->next = curr; curr=p; } tail ->next = NULL; head->prev = NULL;
Struktur Data
Page 32 of 34
insert after curr void insert ( int n ){ struct node *p, *temp; p = (struct node *)malloc(sizeof(struct node)); p->n = n;
}
if ( head == NULL ) { head =tail = curr = p; } else if( curr == tail ){ curr->next=p; tail=p; }else{ p->next = curr->next; curr->next->prev=p; curr->next=p; p->prev=curr; curr=p; } tail ->next = NULL; head->prev = NULL;
Fungsi deletenode digunakan untuk menghapus node dari linked list yang ditunjuk oleh curr. Biasanya curr akan diset menunjuk node head setelah penghapusan. void deletenode(void){ if ( curr==head ) head=head->next; else if ( curr == tail ) tail=tail->prev; else{ curr->prev->next = curr->next; curr->next->prev = curr->prev; } free(curr); tail->next=NULL; head->prev=NULL; }
Struktur Data
Page 33 of 34
Circular Linked List Circular linked list dibagi lagi menjadi dua, yaitu Circular Single Linked List dan Circular Double Linked List. Konsep utama nya adalah tail ->next = head;
head->prev = tail;
Pada program di atas hanya perlu dimodifikasi sedikit. Fungsi clear perlu dimodifikasi sebagai berikut.
void clear(){ curr = head; while ( head != tail ) { head=head->next; free(curr); curr=head; } free(head); head=NULL; }
Struktur Data
Page 34 of 34
