listreverse.cpp

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

#include <iostream>
#include <string>
using namespace std;
#include "clist.h"

StringList RevAux(StringList list, StringList sofar)
// pre: list = (a_0, a_1, ..., a_(n-1))
// post: returns (a_(n-1), ..., a_1, a_0, sofar)
{
    if (list.IsEmpty()) return sofar;
    return RevAux(list.Tail(), cons(list.Head(),sofar));
}
StringList Reverse2(StringList list)
// pre: list = (a_0, a-1, ..., a_(n-1))
// post: return  (a_(n-1), ... a_1, a_0)
{
    return RevAux(list,StringList());
}
StringList Reverse(StringList list)
// pre: list = (a_0, a-1, ..., a_(n-1))
// post: return  (a_(n-1), ... a_1, a_0)
{
   if (list.IsEmpty()) return list;  
   return append(list.Head(),Reverse(list.Tail()));
}
void Print(StringList list)
{
    cout << list.Printer(",") << endl;
    cout << "# cons calls = " << StringList::ConsCalls() << endl << endl;
}

int main()
{
    StringList spices,spices2;
     
    spices = cons(string("paprika"), cons(string("cayenne"),
				cons(string("chili"), cons(string("turmeric"),
				    cons(string("pepper"), StringList())))));			  
	spices2 = cons(string("curry"), cons(string("coriander"),
	             cons(string("cumin"), spices)));
    Print(spices);
    Print(spices2);
    Print(Reverse(spices));
    Print(Reverse2(spices));
    return 0;
}