/* Polynomials like 2x^3 + 7x^2 + 10x -8 can be maintined using a linked list*/
/* program to add two polynomials maintained as linked lists */
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
/* structure representing a node of a linked list and also a term of a
polynomial */
struct polynode
{
float coeff;
int exp;
struct polynode *link;
};
typedef struct polynode *NODEPTR;
void poly_append(NODEPTR*,float,int);
void poly_addition(NODEPTR,NODEPTR,NODEPTR*);
void display(NODEPTR);
main()
{
NODEPTR first,second,total;
int i=0;
clrscr();
first = second = total = NULL; /* empty linked lists */
poly_append(&first,1.4,5);
poly_append(&first,1.5,4);
poly_append(&first,1.7,2);
poly_append(&first,1.8,1);
poly_append(&first,1.9,0);
display(first);
poly_append(&second,1.5,6);
poly_append(&second,2.5,5);
poly_append(&second,-3.5,4);
poly_append(&second,4.5,3);
poly_append(&second,6.5,1);
printf("nn");
display(second);
/* draws a dashed horizontal line */
printf("n");
while(i++<79)
printf("-");
printf("nn");
poly_addition(first,second,&total);
display(total); /* displays the resultant polynomial */
}
void poly_append(NODEPTR *q,float coeff,int expo)
{
NODEPTR temp;
temp = *q;
/* creates a new node if the list is empty */
if(*q == NULL)
{
*q = (NODEPTR)malloc(sizeof(struct polynode));
temp = *q;
}
else
{
/* traverse the entire linked list */
while(temp->link !=NULL)
temp = temp -> link;
/* creates new nodes at intermediate stages */
temp -> link = (NODEPTR) malloc(sizeof(struct polynode));
temp = temp ->link;
}
/* assigning coefficient and exponent */
temp -> coeff = coeff;
temp -> exp = expo;
temp -> link = NULL;
}
void display(NODEPTR q)
{
/* Traverse till the end of the linked list */
while(q!=NULL)
{
printf("%.1fx^%d+",q->coeff,q->exp);
q = q->link;
}
printf("b "); /* erases the last colon */
}
/* adds two polynomials */
void poly_addition(NODEPTR f, NODEPTR s,NODEPTR *t)
{
NODEPTR z;
/* if both linked lists are empty */
if(f == NULL && s == NULL)
return;
/* traverse till one of the list ends */
while(f != NULL && s != NULL)
{
/* creates a new node if the list is empty */
if(*t == NULL)
{
*t = (NODEPTR) malloc(sizeof(struct polynode));
z = *t;
}
/* creates new nodes at intermediate stages */
else
{
z -> link = (NODEPTR) malloc(sizeof(struct polynode));
z = z -> link;
}
/* stores a term of the larger degree polynomial */
if( f -> exp < s ->exp)
{
z -> coeff = s -> coeff;
z -> exp = s->exp;
s = s -> link;
}
else
{
if(f -> exp > s ->exp)
{
z -> coeff = f ->coeff;
z -> exp = s -> exp;
f = f -> link;
}
else
{
/* add the coefficients, when exponents are equal */
if(f -> exp == s ->exp)
{
/* assigning the added coefficient*/
z->coeff = f->coeff + s->coeff;
z->exp = f->exp;
f = f->link;
s = s->link;
}
}
}
}
/* assigning the remaining items of the first polynomial to the result */
while(f != NULL)
{
if(*t == NULL)
{
*t = (NODEPTR) malloc(sizeof(struct polynode));
z = *t;
}
else
{
z -> link = (NODEPTR) malloc(sizeof(struct polynode));
z = z-> link;
}
/* assigning coefficient and exponent */
z->coeff = f->coeff;
z->exp = f->exp;
f = f->link;
}
/* assigning the remaining items of the second polynomial to the result */
while(s != NULL)
{
if(*t == NULL)
{
*t = (NODEPTR) malloc(sizeof(struct polynode));
z = *t;
}
else
{
z -> link = (NODEPTR) malloc(sizeof(struct polynode));
z = z-> link;
}
/* assigning coefficient and exponent */
z->coeff = s->coeff;
z->exp = s->exp;
s = s->link;
}
z ->link = NULL;
}
/*pascal*/
#include<stdio.h>
#include<conio.h>
main()
{
static int a[20][20];
int i,j,n;
clrscr();
printf("n Enter n : ");
scanf("%d",&n);
a[0][0] = 1;
for(i=1;i<=n;i++)
{
for(j=n;j>=i;j--)
printf(" ");
for(j=1;j<=i;j++)
{
/* Pascal triangle elements are given by
a[i][j] = a[i-1][j-1] + a[i-1][j] */
a[i][j] = a[i-1][j-1] + a[i-1][j];
printf("%5d",a[i][j]);
}
printf("n");
}
}
/* Quick Sort or Partition Exchange Sort */
#include<stdio.h>
#include<conio.h>
#define MAX 10
void quick(int [],int,int);
void partition(int x[],int,int,int*);
void quick(int x[],int lb,int ub)
{
int j;
if(lb>=ub)
return; /* array is sorted */
partition(x,lb,ub,&j);
/* recursively sort the subarray between positions
lb and j-1 */
quick(x,lb,j-1);
/* recursively sort the subarray between positions
j+1 and ub */
quick(x,j+1,ub);
}
void partition(int x[],int lb,int ub,int *pj)
{
int a,down,temp,up;
a = x[lb]; /* a is the element whose final
position is sought */
up = ub;
down = lb;
while(down<up)
{
while(x[down]<=a && down <ub)
down++; /* move up the array */
while(x[up]>a)
up--; /* move down the array */
if(down<up)
{
/* interchange x[down] and x[up] */
temp = x[down];
x[down] = x[up];
x[up] = temp;
}
}
x[lb] = x[up];
x[up] = a;
*pj = up;
}
main()
{
int x[MAX],i,n,lb=0;
clrscr();
printf("n Enter Limit : ");
scanf("%d",&n);
printf("n Enter Elements :: ");
for(i=0;i<n;i++)
scanf("%d",&x[i]);
printf("n Before Sorting Ele Are : n");
for(i=0;i<n;i++)
printf("%5d",x[i]);
quick(x,lb,n-1);
printf("n After Sorting Ele Are : n");
for(i=0;i<n;i++)
printf("%5d",x[i]);
}
/* radix sort */
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define MAX 10
void radixsort(int [],int);
main()
{
int a[MAX],n,i;
clrscr();
printf("n Enter num of elements : ");
scanf("%d",&n);
printf("n Enter elements : n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("n Before Sorting Elements Are : n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
radixsort(a,n);
printf("n After Sorting Elements Are : n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
}
void radixsort(int x[],int n)
{
int front[10],rear[10];
struct{
int info;
int next;
}node[MAX];
int exp,first,i,j,k,p,q,y;
/* Initialize linked list */
for(i=0;i<n-1;i++)
{
node[i].info = x[i];
node[i].next = i+1;
}
node[n-1].info = x[n-1];
node[n-1].next = -1;
first = 0; /* first is the head of the linked list */
for(k=1;k<5;k++)
{
/* Assume we have four digit numbers */
for(i=0;i<10;i++)
{
/* Initialize queues */
rear[i] = -1;
front[i] = -1;
}
/* Process each element in the list */
while(first != -1)
{
p = first;
first = node[first].next;
y = node[p].info;
/* Extract the kth digit */
exp = pow(10,k-1); /* raise 10 to (k-1)th power */
j = (y/exp)%10;
/* Insert y into queue[j] */
q = rear[j];
if(q == -1)
front[j] = p;
else
node[q].next = p;
rear[j] = p;
}
/* At this point each record is in its proper queue based on digit k.
We now form a single list from all the queue elements. Find the
first element. */
for(j=0;j<10 && front[j] == -1;j++);
first = front[j];
/* Link up remaining queues */
while(j <= 9) /* Check if finished */
{
/* find the next element */
for(i = j+1; i<10 && front[i] == -1;i++);
if(i<=9)
{
p = i;
node[rear[j]].next = front[i];
}
j = i;
}
node[rear[p]].next = -1;
}
/* Copy back to original array */
for(i = 0;i<n;i++)
{
x[i] = node[first].info;
first = node[first].next;
}
}
/* program for Towers of HANOI using recursion */
/* To move n disks from peg A to peg C, using peg B as auxiliary */
/*
1. If n == 1, move the single disk from A to C and stop.
2. Move the top n-1 disks from A to B, using C as auxiliary.
3. Move the remaining disk from A to C.
4. Move the n-1 disks from B to C, using A as auxiliary.
*/
#include<stdio.h>
#include<conio.h>
void towers(int,char,char,char);
main()
{
int n;
clrscr();
printf("n Enter num of disks : ");
scanf("%d",&n);
towers(n,'A','C','B');
}
void towers(int n,char frompeg,char topeg,char auxpeg)
{
/* If only one disk, make the move and stop */
if(n == 1)
{
printf("nmove disk 1 from peg %c to peg %c",frompeg,topeg);
return;
}
/* Move top n-1 disks from A to B, using C as auxiliary */
towers(n-1,frompeg,auxpeg,topeg);
/* move remaining disk from A to C */
printf("nmove disk %d from peg %c to peg %c",n,frompeg,topeg);
/* Move n-1 disk from B to C using A as auxiliary */
towers(n-1,auxpeg,topeg,frompeg);
}
/* pascal */
#include<stdio.h>
#include<conio.h>
main()
{
long int fact(int);
int i,j,k,m,n;
clrscr();
printf("n Enter number of lines : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(k=0;k<20-(2*i);k++)
printf(" ");
for(j=0;j<=i;j++)
{
m = fact(i) /(fact(j) * fact(i-j));
printf("%5d",m);
}
printf("n");
}
}
long int fact(int n)
{
long int f = 1;
int i;
for(i=1;i<=n;i++)
f = f * i;
return(f);
}
/* heap sort */
#include<stdio.h>
#include<conio.h>
#define MAX 20
int delheap(int [],int);
void insheap(int tree[],int n,int item);
void insheap(int tree[],int n,int item)
{
int ptr,par;
ptr = n;
/* find location to insert item */
while(ptr>1)
{
par = ptr/2; /* location of parent node */
if(item <= tree[par])
{
tree[ptr] = item;
return;
}
tree[ptr] = tree[par];
ptr = par;
}
tree[1] = item;
}
int delheap(int tree[],int n)
{
int item,last,ptr,left,right;
item = tree[1]; /* remove root of tree */
last = tree[n];
ptr = 1,left = 2,right = 3;
while(right <= n)
{
if(last >= tree[left] && last >= tree[right])
{
tree[ptr] = last;
return item;
}
if(tree[right] <= tree[left])
{
tree[ptr] = tree[left];
ptr = left;
}
else
{
tree[ptr] = tree[right];
ptr = right;
}
left = 2 * ptr;
right = left + 1;
}
if(left == n && last < tree[left])
ptr = left;
tree[ptr] = last;
return(item);
}
main()
{
int a[MAX],i,j,n,u;
printf("n Enter Limit : ");
scanf("%d",&n);
u = n;
printf("n Enter ele :: ");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("n Before Sorting Elements are : ");
for(i=1;i<=n;i++)
printf("%10d",a[i]);
for(j=1;j<=n;j++)
insheap(a,j,a[j]);
while(u>1)
{
a[u] = delheap(a,u);
u--;
}
printf("n After Sorting Elements are : ");
for(i=1;i<=n;i++)
printf("%10d",a[i]);
}
/* Merge Sort */
#include<stdio.h>
#include<conio.h>
#define MAX 10
void mergesort(int [],int);
main()
{
int x[MAX],i,n;
clrscr();
printf("n Enter num of elements : ");
scanf("%d",&n);
printf("n Enter elements : ");
for(i=0;i<n;i++)
scanf("%d",&x[i]);
printf("n Before Sorting Ele Are : n");
for(i=0;i<n;i++)
printf("%5d",x[i]);
mergesort(x,n);
printf("n After Sorting Ele Are : n");
for(i=0;i<n;i++)
printf("%5d",x[i]);
}
void mergesort(int x[],int n)
{
int aux[MAX],i,j,k,l1,l2,size,u1,u2;
size = 1; /* Merge files of size 1*/
while(size<n)
{
l1 = 0; /* Initialize lower bounds of first file */
k = 0; /* k is index for auxiliary array. */
while(l1+size < n)
{
/* check to see if there are two files to merge */
/* compute remaining indices */
l2 = l1 + size;
u1 = l2 -1;
u2 = (l2 + size -1 < n) ? l2+size-1 : n-1;
/* proceed through the two subfiles */
for(i = l1,j=l2;i<=u1 && j<= u2;k++)
{
/* Enter smaller into the array aux */
if(x[i] <= x[j])
aux[k] = x[i++];
else
aux[k] = x[j++];
}
/* At this point, one of the subfiles has
been exhausted. Insert any remaining portions
of the other file */
for(;i<= u1;k++)
aux[k] = x[i++];
for(;j<= u2;k++)
aux[k] = x[j++];
/* Advance l1 to the start of the next pair of files.*/
l1 = u2 + 1;
}
/* copy any remaining single file */
for(i = l1;k<n;i++)
aux[k++] = x[i];
/* copy aux into x and adjust size */
for(i =0;i<n;i++)
x[i] = aux[i];
size *= 2;
}
}
/* program to print fibonacci series */
/* 0 1 1 2 3 5 8 13 21.............. */
#include<stdio.h>
#include<conio.h>
/* main()
{
int num,fibo=0,f1=1,f2,i;
clrscr();
printf("n How Many Fibo Numbers Do U Want : ");
scanf("%d",&num);
printf("n%d Fibo series are : n",num);
for(i=1;i<=num;i++)
{
printf(" %d ",fibo);
f2 = fibo + f1;
fibo = f1;
f1 = f2;
}
} */
/* program to generate fibonacci numbers with in a limit */
/* main()
{
int num,fibo=0,f1=1,f2;
clrscr();
printf("n Enter a number : ");
scanf("%d",&num);
printf("n Fibo series with in %d are : n",num);
while(fibo <= num)
{
printf(" %d ",fibo);
f2 = fibo + f1;
fibo = f1;
f1 = f2;
}
} */
/* program to find nth number in the fibo series using recursion */
#include<stdio.h>
#include<conio.h>
int fibo(int n)
{
int f1,f2;
if(n<=1)
return(n);
f1= fibo(n-1);
f2 = fibo(n-2);
return(f1+f2);
/* return(fibo(n-1) + fibo(n-2)); */
}
main()
{
int num,fib;
clrscr();
printf("n Enter a number : ");
scanf("%d",&num);
fib = fibo(num-1);
printf("n element %d in fibo series is %d",num,fib);
}