CS240 – C++
Data Structures
Instructor: Ronald Sarner, Ph.D.
Menu:
- Matrix Search
- Population Growth Simulation
- Noun Counter
- Prime Factorization
- Palindrome
- Bingo
- Hash Table
Matrix Search:
//CS240 GHP1
//Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 42, Problem 2
//This program searches a matrix to see if the integer
//inputed by the user is contained inside the matrix.
//Written by: Ronny L. Bull
//Date: Jan 26, 2010
//Language: C++ <target g++>
//Precondition: User must input an intenger
//Postcondition: "Item Found" , or "Item Not Found" is printed to the screen.
#include <iostream>
using namespace std;
const int NUM = 3;
int main(void)
{
//Variables
int item;
int mat[NUM][NUM];
bool found;
//Loop that requests the user to input integers into the 2D array.
//for (int inrow = 0; inrow < n; inrow++)
// for (int incol = 0; incol < n; incol++)
// {
// cout<<"Please input the integer for row "<<inrow<<" column "<<incol<<" in the matrix: ";
// cin>>mat[inrow][incol];
// cout <<"Row "<<inrow<<" Column "<<incol<<" is: "<<mat[inrow][incol]<<endl;
// }
//Assign static values to the 2D array
mat[0][0] = 45;
mat[0][1] = 77;
mat[0][2] = 93;
mat[1][0] = 78;
mat[1][1] = 79;
mat[1][2] = 85;
mat[2][0] = 72;
mat[2][1] = 96;
mat[2][2] = 77;
//Request an integer to search for from the user
cout << "Please enter an integer to search for: ";
cin>>item;
//Initialize found to false
found = false;
//Search the 2D array for the integer
//Code adapted from:
//Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 42, Problem 2
//Adapted by: Ronny L. Bull
//The problem with the original code is that it did not stop when it found the integer in the matrix
//It constantly returned false on all entries except for the value matched in mat[2][2] because it would
//match all the results in the array and always end with the last value, in effect giving that values
//value for the search.
for (int row = 0; row < NUM; row++)
{
for (int col = 0; col < NUM; col++)
{
if(!(found))
{
if (mat[row][col] == item)
{
found = true;
cout<<"item found at location: "<<row<<" "<<col<<endl;
}
else
{
found = false;
}
}
//DEBUG: Print the value of found
//cout<<"found is "<<found<<endl;
}
}
if(!(found))
cout<<"item not found"<<endl;
return (0);
}
Population Growth Simulation:
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP2
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 138, Problem 6
This program projects the population of 3 regions after 10, 20, 30, 40, and 50 years
The regions are Urban, Suburban, and Exurban
Written by: Ronny L. Bull
Date: Feb 6, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Precondition: Initial Populations are Urban (2.1 Mil), Suburban (1.4 Mil), Exurban (0.9 Mil).
Postcondition: Population projections are printed to the screen for 10, 20, 30, 40, and 50 years for each region.
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Global
INIT_URB; Initial Urban Population
INIT_SUB; Initial Suburban Population
INIT_EX; Initial Exurban Population
PER; Percentage conversion multiplier
Indicies; enum used to store array row and column values
population; 2D array to hold growth rate values
----------------------------------------------------------------------------------------------------------------*/
//Define intial population sizes
const int INIT_URB = 2100000;
const int INIT_SUB = 1400000;
const int INIT_EX = 900000;
const float PER = 0.01;
//Create enums for rows and cols
enum Indices {Urban, Suburban, Exurban, NUM_IND};
//Create the 2d array
float population[NUM_IND][NUM_IND];
//Function Prototypes
int urb_urb(int);
int urb_sub(int);
int urb_ex(int);
int sub_sub(int);
int sub_urb(int);
int sub_ex(int);
int ex_ex(int);
int ex_urb(int);
int ex_sub(int);
//Main
int main(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Main
i,j; counter variables
URBprevious; holds pervious year urban population value
URBnew; holds new year urban population value
SUBprevious; holds previous year suburban population value
SUBnew; holds new year suburban population value
EXprevious; holds previous year exurban population value
EXnew; holds new year exurban population value
urburb; holds internal growth value for urban to urban
suburb; holds migration data from suburban to urban
exurb; holds migration data from exurban to urban
subsub; holds internal growth from suburban to suburban
urbsub; holds migration data from urban to suburban
exsub; holds migration data from exurban to suburban
exex; holds internal growth from exurban to exurban
urbex; holds migration data from urban to exurban
subex; holds migratoin data from suburban to exurban
year; holds the current year count
----------------------------------------------------------------------------------------------------------------*/
//Variables
int i,j;
int URBprevious = INIT_URB;
int URBnew;
int SUBprevious = INIT_SUB;
int SUBnew;
int EXprevious = INIT_EX;
int EXnew;
int urburb;
int suburb;
int exurb;
int subsub;
int urbsub;
int exsub;
int exex;
int urbex;
int subex;
int year;
//Store the annual population growth rates in the array
population[Urban][Urban] = 1.1;
population[Urban][Suburban] = 0.3;
population[Urban][Exurban] = 0.7;
population[Suburban][Urban] = 0.1;
population[Suburban][Suburban] = 1.2;
population[Suburban][Exurban] = 0.3;
population[Exurban][Urban] = 0.2;
population[Exurban][Suburban] = 0.6;
population[Exurban][Exurban] = 1.3;
//Output the population predictions to the screen
for (j=1;j<=5;j++)
for (i=1;i<=10;i++)
{
//Urban
urburb = urb_urb(URBprevious);
suburb = sub_urb(SUBprevious);
exurb = ex_urb(EXprevious);
URBnew = URBprevious + urburb + suburb + exurb;
//Suburban
subsub = sub_sub(SUBprevious);
urbsub = urb_sub(URBprevious);
exsub = ex_sub(EXprevious);
SUBnew = SUBprevious + subsub + urbsub + exsub;
//Exurban
exex = ex_ex(EXprevious);
urbex = urb_ex(URBprevious);
subex = sub_ex(SUBprevious);
EXnew = EXprevious + exex + urbex + subex;
//Set new values to previous values for next run
URBprevious = URBnew;
SUBprevious = SUBnew;
EXprevious = EXnew;
//Year count
year = i*j;
//DEBUG
//if (year==1)
// cout<<"Urban Pop is "<<URBnew<<endl<<endl;
//Output Population for 10, 20, 30, 40, and 50 years
if (i==10)
{
cout<<"*****YEAR "<<year<<"*****"<<endl;
cout<<"Urban Population: "<<URBnew<<endl;
cout<<"Suburban Population "<<SUBnew<<endl;
cout<<"Exurban Population "<<EXnew<<endl<<endl;
}
}
return (0);
}
//Functions
/*----------------------------------------------------------------------------------------------------------------
Urban to Urban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in previous urban population value
Postcondition: Returns internal urban population increase for the new year
----------------------------------------------------------------------------------------------------------------*/
int urb_urb(int oldurbpop)
{
return (population[Urban][Urban] * PER) * oldurbpop;
}
/*----------------------------------------------------------------------------------------------------------------
Suburban to Suburban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the previous suburban population value
Postcondition: Returns internal suburban population increase for the new year
----------------------------------------------------------------------------------------------------------------*/
int sub_sub(int oldsubpop)
{
return (population[Suburban][Suburban] * PER) * oldsubpop;
}
/*----------------------------------------------------------------------------------------------------------------
Exurban to Exurban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the previous exurban population value
Postcondition: Returns internal exurban population increase for the new year
----------------------------------------------------------------------------------------------------------------*/
int ex_ex(int oldexpop)
{
return (population[Exurban][Exurban] * PER) * oldexpop;
}
/*----------------------------------------------------------------------------------------------------------------
Suburban to Urban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the previous suburban population value
Postcondition: Returns the amount of people that migrated from suburban to urban
----------------------------------------------------------------------------------------------------------------*/
int sub_urb(int oldsubpop)
{
return (population[Suburban][Urban] * PER) * oldsubpop;
}
/*----------------------------------------------------------------------------------------------------------------
Exurban to Urban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the previous exurban population value
Postcondition: Returns the amount of people that migrated from exurban to urban
----------------------------------------------------------------------------------------------------------------*/
int ex_urb(int oldexpop)
{
return (population[Exurban][Urban] * PER) * oldexpop;
}
/*----------------------------------------------------------------------------------------------------------------
Suburban to Exurban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the previous suburban population value
Postcondition: Returns the amount of people that migrated from suburban to exurban
----------------------------------------------------------------------------------------------------------------*/
int sub_ex(int oldsubpop)
{
return (population[Suburban][Exurban] * PER) * oldsubpop;
}
/*----------------------------------------------------------------------------------------------------------------
Exurban to Suburban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the prevous exurban population value
Postcondition: Returns the amount of people that migrated from exurban to suburban
----------------------------------------------------------------------------------------------------------------*/
int ex_sub(int oldexpop)
{
return (population[Exurban][Suburban] * PER) * oldexpop;
}
/*----------------------------------------------------------------------------------------------------------------
Urban to Exurban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the previous urban population value
Postcondition: Returns the amount of people that migrated from urban to exurban
----------------------------------------------------------------------------------------------------------------*/
int urb_ex(int oldurbpop)
{
return (population[Urban][Exurban] * PER) * oldurbpop;
}
/*----------------------------------------------------------------------------------------------------------------
Urban to Suburban
Written by: Ronny L. Bull
Date: 02-10-2010
Precondition: Takes in the previous urban population value
Postcondition: Returns the amount of people that migrated from urban to suburban
----------------------------------------------------------------------------------------------------------------*/
int urb_sub(int oldurbpop)
{
return (population[Urban][Suburban] * PER) * oldurbpop;
}
Noun Counter:
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP3
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 249, Problem 2
This program counts the nouns in a text file, and displays the count to the screen
Written by: Ronny L. Bull
Date: Feb 21, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Precondition: Open Text file
Postcondition: Display vowel count
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
#include <string> //String processing library
#include <fstream> //File processing library
#include <cassert> //Assert
using namespace std;
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Global
inFile; input file stream
----------------------------------------------------------------------------------------------------------------*/
//Global Variables
ifstream inFile;
//Function Prototypes
void readFile(void);
void findVowels(void);
//Main
int main(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Main
----------------------------------------------------------------------------------------------------------------*/
//Main Variables
//Call to readFile function
readFile();
return(0);
}
//Functions
/*----------------------------------------------------------------------------------------------------------------
readFile
Written by: Ronny L. Bull
Date: 02-21-2010
Precondition: User inputs name of file
Postcondition: Open the file, proceed to findVowels, then close the file
----------------------------------------------------------------------------------------------------------------*/
void readFile(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for readFile
filename; name of input file
correct; user verification (y or n)
yes; comparison string for user verification
----------------------------------------------------------------------------------------------------------------*/
//readFile Variables
string filename;
string correct = "";
string yes = "y";
//Prompt user for filename and confirm selection
//Code adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 208
//Adapted by: Ronny L. Bull
cout<<"Please input the file name: "<<endl;
getline(cin, filename);
cout<<"You wish to process the file "<<filename<<", is this correct?(y/n)"<<endl;
cin>>correct;
if(correct == yes)
{
cout<<"Processing "<<filename<<"!"<<endl;
//Open the file stream and verify that it is open
//Code adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 208
//Adapted by: Ronny L. Bull
inFile.open(filename.data(), ios::in);
assert(inFile.is_open());
//Proceed to findVowels function
findVowels();
//Close the file
inFile.close();
}
else
{
cout<<"Exiting Program"<<endl;
}
return;
}
/*----------------------------------------------------------------------------------------------------------------
findVowels
Written by: Ronny L. Bull
Date: 02-22-2010
Precondition: Parses file and looks for vowels
Postcondition: Increase counter when a vowel is found, display vowel count
----------------------------------------------------------------------------------------------------------------*/
void findVowels(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for findVowels
cnt; vowel count
j,k; loop counters
vowels; array that holds known vowels
line; current line contents in the file
len; string length for current line
letter; current letter in the string
a,e,i,o,u; vowel counters
----------------------------------------------------------------------------------------------------------------*/
//findVowels Variables
int cnt = 0;
int j,k,a,e,i,o,u;
char vowels[] = {'a','e','i','o','u','\0'};
string line;
int len = 0;
char letter;
//Initialize vowel counters to 0
a = 0;
e = 0;
i = 0;
o = 0;
u = 0;
//Search for vowels
cout<<"Searching for vowels..."<<endl;
//String Functions adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Ch5
//Adapted by: Ronny L. Bull
while (! inFile.eof())
{
//Get the current line from the file and store it in line
getline (inFile,line);
//Get word count for the current line
len = line.length();
//Debug: print out the line and the string count
//cout<<line<<endl;
//cout<<len<<endl;
//Count the vowels
for(k=0;k<=len;k++)
{
//Change all letters to lower case in the current line
letter = (tolower(line[k]));
//Debug: Print letters
//cout<<letter;
//Compare current letter with the vowels in the vowels array
for(j=0;j<=4;j++)
{
if(letter == vowels[j])
{
cnt++;
//Count individual vowels
//Note: I could have just done it all this way then added the sum, but I wanted
//to try it both ways, once with the array and once with the switch.
switch(letter)
{
case 'a':
a++;
break;
case 'e':
e++;
break;
case 'i':
i++;
break;
case 'o':
o++;
break;
case 'u':
u++;
break;
}
}
}
}
}
//Print out vowel count
cout<<"There are "<<cnt<<" vowels in the the file."<<endl;
cout<<"The file has "<<a<<" a's, "<<e<<" e's, "<<i<<" i's, "<<o<<" o's, and "<<u<<" u's."<<endl;
return;
}
Prime Factorization:
ghp4.cpp
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP4
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 387, Problem 4
ghp4.cpp: This program determins the prime factorization of a given integer, and displays the results in descending order.
Written by: Ronny L. Bull
Date: Feb 27, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Precondition: User input of an integer
Postcondition: Display prime factorization in descending order
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include "stack.h" //Nyhoff's Stack class
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Global
----------------------------------------------------------------------------------------------------------------*/
//Global Variables
//Function Prototypes
void inputNumber(void);
void findPrimes(int);
//Main
int main(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Main
----------------------------------------------------------------------------------------------------------------*/
//Main Variables
//Call to inputNumber function
inputNumber();
return(0);
}
//Functions
/*----------------------------------------------------------------------------------------------------------------
inputNumber
Written by: Ronny L. Bull
Date: 02-26-2010
Precondition: Ask user for a number to process
Postcondition: Take in the number and pass it to the findPrimes function
----------------------------------------------------------------------------------------------------------------*/
void inputNumber(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for inputNumber
number; the integer inputted by the user
----------------------------------------------------------------------------------------------------------------*/
//inputNumber Variables
int number;
//Ask the user for a number
cout<<"Please input an integer greater than 1 that you would like to find the prime factorization of: ";
cin>>number;
cout<<"The integer you entered was "<<number<<endl;
if(number>1)
{
//Call to findPrimes function
findPrimes(number);
}
else
{
cout<<"The number you entered was not greater than 1"<<endl;
inputNumber();
}
return;
}
/*----------------------------------------------------------------------------------------------------------------
findPrimes
Written by: Ronny L. Bull
Date: 02-26-2010
Precondition: Take in number from inputNumber function
Postcondition: Display prime factorizationi in descending order using a stack
Adaptation Note: All stack functions adapted from Nyhoff ch7
----------------------------------------------------------------------------------------------------------------*/
void findPrimes(int n)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for findPrimes
d; factor, loop counter
factors; stack to hold the factors
----------------------------------------------------------------------------------------------------------------*/
//findPrimes Variables
int d;
Stack factors;
//Print the prime factorization results to the screen
cout<<"Processing "<<n<<"..."<<endl;
cout<<"The prime factorization of "<<n<<" results in: "<<endl;
for(d=2;d<=n;d++)
{
while(n % d == 0)
{
//Add the value stored in d to the stack
factors.push(d);
//Replace n with the quotient of n/d
n = n/d;
}
}
//Check to see if the stack is not empty
while(!(factors.empty()))
{
//Print the value from the top of the stack with an * after it
cout<<factors.top()<<" * ";
//Remove the first value from the stack
factors.pop();
}
cout<<endl;
return;
}
stack.cpp
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP4
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 387, Problem 4
stack.cpp: This file implements Stack member functions.
Code adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Ch7
Adapted by: Ronny L. Bull
//Date: March 4, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include "stack.h" //Nyhoff's Stack class
//Definition of Stack constructor
Stack::Stack()
: myTop(-1)
{}
//Definition of empty()
bool Stack::empty() const
{
return (myTop == -1);
}
//Definition of push()
void Stack::push(const StackElement & value)
{
if (myTop < STACK_CAPACITY - 1) //Preserve stack invariant
{
++myTop;
myArray[myTop] = value;
}
else
{
cerr << " *** Stack full -- can't add new value ***\n"
"Must increase value of STACK_CAPACITY in stack.h\n";
//compile error on Gentoo Linux if exit(1); is uncommented
//exit(1);
}
}
//Definition of display()
void Stack::display(ostream & out) const
{
for(int i = myTop; i >= 0; i--)
out << myArray[i] << endl;
}
//Definition of top()
StackElement Stack::top() const
{
if(!empty())
return (myArray[myTop]);
else
{
cerr << "*** Stack is empty -- returning garbage value ***\n";
StackElement garbage;
return garbage;
}
}
//Definition of pop()
void Stack::pop()
{
if(!empty())
myTop--;
else
cerr << "*** Stack is empty -- can't remove a value ***\n";
}
Palindrome:
ghp5.cpp
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP5
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 443, Problem 14
ghp5.cpp: This program determins if a string is a palindrome demonstrating the use of stacks and queues.
Written by: Ronny L. Bull
Date: Feb 27, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Precondition: User input of a string
Postcondition: Display if the string is a palindrome or not
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include <string> //String Library
#include "stack.h" //Nyhoff's Stack class
#include "queue.h" //Nyhoff's Queue class
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Global
word; the string inputted by the user
----------------------------------------------------------------------------------------------------------------*/
//Global Variables
string word;
//Function Prototypes
void inputString(void);
void findPal(void);
//Main
int main(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Main
----------------------------------------------------------------------------------------------------------------*/
//Main Variables
//Call to inputString function
inputString();
return(0);
}
//Functions
/*----------------------------------------------------------------------------------------------------------------
inputString
Written by: Ronny L. Bull
Date: 03-12-2010
Precondition: Ask user for a string to process
Postcondition: Take in the string and pass it to the findPal function
----------------------------------------------------------------------------------------------------------------*/
void inputString(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for inputString
----------------------------------------------------------------------------------------------------------------*/
//inputString Variables
//Ask the user for a string
cout<<"This program tests a string to see if it is a palindrome."<<endl;
cout<<"Please input the string you would like to test: ";
getline(cin, word);
cout<<"The string you entered was: *** "<<word<<" ***"<<endl;
findPal();
return;
}
/*----------------------------------------------------------------------------------------------------------------
findPal
Written by: Ronny L. Bull
Date: 03-12-2010
Precondition: Take in the string held in word
Postcondition: Display if it is a palindrome or not
Adaptation Note: All stack functions adapted from Nyhoff ch7
All queue functions adapted from Nyhoff ch8
----------------------------------------------------------------------------------------------------------------*/
void findPal(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for findPal
i; loop counter
j; holds string size
p; match counter
sword; stack to hold the string
qword; queue to hold the string
palindrome; bool value to store if the string was a palindrome or not
sword; stack of characters
qword; queue of characters
----------------------------------------------------------------------------------------------------------------*/
//findPal Variables
int i;
int p = 0;
int j = word.size();
char c;
bool palindrome = false;
Stack sword;
Queue qword;
//Test the string to see if it is a palindrome
cout<<"Processing: "<<"*** "<<word<<" *** ..."<<endl;
//Debug: string count
//cout <<"word is "<<j<<" characters long"<<endl;
//Add the string to the stack and queue
for(i=0;i<j;i++)
{
//Store the current character in c
c = word[i];
//Debug
//cout<<c;
//Add the character to the stack and queue
sword.push(c);
qword.enqueue(c);
}
//Check to see if the stack and queue are not empty
while( (!(sword.empty())) && (!(qword.empty())) )
{
//Compare the strings stored in the stack and queue
for(i=0;i<j;i++)
{
if( sword.top() == qword.front() )
{
//Debug: Print out values
//cout<<sword.top()<<endl;
//cout<<qword.front()<<endl;
p++;
}
//Remove the first value from the stack and queue
sword.pop();
qword.dequeue();
}
}
if(p == j)
{
palindrome = true;
cout<<"The string *** "<<word<<" *** is a palindrome"<<endl;
}
else
{
palindrome = false;
cout<<"The string *** "<<word<<" *** is not a palindrome"<<endl;
}
return;
}
queue.cpp
/*-----------------------------------------------------------------------
CS240 GHP5
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 443, Problem 14
Code adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Ch8
Adapted by: Ronny L. Bull
Date: March 12, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
queue.cpp: This file implements Queue member functions.
-------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include "queue.h"
//--- Definition of Queue constructor
Queue::Queue()
: myFront(0), myBack(0)
{}
//--- Definition of empty()
bool Queue::empty() const
{
return (myFront == myBack);
}
//--- Definition of enqueue()
void Queue::enqueue(const QueueElement & value)
{
int newBack = (myBack + 1) % QUEUE_CAPACITY;
if (newBack != myFront) // queue isn't full
{
myArray[myBack] = value;
myBack = newBack;
}
else
{
cerr << "*** Queue full -- can't add new value ***\n"
"Must increase value of QUEUE_CAPACITY in Queue.h\n";
//compile error on Gentoo Linux if exit(1); is uncommented
//exit(1);
}
}
//--- Definition of display()
void Queue::display(ostream & out) const
{
for (int i = myFront; i != myBack; i = (i + 1)%QUEUE_CAPACITY)
out << myArray[i] << " ";
cout << endl;
}
//--- Definition of front()
QueueElement Queue::front() const
{
if ( !empty() )
return (myArray[myFront]);
else
{
cerr << "*** Queue is empty -- returning garbage value ***\n";
QueueElement garbage;
return garbage;
}
}
//--- Definition of dequeue()
void Queue::dequeue()
{
if ( !empty() )
myFront = (myFront + 1) % QUEUE_CAPACITY;
else
{
cerr << "*** Queue is empty -- "
"can't remove a value ***\n";
//compile error on Gentoo Linux if exit(1); is uncommented
//exit(1);
}
}
stack.cpp
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP5
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 443, Problem 14
stack.cpp: This file implements Stack member functions.
Code adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Ch7
Adapted by: Ronny L. Bull
//Date: March 4, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include "stack.h" //Nyhoff's Stack class
//Definition of Stack constructor
Stack::Stack()
: myTop(-1)
{}
//Definition of empty()
bool Stack::empty() const
{
return (myTop == -1);
}
//Definition of push()
void Stack::push(const StackElement & value)
{
if (myTop < STACK_CAPACITY - 1) //Preserve stack invariant
{
++myTop;
myArray[myTop] = value;
}
else
{
cerr << " *** Stack full -- can't add new value ***\n"
"Must increase value of STACK_CAPACITY in stack.h\n";
//compile error on Gentoo Linux if exit(1); is uncommented
//exit(1);
}
}
//Definition of display()
void Stack::display(ostream & out) const
{
for(int i = myTop; i >= 0; i--)
out << myArray[i] << endl;
}
//Definition of top()
StackElement Stack::top() const
{
if(!empty())
return (myArray[myTop]);
else
{
cerr << "*** Stack is empty -- returning garbage value ***\n";
StackElement garbage;
return garbage;
}
}
//Definition of pop()
void Stack::pop()
{
if(!empty())
myTop--;
else
cerr << "*** Stack is empty -- can't remove a value ***\n";
}
queue.h
/*---------------------------------------------------------------------
CS240 GHP5
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 443, Problem 14
Code adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Ch8
Adapted by: Ronny L. Bull
Date: March 12, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Queue.h contains the declaration of class Queue.
Basic operations:
Constructor: Constructs an empty queue
empty: Checks if a queue is empty
enqueue: Modifies a queue by adding a value at the back
front: Accesses the front queue value; leaves queue unchanged
dequeue: Modifies a queue by removing the value at the front
display: Displays the queue elements from front to back
Class Invariant:
1. The queue elements (if any) are stored in consecutive positions
in myArray, beginning at position myFront.
2. 0 <= myFront, myBack < QUEUE_CAPACITY
3. Queue's size < QUEUE_CAPACITY
-----------------------------------------------------------------------*/
#include <iostream>
#ifndef QUEUE
#define QUEUE
const int QUEUE_CAPACITY = 128;
typedef char QueueElement; //Modified from int to char on 3-12-2010 by Ronny L. Bull
class Queue
{
public:
/***** Function Members *****/
/***** Constructor *****/
Queue();
/*-----------------------------------------------------------------------
Construct a Queue object.
Precondition: None.
Postcondition: An empty Queue object has been constructed; myFront
and myBack are initialized to -1 and myArray is an array with
QUEUE_CAPACITY elements of type QueueElement.
----------------------------------------------------------------------*/
bool empty() const;
/*-----------------------------------------------------------------------
Check if queue is empty.
Precondition: None.
Postcondition: True is returned if the queue is empty and false is
returned otherwise.
----------------------------------------------------------------------*/
void enqueue(const QueueElement & value);
/*-----------------------------------------------------------------------
Add a value to a queue.
Precondition: value is to be added to this queue.
Postcondition: value is added to back of queue provided there is space;
otherwise, a queue-full message is displayed and execution is
terminated.
-----------------------------------------------------------------------*/
void display(ostream & out) const;
/*-----------------------------------------------------------------------
Output the values stored in the queue.
Precondition: ostream out is open.
Postcondition: Queue's contents, from front to back, have been output
to out.
-----------------------------------------------------------------------*/
QueueElement front() const;
/*-----------------------------------------------------------------------
Retrieve value at front of queue (if any).
Precondition: Queue is nonempty.
Postcondition: Value at front of queue is returned, unless queue is
empty; in that case, an error message is displayed and a "garbage
value" is returned.
----------------------------------------------------------------------*/
void dequeue();
/*-----------------------------------------------------------------------
Remove value at front of queue (if any).
Precondition: Queue is nonempty.
Postcondition: Value at front of queue has been removed, unless queue
is empty; in that case, an error message is displayed and
execution is terminated.
----------------------------------------------------------------------*/
private:
/***** Data Members *****/
int myFront,
myBack;
QueueElement myArray[QUEUE_CAPACITY];
}; // end of class declaration
#endif
stack.h
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP5
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 443, Problem 14
stack.h: header file - defines a stack data type
Code adapted from: Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Ch7
Adapted by: Ronny L. Bull
//Date: March 4, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Basic operations:
constructor: Constructs an empty stack
empty: Checks if a stack is empty
push: Modifies a stack by adding a value at the top
top: Retrieves the top stack value; leaves stack unchanged
pop: Modifies stack by removing the value at the top
display: Displays all the stack elements
Class Invariant:
1. The stack elements (if any) are stored in positions 0,1,..., myTop of myArray.
2. -1 <= myTop < STACK_CAPACITY
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
#ifndef STACK
#define STACK
const int STACK_CAPACITY = 128;
typedef char StackElement; //Modified from int to char 3-12-2010 By: Ronny L. Bull
//Stack Class
class Stack
{
public:
//Function Members
//Constructor
Stack();
/*------------------------------------------------------------------------------------------------------
Construct a stack object.
Precondition: None.
Postcondition: An empty stack object is created, myTop is initialized to -1 and myArray is an
array with STACK_CAPACITY elements of type StackElement.
-------------------------------------------------------------------------------------------------------*/
bool empty() const;
/*------------------------------------------------------------------------------------------------------
Check if stack is empty
Precondition: None.
Postcondition: Returns true if stack is empty and false otherwise.
-------------------------------------------------------------------------------------------------------*/
void push(const StackElement & value);
/*------------------------------------------------------------------------------------------------------
Add a value to the stack
Precondition: Value is to be added to this stack
Postcondition: Value is added at top of stak provided there is space; otherwise, a stack-full
message is displayed and execution is terminated.
-------------------------------------------------------------------------------------------------------*/
void display(ostream & out) const;
/*------------------------------------------------------------------------------------------------------
Display values stored in the stack.
Precondition: ostream out is open.
Postcondition: Stack's contents, from top down, have been output to out.
-------------------------------------------------------------------------------------------------------*/
StackElement top() const;
/*------------------------------------------------------------------------------------------------------
Retrieve value at top of stack (if any).
Precondition: Stack is not empty
Postcondition: Value at top of stack is returned, unless the stack is empty;
in that case, an error message is displayed and a "garbage value" is returned.
-------------------------------------------------------------------------------------------------------*/
void pop();
/*------------------------------------------------------------------------------------------------------
Remove value at top of stack (if any).
Precondition: Stack is not empty.
Postcondition: Value at top of stack has been removed, unless the stack is empty;
in that case an error message is displayed and execution allowed to proceed.
-------------------------------------------------------------------------------------------------------*/
private:
//Data Members
StackElement myArray[STACK_CAPACITY];
int myTop;
}; // End of Stack class declaration
#endif
Bingo:
/*----------------------------------------------------------------------------------------------------------------
CS240 GHP6
Nyhoff (ADT's, Data Structures, and Problem Solving with C++ - Second Edition) Pg. 581, Problem 19
ghp6.cpp: This program uses recursion to display the lyrics to the song BINGO.
Written by: Ronny L. Bull
Date: Mar 29, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Precondition: No Inputs
Postcondition: Display the lyrics to BINGO
----------------------------------------------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include <string> //String Library
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Global
bingo; string array holding the letters or claps
clap; string that holds the word clap
----------------------------------------------------------------------------------------------------------------*/
//Global Variables
string bingo[6] = {"B","I","N","G","O","\0"};
string clap = "clap";
//Function Prototypes
int recursion(int);
//Main
int main(void)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for Main
----------------------------------------------------------------------------------------------------------------*/
//Main Variables
//Call to recursion function
recursion(0);
return(0);
}
//Functions
/*----------------------------------------------------------------------------------------------------------------
recursion
Written by: Ronny L. Bull
Date: 03-29-2010
Precondition: No Input
Postcondition: Display lyrics to the song BINGO
----------------------------------------------------------------------------------------------------------------*/
int recursion(int i)
{
/*----------------------------------------------------------------------------------------------------------------
Dictionary of Variables for recursion
i = verse count;
j,k = loop counters;
----------------------------------------------------------------------------------------------------------------*/
//recursion Variables
int j;
int k;
//Print song lyrics to the screen
cout<<"There was a farmer had a dog, "<<endl;
cout<<"And Bingo was his name-o. "<<endl;
for (k=0;k<3;k++)
{
for (j=0;j<5;j++)
{
cout<<bingo[j]<<" ";
}
cout<<"!"<<endl;
}
cout<<"And Bingo was his name-o!"<<endl;
//Set bingo[i] to "clap"
bingo[i] = clap;
if (i==5)
{
return(0);
}
else
{
i++;
//call to recursion function
return(recursion(i));
}
}
Hash Table:
ghp7.cpp
/*---------------------------------------------------------------------------------------
CS240 GHP7
ghp7.cpp:
Driver Program
Written by: Ronny L. Bull
Date: Apr 24, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
Precondition: None
Postcondition: Query the user for 15 strings,
Enter the strings into the hash table,
Print out the entire hash table,
Allow user to search hash table and output the results of the search.
---------------------------------------------------------------------------------------*/
#include "hash.h" //My hash class
using namespace std;
//Main
int main(void)
{
Hash hash = Hash();
//Call to Hash::prompt
hash.prompt();
//Call to Hash::display
hash.display();
//Call to Hash::search
hash.search();
return(0);
}
hash.cpp
/*--------------------------------------------------------------------------------------
CS240 GHP7
hash.cpp:
hash.cpp implements the functions declared in hash.h.
Written by: Ronny L. Bull
Date: Apr 22, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
--------------------------------------------------------------------------------------*/
#include "hash.h"
using namespace std;
//Constructor
Hash::Hash()
{
}
//Prompt
void Hash::prompt(void)
{
/*---------------------------------------------------------------------------------------
Dictionary of Variables for prompt
i; loop counter
---------------------------------------------------------------------------------------*/
//Prompt user for input
for(int i=0;i<15;i++)
{
cout<<"Please input string "<<i+1<<" of 15 to store into the hash table: ";
cin>>word;
cout<<"your word was ("<<word<<")"<<endl;
cout<<endl;
//Call to Hash::process, store hash value in hvalue
int hvalue = process();
//Call to Hash::insert
insert(hvalue);
}
}
//Process
int Hash::process(void)
{
/*--------------------------------------------------------------------------------------
Dictionary of Variables for process
f; char to hold first character of the word
l; char to hold last character of the word
h; hash value
size; holds current word size
---------------------------------------------------------------------------------------*/
//get the size of the string
int size = word.size();
//copy the first letter of the word to f
char f = word[0];
//copy the last letter of the word to l
char l = word[size-1];
//hash function
//Adapted from Dr. Ron Sarner - Angel homework problem posting.
//Adapted by: Ronny L. Bull
//Date: 4-21-2010
int h = (int(f) + int(l))%23;
//Debug
//cout<<"h in process is "<<h<<endl;
return(h);
}
//Insert
void Hash::insert(int h)
{
/*---------------------------------------------------------------------------------------
Dictionary of Variables for insert
h; value returned from process
i; loop counter
---------------------------------------------------------------------------------------*/
cout<<"Inserting ("<<word<<") into the hash table..."<<endl;
cout<<endl;
if(hashArray[h] == "")
{
//use the hash value as the position in the array
hashArray[h]=word;
}
else
{
int i=1;
//Check to see if the spot is taken, if so increase the counter
while(hashArray[h+i] != "")
{
i++;
//Deal with collision on the end of the array
if((h+i) >= 22)
{
h=0;
}
}
//Check to see if the spot is empty, if so insert
if(hashArray[h+i] == "")
{
//insert the word into the next available space
hashArray[h+i]=word;
}
}
return;
}
//Display
void Hash::display(void)
{
/*---------------------------------------------------------------------------------------
Dictionary of Variables for display
i; loop counter
---------------------------------------------------------------------------------------*/
//loop through the positions in the array and print out thier contents
cout<<endl;
cout<<"Printing out the contents of the hash table..."<<endl;
for(int i=0;i<23;i++)
{
cout<<"Position "<<i<<" contains ("<<hashArray[i]<<")"<<endl;
}
return;
}
//Search
void Hash::search(void)
{
/*---------------------------------------------------------------------------------------
Dictionary of Variables for search
i; loop counter
h; hash value from process
---------------------------------------------------------------------------------------*/
cout<<endl;
cout<<"What string would you like to search the hash table for? (Type stop to exit)";
cin>>word;
if(word == "stop")
{
return;
}
else
{
int h = process();
//Debug
//cout<<"h in search is "<<h<<endl;
cout<<"You are searching for ("<<word<<")..."<<endl;
if(word == hashArray[h])
{
cout<<"("<<word<<") was found in position "<<h<<"."<<endl;
}
else if(word != hashArray[h] && hashArray[h] != "")
{
if(h <= 22)
{
h=0;
}
for(int i=h;i<23;i++)
{
if(word == hashArray[i])
{
cout<<"("<<word<<") was found in position "<<i<<"."<<endl;
}
}
}
else
{
cout<<"The string you entered was not found in the table"<<endl;
}
search();
}
return;
}
hash.h
/*--------------------------------------------------------------------------------------
CS240 GHP7
hash.h:
hash.h contains the declaration of the hash class.
Written by: Ronny L. Bull
Date: Apr 23, 2010
Language: C++ <target g++>
Development Operating System: Gentoo Linux
--------------------------------------------------------------------------------------*/
#ifndef HASH
#define HASH
#include <iostream>
#include <string>
using namespace std;
//Hash Class
class Hash
{
public:
string hashArray[23];
string word;
//Constructor
Hash();
void prompt();
/*---------------------------------------------------------------------
prompt
Precondition: none
Postcondition: prompts user for 15 strings
----------------------------------------------------------------------*/
int process();
/*---------------------------------------------------------------------
process
Precondition: takes in the string entered by the user
Postcondition: creates a hash from the ascii values of the characters
----------------------------------------------------------------------*/
void insert(int);
/*---------------------------------------------------------------------
insert
Precondition: uses ascii value created from process
Postcondition: inserts the string into the hash table using the hash
as the insertion point in the array.
----------------------------------------------------------------------*/
void display();
/*---------------------------------------------------------------------
display
Precondition: hash table is present
Postcondition: displays contents of hash table
----------------------------------------------------------------------*/
void search();
/*---------------------------------------------------------------------
search
Precondition: prompt user for a string to search the hash table for
Postcondition: search hash table for the string, and output results
----------------------------------------------------------------------*/
};
#endif
