Trivial C, C++ Programs.

Merge Sort in C++

Written by m1k3y on April 11, 2010 — Leave a Comment

Been a while since I posted some code here, this one I’m posting to help a junior from NSIT out.

 
#include <iostream.h>
 
 
int *Arr, maxSize;
 
void createArr()
{
  cout<<"\n\n Enter the maximum size of array : ";
  cin>>maxSize;
  Arr = new int[maxSize];
}
 
void fillArr()
{
  cout<<"\n\n Enter the elements of the array (to be sorted) (maximum "
      <<maxSize<<")";
  int i = 0;
  for (i=0; i<maxSize; i++)
    cin>>Arr[i];
}
 
int* merge(int* l, int* r, int lS, int rS)
{
  int* res, lIndex = 0, rIndex = 0, i = 0, totalSize;
  totalSize = lS + rS;
 
  res = new int[totalSize];
 
  for(i = 0; lIndex != lS && rIndex != rS; i++)
    {
      if (l[lIndex] < r[rIndex])
	{	
	  res[i] = l[lIndex];
	  lIndex++;
	}
      else 
	{
	  res[i] = r[rIndex];
	  rIndex++;
	}
    }
  for(i; i < totalSize; i++)
    {
      if (lIndex < lS)
	{
	  res[i] = l[lIndex];
	  lIndex++;
	}
      else if (rIndex < rS)
	{
	  res[i] = r[rIndex];
	  rIndex++;
	}
    }
  return res;
}
 
int* append (int* l, int* r, int lS, int rS)
{
  int *res, totalSize, i=0, j=0;
 
  totalSize = lS + rS;
 
  res = new int[totalSize];
 
  for (i=0; i < lS; i++)
    {
      res[i] = l[i];
    }
  for (i = lS; i < totalSize; i++)
    {
      res[i] = r[j];
      j++;
    }
  return res;
}
 
int* mergeSort (int* array, int length)
{
  if (length <= 1)
    return array;
 
  int *left, *right, *final, middle = 0, i = 0, j = 0;
 
  middle = length/2;
 
  left = new int[middle];
  right = new int[length-middle];
 
  for (i = 0; i < middle; i++)
    {
      left[i] = array[i];
    }
 
  for (i = middle; i < length; i++)
    {
      right[j] = array[i];
      j++;
    }
 
  left = mergeSort(left, middle);
  right = mergeSort(right, (length-middle));
 
  if (left[middle-1] > right[0])
    final = merge (left, right, middle, length-middle);
  else
    final = append (left, right, middle, length-middle);
 
  return final;
}
 
 
int main()
{
  int choice = 0, *sorted, i=0;
  while (choice != 4)
    {
      cout<<"\n\n Enter choice :"
	  <<"\n 1. Create array."
	  <<"\n 2. Enter elements in array."
	  <<"\n 3. Sort the array using Mergesort."
	  <<"\n 4. Exit. ";
      cin>>choice;
 
      switch(choice)
	{
	case 1:
	  createArr();
 
	  break;
	case 2:
	  fillArr();
	  break;
	case 3:
	  sorted = mergeSort(Arr, maxSize);
	  cout<<"\n\n The sorted array is : \n";
	  for (i=0; i < maxSize; i++)
	    {
	      cout<<sorted[i]<<" ";
	    }
	  break;
	case 4:
	  break;
	default:
	  cout<<"\n Invalid choice entered.";
	  break;
	}
    }
}
Posted in Code Archive | Tagged , ,

Queues Using Linked Lists in C++

Written by m1k3y on November 12, 2009 — 2 Comments

And NO, there is no meaning to adding a special operation called ‘Create’ the queue. When you push in the first element, the queue is created. Of course I didn’t bother to check for exceptions. This is a straight off the text book program, suck on it bitches.

 
#include<iostream.h>
#include<conio.h>
 
struct node
{
  int data;
  node *next;
}*p,*front,*rear;
 
void display();
void push(int);
void pop();
int main()
{
  int choice,item;
	while(choice != 4)
	  {
	    cout<<"\n Enter your choice : ";
	    cout<<"\n 1. Push an element into Queue : "
		<<"\n 2. Pop an element. "
		<<"\n 3. Display elements in queue. "
		<<"\n 4. Exit.\n ";
	    cin>>choice;
		switch(choice)
		  {
		  case 1:
		    cout<<"\nEnter the element you want to insert : ";
		    cin>>item;
		    push(item);
		    break;
		  case 2:
		    pop();
		    break;
		  case 3:
		    display();
		    break;
		  case 4:
		    break;
		  default:
		    cout<<"\n Invalid choice.";
		    break;
		  }
	  }
	  getch();
}
 
void push(int x)
{
  if(front==NULL)
    {
      node *q=new node;
      q->data=x;
      q->next=front;
      front=q;
      rear=q;
      front->next=rear;
    }
  else
    {
      node * t= new node;
      t->data=x;
      rear->next=t;
      rear=t;
    }
}
 
 
void display()
{
  cout<<"\n\n The queue is : \n";
  node* temp=new node;
  temp=front;
  if(temp==NULL)
    cout<<"Queue is empty!";
  else
    {
      do
	{
	  cout<<temp->data<<" << ";
     temp=temp->next;
	}
      while(temp!=rear);
if(front!=rear)
  cout<<rear->data;
    }
}
 
void pop()
{
  if(front->next==rear)
    {
      cout<<"\n The Queue is:\n"<<rear->data;
    }
  else
    {
      node* d;
      d=front;
      front=front->next;
      delete d;
    }
}
Posted in Code Archive | Tagged , , , , , ,

Queues Using Arrays (Static) in C++

Written by m1k3y on November 3, 2009 — Leave a Comment

It does what it says. A first-in first-out structure, implement in the simplest possible way. Again, no bound checks. Sanitize your inputs please.

#include <iostream.h>
 
int *Queue, front, rear, maxSize;
 
void createQueue();
void push();
void pop();
void dispQueue();
 
int main()
{
  int choice;
  while(choice != 5)
    {
      cout<<"\n\n Enter your choice :"
	  <<"\n 1. Create an empty Queue."
	  <<"\n 2. Push an element into Queue."
	  <<"\n 3. Pop an element from Queue."
	  <<"\n 4. Display the Queue."
	  <<"\n 5. Exit the program.\n\n";
      cin>>choice;
 
      switch (choice)
	{
	case 1:
	  createQueue();
	  break;
	case 2:
	  push();
	  break;
	case 3:
	  pop();
	  break;
	case 4:
	  dispQueue();
	  break;
	case 5:
	  break;
	case 6:
	  cout<<"\n Invalid choice.";
	  break;
	}
    }
  std::cin.get();
}
 
void createQueue()
{
  cout<<"\n Enter the maximum size of Queue : ";
  cin>>maxSize;
  Queue = new int[maxSize];
  front=-1;
  rear=-1;
}
 
void push()
{
  if (rear == (maxSize-1))
    {
      cout<<"\n Overflow! No space left in Queue. Cannot push.";
 
    }
  else
    {
      rear++;
      cout<<"\n Enter the element to be pushed in Queue : ";
      cin>>Queue[rear];	
    }
}
 
void pop()
{
  if (front == rear)
    {
      cout<<"\n Underflow! Cannot pop any items because Queue is empty.";
    }
  else
    {
      cout<<"\n The element that was popped was : "<<Queue[++front];
    }
}
 
void dispQueue()
{
  if (front == rear)
    {
      cout<<"\n Queue is empty, no element to display";
    }
  else
    {
      for(int i = (front+1); i<=rear; i++)
	{
	  cout<<Queue[i];
	  if (i != rear)
	    {
	      cout<<"<--";
	    }
	}
    }
}
Posted in Code Archive | Tagged , , , , , , , ,

Stacks Using Arrays (Static) in C++

Written by m1k3y on October 19, 2009 — 1 Comment

This is a general implementation of the stack data structure in C++. I’ve made it a ‘menu-driven’ program, for all you menu-loving whores. Nobody cares if it is rendered unreadable. Also, I’ve skipped bound checks in this program, so remember to sanitize your inputs or you may get sucked into a vortex.

Also, since I’m such a lazy bitch, I didn’t bother with issues relating to scope of the data structure – I made it global for convenience. Take this code, and don’t bitch about it.

 
#include<iostream.h>
 
int *Stack, top=-1, maxSize;
 
void createStack();
void push ();
void pop();
void dispStack();
 
int main()
{
  int choice=0, elem;
  while(choice!=5)
    {
      cout<<"\n\n Enter a choice :"
      <<"\n 1. Create a new empty stack"
      <<"\n 2. Push an element into stack"
      <<"\n 3. Pop an element from stack"
      <<"\n 4. Display the stack"
      <<"\n 5. Exit.\n\n";
      cin>>choice;
      switch (choice)
	{
	case 1:
	  createStack();
	  break;
	case 2:
	  push();
	  break;
	case 3:
	  pop();
	  break;
	case 4:
	  dispStack();
	  break;
	case 5:
	  exit(0);
	  break;
	default:
	  cout<<"\n Invalid choice.";
	  break;
	}
    }
}
 
void createStack()
{
  cout<<"\n Enter maximum size for stack : ";
  cin>>maxSize;
  Stack = new int[maxSize];
}
 
void push()
{
  if (top>=(maxSize-1))
    {
      cout<<"\n Overflow! Element cannot be pushed.";
    }
  else
    {
      top++;
      cout<<"\n Enter element to be pushed into stack : ";
      cin>>Stack[top];
    }
}
 
void pop()
{
  if (top<0)
    {
      cout<<"\n Underflow! Stack is empty, so no element can be popped.";
    }
  else
    {
      cout<<"\n The element that was popped : "<<Stack[top--];
    }
}
 
void dispStack()
{
  if (top<0)
    {
      cout<<"\n Stack is empty, no elements to display.";
    }
  else
    {
      cout<<"\n The stack is : ";
      for (int i=top;i>=0;i--)
	{
	  cout<<"\n"<<Stack[i];
	}
    }
}
Posted in Code Archive | Tagged , , , , , ,

Fibonacci Series (Using Recursion) in C++

Written by m1k3y on October 17, 2009 — 5 Comments

This is a simple 2 statement function that takes n as an argument and returns the nth Fibonacci number. Can be used to display the Fibonacci series upto the integer size limit.

 
#include <iostream.h>
#include <conio.h>
 
unsigned int fibonacci (unsigned int n)
{
  if (n <= 2)
    {
      return 1;
    }
  else
    {
      return fibonacci(n-1) + fibonacci(n-2);
    }
}
 
int main()
{
  unsigned int i, j=0;
 
  cout<<"\n Enter the fibonnaci number : ";
  cin>>i;
 
  for(j=1; j<=i; j++)
    cout<<fibonacci(j)<<" ";
 
  getch();
}
Posted in Code Archive | Tagged , , , , ,

Linear Search in C++

Written by m1k3y on October 16, 2009 — 1 Comment

Oh yeah, they ask us to make Linear Search TOO. This code is as simple as it gets. Sorry, but making it any simpler would make my eyes bleed. Here you go.

 
#include <iostream.h>
#include <conio.h>
 
int linearSearch(int*, int, int, int);
 
int main()
{
  int *sArray, mSize, i, elem, index;
 
  cout<<"\n Enter the maximum size of array : ";
  cin>>mSize;
 
  sArray = new int[mSize];
 
  cout<<"\n Enter the elements of the array : \n";
 
  for (i=0; i<mSize; i++)
    {
      cin>>sArray[i];
    }
 
  cout<<"\n Enter the element to be searched : ";
  cin>>elem;
 
  index = linearSearch (sArray, 0, mSize-1, elem);
 
  if (index < 0)
    {
      cout<<"\n Element not found";
    }
  else
    {
      cout<<"\n The element was found at index "<<index;
    }
 
    getch();
 
}
 
int linearSearch(int sArray[], int first, int last, int elem)
{
  int i = 0;
 
  for (i = first; i <= last; i++)
    {
      if (sArray[i] == elem)
	{
	  return i;
	}
    }
 
  return -(first + 1);
}
Posted in Code Archive | Tagged , , , , ,

Binary Search in C++

Written by m1k3y on October 15, 2009 — Leave a Comment

Now the important thing to note here is that Binary Search only has a meaning when your input is sorted in some way, using some parameter as basis for sorting. This program implements binary search for a set of integers, sorted in ascending order. Binary search on an unsorted input makes no sense as if you first sort it and then reveal its position, the position has changed from what you initially gave as input, and is therefore, meaningless.

This should be the one your teacher will ask you to make. If its any different, please post a comment, I will try to make you a custom one according to your needs.

 
#include <iostream.h>
#include <conio.h>
 
 
int binarySearch(int*, int, int, int);
 
int main()
{
  int *sArray, mSize, i, elem, index;
 
  cout<<"\n Enter the maximum size of array : ";
  cin>>mSize;
 
  sArray = new int[mSize];
 
  cout<<"\n Enter the elements of the array, sorted in ascending order : \n";
 
  for (i=0; i<mSize; i++)
    {
      cin>>sArray[i];
    }
 
  cout<<"\n Enter the element to be searched : ";
  cin>>elem;
 
  index = binarySearch (sArray, 0, mSize-1, elem);
 
  if (index < 0)
    {
      cout<<"\n Element not found";
    }
  else
    {
      cout<<"\n The element was found at index "<<index;
    }
 
    getch();
 
}
 
 
int binarySearch(int sArray[], int first, int last, int elem) 
{
  while (first < last)
    {
      int mid = (first + last) / 2;
 
      if (elem > sArray[mid])
	{
	  first = mid + 1;
	}
      else if (elem < sArray[mid])
	{
	  last = mid - 1;
	}
      else
	{
	  return mid;
	}
    }
  return -(first + 1);
}
Posted in Code Archive | Tagged , , , , , ,