Description

Re-write the String class from the previous work, but use a singly-linked list of character as the

representation. Like previous work, these strings will be of varying lengths and must grow and shrink as

necessary. Implement all the appropriate methods given below. Use memory storage proportional to the

number of characters in the string (no more and no less). Any memory errors reported by valgrind will

cause -40 points.

 Write the static methods given below: copy(L), append(L1, L2), length(L), reverse(L), compare(L1, L2),

stringToList(S), deleteList(L) This is the place to experiment with recursion. You could try writing them

iteratively at first, then try recursion after you have the codes working.

 Use the static methods to write the public methods as given in the class declaration below:

 Class String declaration:

class String

{

public:

/// Both constructors should construct

/// this String from the parameter s

explicit String( const char * s = "");

String( const String & s );

String operator = ( const String & s );

char & operator [] ( const int index );

int size() const;

int indexOf( char c ) const;

bool operator == ( const String & s ) const;

bool operator < ( const String & s ) const;

/// concatenates this and s

String operator + ( const String & s ) const;

/// concatenates s onto end of this

String operator += ( const String & s );

String reverse() const; // does not modify this String

void print( ostream & out ) const;

void read( istream & in );

~String();

private:

bool inBounds( int i )

{

return i >= 0 && i < length();

}

struct ListNode

{

char info;

ListNode * next;

ListNode(char newInfo, ListNode * newNext)

: info( newInfo ), next( newNext )

{

}// Below: primitives you *must* write and use (try recursion)

static ListNode * stringToList(const char *s);

static ListNode * copy(ListNode * L);

static ListNode * reverse(ListNode * L, ListNode * R = 0);

static ListNode * append(ListNode * L1, ListNode * L2); // +

static int compare(ListNode * L1, ListNode * L2);//like strcmp

static void deleteList(ListNode * L);

static int length(ListNode * L); // O(N) so call rarely

};

ListNode * head; // no other data members!! - especially no len!

};

ostream & operator << ( ostream & out, String str );

istream & operator >> ( istream & in, String & str );

● Write a main function which tests each function defined in your class String.

● Make it work with the main we provided below.

● You must make sure your program works correctly with the test mains and that you have no memory

leaks. Be sure to run them under valgrind with appropriate arguments to show your programs

have no memory leaks.