Review

Data Structures means of organizing and storing data in computers so that we can perform operations on stored data more efficiently.

Common example of data structures :

1.     Array               : Structure which hold items of the same data

2.     Linked list      : Structure that link items in linear order

3.     Stacks             : Structure that do Last In First Out to it’s element

4.     Queues                        : Structure that do First In First Out to it’s element

5.     Hash Tables    : Structure that stores value with its key

6.     Binary Trees   : Structure that stores value in sorted order

Array

Structure that stores items of same data type, can be array of int, float, string or even array of arrays

Array Operations:

·       Traverse          : Go through elements and print them

·       Search             : Search for an element in the array (by value or index)

·       Update            : Update the value of an existing element by index

Linked List

Structure that consists of items in linear order which are linked to each other so that you must access data sequentially and random access is not possible.

Attributes of linked list:

·       Each elements known as nodes

·       Each node has a key and pointer to its successor, known as next

·       The first nodes, known as head

·       The last nodes, known as tail

Types of linked list

·       Single linked list         : Can be traverse forward direction only

·       Double linked list       : Can be traverse both forward and backward direction

·       Circular linked list      : Linked list where head points to tail and tail points to head

Linked list operations

·       Search : Find the first element with the given key by simple linear search

·       Insert   : Insert a key to the linked list. Can be done by inserting at the beginning, middle, or at the end.

·       Delete : Delete a key from the linked list. Can be done by deleting from the beginning, middle, or from the end.

Stacks

Stacks is a LIFO which its element placed at last can be accessed at first.

Stack Operations:

·       Push      : Insert an element on to the top of the stack

·       Pop        : Delete the topmost element and return it

·       Peek      : Return the top element of stack without deleting it

·       isEmpty : Check if the stack is empty

·       isFull     : Check if the stack is full

Queues

Queues is a FIFO which its element placed at first can be accessed at first.

Queue Operations:

·       Enqueue          : Insert an element to the end of the queue

·       Dequeue          : Delete an element from the beginning of the queue

Hash Tables

Structure that stores values with its keys. Usually used if the table is very huge with so many records and may be impractical or even impossible to be stored.

Hash Function

Hash function is used to overcome direct addressing problem, a value with key k is stored in the slot k so we can find out value more easily.

Binary Trees

Binary tree is a structure where data is organized in a hierarchical structure and stores values in sorted order.

Binary tree attributes:

·       Key     : the value stored in the node

·       Left     : the pointer to the left child

·       Right   : the pointer to the right child

·       P          : the pointer to the parent node

 Linklist Example

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

struct data{
char name[100];
int quantity;
struct data *next;
struct data *prev;
};

typedef struct data dt;

dt *head=NULL, *tail=NULL;

void table(){
dt *curr = head;
if(curr != NULL){
printf("===========================\n");
printf("| Product         | Qty   |\n");
printf("===========================\n");
while(curr!=NULL){
printf("| %-15s | %5d |\n",curr->name,curr->quantity);
curr = curr->next;
}
printf("===========================\n\n");
}
}

void pMenu(){

table();
printf("1. Add Cart\n");
printf("2. Edit Cart\n");
printf("3. Delete Cart\n");
printf("4. Checkout\n");
printf("Choose >> ");
}

dt input(){
dt in;
getchar();
printf("Type Product Name: ");
scanf("%[^\n]",in.name);getchar();
printf("Quantity: ");
scanf("%d",&in.quantity );getchar();

return in;
}

dt* getNode(char nama[]){
dt *search;
search = head;
while(search->name != NULL){
if(strcmp(search->name,nama)==0) break;
search = search->next;
}
return search;
}

dt* getPrevNode(dt *search){
dt *temp;


temp = head;
while(temp->next != search){
temp = temp->next;
}
return temp;
}
void add(dt in){
dt *node = (dt*) malloc(sizeof(dt));
*node = in;
node->next = NULL;
node->prev = NULL;
if(head==NULL){
head = tail = node;
}else if(strcmp(node->name,head->name)<0){
node->next = head;
head->prev = node;
head = node;
}else if(strcmp(node->name,tail->name)>0){
tail->next = node;
node->prev = tail;
tail = node;
}else{
dt *curr;
curr = head;
while(strcmp(curr->next->name , node->name)<0){
curr = curr->next;
}
node->next = curr->next;
node->prev = curr;
curr->next->prev = node;
curr->next = node;
}
}

void edit(){
char nama[100];
int qty;
printf("Product you want to edit: "); getchar();
scanf("%[^\n]",nama);
printf("Quantity : ");getchar();
scanf("%d",&qty);
dt *search;
search = getNode(nama);

if(search==NULL) printf("No data found\n");
else {
search->quantity = qty;
}
}

void del(){
dt *search;
char nama[100];
int qty;
printf("Product you want to delete: ");getchar();
scanf("%[^\n]",nama);

search = getNode(nama);
if(search == NULL) printf("No data found");
else{
if(strcmp(head->name,nama)==0){
head = head->next;
free(search);
}else if(strcmp(tail->name,nama)==0){
dt *temp;
temp = getPrevNode(search);
tail = temp;
tail->next = NULL;
free(search);
}else{
dt *temp;
temp = getPrevNode(search);
temp->next = search->next;
search->next->prev = temp;
free(search);
}
}

}

int main(){

int menu;

do{
pMenu();
scanf("%d",&menu);
if(menu==1){
dt in = input();
add(in);
}else if(menu == 2){
edit();
}else if(menu == 3){
del();
}else if(menu == 4){
table();
int e = (rand() % (1000000000 - 0 + 1) + 0);
printf("Price : %d\n\n",e );getchar();
printf("Checking out...\n\n");
printf("Enter to continue");
getchar();
printf("\n\n======================\n");
printf("|        BILL        |\n");
printf("|                    |\n");
printf("|  Kindness is Free  |\n");
printf("|                    |\n");
printf("======================\n");
}

}while(menu!=4);


return 0;
}