• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 756
  • Last Modified:

find anagrams in an array using pointers in c++

I am working on a homework assignment for my c++ class and I am stumped.  

I need to read words from a file into an array.  then create a second array with the key value of those words (IE bubble sort these words) then sort the array of keys while keeping the word array in the same order.  Then return the words that have duplicate keys, which are anagrams.  I have gotten the code to read in the words and I think I am copying the array right.  I am stuck on how to sort the words into the keys  what I have is below.  Thanks for any help anyone can give.  Getting down to the wire and now I'm stuck.

Here is my psuedocode I am not sure if this makes sense but I'd love some guidance

for ( bubbleKey = 0; bubbleKey < wordCount; bubbleKey++ ) // I guess I would do this to step through the array and get each word
{

    strlen( keyArray[index] );  // Use this to get the length of the word

    //create an array with the length of the word

    //put the letters into the array (not sure how to do this)

    //Perform a bubble sort on the temporary array

} // Do this for every word


-------------
#include <iostream>
#include <fstream>
using namespace std;

char** read(const char* fileName, int& count)
{
  ifstream countingStream(fileName);
  // first count them
  count = 0;
  while (true)
  {
            char line[100];
            countingStream.getline(line, 100);
            if (strlen(line) == 0)
            {
                  break;
            }
            count += 1;
  }
  countingStream.close();

  ifstream readingStream(fileName);
  char** words = new char* [count];

  for (int index = 0; index < count; ++index)
  {
            char line[100];
            readingStream.getline(line, 100);
            words[index] = strdup(line);
            cout << line << std::endl;
  }
  readingStream.close();
  return words;
}

char** arrayCopy(char* words[], int& count)
{
      int wordCount;
      char** keyArray = new char* [wordCount];
      for (int index = 0; index < wordCount; ++index)
      {
            keyArray[index] = strdup(words[index]);
      }

      return keyArray;
}

void getKeys(char* keys[])
{


}

void bubbleSort (char *array , int& wordCount)
{
      

}
int main ()
{
      int wordCount;
      char** words = read("c:\\words.txt",wordCount);
      char** keys = arrayCopy(words,wordCount);
      
      system("pause");
      return 0;

}
0
urobins
Asked:
urobins
  • 28
  • 22
1 Solution
 
ozoCommented:
You could use the qsort function
Synopsis
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
Description
The qsort function sorts an array of nmemb objects, the initial element of which is
pointed to by base. The size of each object is specified by size.
The contents of the array are sorted into ascending order according to a comparison
function pointed to by compar, which is called with two arguments that point to the
objects being compared. The function shall return an integer less than, equal to, or
greater than zero if the first argument is considered to be respectively less than, equal to,
or greater than the second.
0
 
urobinsAuthor Commented:
I thnk I have to use a bubble sort, which I am fairly certain I have working okay, my main problem is isolating the words in the array to sort the word.  I am pretty sure my bubble sort will work on this too, if I can pull the words out, I now that they are arrays of char's I just can't get them isolated right...
0
 
Infinity08Commented:
>>       int wordCount;
>>       char** keyArray = new char* [wordCount];

wordCount does not contain a valid value when you use it to allocate memory ... You probably want to use count instead.


Now, you need to sort each word in the keyArray using bubble sort (qsort can thus NOT be used, as it uses quicksort). You can implement your own bubble sort using the algorithm on this page :

        http://en.wikipedia.org/wiki/Bubble_sort

Your pseudo code is not bad :


>> // I guess I would do this to step through the array and get each word

Indeed.

>> strlen( keyArray[index] );  // Use this to get the length of the word

yep.

>> //create an array with the length of the word
>> //put the letters into the array (not sure how to do this)
>> //Perform a bubble sort on the temporary array

You don't need to create a new array - you can perform the sort on the string in the keyArray[index] position.

You'd place the bubble sort in a function that takes a string as input, and sorts the characters in the string. Then you can call that function for every element in the keyArray table.


Then finally, you need to find the duplicate keys, and return the original words that correspond to them. There are different approaches to this, but the one I'd prefer goes like this :

         1) create a struct that that contains two pointers : one to the original word in the words array, and one to the corresponding key in the keys array.
         2) now create an array of these structs containing one struct for each of the original words.
         3) sort this array, using the key pointer.
         4) you can now easily spot the duplicates (they will be next to each other), and using the word pointer, you can retrieve the original words.

If this looks too complicated to you, you can also use a more brute-force method :

         1) go over the keys array, and check if there's a duplicate in the rest of the array for every key.
         2) if you find a duplicate, then you can retrieve the original words from the words array that have the same indexes.
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
Infinity08Commented:
>> bubble sort, which I am fairly certain I have working okay

Can you show what you have so we can take a look at it ?
0
 
urobinsAuthor Commented:
here is my bubble sort I have used it on a single array so I guess it will need some modifications but I think that shouldn't be too difficult

void bubbleSort (char *array , int& wordCount)
{
      for (int pass =0; pass < size-1;pass++)
      
            for (int compare =0; compare < size -1; compare++)

                  if (array[compare] > array[compare +1])
                        swap (&array[compare], &array[compare+1);
      

}

void swap (int *const element1Pointer, int * const element2Ptr)
{
      int tempHold = *element1Ptr;
      *element1Ptr=*element2Ptr;
      *element2Ptr= tempHold;
}
0
 
Infinity08Commented:
1)
>> void bubbleSort (char *array , int& wordCount)

I assume you wanted to pass size (ie. the length of the string) ?


2)
>>             for (int compare =0; compare < size -1; compare++)

Your start point for the inner loop should be the element after the current one, and the last element should be the last in the string (assuming that size contains the strlen() of the string) :

            for (int compare = pass + 1; compare < size; compare++)


3)
>>                   if (array[compare] > array[compare +1])

You should compare the two previous values :

                  if (array[compare - 1] > array[compare])

Same for the swap call of course !


4) Your swap function should swap characters, not ints.


5) Finally, you need to be consistent with your parameter usage : element1Pointer is not the same as element1Ptr ...
0
 
urobinsAuthor Commented:
Thanks, I will make the changes it was code I used for an earlier assignment that I through together real quick (should have cut and pasted :) )

I need two bubble sorts right?  I'll need one that will sort the string and one that will sort the actual array right?  Or could I use the same sort and just call wordcount something generic because I'll either pass the number of words or the number of characters?  Also don't I have to pass strlenght+1 to account for the null space?

0
 
urobinsAuthor Commented:
So here is what i have now.  I'll have to create another bubble sort, I guess I'll call it bubbleSortArray for doing the arrays and I'll need to swap both arrays the same right?  I am not allowed to use structs yet because we haven't been taught them so what I was thinking was this

bubble sort the array of keys and when I move an element in keys, move the same element in words.  that way they are sorted the same, I can then work through keys and when I find a dup print the element from both arrays.


void bubbleSortKeys (char *array , int& wordCount)
{
      for (int pass =0; pass < size-1;pass++)
      
             for (int compare = pass + 1; compare < size; compare++)

                   if (array[compare - 1] > array[compare])
                        swap (&array[compare], &array[compare+1);
      

}

void swap (char *const element1Pointer, char * const element2Pointer)
{
      char tempHold = *element1Pointer;
      *element1Pointer=*element2Pointer;
      *element2Pointer= tempHold;
0
 
Infinity08Commented:
>> I need two bubble sorts right?  I'll need one that will sort the string and one that will sort the actual array right?

You need at least the one for the strings. Sorting the array is not absolutely required, but makes things easier.


>> Or could I use the same sort and just call wordcount something generic because I'll either pass the number of words or the number of characters?

You could make it generic, but that involves techniques that might be too advanced for your assignment (have you heard of templates ?). So, I would just make two functions for now.


>> Also don't I have to pass strlenght+1 to account for the null space?

No. We don't need to sort the terminating null character, so we can just ignore it inside the bubble sort function.


>> bubble sort the array of keys and when I move an element in keys, move the same element in words.  that way they are sorted the same, I can then work through keys and when I find a dup print the element from both arrays.

If you're not allowed to use structs, then the approach I explained earlier is indeed not possible. What you described sounds like a good alternative to me :) Remember that you just have to swap the pointers around, not the actual string characters.



btw, I see that you didn't do all the modifications to the bubbleSortKeys function that I suggested, namely :

1) wordCount is not used in the function - instead you use size ...

3) you didn't change the swap arguments accordingly ... It needs to become :

                        swap (&array[compare - 1], &array[compare);
0
 
urobinsAuthor Commented:
Thanks, sorry had to run in to work unfortunately.  Just got back and will try those changes, I really appreciate the help with this!
0
 
urobinsAuthor Commented:
its giving me this error when I try to build.  my code is as follows:  any ideas?  I'm gonna cheap chuggin away :)


#include <iostream>
#include <fstream>
using namespace std;

char** read(const char* fileName, int& count)
{
  ifstream countingStream(fileName);
  // first count them
  count = 0;
  while (true)
  {
            char line[100];
            countingStream.getline(line, 100);
            if (strlen(line) == 0)
            {
                  break;
            }
            count += 1;
  }
  countingStream.close();

  ifstream readingStream(fileName);
  char** words = new char* [count];

  for (int index = 0; index < count; ++index)
  {
            char line[100];
            readingStream.getline(line, 100);
            words[index] = strdup(line);
            cout << line << std::endl;
  }
  readingStream.close();
  return words;
}

char** arrayCopy(char* words[], int& count)
{
      
      char** keyArray = new char* [count];
      for (int index = 0; index < count; ++index)
      {
            keyArray[index] = strdup(words[index]);
      }

      return keyArray;
}

void getKeys(char* keys[])
{


}

void bubbleSortKeys (char *array , int& count)
{
      for (int pass =0; pass < count-1;pass++)
      
             for (int compare = pass + 1; compare < count; compare++)

                   if (array[compare - 1] > array[compare])
                        swap (&array[compare - 1], &array[compare]);

      

}

void swap (char *const element1Pointer, char * const element2Pointer)
{
      char tempHold = *element1Pointer;
      *element1Pointer=*element2Pointer;
      *element2Pointer= tempHold;
}
int main ()
{
      int wordCount;
      char** words = read("c:\\words.txt",wordCount);
      char** keys = arrayCopy(words,wordCount);
      
      system("pause");
      return 0;

}



d:\my documents\visual studio 2005\projects\project2\project2\bubblesort.cpp(65) : error C2664: 'void std::swap<char*__w64 >(_Ty &,_Ty &)' : cannot convert parameter 1 from 'char *__w64 ' to 'char *__w64 &'
1>        with
1>        [
1>            _Ty=char *__w64
1>        ]
0
 
Infinity08Commented:
Your swap is not visible when you call it in bubbleSortKeys, so it uses the std::swap (the standard swap function).

Move the implementation of your swap function BEFORE the bubbleSortKeys function.
0
 
urobinsAuthor Commented:
I put prototypes in will that achieve the same thing?  after doing that the error went away :)
0
 
Infinity08Commented:
>> I put prototypes in will that achieve the same thing?  after doing that the error went away :)

Yes, that's ok too.
0
 
urobinsAuthor Commented:
Here is what I have now but I am getting an error compiling at line 63 which is this line
bubbleSortKeys(keys[keyIndex], strlen(keys[keyIndex]);

I don't see a problem with it though?


// Uriah Robins
//Using code snippett provided by professor
//Program to read in words from file to an array and using modified bubble sort find anagrams.

#include <iostream>
#include <fstream>
using namespace std;

//prototypes
char read (char *, int);
void swap (char * const, char * const);
char arrayCopy(char* , int& );
void getKeys(char*, int& );
void bubbleSortKeys (char * , int& );

char** read(const char* fileName, int& count)
{
  ifstream countingStream(fileName);
  // first count them
  count = 0;
  while (true)
  {
            char line[100];
            countingStream.getline(line, 100);
            if (strlen(line) == 0)
            {
                  break;
            }
            count += 1;
  }
  countingStream.close();

  ifstream readingStream(fileName);
  char** words = new char* [count];

  for (int index = 0; index < count; ++index)
  {
            char line[100];
            readingStream.getline(line, 100);
            words[index] = strdup(line);
            cout << line << std::endl;
  }
  readingStream.close();
  return words;
}

char** arrayCopy(char* words[], int& count)
{
      
      char** keyArray = new char* [count];
      for (int index = 0; index < count; ++index)
      {
            keyArray[index] = strdup(words[index]);
      }

      return keyArray;
}

void getKeys(char* keys[], int& count)
{
      for (int keyIndex = 0; keyIndex < count; ++keyIndex)
      {
            bubbleSortKeys(keys[keyIndex], strlen(keys[keyIndex]);
      }


}

void swapKeys (char *const element1Pointer, char *const element2Pointer)
{
      char tempHold = *element1Pointer;
      *element1Pointer=*element2Pointer;
      *element2Pointer= tempHold;
}

void bubbleSortKeys (char *array , int& count)
{
      for (int pass =0; pass < count-1;pass++)
      
             for (int compare = pass + 1; compare < count; compare++)

                   if (array[compare - 1] > array[compare])
                        swapKeys (&array[compare - 1], &array[compare]);

}


int main ()
{
      int wordCount;
      char** words = read("c:\\words.txt",wordCount);
      char** keys = arrayCopy(words,wordCount);
      getKeys(keys,wordCount);

      system("pause");
      return 0;

}
0
 
urobinsAuthor Commented:
found the missing ) but I don't see why it doesn't like my second paramater?
0
 
Infinity08Commented:
Use this header for the bubbleSortKeys function :

        void bubbleSortKeys (char *array , int& count)

You can't pass a reference to a temporary. And in this case, you don't need a reference, since count is not modified by the bubbleSortKeys function.
0
 
Infinity08Commented:
Oops, I meant this of course :

        void bubbleSortKeys (char *array , int count)
0
 
urobinsAuthor Commented:
Thanks, Yeah I just figured that out and I have it sorting the words now.  So I need to get the array sorted too (a requirement, while not necessary gotta do whats asked I guess :) )  

So this is where I am a little fuzzy, I can do the same sort of sorting function right?  Now I need to sort both arrays of pointers while I do this, I'm not too sure how to go about this though..

0
 
Infinity08Commented:
>> So this is where I am a little fuzzy, I can do the same sort of sorting function right?

Indeed, although sorting an array of strings is slightly more complicated than sorting an array of characters. Just slightly :)

First of all, you'll need the strcmp function to compare two strings, and see which one is the smallest. The swap function will swap the pointers around. The rest will be pretty much the same (except that you'll need to use strings instead of characters). Does that get you started ?
0
 
Infinity08Commented:
Maybe this is interesting : a reference for the strcmp function :

        http://www.cplusplus.com/reference/clibrary/cstring/strcmp.html

btw, just out of curiosity - is there a reason you use char* (C style strings) instead of std::string (C++ strings) ?
0
 
urobinsAuthor Commented:
I asked the same question!  This instructor has us using a lot of C instead of C++ even though this is a c++ class.   I wish I had an answer but alas I don't.  This is the way he told us to do it.  Maybe it is so we appreciate the power of C++ when we start getting into it more.  dunno though.  


So I will need to do a sort by using the strcmp on each string, I'll read up on that.  Thanks again for all of your help I do appreciate it.  These online courses get to be difficult with such limited access to the teacher.  Haven't done any c/c++ coding in about 7 years or so :)


0
 
Infinity08Commented:
You're doing fine ... If I'm not giving enough information, then let me know.
0
 
urobinsAuthor Commented:
Nope perfect so far!  I want to learn what I'm doing so I appreciate you giving me just enough to get me going :)
0
 
urobinsAuthor Commented:
so do I do something like

void bubbleSortArray (char *array , int& count)
{
      for (int pass =0; pass < count-1;pass++)
      
             for (int compare = pass + 1; compare < count; compare++)

                   if (strcmp(array[compare - 1],  array[compare])>0)
                        swap (&array[compare - 1], &array[compare]);

}
0
 
Infinity08Commented:
Close. Right now, you're still passing a character array. That should be a string array (char**).
And the swap function will have to be a different one - one that swaps char* instead of char.
And finally, as you said earlier, you'll have to do the same swap in the words array too.
0
 
urobinsAuthor Commented:
Thanks!  I'll take a stab at that.
0
 
urobinsAuthor Commented:
will this do it

void bubbleSortArray (char **array,char **array2 , int& count)
{
      for (int pass =0; pass < count-1;pass++)
      
             for (int compare = pass + 1; compare < count; compare++)

                   if (array[compare - 1] > array[compare])
                   {
                        swapString (&array[compare - 1], &array[compare]);
                        swapString (&array2[compare -1], &array2[compare]);
                   }

void swapString (char *const element1Pointer, char *const element2Pointer)
{
      char* tempHold = *element1Pointer;
      *element1Pointer=*element2Pointer;
      *element2Pointer= tempHold;
}

0
 
Infinity08Commented:
If you use strcmp for the compare like you did before, then the bubbleSortArray function looks ok.

The swapString function however will have to swap char*'s. So, you'll need to pass a pointer to a char*, or a char**.
0
 
urobinsAuthor Commented:
Okay so I fixed the strcmp wasn't paying attention :)
How do I go about passing a pointer to a char*  

so instead of passing the char *const elemexxxxxx I should be passing something different?




void bubbleSortArray (char **array,char **array2 , int& count)
{
      for (int pass =0; pass < count-1;pass++)
      
             for (int compare = pass + 1; compare < count; compare++)

                   if (strcmp(array[compare - 1],  array[compare])>0)
                   {
                        swapString (&array[compare - 1], &array[compare]);
                        swapString (&array2[compare -1], &array2[compare]);
                   }

}
0
 
Infinity08Commented:
>> so instead of passing the char *const elemexxxxxx I should be passing something different?

Look at it this way. Your first swap function swapped char's. In order to be able to swap char's, you needed to pass pointers to char's as arguments :

        void swapKeys (char *const element1Pointer, char *const element2Pointer)

And inside the swap function, those pointers are dereferenced using *element1Pointer and *element2Pointer.

Now, we need to do the same, but for char*'s instead of char's. So, basically, you replace the char's by a char* :

        void swapStrings (char **const element1Pointer, char **const element2Pointer)
0
 
urobinsAuthor Commented:
So like this then... I think I get it!

void swapString (char **const element1Pointer, char **const element2Pointer)
{
      char** tempHold = **element1Pointer;
      **element1Pointer=**element2Pointer;
      **element2Pointer= tempHold;
}


0
 
urobinsAuthor Commented:
I get these errors when I try to compile

1>d:\my documents\visual studio 2005\projects\project2\project2\bubblesort.cpp(83) : error C2440: 'initializing' : cannot convert from 'char' to 'char **'
1>        Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
1>d:\my documents\visual studio 2005\projects\project2\project2\bubblesort.cpp(85) : error C2440: '=' : cannot convert from 'char **' to 'char'
0
 
Infinity08Commented:
>> So like this then... I think I get it!

Not quite. I guess I didn't explain it well.

The first swap function for chars looked like this :

        void swapKeys (char *const element1Pointer, char *const element2Pointer)
        {
              char tempHold = *element1Pointer;
              *element1Pointer=*element2Pointer;
              *element2Pointer= tempHold;
        }

It works as follows : the two pointers element1Pointer and element2Pointer contain the memory addresses of the two characters that need to be swapped. ie. the character at memory address element1Pointer needs to be put at memory address element2Pointer, and vice versa.

By dereferencing the element1Pointer, we get the character that is stored at that memory address :

        *element1Pointer

We put that character in a temporary variable tempHold :

        char tempHold = *element1Pointer;

Then we can copy the character at memory address element2Pointer to memory address element1Pointer. We need to dereference the pointers again, because we need the characters :

        *element1Pointer=*element2Pointer;

And finally, we copy the temporary character to memory address element2Pointer :

        *element2Pointer= tempHold;

Notice that I use "pointer" and "memory address" to refer to the same thing ? That's because a pointer is basically a memory address, namely the memory address of the data the pointer is pointing to.


Now, we don't want to swap char's - we want to swap char*'s. The algorithm is exactly the same : we take two pointers to char*'s, and swap the char*'s they're pointing to using a temporary variable :

        void swapStrings (char **const element1Pointer, char **const element2Pointer)
        {
              char *tempHold = *element1Pointer;
              *element1Pointer=*element2Pointer;
              *element2Pointer= tempHold;
        }

Note that tempHold is a char*, not a char**, because the data we're swapping is a char*.
Note further that we only dereference once - we want the data that is stored at a certain memory address, and in this case, that's a char*.


For more information on pointers, and dereferencing, take a look at this tutorial :

        http://www.cplusplus.com/doc/tutorial/pointers.html
0
 
Infinity08Commented:
Pointers are one of the more complicated things to get your head around in C/C++. Try to really understand what's happening - make drawings of the memory and the data it contains, that will make things clearer.

Remember that a pointer is just a memory address. Keeping that in mind should help you in understanding pointer operations.
0
 
urobinsAuthor Commented:
Thank you so much.  Yeah I am having a little trouble with the terminology and the notations, but I think I get it now!  

So I have it all working it would appear :)

Now I need to go through and find my duplicates and I am assuming I can use something like this

void findDuplicates(char* keys[],char* words[], int& count)
{
      int length=0;
      for (int keyIndex = 0; keyIndex < count; ++keyIndex)
      {
            if (strcmp(array[compare - 1],  array[compare])==0)
            {
                  cout << keys[keyIndex] << words[keyIndex]<< endl;
            }            
      }
}
0
 
urobinsAuthor Commented:
sorry like this
void findDuplicates(char* keys[],char* words[], int& count)
{
      int length=0;
      for (int keyIndex = 0; keyIndex < count; ++keyIndex)
      {
            if (strcmp(keys[count - 1],  words[count])==0)
            {
                  cout << keys[keyIndex] << words[keyIndex]<< endl;
            }
            
            
      }


}
0
 
urobinsAuthor Commented:
whoops more like this ;) Doesn't run quite right yet but I think I'm on the right track.

void findDuplicates(char* keys[],char* words[], int& count)
{
      int length=0;
      for (int keyIndex = 0; keyIndex < count; ++keyIndex)
      {
            if (strcmp(keys[count - 1],  keys[count])==0)
            {
                  cout << keys[keyIndex] << words[keyIndex]<< endl;
            }            
      }
}

0
 
Infinity08Commented:
>> Yeah I am having a little trouble with the terminology and the notations, but I think I get it now!  

Pointers are an important aspect of C/C++, and it takes some time to understand. A lot of practice helps a lot ;)


About the findDuplicates function : it would indeed look something like that. Although you need to be careful with the indexes :

1) You're using both keyIndex and compare. You should choose one and use that.

2) if the index is 0 (first iteration of the loop), then you will compare it with the string at index -1 ... That's not correct. You will have to start your loop at the second position.

Also : think about what happens if more than two words have the same key.
0
 
urobinsAuthor Commented:
yeah after I posted that I caught the problem this is what I fixed it with.  I think it is right but I'm not getting  quite the right out put.  My sort is a little off here is my entire program.  Here is the small file I am testing with

RUDE
WORD
DURE
FROM
FORM
LETTER

when I do a print of the sorted array of keys this is what is being returned... Rude isn't keying right and for some reason word isn't swapping right either... any ideas?

ODRW
DERU
ELERTT
FMOR
FMOR
RDEU



#include <iostream>
#include <fstream>
using namespace std;

//prototypes
char read (char *, int);
void swapChar(char * const, char * const);
void swapString(char ** const, char ** const);
char arrayCopy(char* , int& );
void getKeys(char*, int& );
void bubbleSortKeys (char * , int );
void bubbleSortArray (char **,char ** , int& );
void findDuplicates(char* ,char* , int& );

char** read(const char* fileName, int& count)
{
  ifstream countingStream(fileName);
  // first count them
  count = 0;
  while (true)
  {
            char line[100];
            countingStream.getline(line, 100);
            if (strlen(line) == 0)
            {
                  break;
            }
            count += 1;
  }
  countingStream.close();

  ifstream readingStream(fileName);
  char** words = new char* [count];

  for (int index = 0; index < count; ++index)
  {
            char line[100];
            readingStream.getline(line, 100);
            words[index] = strdup(line);
            cout << line << std::endl;
  }
  readingStream.close();
  return words;
}

char** arrayCopy(char* words[], int& count)
{
      
      char** keyArray = new char* [count];
      for (int index = 0; index < count; ++index)
      {
            keyArray[index] = strdup(words[index]);
      }

      return keyArray;
}

void getKeys(char* keys[], int& count)
{
      int length=0;
      for (int keyIndex = 0; keyIndex < count; ++keyIndex)
      {
            length =strlen(keys[keyIndex]);
            bubbleSortKeys(keys[keyIndex], length);
            //cout << length <<endl<<keys[keyIndex]<<endl; // Testing Line
      }


}

void swapChar (char *const element1Pointer, char *const element2Pointer)
{
      char tempHold = *element1Pointer;
      *element1Pointer=*element2Pointer;
      *element2Pointer= tempHold;
}

void swapString (char **const element1Pointer, char **const element2Pointer)
{
      char* tempHold = *element1Pointer;
      *element1Pointer=*element2Pointer;
      *element2Pointer= tempHold;
}


void bubbleSortKeys (char *array , int count)
{
      for (int pass =0; pass < count-1;pass++)
      
             for (int compare = pass + 1; compare < count; compare++)

                   if (array[compare - 1] > array[compare])
                        swapChar (&array[compare - 1], &array[compare]);

}

void bubbleSortArray (char **array,char **array2 , int& count)
{
      for (int pass =0; pass < count-1;pass++)
      
             for (int compare = pass + 1; compare < count; compare++)

                   if (strcmp(array[compare - 1],  array[compare])>0)
                   {
                        swapString (&array[compare - 1], &array[compare]);
                        swapString (&array2[compare -1], &array2[compare]);
                   }
}

void findDuplicates(char* keys[],char* words[], int& count)
{
      
      for (int keyIndex = 1; keyIndex < count; ++keyIndex)
      {
            if (strcmp(keys[keyIndex -1],  keys[keyIndex])==0)
            {
                  cout << keys[keyIndex] << "  " << words[keyIndex]<< endl;
                  cout << keys[keyIndex-1] << "  " << words[keyIndex-1]<< endl;
            }            
      }
}

void printArray(char* keys[],char* words[], int& count)
{
      cout <<"-----------------------------------------------------" << endl;
      cout <<" Keys array" << endl;
      for (int keyIndex = 0; keyIndex < count; keyIndex++)
            cout << keys[keyIndex] << endl;
}
int main ()
{
      int wordCount;
      char** words = read("c:\\test.txt",wordCount);
      char** keys = arrayCopy(words,wordCount);
      getKeys(keys,wordCount);
      bubbleSortArray(keys,words,wordCount);
      findDuplicates(keys,words,wordCount);
      printArray(keys,words,wordCount);  // for testing my sorts

      system("pause");
      return 0;

}
0
 
Infinity08Commented:
The problem is in the bubble sort algorithm (can't believe I missed that earlier lol) : the inner loop has to count backwards :

void bubbleSortKeys (char *array , int count)
{
      for (int pass =0; pass < count-1; ++pass)
     
             for (int compare = count - 1; compare > pass; --compare)          // <--- go backwards
                   if (array[compare - 1] > array[compare])
                        swapChar (&array[compare - 1], &array[compare]);
}

Same for the bubbleSortArray of course ...
0
 
urobinsAuthor Commented:
Thank you so much for your help I really do appreciate it!
0
 
Infinity08Commented:
No problem. Everything working fine now ?
0
 
urobinsAuthor Commented:
Yep, had to make a few minor adjustments to get my output just right but all of my logic seems sound now.  I really do appreciate it, don't know what I would have done without your help!  Have a great weekend!
0
 
Infinity08Commented:
You too !
0
 
urobinsAuthor Commented:
actually I think I am missing one piece.  how would I go about handling a word showing up more than once?  I don't know if I am I am going to try and test that quick.

0
 
urobinsAuthor Commented:
Actually it looks like it handles it okay, just lists them twice kind of :)  so I think I am all good.  Thanks again!
0
 
Infinity08Commented:
>> Actually it looks like it handles it okay, just lists them twice kind of :)

That's what it does now indeed. If you want to show them only once, then you'll need to add a bit of logic to the loop to check the nextkey, and if it's the same as the current, print it too. Something like this :

        for (i = 1; i < cnt; ++i) {
            if (!strcmp(key[i - 1], key[i])) {
                std::cout << key[i - 1] << " : " << word[i - 1];
                std::cout << ", " << word[i] << std::endl;
                while ((i + 1 < cnt) && !strcmp(key[i], key[i + 1])) {
                    std::cout << ", " << word[++i];
                }
                ++i;
                std::cout << std::endl;
            }
        }

Test, and check for errors before using it, as I just wrote it off the top of my head ;) Also, understand how it works before copying it into your code ...
0
 
urobinsAuthor Commented:
:)  Thanks, I will look at it a bit and see if I can get it to work but at least it does what it needs to so anything else would just be fluff :)

Just out of curiousity what isyour belief on test code?  I had a few functions in there just for testing so I commented out the calls to them but left the code.  Is there a rule of thumb on that type of thing?

-U
0
 
Infinity08Commented:
>> Is there a rule of thumb on that type of thing?

Depends what you want. You can leave the code in there. Just keep one thing in mind : code that is visible to the compiler will be compiled, even if it's never used. That can increase the size of the executable (unless it's optimized out). For assignments like this, that's no problem however.

There are two main ways to make code "invisible" to the compiler :

1) comment it

2) use pre-compiler statements, like :

#ifdef INCLUDE_TEST_CODE
some_test_code();
#endif /* INCLUDE_TEST_CODE */

You can then simply #define INCLUDE_TEST_CODE if you want to include the test code.


However, as I said : for your purposes, there's no problem either way.
0
 
urobinsAuthor Commented:
Thanks!  I appreciate it, I asked my instructor his view and haven't gotten a reply yet so I thought I'd ask someone who actually works with this stuff :)  Thanks again, you'll prob'ly here from me again as I'm gearing up my next project which is a text analyzer.  Again have a good weekend, off to do a research paper now :)
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

  • 28
  • 22
Tackle projects and never again get stuck behind a technical roadblock.
Join Now