Binary Search Tree

[joe2011]

Hello,
So I have a dynamic string array and I fill it up with words. When I'm done with the insert if the array isn't full the last cells are empty and I'm wondering if there is any way to delete the last empty cells.

I was thinking something like:
string *arr;
arr = new string[3];

arr[1] = "yes";
arr[2] = "no";

delete arr[3]; //I know this is wrong

the arr[3] is empty and I don't want it anymore. Can I delete the arr[3] and finally the array size become 2? Because if I want to do this:

for(i=0;i<3;i++)
cout<<arr[i]<endl;

it will also print the empty cells. Obviously I wanna do this with way more big array and if I have an array with size = 100 and insert 50 words, it will also print and the 50 empty cells in the screen. Note that I don't know from the beginning the amount of words that I want to insert.

I don't know if you understood. Thanks in advance.

[lastchance]

Use a vector<string>

Then you can either use push_back() to put an arbitrary number of words, or you can create it with a decent size and then resize() it later.

[joe2011]

I never heard of this "vector<string>" and I checked it how it works. I want to store words from a text file to array. Can I do this with the vector<string>? I have a project to implement a binary search tree and after I store the words into the array, I insert them into the tree. I will have problem if I leave the empty cells? To be honest I didn't notice something weird with my tree. Do you suggest me to do something else?

[lastchance]

joe2011 wrote:

after I store the words into the array, I insert them into the tree. Do you suggest me to do something else?

I suggest you read the words one by one and insert them straight into the tree. You don't need an array to store them in first.

[joe2011]

Yeah, I thought about it, but my text file has numbers and punctuations and also I want to convert all the upper case letters into lower. So I store them into the array and then I do the convert inside the array. Can I do this while I insert them into the tree?

[highwayman]

Yes. It should be relatively easy.

General example:

while(true) {
  std::string val = getVal();
  transform(val);
  tree.insert(val);
}

[lastchance]

You can read one word at a time, put it through a filter that strips numbers and punctuation and does whatever change you wanted, then, if it's still a viable word after this mangling, puts it in your tree.

Repeat: there is no need to store in an intermediate array just to do that.

Time you showed some code.

[keskiverto]

I was thinking something like:

string *arr = new string[3];
arr[1] = "yes";
arr[2] = "no";
for ( i=0; i<3; i++ )
  cout<<arr[i]<endl;

You have two issues there:
1. Indexing starts from 0. Your "empty string" is at arr[0]
2. You hardcode that your array has exactly 3 items.

int MAX = 3;
string *arr = new string[MAX];
int count = 0; // indexing starts from 0
arr[count++] = "yes";
arr[count++] = "no";
for ( i=0; i<count; i++ ) // show used elements
  cout<<arr[i]<endl;

The one thing lacking in this is a safeguard that count<=MAX remains true.

To resize an array requires that
1. You create a new array with desired size
2. You copy existing data from old array to new
3. You remove the old array
4. You refer to the new array like you previously did refer to the old array

Many steps, many ways for things to go wrong. The std::vector does all that "under the hood" for you. Correctly.

[joe2011]

Guys thanks everyone but I've changed my code and I insert the words straight into the tree.

Here is a part of my new code:

    while (file>>word)
    {
        int len = word.size();
        for(j=0;j<len;j++)
        {
            //Convert upper case letters into lower
            if(word[j] >= 'A' && word[j] <= 'Z')
                word[j] = word[j] + 32;

            //Convert punctuations and numbers into space 
            if((word[j] >= '!' && word[j] <= '@') || (word[j] >= '[' && word[j] <= '`') || (word[j] >= '{' && word[j] <= '~'))
                word[j] = word[32];
        }

        tree.insert(word);
    }

The second if (Convert punctuations and numbers into space) isn't working 100% correct but it was the only thing I was able think. For example, if I insert the word "who's" the word convert into "who s" and thats obviously wrong. Have you any idea how I have to do it?

[keskiverto]

1. It is safer to use Standard Library functions for operations, like lowercase or test if punctuation:
http://www.cplusplus.com/reference/cctype/tolower/
http://www.cplusplus.com/reference/cctype/isdigit/
http://www.cplusplus.com/reference/cctype/ispunct/

2. What do you mean by "thats obviously wrong"?
"who s" is clearly "who's", where prime has been replaced with space, just like you want.


[EDIT] Oh wait, what is this: word[j] = word[32];?
Does every word have at least 33 characters?
Why all punctuation is replaced with the 33rd character of the word?

You want space, then make it so:
word[j] = ' ';