summary

To summarise what was learnt in class, we studied about linked list and its type, which is single and double, stack and queue concept, moreover we studied about hashing and how it is fast in order to retrieve data, and binary search tree, the summary is below.

link to the coding assignment
https://drive.google.com/open?id=1zQnFNFnsSo1HLUdupK6EomdaTY7KRMLW

Linked list is a data structure that consist of a sequence of data records such that each record there is a field that contain a reference to the next record in the sequence

3 types :-

- single

- double

- multiple

in single list we can create a pointer that can point in one direction, a double linked list we can point to two direction, while a multiple linked list can point to more than two.

code snippet for a double linked list.

in a single linked list we only have one pointer for ex:-

struct tnode *next;

there is 2 methods of a linked list, insert and delete.

in the code snippet we have insert, to insert a new node and free all node starting from the head.

we can free from the head, tail or free a certain type of node. most of the explanation of how these 2 functions work is explained in the screenshot.

Stack concept
data struct which stores data in an ordered matter. It is a linear data structure, elements are added and removed only at one end, which i called top. In a linked list we can use  linked list to implement this data structure, we can push and pop from one end.
operation.
push(x) :- push a new element
pop():- remove an item from the top
top:- reveal the top element
Queue concept
elements are entered through the rear and leave through the front, it follows the FIFO(first in first out) concept.
we can use linked list to implement this data structure.
operation.
push(x):- push a new element through the rear
pop():- pop an element through the front
front():- return or reveal the front item

prefix :- operator is written before operand
infix :- operator is written between operand
postfix :- operator is written after operand

infix =  (10 + 5) * ( 10 - 5 ) / 2
prefix = * + 10 5 / - 5 10 2
postfix = 5 10 + 5 10 - 2 / *

Hashing
hashing is a technique used for storing and retrieving keys in a rapid manner. in hashing a value is transformed into a shorter value in a way in which it represent a key to that specific value, it is used to index and retrieve data in a way that it is faster that to search manually. hashing can also be defined as a concept of distributing keys in a table(array) using a hash function.
Hash function
some method to hash a function includes:-
- mid-square:-
* square the string and then use the appropriate number of bits from the middle of the square to obtain the hash-key
- Division :-
* divide the string using the modulus operator
- folding :-
* partition the string into several parts, then add the part together to obtain the hash key
- digit extraction :-
* predefined the digit of the given number is considered as the hash address
- rotating hash :-
* use any method of hashing then shift the digits to get a new address
Collision
there will be cases in which a certain hash address be similar with another data, it is called collision.
There are two ways we can handle this.
- linear probing :-
* when a collision happen, we should iterate the cell to find a new empty cell, due to iterating, this has a bad search complexity, another way to do this is to,
- chaining :-
* we store each data in a chain(linked list), if there is a collision we iterate through the chain.

I tried to make a hash table with chaining, i may be wrong but its worth taking a look.
https://drive.google.com/file/d/1v00aMBAhcp-G5CCdA32MpioGLjUEOaBz/view?usp=sharing

Tree and Binary Tree
A tree is a non linear data structure that represent the hierarchal relationship among objects.
A tree is a collection of one or more nodes
concept :-
the top is called as the root
a line connecting two nodes is an edge
nodes which don't have children is called a leaf
nodes that have the same parent is called sibling
degree of node is the total sub tree of the node
depth is the max degree of nodes

A binary tree is a rooted tree data structure in which each node has at most 2 children
types :-
- perfect (every leaf have the same depth
- complete (every level is completely filled)
- skewed( in which each binary tree node has 1 child)
- balanced (no leaf is far from the root)
property of the binary tree
maximum number of nodes on level k of a binary tree is 2^k
height of the tree is the total number of levels

implementation

struct node {
    int data;
    struct node *left;
    struct node *right;
    struct node *parent;
};

threaded binary tree concept
in a normal binary tree, nodes contains a null pointer, when null pointers can be used to store a more relevant piece of data, for example these pointer can point to the predecessor or parent. these special pointers are called thread.

advantages
- it enables linear traversal of elements in the tree
- linear traversal eliminates the use of stacks which will consume more memory space and time
- it make ease to find parent without explicitly using the parent pointer
- it enables moving forward or backward.

code for the assignment

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

struct shop{
    char name[30];
    int value;
    int qty;
    struct shop *next;
    struct shop *prev;
}*head,*tail,*curr,*temp;

void push(int value,char *name, int qty){
    curr = (struct shop*) malloc(sizeof(struct shop));
    strcpy(curr -> name, name);
    curr -> qty = qty;
    curr -> value = value;
    if(head == NULL){
        head = tail = curr;
    }
    else if(strcmp(curr -> name, head -> name) < 0){
        curr -> next = head;
        head -> prev = curr;
        head = curr;
    }
    else if(strcmp(curr -> name, tail -> name) > 0){
        curr -> prev = tail;
        tail -> next = curr;
        tail = curr;
    }
    else{
        temp = head;
        while(strcmp(curr -> name, temp -> next -> name) > 0){
            temp = temp -> next;
        }
        curr -> next = temp -> next;
        temp -> next -> prev = curr;
        curr -> prev = temp;
        temp -> next = curr;
    }
    tail -> next = NULL;
    head -> prev = NULL;
}

void popAll(){
    while(head != NULL){
        temp = head;
        head = temp -> next;
        free(temp);
    }
}

int popSpec(char *name){
    if(head == tail){
        curr = head;
        free(curr);
        head = tail = NULL;
        return 1;
    }
    if(strcmp(head -> name, name) == 0){
        curr = head;
        head = curr -> next;
        free(curr);
        head -> prev = NULL;
        return 1;
    }
    else if(strcmp(tail -> name, name) == 0){
        curr = tail;
        tail = curr -> prev;
        free(curr);
        tail-> next = NULL;
        return 1;
    }
    else{
        curr = head;
        while(strcmp(curr -> name, name) != 0){
            if(curr -> next == NULL){
                break;
            }
            curr = curr -> next;
        }
        if(curr -> next == NULL){
            return 0;
        }
        temp = curr -> prev;
        temp -> next = curr -> next;
        curr -> next -> prev = temp;
        free(curr);
        return 1;
    }
    return 0;
}

void cetak(){
    curr = head;
    int i= 1;
    while(curr != NULL){
        printf("%d.) %s $%d %d\n",i , curr -> name, curr -> value, curr -> qty);
        curr = curr -> next;
        i++;
    }
    printf("\n\n");
}

int edit(char *name, int qty){
    if(strcmp(head -> name, name) == 0){
        head -> qty = qty;
        return 1;
    }
    else if(strcmp(tail -> name, name) == 0){
        tail -> qty = qty;
        return 1;
    }
    else{
        curr = head;
        while(strcmp(curr -> name, name) != 0){
            if(curr -> next == NULL){
                break;
            }
            curr = curr -> next;
        }
        if(curr -> next == NULL){
            return 0;
        }
        curr -> qty = qty;
        return 1;
    }
}

int getRandom(){
    int res = 0;
    time_t seconds;
    time(&seconds);
    res += seconds%1000;
    return res;
}

void checkOut(){
    int total = 0;
    curr = head;
    while(curr != NULL){
        total += (curr -> value * curr -> qty);
        curr = curr -> next;
    }
    printf("================================\n");
    printf("Check out bill\n");
    printf("================================\n");
    cetak();
    printf("================================\n");
    printf("total = $%d\n", total);
    printf("================================\n");
    printf("Kindess is free ;)\n\n\n");
    popAll();
}


int main(){
    int dec = 0;
   
    do{
        printf("Welcome to the shopping list!\n");
        printf("1. add new item\n");
        printf("2. edit quantity\n");
        printf("3. delete item\n");
        printf("4. view item\n");
        printf("5. checkout!\n");
        printf("6. exit\n");
        do{
            printf("Choose >> ");
            scanf("%d",&dec);
        }while(dec < 1 || dec > 6);
        if(dec == 1){
            char name[31];
            int qty, price;
            printf("Please name the product : ");
            getchar();
            scanf("%[^\n]", name);
            printf("please input the quantity : ");
            getchar();
            scanf("%d",&qty);
            price = getRandom();
            push(price,name,qty);
            printf("Added succesfully!\n\n\n");
        }
        else if(dec == 2){
            char name[31];
            int flag, qty;
            cetak();
            printf("what is the name of the product that you want to edit?[case sensitive] : ");
            getchar();
            scanf("%[^\n]",name);
            printf("new quantity for the following product : ");
            getchar();
            scanf("%d", &qty);
            flag = edit(name,qty);
            if(flag == 0){
                printf("item input does not exist\n\n\n");
            }
            else{
                printf("edited succesfully!\n\n\n");
            }
        }
        else if(dec == 3){
            int flag;
            char name[31];
            cetak();
            printf("what is the name of the product that you want to delete?[case sensitive] : ");
            getchar();
            scanf("%[^\n]",name);
            printf("%s\n\n", name);
            flag = popSpec(name);
            if(flag == 0){
                printf("item input does not exist\n\n\n");
            }
            else{
                printf("deleted succesfully!\n\n\n");
            }
        }
        else if(dec == 4){
            cetak();
        }
        else if(dec == 5){
            checkOut();
        }
    }while(dec != 6);
    printf("Thanks for using :)\nRemember, kindness is free!");
    return 0;
}