Useful Links to C/C++

/*21. Using pointers & dynamic variables,write a C program to implement a
   singly linked list.The information field to a node contains an integer
   value.The operations to be supported are:
   a>Insert a new node at the position such that the list remains sorted in
     ascending order.
   b>Delete a node at the specified position(first position is counted as one)
   c>Display all the elements of the list.  */

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define NULL '0'

struct n {
   int info;
   struct n *next;
  };
typedef struct n node;
main()
{
 node *first=NULL;
 int ch;
 node *create();
 node *insert();
 node *del();
 void display();
 clrscr();
 do
 {
  printf("\n1.Create the linked list");
  printf("\n2.Insert a new node");
  printf("\n3.Delete a node at specified position");
  printf("\n4.Display all elements of list");
  printf("\n5.Quit");
  printf("\nSelect any one of the above==>");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1: first=create(first);
    display(first);
    break;
   case 2: first=insert(first);
    display(first);
    break;
   case 3: first=del(first);
    display(first);
    break;
   case 4: display(first);
    break;
   default:printf("\nInvalid Choice! Please try again");
  }
 }while(ch!=5);
}

node *create(node *first)
{
 node *temp,*prev=NULL,*ne;
 int item;
 first=prev;
 printf("\nEnter the data & -999 to exit:");
 scanf("%d",&item);
 while(item!=-999)
 {
  temp=(node*)malloc(sizeof(node));
  temp->next=NULL;
  temp->info=item;
  if(first==NULL)
 first=temp;
  else
  {
   prev=first;
   for(ne=first;(ne!=NULL && ne->info<item);ne=ne->next)
 prev=ne;
   if(prev==first && ne==first)
   {
    first=temp;
    temp->next=prev;
   }
   else
   {
    prev->next=temp;
    temp->next=ne;
   }
  }
  printf("\nEnter the data & -999 to exit:");
  scanf("%d",&item);
 }
 return(first);
}

node *insert(node *first)
{
 node *temp,*prev,*ne;
 int item;
 printf("\nEnter the data:");
 scanf("%d",&item);
 temp=(node*)malloc(sizeof(node));
 temp->next=NULL;
 temp->info=item;
 if(first==NULL)
 first=temp;
 else
 {
  prev=first;
  for(ne=first;(ne!=NULL && ne->info<item);ne=ne->next)
 prev=ne;
  if(prev==first && ne==first)
  {
   first=temp;
   temp->next=prev;
  }
  else
  {
   prev->next=temp;
   temp->next=ne;
  }
 }
 return(first);
}

node *del(node *first)
{
 node *temp,*prev;
 int i=1,pos;
 printf("Enter the position to be deleted:");
 scanf("%d",&pos);
 prev=first;
 for(temp=first;(temp!=NULL && i<pos);temp=temp->next)
 {
  prev=temp;
  i++;
 }
 if(prev==first && temp==first)
 first=first->next;
 if(temp!=NULL)
 prev->next=temp->next;
 else
 printf("\nThe element was not found");
 return(first);
}

void display(node *first)
{
 node *temp;
 for(temp=first;temp!=NULL;temp=temp->next)
 {
  printf("%d",temp->info);
  if(temp->next!=NULL)
 printf("====>");
 }
 getch();
}

/*22. Write a C program to represent a polynomial in two variables(x,y).Each
      node should represent a term and should contain powers of x,y as well
      as the coefficients of those terms.Using this representation,implement
      evaluation of the polynomials for given values of x and y.  */

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<conio.h>
#define NULL '0'

struct node{
     int px,py,pc;
     struct node *link;
    };
typedef struct node nd;
main()
{
 int x,y,c;
 nd *p1=NULL;
 nd *insert();
 void d();
 int add();

 clrscr();
 printf("\nInput the powers and coeff of one term of the polynomial\n");
 scanf("%d %d %d",&x,&y,&c);
 while(c!=0)
 {
  p1=insert(p1,x,y,c);
  printf("\nInput the powers and coeff of one term of the polynomial\n");
  scanf("%d %d %d",&x,&y,&c);
 }
 printf("\nThe polynomial is:\n");
 d(p1);
 printf("\nThe value of polynomial is %d\n",add(p1));
 getch();
}

nd *insert(nd *p,int x,int y,int c)
{
 nd *temp=p;
 while(!(temp->px==x && temp->py==y) && temp!=NULL)
 temp=temp->link;
 if(temp!=NULL)
 {
  temp->pc+=c; /* add the coeff's of 2 terms if there powers are same */
  return(p);
 }
 temp=(nd*)malloc(sizeof(nd));  /* create new node for new term */
 temp->link=NULL;
 temp->px=x;
 temp->py=y;
 temp->pc=c;
 if(p==NULL)
 return(temp);
 temp->link=p;
 p=temp;
 return(p);
}

int add(nd *p)
{
 nd *s;
 int x,y,sum=0;
 printf("\nInput the values of x and y\n");
 scanf("%d %d",&x,&y);
 for(s=p;s!=NULL;s=s->link)
 sum+=s->pc*pow(x,s->px)*pow(y,s->py);
 return(sum);
}

void d(nd *r)
{
 nd *temp;
 for(temp=r;temp!=NULL;temp=temp->link)
 printf("+%dx^%dy^%d",temp->pc,temp->px,temp->py);
}
 
/*23. Write a C program to represent a polynomial in two variables(x,y).Each
      node should represent a term and should contain powers of x,y as well
      as the coefficients of those terms.Using this representation,implement
      the addition of two such polynomials.  */

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<conio.h>
#define NULL '0'

struct node{
     int px,py,pc;
     struct node *link;
    };
typedef struct node nd;
main()
{
 int x,y,c;
 nd *p1=NULL,*p2=NULL,*sum=NULL;
 nd *insert();
 nd *add();
 void d();
 clrscr();
 printf("\nInput the powers and coeff of first term of first polynomial\n");
 scanf("%d %d %d",&x,&y,&c);
 while(c!=0)
 {
  p1=insert(p1,x,y,c);
  printf("\nInput the powers and coeff of next term of the polynomial\n");
  scanf("%d %d %d",&x,&y,&c);
 }
 printf("\nInput the powers and coeff of first term of second polynomial\n");
 scanf("%d %d %d",&x,&y,&c);
 while(c!=0)
 {
  p2=insert(p2,x,y,c);
  printf("\nInput the powers and coeff of next term of the polynomial\n");
  scanf("%d %d %d",&x,&y,&c);
 }
 printf("\nThe first polynomial is:\n");
 d(p1);
 printf("\nThe second polynomial is:\n");
 d(p2);
 printf("\nThe sum of two polynomials is:\n");
 sum=add(p1,p2);
 d(sum);
 getch();
}

nd *insert(nd *p,int x,int y,int c)
{
 nd *temp=p;
 while(!(temp->px==x && temp->py==y) && temp!=NULL)
 temp=temp->link;
 if(temp!=NULL)
 {
  temp->pc+=c; /* add the coeff's of 2 terms if there powers are same */
  return(p);
 }
 temp=(nd*)malloc(sizeof(nd));  /* create new node for new term */
 temp->link=NULL;
 temp->px=x;
 temp->py=y;
 temp->pc=c;
 if(p==NULL)
 return(temp);
 temp->link=p;
 p=temp;
 return(p);
}

nd *add(nd *p,nd *q)
{
 nd *s;
 for(s=q;s!=NULL;s=s->link)
 p=insert(p,s->px,s->py,s->pc);
 return(p);
}

void d(nd *r)
{
 nd *temp;
 for(temp=r;temp!=NULL;temp=temp->link)
 printf("+%dx^%dy^%d",temp->pc,temp->px,temp->py);
}

/*24. Program to sort numbers using merge sort */
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
void merge_sort(float list[],int top,int size,int bot)
{
int u,f1,s1,t1;
float tmp[10000];
f1=top; //f1=start(start of 1 half)
s1=size+1; //s1=midpt(start of 2 half)
t1=top;
while((f1<=size) && (s1<=bot))
{ //list[] is the array passed from calling program
if(list[f1]<=list[s1]) //compare the first element of the 1 half with
{ //the first element of the 2 half
tmp[t1]=list[f1]; //already sorted,so put first element of 1 half of the
f1=f1+1; //array in tmp[];increment the index of 1 half
}
else
{
tmp[t1]=list[s1]; //not in sorted order,so put first element of 2 half of
s1=s1+1; //the array in tmp[];increment the index of 2 half
}
t1=t1+1; //increment the index of tmp[]
} //end while
if(f1<=size)
{
for(f1=f1;f1<=size;f1++)
{
tmp[t1]=list[f1];
t1=t1+1;
}
}
else
{
for(s1=s1;s1<=bot;s1++)
{
tmp[t1]=list[s1];
t1=t1+1;
}
}
for(u=top;u<=bot;u++)
list[u]=tmp[u];
return;
}

void merge_pass(float a[],int m,int n) // m is the start,n is the end
{
int h;
if(m!=n)
{
h=(m+n)/2; //h is the midpoint
merge_pass(a,m,h); //mergepass start to midpoint ;recursion used(1 half)
merge_pass(a,h+1,n); //mergepass midpoint to start ;recursion used(2 half)
merge_sort(a,m,h,n); //m=start,h=midpoint,n=end
}
return;
}

void main()
{
float vector[10000];
int i,n;
clock_t start,end;
void merge_sort();
void merge_pass();

clrscr();
printf("Size of the List ? ");
scanf("%d",&n);
printf("\nRandom Elements from 0-1999 are inputted\n");
getch();
for(i=0;i<n;i++)
vector[i]=random(2000);
i=0;
start=clock();
merge_pass(vector,i,n-1); //i=0,n=is the size of the array
end=clock();
printf("\nMerge sorted list:\n");
for(i=0;i<n;i++)
printf("%8.1f",vector[i]);
printf("\nTime taken by the program = %f seconds",(end-start)/CLK_TCK);
getch();
}

Working of Quick Sort

/*25. Quick Sort */
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
#define MAX 10000

void main()
{
int data[MAX];
int l,n,i;
void quicksort();
clock_t start,end;

clrscr();
printf("\nEnter the size of array:");
scanf("%d",&n);
randomize();
printf("Input of array is random elements from 0-1999:\n");
getch();
for(i=0;i<n;i++)
data[i]=random(2000);
start=clock();
quicksort(data,0,n-1);
end=clock();
printf("\nSorted array:\n");
for(i=0;i<n;i++)
printf("%d ",data[i]);
printf("\nTime taken = %8.8f seconds",(end-start)/CLK_TCK);
getch();
}

void quicksort(int a[],int l,int r)
{
int i,j,x,temp;
i=l;j=r;
x=a[l];
do
{
while(a[i]<x)
i+=1;
while(x<a[j])
j-=1;
if(i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i+=1;
j-=1;
}
}while(i<j);
if(l<j) quicksort(a,l,j); // Recursion used
if(i<r) quicksort(a,i,r); // Recursion used
}

Working of Quick Sort

/*26. Warshalls algorithm */
#include<stdio.h>
int i,j,k,n,p[10][10],a[10][10];
void getdata();
void warshall();
void display();
void init();
void main()
{
char c;
for(;;)
{
printf("\nPress 'y' to Continue (y/n):");
scanf("%c",&c);
switch(c)
{
case 'y':clrscr();
getdata();
init();
warshall();
display();
break;
case 'n':printf("\nBye!");
exit(0);
break;
default: printf("\nInvalid Entry!");
break;
}
}
}
void getdata()
{
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
void init()
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=a[i][j];
}
void warshall()
{
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=p[i][j] | (p[i][k] & p[k][j]);
}
void display()
{
printf("\nThe Path matrix is:\n");
for(i=0;i<n;i++)
{
{
for(j=0;j<n;j++)
printf("%d",p[i][j]);
}
printf("\n");
}
}

/27. * HASH SORT
Write a Program to sort a given set of N integers using address
calculation sort(Hash sort) : Working of Hash Sort */
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
typedef struct nd
{
int x;
struct nd *next;
}*node;
void insert(node *head,int x)
{
node new,temp,pr;
new=(node)malloc(sizeof(struct nd));
new->x=x;
if(*head==NULL || (*head)->x >= x) /* Insert at the begining */
{
new->next=*head;
*head=new;
}
else
{
temp=*head;
pr=temp;
while(temp!=NULL && temp->x <= x)
{
pr=temp;
temp=temp->next;
}
pr->next=new; /* Insert in the middle */
new->next=temp;
}
}
hassing(int x)
{
return(x/10);
}
void hashsort()
{
node has[25],temp;
int x,first,n,i;
for(i=0;i<=25;i++)
has[i]=NULL; /* Initialize Pointers to NULL */
printf("\nEnter the no of elements:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\nEnter the element:");
scanf("%d",&x);
first=hassing(x); /* Get the first digit of the entered */
insert(&has[first],x); /* 2 digit number */
} /* Insert the no at the "first" position in ll */
printf("\nThe Hash sorted elements are:\n");
for(i=1;i<=n;i++)
{
temp=has[i];
while(temp!=NULL)
{
printf("%10d",temp->x);
temp=temp->next;
}
}
}
void main()
{
char ch;
for(;;)
{
printf("\nHash Sort ? (y/n) :");
scanf("%c",&ch);
if(ch=='n' | ch=='N')
exit(1);
else hashsort();
}
}

Working of Hash Sort

Useful Links to C/C++

© Copyrights Madhu Sudan Rao G.K