Hvordan kan jeg teste dette?
Hej,Jeg skal teste nedenstaaende program's function der hedder:
int bin_search (int list[], int len, int value);
Men er meget i tvivl om hvordan jeg skal goere det. Jeg skal vist bruge min delete_value function, men hvordan? Her er mine test cases:
Case 1: Empty list
Expected outcome:
Result:
Case 2: Value in the list (beginning of the list)
Expected outcome:
Result:
Case 3: Value in the list (middle of the list)
Expected outcome:
Result:
Case 4: Value in the list (end of the list)
Expected outcome:
Result:
Case 5: Value in the list (A value that isn't there)
Expected outcome:
Result:
Programmet faar foelgende integer fra en tekst file gemt paa c drivet
2 13 48 90 23 44 88 45 97 32 48 97 67 453
Her er mit program:
#include <iostream.h> // for input and output statements
#include <fstream.h> // for reading from and writing to a file
#define DATAFILE "c:\\datafile.txt" // the file containing integer numbers
const int MAX_LEN = 50; // maximum number of elements
const char BLANK = ' '; // used for a dummy character
const int DONT_CARE = 0; // used for a dummy integer variable
const int SO_MANY_CHARS = 100; // to be used with ignor() to skip blanks
enum message_type {OPENING,CLOSING,UNKNOWN_CHAR, NOT_FOUND,POSITION_IN_LIST,WARNING};
//==========================================================================================
// prototypes
//==========================================================================================
void print_message(message_type sttm, char ch, int val, int pos);
void fill_list(ifstream &infile, int list[], int& len);
void print_list (const int list[], int len);
void get_menu_item (char& ans);
void get_value (int& val);
int find_position(const int list[],int len, int val);
void delete_value (int list[],int& len,int index);
void insertion_sort (int file, const int list[], int len );
int shift_right (int list[], int len, int pos);
int bin_search (int list[], int len, int value);
//******************************************************************************************
// main()
//******************************************************************************************
void main()
{
int list[MAX_LEN]; // the list for holding up to MAX_LEN numbers
int length; // number of elements of the array
int value; // value to be deleted from the list entered by the user
int index; // the index to the value to be deleted in the list
char answer; // answer to the query enterd by the user
ifstream infile; //input file stream
infile.open(DATAFILE,ios::in|ios::nocreate); //open datafile for reading
if (infile.fail())
cout<<"*** Can't open the file**"<<endl;
else
{
print_message(OPENING,BLANK,DONT_CARE,DONT_CARE);
fill_list (infile,list,length);
print_list(list, length);
do
{
get_menu_item(answer);
switch (answer)
{
case 'd': get_value (value);
index= bin_search (list, length, value);
if (index<0) // value not found
print_message(NOT_FOUND,BLANK, value,DONT_CARE );
else
{
print_message(POSITION_IN_LIST,BLANK, value,index+1); //add one to index to be user friendly
delete_value (list, length, index);
print_list(list, length);
}
break;
case 'q': print_message(CLOSING,BLANK,DONT_CARE,DONT_CARE);
break;
default: print_message (UNKNOWN_CHAR,answer,DONT_CARE,DONT_CARE);
break; //not necessary but a good habit
}//switch
} while (answer != 'q');
infile.close();
}
}
//******************************************************************************************
// print_message()
// This function writes messages on the screen.
//******************************************************************************************
void print_message(/*in*/ message_type sttm, //type of message
/*in*/ char ch, //used with UNKNOWN_CHAR message
/*in*/ int val, //used with NOT_FOUND and POSITION_INLIST message
/*in*/ int pos) //used with POSITION_INLIST message
{
switch (sttm)
{
case UNKNOWN_CHAR: cout<<"=======> Sorry I don't understand what "<<'"'<<ch<<'"'<< " means";
break;
case NOT_FOUND: cout<<"=======> Sorry "<<val<<" is not in the listn";
break;
case OPENING: cout<<"This program deletes a number form a given list for you. "
<<"Here is the list (read from a file):" << endl;
break;
case CLOSING: cout<<"***********************************************************n";
cout<<" Thanks for choosing our program and bye now.n";
cout<<"***********************************************************n";
break;
case POSITION_IN_LIST:
cout<<"The first occurance of the value "<<"("<<val<<")"<< " is at position ";
cout<<pos<<endl;
break;
case WARNING: cout<<"----Warning---> The file contains more than " << MAX_LEN<<" elements. ";
cout<<"Only the first "<< MAX_LEN<<" elements will be processed.n";
break;//UNNECESSARY BUT A GOOD HABIT
}
}
//******************************************************************************************
// fill_list()
// This function fills up the array with numbers in the file. If the file contains
// more than MAX_LEN numbers only the first MAX_LEN numbers will be processed.
//******************************************************************************************
void fill_list(/* in*/ ifstream &infile,//contains the numbers
/*out*/ int list[], //for holding the numbers
/*out*/ int& len) //length of the list
{
int buffer; //temporary storage for numbers
len=0; //initialize the length
infile >> buffer; // priming read in the buffer
while (infile && (len < MAX_LEN)) // as long as the file is not empty and
{ // there are enough locations in the array
list[len]=buffer;
len++;
infile >> buffer; // read the next number
}
if (infile) //More than MAX_LEN elements
print_message(WARNING,NOT_FOUND,BLANK,DONT_CARE);
}
//******************************************************************************************
// print_list()
// This function prints the elements of the array.
//******************************************************************************************
void print_list (/* in*/ const int list[], // the list
/*in*/ int len) // number of elements stored in the array
{
int curr_index;
for (curr_index =0; curr_index<len; curr_index++)
{
cout << list [curr_index]<<endl;
}
}
//******************************************************************************************
// get_menu_item()
// This function gets a menu item from the user.
//******************************************************************************************
void get_menu_item (/*out*/ char& ans) // d for delete and q for quit
{
cout<< "Would you like to [d]elete a value or [q]uit the program?";
cin >> ans;
cout << endl;
}
//******************************************************************************************
// get_value()
// This function gets an integer number from the user.
//******************************************************************************************
void get_value (/*out*/ int& val) // an integer number to be deleted from the list
{
cout<< "Enter the value you wish to delete: ";
cin >> val;
cout<<endl;
}
//******************************************************************************************
// find_position()
// This function finds the postion of the value in the list, if found. if the value is not
// in the list it returns -1.
//******************************************************************************************
int find_position(/*in*/ const int list[],// the list to be searched
int len, // the lenght of the list
int val) // the vlaue to be looked up
{
bool found=false; // Initialize found to false
int curr_pos =0; // Initialize curr_pos to zero
while ((curr_pos<len) && (!found)) // As long as the variable
// is not found and
// len < MAX_LEN
{
if( list[curr_pos] == val )
found= true;
else curr_pos++;
}
if (found)
return curr_pos;
else
return -1;
}
//******************************************************************************************
// delete_value()
// This function deletes the value from the list. Note that it is assumed the value is in
// the list.
//******************************************************************************************
void delete_value (/*out*/ int list[], // the list to be modified
/*out*/ int& len, // length of the list
/*in*/ int index) // the index of the value to be deleted
{
int last_index = len-1; // last_index as the last
// element in the list
for (int i=index; i < last_index; i++) // as long as curr_pos is
// smaller than last_index
{
list[i]=list[i + 1];
}
len--;
}
//******************************************************************************************
// insertion_sort()
// This function finds the correct position in the buffer if there is
// room in the array
//******************************************************************************************
void insertion_sort (ifstream &infile, int list[], int& len )
{
int buffer; // temporary storage for numbers
int position;
len=0;
infile >> buffer; // priming read in the buffer
while(infile && len < MAX_LEN) // as long as the file is not
{ // empty and there are enough
//locations in the array
position= find_position(list, len, buffer);
buffer=shift_right (list, len, position);
list[position]=buffer;
len++;
infile>>buffer; // priming read in the buffer
}
if (infile) //More than MAX_LEN elements
print_message(WARNING,NOT_FOUND,BLANK,DONT_CARE);
}
//******************************************************************************************
// shift_right()
// This function makes room for the position you want to enter
//
//******************************************************************************************
int shift_right (int list[], int len, int pos)
{
for( int i = len; pos < i; i-- )
{
list[i]=list[i-1];
}
return 0;
}
//******************************************************************************************
// bin_search()
// This function continues narrowing the part of the sequence being
// searched until only one term of the sequence remains.
//******************************************************************************************
int bin_search(/*in*/ int list[], // the list to be searched
int len, // the lenght of the list
int value) // the vlaue to be looked up
{
int middle; // initialize the middle
int lower=len; // initialize lower
int upper = len-1; // initialize upper to be
// the index of the last
// element in the list
bool found = false;
while ((upper >= lower) && (!found))// as long as upper is greater
// than or equal to lower and
{ // found is false
middle = (lower + upper)/2; // middle of interval
if (value == list[middle]) // value equal to middle value
// in the list
found = true;
else
if (value < list[middle]) // if value is smaller than
// middle value in the list
upper= middle-1;
else
lower = middle + 1;
}
if (found = true)
return middle;
else
return -1;
}
