Oke sampailah materi di bagian review materi sebelum UTS, materi UTS nanti akan membahas Linked list Single maupun Doubly;Stack, dan queue; hashing; Tree/Binary Tree; Binary Search Tree.
1. Single Linked List
saya hanya membahas dari segi pengimplementasi saja, okee langsung saja
pertama kita buat Struct data untuk menyimpan data, di Single kita hanya menggunakan next sebagai petunjuk dan head sebagai kepala dan tail sebagai data terakhir.
struct data{
int angka;
char name[100];
data *next;
}*head,*tail ;
Setelah itu membuat memory allocate agar komputer menyediakan memory yang pas dan tidak kurang, dan saat di malloc sebelum nya harus di type casting.
data* newData(char name[],int angka){
data* curr =(data*)malloc(sizeof(data));
curr->angka=angka;
strcpy(curr->name,name);
curr->next=NULL;
return curr;
}
sekarang kita sudah memesan memori ke komputer kita, setelah itu kita buat push Depan,
void pushHead(data *curr){
if(head==NULL){
head=tail=curr;
}else{
curr->next=head;
head=curr;
}
}
penjelasan code ya tersebut adalah kondisi awal data tersebut sama dengan NULL maka head=tail=curr dalam satu tempat, kondisi else ya adalah kita ingin memasukkan data dan menyambungkan data tersebut maka kita membutuhkan curr->next = head, current ke next diubah mejadi head, dan head diubah ke curr.
Setelah itu kita buat push Belakang,
void pushTail(data *curr){
if(head==NULL){
head=tail=curr;
}else{
tail->next=curr;
tail=curr;
}
}
kondisi awal sama seperti push Depan, dan kondisi else ya tail ke next diubah menjadi curr dan tail menjadi curr.
oke lanjut ke Pop/delete
pertama delete Head/depan.
void popHead(){
if(head==tail){
head=tail=NULL;
free(head);
}else{
data *temp = head;
head=head->next;
temp->next=NULL;
free(temp);
temp = NULL;
}
}
kedua delete Belakang/tail
void popTail(){
if(head==tail){
head=tail=NULL;
free(head);
}else{
data *temp=head;
while(temp->next!=tail){
temp=temp->next;
}
free(tail);
tail=temp;
tail->next=NULL;
}
}
dalam implementasikan harus membuat function untuk print sebagai berikut:
void printAll(){
data *temp=head;
while(temp!=NULL){
printf("%d %s\n",temp->angka,temp->name);
temp=temp->next;
}
}
2. Double Linked List
di doubly sedikit berbeda dengan single karena di double ini memiliki tambahan petunjuk prev. oke langsung pengimplementasi saja. sama aja ya harus membuat struct dan malloc (memory alloce), saya di sini langsung membahas ke push dan pop aja.
struct data{
int angka;
char name[101];
data *next, *prev;
}*head,*tail;
data *newData(char name[],int angka){
data *curr =(data*)malloc(sizeof(data));
curr -> angka=angka;
strcpy(curr->name,name);
curr -> prev = curr -> next = NULL;
return curr;
}
push Depan
void pushHead(data *curr)
{
if(head==NULL)
{
head = tail = curr;
}
else
{
head -> prev=curr;
curr -> next=head;
head = curr;
}
}
Push Belakang
void pushTail(data *curr)
{
if(head==NULL)
{
head=tail=curr;
}
else
{
tail -> next=curr;
curr-> prev= tail;
tail = curr;
}
}
Pop Depan
void popHead()
{
if(head==tail)
{
head=tail=NULL;
free(head);
}
else
{
data*temp=head;
head=head->next;
temp->next=NULL;
free(temp);
}
}
Pop Belakang
void popTail()
{
if(head==tail)
{
head=tail=NULL;
free(tail);
}
else
{
data*temp=tail;
tail=tail->prev;
tail->next=NULL;
free(temp);
}
}
Pop Semua nya
void popAll()
{
while(head!=NULL)
{
popHead();
}
}
print data
void printAll()
{
data *temp=head;
while(temp != NULL)
{
printf("%s %d\n",temp->name, temp->angka);
temp = temp->next;
}
}
3. Stack & Queue
a. Stack ini sama aja dengan linked list, ini sistem ya LIFO
sistem ya Last in First Out, maka dari menggunakan push Tail dan pop Tail
b. Queue sistem ya FIFO ( First In First Out), maka menggunakan Push Head dan Pop Head
4. Hashing
materi ini langsung ke implementasi saja
a. hashing secara linear Probling
const int tableSize = 27;
char hashTable[tableSize][100];
int generateKey(char *name)//SmallCase{
int result = name[0] - 'a';
return result;
}
void insert(char *name){
int idx = generateKey(name);
strcpy(hashTable[idx],name);
}
void print(){
for(int i=0;i<tableSize;i++){
printf("[%-2d] : %s\n",i, hashTable[i]);
}
}
b. hashing secara Chaining
struct tnode{
char name[100];
int key;
struct tnode *next;
};
struct hashPool{
struct tnode *head;
struct tnode *tail;
};
const int tableSize = 97;
struct hashPool hashTable[tableSize];
int generateKey(const char *name){
int result = 0;
int len=strlen(name);
for(int i=0;i<len;i++){
result += name[i];
}
return result % tableSize;
}
struct tnode *newNode(const char *name){
struct tnode *curr =(struct tnode*)malloc(sizeof(struct tnode));
strcpy(curr->name,name);
curr->key=generateKey(name);
curr->next=NULL;
return curr;
}
void insert(struct tnode *node){
if(hashTable[node->key].head==NULL){
hashTable[node->key].head=hashTable[node->key].tail=node;
}
else{
hashTable[node->key].tail->next=node;
hashTable[node->key].tail=node;
}
}
void print(){
for(int i=0;i<tableSize;i++){
printf("[%2d] : ",i);
tnode *curr = hashTable[i].head;
while(curr){
printf("%-10s ->",curr->name);
curr=curr->next;
}
printf("NULL\n");
}
}
5. Tre/Binary Tree
struct data{
int value;
data *left;
data *right;
};
struct data *newData(int value){
data *curr=(data*)malloc(sizeof(data));
curr->value=value;
curr->left=NULL;
curr->right=NULL;
return curr;
}
void inOrder(data *root){
if(root){
inOrder(root->left);
printf("%d ",root->value);
inOrder(root->right);
}
}
void preOrder(data *root){
if(root){
printf("%d ",root->value);
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(data *root){
if(root){
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->value);
}
}
struct data *freeAll(data *root){
if(root){
freeAll(root->left);
freeAll(root->right);
free(root);
root=NULL;
}
return root;
}
6. Binary Search Tree
struct data{
int umur;
struct data *left;
struct data *right;
};
struct data* newData(int umur){
struct data* newNode = (struct data*)malloc(sizeof(struct data));
newNode->umur = umur;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct data* insertion(struct data* root,int umur){
struct data* temp = newData(umur);
if(root == NULL) root = temp;
else if(umur > root->umur) root->right = insertion(root->right,umur);
else if(umur < root->umur) root->left = insertion(root->left, umur);
return root;
}
void printAll(struct data* root){
if(root == NULL) return;
printAll(root->left);
printf("%d\n",root->umur);
printAll(root->right);
}
struct data* minValue(struct data* root){
while(root->left!=NULL){
root = root->left;
}
return root;
}
struct data* delete(struct data* root,int umur){
if(root == NULL) printf("Tidak ada data\n");
else if(umur > root->umur) root->right = delete(root->right, umur);
else if(umur < root->umur) root->left = delete(root->left, umur);
else{
if(root->left == NULL && root->right == NULL){
free(root);
root = NULL;
}
else if(root->left == NULL){
struct data* temp = root;
root = root->right;
free(temp);
}
else if(root->right == NULL){
struct data* temp = root;
root = root->left;
free(temp);
}
else{
struct data* temp = minValue(root->right);
root->umur = temp->umur;
root->right = delete(root->right, temp->umur);
}
}
return root;
}
oke selesai materi review kali ini, oke saya kasih contoh kasus atau case
: Shop Case, kita dimampukan untuk membeli barang, mengedit jumlah barang, dan menghapus barang. Semua barang yang kita beli akan otomatis tersorting.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
int totalBarang = 0;
struct Shop{
char barang[100];
int Qty;
int harga;
Shop *prev, *next;
}*head,*tail;
struct Shop *newShop(const char *barang, int Qty)
{
Shop *curr = (Shop *)malloc(sizeof(Shop));
strcpy(curr->barang,barang);
curr->Qty = Qty;
curr->harga = (rand()%100)*1000;
curr->next = NULL;
curr->prev = NULL;
return curr;
}
void pushShop(Shop *curr)
{
if(head==NULL)
{
head=tail=curr;
}
else if (strcmp(curr->barang,head->barang)<0)
{
curr->next = head;
head->prev = curr;
head = curr;
}
else if(strcmp(curr->barang,tail->barang)>0)
{
tail->next = curr;
curr->prev = tail;
tail = curr;
}
else
{
Shop *temp = head;
while(strcmp(curr->barang,temp->barang)>0)
{
temp = temp->next;
}
curr->next = temp;
curr->prev = temp->prev;
temp->prev->next = curr;
temp->prev = curr;
}
}
void update(int ID, int Qty)
{
Shop *temp = head;
int count = 1;
while(count != ID)
{
temp = temp->next;
count++;
}
temp->Qty = Qty;
temp->harga = (rand()%100)*1000;
}
void Delete(int input)
{
int count = 1;
Shop *temp = head;
if(input == 1)
{
if(head==tail)
{
head=NULL;
free(temp);
}
else
{
head = head->prev;
head->prev = NULL;
free(temp);
temp = NULL;
}
}
else if(input == totalBarang && totalBarang != 1)
{
temp = tail;
tail = tail->prev;
tail->next = NULL;
free(temp);
temp = NULL;
}
else
{
while(count != input-1)
{
temp = temp->next;
count++;
}
Shop *curr = temp->next = curr->next;
temp->next->prev = temp;
free(curr);
curr = NULL;
}
totalBarang--;
}
void cetak()
{
int count = 1;
while(head!=NULL)
{
printf("%-15d | %-20s | %-5d | %-7d\n",count,head->barang,head->Qty,head->harga);
head = head->next;
count++;
}
puts("");
}
void buy()
{
system("cls");
char barang[100];
int Qty;
printf("Input Produk Nama: ");
scanf("%[^\n]",barang);getchar();
printf("Input Produk Qty: ");
scanf("%d",&Qty);getchar();
pushShop(newShop(barang,Qty));
printf("Data berhasil ditambahkan\n");
totalBarang++;
getchar();
}
void DeleteBarang()
{
system("cls");
int ID;
cetak();
printf("Input Id to deleted: ");
scanf("%d",&ID);
Delete(ID);
printf("Item berhasil di delete\n");getchar();
}
void editBarang(){
system("cls");
int ID;
int Quality;
cetak();
printf("Input Id to updated: ");
scanf("%d", &ID) ; getchar();
printf("Input new quantity: ");
scanf("%d", &Quality) ; getchar();
update(ID,Quality);
printf("Item berhasil di update\n") ; getchar() ;
}
void PrintHasil()
{
system("cls");
printf("Jumlah Harga\n");
printf("==============\n");
cetak();
printf("Total: \n");
printf("Harga Free\n");getchar();
Shop *temp = head ;
while(temp != NULL){
Shop *curr = temp ;
temp = temp->next ;
free(curr) ;
curr=NULL;
}
exit(0);
}
int main()
{
srand(time(0));
int chose;
do
{
printf("Rizki Ashari Shop\n");
printf("====================\n");
cetak();
printf("1. Buy Item\n");
printf("2. Edit Item Qty\n");
printf("3. Delete Item\n");
printf("4. Print Bill\n");
printf("5. Exit\n");
printf("Choose >> ");
scanf("%d",&chose);getchar();
if(chose == 1)
{
buy();
}
else if(chose == 2)
{
editBarang();
}
else if(chose == 3)
{
DeleteBarang();
}
else if(chose == 4)
{
PrintHasil();
}
else if(chose == 5)
{
printf("Thank You to Order\n");
}
}while(chose!=5);
return 0;
}
sumber materi : PPT BINUS
