Review Data
Structure
UTS
Linked List
A linked list is a
linear data structure, in which the elements are not stored at contiguous
memory locations. The elements in a linked list are linked using pointers.
These are the advantages of using linked list:
- Dynamic size, so the size can change during run time
- Ease of insertion and deletion
- Efficient memory utilization, no need to pre-allocate memory
- Faster access time
- Linear data structures such as Stack, Queue can easily be implemented
using Linked List
These are the disadvantages of using linked list :
- Use more memory because pointer requires extra
memory for storage
-
No random access
- Reverse traversing is difficult
There
are types of Linked List, which is :
- Singly Linked List
It
is the most common. Each node has data and a pointer the next code
- Doubly Linked List
Add
a pointer to the previous node in a doubly-linked list. Thus, we can go in
either direction, forward and backward
- Circular Singly Linked List
The
last node contains a pointer to the first node. We can have a circular singly
linked list as well as a circular doubly linked list. There is no storing of
NULL values in the list
- Circular Doubly Linked List
It
is similar to a circular single linked list, but the total pointer in each node
here is two pointers. The more complex type of data structure in which a node
contains pointers to its previous node as well to the next node. The circular
doubly linked list doesn't contain NULL in any of the nodes. The last node of
the list contains the address of the first node of the list. The first node of
the list also contain address of the last node in its previous pointer.
Stack & Queue
Stack, in the pushdown stacks only two operations are allowed: push
the item into the stack, and pop the item out of the stack. A stack is a
limited access data structure - elements can be added and removed from the
stack only at the top. push adds an item to the top of the stack, pop removes
the item from the top. A helpful analogy is to think of a stack of books; you
can remove only the top book, also you can add a new book on the top.
Queue, an excellent example of a queue is a
line of students in the food court of the UC. New additions to a line made to
the back of the queue, while removal (or serving) happens in the front. In the
queue only two operations are allowed enqueue and dequeue. Enqueue means to
insert an item into the back of the queue, dequeue means removing the front
item. The picture demonstrates the FIFO access. The difference between stacks
and queues is in removing. In a stack we remove the item the most recently
added; in a queue, we remove the item the least recently added.
Hash & Binary Tree
Hashing is a technique used to identify a specific
object from a group of similar objects. Assume that you have an object and you
want to assign a key to it to make searching easy. To store the key/value pair,
you can use a simple array like a data structure where keys (integers) can be
used directly as an index to store values. However, in cases where the keys are
large and cannot be used directly as an index, you should use hashing.
In hashing, large keys are
converted into small keys by using hash functions. The values are then stored
in a data structure called a hash table.
Hashing is
implemented in two steps
- An
element is converted into an integer by using a hash function. This
element can be used as an index to store the original element, which falls
into the hash table.
- The
element is stored in the hash table where it can be quickly retrieved
using a hashed key.
A good
hashing mechanism is :
- Easy to
compute
- Uniform
distribution
- Fewer
collisions
There is also hash table which
is a data structure that
is used for storing keys or value pairs. With a good hash function then comes
to a good hash table and hashing can work very well.
Binary Tree, tree is a hierarchical data structure. Main uses of trees
include maintaining hierarchical data, provide moderate access and
insert/delete operations. Then comes the binary tree. Binary tree is a tree
that have at most 2 children. Usually, the children are
called left and right children. A tree contains following parts :
- Data
- Pointer to left child
- Pointer to right child
There are several applications of tree
include :
- Manipulate hierarchical data
- Make information easy to search
- Manipulate sorted list of data
- As a workflow for compositing digital image
for visual effects
- Router algorithms
- Form of a multi-stage decision-making
Binary Search Tree (BST)
Binary Search Tree is a
node-based binary tree data structure which has the following properties:
1.
The left subtree of a node contains only nodes with keys lesser than the
node’s key.
2.
The right subtree of a node contains only nodes with keys greater than
the node’s key.
3.
The left and right subtree each must also be a binary search tree.
Search, to search a given key in Binary Search Tree, we first compare
it with root, if the key is present at root, we return root. If key is greater
than root’s key, we recur for right subtree of root node. Otherwise we recur
for left subtree.
Insertion, a new key is always inserted at leaf. We start searching a
key from root till we hit a leaf node. Once a leaf node is found, the new node
is added as a child of the leaf node.
Delete, when we delete a node, three possibilities arise which is :
1. Node to be deleted
is leaf: Simply remove from the tree.
2. Node to be deleted
has only one child: Copy the child to the node and delete the child
3. Node to be deleted
has two children: Find inorder
successor of the node. Copy contents of the inorder successor to the node and
delete the inorder successor. Note that inorder predecessor can also be used.
The
important thing to note is, inorder successor is needed only when right child
is not empty. In this particular case, inorder successor can be obtained by
finding the minimum value in right child of the node.
Here I attach my code for
the program :
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
struct toko{
int qty, price;
char name[100];
toko *next, *prev;
}*head=NULL, *tail=NULL;
toko* createNode(char
*name, int qty, int price){
toko *temp = (toko*) malloc(sizeof(toko));
strcpy (temp->name, name);
temp->qty = qty;
temp->price = price;
temp->prev = temp->next = NULL;
return temp;
}
void pushHead (char *name,
int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
temp->next = head;
head->prev = temp;
head = temp;
}
}
void pushTail (char *name,
int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
void popHead(){
if(!head) return;
else if (head == tail){
toko *temp = head;
head = tail = NULL;
free(temp);
}
else {
toko *temp = head;
head = head->next;
head->prev = NULL;
free(temp);
}
}
void popTail(){
if(!head) return;
else if (head == tail){
toko *temp = head;
head = tail = NULL;
free(temp);
}
else {
toko *temp = tail;
tail = tail->prev;
tail ->next = NULL;
free(temp);
}
}
void pushMid (char *name,
int qty, int price){
if (!head) head = tail = createNode(name, qty, price);
else if (strcmp(name, head->name) < 0)
pushHead(name, qty, price);
else if (strcmp(name, tail->name) > 0)
pushTail(name, qty, price);
else {
toko *temp = createNode(name, qty, price);
toko *curr = head;
while (strcmp(name, curr->name) > 0){
curr = curr->next;
}
temp->next = curr;
temp->prev = curr->prev;
curr->prev->next = temp;
curr->prev = temp;
}
}
void popSearch(char
*name){
if (!head) {
printf("No item found\n");
return;
}
else if (strcmp(head->name, name) == 0) popHead();
else if (strcmp(tail->name, name) == 0) popTail();
else {
toko *temp = head;
toko *curr;
while (strcmp(name, temp->name) < 0){
curr = temp;
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
free(temp);
}
}
int tot=0;
void printAll(){
toko *temp = head;
if(!head){
printf("No item found\n"); return;
}
else{
while (temp){
printf ("item name : %s,
quantity : %d, price each : %d\n", temp->name, temp->qty,
temp->price);
temp = temp->next;
}
}
}
void printCheckout(){
toko *temp = head;
if(!head){
printf("No item found\n"); return;
}
else{
while (temp){
printf ("item name : %s,
quantity : %d, price each : %d\n", temp->name, temp->qty,
temp->price);
tot += temp->price *
temp->qty;
temp = temp->next;
}
}
}
int main(){
char item_Name[100];
int qty, price;
printf("Input item name : ");
scanf ("%[^\n]", &name);
printf("Input item quantity : ");
scanf ("%d", &qty); getchar();
price = rand() % 1000;
pushMid(name, qty, price);
printf("Input success\n");
printf("Press enter to continue...");getchar();
system("cls");
int x = 0;
do
{
printf("1. add another item\n");
printf("2. edit item quantity\n");
printf("3. delete item\n");
printf("4. view\n");
printf("5. checkout\n");
int menu;
printf("Choose menu : ");
scanf("%d", &menu); getchar();
system("cls");
switch (menu)
{
case 1 :
{
printf("Input
item name : ");
scanf
("%[^\n]", &name);
printf("Input
item quantity : ");
scanf
("%d", &qty); getchar();
price = rand() %
1000;
pushMid(name, qty,
price);
printf("Input
success\n");
printf("press
enter to continue...");getchar();
system("cls");
break;
}
case 2 :
{
printf("Input
item name to change the quantity : ");
scanf("%[^\n]",
&name);
printf("Change
quantity to : ");
scanf("%d",
&qty);getchar();
price = rand() %
1000;
popSearch(name);
pushMid(name, qty,
price);
printf("Input
change success\n");
printf("press
enter to continue...");getchar();
system("cls");
break;
}
case 3 :
{
printf("Input
item name to delete : ");
scanf("%[^\n]",
&name);
popSearch(name);
printf("Deletion
success\n");getchar();
printf("press
enter to continue...");getchar();
system("cls");
break;
}
case 4 :
{
printAll();
printf("press
enter to continue...");getchar();
system("cls");
break;
}
case 5 :
{
printCheckout();
printf ("Your
total price : %d\n", tot);
printf ("press
enter to continue...");getchar();
printf ("Thanks
for checking out..");getchar();
return 0;
}
}
}while(x!=4);
return 0;
}
src : everythingcomputerscience, geeksforgeeks, programiz
Comments
Post a Comment