Sample Solution to Lab #1
/////////////////////////////////////////////////////////////////////////////
// Student Name : Denny Ubbm
// Student ID : 123-45-6789
// Course : CS 162
// Assignment : Lab #1
// Program File : search.cpp
// Due Date : 7/8/98
//
// Description : This implementation file contains functions necessary
// to read a data file, store it in an array, and perform
// various manipulations on the data, as specified in
// specification file search.h. Manipulations include:
// o Linear search on an unsorted list
// o Linear search on a sorted list
// o Binary search on a sorted list
// o A selection-type sort on a list
// o Deleting the first occurrence of a specified item
// o Deleting all occurrences of a specified item
//
/////////////////////////////////////////////////////////////////////////////
#include "search.h" // interface header file
#include <iostream.h> // for I/O
#include <iomanip.h> // for data manipulation
#include <fstream.h> // for file I/O
/////////////////////////////////////////////////////////////////////////////
// Function: ReadData
//
// This function reads integers from a text file. If there are
// more than MAX_LENGTH data, the extra data will not be read.
//
//
// Inputs: filename - the name of the file that contains the integers
//
// Outputs: list - the array representing the list of items
// count - the number of integers read in
// success - a Boolean indicating if the function successfully
// read in the integers
//
void ReadData(const char filename[],
ItemType list[],
int& count,
Boolean& success)
{
// holds input file
ifstream inFile;
// declare varible to temporarily hold input data
ItemType data;
// attempt to open file
inFile.open (filename);
// set counter to start at beginning of list
count = 0;
// test to see if file opened, if so, begin entering data into list
// if can't open, set boolean to FALSE
if (inFile)
{
// prime while loop
inFile >> data;
// read data into array until maximum array size is reached or
// EOF is encountered
while (inFile && count < MAX_LENGTH)
{
// read data into array named list
list[count] = data;
count++;
inFile >> data;
}
// set boolean to TRUE
success = TRUE;
}
else
{
// if can't open file, set boolean to FALSE and beep
success = FALSE;
cout<<"\a";
}
}
/////////////////////////////////////////////////////////////////////////////
// Function: LinearSearch
//
// This function searches sequentially for an item in an unsorted
// list.
//
// Inputs: list - the array representing the list of items
// item - the item to search for (type is ItemType)
// length - an integer representing the length of the list
//
// Outputs: index - an integer representing the item's position (if found)
// found - a Boolean indicating if the item was found
// compares - an integer representing the number of compares.
//
void LinearSearch(const ItemType list[],
ItemType item,
int length,
int& index,
Boolean& found,
int& compares)
{
// set index to start at beginning of list
index = 0;
// set compares to zero
compares = 0;
// loop through list until item is found or all data have been read
while (index < length && item != list [index])
index++;
// if item matches a value on the list, then index < length at drop
// from loop, so boolean is set to TRUE; if the item was not found,
// index will be equal to length at drop from loop, so boolean = FALSE
found = (index < length);
// if the item was found, the # of compares will be the index value
// at dropping out of the while loop plus 1; if not found, the # of
// compares will be the length of the list
if (found)
compares = index + 1;
else
compares = length;
}
/////////////////////////////////////////////////////////////////////////////
// Function: LinearSearchOrd
//
// This function searches sequentially for an item in an sorted list.
//
// Inputs: list - the array representing the list of items
// item - the item to search for (type is ItemType)
// length - an integer representing the length of the list
//
// Outputs: index - an integer representing the item's position (if found)
// found - a Boolean indicating if the item was found
// compares - an integer representing the number of compares.
//
void LinearSearchOrd(const ItemType list[],
ItemType item,
int length,
int& index,
Boolean& found,
int& compares)
{
// set index to start at beginning of list
index = 0;
// set compares to zero
compares = 0;
// since the list is sorted (ascending), loop through list until the
// item is greater than the value it is being compared to, or until
// all the data values in the list have been compared to item
while (item > list [index] && index < length)
index++;
// set boolean to TRUE if item matches a value in the list
found = (item == list[index]);
// if the item was found or if it was not found and the entire list
// has not been evaluated, then the # of compares will be the
// index plus 1; if the item was not found and the entire list has
// been searched, the # of compares will be the length of list
if (found || (!found && index < length))
compares = index + 1;
else
compares = length;
}
////////////////////////////////////////////////////////////////////////////
// Function: BinarySearch
//
// This function uses a binary search method to find an item in a
// sorted list.
//
// Inputs: list - the array representing the list of items
// item - the item to search for (type is ItemType)
// length - an integer representing the length of the list
//
// Outputs: index - an integer representing the item's position (if found)
// found - a Boolean indicating if the item was found
// compares - an integer representing the number of compares.
//
void BinarySearch(const ItemType list[],
ItemType item,
int length,
int& index,
Boolean& found,
int& compares)
{
// lower bound on list
int first = 0;
// upper bound on list
int last = length -1;
// middle index
int middle;
// set number of comparisons initially to zero
compares = 0;
// set boolean initially to indicate item not found
found = FALSE;
//loop through data until item
while (last >= first && !found)
{
// compute midpoint of array
middle = (first + last) / 2;
// search lower half
if (item < list[middle])
last = middle -1;
// search upper half
else if (item > list[middle])
first = middle + 1;
// item found
else
found = TRUE;
// increment compare counter each loop-through
compares++;
}
// if item is found, its index is equivalent to middle variable
index = middle;
}
/////////////////////////////////////////////////////////////////////////////
// Function: Sort
//
// This function sorts a list of items. When the function returns,
// the array will be sorted.
//
// Inputs: list - the array representing the list of items
// length - an integer representing the length of the list
//
// Outputs: list - the sorted array
//
void Sort(ItemType list[], int length)
{
// temporary variable
ItemType temp;
// outer loop counter
int passCount;
// inner loop counter
int placeCount;
// index of temporary minimim value
int minIndex;
// loop through the list
for (passCount = 0; passCount < length - 1; passCount++)
{
// temporarily set current item index to minimum index
minIndex = passCount;
// search rest of list for index of the smallest item in the list
// and set it to minIndex if it's smaller
for(placeCount = passCount + 1 ; placeCount < length ; placeCount++)
{
if (list[placeCount] < list[minIndex])
minIndex = placeCount;
}
// perform a swap on the two values, now smallest number is
// is in the placeCount index location (highest on list)
temp = list[minIndex];
list[minIndex] = list[passCount];
list[passCount] = temp;
}
}
////////////////////////////////////////////////////////////////////////////
// Function: DeleteOne
//
// This function deletes one item from an unsorted list
//
// Inputs: list - the array representing the list of items
// length - an integer representing the length of the list
// item - the item to delete
//
// Outputs: list - the array with one occurrence of item removed
// length - the length of the updated list
//
void DeleteOne(ItemType list[], int &length, ItemType item)
{
// declare a boolean variable to flag if item was found
Boolean located;
// set counter to start at beginning of list
int counter = 0;
// search list as was done in LinearSearch function
while (counter < length && item != list[counter])
counter++;
// set boolean to TRUE if item found
located = (counter < length);
// if item was found on the list, its position is list[counter]
if (located)
{
// loop through the list, starting at one postion past where
// the match was, and shift all values down, overwriting the
// matched item
while (counter < length)
{
list[counter] = list[counter + 1];
counter++;
}
// decrement the length by one since one value was "removed"
length -= 1;
} // if item was not found, change nothing
}
/////////////////////////////////////////////////////////////////////////////
// Function: DeleteAll
//
// This function deletes all elements from an unsorted list that
// match a certain item.
//
// Inputs: list - the array representing the list of items
// length - an integer representing the length of the list
// item - the item to search for
//
// Outputs: list - the array with all occurrences of 'item' removed
// length - the length of the updated list
//
void DeleteAll(ItemType list[], int &length, ItemType item)
{
// set outer loop counter to start at beginning of list
int outCounter = 0;
// declare another counter for the inner loop
int inCounter;
// loop through list, when a match is found, shift all values down,
// overwriting the matched item; decrement length and loop counter
// whenever an item is "removed"; if no match, change nothing
while (outCounter < length)
{
if (list[outCounter] == item)
{
for ( inCounter = outCounter ; inCounter < length ; inCounter++)
list [inCounter] = list [inCounter + 1];
length -= 1;
outCounter -=1;
}
outCounter++;
}
}
Back to Outline