I would like to share my codes of data structures in c and c++
1st program is for the addition and multiplication of two polynomials
#include
#include
#define MAX 10
void initialise(int[]);
void addition(int[],int[],int[],int);
void multi(int[],int[],int[],int,int);
void accept(int[],int);
void display(int[],int);
int eval(int[],int,int);
int pow(int,int);
void main()
{
int a[MAX],b[MAX],c[MAX],m,n,i,j,x,ch,o,m1;
clrscr();
do
{
printf("\n menu");
printf("\n 1.addition");
printf("\n 2.multiplication");
printf("\n 3.evaluation");
printf("\n 4.exit");
printf("\n enter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
initialise(a);
initialise(b);
initialise(c);
printf("\n enter the highest power of first polynomial:");
scanf("%d",&m);
accept(a,m);
printf("\n enter the highest power of second polynomial:");
scanf("%d",&n);
accept(b,n);
o=m>n?m:n;
addition(a,b,c,o);
printf("\naddition=");
display(c,o);
break;
case 2:
initialise(a);
initialise(b);
initialise(c);
printf("\n enter the highest power of first polynomial:");
scanf("%d",&m);
accept(a,m);
printf("\n enter the highest power of second polynomial:");
scanf("%d",&n);
accept(b,n);
multi(a,b,c,m,n);
printf("\nmultiplication=");
display(c,m+n);
break;
case 3:
initialise(a);
printf("\n enter the highest power of first polynomial:");
scanf("%d",&m);
accept(a,m);
printf("\n enter the value of x:");
scanf("%d",&x);
m1=eval(a,m,x);
printf("\n result is=%d",m1);
break;
case 4:
exit(0);
}
}while(ch!=4);
getch();
}
void accept(int a[],int m)
{
int i;
for(i=m;i>=0;i--)
{
printf("\n enter the coefficient of x[%d]=",i);
scanf("%d",&a[i]);
}
}
void addition(int a[],int b[],int c[],int m)
{
int i;
for(i=m;i>=0;i--)
c[i]=a[i]+b[i];
}
void initialise(int a[])
{
int i;
for(i=0;i
}
void multi(int a[],int b[],int c[],int m,int n)
{
int i,j;
for(i=m;i>=0;i--)
for(j=n;j>=0;j--)
c[i+j]=c[i+j]+(a[i]*b[j]);
}
int eval(int a[],int m,int x)
{
int i,p=1,sum=0;
for(i=m;i>=0;i--)
{
p=pow(x,i);
sum=sum+(a[i]*p);
}
return(sum);
}
int pow(int a,int b)
{
int i,p=1;
for(i=1;i<=b;i++)
p=p*a;
return(p);
}
void display(int a[],int n)
{
int i;
for(i=n;i>=0;i--)
if(i==0)
printf("%d",a[i]);
else
printf("%dx^%d+",a[i],i);
}
**********************************************************************************************************************************************************************
Binary search without recurssion
#include
struct actor
{
int actorno;
char name[20];
}a[20];
void bsearch(int,int,int);
void sort(int);
main()
{
int i,n,r,top,bot;
char ch;
FILE *fp;
fp=fopen("d:\\tc\\bin\\sy_ds\\a.dat","w");
printf("\n \t Enter total number of Records : ");
scanf("%d",&n);
for(i=0;i
printf("\n \t Enter Record %d \n",i+1);
printf(" \t Enter Actor Number : ");
scanf("%d",&a[i].actorno);
printf(" \t Enter Actor Name : ");
scanf("%s",a[i].name);
}
sort(n);
for(i=0;i
fclose(fp);
fp=fopen("d:\\tc\\bin\\sy_ds\\a.dat","r");
fread(a,sizeof(a),1,fp);
do
{
top=0;bot=n-1;
printf("\n \t Enter the Actor Number to be Searched : ");
scanf("%d",&r);
bsearch(top,bot,r);
printf("\n \t Search Another (Y/N) : ");
ch=getche();
}while(ch=='y' || ch=='Y');
fclose(fp);
}
void bsearch(int top,int bot,int r)
{
int mid;
while(top<=bot)
{
mid=(int)(top+bot)/2;
if(a[mid].actorno==r)
{
printf("\n \t Search Successful...");
printf("\n \t Name of Actor having No. %d is : %s",a[mid].actorno,a[mid].name);
break;
}
else if(a[mid].actorno>r)
bot=mid-1;
else
top=mid+1;
}
if(top>bot)
{
printf("\n \t Search Failed.\n");
printf(" \t Record Not Found.\n");
}
}
void sort(int n)
{
int ctr=0,temp,i,j;
char nam[20];
for(i=0;i
ctr=0;
for(j=0;j
if(a[j].actorno>a[j+1].actorno)
{
temp=a[j].actorno;
a[j].actorno=a[j+1].actorno;
a[j+1].actorno=temp;
strcpy(nam,a[j].name);
strcpy(a[j].name,a[j+1].name);
strcpy(a[j+1].name,nam);
}
}
if(ctr==0)
break;
}
}
********************************************************************************************************************************************************************************
Dfs of a graph
#include
#define MAX 10
struct stack{int stk[MAX];
int top;
};
typedef struct stack STACK;
int isempty(STACK *s)
{
return(s->top==-1?1:0);
}
void push(int val,STACK *s)
{
s->stk[++s->top]=val;
}
int pop(STACK *s)
{
int val;
val=s->stk[s->top--];
return(val);
}
void accept(int g[10][10],int n)
{
int i,j;
for(i=0;i
printf("Enter [V%d,V%d]entry=> ",i+1,j+1);
scanf("%d",&g[i][j]);
}
}
void display(int g[10][10],int n)
{
int i,j;
printf("\n\t*********ADJACENCY MATRIX************\n");
for(i=0;i
for(i=0;i
printf("\nV%d",i+1);
for(j=0;j
}
}
void dfs(int g[10][10],int n)
{
int visit[MAX],i,j,flag=1;
STACK s;
s.top=-1;
printf("\nDFS IS=>");
for(i=0;i
while((i=getpos(visit,n))!=-1)
{
visit[i]=1;
printf("\n V%d",i+1);
push(i,&s);
while(!isempty(&s))
{
while(flag)
{
flag=0;
i=pop(&s);
for(j=0;j
if(g[i][j]==1&&visit[j]==0)
{
visit[j]=1;
printf(" V%d",j+1);
push(i,&s);
push(j,&s);
flag=1;
break;
}
}
}
flag=1;
}
}
}
int getpos(int v[10],int n)
{
int i;
for(i=0;i
return(i);
return(-1);
}
main()
{
int g[MAX][MAX],n;
printf("\nEnter the number of vertices=> ");
scanf("%d",&n);
accept(g,n);
display(g,n);
dfs(g,n);
}
**************************************************************************************************************************************************************************
PRODRAM ON BFS OF GRAPH
#include
struct q
{
int data[20];
int front,rear;
}q1;
void display(int m[10][10],int n)
{
int i,j;
printf("\n\t*********ADJACENCY MATRIX************\n");
for(i=0;i
for(i=0;i
printf("\nV%d",i+1);
for(j=0;j
}
}
void add(int n)
{
q1.rear++;
q1.data[q1.rear]=n;
}
int del()
{
q1.front++;
return q1.data[q1.front];
}
void initq()
{
q1.front=q1.rear=-1;
}
int emptyq()
{
return (q1.rear==q1.front);
}
void bfs(int m[10][10],int n)
{
int i,j,v,w;
int visited [20];
initq();
for(i=0;i
printf("\nBFS IS=> \n");
v=0;
visited[v]=1;
add(v);
while(!emptyq())
{
v=del();
printf(" V%d",v+1);
for(w=0;w
if((m[v][w]==1)&&(visited[w]==0))
{
add(w);
visited[w]=1;
}
}
}
}
main()
{
int m[10][10],n,i,j;
printf("\nENTER HOW MANY VERTICES=> ");
scanf("%d",&n);
for(i=0;i
printf("Is there an edge between vertex %dand %d(1/0)=>",i+1,j+1);
scanf("%d",&m[i][j]);
}
display(m,n);
bfs(m,n);
}
***********************************************************************************************************************************************************************
HASH TABLE USING LIKKED LIST
#include
struct node
{
int indent;
struct node *next;
}*ht[10];
typedef struct node NODE;
int hash(int x)
{
return x%10;
}
void init()
{
int i;
for(i=0;i<10;i++)
ht[i]=NULL;
}
NODE *findlast(NODE *ht)
{
NODE *ptr;
for(ptr=ht;ptr->next!=NULL;ptr=ptr->next);
return ptr;
}
NODE *add(int id)
{
NODE *New,*temp;
int bk;
bk=hash(id);
New = (NODE *)malloc(sizeof(NODE));
New->indent=id;
New->next=NULL;
/* Add to list */
if( ht[bk]==NULL)
{
ht[bk]=New;
return(ht[bk]);
}
else
{
//temp=findlast(ht[bk]);
temp=ht[bk];
while(temp->next!=NULL)
temp=temp->next;
temp->next=New;
return(temp);
}
}
void del(int id)
{
int bk;
NODE *New , *temp;
bk= hash(id);
New=temp=ht[bk];
if(New->indent==id)
{
ht[bk]=New->next;
free(New);
return;
}
while(New->next!=NULL)
{
if(New->next->indent==id)
{
temp=New;
temp->next = New->next->next;
free(temp);
return ;
}
New=New->next;
}
printf("\n Indentifier not found");
}
void display()
{
NODE *temp;
int i;
for(i=0;i<10;i++)
{
printf("\n Bucket %d\t",i);
for(temp=ht[i];temp!=NULL;temp=temp->next)
printf("->%d",temp->indent);
}
}
main()
{
int ind ,ch;
init();
while(1)
{
printf("\n***MAIN MENU***");
printf("\n 1. ADD");
printf("\n 2. DELETE");
printf("\n 3. DISPLAY");
printf("\n 4. EXIT");
printf("\n Enter ur choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n Enter an identifier:");
scanf("%d",&ind);
add(ind);
break;
case 2:
printf("\n Enter an identifier to be deleted:");
scanf("%d",&ind);
del(ind);
display();
break;
case 3:
display();
break;
case 4:
exit(0);
}
}
}
***************************************************************************************************************************
Program to convert an Infix form to Postfix form
#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( ) ;
}
void initinfix ( struct infix *p )
{
p -> top = -1 ;
strcpy ( p -> target, "" ) ;
strcpy ( p -> stack, "" ) ;
p -> t = p -> target ;
p -> s = "" ;
}
void setexpr ( struct infix *p, char *str )
{
p -> s = str ;
}
void push ( struct infix *p, char c )
{
p -> top++ ;
p -> stack[p -> top] = c ;
}
char pop ( struct infix *p )
{
char item = p -> stack[p -> top] ;
p -> top-- ;
return item ;
}
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' ;
}
int priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void show ( struct infix p )
{
printf ( " %s", p.target ) ;
}
*****************************************************************************************************************************************************
Hope you would have got some help!