Question

Specify and implement an ADT character string by using a linked chain of characters. Include typical operations such as fi nding its length, appending one string to another, fi nding the index of the leftmost occurrence of a character in a string, and testing whether one string is a substring of another.

Do not #include<string>...you are making something like a STL string. Also do not use an array or vector...the point is to practice linked lists. Remember the last character in a string is a \n.

You should be able to use subscripting [ ] to go to a specific position of the string.

Note operator + can be a friend function but operator [ ] must be a member function not a friend function. Remember that operator + if a member function will have only one parameter (the right hand side of the + ) Operator [ ] will return an index which points to the location of the subscript.

This is c++ language problem, Can someone help me on this problem?

Answer 1

Since we are not allowed to used array or vector we create our own class for list manipulation. Three class were created

1. ListNode : It holds a single character of the string and a points to next character or NULL.
2. List: It holds the head and tails of the ListNode forming a chain.
3. String: Class to have basic operation on string.

#include <iostream>

using namespace std;

class ListNode {

public:

   char item;

   ListNode *next;

   ListNode(char ch) {

       item = ch;

       next = NULL;

   }

   ListNode(char ch, ListNode *next) {

       item = ch;

       this->next = next;

   }

};

class List {

private:

   ListNode *first;

   ListNode *last;

public:

   ListNode *getIterator() {

       ListNode *temp = first;

       return temp;

   }

   int length;

   List() {

       first = last = NULL;

       length = 0;

   }

   void insertFront(char ch) {

       if (first == NULL) {

           first = new ListNode(ch);

           last = first;

       } else {

           ListNode *newNode = new ListNode(ch);

           newNode->next = first;

           first = newNode;

       }

       ++length;

   }

   void insertRear(char ch) {

       if (first == NULL) {

           first = new ListNode(ch);

           last = first;

       } else {

           ListNode *newNode = new ListNode(ch);

           last->next = newNode;

           last = newNode;

       }

       ++length;

   }

};

class String {

private:

   int length;

   List *list;

public:

   String() {

       length = 0;

       list = new List();

   }

   String(char array[], int n) {

       length = 0;

       list = new List();

       for (int i = 0; i < n; ++i) {

           list->insertRear(array[i]);

       }

       if (list != NULL)

           length = list->length;

   }

   int getLength() {

       return length;

   }

   void append(String rhs) {

       for (int i = 0; i < rhs.getLength(); ++i) {

           list->insertRear(rhs[i]);

       }

       if (list != NULL)

           length = list->length;

   }

   int indexOfLeftMostChar(char ch) {

       ListNode *iter = list->getIterator();

       int idx = 0;

       while (iter) {

           if (iter->item == ch) {

               return idx;

           }

           ++idx;

           iter = iter->next;

       }

       return -1;

   }

   char operator[](const int index) {

       if (index < 0 || index >= length) {

           throw std::out_of_range("String index out of range");

       }

       ListNode *iter = list->getIterator();

       for (int i = 0; i < index; ++i)

           iter = iter->next;

       return iter->item;

   }

};

int main() {

   char a[3] = { 'a', 'b', 'c' };

   String s1(a, 3);

   cout << s1.getLength() << endl;

   cout << s1[0] << endl;

   char b[5] = { 'd', 'e', 'e', 'g', 'e' };

   String s2(b, 5);

   cout << s2.indexOfLeftMostChar('e') << endl;

   s1.append(s2);

   cout << s1.getLength();

}