REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

Experiment 3
Design and Analysis of Algorithms Lab
20CP209P

AIM: To perform addition, subtraction, multiplication and exponent operations using linked
list.

THEORY: Linked list is a dynamic, linear data structure in which each element is a
separate node and each node contains the address of the next node in the sequence as well as
the data. These ‘links’ make it a linear data structure but there is no way to reach a particular
node without traversing the list until we reach it. The pointer to the first node is the only data
we typically have and this pointer is called the ‘start’ pointer.

CODE: (in C)
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node*link;
};

struct node* add(struct node* a,struct node* b)

{
struct node* z;
struct node* h;

1
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

z=NULL;
int s,c=0;
while((a!=NULL)&&(b!=NULL))
{
s=((a->data)+(b->data)+c);
c=s/10;
h=(struct node*)malloc(sizeof(struct node));
h->data=s%10;
h->link=z;
z=h;
a=a->link;
b=b->link;
}
while(a!=NULL)
{
s=(c+(a->data));
c=s/10;
h=(struct node*)malloc(sizeof(struct node));
h->data=s%10;
h->link=z;
z=h;
a=a->link;
}
while(b!=NULL)
{
s=(c+(b->data));
c=s/10;
h=(struct node*)malloc(sizeof(struct node));
h->data=s%10;
h->link=z;

2
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

z=h;
b=b->link;
}
if(c)
{
h=(struct node*)malloc(sizeof(struct node));
h->data=c;
h->link=z;
z=h;
}
return(z);
}

struct node* sub(struct node* a,struct node* b)

{
struct node* z;
struct node* h;
z=NULL;
int s;
while((a!=NULL)&&(b!=NULL))
{
s=((a->data)-(b->data));
if((s<0)&&(a->link!=NULL))
{
s+=10;
a->link->data-=1;
}
h=(struct node*)malloc(sizeof(struct node));
h->data=s%10;
h->link=z;

3
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

z=h;
a=a->link;
b=b->link;
}
while(a!=NULL)
{
s=a->data;
if((s<0)&&(a->link!=NULL))
{
s+=10;
a->link->data-=1;
}
h=(struct node*)malloc(sizeof(struct node));
h->data=s%10;
h->link=z;
z=h;
a=a->link;
}
while(b!=NULL)
{
s=(0-(b->data));
if((s<0)&&(b->link!=NULL))
{
s+=10;
b->link->data-=1;
}
h=(struct node*)malloc(sizeof(struct node));
h->data=s%10;
h->link=z;
z=h;

4
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

b=b->link;
}
return(z);
}

struct node* prod(struct node* a,struct node* b)

{
struct node* t;
t=(struct node*)malloc(sizeof(struct node));
t->data=0;
t->link=NULL;
struct node* g;
struct node* h;
struct node* x;
int n=1,i;
while(b!=NULL)
{
for(i=0;i<(b->data)*n;i++)
{
g=add(a,t);
h=g;
free(t);
t=(struct node*)malloc(sizeof(struct node));
t->data=h->data;
h=h->link;
t->link=NULL;
while(h!=NULL)
{
x=(struct node*)malloc(sizeof(struct node));
x->data=h->data;

5
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

h=h->link;
x->link=t;
t=x;
}
}
n*=10;
b=b->link;
}
return(g);
}

struct node* expd(struct node* a,struct node* b)

{
int n=1,i;
struct node* p;
struct node* q;
struct node* r;
struct node* t;
r=(struct node*)malloc(sizeof(struct node));
r->data=1;
r->link=NULL;
while(b!=NULL)
{
for(i=0;i<(b->data)*n;i++)
{
q=prod(a,r);
p=q;
p=q;
free(r);
r=(struct node*)malloc(sizeof(struct node));

6
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

r->data=p->data;
p=p->link;
r->link=NULL;
while(p)
{
t=(struct node*)malloc(sizeof(struct node));
t->data=p->data;
p=p->link;
t->link=r;
r=t;
}

}
n*=10;
b=b->link;
}
return(q);
}

void main()
{
int y,i=0,a,b;
struct node* start1;
struct node* start2;
struct node* p;
printf("enter 1st number: ");
scanf("%d",&a);
printf("enter 2nd number: ");
scanf("%d",&b);
int c=a;

7
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

int d=b;
start1=(struct node*)malloc(sizeof(struct node));
y=a%10;
a=a/10;
start1->data=y;
p=start1;
start1->link=NULL;
while(a)
{
y=a%10;
a=a/10;
p->link=(struct node*)malloc(sizeof(struct node));
p=p->link;
p->data=y;
p->link=NULL;
}
start2=(struct node*)malloc(sizeof(struct node));
y=b%10;
b=b/10;
start2->data=y;
p=start2;
start2->link=NULL;
while(b)
{
y=b%10;
b=b/10;
p->link=(struct node*)malloc(sizeof(struct node));
p=p->link;
p->data=y;
p->link=NULL;

8
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

}
printf("\naddition of the 2 numbers: ");
p=add(start1,start2);
while(p!=NULL)
{
printf("%d",p->data);
p=p->link;
}
printf("\nmagnitude of subtraction of the 2 numbers: ");
if(c<d)
p=sub(start2,start1);
else
p=sub(start1,start2);
while(p!=NULL)
{
printf("%d",p->data);
p=p->link;
}
printf("\nproduct of the two numbers: ");
p=prod(start1,start2);
while(p!=NULL)
{
printf("%d",p->data);
p=p->link;
}
printf("\n%d to the power %d = ",c,d);
p=expd(start1,start2);
while(p!=NULL)
{
printf("%d",p->data);

9
REHA SHAH 21BCP148 G5 DAA LAB EXPERIMENT 3

p=p->link;
}
}

OUTPUT:

10