Data Structure: April 2020

Halo teman teman sekalian saya Willen Febryanto dan ini adalah rangkuman pelajaran data struct saya selama satu semester.

sebelumnya saya ingin menunjukan program yang saya buat dulu ya.

hallo semuanya, aku ada buat program nih menggunakan double linked List, program Menu di supermarket, programnya adalah murni buatan saya sendiri ya .
berikut adalah Program yang saya buat:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<windows.h>
struct Item{
int kuotaItem;
char namaItem[30];
struct Item* next;
struct Item* prev;
}*head=NULL,*tail=NULL;
int flag=0;
int count=0;
struct Item* createNode(int value, char* namaItem){
struct Item* newNode=(struct Item*)malloc(sizeof(struct Item));
newNode->kuotaItem=value;
strcpy(newNode->namaItem,namaItem);
newNode->next=NULL;
newNode->prev=NULL;
}
void pushHead(int value,char* namaItem){
struct Item* newNode=createNode(value,namaItem);
if(head==NULL){
head=tail=newNode;
}else{
newNode->next=head;
head->prev=newNode;
head=newNode;
}
}

void pushTail(int value,char* namaItem){
struct Item* newNode=createNode(value,namaItem);
if(head==NULL){
head=tail=newNode;
}else{
struct Item* temp=tail;
temp->next=newNode;
newNode->prev=temp;
tail=newNode;
}
}
void pushMid(int value, char* namaItem){
struct Item* newNode = createNode(value,namaItem);
if(head==NULL){
head=tail=newNode;
}else if(strcmp(namaItem,head->namaItem)==-1){
pushHead(value,namaItem);
}else if(strcmp(namaItem,tail->namaItem)==1){
pushTail(value,namaItem);
}else{
struct Item* curr=head;
while(curr!=NULL&&strcmp(newNode->namaItem,curr->namaItem)==1){
curr=curr->next;
}
newNode->next=curr;
newNode->prev=curr->prev;
curr->prev->next=newNode;
curr->prev=newNode;
}

}
void popHead(){
if(head==NULL){
return;
}else if(head==tail){
free(head);
head=tail=NULL;
}else{
struct Item* temp=head;
head=head->next;
head->prev=NULL;
free(temp);
}
}
void popTail(){
if(head==NULL){
return;
}else if(head==tail){
free(head);
head=tail=NULL;
}else{
struct Item* temp=tail;
tail=tail->prev;
tail->next=NULL;
free(temp);
}
}
void popMid(char *namaItem){
if(head==NULL){
return;
}else if(head==tail){
free(head);
head=tail=NULL;
}else if(strcmp(namaItem,head->namaItem)==0){
popHead();
}else if(strcmp(namaItem,tail->namaItem)==0){
popTail();
}else{
struct Item* curr=head;
while(curr!=NULL&&strcmp(curr->namaItem,namaItem)!=0){
curr=curr->next;
}
if(!curr){
printf("data tidak ditemukan\n");
flag=1;
return;
}else{
flag=0;
curr->prev->next=curr->next;
curr->next->prev=curr->prev;
free(curr);
}

}
}
void printItem(){
struct Item* curr=head;
printf("ListofItem\tQty\n");
while(curr!=NULL){
printf("%s\t%d\n",curr->namaItem,curr->kuotaItem);
curr=curr->next;
count++;
}
}
void beli(){
char barang[30];
int jumlahBarang;
printf("Nama Barang:");
scanf("%s",barang);getchar();
printf("Jumlah Barang:");
scanf("%d",&jumlahBarang);getchar();
pushMid(jumlahBarang,barang);
}
void Edit(){
count=0;
char barang[30];
int jumlahBarang;
if(head==NULL){
printf("tidak ada item\n");
}else{
printItem();
printf("Masukan nama Item yang ingin di edit:");
scanf("%s",barang);
popMid(barang);
if(flag==0){
printf("Masukan nama barang:");
scanf("%s",barang);getchar();
printf("Jumlah Barang:");
scanf("%d",&jumlahBarang);getchar();
pushMid(jumlahBarang,barang);
}

}

}
void cekBarang(){
count=0;
if(head==NULL){
printf("Empty\n");
}else{
printItem();
}
}
int Checkout(){
struct Item* curr=head;
srand(time(0));
int x=0;
long long int y=0;
for(int i=0;i<count;i++){
x=rand()%100000+1;
// printf("%s\t%d\t%d\n",curr->namaItem,curr->kuotaItem,x);
y=y+x;
}
printf("Total Harga:\t\t%d\n",y);
return y;
}
void Bill(){
struct Item* curr=head;
srand(time(0));
int x=0;
long long int y=0;
for(int i=0;i<count;i++){
x=rand()%100000+1;
printf("%s\t%d\t%d\n",curr->namaItem,curr->kuotaItem,x);
curr=curr->next;
y=y+x;
}
printf("Total Harga:\t\t%d\n",y);
printf("Kindness Is Free ^_^\n");
}
void Bayar(){
if(head==NULL){
printf("tidak ada barang\n");
}else{
count=0;
int choose=0;
printItem();
Checkout();
printf("1. Bayar sekarang\n");
printf("pilih:");getchar();
scanf("%d",&choose);
Bill();
}

}
void menu(){
puts("1. Beli");
puts("2. Edit");
puts("3. Cek Barang");
puts("4. bayar");
puts("5. Tidak Jadi beli");
}
int main(){
printf("Dikarenakan Co-Vid 19 Mesin scan tidak bisa digunakan, silahkan pilih menu dibawah untuk berbelanja\n");
int pilihan=0;
while(pilihan!=5)
{
menu();

printf("Pilih Nomor Berapa:");
scanf("%d",&pilihan);
switch(pilihan){
case 1:
beli();
system("cls");
break;
case 2:
Edit();
system("cls");
break;
case 3:
cekBarang();
break;
case 4:
Bayar();
pilihan=5;
break;
case 5:
pilihan=5;
break;
Default:
printf("Invalid Number Please Enter Number between 1-5\n");
break;
}

}

return 0;
}

saya mendapatkan referensi membuat program ini dari video video tutorial mengenai data Structure, dan juga dari https://www.geeksforgeeks.org/commonly-used-string-functions-in-c-c-with-examples/ Untuk beberapa function yang saya lupa atau yang saya tidak tau.

berikut adalah rangkuman saya selama setengah semester ini.

What I’ve learned today:

-a circular single linked list is a variation of linked list in which the first element points to the last element and the last element points to the first element. Both singly linked list and doubly linked list can be made into a circular linked list

-In the circular linked list, the last node contains a pointer to the first node and there is no storing of NULL values in the list.

Example:

-Doubly linked list is a linked list data structure with to link, one that contain reference to the next data and one that contain reference to the previous data.

-circular Doubly linked list is similar with circular single linked list, but total pointer in each node here is two pointers

-if we want to insert doubly linked list the first thing that we need to do is we should allocate new node and assign the value to it, and then we connect the node with the existing linked list. This is the example for insertion operation:

insertFirst(data):

Begin

create a new node

node -> data := data

if the list is empty, then

head := node

next of node = head

else

temp := head

while next of temp is not head, do

temp := next of temp

done

next of node := head

next of temp := node

head := node

end if

End

-there are 4 important things when we wanted to delete doubly linked list, first the node to be deleted is the only node in linked list, second the node to be deleted are head, tail or not both of them. This is the example for deleting operation

deleteFirst():

Begin

   if head is null, then

      it is Underflow and return

   else if next of head = head, then

      head := null

      deallocate head

   else

      ptr := head

      while next of ptr is not head, do

         ptr := next of ptr

      next of ptr = next of head

      deallocate head

      head := next of ptr

   end if

End

Referensi:

https://www.tutorialspoint.com/data_structures_algorithms/circular_linked_list_algorithm.htm

SUMMARY:

Stack is a Data structure which is used to store data in a practicular order, stack is a linear data structure which can be implemented by either using an array or a linked list. two operation that can be performed on a stack are: push operation which inserts an element into a stack. Pop operation which removes the last element that was added intp the stack. it follows Last in first out (LIFO) Order

this is the program example that helps me to understand pop and push operation
I got this from https://www.sanfoundry.com/c-program-stack-implementation/
I'm just gonna copy paste the program from the website.

```
#include <stdio.h>
```
```
#define MAXSIZE 5
```
```
 
```
```
struct stack
```
```
{
```
```
    int stk[MAXSIZE];
```
```
    int top;
```
```
};
```
```
typedef struct stack STACK;
```
```
STACK s;
```
```
 
```
```
void push(void);
```
```
int  pop(void);
```
```
void display(void);
```
```
 
```
```
void main ()
```
```
{
```
```
    int choice;
```
```
    int option = 1;
```
```
    s.top = -1;
```
```
 
```
```
    printf ("STACK OPERATION\n");
```
```
    while (option)
```
```
    {
```

        printf ("------------------------------------------\n");

        printf ("      1    -->    PUSH               \n");

        printf ("      2    -->    POP               \n");

        printf ("      3    -->    DISPLAY               \n");

        printf ("      4    -->    EXIT           \n");

        printf ("------------------------------------------\n");

```
 
```
```
        printf ("Enter your choice\n");
```
```
        scanf    ("%d", &choice);
```
```
        switch (choice)
```
```
        {
```
```
        case 1:
```
```
            push();
```
```
            break;
```
```
        case 2:
```
```
            pop();
```
```
            break;
```
```
        case 3:
```
```
            display();
```
```
            break;
```
```
        case 4:
```
```
            return;
```
```
        }
```
```
        fflush (stdin);
```

        printf ("Do you want to continue(Type 0 or 1)?\n");

```
        scanf    ("%d", &option);
```
```
    }
```
```
}
```

/*  Function to add an element to the stack */

```
void push ()
```
```
{
```
```
    int num;
```
```
    if (s.top == (MAXSIZE - 1))
```
```
    {
```
```
        printf ("Stack is Full\n");
```
```
        return;
```
```
    }
```
```
    else
```
```
    {
```

        printf ("Enter the element to be pushed\n");

```
        scanf ("%d", &num);
```
```
        s.top = s.top + 1;
```
```
        s.stk[s.top] = num;
```
```
    }
```
```
    return;
```
```
}
```

/*  Function to delete an element from the stack */

```
int pop ()
```
```
{
```
```
    int num;
```
```
    if (s.top == - 1)
```
```
    {
```
```
        printf ("Stack is Empty\n");
```
```
        return (s.top);
```
```
    }
```
```
    else
```
```
    {
```
```
        num = s.stk[s.top];
```

        printf ("poped element is = %dn", s.stk[s.top]);

```
        s.top = s.top - 1;
```
```
    }
```
```
    return(num);
```
```
}
```

/*  Function to display the status of the stack */

```
void display ()
```
```
{
```
```
    int i;
```
```
    if (s.top == -1)
```
```
    {
```
```
        printf ("Stack is empty\n");
```
```
        return;
```
```
    }
```
```
    else
```
```
    {
```

        printf ("\n The status of the stack is \n");

```
        for (i = s.top; i >= 0; i--)
```
```
        {
```
```
            printf ("%d\n", s.stk[i]);
```
```
        }
```
```
    }
```
```
    printf ("\n");
```
```
}
```

and the Run Time Cases will be like this

STACK OPERATION

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

Enter the element to be pushed

Do you want to continue(Type 0 or 1)?

$ a.out

STACK OPERATION

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

Enter the element to be pushed

Do you want to continue(Type 0 or 1)?

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

poped element is = 34

Do you want to continue(Type 0 or 1)?

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

Stack is empty

Do you want to continue(Type 0 or 1)?

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

Enter the element to be pushed

Do you want to continue(Type 0 or 1)?

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

Enter the element to be pushed

Do you want to continue(Type 0 or 1)?

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

The status of the stack is

Do you want to continue(Type 0 or 1)?

------------------------------------------

1 --> PUSH

2 --> POP

3 --> DISPLAY

4 --> EXIT

------------------------------------------

Enter your choice

========================================================================

There are 3 notation which are Infix, Postfix, and Prefix Notation.

Prefix : operator is written ahead of operator.

Infix : it is characterized by the placement of operators between operands

Prefix : Operator is written after operands

example:

No	Infix Notation	Prefix noatation	Postfix notation
1	a+b	+ab	ab+
2	(a+b)*c	*+abc	ab+*c
3	a*(b+c)	*a+bc	abc+*
4	a/b+c/d	+/ab/cd	ab/cd/+

SUMMARY

Binary tree a tree whose at most 2 children. since each element in a binary tree can have only 2 children, we typically name them the left and right child.

A binary tree contains the Following part:
1. Data
2.Pointer to left child
3.Pointer to right child

Tree vocabulary: the topmost node is called root of the tree The element that are directly under an element are called its children and directly above something its called parents. Element with no children are called leaves.

For example:
A<---- this is a root
/ \
B C
/ \ / \
E F G H<---- leaves

why Binary Tree??
1. if we want to store information that naturally forms a hierarchy then we will use binary tree.
2. trees provide moderate access/search (quicker than linked list but slower than array)
3. Trees Provide moderate insertion /deletion ( Quicker than array and slower than unordered Linked list)
4. Trees don't have an upper limit on number of nodes as nodes are linked using pointers.

main application of trees include:
1. Manipulate hierarchy data
2. Make information easy to search
3. Manipulate sorted Lists of data
4. as a workflow for composing digital images for visual effects.
5. Router algorithms
6. form of a mullti-stage decision -making

this is the example of Binary Tree in C:

#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* right;
struct node* left;
};
//allocate a new node with the given data and NULL left and right Pointers
struct node* newNode(int data){
struct node* node=(struct node*)malloc(sizeof(struct node);
node->data=data;
node->left = NULL;
node->right=NULL;
return(node);
}

int main(){
//make a root
struct node* root =newNode(1);
root->left =newNode(2);
root->right=newNode(3);
root->left->left = new node (4)
//the tree would be like this
/*

1

       /       \ 

      2          3 

    /   \       /  \ 

   4    NULL  NULL  NULL 

  /  \ 

NULL NULL 

*/

return 0;
}

Hashing

Hash table is a data structure that stores data in an associative. in a hash table data is stored in an array format, where each data value has its own unique index value.
Hashing is a technique to convert a range of key values into a range of index of an array
there are 3 basic operations for hash table:
1. search-searches an element in a hash table.
2. insert- inserts an element in a hash table.
3. delete - Deletes an element from a hash table.

I got this code from: https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

hash fucntion will return integer 0-19

vector <string> hashTable[20];
    int hashTableSize=20;

insert code

void insert(string s)
    {
                // Compute the index using Hash Function
        int index = hashFunc(s);
        // Insert the element in the linked list at the particular index
        hashTable[index].push_back(s);
    }

search code

void search(string s)
    {
        //Compute the index by using the hash function
        int index = hashFunc(s);
        //Search the linked list at that specific index
        for(int i = 0;i < hashTable[index].size();i++)
        {
            if(hashTable[index][i] == s)
            {
                cout << s << " is found!" << endl;
                return;
            }
        }
        cout << s << " is not found!" << endl;
    }

Algoritma hash digunakan dalam block chain untuk memastikan data yang dituliskan valid, sehinggga perubahan data secara sepihak akan sulit dilakukan. terutama jika block chain diimplementasikan pada sistem terdistribusi dengan konsensus tertentu, jika ada perubahan data pada suatu blok akan menghasilkan hash yang berbeda sehingga blok blok selanjutnya menjadi tidak valid.
teknologi teknologi block chain yang sekarang diketahui masih menggunakan fungsi hash yang lama, contohnya bitcoin yang masih menggunakan SHA-12, ada beberapa algoritma hash yang baru dan cukup populer yaitu KECCAK dan BLAKE2, kedua algoritma ini merupakan finalis dalam penentuan SHA-3

Thank you ^_^

Data Structure

Selasa, 07 April 2020

Summary in this semester