timesearch.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#include "tvector.h"
#include "ctimer.h"
#include "strutils.h"       // for StripPunc and ToLower
#include "stringset.h"
#include "prompt.h"
#include "sortall.h"

// demonstrate differences between sequential and binary search
// Owen Astrachan, 5/4/99

void Read(const string& filename, tvector<string>& list)
// post: list is unsorted collection of all the strings
//       in text file filename, each string is converted to
//       lowercase with leading/trailing punctuation removed
{
    ifstream input(filename.c_str());
    string word;
    while (input >> word)
    {   StripPunc(word);
        ToLower(word);
        list.push_back(word);
    }
}

void makeSet(const tvector<string>& list,StringSet& sset)
// post: sset is set of strings from list
{
    int k;
    int len = list.size();
    for(k=0; k < len; k++)
    {   sset.insert(list[k]);
    }
}

int search(const tvector<string>& list, const string& key)
// precondition: list.size() == # elements in list
// postcondition: returns index of key in list, -1 if key not found
{
    int k;
    for(k=0; k < list.size(); k++)
    {   if (list[k] == key)
        {   return k;
       }
    }
    return -1;   // reach here only when key not found
}

int bsearch(const tvector<string>& list, const string& key)
// precondition: list.size() == # elements in list
// postcondition: returns index of key in list, -1 if key not found
{
    int low = 0;                   // leftmost possible entry
    int high = list.size()-1;      // rightmost possible entry
    int mid;                       // middle of current range
    while (low <= high)
    {   mid = (low + high)/2;
        if (list[mid] == key)       // found key, exit search
        {   return mid;
        }
        else if (list[mid] < key)   // key in upper half
        {   low = mid + 1;
        }
        else                        // key in lower half
        {   high = mid - 1;
        }
    }
    return -1;                      // not in list
} 

double timeLinear(const StringSet& sset, const tvector<string>& list)
{
    CTimer timer;
    StringSetIterator it(sset);
    
    timer.Start();
    for(it.Init(); it.HasMore(); it.Next())
    {   int index = search(list,it.Current());
        if (index == -1)
        {   cout << "missed a search for " << it.Current() << endl;
        }
    }
    timer.Stop();
    return timer.ElapsedTime();
}

double timeBinary(const StringSet& sset, const tvector<string>& list)
{
    CTimer timer;
    StringSetIterator it(sset);
    
    timer.Start();
    for(it.Init(); it.HasMore(); it.Next())
    {   int index = bsearch(list,it.Current());
        if (index == -1)
        {   cout << "missed a search for " << it.Current() << endl;
        }
    }
    timer.Stop();
    return timer.ElapsedTime();
}

int main()
{

   string filename = PromptString("enter file ");
   CTimer timer;
   tvector<string> list, sortedList;
   StringSet sset;
   
   timer.Start();
   Read(filename,list);
   timer.Stop();
   cout << timer.ElapsedTime() << " secs to read "
        << list.size() << " total words" << endl;
        
   timer.Start();
   makeSet(list,sset);
   timer.Stop();
   cout << "make set time:\t" << timer.ElapsedTime() << " set size: "
        << sset.size() << endl;       
        
   timer.Start();
   sortedList = list;
   QuickSort(sortedList,sortedList.size());
   timer.Stop();
   cout << "make sorted time:\t" << timer.ElapsedTime() << endl;
   
   cout << "unsorted search time:\t" << timeLinear(sset,list) << endl;
   cout << "sorted search time:\t"   << timeBinary(sset,sortedList) << endl;   
   return 0;
}