Review

a.      Linked List

Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.

Ada 3 Jenis Linked List :

–Single Linked List :

–Double Linked List

–Circular Linked List

b.      Single Linked List

Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer.

Basic operations single linked list :

·        Insertion

·        Deletion

·        Display

·        Search

·        Delete

Double Linked List

c.      Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya.

Basic operations double linked list :

·        Insertion

·        Deletion

·        Display

·        Search

·        Delete

Code :


#include <stdio.h>
#include<stdlib.h>
#include<string.h>

struct data{
int key;
char name[30];
data *next, *prev;
}*head=NULL,*tail=NULL;

data* newNode(char *name, int key){
data* temp = (data*)malloc(sizeof(data));

temp->key = key;
strcpy(temp->name,name);

temp->next = temp->prev = NULL;

return temp;
}

void pushHead(char *name, int key){
if(!head) head = tail = newNode(name,key);
else {
data* curr = newNode(name,key);

curr->next = head;
head->prev = curr;
head = curr;
}
}

void pushTail(char *name, int key){
if(!head) head = tail = newNode(name,key);
else{
data* curr = newNode(name,key);

curr->prev = tail;
tail->next = curr;
tail = curr;
}
}

void pushMid(char *name, int key){
if(!head) head = tail = newNode(name,key);
else if(strcmp(head->name, name) > 0){
pushHead(name,key);
}
else if(strcmp(tail->name, name) < 0){
pushTail(name,key);
}
else{
data* temp = head;

while(strcmp(name, temp->name) > 0){
temp = temp->next;
}

data* curr = newNode(name,key);

curr->next = temp;
curr->prev = temp->prev;

temp->prev->next = curr;
temp->prev = curr;
}

}

void popHead(){
data *temp;
if(!head) {
puts("There is no data");
return;
}
else if(head == tail){
temp = head;
head = tail = NULL;
}
else {
temp = head;
head = head->next;
head ->prev = temp->next = NULL;
}
free(temp);
}

void popTail(){
data*temp;
if(!head) {
puts("There is no data");
return;
}
else if(head == tail){
temp = head;
head = tail = NULL;
}
else {
temp = tail;
tail = tail->prev;
tail->next = temp->prev = NULL;
}
free(temp);
}

void popSearch(char *name){
if(!head){
printf("No Data!");
}
else if(strcmp(head->name, name) == 0) popHead();
else if(strcmp(tail->name, name) == 0) popTail();
else{
data *curr = head;
while(strcmp(name,curr->name) != 0){
curr = curr->next;
if(curr == NULL){
printf("There is no matching data!");
return;
}
}
curr->next->prev = curr->prev;
curr->prev->next = curr->next;

curr->prev = curr->next = NULL;

free(curr);
}
}

void showData(){
data* curr = head;

while(curr != NULL){
printf("%d %s\n", curr->key, curr->name);
curr = curr->next;
}

}

Hash Table

d.      Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Operasi Pada Hash Tabel :

Ø  insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

Ø  find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

Ø  remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

Ø  getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

 Code :

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

struct Node

{

char name[100];

char age[100];

char key[205];

char NIM[100];

Node* next;

};

Node* tableHead[100];

Node* tableTail[100];

int hashFunction(char key[205])

{

int len = strlen(key);

int total = 0;

for(int a = 0; a < len;a++)

{

total += key[a] * a;

total %= 100;

}

return total;

}

//fungsi untuk membuat Node yang sudah diisi namun tidak ada hubungan apapun

Node* createNode(char name[100], char age[100])

{

Node* temp = (Node*)malloc(sizeof(Node));

strcpy(temp->name, name);

strcpy(temp->age, age);

strcpy(temp->NIM,"1");

//buat key yang merupakan gabungan dari name dan age

sprintf(temp->key, "%s%s", temp->name, temp->age);

temp->next = NULL;

return temp;

}

void pushTail(int hashIndex, Node* newNode)

{

if(tableHead[hashIndex] == NULL)

{

tableHead[hashIndex] = tableTail[hashIndex] = newNode;

}

else

{

tableTail[hashIndex]->next = newNode;

tableTail[hashIndex] = newNode;

}

}

//pakai node yang sudah diisi namun tidak ada hubungan apapun

//dan masukan ke dalam table

void insert(Node* newNode)

{

int hashIndex = hashFunction(newNode->key);

pushTail(hashIndex, newNode);

}

void showAll()

{

for(int a = 0; a < 100;a++)

{

printf("Index %d : ",a);

Node* curr = tableHead[a];

while(curr)

{

printf("[key:%s name:%s age:%s NIM: %s] ->", curr->key, curr->name, curr->age, curr->NIM);

curr = curr->next;

}

printf("\n");

}

}

void updateNIM(char name[100], char age[100], char newNIM[100])

{

char key[200];

sprintf(key, "%s%s", name, age);

int hashIndex = hashFunction(key);

Node* curr = tableHead[hashIndex];

while(curr)

{

if(strcmp(curr->key, key) == 0)

{

strcpy(curr->NIM, newNIM);

break;

}

curr = curr->next;

}

}

Binary Search Tree

e.      Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

Binary Search Tree memiliki 3 operasi dasar :

·        Find(x)     : find value x didalam BST ( Search )

·        Insert(x)   : memasukan value baru x ke BST ( Push )

·        Remove(x)  : menghapus key x dari BST ( Delete )

·        View/Print  :

§  PreOrder : Print data, telusur ke kiri, telusur ke kanan

§  InOrder : Telusur ke kiri, print data, telusur ke kanan

§  Post Order : Telusur ke kiri, telusur ke kanan, print data

Code :

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct Stuff{

int code;

char name[100];

Stuff *left, *right;

} *root;

Stuff *newNode(int code, char name[100]){

Stuff *node = (Stuff*)malloc(sizeof(Stuff));

node->code = code;

strcpy(node->name, name);

node->left = node->right = NULL;

return node;

}

Stuff *insert(Stuff *root, int code, char name[100]){

if(root == NULL)

return newNode(code, name);

else if(root->code > code)

root->left = insert(root->left, code, name);

else

root->right = insert(root->right, code, name);

return root;

}

Stuff *remove(Stuff *root, int code){

if(root == NULL)

return root;

else if(root->code > code)

root->left = remove(root->left, code);

else if(root->code < code)

root->right = remove(root->right, code);

else{

//kalo dia punya 1 anak atau ga punya anak

if(root->left == NULL || root->right == NULL){

Stuff *temp = root->left != NULL?

 root->left : root->right;

//kalo punya 1 anak

if(temp != NULL){

*root = *temp;

}

//kalo tidak punya anak

else{

temp = root;

root = NULL;

}

free(temp);

}

//kalo dia punya 2 anak

else{

Stuff *temp = root->left;

while(temp->right != NULL)

temp = temp->right;

root->code = temp->code;

strcpy(root->name, temp->name);

root->left = remove(root->left, temp->code);

}

return root;

}

}

Stuff *update(Stuff *root, int code, char name[100]){

if(root == NULL)

return root;

else if(root->code > code)

root->left = remove(root->left, code);

else if(root->code < code)

root->right = remove(root->right, code);

else

strcpy(root->name, name);

return root;

}

Stuff *removeAll(Stuff *root){

if(root != NULL){

removeAll(root->left);

removeAll(root->right);

free(root);

}

return NULL;

}

void inOrder(Stuff *root){

if(root != NULL){

inOrder(root->left);

printf("%d %s\n", root->code, root->name);

inOrder(root->right);

}

}

void preOrder(Stuff *root){

if(root != NULL){

                printf("%d %s\n", root->code, root->name);

inOrder(root->left);

inOrder(root->right);

}

}

void postOrder(Stuff *root){

if(root != NULL){

inOrder(root->left);

inOrder(root->right);

                printf("%d %s\n", root->code, root->name);

}

}

AVL Tree

AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

Cara menentukan Height dan Balance Factor :

Height :
– Jika node (root) tidak memiliki subtree heightnya = 0
– Jika node adalah leaf, height =  1
– Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :
-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

Insert:Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

(anggap T adalah node yang harus diseimbangkan kembali)

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation

Gambaran Single Rotation :

Gambaran Double Rotation:

Delete :

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. 

Jika yang dihapus adalah leaf, maka langsung hapus saja. 

Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. 

Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali.

Cara menyeimbangkannya pun sama seperti insertion.