Elementary Data Structures

Elementary Data Structures

Name: - Sanjyot Sanjay Mankar

Urn no: - 2020-B-03022003

Class: - BCA CTMA

Course Name: - Data structure using C.

Abstract Data Type & Array in C++:

Abstract Data type: -

The Data Type is basically a type of data that can be used in a different computer program. It signifies the type like integer, float, etc, the space-like integer will take 4-bytes, a character will take 1-byte of space, etc.
The abstract data type is a special kind of datatype, whose behavior is defined by a set of values and a set of operations. The keyword “Abstract” is used as we can use these data types, we can perform different operations.
But how those operations are working is totally hidden from the user. The ADT is made of primitive data types, but operation logics are hidden. Some examples of ADT are Stack, Queue, List, etc.

2. Arrays in C: -

The array is a container that can hold a fixed number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array.

Element − Each item stored in an array is called an element.
Index − Each location of an element in an array has a numerical index, which is used to identify the element.

Array Representation: -

Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration.

Fig(1) Array Representation

3.Arrays in C ++: -

C++ provides a data structure, the array, which stores a fixed-size sequential collection of elements of the same type. An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type.
Instead of declaring individual variables, such as number0, number1, ..., and number99, you declare one array variable such as numbers and use numbers[0], numbers[1], and ..., numbers[99] to represent individual variables. A specific element in an array is accessed by an index.
All arrays consist of contiguous memory locations. The lowest address corresponds to the first element and the highest address to the last element.

Declaring Arrays: -

To declare an array in C++, the programmer specifies the type of the elements and the number of elements required by an array as follows −

type arrayName [ arraySize ];

Introduction to stack and queue: -

Implementation of the list with an array:-

This implementation stores the list in an array.
The position of each element is given by an index from 0 to n-1, where n is the number of elements.
The element with the index can be accessed in constant time (ie) the time to access does not depend on the size of the list.
The time taken to add an element at the end of the list does not depend on the size of the list. But the time taken to add an element at any other point in the list depends on the size of the list because the subsequent elements must be shifted to the next index value. So the additions near the start of the list take a longer time than the additions near the middle or end.

2. Introduction to Stack: -

A stack is an Abstract Data Type (ADT), commonly used in most programming languages.

Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack. This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation, and removal operation is called POP operation.

Stack Representation: -

Fig(2) Stack Implementation

Basic Operations: -

push() − Pushing (storing) an element on the stack.
pop() − Removing (accessing) an element from the stack.
peek() − get the top data element of the stack, without removing it.
isFull() − check if stack is full.
isEmpty() − check if stack is empty.

3.Introduction to Queue: -

A queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

Queue Representation:

As we now understand that in the queue, we access both ends for different reasons. The following diagram given below tries to explain queue representation as data structure −

Fig (3) Representation of Queue

Basic Operations:

enqueue() − add (store) an item to the queue.
dequeue() − remove (access) an item from the queue.
peek() − Gets the element at the front of the queue without removing it.
isfull() − Checks if the queue is full.
isempty() − Checks if the queue is empty.

Pointer and References in c++: -

1. Review of Pointer: -

Just like integers and characters, a pointer is a primitive data type in C/C++.
An integer takes up 4 bytes, a character takes up 1 byte, and a pointer takes up 4 bytes on a 32-bit machine (and 8 bytes on a 64-bit machine, but we will assume that we are running on a 32-bit machine for the rest of this discussion).
A pointer is simply a 4-byte quantity that contains a memory address. Here's an example of how you would declare an integer variable, a character variable, and a pointer variable in C:

Fig (3) Intro to pointer
n = 5 means to put an integer value of 5 into the memory location referred to by n. c = 'z' means to put an encoded character 'Z into the memory location referred to by c. p = NULL means to put a value of 0 into the memory location referred to by p since NULL is simply defined as 0.

2. C-Pointers: -

A pointer is a variable whose value is the address of another variable, i.e., the direct address of the memory location. Like any variable or constant, you must declare a pointer before using it to store any variable address. The general form of a pointer variable declaration is −

type *var-name;

Here, type is the pointer's base type; it must be a valid C data type and var-name is the name of the pointer variable. The asterisk * used to declare a pointer is the same asterisk used for multiplication. However, in this statement, the asterisk is being used to designate a variable as a pointer. Take a look at some of the valid pointer declarations −

int    *ip;    /* pointer to an integer */
double *dp;    /* pointer to a double */
float  *fp;    /* pointer to a float */
char   *ch     /* pointer to a character */

Simple Program: -

#include <stdio.h>

int main ()

{

int var =60;

int *ip;

ip = &var;

printf("Address of var variable: %x\n", &var );

printf("Address stored in ip variable: %x\n", ip );

printf("Value of *ip variable: %d\n", *ip );

return 0;

}

After run, this program Output gives like this: -

Address of var variable: cd880e6c

Address stored in ip variable: cd880e6c

Value of *ip variable: 60

3. C-Array of Pointers: -

There may be a situation when we want to maintain an array, which can store pointers to an int or char or any other data type available. Following is the declaration of an array of pointers to an integer −

int *ptr[MAX];

It declares ptr as an array of MAX integer pointers. Thus, each element in ptr, holds a pointer to an int value. The following example uses three integers, which are stored in an array of pointers, as follows −

Simple Program: -

#include <stdio.h>

const int MAX = 3;

int main ()

{

int var[] = {19, 38, 57};

int i, *ptr[MAX];

for ( i = 0; i < MAX; i++)

{

ptr[i] = &var[i];

}

for ( i = 0; i < MAX; i++) {

printf("Value of var[%d] = %d\n", i, *ptr[i] );

}

return 0;

}

After Run this program the Output gives like this: -

Value of var[0] = 19

Value of var[1] = 38

Value of var[2] = 57

Dynamic Memory Allocation: -

Dynamic memory allocation: -

memory is allocated at run time.
memory can be increased while executing program.
used in linked list.

2 . Dynamic memory allocation in C: -

It is possible by 4 functions :

malloc()
calloc()
realloc()
free()

The syntax of malloc() function is given below:

1. ptr=(cast-type*)malloc(byte-size)

Let's see the example of malloc() function.

#include<stdio.h>

#include<stdlib.h>

int main(){

int n,i,*ptr,sum=0;

printf("Enter number of elements: ");

scanf("%d",&n);

ptr=(int*)malloc(n*sizeof(int));

if(ptr==NULL)

{

printf("Sorry! unable to allocate memory");

exit(0);

}

printf("Enter elements of array: ");

for(i=0;i<n;++i)

{

scanf("%d",ptr+i);

sum+=*(ptr+i);

}

printf("Sum=%d",sum);

free(ptr);

return 0;

}

After running this program output gives like this: -

Enter elements of array: 3

Enter elements of array: 10

Sum=30

The syntax of calloc() function is given below:

1. ptr=(cast-type*)calloc(number, byte-size)

Let's see the syntax of realloc() function.

1. ptr=realloc(ptr, new-size)

Let's see the syntax of free() function.

1. free(ptr)

All these 4 functions output is same just changing the function.

Dynamic memory Allocation in C++: -

How dynamic memory really works in C++ is essential to becoming a good C++ programmer. Memory in your C++ program is divided into two parts −
The stack − All variables declared inside the function will take up memory from the stack.
The heap − This is unused memory of the program and can be used to allocate the memory dynamically when program runs.
Many times, you are not aware in advance how much memory you will need to store particular information in a defined variable and the size of required memory can be determined at run time.
You can allocate memory at run time within the heap for the variable of a given type using a special operator in C++ which returns the address of the space allocated. This operator is called new operator.
If you are not in need of dynamically allocated memory anymore, you can use delete operator, which de-allocates memory that was previously allocated by new operator.

New and delete Operators

There is following generic syntax to use new operator to allocate memory dynamically for any data-type.

new data-type;

Here, data-type could be any built-in data type including an array or any user defined data types include class or structure. Let us start with built-in data types. For example we can define a pointer to type double and then request that the memory be allocated at execution time. We can do this using the new operator with the following statements −

double* pvalue  = NULL; // Pointer initialized with null
pvalue  = new double;   // Request memory for the variable

The memory may not have been allocated successfully, if the free store had been used up. So it is good practice to check if new operator is returning NULL pointer and take appropriate action as below −

double* pvalue  = NULL;
if( !(pvalue  = new double )) {
   cout << "Error: out of memory." <<endl;
   exit(1);
}

The malloc() function from C, still exists in C++, but it is recommended to avoid using malloc() function. The main advantage of new over malloc() is that new doesn't just allocate memory, it constructs objects which is prime purpose of C++.
At any point, when you feel a variable that has been dynamically allocated is not anymore required, you can free up the memory that it occupies in the free store with the ‘delete’ operator as follows −

delete pvalue;        // Release memory pointed to by pvalue

Let us put above concepts and form the following example to show how ‘new’ and ‘delete’ work −

#include<iostream>

using namespace std;

int main ()

{

double* pvalue = NULL; // Pointer initialized with null

pvalue = new double; // Request memory for the variable

*pvalue = 29494.99; // Store value at allocated address

cout << "Value of pvalue : " << *pvalue << endl;

delete pvalue; // free up the memory.

return 0;

}

After running this program output gives like this: -

Value of pvalue : 29495

Linked stacks, queues, lists: -
Link 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 as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.

2. Link Stacks: -

instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.

Implementaion of stack in link list in C: -

#include <stdio.h>

#include <stdlib.h>

void push();

void pop();

void display();

struct node

{

int val;

struct node *next;

};

struct node *head;

void main ()

{

int choice=0;

while(choice != 4)

{

printf("\n\nChose one from the below options...\n");

printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");

printf("\n Enter your choice \n");

scanf("%d",&choice);

switch(choice)

{

case 1:

{

push();

break;

}

case 2:

{

pop();

break;

}

case 3:

{

display();

break;

}

case 4:

{

printf("Exiting....");

break;

}

default:

{

printf("Please Enter valid choice ");

}

};

}

void push ()

{

int val;

struct node *ptr = (struct node*)malloc(sizeof(struct node));

if(ptr == NULL)

{

printf("not able to push the element");

}

else

{

printf("Enter the value");

scanf("%d",&val);

if(head==NULL)

{

ptr->val = val;

ptr -> next = NULL;

head=ptr;

}

else

{

ptr->val = val;

ptr->next = head;

head=ptr;

}

printf("Item pushed");

}

void pop()

{

int item;

struct node *ptr;

if (head == NULL)

{

printf("Underflow");

}

else

{

item = head->val;

ptr = head;

head = head->next;

free(ptr);

printf("Item popped");

}

void display()

{

int i;

struct node *ptr;

ptr=head;

if(ptr == NULL)

{

printf("Stack is empty\n");

}

else

{

printf("Printing Stack elements \n");

while(ptr!=NULL)

{

printf("%d\n",ptr->val);

ptr = ptr->next;

}

After run this program output gives like this: -

Chose one from the below options...

1.Push

2.Pop

3.Show

4.Exit

Enter your choice

3. Linked Queus: -

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory.
In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.
Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty.
The linked representation of queue is shown in the following figure.

Implementing link queued in C: -

#include<stdio.h>

#include<stdlib.h>

struct node

{

int data;

struct node *next;

};

struct node *front;

struct node *rear;

void insert();

void delete();

void display();

void main ()

{

int choice;

while(choice != 4)

{

printf("\nMain Menu\n");

printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");

printf("\nEnter your choice =");

scanf("%d",& choice);

switch(choice)

{

case 1:

insert();

break;

case 2:

delete();

break;

case 3:

display();

break;

case 4:

exit(0);

break;

default:

printf("\nEnter valid choice??\n");

}

void insert()

{

struct node *ptr;

int item;

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)

{

printf("\nOVERFLOW\n");

return;

}

else

{

printf("\nEnter value?\n");

scanf("%d",&item);

ptr -> data = item;

if(front == NULL)

{

front = ptr;

rear = ptr;

front -> next = NULL;

rear -> next = NULL;

}

else

{

rear -> next = ptr;

rear = ptr;

rear->next = NULL;

}

void delete ()

{

struct node *ptr;

if(front == NULL)

{

printf("\nUNDERFLOW\n");

return;

}

else

{

ptr = front;

front = front -> next;

free(ptr);

}

void display()

{

struct node *ptr;

ptr = front;

if(front == NULL)

{

printf("\nEmpty queue\n");

}

else

{ printf("\nprinting values .....\n");

while(ptr != NULL)

{

printf("\n%d\n",ptr -> data);

ptr = ptr -> next;

}

After run this program output gives like this: -

Main Menu

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice =

Algorithm Efficiency: -
algorithm efficiency A measure of the average execution time necessary for an algorithm to complete work on a set of data. Algorithm efficiency is characterized by its order.
Typically a bubble sort algorithm will have efficiency in sorting N items proportional to and of the order of N2, usually written O(N2).
This is because an average of N/2 comparisons are required N/2 times, giving N2/4 total comparisons, hence of the order of N2. In contrast, quicksort has an efficiency O(N log2N).
If two algorithms for the same problem are of the same order then they are approximately as efficient in terms of computation. Algorithm efficiency is useful for quantifying the implementation difficulties of certain problems

Searching and Sorting Algorithms: -

1.Searching Algorithm: -

A search algorithm is a step-by-step procedure used to locate specific data among a collection of data. It is considered a fundamental procedure in computing. In computer science, when searching for data, the difference between a fast application and a slower one often lies in the use of the proper search algorithm.
To search an element in a given array, there are two popular algorithms available:

1.Linear Search

2.Binary Search

1]Linear Search

Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
It compares the element to be searched with all the elements present in the array and when the element is matched successfully, it returns the index of the element in the array, else it returns -1.
Linear Search is applied on unsorted or unordered lists, when there are fewer elements in a list.

Features of Linear Search Algorithm

It is used for unsorted and unordered small list of elements.
It has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not bad, but not that good too.
It has a very simple implementation.

2] Binary Search: -

· Binary Search is used with sorted array or list. In binary search, we follow the following steps:
· We start by comparing the element to be searched with the element in the middle of the list/array.
· If we get a match, we return the index of the middle element.
· If we do not get a match, we check whether the element to be searched is less or greater than in value than the middle element.
· If the element/number to be searched is greater in value than the middle number, then we pick the elements on the right side of the middle element(as the list/array is sorted, hence on the right, we will have all the numbers greater than the middle number), and start again from the step 1.
· If the element/number to be searched is lesser in value than the middle number, then we pick the elements on the left side of the middle element, and start again from the step 1.
· Binary Search is useful when there are large number of elements in an array and they are sorted.
· So a necessary condition for Binary search to work is that the list/array should be sorted.

Features of Binary Search

· It is great to search through large sorted arrays.
· It has a time complexity of O(log n) which is a very good time complexity. We will discuss this in detail in the Binary Search tutorial.
· It has a simple implementation.