Thursday, December 9, 2010

Insert and Reverse Nodes

/*
 * midtermPraj.cpp
 *
 *  Created on: Nov 16, 2010 *
 *  
 *      Description:
 *      Write a C++ class that establishes a data structure for storing floating-point values. Implement
 *   the data structure using a singly linked list. Required methods:
 * Insert_Nodes, Display_Nodes, and Reverse_Nodes.
 */

#include <iostream>
#include <fstream>

using namespace std;
const char INPUT_PATH_FILE[] = "C:\\Users\\Shiva\\workspace\\midtermPraj\\floatingPoints.txt";

// Structure for our float node
struct Float_Node {
float Value; // Holds value
struct Float_Node* Next; // Holds the address.
};

class linkedList {
private:
Float_Node* base;
Float_Node* p;
Float_Node* q;
//Float_Node* r;

public:
linkedList();
void insertNodes(double);
void displayNodes();
void reverseNodes();
~linkedList();
};

linkedList::linkedList() {
// Default Constructor
base = NULL;
}

linkedList::~linkedList() {
//Destructor
while(base){
p = base;
base = base->Next;
delete p;
}
}
void linkedList::insertNodes(double input) {
// Method to insert the nodes in the linked list created.
p = new struct Float_Node;
p->Value = input;
p->Next = NULL;
if(base){
q = base;
while(q->Next != NULL) {
q = q->Next;
}
q ->Next = p;
} else {
base = p;
}
}

void linkedList::displayNodes() {
// This method displays the linked list we created.
if(base){
q = base;
while(q){
cout << q->Value << endl;
q = q->Next;
}
} else {
cout << endl << "\aNo link list found. "<< endl;
}

}

void linkedList::reverseNodes() {
// This method reverses the nodes in the link list we created.
//p = new struct Float_Node;
if(base) {
q = base;
base = NULL;
while(q) {
p = new struct Float_Node;
p->Value = q->Value;
q = q->Next;
p->Next = NULL;
if (base) {
p->Next = base;
base = p;
} else {
base = p;
}
}
}
}

int main() {
linkedList obj; // Instance of the class linkedList.
double input; // Variable to hold the input from the input file "floatingPoints.txt".

ifstream InFile;
InFile.open(INPUT_PATH_FILE); // Reading the input file data.

if (InFile) {
// Executes only when input file is read successfully.
while (InFile >> input) {
// Executes until the file has data which is stored in variable input.
obj.insertNodes(input); // using the method to insert nodes creating a linked list.
}
InFile.close();
// Closing the input file as it is not necessary from this point.
cout << endl << "Inserting the nodes in the linked list......." << endl;
obj.displayNodes(); // Using the function to display the nodes that were inserted.

obj.reverseNodes(); // Now, using the function to reverse the nodes inserted.
cout << endl << "Reversing the nodes in the linked list......." << endl;
obj.displayNodes(); // Using the function to display the reversed nodes in the linked list.

} else { // Executes when the file in not opened.
cout << endl << "Error!! The file couldn't be read! Please check the path where your input file resides.";
}
return 0;
}

Square Root using Recursive Function

/*
 * SquareRoot.cpp
 *
 *  Created on: Dec 2, 2010
 *      Program Description:
 *      This program would calculate the square root of a number entered by user using
 *      recursive function as well as the non recursive version of it.
 */

#include<iomanip>
#include<cmath>
#include<iostream>

using namespace std;

const double tol = 1.0E-4; // Tolerance constant.

// Function Prototypes
double sqrRootRecursive(double, double, double);
double sqrRootNonRecursive(double, double, double);

// Function Definitions
double sqrRootRecursive(double number, double approx, const double tol) {
// Using Recursive function to calculate Square Root of user input.
if (fabs (approx * approx - number) <= tol)
return approx;
else if (fabs((approx * approx) - number) > tol)
approx = sqrRootRecursive(number, (approx * approx + number) / (2 * approx), tol);

return approx;
}

double sqrRootNonRecursive(double number, double approx, double tol) {
// Using non recursive function to calculate Square Root of user input.
while(fabs(approx * approx - number) != tol && fabs(approx * approx - number) > tol) {
approx = (approx * approx + number) / (2 * approx);
}
return approx;
}

int main(void) {
double numInput; // Variable created to hold user input.
double approximation;
// Variable created to hold approximation so that if user inputs 0 then the
// Square Root of 0 is evaluated as 0 not 0.00781305

cout << endl << "----------------------";
cout << endl << "SQUARE ROOT CALCULATOR";
cout << endl << "----------------------\n";
cout << "Enter the number to get the Square Root: \n";
cin >> numInput; // User input stored in variable "numInput".

while(numInput < 0.0) {
// If the user inputs negative numbers than we prompt them to
// enter the positive number.
cout << endl << "Error!! Please Enter Positive Number: \n";
cin >> numInput;
}

approximation = numInput / 10000;
// To get the approximate value of the Square Root Operation.

double sqrRootRec = sqrRootRecursive(numInput, approximation, tol);
// Square Root using recursive function is stored in variable "sqrRootRec".
cout << endl << "Square Root of " << numInput << " using Recursive Function: "
<< sqrRootRec << endl; // Display

double sqrRootNonRec = sqrRootNonRecursive(numInput, approximation, tol);
// Square Root using non recursive function is stored in variable "sqrRootNonRec".
cout << endl << "Square Root of " << numInput << " using Non-Recursive Function: "
<< sqrRootNonRec << endl; // Display

return 0;
}

Circular Queue

/*
 * pshrestha_a3.cpp
 *
 *  Created on: Nov 16, 2010
 *      Program Description:
 *      A class is written that implements a "Circular Queue" data structure for storing
 *      and retrieving floating point values. The methods created are: Enqueue(), Dequeue(),
 *      isEmpty(), isFull(), makeEmpty(), goToHead().
 *     A switch statement is used in the main program for the efficiency of its application
 *     to handle the structured data.
 */

#include <iostream>
#include <cctype>
#include <iomanip>

using namespace std;

const int MAX_ELEMENTS = 17; // Declaring maximum number of elements.

struct Float_Node {
// Structure for the node containing a value and the next node.
double Value;
struct Float_Node* Next;
};

class CircularQueue {
private:
Float_Node *rear;
Float_Node *p; // Current
int nodeCounter; // To count the nodes.
public:
CircularQueue();
bool Enqueue(double);
double Dequeue(bool&);
bool isEmpty();
bool isFull();
void makeEmpty();
struct Float_Node *goToHead();
void display();
~CircularQueue();
};

CircularQueue::CircularQueue() {
// Default Constructor
nodeCounter = 0;
rear = NULL;
}

bool CircularQueue::Enqueue(double input) {
// This function will insert the value user enters in to the queue.
p = new struct Float_Node;
p->Value = input;
if(!isFull()) {
// If Queue is not full
if(rear) {
//If rare has value
p->Next = rear->Next;
rear->Next = p;
rear = p;
} else {
// If rare don't have a value already.
rear = p;
rear ->Next = p;
}
++ nodeCounter; // Counting.
return true;
}
return false;
}

double CircularQueue::Dequeue(bool& logicVal) {
// Takes the value out of the stack.
double Value;
if(!isEmpty()) {
if (rear) {
// if rear is true only.
Float_Node *p = rear->Next;
Value = p->Value;
if (p != rear) {
rear->Next = p->Next;
} else {
rear = NULL;
}
delete p;
--nodeCounter; //decreasing the node counter.
logicVal = true; // Setting true for successful dequeue process.
return Value;
}
}
logicVal = false; // Setting false for unsuccessful dequeue process.
return 8;
}

bool CircularQueue::isEmpty() {
// Checks if the queue is Empty or not.
if (rear) {
return false;
}
return true;
}

bool CircularQueue::isFull() {
// Checks if the queue is Full or not.
if (nodeCounter == MAX_ELEMENTS) {
return true;
}
return false;
}

void CircularQueue::makeEmpty() {
// Makes the Queue Empty.
double empty; // holds the variable that would be emptied from the queue.
if (rear) {
while (rear) {
p = rear->Next;
empty = p->Value;
if(p != rear) {
rear->Next = p->Next;
} else {
rear = NULL;
}
delete p;
-- nodeCounter;
cout << endl << "Queue --> Emptied is: " << empty << endl;
}
} else {
cout << endl << "Queue --> Empty!!" << endl;
}
}

struct Float_Node *CircularQueue::goToHead() {
// Positions the Queue to the head of the Queue.
return  rear->Next;
}

void CircularQueue::display() {
// Function to display the Queue for the users.
double input;
if (rear) {
struct Float_Node *p = goToHead();
// Positions the Queue to the top so that we can display the queue.

cout << endl << "Displaying Queues: " << endl;
while (p != rear) {
input = p->Value;
p = p->Next;
cout << input << endl;
}
cout << rear->Value << endl;
} else {
cout << "Queue --> Empty!!" << endl;
}
}

CircularQueue::~CircularQueue() {
// De-allocating the memory space used that could be freed!!
while(rear) {
p = rear->Next;
if (p != rear) {
rear->Next = p->Next;
} else {
rear = NULL;
}
delete p;
}
}

int main (void) {
CircularQueue q1; // Instance of the class CircularQueue.
int option; // Variable to hold the user option from 1 - 6.
float inputValue; // Variable to hold user's input value for queue operation.
bool logicValue;
// Boolean variable to figure out if the Dequeue operation was successful or not.

while(1) {
// Using switch statement which seems to be ideally very efficient to
// handle data structures.
cout << "\n\n--------------" << endl;
cout << "CIRCULAR QUEUE" << endl;
cout << "--------------" << endl;
cout << "[1] Enqueue." << endl;
cout << "[2] Dequeue." << endl;
cout << "[3] Empty Queue." << endl;
cout << "[4] Display Queue." << endl;
cout << "[5] Go to Head of Queue." << endl;
cout << "[6] Done. Quit me out!!" << endl;
cout << "Enter your Choice: ";
cin >> option;

switch(option) {
case 1:
// If users hits 1
cout << "Enter the value to enqueued in the Queue: \n";
// Asking the user for input to be inserted in the Queue.
cin >> inputValue;
// Storing in variable.
logicValue = q1.Enqueue(inputValue);
if (logicValue) {
// If logic value is true.
cout << "Value Enqueued: " << inputValue << endl;
} else {
// If logic value is false.
cout << "Stack Full!! Value not Enqueued!! \n";
}
break;

case 2:
// If users hits 2
double val;
val = q1.Dequeue(logicValue);
if (logicValue) {
// If logic value is true.
cout << "Value Dequeued: " << val << endl;
} else {
// If logic value is false.
cout << "Queue --> Empty!! \n";
}
break;

case 3:
// If users hits 3
q1.makeEmpty(); // Calling function/method.
break;

case 4:
// If users hits 4
q1.display(); //Calling function/method.
break;

case 5:
// If users hits 5
q1.goToHead(); //Calling function/method.
// It may not be used directly but is helpful when displaying the Queue.
break;

case 6:
// If users hits 6
cout << endl << "Closing.......Application!!" << endl << "Thank You!!";
return 0;

default:
// If users hits any other permutations or combinations.
cout << endl <<".....Enter the Option in between 1 & 6!! Retry Again. \n";
}
}

return 0;
}

Thursday, December 2, 2010

Concept of recursive function to take user input of two numbers and performs an addition of those two numbers

/*
 * p4_pshr_Adder.cpp
 *
 *     Created on: Nov 23, 2010
 * Program Description:
 * This program uses the concept of recursive function to take user input of two numbers and
 * performs an addition of those two numbers.
 */

#include <iostream>
#include <cctype>
#include <iomanip>

using namespace std;

class Add {
private:
public:
unsigned int Adder(unsigned int, unsigned int);
};

unsigned int Add::Adder(unsigned int num1,unsigned int num2) {
// This recursive function very smartly deals with the 3 possible cases of the input number
// entered by the user being both equal to zero, one number being equal to zero and other number
// being equal to zero.
if (num1 != 0 && num2 != 0) {
// If both number entered by user becomes zero, this recursive function comes to and end
// and moves to the next line. But, if both the numbers are non-zero, then, it adds "2"
// the times either one of the number is not equal to zero as we decrease the input by "1" each!!
return 2 + Adder(num1 - 1, num2 - 1);
}

else if (num1 == 0 && num2 != 0) {
// If one of the number is zero, it decreases the other number by 1 and adds "1" on to it!!
return 1 + Adder(0, num2 - 1);
}
else if (num2 == 0 && num2 != 0) {
// If the other number is zero, it decreases the next number by 1 and adds "1" on to it!!
return 1 + Adder(num1 - 1, 0);
}
else {
// If both the number entered by user was "0" then it return "0" as the sum.
return 0;
}
}

int main(void) {
Add a1; // Instance of class Add.
unsigned int addentOne; // Variable to store unsigned int.
unsigned int addentTwo; // Variable to store unsigned int.

// User Input
cout << endl << "Enter the first number: ";
cin >> addentOne;
cout << endl << "Enter the second number: ";
cin >> addentTwo;

// Formatting the output using recursive function created in the class.
cout << endl << "ADDITION USING RECURSION";
cout << endl << "------------------------";
cout << endl << "  " << addentOne;
cout << endl << " +" << addentTwo;
cout << endl << " ------";
cout << endl << "  " << a1.Adder(addentOne, addentTwo);
// Calling the recursive function Adder of the instance of class Add (a1).
return 0;
}

C++ class that implements a “stack” data structure for storing floating-point values. Required methods: Push, Pop, isEmpty, and isFull.

/*
 * pshrestha_a2.cpp
 *
 *
 *      Created on: Nov 7, 2010
 *
Write a C++ class that implements a “stack” data structure for storing floating-point values. Required
methods: Push, Pop, isEmpty, and isFull. Feel free to come up with any additional methods you think a
programmer would find useful.

Implement your “stack” object using a singly linked list.

Write an associated “driver” C++ program that demonstrates the use of your “stack” class.
 */

#include <iostream>
#include <cctype>
#include <iomanip>

using namespace std;
const int MAX_ELEMENTS = 10; // Maximum Number of nodes our stack supports.

struct Stack_Node {
// Structure for the node containing a value and the next node.
double Value;
struct Stack_Node* Next;
};

class Stack {
private:
struct Stack_Node* p; // Current
struct Stack_Node* top;
int nodeCounter; // To count the nodes.
public:
Stack();
bool push(double&);
bool isEmpty();
bool isFull();
double pop(bool&);
~Stack();
};

Stack::Stack() {
// Default Constructor
top = NULL;
nodeCounter = 0;
}

bool Stack::push(double& input) {
// Method for push operation.
if(!isFull()) { // operates only when the stack is not full.
p = new struct Stack_Node; // Dynamic Allocation of node.
p->Value = input; // input value is put in to the node p.
p->Next = NULL; // the node is pointed to nothing.
if(top){
p->Next = top;
}
top = p;
++ nodeCounter;
return true;
}
return false;
}

double Stack::pop(bool& logicVal) {
// Performs the pop operation.
double popValue; // variable where we store the value to be popped.
if(!isEmpty()) {
// operates only when the stack is not empty.
popValue = top->Value; //putting the top's value in to popValue variable.
p = top;
top = top->Next; //
--nodeCounter;
delete p; // deleting the node.
logicVal = true;
return popValue; // Returning the topmost node to the function.
} else {
logicVal = false;
return 7;
}
}

bool Stack::isEmpty() {
// Bool method to test if the stack is empty or not.
if(top == NULL) {
return true;
} else {
return false;
}

// Alternative way for the same code above.
// return Top == NULL;
}

bool Stack::isFull() {
// Bool method to test if the stack is full or not.
return nodeCounter == MAX_ELEMENTS;

// Alternative way for the same code above.
/*if(nodeCounter == MAX_ELEMENTS) {
return true;
} else {
return false;
} */
}


Stack::~Stack() {
// Destructor for the De-allocation of the memory.
while(top) {
p = top;
top = top->Next;
delete p;
}
}

int main() {
Stack stackOne; // Instance of the class Stack.
double userInput; // Variable to hold the user Input.
int numTimesPush; // Variable to hold the number of time a user want to perform the push operation

cout << endl << "How many times you want to perform push() Operation? ";
cin >> numTimesPush;
for (int i = 1; i <= numTimesPush; ++i ) {
// For loop for the number of time user want to push the item in to stack.
cout << endl << "Enter the floating point number to push in the stack: ";
cin >> userInput;
//stackOne.push(userInput);
if (stackOne.push(userInput)) {
// if we are able to push user input then,
cout << endl << "Your Input is pushed in to the Stack " << i << " times." << endl;
} else {
// if we are not able to push the user input then,
cout << endl << "The Stack is full." << "It is more than " << MAX_ELEMENTS << " elements." << endl;
}
}

int numTimesPop; // Variable to hold the number of times the user want to perform the pop operation.
bool logicValue; // Boolian variable to hold the logical state of true or false.
double popedValue; // Variable to hold the value that would be popped out of the stack.

cout << endl << "How many times you want to perform pop() Operation? ";
cin >> numTimesPop;

for (int j = 1; j <= numTimesPop; ++j) {
// For loop for the number of times user want to operate pop operation.
popedValue = stackOne.pop(logicValue);
if (logicValue) {
cout << endl << "The value popped out of Stack = " << popedValue;
} else {
cout << endl << "Sorry!! The Stack is Empty.";
}
}
return 0;
}

C++ program that reads a textual data file and builds linked lists using the data therein.

/*
 * pshrestha_1.cpp
 *
 *  Created on: Oct 27, 2010
 *  Write a C++ program that reads a textual data file and builds linked lists using the data therein.
Each line of the file contains a letter (either I or F) following by a corresponding numeric value.
In each line, an integral value is preceded by character I and a floating-point value is preceded
by character F. An "I integer" line may or may not be followed by one or more "F float" lines.

Your program is to process each line of the file and build linked lists. An "integer" linked list
(nodes sorted ascendingly by integer value) will be created using the "I integer" lines. "F float"
lines will begin/continue another singly linked list "off of" the integer node corresponding to
the integer value and node processed immediately before (again, any "I integer" line may or may not
be followed by one or more "F float" lines). Any list of floating-point nodes must be ordered
ascendingly.

After the file is processed and the linked lists are built, traverse your lists and display the
address and value of each node. That is, as you traverse your list of integer values, display the
address and value of each node and, if an integer node has a corresponding list of floating-point
values, traverse that list and display the address and value of each of those nodes. (Of course,
label your output appropriately.)

Create and use your own data file.
 */

#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;
// Named Constant for the input file.
const char INPUT_PATH_FILE[] = "C:\\Users\\Shiva\\workspace\\dataStructure\\pshrestha_1\\progAssignOne.txt";

// Structure for our float node
struct Float_Node {
float Value; // Holds value
struct Float_Node* Next; // Holds the address.
};

// Structure for our integer node
struct Integer_Node {
int Value;
struct Float_Node* Base_Float;
struct Integer_Node* Next;
};

int main(void) {

ifstream InFile;
InFile.open(INPUT_PATH_FILE);

if (InFile) { // If input file opened successfully the the following line of code executes.
char Input_Character; // Holds character.
float Input_Float;
int Input_Integer;
struct Integer_Node* base = NULL; // Making it point to nothing.
struct Integer_Node* p;
struct Integer_Node* q;
struct Integer_Node* r;
struct Integer_Node* Ptr_Last_Int_Node; // Optional
struct Float_Node* pf;
struct Float_Node* qf;
struct Float_Node* rf;
while (InFile >> Input_Character >> Input_Float) {
// Operates until the input file has values in it.
if (Input_Character == 'I' || Input_Character == 'i') {
// Checking for both "I" and "i".
Input_Integer = (int)Input_Float;
p = Ptr_Last_Int_Node = new struct Integer_Node;
p->Value = Input_Integer;
p->Base_Float = NULL;
p->Next = NULL;
if (base) { // If base is true.
q = r = base;
while (q && p->Value > q->Value) {
r = q;
q = q->Next;
}
if (q) {
if (q != base) {
r->Next = p;
p->Next = q;
} else {
base = p;
p->Next = q;
}
} else {
r->Next = p;
}
} else {
base = p;
}
} else if (Input_Character == 'F'|| Input_Character == 'f'){
// Checking for both "F" and "f".
if (! base) {
continue;
}
pf = new struct Float_Node;
pf->Value = Input_Float;
pf->Next = NULL;
// p is pointing at the integer node for this incoming
// floating-point node.
if (Ptr_Last_Int_Node->Base_Float) {
qf = rf = Ptr_Last_Int_Node->Base_Float;
while (qf && pf->Value > qf->Value) {
rf = qf;
qf = qf->Next;
}
if (qf) {
if (qf != Ptr_Last_Int_Node->Base_Float) {
rf->Next = pf;
pf->Next = qf;
} else {
Ptr_Last_Int_Node->Base_Float = pf;
pf->Next = qf;
}
} else {
rf->Next = pf;
}
} else {
Ptr_Last_Int_Node->Base_Float = pf;
}
}
}
InFile.close (); // Closing the opened file.
// Display linked lists (addresses and values of nodes).
cout << "ADDRESS" << setw (8) << "VALUE" << endl;
cout << "-------" << setw (8) << "-----" << endl;
if (base) {
q = base;
while (q) {
cout << (unsigned)q << setw (6) << q->Value << endl;
// Displaying address of the memory and the value residing on it
qf = q->Base_Float;
while (qf) {
cout << (unsigned)qf << setw (6) << qf->Value << endl;
qf = qf->Next;
}
q = q->Next;
}
} else {
cout << endl << "\a\aNo Linked Lists Created!";
}
} else {
cout << endl << "\aCannot Open Input File";
}
return 0;
}