What is pointer in C ? | Application of pointer | Allocation of pointer | Types of pointer and more

Introduction to pointer 

Pointers are as important part of c language. Pointer provide a powerful and flexible way to manipulate data. To understand pointer we need to understand how computer main memory RAM is organized.

Memory organization :

The computers main memory RAM consist of a large number of sequential storage locations. Each memory location is identified by unique address. The address are numbered sequential for 0 to some maximum number depending upon the memory size. i. e they are positive integer. When we run a program the program code and program data. Occupy some part of the main memory. When we use a variable in a program the compiler sets a side a memory location for that variable. It associates the address with the variable name.

WHAT IS POINTER ?

A pointer is a variable that stores the address of the another variable. i.e it points to the another variable.

APPLICATIONS OF POINTER:

1.The pointer are used to pass the parameter by reference. i.e. the actual argument can be modified.

2. All array are implemented as a pointer in c language.

3. They are used for passing array and string to the function.

4. Pointer are used for dynamic memory allocation where memory is allocated and released for a                variable during run time.

5. All file handling operation are performed using pointer.

6. They are used in complex data structure like  linked list ,tree ,graph etc.

THE BASIC OF POINTER:

1. PONTER DECLARATION:

Since the pointer is a variable it has to declare like any other variable before it can be used.

Syntax:

                        

1. data_type is in c data type. It indicates the type of the variable that the pointer points to.

2. The asterisk(*) is indirection operator.

3. Pointer name is valid C identifire.

2. PONTER DEFINATTION :

The pointer must be assigned the address of the variable before it can be used. The address of the variable is obtained by the address of operator(&) The pointer can be defined by a statement of the form.

Syntax:

                                

E.G: ptr=&n;

assign address of variable n to ptr.

3. POINTER INITIALIZATION:

Assigning an address to a pointer during declaration is called initialization.

Syntax:

                    

E.g: int *ptr=&n 

4. PONTER DEREFERENCING:

To use a pointer it has to declare dereferenced. De-referencing operation accesses the data in the memory address which the operator holds. The Dereferenced operatoris * (indirection operator). It is also called the value at the operator.

syntax :

                                

Example:

int n=20,*ptr;

ptr = &n;

printf("%d",*ptr) // display 20

POINTER ARITHMETICS:

The c language allows the five Arithmetics  operations to be performed on pointers.

1. Increment ++

2. Decrement --

3. Addition +

4. Subtraction -

5. Differencing

1.Increment or Decrement:

when a pointer incremented using ++, The address in the pointer is increment by a sizeof (data_type) the new value to the pointer will be 

            (current address in the pointer) + sizeof(data_type))

Incrementing a pointer to an int will cause its value to be incremented by sizeof(int).

similarly a pointer to a float will be incremented by sizeof(float).

The same concept is apply for decrementing the  pointer i.e if a pointer is decremented it is decremented by sizeof(data_type).

2. Addition and subtraction:

C allows integer to be added to or subtracted for pointer. When a pointer is incremented by an integer i.e. the new value will be 

(current address in pointer ) + i* sizeof(data)type))

Example: int *ptr,n = 20;

ptr = &n;

ptr= ptr+3;

This code will increment the address in the ptr by 3*sizeof(int). If the size of (int) is 2 then the pointer will increment by 6.

Subtraction is performed in the same way.

3. DIFFERENCING:

Differencing is the subtraction of two pointer. The subtraction of two pointer gives the number of element between the two pointer. The result which an integer which is ;

Address in pointer1 - address in poinnter2 / sizeof(data_type)

Example:

int a[5] = {10,20,30,40,50};

int *p,*q;

p = &a[0];

q= &a[3];

printf("%d",q-p);

The output of q-p will be (1006-1000)/sizeof(int). i.e 6/2 = 3.

RELATIONSHIP BETWEEN ARRAY AND POINTER:

Array and pointer are very closely related. All array are implemented as pointer in 'C'. The array name is a constant pointer and it is stores th base address of the array.

int a[5];

here a is an array name and it is also a pointer. It stores the base address of the array i.e &a[0]

An array operation is converted to corresponding pointer operation. The C compiler internally convert the subscripted notation a[i] to the form *(a+i).

    a[i] = *(a+i)

Dynamic memory allocation :

When variable are declared in a program, the compiler calculates the size of variable and allocates the memory to the variable. This method is called static memory allocation. The amount of memory required is calculated during compile time. In case of array the size of the array has to be declared at the beginning. In many cases a user does not know how many element are to be put. In such a case memory is either wasted if the size is specified is  very large or enough memory is not allocated if the size specified is smaller than required.

In the dynamic memory allocation method we can allocate and de-allocate memory whenever required. Dynamic memory allocation means allocating memory at run-time.

C-provide the four memory allocation and de-allocation functions. They are declared in stdlib.h.

1. malloc:- Allocates requested the number of bytes and returns the pointer to the first byte.

2. calloc:-This also allocates memory for a group of objects, initializes them zero  and returns a pointer                 to the first byte.

3. realloc:-It changes the size of previously allocated block of memory and returns the pointer to the                     block.

4. free:-Release or free previously allocated space.

ALLOCATION:

Two functions are used to allocates the block of memory dynamically: 

These are:

1. malloc allocation :- The allocation function is used to allocate memory aa single block of memory specified size. The malloc() function allocates the size number of bytes of 

storage and returns the a pointer to the first byte. It returns NULL if allocation is unsuccessful or if size is 0. 

The prototype of malloc is:

                                        

Usage: pointer = (type *)malloc(number_of_bytes);

2. calloc allocation : The calloc function() is similar to malloc. It allocates a single memory block of the specified  size and also initialize the byte is 0. 

The Prototype is :

                                    

Difference between malloc and calloc:

1. malloc require one argument   i.e total number of bytes to be allocated. calloc requires the two arguments- the number of objects and size of each object.

2. Memory allocates by malloc contain garbage value. i.e malloc does not initialize the memory whereas calloc() initialize the  memory to 0.

3. Reallocation : 

Reallocation means the changing the size of allocated block of memory. The realloc() function is used to reallocate memory for a block which was dynamically allocated memory using malloc() or calloc().

Prototype of reallocation:

                                            

ptr  points to the original block, size is the required new size in bytes:

1. If ptr is NULL realloc acts like malloc and returns a pointer to it.

2. If argument size is 0, the memory that the ptr points to is freed and function returns NULL.

3. If sufficient space exits to expand memory block, additional memory is allocated and function returns ptr.

4. If sufficient space does not exist to expand the current block, a new block of the same size is allocated existing data coppied in to it. old block is freed and 

a pointer  to the new block is returned.

5. If memory is insufficient for reallocation , the function returns the NULL and the old block  remains unchanged. 

5.Freeing or De-allocating memory:

The dynamically allocated memory is taken from the dynamic memory pool(heap) that is avialble to the program. After the program finishes using that memory block, it should be freed to make memory available for future use. The free() function is used to release the memory  that was allocated by malloc() or calloc() or realloc().

Prototype of free allocation:

                                    

Memory leak and dangling pointer:

Memory leak:

Memory leak occures when there is dynamically allocated memory area in a heap but no pointer vairable pointing to the memory. A memory leak is memory which hasn't been freed and there is no way to access it. This usually happens when a pointer which was the only reeference to the dynamically allocated memory location points somewhere else now.

Example:

int *ptr1 = (int *)malloc(10);

int * ptr2 = (int *)malloc(20);

ptr1 = ptr2;

here the first block of 10 bytes does not have any pointer pointing to it anymore. Hence it is a memory leak.

Dangling pointer:

When there is a pointer variable which holds the address of a memory block but there is no memory in heap, the pointer is dangling pointer. A dangling pointer is the  reverse of the memory leak. When you free an area of memory but still keep a pointer to it that the pointer is dangling.

Example: int *ptr = (int *)malloc(10);

printf("Address in ptr = %u",ptr);

free(ptr);

printf("Address in ptr =%u",ptr);

ptr = NULL; 

TYPES OF PPOINTER IN C :

1. NULL POINTER: A NULL is a pointer which is pointing to nothing. Usually pointers are initialized                                    in the begining to NULL indicates the it does not have any valid address.

2. DANGLING POINTER: A pointer pointing to a memory location that has been deleted is called                                                     dangling pointer.

3. GENERIC POINTER: When a pointer is declared as type void it is known as a generic pointer. this                                              pointer can not be used directly to points to any element i.e it can not be de-                                            referenced. This pointer can be typecast to any other pointer type. Hence it                                             is called the generic pointer.

4. WILD POINTER: A pointer which has not been initialized to anything is known as a wild pointer. A                                   wild pointer points to some random memory location.

5. NEAR POINTER : A near pointer can stores the 16 bit address which can points to only 64KB data                                        segments or segment number 8 is known as near pointer. It can not access the                                        data beyond the data segment to access data like graphics video memory, text                                        video  memory, etc. size of near pointer is two bytes.

6. FAR POINTER : A pointer which can point or access the while memory if RAM i.e all 16 segment is                                 known as fat pointer. Size of far pointer is 4 bytes or 32 bit. In case of far pointer a                                 segment is fixed. 

7. HUGE POINTER : A pointer which can point or access the whole the residense memory of RAM i.e.                                     which can access all 16 segments is known as huge pointer. Size ofof the far                                             pointer is 4 bytes or 32 bit. In huge pointer the segment part can be modified.

8.COMPLEX POINTER : Multilevel pointer, pointer to function, pointer to array function, pointer to                                               multidimensional array, pointer in nested in structure or union etc. are                                                       complex pointers.

Read More

linked list in C | and their functions in data structure

 linked list :

a linked collection of data element which are stored at ranf=dom memory location and linked to one another the order among element is given by mean of links i e each item is linked to another item 

types of linked list 

1. singly linked list 

2. doubly llinked list 

3. singly circular linked list 

doubly circular linked list

1. singly linked list :

Each node in the list contain only one pointer which points to the next  node of the list The pointer in the last node stores NULL

Node structure :

 struct node                         

{

int info;

struct node next;

}

2. Doubly linked list :

Each node in the list contain two pointers on pointing to the previous node and the other pointing to the next node this list is used when we want to traverse the list in both directions.

Node structure:

struct node 

{

int info;

struct node *prev, *next;

};

3. Singly circular linked list :

This is a singly linked list in which the last node points to the first node . i . e it contain the address of the first node. 

4. Doubly circular linked list :

This is a doubly linked list in which the last node points to the first  and the first node points to the last .

operations on linked list :

teh various operation that can be performed on the linked list :

1, CREATE :  create a list of n nodes.

2. TRAVERSE : Visit each node of the list .

3. LENGTH :  Count the total numbers in the list.

4. INSERT : A node can be inserted at the beginning at end and in between the two nodes 5;

5. DELETE: The deletion  may be done either position wise or element wise .

6.SEARH : This process searches for a specific element in the list.

7 REVERSE: This process reverse the order of node in the list.

8. CONCATENATE: This operation apends the node of the second list of the end of the first list i . e it join two lists .

9. MERGE: This operation merge two sorted list in to a third list such that the third list is also in sorted order.

Read More

How to use Keil u vision 3. | interfacing 8051 microcontroller

 How to use Keil u vision 3.  for interfacing 8051 microcontroller   : 

1. Open keil u Vision 3. 

2. Click on Project > New uVision Project >

3. Create New Folder in my document by your name and give some name, e.g. ags

 

4. Save file by name of application, e.g. lcd. It automatically saves with .uv2 extension.

 5. Select CPU >NXP(founded by phillips) > P89V51RD2

 6. Create new file. 

7. Write program and save with .c extension. e.g. lcd.c.

8. In project workspace > target 1 > source group 1 > add files to group ‘source group1’. 

9. Click on filename. E.g. traffic > add > close. 

10. Right click on target 1 > option for ‘target 1’ a. target > set XTAL (MHz) =12 b. output – click on create Hex file. c. ok.

11. Build target. It shows errors and warnings and creates hex file in folder. e.g. ags.hex.

 12. Connect the 89V51RD2 Embedded Trainer Kit to PC.

 13. Set the switches 1 to 3 to HIGH on SW1. 

14. Set the switch SW4 and switch ON SW3. 

15. Open ECE Flash and browse the hex file from folder and burn hex file into microcontroller by Clicking on Flash.

 16. Change the position of switch SW4 and switch OFF switch SW3.

 17. Press RESET Key and Observe output on LCD.

Read More

Sorting methods in data structure | Bubble sort | insertion sort | selection sort | quick sort

 

Sorting  methods :

Sorting is nothing but arranging the data in ascending or descending order. The term sorting came into picture, as humans realized the importance of searching quickly.

There are so many things in our real life that we need to search for, like a particular record in database, roll numbers in merit list, a particular telephone number in telephone directory, a particular page in a book etc. All this would have been a mess if the data was kept unordered and unsorted, but fortunately the concept of sorting came into existence, making it easier for everyone to arrange data in an order, hence making it easier to search.

Sorting arranges data in a sequence which makes searching easier.

Types of sorting  methods :

comparison based sorting methods :                        NON- comparison based 

1. Bubble                                                                     1. Radix 

2.Insertion                                                                    2. Counting 

3.Selection                                                                   3.Bucket 

4.Quick 

5. Merge 

1.BUBBLLE SORT :

Bubble sort  one of the simplex and most popular sorting method.

In this method there are n-1 passes in each pass we compare each successive element a(i) with the a(i+1)  and interchange the two if they are not in require order .One element is placed in its correct position in each pass This element is not considered in next pass.  in the first pass the largest element is sink to the bottom. second largest is the second large  and so on. Thus a total of n-1 pass passes are require to sort n keys. 

Algorithm for bubble sort :

step 1. start 

step 2. pass =1

step 3. repeat step 4-8 while pass <=n-1 

step 4. i= 0 

step 5. Repeat step 6-7 while i<=n- pass-1 

step 6. if (a[i]> a[i+1]) then interchange a[i], a[i+1]

step 7. i =i+1

step 8. pass = pass +1

step 9. stop 

* FUNCTION FOR BUBBLE SORT :

void bubblesort (int a[], int n)

{

int i , temp, pass;

for(pass = 1 ;pass < = n-1 ;pass ++)

for (i =0;i<= n- pass -1 ; i++)

{

if (a[i] > a[i+1])

{

temp = a [i];

a[i] = a[i+1];

a[i +1 ] = temp;

}

}

}

*  Program for Bubble sort:

#include<stdio.h>

void bubblesort(int a[],int n)

{

    int i,temp,pass;

    for(pass=1;pass<n;pass++)

    for(i=0;i<=n-pass-1;i++)

    {

            if(a[i]>a[i+1])

            {

                temp = a[i];

                a[i] = a[i+1];

                a[i+1] = temp;

            }

    }

}

void display(int a[],int n)

{

        int i;

        printf("sorted numbers are :");

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

        

        printf("\n--%d--",a[i]);

}

void main()

{

        int a[30],i,n;

        printf("enter how many numberrs you want :");

        scanf("%d",&n);

        printf("enter the unsorted elements :");

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

        scanf("%d",&a[i]);

        bubblesort(a,n);

        

        display(a,n);

}

Advantages of bubble sort :

*     It is a simple sorting method 

*     No additional data structure is require.

*     It is in place sorting method .

*     It is a stable sorting method.

Disadvantages ;

*     It is very efficient method .

*    even if the element are sorted all n-1 passes will be done.

2. INSERTION SORT :

The basic idea of  insertion sort method is to insert an unsorted element in its correct position in the sorted set of element we select one element from the unsorted set at a time and insert it in to its correct position in the sorted set the process continue till the unsorted set becomes empty.

for example :in order to arrange playing cards we pick one card at a time and insert this card in its correct position in the set held in the hand.

ALGORITHM FOR INSERTION SORT  :

step 1 . start

step 2. unsorted index i =1 

step 3. repeat step 4 to 10 while i <=n-1

step 4 . key = a[i] 

step 5 . sorted index j = i-1

step 6. repeat step 7 to 9 while j>= 0 and key < a[j]

step 7. shift a[j] to a[j+1]

step 8 . j = j-1 

step 9. insert key at a[j+1]

step 10. i = i+1 

step 11 . stop 

* Function for insertion sort :

void insertionsort(int a[],int n)

{

        int i,j,key;

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

        {

            key = a[i];

            for(j=i-1;j>=0;j--)

            if(key < a[j])

            a[j+1]=a[j];

            else

            break;

            a[j+1] = key;

        }

}

* program for insertion sort :

#include<stdio.h>

void insertionsort(int a[],int n)

{

        int i,j,key;

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

        {

            key = a[i];

            for(j=i-1;j>=0;j--)

            if(key < a[j])

            a[j+1]=a[j];

            else

            break;

            a[j+1] = key;

        }

}

void main()

{

        int i,a[40],n;

        printf("enter how many numbers you want :");

        scanf("%d",&n);

        printf("enter the unsortd numbers :");

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

        sccanf("%d",&a[i]);

        insertionsort(a,n);

        prinntf("sorted numbers are :");

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

        printf("--%d--",a[i]);

}

ADVANTAGE INSERTION SORT :

1. It is a simple sorting method 

2. No additional data structure is required.

3. It is in-place sorting method.

4. It is a stable method sorting.

5. This method gives best efficiency if the elements are almost sorted.

DISADVANTAGE :

1. worst case efficiency is O(n2).

SELECTION SORT :

Selection sort method is one of the most intuitive sorting method suppose we are given a list of the items to sort what would we do  we would select the smallest item and put it in another list then we pick the next smallest and so on till we have a sorted list.

In this Selection sort method  the set is divided into two sets sorted and unsorted initially the sorted set is empty and unsorted set is full we select the smallest element from the unsorted set and add it at the end of the sorted set to add it to the sorted set we exchange it with the first element in the unsorted set after each exchange the sorted set grow by 1 element and the unsorted set reduces by 1 element thus to sort n element we need to select and place n-1 element Hence there are n-1 passes in this method.

ALGORITHM  FOR  SELECTION  SORT :

STEP1. START 

STEP 2. sorted index current = 0 

step 3. repeat step 4 - 11 while current <=n-1

step 4. smallest = a[current] 

step 5. pos = current ;

step 6. i =current +1

step 7 . repeat step 7 - 9 while i= <n-1

step 8 . if (a[i] <smallest) then smallest = a[i]

            pos =i

step 9  .i = i+1

step 10 .  swap a[pos]  and a[current] 

step 11. current = current +1

step 12. stop

* Function for selection sort : 

int selectionsort(int a[],int n)

{

        int i,temp,pos,current,smallest;

        for(current=0;current<n-1;current++)

        {

            smallest = a[current];

            pos = current;

            for(i=current+1;i<=n-1;i++)

            if(a[i]<smallest)

            {

                smallest = a[i];

                pos = i;

            }

            else

            {

                temp = a[current];

                a[current] = a[pos];

                a[pos] = temp;

            }

        }

        

}

* Program for selection sort: *

#include<stdio.h>

int selectionsort(int a[],int n)

{

        int i,temp,pos,current,smallest;

        for(current=0;current<n-1;current++)

        {

            smallest = a[current];

            pos = current;

            for(i=current+1;i<=n-1;i++)

            if(a[i]<smallest)

            {

                smallest = a[i];

                pos = i;

            }

            else

            {

                temp = a[current];

                a[current] = a[pos];

                a[pos] = temp;

            }

        }

        

}

void main()

{

        int n,i,a[30];

        printf("enter how many number you want : ");

        scanf("%d",&n);

        printf("enter numbers in an array :");

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

        scanf("%d",&a[i]);

        selectionsort(a,n);

        printf("the sorted output is :");

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

        printf("--%d--",a[i]);

        

}

ADVANTAGES  SELECTION SORT :

1. It is a simple sorting method.

2. non additional data structure is required.

3. It is in place sorting method.

4. it is a stable sorting method. 

DISADVANTAGE SELECTION SORT :

Best  and Worst case efficiency is O(n^2). 

learn  about more sorting methods 👇

Read more 

Read More

linear vs binary searching in c | linear search |binary search

 

Searching Methods :

1. linear  or  sequential search .

2. Binary search .

1. Linear search /Sequential search : 

This is a simplex method of searching It is also called as a linear search and applied to sequential storage structure like file array or linked list.

Procedure : In this method the search for the key begin from the fist element and search continuous sequentially till the element will matching key value is found till the list end. 

ANALYSIS OF LINEAR SEARCH :

BEST CASE :

 The best case occurs when the key is found  at the first position. i . e. at index 0 here only one comparison performed Hence the best time complexity is omega 1.

WORST CASE :

 This case occurs when the  key is found in the array in such a case n comparisons are performed  Hence the ort case time complexity is O(n).

AVERAGE CASE :

Let us consider that all keys occurs with equal probability for all keys Ki (0 <= i<n) the total number of comparisons for successful searches are :

1 + 2 + . . . . . + n = n(n+1) /2

so average comparison is = n(n+1)/2n = (n+1 ) /2 Hence the average case time complexity of this method is O(n).

EFFICIENCY OF LINEAR SEARCHES ARE :

BEST CASE :  OMEGA 1 .

WORST CASE : O(n).

AVERAGE CASE : O(n).

Advantages :

1. It is a very simple method .

2. It does not require the data to be ordered.

3. It does not require any additional data structure.

Disadvantage :

1. If n  is very large this method is very inefficient and slow.

2. its worst case complexity is O(n) Hence the worst case search time increase in proportion to the number of elements. 

FUNCTION FOR LINEAR  SEARCH :

The function for linear search accepts an array , number of element and key as arguments it return the position of of key is found and return -1 if key is not found.

int linear_ search (int A[], int n, int key)

{

int  i ; 

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

if (A[ i ] = = key )

return 1;                /// return position 

return -1 ;             ///key not found 

}

Program for linear / sequential  search :

#include<stdio.h>

#include<stdlib.h>

int compcount=0;

int linearsearch(int a[],int n, int key)

{

        int i;

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

     {  

         compcount++;

        if(a[i] ==key)

        return 1;

        

     }

     return -1;

        

}

void accept(int a[],int n)

{

    int i;

    printf("enetr the %d element :",n);

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

    scanf("%d",&a[i]);

}

void main()

{

        int a[30],pos,key,n;

        printf("how many number you wnat in an array:");

        scanf("%d",&n);

        accept(a,n);

        printf("enetr number to be searched  :");

        scanf("%d",&key);

       pos = linearsearch(a,n,key);

       if(pos==-1)

       printf("%d not found in the array ",key);

       else

       printf("\n %d  found at position : ",pos);

       printf("\nthe total number of comparision =%d",compcount);

      }

2. Binary Search :

This method is based on  divide an conquer algorithmic strategy. in this strategy problem is solved by dividing the set of element and performing operation on each part

Precondition for binary search:

1. Data must be organized in linear way. 

2. Data has to be in the sorted order in either ascending or descending order.

Procedure :

* In this method the list is partitioned in two equal halves.

* The key compared with the middle element If a match is found the search is terminate.

* If the key is less than middle element search proceed in the same manner in the upper half of the table. 

* if the key is greater than middle element search proceed in the same way in the lower half of the table.

* The process continues till the key is found or no more partition are possible.

* Thus every time a match is not found the remaining list sized to searched reduce to half .

EFFICIENCY :

BEST CASE :

In this best case key is found at the middle position after 1 comparison . Hence the best case time complexity is  omega 1

WORST CASE :

If we observe the loop is repeatedly halving the number off element. Hence the algorithm complexity is logarithmic. Thus the time complexity is O(log2 n) which is very efficient.

ADVANTAGE :

Worst case time complexity is O (log2n) which is very efficient compared to sequential search (O(n)).

DISADVANTAGE :

Data has to be in sorted order.

Difference between linear search and binary search .

* FUNCCTION FOR BINARY SEARCH :

int binarysearch( int A[],int n ,int key )

{

int begin = 0, middle, end = n- 1;

while (begin < = end )

{

mid = (begin + end )/2;

if (key == A[mid] 

return mid ;

if (key < A[mid ]) 

end = mid -1 ;

else 

begin = mid +1 ;

}

return -1;

}

* program for Binary search : 

#include<stdio.h>

#include<stdlib.h>

int binarysearch(int a[],int n,int key)

{

    int begin=0,end=n-1,mid;

    if(begin<=end)

    {

            mid=(begin+end)/2;

            if(key == a[mid])

            return mid;

            if(key <= a[mid])

            end=mid-1;

            else

            begin=mid+1;

            

    }

    else

    {

            return -1;

    }

    }

void accept(int a[],int n)

{

    int i;

    printf("enter numbers in an array :");

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

    scanf("%d",&a[i]);

    

}

int main()

{

    int n,key,a[30];

    int pos;

    printf("enter how many numbers you want in an array :");

    scanf("%d",&n);

    accept(a,n);

    printf("enter number i to be search :");

    scanf("%d",&key);

     pos = binarysearch(a,n,key);

     if(pos == -1)

     printf("key is not found ");

     else

     printf("key is found ");

     

}

learn more about searching methods 👇

Read More

Data structure and algorithm -1

 

Need for data structures :

1.Modern day computing problems are complex and large.

2. They need to handle data in large volumes.

3.There is need to store and process information of a variety of types:  character, numeric, audio , video ,graphics, etc. 

4. Data has to be stored such that the logical relationship between the data element is retained. 

ADVANTAGE OF DATA STRUCTURE 

1. Structured data makes it easier to access the manipulate the information as compared to the raw unstructured data.

2. A variety of operation can be performed in structured data. 

3. Related data can be stored together and in the required format. 

4. better algorithm can be used on organized data. This improve program efficiency. 

5. They provide a means to store organize and retrieve data in an efficient manner.

DATA:

Data is a unprocessed input given to an a system or process.

1:ATOMIC DATA :Atomic data is a single elementary piece of data which cannot be further decomposed 

example: character 'a' and number 20etc. 

2:COMPOSITE DATA :Composite data is a grouped data item which consist of subfield each of which atomic 

example: a data like a subfield like day, month, and year.

DATA TYPE :

Data describe the  format in which data is stored and processed by a computer It also refers to the kind of data that variable hold in a programming language.

DATA OBJECT :

Data object refers to a set of element(D) of a specific data type. this  set may be finite or infinite. If the set is infinite we have to advise some mechanism to represent that set in memory because available memory is limited. 

DATA STRUCTURE :

A data structure consist of a data object , their properties and the set of legal operation which may be applied to the element of the data object.

definition:

A data structure is set of domains D a designated domain d belongs to D a set of function F and a set of axioms A. The triple (D F A ) denotes the data structure .

D = denotes the data object that is set of element.

F = denotes the set of operation that can be carried out on the element.

A = describe the properties and rules of operation.\

ABSTRACT DATA TYPE :

An ADT  is a mathematical and conceptual definition of a data structure the data structure i . e the triple DFA is called the abstract data type because it  is simply to conceptual specification off the data structure. 

IMPLEMENTATION OF DATA STRUCTURE :

The ADT is just a abstract data type. To use the data type or data structure it must  be implemented in a programming language. The implementation is concerned with 

1. How the elements are stored in memory.

2. How the operation are performed .

3. How the rules are enforced. 

SPACE COMPLEXITY :

The space complexity of an algorithm/program is the amount of memory is needs to execute. 

COMPONENTS OF SPACE COMPLEXITY :

1. Fixed part : This part is the independent of the characteristics of the input and the output of the memory space for simple variable component variable and constant. 

2.Variable part : It consist of the space needed by variable whose size depend on the particular problem instant being solved the space needed by reference variable and the recursive stack space. 

The space complexity S(P) for an algorithm is written as 

S(P) = C + Sp 

where c is a constant and is the fixed part Sp is the variable part which depend on the instance characteristics i . e. the program instance being run. 

example : float area (float r)

{

return 3.142 *r *r ;

}

the space needed is independent of the input and output of the characteristics it requires space for only one variable r 

Sp= 0, c= 1 .

TIME COMPLEXITY :

The time complexity of a program is the amount of time the program requires to execute however it is difficult to calculate the extract running time also the extract running time depend on the underlaying hardware and software. 

Hence instead of calculating exact running time a rough estimate can be made to do this we have to identify the 'active operation' of the program . The other operation like initialization assignment input and output etc. are called' book keeping operation'. and will not execute any times at the active operation. 

The total number of active operations is defined as frequency count.. 

BEST CASE AVERAGE CASE AND WORST CASE :

1. BEST CASE :

The term best case is analyze an algorithm under optimal conditions. The best case performance is the minimum number of steps that can be executed for the given input values. 

Best case (Tn) = min (Tx1, Tx2, . . . .. . Txn)

2.WORST CASE :

The worst case count the number of steps count the maximum number of steps that can be executed for the given parameter. This is the slowest possible time an algorithm may take an it upper bound. It is important to calculate the worst case behavior because  we know that the running time will execute this limit.

worst case Tn = Max(Tx1,Tx2, . . . .. . . . ,Txn)

3. AVERAGE CASE :

Average case running time assume that all input of a given are equally likely The average case step count is the average number of step executed 

Average case  =   1/  All possible inputs T(x1, x2, . . . . , xn )

 ADT of array :The ADT specifies the data object (D), function (F),axioms (A) of the data structure .

FUNCTIONS :

1. CREAT(array, type, size ): This operation creates the new array . This operation needs information like type of data of data element like a number of data element to be stored .

example : int [10]; 

2. STORE(array , index ,value ): store a value at a particular position. This operation needs the name of array the position in an array and value to be stored at that position. 

example : a[0] = 5; 

3. RETRIEVE (array , index): Retrieve a value at a position This operation requires the array  name and an index and it return to corresponding value .

example : num = a[0];

AXIOMS :

Create : The array name should be valid identifier size should be an integer and type should be a valid type.

Store : The index must be an integer value should be of the same type array .

Retrieve : the index must be an integer.

APPLICATION OF ARRAY :

Most application which handle large volume of data use array to store the element.

1. Searching .

2. Sorting .

3. Matrix operation.

4. Static implementation of data structure like stack , queue , tree, graph , etc.

SEARCHING : It is a process of locating an element with particular key value.

Key: particular element searched is called as key.

Retrieval : A successful search is called retrieval .

Internal searches : searches in which the entire table is stored in the main memory  are called as internal searches.

External searches : In this case most of the table is stored in auxiliary storage devise.

SORTING :

The sorting is a process of arranging the elements in the ascending or descending order.

1. Internal sorting : sorting is done on the data which is stored in the main memory.

2. External sorting : sorting is done on the data which is stored in auxiliary storage device. 

3. Stable sorting technique: A sorting method  is said to stable if the order of key having the same values in the unsorted set is retained in the sorted set. 

4. In place sorting : A sorting algorithm is said to be in place sorting if it does not use a lot of additional memory for sorting. 

Example : bubble sort , insertion sort etc. 

Read More

prescriptive process models

 prescriptive process model orderly approach to software engineering. its specific step by step sequence of activities addressing how to do the software development. all activities involve the dependent on one or other activity.

1 . THE WATERFALL MODEL :

It is also referred as "traditional" or "typical" or "classic life cycle" . model an is the oldest model of the software engineering. This model was proposed by Winston Royce in 1970.

Different phases and activities performed in each phase of waterfall model.

waterfall model follows the generic framework activities in sequential manner. The developer completes each phase before moving to the next . As the diagram resembled cascading waterfalls this model in called as "waterfall model".

PHSES OF WATERFALL MODEL :

1. Communication and requirement analysis phase : understanding user requirement and documenting the it is the basic aim of the phase.

2. Planning and scheduling phase : This phase aims to schedule the various activities of software development it identifies the risk involve and estimate the cost of development. it is also helps in tracking the development. 

3. Modeling and design phase : The main goal of this phase is to design the overall system with detailed specification. 

4. Construction or coding and testing : As the name of suggest this phase is responsible for implementation of the system design.  various components of the system are coded and tested of ensuring accuracy . 

5. deploying or operating maintenance phase : The phase aims of maintenance and successful operation of development software at users end for final acceptance. 

FEATURES OF WATERFALL MODEL:

1. The entire development process is divided in to number of phase.

2. It uses a linear process flow.

3. Each phase perform a specific task or activity.

4. Each phase generates a certain outcome called as a "work product ".

5.Outcomes of previous page acts as a input for the next stage. 

ADVANTAGES OF WATERFALL MODEL :

1. It is very simple to understand and use.

2.As each stage is responsible for a specific task it helps in good scheduling as cost estimation.

3. Efficient use of resource because of good scheduling. 

4. Work product helps in the judging the progress of the development process. 

LIMITATIONS OF WATERFALL MODEL :

1.Software product rarely follow the sequential process.

2. IT is not easy for user to explicitly specify all requirement of the beginning of the project which the model expects. 

3. It is unable to ideal with uncertainty which exists at beginning off the project. 

4. when project enter in a later stage i e. coding and testing it becomes difficult to accommodate change.

5. If a problem is identified in later stage then rectifying the problem leads to increase in cost and time of development.

2. V- MODEL :

This model is also referred as Verification and validation model. basic phase performed for software development in v- model are same as waterfall model. this model considered at as extension to the waterfall model. In this model action be be carried out for ensuring the quality development are describe with with each fundamental phase of waterfall model. This action involve various tests do validate the product at which as shown in the below figure.

VALIDATION PHASES IN V- MODEL :

1. Unit testing : unit test are designed and performed to ensure error free code at program module level. It checks the correct execution of each functionality implemented. 

2.Integration testing: system testing and ensure the error free and smooth working of various component module together. 

3. System Testing : System testing ensures that the system that whole working and correctly and providing the expected functionalities. 

4. Acceptance testing :The system tested in user environment  before the final acceptance. 

ADVANTAGE OF V- MODEL :

1. testing is planned before planned well before coding.

2. higher chances for success over waterfall model. 

3.Efficient for small project when requirement are clearly specified. 

DISADVANTAGE OF V- MODEL :

1. Not flexible.

2. Does not work efficiently with large and complex project. 

3. Difficult to adapt to changing requirement. 

 

THE UNIFIELD PROCESS MODEL :

The unified process model tries to extract the best of all traditional model. The process flow in unified process is incremental iterative and highly focused. on customer involvement . It is mainly designed for object oriented developing using UML (Unified Modeling Language).

PHASES OF UNIFIED PROCESS ARE AS FOLLOWS :

Inception Phase :  Inception phase mainly focused on objectives, business requirement and scope of project. It involves communication and planning activities.

Elaboration phase :  At the end of this phase most of requirement of the system is identified .It involves communication and modeling activities. 

Construction phase : This phase results in the actual software increment. different software components are integrated together and software increment is developed and tested.  Analysis and design models developed in elaboration are thus completed here.

Transition phase :  The outcome of this phase results is product release. Here the developed software is transferred for beta testing to client environment. All supporting document like user manual installation procedure etc. are also delivered to the client together with the software. 

 

 

Read More