Category Archives: Data Structures

CSE 255 Unit V Graph Notes

Dear Students,

In this Unit 5, we have discussed the following Sorting Techniques:

  • Topological Sort
  • Shortest-path Algorithms
  • Dijkstra’s Algorithm
  • Minimum Spanning Tree
  • Kruskal’s Algorithm
  • Prim’s Algorithm
  • Depth-First Search
  • Breadth-First Search
  • Applications of Depth-First Search
  • Undirected Graphs – Bi Connectivity
  • NP-Completeness Problem

Download Graph PPT

Download Graph Notes

Hope this may helpful to u..

Thank you.

Advertisements

Array Implementation of List ADT

Array Implementation of List ADT

Program:

#include
#include
int a[20],i,n;
void create(int);
void display();
void insert(int,int);
void delet(int);
int search(int);
void makeempty();
void main()
{ int op=1,ch,x,p,k;
do
{
printf(“enter your choice\n\n”);
printf(“1.Creation\n”);
printf(“2.Display\n”);
printf(“3.Insertion\n”);
printf(“4.Deletion by position\n”);
printf(“5. Deletion by element\n”);
printf(“6.Search\n”);
printf(“7. Find Kth\n”);
printf(“8. FindNext\n”);
printf(“9. Find Previous\n”);
printf(“10. MakeEmpty\n”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“enter the number of elements\n”);
scanf(“%d”,&n);
create(n);
break;
case 2:
display();
break;
case 3:
printf(“enter the element to be inserted\n”);
scanf(“%d”,&x);
printf(“Enter the position”);
scanf(“%d”,&p);
insert(p,x);
break;
case 4:
printf(“Enter the position to be deleted “);
scanf(“%d”,&p);
delet(p);
break;
case 5:
printf(“Enter the element to be deleted\n”);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found \n”);
else
delet(p);
break;
case 6:
printf(“enter element to search”);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found \n”);
else
printf(“the variable is found in position: %d\n”,p);
break;
case 7:
printf(“Enter the value of k “);
scanf(“%d”,&k);
if(k>n)
printf(“no such position\n”);
else
printf(“%d “,a[k-1]);break;
case 8:
printf(“Enter the element “);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found\n”);
else
{
if(p==n)
printf(“It is the last element. There is no next value \n”);
else
printf(“%d “,a[p]);
}break;
case 9:
printf(“Enter the element “);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found\n”);
else
{
if(p==1)
printf(“Its the first element.Thereis no previousvalue\n”);
else
printf(“%d “,a[p-2]);
}break;
case 10:
makeempty();
break;
}
printf(“Enter 0 to quit and 1 to continue “);
scanf(“%d”,&op);
}while(op);
}

void create(int n)
{ for(i=0;i<n;i++)
{
printf(“enter the element”);
scanf(“%d”,&a[i]);
}
}

void display()
{ if(n==0)
printf(“array is empty\n”);
for(i=0;in+1)
printf(“Cannot insert element “);
else
{
n++;
for(i=n-1;i>=p;i–-)
{
a[i]=a[i-1];
}
a[p-1]=x;
}
}

void delet(int p)
{
if(p>n)
printf(“no element in that position\n”);
else
{
for(i=p-1;i<n;i++)
a[i]=a[i+1];
n–-;
printf(“The element is deleted\n”);
}
}

int search(int x)
{
int pos=0;
for(i=0;i<n;i++)
{
if(a[i]==x)

pos=i+1;

}
return pos;
}

void makeempty()
{
printf(“Are you sure u want to make empty?; \n press 1 for yes & 0 for no\n");
scanf(“%d”,&n);
if(n==1)
{
for(i=0;i<n;i++)
a[i]=0;
}
printf(“Now the array is empty \n”);
}

Sorting – Heap Sort

Heap Sorting

Method and Algorithm

Heap sorting process:

First of all organizing the whole data to be sorted as a binary tree i.e. heap. And after that implement heap sorting.

Step 1: (How to data organizing as binary tree?)

Remember only 2 rule:

Rule:1.

The parent node must be greater then child node.
If parent node is not greater then to child node not replace it with parent node. And if binary tree is large then, if relaceing child node(now its parent node) is greater then to great-parent node then its also is replace the great-parent node.

Rule:2.

New element always insert in left side and after right side of parent node.
If left side of parent element has already element then new element would be insert in right side. And if right side of parent node has already element then new element will be insert in left side.

Step 2: (How to perform heap sorting:)

Remove the topmost element(largest element) and replace it with the rightmost element.
Step 3:
Repeat steps 1 and 2 untill all elements is not sorted.

Heap Sorting method/process by example:

max heap : 80 , 32 , 31 , 110 , 50 , 40 , 120

<img src=”https://mrajacse.files.wordpress.com/2012/09/heap-sort-1.jpg”&gt;

<img alt=”” src=”https://mrajacse.files.wordpress.com/2012/09/heap-sort-1.jpg&#8221; />

<img src=”https://mrajacse.files.wordpress.com/2012/09/heap-sort-1.jpg&#8221; alt=”Smiley face” height=”42″ width=”42″>

<img alt=src=””>

Step1:
80

Step2:  
80
/      \
32      31
Step3:  
80                                         80                                    110
/     \                                     /     \                                 /       \
   32         31       ==>        110       31          ==>        80       31
   /                                            /                                        /
110                                       32                                      32
Step4:
110
/      \
80        31
/    \
32      5
Step5:
            110                                         110
/      \                                      /       \
80       31         ==>           80         40
/    \       /                               /   \        /
32   50  40                           32   50  31
Step6:
              110                                              110                                      120
/         \                                         /         \                                  /        \
80         40             ==>          80          120      ==>         80         110
/     \       /    \                             /    \         /    \                     /     \      /    \
32    50  31   120                     32     50  31     40             32    50 31    40————————————————————————————-(1)
120 [1]
/                      \
80 [2]               110 [3]
/         \              /           \
32 [4]   50 [5] 31 [6]   40 [7]// [1],[2],[3],[4],[5],[6],[7]: Index number
// Now applying step 2(perform heap sorting)
// Replace the topmost element with the rightmost element.

(2)
40                                             110
/      \             Heaping             /       \
80       110        =====>        80          40
/   \       /    \                           /    \       /    \
32    50 31    120                  32     50   31    120

(3)

//now replace 110 with rightmost element i.e. 31 because 120 had been sorted.
        31                                                           80                                                                     80
/            \           Heaping                     /           \                        Heaping                   /        \
80           40        ======>            31               40                 ======>            50         40
/    \          /    \                                     /     \            /    \                                              /    \        /   \
32   50  110   120                           32     50   110    120                                     32    31  110  120
(4)
//now replace 80 with rightmost element i.e. 31 because 110, 120 had been sorted.          31                                                 50                                                  50
/      \             Heaping              /        \           Heaping                   /     \
50       40          ======>         31          40        ======>          32      40
/    \      /   \                                /     \       /     \                             /    \     /     \
32     80  110  120                      32     80     110    120                31     80  110   120(5)
//now replace 50 with rightmost element i.e. 31 because 80, 110, 120 had been sorted.31                                                              40
/        \            Heaping                       /          \
32           40        ======>              32             31
/     \        /    \                                       /    \          /     \
  50     80    110    120                        50     80   110    120(6)
//now replace 40 with rightmost element i.e. 31 because 50, 80, 110, 120 had been sorted.31                                                       32
/     \           Heaping                        /         \
32      40        ======>                   31           40
/    \     /    \                                    /    \        /    \
50   80   110   120                       50    80  110    120(7)
//now replace 32 with rightmost element i.e. 31 because 40, 50, 80, 110, 120 had been sorted.                     31
                 /        \
              32          40
            /     \       /      \
         50     80   110    120Now all elements are sorted: 31 , 32 , 40 , 50 , 80 , 110 , 120

Program:

#include<stdio.h>
#include<conio.h>
void manage(int *, int);
void heapsort(int *, int, int);
int main()
{
int arr[20];
int i,j,size,tmp,k;
printf(“\n\t——- Heap sorting method ——-\n\n”);
printf(“Enter the number of elements to sort : “);
scanf(“%d”,&size);
for(i=1; i<=size; i++)
{
printf(“Enter %d element : “,i);
scanf(“%d”,&arr[i]);
manage(arr,i);
}
j=size;
for(i=1; i<=j; i++)
{
tmp=arr[1];
arr[1]=arr[size];
arr[size]=tmp;
size–;
heapsort(arr,1,size);
}
printf(“\n\t——- Heap sorted elements ——-\n\n”);
size=j;
for(i=1; i<=size; i++)
printf(“%d “,arr[i]);
getch();
return 0;
}void manage(int *arr, int i)
{
int tmp;
tmp=arr[i];
while((i>1)&&(arr[i/2]<tmp))
{
arr[i]=arr[i/2];
i=i/2;
}
arr[i]=tmp;
}void heapsort(int *arr, int i, int size)
{
int tmp,j;
tmp=arr[i];
j=i*2;
while(j<=size)
{
if((j<size)&&(arr[j]<arr[j+1]))
j++;
if(arr[j]<arr[j/2])
  break;
arr[j/2]=arr[j];
j=j*2;
}
arr[j/2]=tmp;
}

 

Quick sorting

Quick sort is a divide and conquer algorithm. Its divided large list in mainly three parts:

1.     Elements less than pivot element.

2.     Pivot element.

3.     Elements greater than pivot element.

Where pivot as middle element of large list. Let’s understand through example:

List : 3  7  8  5  2  1  9  5  4

In above list assume 4 is pivot element so rewrite list as:

3   1   2   4   5    8   9   5   7

Here, we set the pivot element(4) which has in left side elements are less than and right hand side elements are greater than. Now you think, how’s arrange the less than and greater than elements? Be patient, you get answer soon.

Now let’s start understand the concept of quick sort. The steps are:

1.    Pick a pivot element.

2.    Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with     values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final     position. This is called the partition operation.

3.    Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

        The base case of the recursion are lists of size zero or one, which never need to be sorted
Example of quick sort process:

Program:

#include<stdio.h>

#include<conio.h>
void qsort(int arr[20], int fst, int last);
int main()
{
    int arr[30];
    int i,size;
    printf(“Enter total no. of the elements : “);
    scanf(“%d”,&size);
    printf(“Enter total %d elements : \n”,size);
    for(i=0; i<size; i++)
         scanf(“%d”,&arr[i]);
    qsort(arr,0,size-1);
    printf(“Quick sorted elements are as  : \n”);
    for(i=0; i<size; i++)
    printf(“%d\t”,arr[i]);
getch();
    return 0;
}
void qsort(int arr[20], int fst, int last)
{
    int i,j,pivot,tmp;
    if(fst<last)
     {
          pivot=fst;
          i=fst;
          j=last;
          while(i<j)
                    {
                         while(arr[i]<=arr[pivot] && i<last)
                          i++;
                          while(arr[j]>arr[pivot])
                          j–;
                         if(i<j)
                           {
                                 tmp=arr[i];
                                 arr[i]=arr[j];
                                arr[j]=tmp;
                           }
                    }
                  tmp=arr[pivot];
                  arr[pivot]=arr[j];
                  arr[j]=tmp;
                  qsort(arr,fst,j-1);
                  qsort(arr,j+1,last);
              }
}

PROGRAM – LINKED LIST IMPLEMENTATION OF BINARY SEARCH TREE

Implementation of Binary Search Tree:

#include<stdio.h>

#include<conio.h>

struct Treenode;

typedef struct Treenode *Position;

typedef struct Treenode *SearchTree;

SearchTree Insert(int X,SearchTree T);

SearchTree Delete(int X,SearchTree T);

Position Find(int X,SearchTree T);

Position FindMin(SearchTree T);

Position FindMax(SearchTree T);

void Display(SearchTree T);

struct Treenode

{

int Element;

SearchTree Left;

SearchTree Right;

};

Position T,P;

void main()

{

int X,op=1;

clrscr();

T=NULL;

while(op!=7)

{

printf(“enter your option 1.Insert 2.Delete 3.Find 4.FindMin 5.FindMax 6.Display 7.Quit\n”);

scanf(“%d”,&op);

switch(op)

{

case 1:

printf(“enter the element\n”);

scanf(“%d”,&X);

T=Insert(X,T);

printf(“the new element is inserted\n “);

break;

case 2:

printf(“Enter the element to delete”);

scanf(“%d”,&X);

P=Delete(X,T);

printf(“the element at position %d is deleted\n”,P);

break;

case 3:

printf(“enter the element to find”);

scanf(“%d”,&X);

P=Find(X,T);

if(P==NULL)

printf(“The element is not found\n”);

else

printf(“the element is found at position %d\n”,P);

break;

case 4:

P=FindMin(T);

printf(“The minimum element in the tree is %d and it is found at position %d\n”,P->Element,P);

break;

case 5:

P=FindMax(T);

printf(“The maximum element in the tree is %d and it is found at position %d\n”,P->Element,P);

break;

case 6:

Display(T);

break;

case 7:

exit(0);

break;

}

}

}

SearchTree Insert(int X,SearchTree T)

{

if(T==NULL)

{

T=(SearchTree)malloc(sizeof(struct Treenode));

T->Element=X;

T->Left=T->Right=NULL;

}

else if(X<T->Element)

T->Left=Insert(X,T->Left);

else if(X>T->Element)

T->Right=Insert(X,T->Right);

return T;

}

Position Find(int X,SearchTree T)

{

if(T==NULL)

return NULL;

if(X<T->Element)

return Find(X,T->Left);

else if(X>T->Element)

return Find(X,T->Right);

else

return T;

}

Position FindMin(SearchTree T)

{

if(T==NULL)

return NULL;

else if(T->Left==NULL)

return T;

else

return FindMin(T->Left);

}

Position FindMax(SearchTree T)

{

if(T==NULL)

return NULL;

else if(T->Right==NULL)

return T;

else

return FindMax(T->Right);

}

SearchTree Delete(int X, SearchTree T)

{

Position TmpCell;

if(T==NULL)

printf(“Element not found\n”);

else if(X<T->Element)

T->Left=Delete(X,T->Left);

else if(X>T->Element)

T->Right=Delete(X,T->Right);

else if(T->Left && T->Right)

{

TmpCell=FindMin(T->Right);

T->Element=TmpCell->Element;

T->Right=Delete(T->Element,T->Right);

}

else

{

TmpCell=T;

if(T->Left==NULL)

T=T->Right;

else if(T->Right==NULL)

T=T->Left;

free(TmpCell);

}

return T;

}

void Display(SearchTree T)

{

if(T!=NULL)

{

Display(T->Left);

printf(“%d   %d\n”,T,T->Element);

Display(T->Right);

}

}

CSE255 Unit III Data Structures Notes

Dear Students,
From trees Concepts the following topics were discussed.

  • Binary Trees
  • The Search Tree ADT
  • Binary Search Trees
  • AVL Trees
  • Tree Traversals
  • Hashing – Hash Function
  • Separate Chaining – Open Addressing
  • Priority Queues
  • Binary Heap

Download AVL tree PPT

Download Binary Tree ,BST PPT

Download Tree Problems PPT

Download Unit III Trees Notes

Hope it Helps you.

Regards,
Raja. M

CSE 255 Unit IV – Sorting

Dear Students,

In this Unit 4 we have discussed the following Sorting Techniques:

  • Insertion Sort
  • Shell Sort
  • Heap Sort
  • Merge Sort
  • Quick Sort

There are some other sorting techniques also available. But not in the Syllabus.

Download bubble, selection, insertion shell sort PPT

Download Quick, merge sort PPT

Download Unit 4 Searching & Sorting Notes

Refer this Animation:

Insertion Sort

Heap Sort

Merge Sort