< Back

Lecture 24 - Data Structures

---

As usual, create a directory to hold today's activities:

$ mkdir ~/cs170/labs/lab24 
$ cd ~/cs170/labs/lab24 

---

Data Structures

So far this semester, we have spent a lot of time worrying about standard C++ syntax and various algorithms. Today, we are going to really start focusing on data structures: how do we store large amounts of data within our program, in a sane way? One data structure we have used is a String. How do strings store data? How do various processes work on them? Today, we will explore the background on strings.

---

testString.cc

---

One of the quickest ways to get a good idea of how a datastructure works is by implementing it. So today, we are going to spend some time implementing our own String class which we will call MyString. By the end of the day today, you should really, really appreciate the built in string class!

Details

Create a C++ class called MyString. This means you need a .h and .cc file for this class. You are going to be implementing your own version of the standard string object.

A MyString object needs 3 pieces of member data:

• A pointer to a char array, which is storing the data of the string,
• The number of characters currently stored, and
• The size of the character array (minus 1...pay attention to the lecture).

When a MyString object gets initialized, you need to allocate space for 1 character, the '\0' (null-terminator) character. Make sure at every point, when every one of your methods finishes, you hae the null-terminator at the end of the string.

Add a method void addCharacter(char c) to your MyString object. This method should add the specified character to the end of the current string.

Note: If there is not enough space for the character at the end of the string, you should double the amount of space that the string is using for storage. You should then copy everything from the previous array into the new array. Then add the new character.

Example

  MyString myName;
  myName.addCharacter('S');
  myName.addCharacter('c');
  myName.addCharacter('o');
  myName.addCharacter('t');
  myName.addCharacter('t');
  myName.addCharacter('y');
  cout << myName.getString() << endl; // Scotty is printed to the terminal.

Once you have a mechanism for adding new characters to the string, you are basically done with your MyString class. However, it's not entirely as useful as the built in String object. We should be able to initialize a MyString with another String, and we should be able to expand the MyString by adding another MyString to the end.

Details

Add a new constructor MyString(string starter). This constructor should use your addCharacter method to continually add a character to the MyString that is being created.

Add an additional method called void add(MyString & other). Notice that this method's parameter has an '&' character in the parameter list. If you ignore this, you might get some weird behavior. You probabaly wouldn't experience it here, but you should put it there. Again, this should simply use the addCharacter method repeatedly to the implicit string.

Example

  MyString myName("Scotty";
  MyString extension(" is awful?");
  myName.add(extension);
  cout << myName.getString() << endl;

---