bab 1 pointer dan array pointer - dewapurnama · pdf filepada int ). sama halnya jika ... int...

Struktur Data of 34

Bab 1 Pointer dan Array

Pointer Dalam bab ini kita akan membahas konsep dasar dari pointer. Bentuk deklarasi dari pointer menggunakan tanda bintang ( * ) contoh: 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 contoh :

Pointer berisi alamat dari variabel

int *countPtr;

float *countPtr;

#include <stdio.h> #include <conio.h> void main(){ int a; float b; int *p; float *q; p = &a; q = &b; clrscr(); printf(“%d\n”,*p); printf(“%f\n”,*q); getch(); }

a

p b

q

Struktur Data 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 Kita mendeklarasikan sebuah array dengan identifier arr1 yang masing-masing elemennya memiliki tipe data int. Mendeklarasikan sebuah array dengan identifier arr2 yang masing-masing elemennya bertipe float dan langsung diinisialisasi ( diberi nilai awal ). 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 pendeklarasian di atas arr4 dideklarasikan sebagai sebuah array berukuran 5 elemen dan bertipe int dan semua elemennya diinisialisasi dengan nilai 0.

int arr1[5];

float arr2[5] = { 1.5, 2.6, 3.7, 4.8, 5.9 };

int arr3[] = { 1,2,3 };

int arr4[5] = {0};

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.

Struktur Data of 34

Hubungan Pointer dan Array Misalkan kita mendeklarasikan sebagai berikut Di sini a dideklarasikan sebagai variabel integer sedangkan arr dideklarasikan sebagai array dari integer. 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 Jika kita ingin menunjuk arr (suatu array) maka tidak menggunakan tanda & Dengan statement di atas maka pointer p akan menunjuk pada elemen pertama dari arr (alamat dari arr[0] ). Hal ini boleh dituliskan sebagai berikut Untuk mencetak seluruh isi elemen dari array dapat melalui pointer maupun array.

int a; int arr[5];

int *p;

p=&a;

p=arr;

p=&arr[0];

#include<stdio.h> #include<conio.h> 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 of 34

Passing Array ke Fungsi 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.

void cetakarray(int arr[],int n){ int i; for(i=0;i<n;i++){ printf(“%d “,arr[i]); } } void main(){ int arr[5]; int i; clrscr(); for(i=0;i<5;i++){ printf(“Masukkan angka ke-%d : “,i+1); scanf(“%d”,&arr[i]); } cetakarray(arr,5); getch(); }

void cetakarray(int *arr,int n){ int i; for(i=0;i<n;i++){ printf(“%d “,arr[i]); } }

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 of 34

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 : Kemudian kita dapat membuat suatu variable bertipe struct orang atau dapat ditulis juga seperti berikut ini

p

arr

int a; float *p; p = &a;

struct orang { char nama[31]; //lebihkan satu untuk karakter null int berat; int tinggi; };

struct orang var;

struct orang { char nama[31]; //lebihkan satu untuk karakter null int berat; int tinggi; } var;

Struktur Data of 34

Pada program ini kita dapat menggunakan variable var yang bertipe struct orang sebagai berikut Cara passing sebuah struct ke fungsi 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.

#include<stdio.h> #include<conio.h> 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(); }

#include<stdio.h> #include<conio.h> 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(); }

Struktur Data 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. 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. 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.

#include<stdio.h> #include<conio.h> 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(); }

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.

Struktur Data 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

Untuk menampung data lebih dari satu, kita dapat menggunakan array dalam program kita. Tapi array memesan memori secara statis, misalkan 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.

n

next

n

next

n

next

n

next

head tail

struct node { int n; struct node *next; }; struct node *head=NULL, *tail,*curr;

Kenapa harus menggunakan linked list ?

int arr[5];

Struktur Data 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.

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. Fungsi untuk menambahkan node baru ke suatu linked list adalah cukup mudah. Fungsi dapat dilihat sebagai berikut.

Kita akan membahas bagian per bagian dari fungsi di atas.

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; }

void clear(void){ curr=head; while(curr!=NULL){ head=head->next; free(curr); curr=head; } }

void main(){ //mulai program … … … clear(); // membebaskan semua memori ( dealokasi ) }

curr = (struct node *)malloc(sizeof(struct node)); curr->n = n;

Struktur Data of 34

malloc digunakan untuk mengalokasi memori sebesar ukuran struct node ( byte(s) ) dan akan ditunjuk oleh pointer curr. Kemudian nilai n akan di varibel n dari node yang ditunjuk oleh curr. malloc digunakan untuk mengalokasi memori sebesar ukuran struct node ( byte(s) ) dan akan ditunjuk oleh pointer curr. Kemudian nilai n akan di varibel n dari node yang ditunjuk oleh curr. Jika head == NULL pada saat head masih NULL atau belum ada data, maka head=tail=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 <conio.h> void main(){ clrscr(); insert(9); insert(8); insert(7); curr=head; while(curr !=NULL ){ printf(“%d “,curr->n); curr=curr->next; } clear(); }

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

n

next

curr

head tail

Struktur Data 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. 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. Perhatikan ada penambahan pada deklarasi, yaitu pointer prev Untuk fungsi clearnya sama. Tetapi untuk insertnya ada beberapa tambahan Sehingga kita dapat mencetak data-data dari node-node pada linked list dari head ke tail maupun dari tail ke head.

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

struct node { int n; struct node *next, *prev; }; struct node *head=NULL, *tail,*curr;

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; // tambahkan baris berikut tail = curr; } tail ->next = NULL; head->prev = NULL; //tambahkan baris berikut }

Struktur Data of 34

mencetak dari head ke tail mencetak dari tail ke head 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 Jadi pada program di atas hanya perlu memodifikasi sedikit. Untuk fungsi-fungsi lengkapnya dari Linked List dapat dilihat di lampiran halaman belakang.

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

curr = tail; while ( curr != NULL ){ printf(“%d “,curr->n); curr=curr->prev; }

tail ->next = head;

head->prev = tail;

void insert ( int n ){ … … tail -> next = head; //ubah pada bagian akhir fungsi insert }

Struktur Data 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 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

push pop

Struktur Data 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. 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. Kondisi awal dari stack. top bernilai -1 menandakan stack kosong. Kondisi pada saat stack penuh adalah jika top bernilai MAXSIZE-1.

#define MAXSIZE 5 int stack[MAXSIZE]; int top=-1;

1

2

3

4

0

top

int isEmpty(void){ return (top==-1); }

int isFull(void){ return (top==MAXSIZE-1); }

void create(void){ top=-1; }

Struktur Data of 34

Fungsi create digunakan untuk mengosongkan stack, dengan cara memberi nilai pada top dengan -1. Fungsi push digunakan untuk menambahkan sebuah integer ke dalam stack. Fungsi pop digunakan untuk mengeluarkan data dari stack. atau

void push ( int n ) { top++; stack[top]=n; }

int pop ( int *n ) { if ( ! isEmpty() ){ *n = stack[top]; top--; return 1; } return 0; }

int pop (void) { if ( ! isEmpty() ){ top--; return stack[top-1]; } return -1; }

Struktur Data of 34

contoh :

#include <stdio.h> #include <conio.h> #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 of 34

Implementasi Stack dengan Linked List

#include <stdio.h> #include <conio.h> #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<n;i++){ printf(“angka ke-%d: “,i+1); scanf(“%d”,&tmp); push(tmp); } //pop semua printf(“Hasil pop: “); while(top!=NULL){ tmp = pop(); printf(“%d “,tmp); } getch(); }

Struktur Data 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 Maka computer akan mengkonversi ke dalam bentuk postfix sebelum dievaluasi

INFIX POSTFIX 5+2 52+ (5+2)*8 52+8* 5+2*8 528*+ (5+2)*(8-1)/2 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

5+2

52+

#include <stdio.h> #include <conio.h> 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 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 of 34

Evaluasi suatu ekspresi postfix

#include <stdio.h> #include <conio.h> 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; }

void main(){ clrscr(); printf(“Masukkan ekspresi (infix): “); scanf(“%s”,infix); getpostfix(infix,postfix); printf(“Hasil Postfix: %s“,postfix); getch(); }

Struktur Data of 34

Queue Menggunakan konsep FIFO ( First In First Out ), di mana data yang pertama masuk adalah data yang pertama kali keluar. Buat fungsi enqueue dan dequeue

struct node { int data; struct node *next; } *head=NULL, *tail, *curr;

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; }

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(); }

Struktur Data of 34

Buat fungsi createnew Implementasi dalam program Implementasi Queue dengan Array

void createnew(void){ curr=head; while(curr!=NULL){ head=head->next; free(curr); curr=head; } head=tail=curr=NULL; }

#include <stdio.h> #include <conio.h> 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(); }

#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 of 34

Circular Queue Menggunakan array untuk implementasi Circular Queue

0 1

5

4

2

3

rear

front

kondisi kosong (rear+1)%MAX=front Kondisi penuh (rear+2)%MAX=front

#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; } }

void dequeue(int *e){ int i; if(!isEmpty()){ *e = queue[front]; for(i=front;i<rear;i++) queue[i]=queue[i+1]; rear--; } }

Struktur Data of 34

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); } }

void dequeue(int *e){ if(!isEmpty()){ *e = queue[front]; front = (front+1)%MAX; } }

Struktur Data 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 cabang-cabangnya. 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 of 34

Pada fungsi delete, jika salah satu node di delete maka semua node turunannya akan di delete juga. 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. Pada fungsi terdapat sedikit perubahan sebagai berikut.

void del (struct node *p){ if(p==NULL) return; del(p->left); del(p->right); free(p); p=NULL; }

struct node { int data; struct node *left,*right,*parent; } *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; 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 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 12

9 1563

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 of 34

Traversal Order Inorder Preorder Postorder

void inorder ( struct node *p ){ if(p==NULL) return; inorder(p->left); printf(“%d “,p->data); inorder(p->right); }

void preorder ( struct node *p ){ if(p==NULL) return; printf(“%d “,p->data); preorder(p->left); preorder(p->right); }

void postorder ( struct node *p ){ if(p==NULL) return; postorder(p->left); postorder(p->right); printf(“%d “,p->data); }

Struktur Data of 34

Lampiran Single Linked List Deklarasi linked listnya Kemudian kita buat pointer penunjuk head, tail, dan curr. Fungsi clear digunakan untuk membebaskan semua memory yang dialokasi denga perintah malloc. ( dealokasi ) 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

struct node { int n; struct node *next; };

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


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 of 34

insert after tail insert before curr insert after curr

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; }

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; }

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 of 34

Fungsi deletenode digunakan untuk menghapus node dari linked list yang ditunjuk oleh curr. Biasanya curr akan diset menunjuk node head setelah penghapusan. Double Linked List Deklarasi linked listnya Kemudian kita buat pointer penunjuk head, tail, dan curr. Fungsi clear digunakan untuk membebaskan semua memory yang dialokasi denga perintah malloc. ( dealokasi ) 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

struct node { int n; struct node *next, *prev; };

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


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; }

Struktur Data of 34

insert before head insert after tail insert before curr

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; }

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; }

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 of 34

insert after curr Fungsi deletenode digunakan untuk menghapus node dari linked list yang ditunjuk oleh curr. Biasanya curr akan diset menunjuk node head setelah penghapusan.

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; }

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 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 Pada program di atas hanya perlu dimodifikasi sedikit. Fungsi clear perlu dimodifikasi sebagai berikut.

tail ->next = head;

head->prev = tail;

void clear(){ curr = head; while ( head != tail ) { head=head->next; free(curr); curr=head; } free(head); head=NULL; }

bab 1 pointer dan array pointer - dewapurnama · pdf filepada int ). sama halnya jika ... int...

Documents