Tuesday, November 17, 2009

Data structure using C PROGRAMS, DATA STRUCTURE,array,infix , postfix, implementation,queue,linked list ,array,stack using array, binary search, mer

DATA STRUCTURE PROGRAMS using c C++
data structure using
here are basic data structure programs for learner/beginner



Programs: To demonstrate simple array operations,
infix to postfix,
implementation of queue using stack and linked list or array,
implementation of stack using array and linked list,
binary search,
merge sort,
shell sort,
quick sort,
insertion sort,
binary tree traversal








9)
10)





ASSIGNMENT 1
// Date:
// Program Name: To demonstrate simple array operations

#include
#define N 100
int i,j,r,c,r1,r2,c1,c2;
int accept_values(int a[N])
{
int n;
printf("\nHow many values you wish to enter..? ");
scanf("%d",&n);
printf("\nEnter the data elements..\n");
for(i=0;i=pos;i--)
a[i] = a[i-1];
a[pos-1] = new;
n++;

printf("\n Do you wish to continue..(y/n)?");
ch = getche();
if(ch=='y') insert_cell(a,n);
return n;
}

/* To find the biggest of an existing array */
int getmaxelement(int a[N] ,int n)
{
int temp;
int b[N] ;
//b = a ;
for (i =0;i< temp =" b[i];" l =" getmaxelement(a" i="0;i
#include
#define M 10
int i, j, r, c, r1, r2, c1, c2;

/* Read the values for a MATRIX */
void read_matrix(int A[M][M])
{
printf("\nHow many rows? ");
scanf("%d",&r);
printf("\nHow many columns? ");
scanf("%d",&c);
for(i=0;i
# include
# include

# define size 100

int top = -1;
int flag = 0;

int stack[100];
int data;

void push(int *, int);
int peep(int *);
void display(int *);

/* Definition of the push function */

void push(int s[], int d)
{
if(top ==(size-1))
flag = 0;
else
{
flag = 1;
++top;
s[top] = d;

}
}

/* Definition of the peep function */

int peep(int s[])
{
int i;
int peeped_element;
printf("\n Input the information number to which you want access:");
scanf("%d", &i);

if(top - i + 1 < peeped_element =" 0;" flag =" 0;" flag =" 1;" peeped_element =" s[top-i" top ="=" i =" top;">=0; --i)
printf(" %d ", s[i]);
}
}

/* Function main */

void main()
{
int data;
char choice;
int q = 0;
int top = -1;

do
{
printf(" \nPush->i Peep->p Quit->q:");
printf("\nInput the choice : ");
do
{
choice = getchar();
choice =tolower(choice);
}while(strchr("ipq",choice)==NULL);
printf("Your choice is: ", choice);

switch(choice)
{
case 'i' :
printf("\n Input the element to push:");
scanf("%d", &data);
push(stack, data);
if(flag)
{
printf("\n After inserting ");
display(stack);
if(top == (size-1))
printf("\n Stack is full");
}
else
printf("\n Stack overflow after pushing");
break;

case 'p' :
data = peep(stack);
if(flag)
{
printf("\n Data is peeped: %d", data);
printf("\n Stack is as follows:\n");

display(stack);
}
else
printf("\n Stack underflow");
break;
case 'q':
q = 1;
}
} while(!q);
printf("\n\t\t\t###############################");
getch();
}


//Date:

//program: implementation of Queues using Array


# include
# define MAX 5

int queue_arr[MAX];
int rear = -1;
int front = -1;

main()
{
int choice;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
insert();
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/


insert()
{
int added_item;
if (rear==MAX-1)
printf("Queue Overflow\n");
else
{
if (front==-1) /*If queue is initially empty */
front=0;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
rear=rear+1;
queue_arr[rear] = added_item ;
}
}/*End of insert()*/

del()
{
if (front == -1 || front > rear)
{
printf("Queue Underflow\n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_arr[front]);
front=front+1;
}
}/*End of del() */

display()
{
int i;
if (front == -1)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
for(i=front;i<= rear;i++) printf("%d ",queue_arr[i]); printf("\n"); }} //Date : //program: convert infix to postfix. #include
#include
#include
#include

#define MAX 50

struct infix
{
char target[MAX] ;
char stack[MAX] ;
char *s, *t ;
int top ;
} ;

void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char ) ;
void show ( struct infix ) ;

void main( )
{
struct infix p ;
char expr[MAX] ;

initinfix ( &p ) ;

clrscr( ) ;

printf ( "\nEnter an expression in infix form: " ) ;
gets ( expr ) ;

setexpr ( &p, expr ) ;
convert ( &p ) ;

printf ( "\nThe postfix expression is: " ) ;
show ( p ) ;

getch( ) ;
}

/* initializes structure elements */
void initinfix ( struct infix *p )
{
p -> top = -1 ;
strcpy ( p -> target, "" ) ;
strcpy ( p -> stack, "" ) ;
p -> t = p -> target ;
p -> s = "" ;
}

/* sets s to point to given expr. */
void setexpr ( struct infix *p, char *str )
{
p -> s = str ;
}

/* adds an operator to the stack */
void push ( struct infix *p, char c )
{
if ( p -> top == MAX )
printf ( "\nStack is full.\n" ) ;
else
{
p -> top++ ;
p -> stack[p -> top] = c ;
}
}

/* pops an operator from the stack */
char pop ( struct infix *p )
{
if ( p -> top == -1 )
{
printf ( "\nStack is empty.\n" ) ;
return -1 ;
}
else
{
char item = p -> stack[p -> top] ;
p -> top-- ;
return item ;
}
}

/* converts the given expr. from infix to postfix form */
void convert ( struct infix *p )
{
char opr ;

while ( *( p -> s ) )
{
if ( *( p -> s ) == ' ' || *( p -> s ) == '\t' )
{
p -> s++ ;
continue ;
}
if ( isdigit ( *( p -> s ) ) || isalpha ( *( p -> s ) ) )
{
while ( isdigit ( *( p -> s ) ) || isalpha ( *( p -> s ) ) )
{
*( p -> t ) = *( p -> s ) ;
p -> s++ ;
p -> t++ ;
}
}
if ( *( p -> s ) == '(' )
{
push ( p, *( p -> s ) ) ;
p -> s++ ;
}

if ( *( p -> s ) == '*' || *( p -> s ) == '+' || *( p -> s ) == '/' || *( p -> s ) == '%' || *( p -> s ) == '-' || *( p -> s ) == '$' )
{
if ( p -> top != -1 )
{
opr = pop ( p ) ;
while ( priority ( opr ) >= priority ( *( p -> s ) ) )
{
*( p -> t ) = opr ;
p -> t++ ;
opr = pop ( p ) ;
}
push ( p, opr ) ;
push ( p, *( p -> s ) ) ;
}
else
push ( p, *( p -> s ) ) ;
p -> s++ ;
}

if ( *( p -> s ) == ')' )
{
opr = pop ( p ) ;
while ( ( opr ) != '(' )
{
*( p -> t ) = opr ;
p -> t++ ;
opr = pop ( p ) ;
}
p -> s++ ;
}
}

while ( p -> top != -1 )
{
char opr = pop ( p ) ;
*( p -> t ) = opr ;
p -> t++ ;
}

*( p -> t ) = '\0' ;
}

/* returns the priority of an operator */
int priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}

/* displays the postfix form of given expr. */
void show ( struct infix p )
{
printf ( " %s", p.target ) ;
}







































//Date:

//program: to convert infix to prefix.

#include
#include
#include
#include

#define MAX 50

struct infix
{
char target[MAX] ;
char stack[MAX] ;
char *s, *t ;
int top, l ;
} ;

void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char c ) ;
void show ( struct infix ) ;

void main( )
{
struct infix q ;
char expr[MAX] ;

clrscr( ) ;

initinfix ( &q ) ;

printf ( "\nEnter an expression in infix form: " ) ;
gets ( expr ) ;

setexpr ( &q, expr ) ;
convert ( &q ) ;

printf ( "The Prefix expression is: " ) ;
show ( q ) ;

getch( ) ;
}

/* initializes elements of structure variable */
void initinfix ( struct infix *pq )
{
pq -> top = -1 ;
strcpy ( pq -> target, "" ) ;
strcpy ( pq -> stack, "" ) ;
pq -> l = 0 ;
}

/* reverses the given expression */
void setexpr ( struct infix *pq, char *str )
{
pq -> s = str ;
strrev ( pq -> s ) ;
pq -> l = strlen ( pq -> s ) ;
*( pq -> target + pq -> l ) = '\0' ;
pq -> t = pq -> target + ( pq -> l - 1 ) ;
}

/* adds operator to the stack */
void push ( struct infix *pq, char c )
{
if ( pq -> top == MAX - 1 )
printf ( "\nStack is full.\n" ) ;
else
{
pq -> top++ ;
pq -> stack[pq -> top] = c ;
}
}

/* pops an operator from the stack */
char pop ( struct infix *pq )
{
if ( pq -> top == -1 )
{
printf ( "Stack is empty\n" ) ;
return -1 ;
}
else
{
char item = pq -> stack[pq -> top] ;
pq -> top-- ;
return item ;
}
}

/* converts the infix expr. to prefix form */
void convert ( struct infix *pq )
{
char opr ;

while ( *( pq -> s ) )
{
if ( *( pq -> s ) == ' ' || *( pq -> s ) == '\t' )
{
pq -> s++ ;
continue ;
}

if ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
while ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
*( pq -> t ) = *( pq -> s ) ;
pq -> s++ ;
pq -> t-- ;
}
}

if ( *( pq -> s ) == ')' )
{
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}

if ( *( pq -> s ) == '*' || *( pq -> s ) == '+' || *( pq -> s ) == '/' ||
*( pq -> s ) == '%' || *( pq -> s ) == '-' || *( pq -> s ) == '$' )
{
if ( pq -> top != -1 )
{
opr = pop ( pq ) ;

while ( priority ( opr ) > priority ( *( pq -> s ) ) )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
push ( pq, opr ) ;
push ( pq, *( pq -> s ) ) ;
}
else
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}

if ( *( pq -> s ) == '(' )
{
opr = pop ( pq ) ;
while ( opr != ')' )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
pq -> s++ ;
}
}

while ( pq -> top != -1 )
{
opr = pop ( pq ) ;
*( pq -> t ) = opr ;
pq -> t-- ;
}
pq -> t++ ;
}

/* returns the priotity of the operator */
int priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}

/* displays the prefix form of given expr. */
void show ( struct infix pq )
{
while ( *( pq.t ) )
{
printf ( " %c", *( pq.t ) ) ;
pq.t++ ;
}
}















//Date:
// program to evaluate an expression.
typedef struct
{
int a[100];
int top;
}

STACK;

void push(STACK *s,int x)
{
if(s->top==99)
printf("STACK OVERFLOW\n");
else
s->a[++s->top]=x;
}

int pop(STACK *s)
{
int x;
if(s->top<0) x="s-">a[s->top--];
}
return x;
}

int operation(int p1,int p2,char op)
{
int x;

switch(op)
{
case '+':
x= p1+p2;
case '*':
x= p1*p2;
case '-':
x= p1-p2;
case '/':
x= p1/p2;
}
return x;

}

int evaluate(char pos[])
{
STACK s1;
int p1,p2,result,i;
s1.top=-1;

for(i=0;pos[i]!='\0';i++)
if(isdigit(pos[i]))
push(&s1,pos[i]-'0'); /*use to find the integer value of it*/

else
{
p2=pop(&s1);
p1=pop(&s1);
result=operation(p1,p2,pos[i]);
push(&s1,result);
}/*end of for loop*/ return pop(&s1);

}

void main()
{
char postfix[100];
clrscr();
printf("Please Enter the VALID POSTFIX string\n\n Operands are SINGLE DIGIT\n\n");

gets(postfix);
printf("The Result is==>%d",evaluate(postfix));

getch();

}






//Date:

// PROGRAM TO check for brackets in an expression.

#include
#define MAX 20
#define true 1
#define false 0
int top = -1;
int stack[MAX];

push(char);
char pop();

main()
{
char exp[MAX],temp;
int i,valid=true;
printf("Enter an algebraic expression : ");
gets(exp);

for(i=0;i
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')
push( exp[i] );
if(exp[i]==')' || exp[i]=='}' || exp[i]==']')
if(top == -1) /* stack empty */
valid=false;
else
{
temp=pop();
if( exp[i]==')' && (temp=='{' || temp=='[') )
valid=false;
if( exp[i]=='}' && (temp=='(' || temp=='[') )
valid=false;
if( exp[i]==']' && (temp=='(' || temp=='{') )
valid=false;
}/*End of else */
}/*End of for*/
if(top>=0) /*stack not empty*/
valid=false;

if( valid==true )
printf("Valid expression\n");
else
printf("Invalid expression\n");
}/*End of main()*/

push(char item)
{
if(top == (MAX-1))
printf("Stack Overflow\n");
else
{
top=top+1;
stack[top] = item;
}
}/*End of push()*/

char pop()
{
if(top == -1)
printf("Stack Underflow\n");
else
return(stack[top--]);
}/*End of pop()*/




























ASSIGNMENT 3

//Date:

//Program: implementation of Linked list

#include
#include
#include
//Structure containing a Data part & a Link part

struct node
{
int data;
struct node *next;
}*Head;

// putsDeleting a node from List.

delnode(int num)
{
struct node *prev_ptr, *cur_ptr;

cur_ptr=Head;

while(cur_ptr != NULL)
{
if(cur_ptr->data == num)
{
if(cur_ptr==Head)
{
Head=cur_ptr->next;
free(cur_ptr);
return;
}
else
{
prev_ptr->next=cur_ptr->next;
free(cur_ptr);
return;
}
}
else
{
prev_ptr=cur_ptr;
cur_ptr=cur_ptr->next;
}
}

printf("\nElement %d is not found in the List", num);
}

//Adding a Node at the end of the list

append(int num)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;

// Copying the Head location into another node.
r=Head;

if (Head == NULL) // If List is empty we create First Node.
{
Head=temp;
Head->next =NULL;
}
else
{ // Traverse down to end of the list.
while(r->next != NULL)
r=r->next;

// Appending at the end of the list.
temp->next=NULL;
r->next =temp;
}
}

// Adding a Node at the Beginning of the List

addbeg(int num)
{
struct node *temp;

temp=(struct node *)malloc(sizeof(struct node));
temp->data = num;

if ( Head == NULL)
{
Head=temp;
Head->next=NULL;
}
else
{
temp->next=Head;
Head=temp;
}
}

// Adding a new Node after specifies number of Nodes

addafter(int num, int loc)
{
int i;
struct node *temp,*prev_ptr,*cur_ptr;

cur_ptr=Head;

if(loc > count()+1 || loc <= 0) { printf("\nInsertion at given location is not possible\n "); return; } if (loc == 1)// if list is null then add at beginning { addbeg(num); return; } else { for(i=1;inext;
}

temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;

prev_ptr->next=temp;
temp->next=cur_ptr;

return;
}
}

// Displaying list contents

display()
{
struct node *cur_ptr;

cur_ptr=Head;

if(cur_ptr==NULL)
{
printf("\nList is Empty");
return;
}

//traverse the entire linked list

while(cur_ptr!=NULL)
{
printf(" -> %d ",cur_ptr->data);
cur_ptr=cur_ptr->next;
}
printf("\n");
}

// Counting number of elements in the List
displaysearch()
{
int sk=0;
int i=0;
struct node *cur_ptr;

cur_ptr=Head;

if(cur_ptr==NULL)
{
printf("\nList is Empty");
return;
}
printf("Enter element to search\n");
scanf("%d",&sk);
//traverse the entire linked list


while(cur_ptr!=NULL)
{
// printf(" -> %d ",cur_ptr->data);
i++;
if (cur_ptr->data == sk)
{
printf("Searched Element is at %d position ",i);
}
cur_ptr=cur_ptr->next;
}
printf("\n");
}

//
count()
{
struct node *cur_ptr;
int c=0;

cur_ptr=Head;

while(cur_ptr!=NULL)
{
cur_ptr=cur_ptr->next;
c++;
}
return(c);
}

//This function Reverses a Linked List

reverse()
{
struct node *prev_ptr, *cur_ptr, *temp;

cur_ptr=Head;
prev_ptr=NULL;

while(cur_ptr != NULL)
{
temp=prev_ptr;
prev_ptr=cur_ptr;

cur_ptr=cur_ptr->next;
prev_ptr->next=temp;
}

Head=prev_ptr;
}

int main()
{
int i;
Head=NULL;

while(1)
{
printf(" \nInsert a number \n1. At Beginning");
printf(" \n2. At End");
printf(" \n3. At a Particular Location in List");
printf(" \n\n4. Print the Elements in the List");
printf(" \n5. Print number of elements in the List");
printf(" \n6. Delete a Node in the List");
printf(" \n7. Reverse the linked List");
printf(" \n8. Exit");
printf(" \n9. Search for a node");
printf(" \n\nChoose Option: ");
scanf("%d",&i);

switch(i)
{
case 1:
{
int num;
printf(" \nEnter the Number to insert: ");
scanf("%d",&num);
addbeg(num);
break;
}
case 2:
{
int num;
printf(" \nEnter the Number to insert: ");
scanf("%d",&num);
append(num);
break;
}
case 3:
{
int num, loc, k;
printf("\nEnter the Number to insert: ");
scanf("%d",&num);
printf("\nEnter the location Number: ");
scanf("%d",&loc);
addafter(num,loc);
break;
}
case 4:
{
printf(" \nElements in the List: ");
display();
break;
}
case 5:
{
display();
printf(" \nTotal number of Elements in the List: %d",count());
break;
}
case 6:
{
int num;
printf(" \nEnter the number to be deleted from List: ");
scanf("%d",&num);
delnode(num);
break;
}
case 7:
{
reverse();
display();
break;
}
case 8:
{
struct node *temp;

while( Head!=NULL)
{
temp = Head->next;
free(Head);
Head=temp;
}
exit(0);
}
case 9:
{

displaysearch();
break;
}
default:
{
printf("\nWrong Option choosen");
}
}/* end if switch */
}/* end of while */
}/* end of main */






//Date:
//Program : Sorting Linked List
#include
#include
#define MAX 10
struct lnode {
int data;
struct lnode *next;
} *head, *visit;
/* add a new entry to the linked list */
void llist_add(struct lnode **q, int num);
/* preform a bubble sort on the linked list */
void llist_bubble_sort(void);
/* print the entire linked list */
void llist_print(void);

int main(void) {
/* linked list */
struct lnode *newnode = NULL;
int i = 0; /* a general counter */

/* load some random values into the linked list */
for(i = 0; i < head =" newnode;" tmp =" *q;" q ="=" q =" malloc(sizeof(struct" tmp =" *q;">next != NULL)
tmp = tmp->next;

/* add node at the end */
tmp->next = malloc(sizeof(struct lnode));
tmp = tmp->next;
}

/* assign data to the last node */
tmp->data = num;
tmp->next = NULL;
}

/* print the entire linked list */
void llist_print(void) {
visit = head;

while(visit != NULL) {
printf("%d ", visit->data);
visit = visit->next;
}
printf("\n");
}

/* preform a bubble sort on the linked list */
void llist_bubble_sort(void) {
struct lnode *a = NULL;
struct lnode *b = NULL;
struct lnode *c = NULL;
struct lnode *e = NULL;
struct lnode *tmp = NULL;

/*
// the `c' node precedes the `a' and `e' node
// pointing up the node to which the comparisons
// are being made.
*/
while(e != head->next) {
c = a = head;
b = a->next;
while(a != e) {
if(a->data > b->data) {
if(a == head) {
tmp = b -> next;
b->next = a;
a->next = tmp;
head = b;
c = b;
} else {
tmp = b->next;
b->next = a;
a->next = tmp;
c->next = b;
c = b;
}
} else {
c = a;
a = a->next;
}
b = a->next;
if(b == e)
e = a; } }}





//Date:
//PROGRAM TO ADD TWO POLYNOMIALS
#include "stdio.h"
#include "conio.h"
struct barbie
{
int coff;
int pow;
struct barbie *link;
}*ptr,*start1,*node,*start2,*start3,*ptr1,*ptr2;
typedef struct barbie bar;
int temp1,temp2;

void main()
{

void create(void);
void prnt(void);
void suml(void);
void sort(void);
clrscr();

printf("Enrter the elements of the first poly :");
node = (bar *) malloc(sizeof (bar));
start1=node;
if (start1==NULL)
{
printf("Unable to create memory.");
getch();
exit();
}
create();

printf("
Enrter the elements of the second poly :");
node = (bar *) malloc(sizeof (bar));
start2=node;
if (start2==NULL)
{
printf("Unable to create memory.");
getch();
exit();
}
create();
clrscr();
//printing the elements of the lists
printf("The elements of the poly first are :");
ptr=start1;
prnt();

printf("The elements of the poly second are :");
ptr=start2;
prnt();

printf("The first sorted list is :");
ptr=start1;
sort();
ptr=start1;
prnt();

printf("

The second sorted list is :");
ptr=start2;
sort();
ptr=start2;
prnt();

printf("The sum of the two lists are :");
suml();
ptr=start3;
prnt();

getch();

}

/*-----------------------------------------------------------------------------*/
void create()
{
char ch;
while(1)
{
printf("Enter the coff and pow :");
scanf("%d%d",&node->coff,&node->pow);
if (node->pow==0 )
{
ptr=node;
node=(bar *)malloc(sizeof(bar));
node=NULL;
ptr->link=node;
break;
}

printf("
Do u want enter more coff ?(y/n)");
fflush(stdin);
scanf("%c",&ch);
if (ch=='n' )
{
ptr=node;
node=(bar *)malloc(sizeof(bar));
node=NULL;
ptr->link=node;
break;
}
ptr=node;
node=(bar *)malloc(sizeof(bar));
ptr->link=node;
}
}
/*-------------------------------------------------------------------------*/
void prnt()
{ int i=1;

while(ptr!=NULL )
{
if(i!=1)
printf("+ ");
printf(" %dx^%d ",ptr->coff,ptr->pow);
ptr=ptr->link;
i++;
}
//printf(" %d^%d",ptr->coff,ptr->pow);
}
/*---------------------------------------------------------------------------*/
void sort()
{
for(;ptr->coff!=NULL;ptr=ptr->link)
for(ptr2=ptr->link;ptr2->coff!=NULL;ptr2=ptr2->link)
{
if(ptr->pow>ptr2->pow)
{
temp1=ptr->coff;
temp2=ptr->pow;
ptr->coff=ptr2->coff;
ptr->pow=ptr2->pow;
ptr2->coff=temp1;
ptr2->pow=temp2;

}
}
}
/*---------------------------------------------------------------------------*/
void suml()
{
node=(bar *)malloc (sizeof(bar));
start3=node;

ptr1=start1;
ptr2=start2;

while(ptr1!=NULL && ptr2!=NULL)
{
ptr=node;
if (ptr1->pow > ptr2->pow )
{
node->coff=ptr2->coff;
node->pow=ptr2->pow;
ptr2=ptr2->link; //update ptr list B
}
else if ( ptr1->pow <>pow )
{
node->coff=ptr1->coff;
node->pow=ptr1->pow;
ptr1=ptr1->link; //update ptr list A
}
else
{
node->coff=ptr2->coff+ptr1->coff;
node->pow=ptr2->pow;
ptr1=ptr1->link; //update ptr list A
ptr2=ptr2->link; //update ptr list B

}

node=(bar *)malloc (sizeof(bar));
ptr->link=node; //update ptr list C
}//end of while

if (ptr1==NULL) //end of list A
{
while(ptr2!=NULL)
{
node->coff=ptr2->coff;
node->pow=ptr2->pow;
ptr2=ptr2->link; //update ptr list B
ptr=node;
node=(bar *)malloc (sizeof(bar));
ptr->link=node; //update ptr list C
}
}

else if (ptr2==NULL) //end of list B
{
while(ptr1!=NULL)
{
node->coff=ptr1->coff;
node->pow=ptr1->pow;
ptr1=ptr1->link; //update ptr list B
ptr=node;
node=(bar *)malloc (sizeof(bar));
ptr->link=node; //update ptr list C
}
}
node=NULL;
ptr->link=node;
}

























Assignment 4
//Date:

//Program: double linked list Implementation

#include
#include

struct dllist {
int number;
struct dllist *next;
struct dllist *prev;
};

struct dllist *head, *tail;

void append_node(struct dllist *lnode);
void insert_node(struct dllist *lnode, struct dllist *after);
void remove_node(struct dllist *lnode);

int main(void) {
struct dllist *lnode;
int i = 0;

/* add some numbers to the double linked list */
for(i = 0; i <= 5; i++) { lnode = (struct dllist *)malloc(sizeof(struct dllist)); lnode->number = i;
append_node(lnode);
}

/* print the dll list */
for(lnode = head; lnode != NULL; lnode = lnode->next) {
printf("%d\n", lnode->number);
}

/* destroy the dll list */
while(head != NULL)
remove_node(head);

return 0;
}

void append_node(struct dllist *lnode) {
if(head == NULL) {
head = lnode;
lnode->prev = NULL;
} else {
tail->next = lnode;
lnode->prev = tail;
}

tail = lnode;
lnode->next = NULL;
}

void insert_node(struct dllist *lnode, struct dllist *after) {
lnode->next = after->next;
lnode->prev = after;

if(after->next != NULL)
after->next->prev = lnode;
else
tail = lnode;

after->next = lnode;
}

void remove_node(struct dllist *lnode) {
if(lnode->prev == NULL)
head = lnode->next;
else
lnode->prev->next = lnode->next;

if(lnode->next == NULL)
tail = lnode->prev;
else
lnode->next->prev = lnode->prev;
}









//Date :

//Program: Circular Linked List in C

#include
#include
#include
#include
#define null 0
struct node
{
int info;
struct node *link;
}*start;
void main()
{
int ch,n,m,position,i;
last=null;
while(1)
{
printf("1.create
2.addat
3.addbt
4.del
5.disp
6.exit
");
printf("er ur ch");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("er no of itc");
scanf("%d",&n);
for(i=0;iinfo=data;
tmp->link=null;
if(last==null)
{
last=tmp;
tmp->link=last;
}
else
{
tmp->link=last->link;
last->link=tmp;
last=tmp;
}}


addat(int data)
{

struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=last->link;
last->link=tmp;
}
addbt(int data,int pos)
{
struct node *tmp,*q;
int i;
q=last->link;;
for(i=0;ilink;
if(q==last->link)
{
printf("there r lessthan %d elements",pos);
return;
}
}
tmp=(struct node *)malloc(sizeof(struct node));
tmp->link=q->link;
tmp->info=data;
q->link=tmp;
if(q==last)
last=tmp;
}
del(int data)
{
struct node *tmp,*q;
if(last->link==last&&last->info==data)
{
tmp=last;
last=null;
free(tmp);
return;
}
q=last->link;

if(q->info==data)
{
tmp=q;
last->link=q->link;
free(tmp);
return;
}
while(q->link!=last)
{

if(q->link->info==data)
{
tmp=q->link;
q->link=tmp->link;
free(tmp);

printf("element %d is deleted",data);
}
if(q->link->info=data)
{
tmp=q->link;
q->link=last->link;
free(tmp);
last=q;
return;}
printf("element%d is not found",data);
}
disp()
{
struct node *q;
if(last==null)
{
printf("list isdempty");
return;
}q=last->link;
while(q!=last)
{
printf("%d",q->info);
q=q->link;
}
printf("%d",last->info); }
//Date:

//Program: Implementation of stack using linked list

#include
#include

#define maxsize 10
void push();
void pop();
void display();

struct node
{
int info;
struct node *link;
}*start=NULL, *new,*temp,*p;
typedef struct node N;


main()
{
int ch,a;
do
{
printf("\t\t\tLinked stack");
printf("\n 1.Push");
printf("\n 2.Pop");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nInvalid choice");
break;
}
}
while(ch<=3); } void push() { new=(N*)malloc(sizeof(N)); printf("\nEnter the item : "); scanf("%d",&new->info);
new->link=NULL;
if(start==NULL)
start=new;
else
{
p=start;
while(p->link!=NULL)
p=p->link;
p->link=new;
}
}


void pop()
{
if(start==NULL)
printf("\nStack is empty");
else if(start->link==NULL)
{
printf("\nThe deleted element is : %d",start->info);
free(start);
start=NULL;
}

else
{
p=start;
while(p->link!=NULL)
{
temp=p;
p=p->link;
}
printf("\nDeleted element is : %d\n", p->info);
temp->link=NULL;
free(p);
}
}


void display()
{
if(start==NULL)
printf("\nStack is empty");
else
{

printf("\nThe elements are : ");
p=start;
while(p!=NULL)
{
printf("%d",p->info);
p=p->link;
}
printf("\n");
}
}


















//Date:

//Program : Queue operations using linked list

#include
#include
#define MAXSIZE 10

void insertion();
void deletion();
void display();

struct node
{
int info;
struct node *link;
}*new,*temp,*p,*front=NULL,*rear=NULL;
typedef struct node N;


main()
{
int ch;
do
{
printf("\n\t\t\tLinked queue");
printf("\n 1.Insertion");
printf("\n 2.Deletion");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
insertion();
break;
case 2:
deletion();
break;
case 3:
display();
break;
default:
break;
}
}
while(ch<=3); } void insertion() { int item; new=(N*)malloc(sizeof(N)); printf("\nEnter the item : "); scanf("%d",&item); new->info=item;
new->link=NULL;
if(front==NULL)
front=new;
else
rear->link=new;
rear=new;
}

void deletion()
{
if(front==NULL)
printf("\nQueue is empty");
else
{
p=front;
printf("\nDeleted element is : %d",p->info);
front=front->link;
free(p);
}
}

void display()
{
if(front==NULL)
printf("\nQueue is empty");
else
{
printf("\nThe elements are : ");
temp=front;
while(temp!=NULL)
{
printf("%d",temp->info);
temp=temp->link;
}
}
}




ASSIGNMENT 5

//Date:

//Program : Binary Search Tree

#include
#include
#include

struct searchtree
{
int element;
struct searchtree *left,*right;
}*root;
typedef struct searchtree *node;
typedef int ElementType;

node insert(ElementType, node);
node delet(ElementType, node);
void makeempty();
node findmin(node);
node findmax(node);
node find(ElementType, node);
void display(node, int);

void main()
{
int ch;
ElementType a;
node temp;
makeempty();
while(1)
{
printf("\n1. Insert\n2. Delete\n3. Find min\n4. Find max\n5. Find\n6. Display\n7. Exit\nEnter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter an element : ");
scanf("%d", &a);
root = insert(a, root);
break;
case 2:
printf("\nEnter the element to delete : ");
scanf("%d",&a);
root = delet(a, root);
break;
case 3:
printf("\nEnter the element to search : ");
scanf("%d",&a);
temp = find(a, root);
if (temp != NULL)
printf("Element found");
else
printf("Element not found");
break;
case 4:
temp = findmin(root);
if(temp==NULL)
printf("\nEmpty tree");
else
printf("\nMinimum element : %d", temp->element);
break;
case 5:
temp = findmax(root);
if(temp==NULL)
printf("\nEmpty tree");
else
printf("\nMaximum element : %d", temp->element);
break;
case 6:
if(root==NULL)
printf("\nEmpty tree");
else
display(root, 1);
break;
case 7:
exit(0);
default:
printf("Invalid Choice");
}
}
}

node insert(ElementType x,node t)
{
if(t==NULL)
{
t = (node)malloc(sizeof(node));
t->element = x;
t->left = t->right = NULL;
}
else
{
if(x <>element)
t->left = insert(x, t->left);
else if(x > t->element)
t->right = insert(x, t->right);
}
return t;
}

node delet(ElementType x,node t)
{
node temp;
if(t == NULL)
printf("\nElement not found");
else
{
if(x <>element)
t->left = delet(x, t->left);
else if(x > t->element)
t->right = delet(x, t->right);
else
{
if(t->left && t->right)
{
temp = findmin(t->right);
t->element = temp->element;
t->right = delet(t->element,t->right);
}
else if(t->left == NULL)
t=t->right;
else
t=t->left;
}
}
return t;
}
void makeempty()
{
root = NULL;
}


node findmin(node temp)
{
if(temp == NULL || temp->left == NULL)
return temp;
return findmin(temp->left);
}


node findmax(node temp)
{
if(temp==NULL || temp->right==NULL)
return temp;
return findmin(temp->right);
}


node find(ElementType x, node t)
{
if(t==NULL) return NULL;
if(xelement) return find(x,t->left);
if(x>t->element) return find(x,t->right);
return t;
}


void display(node t,int level)
{
int i;
if(t)
{
display(t->right, level+1);
printf(“\n”);
for(i=0;ielement);
display(t->left, level+1);
}
}













Assignment 6

//Date:

//Program : Bubble sort

#include
#include
#include

#define MAX 50
#define N 2000

void sort_words(char *x[], int y);
void swap(char **, char **);

int main(void) {
char word[MAX];
char *x[N];
int n = 0;
int i = 0;

for(i = 0; scanf("%s", word) == 1; ++i) {
if(i >= N)
printf("Limit reached: %d\n", N), exit(1);

x[i] = calloc(strlen(word)+1, sizeof(char));
strcpy(x[i], word);
}

n = i;
sort_words(x, n);
for(i = 0; i < i =" 0;" j =" 0;" i =" 0;" j =" i"> 0)
swap(&x[i], &x[j]);
}

void swap(char **p, char **q) {
char *tmp;

tmp = *p;
*p = *q;
*q = tmp;
}

































//Date:

//Program : Insertion sort

#include

void isort(float arr[], int n);
int fm(float arr[], int b, int n);

int main(void) {
float arr1[5] = {4.3, 6.7, 2.8, 8.9, 1.0};
float arr2[5] = {4.3, 6.7, 2.8, 8.9, 1.0};
int i = 0;

isort(arr2, 5);

printf("\nBefore\tAfter\n--------------\n");

for(i = 0; i < f =" b;" c =" b" f =" c;" s =" 0;" w =" fm(arr," sm =" arr[w];">
#include

#define MAXARRAY 10

void mergesort(int a[], int low, int high);

int main(void) {
int array[MAXARRAY];
int i = 0;

/* load some random values into the array */
for(i = 0; i < i =" 0;" i =" 0;" i =" 0;" length =" high" pivot =" 0;" merge1 =" 0;" merge2 =" 0;" low ="=" pivot =" (low" i =" 0;" merge1 =" 0;" merge2 =" pivot" i =" 0;"> working[merge2])
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
else
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
}
}

















//Date:

//Program : quick sort


#include

#define MAXARRAY 10

void quicksort(int arr[], int low, int high);

int main(void) {
int array[MAXARRAY] = {0};
int i = 0;

/* load some random values into the array */
for(i = 0; i < i =" 0;" i =" 0;"> `high' */
void quicksort(int arr[], int low, int high) {
int i = low;
int j = high;
int y = 0;
/* compare value */
int z = arr[(low + high) / 2];

/* partition */
do {
/* find member above ... */
while(arr[i] <> z) j--;

if(i <= j) { /* swap two elements */ y = arr[i]; arr[i] = arr[j]; arr[j] = y; i++; j--; } } while(i <= j); /* recurse */ if(low <>

#define MAXARRAY 10

void shellsort(int a[], int total, int index);

int main(void) {
int array[MAXARRAY] = {0};
int i = 0;

/* load some random values into the array */
for(i = 0; i < i =" 0;" i =" 0;" i =" 0;" j =" 0;" k =" 0;" l =" 0;" k =" 0;" i =" k;" l =" a[i];" j =" (i">= 0; j -= index) {
if(a[j] > l)
a[j + index] = a[j];
else
break;
}
a[j + index] = l;
}
}

return;
}






























//Date:

//Program: selection sort

Ssort, selection sort [array]

#include

void selection_sort(int a[], int size);

int main(void) {
int arr[10] = {10, 2, 4, 1, 6, 5, 8, 7, 3, 9};
int i = 0;

printf("before:\n");
for(i = 0; i < i =" 0;" i =" 0;" j =" 0;" large =" 0;" index =" 0;" i =" size"> 0; i--) {
large = a[0];
index = 0;
for(j = 1; j <= i; j++) if(a[j] > large) {
large = a[j];
index = j;
}
a[index] = a[i];
a[i] = large;
}}
//Date:

//Program : Linear Search

#include
void print_arr(int myArray[], int elements);
int search_arr(int myArray[], int elements, int number);

int main(void)
{
int myArray[10] = {12,23,56,35,18,65,12,87,73,9};
int result,number;
print_arr(myArray,10);
number = 65;
result = search_arr(myArray,10,number);
if(result == -1)
printf("%d was not found.\n",number);
else
printf("Found %d\n",result);
return 0;
}

void print_arr(int myArray[], int elements)
{
int i;

for(i = 0;i < i =" 0;i">

#define TRUE 0
#define FALSE 1

int main(void) {
int array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int left = 0;
int right = 10;
int middle = 0;
int number = 0;
int bsearch = FALSE;
int i = 0;

printf("ARRAY: ");
for(i = 1; i <= 10; i++) printf("[%d] ", i); printf("\nSearch for Number: "); scanf("%d", &number); while(bsearch == FALSE && left <= right) { middle = (left + right) / 2; if(number == array[middle]) { bsearch = TRUE; printf("** Number Found **\n"); } else { if(number < right =" middle"> array[middle]) left = middle + 1;
}
}

if(bsearch == FALSE)
printf("-- Number Not found --\n");

return 0;
}