Data Structure -Intro , algorithms , analysis & types

Data structure is a format & branch of computer science used for data handling , organizing , managing and storing of data in different ways .

The problems are solved using algorithms in data structure .

The algorithms of data structure are performed using C programing .

There different forms and types of data structure for storage of data like array , trees , stack , etc .

Algorithm : Algorithms are sequential set of instructions which is used to sole a problem .

Attributes of algorithms :

  • correctness 
  • Clarity
  • Elegance
  • Efficiency 

Example : Write an algorithm t find volume area of a cylinder .

volume=27*r*r*h

Solution :

Step 1 : Start

Step 2: read r

Step 3 : read h

Step 4 : Calculate s=r*r

Step 5 : Calculate x=27*s

Step 6 : Calculate a=x*h

Step 7 : print a

Step 8 : Stop

 

Example : Write an algorithm to check if the given no is palindrome or not .

(Palindrome number e.g 121 , 434 , 545 , 010)

Solution :

Step 1 : Start

Step  : read number

Step 3 : let temp=no & mirror=0

Step 4 : Repeat steps 4 & 5 until temp is not equal to 0

Step 5 : calculate mirror=temp mod 10 + mirror*10

Step 6 : Calculate temp=temp div 10

Step 7 : if no=mirror then print "Number is palindrome"

Step 8 : if no is not=mirror then print "number s not palindrome"

Step 9 : stop 

 

Performance of Algorithm :

Let's see how to check the performance of an algorithm 7 check which algorithm is best .It has two ways to find the performance of an algorithm 

  1. Space complexity
  2. Time complexity
The process of checking performance and quality of an algorithm is called as algorithm analysis.

1. Space complexity : The amount of space or memory required for performing a task is called as space complexity .
The space complexity measurements can be done as to times i.e. 
  1. Compile time space complexity : The storage required for program execution at compile time .
  2. Run time space complexity : The storage required for execution of program at run time 

2. Time complexity : The total amount of time required for performing a task is called as time complexity .
The number f time the statement is executed is called as its frequency count .

Types of time complexities :
 
  1. Best case time complexity :  It counts minimum time required to perform n tasks 
  2. Worst case complexity : It counts maximum time required for perform tasks
  3. Average case time complexity : It counts total/actual time required for performing task 

OPERATIONS ON DATA STRUCTURE :

  1. Inserting : Adding new data in data structure is called as inserting
  2. Deleting : deleting data from data structure is called as deleting
  3. Sorting : arranging data in some logical order is called as sorting 
  4. Searching : Finding the location of data within data structure is called as searching 
  5. Traversing : Accessing each data exactly once in data structure so that each data item is traversed or visited 
  6. Merging : Combining the data of two different sorted files into a single file is called as merging

ABSTRACT DATA TYPES (ADT) :

It is an mathematical term that creates user defined data types .

The ADT is a useful tool for specifying the logical properties of data type without giving any details about the implementation of operations on that data type.

The above term can be done using dynamic memory allocation functions in c

Memory allocation functions in C :
  1. malloc() : used for allocating memory block at runtime
  2. calloc() : used for allocating memory at runtime
  3. realloc() : used for resize the assigned memory block
  4. free()  : used to delete assigned memory block

TYPES OF DATA STRUCTURE: 



  1. Linear data structure : The data structure which has a specific format or sequence is called as linear data structures
  2. Non-linear data structure : The data structure which has no specific sequence or specific format is called as non-linear data structure .


In the next chapters we will see these types of data structures in detail.

ARRAY : - 

Array is a ordered collection of similar/homogeneous data types which is referred by unique name.

  • We can write & insert data of similar types from starting to end .
  • For example writing data as integer from starting , then to the last we will use integer data type .
  • The size of array is defined using [ ]  . these square brackets are called as subscripts
  • When there is only one [ ] subscript , it mean it is an one dimensional array .
  • when there are two subscripts [ ] [ ] , it is an two dimensional array .
  • When there will be more than two subscripts , then it will be multi-dimensional array .
  • Indexing of array elements always starts from 0 .
  • The 0th position or smallest index is called as lower bound .
  • The highest index is called as upper bound . 

ONE DIMENSONAL ARRAT - 1 D ARRAY : - 


Declaration :

Syntax : 

data_type array_nam[size];

example :

int arr[5];

char str[10];

float arr[10];

 

Initialization :

Syntax :

data_type array_name[size]={values};

Example :

int ar[5]={1,2,3,4,5,6};

char str[10]={'a','b','c','d','e','f'}; Or str[10]="abcdef"

float arr[10]={11.2,45.5,2.9};




                                                 


TWO DIMENSIONAL ARRAY - 2 D ARRAY : - 


Array which has two subscripts of rows & columns is called as two dimensional array.

Declarations :

Syntax :

data_type array_name[row_size][column_size];

Example :

int arr[2][3];

Initialization : 

Syntax :

data_type array_name[row_size][colmn_size]={ {values},{values} } ;

Example :

int arr[2][3]={{1,2,3},{4,5,6}};





MULTI-DIEMNSIONAL ARRAY :-


Array which has more than two subscripts is called as multidimensional array .

Declarations :

          data_type array_name[][][];

Example :

          int arr[2][3][4];



Question : Write program for printing row-major and column-major representation of multidimensional  array .

Solution :

#include<conio.h>
#include<stdio.h>
void main()
{
int a[3][4]
int i,j;
printf("enter 12 elements : ");
for(i=0;i<=2;i++);
   for(j=0;j<=3;j++)
      scanf("%d",&a[i][j]);
printf("\n row-major representation : \n");
for(i=0;i<=2;i++)
{
printf("\n row %d:",i);
for(j=0;j<=3;j++)
printf("%d",a[i][j]);
}
printf("\n column-major representation : \n");
for(i=0;i<=3;i++)
{
printf("\n column %d:",i);
for(j=0;j<2;j++)
printf("%d",a[j][i]);
}
getch();
}


Output :

enter 12 elements : 1 2 3 4  5 6 7 8 9 10 11 12

row-major representation :
 
row 0 : 1 2 3 4 

row 1 : 5 6 7 8 

row 2 : 9 10 11 12

column-major representation :

column 0 : 1 5 9

column 1 : 2 6 10

column 2 : 3 7 11
column 3 : 4 8 12