Specify and implement an ADT character string by using a linked chain of charact
ID: 3792253 • Letter: S
Question
Specify and implement an ADT character string by using a linked chain of characters. Include typical operations such as nding its length, appending one string to another, 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 .
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?
Explanation / Answer
Since we are not allowed to used array or vector we create our own class for list manipulation. Three class were created
#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();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.