Like Tree1Likes
  • 1 Post By quzah

Need help organizing an array of string, it has to be my teachers way.

This is a discussion on Need help organizing an array of string, it has to be my teachers way. within the C++ Programming forums, part of the General Programming Boards category; Well here is our assignment. Code: rite a C++ program that will build a Word Concordance for a series of ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    67

    Need help organizing an array of string, it has to be my teachers way.

    Well here is our assignment.

    Code:
    rite a C++ program that will build a Word Concordance for a series of text lines. A Concordance is basically an index of 
    words in a document, and a listing of their context (line numbers).
    
    Then the program should read a series of lines of input from cin and keep track of the words that appear on the lines, and
     the line numbers of where those words appear in the input stream. Upon completing the processing of the input, the 
    program should display an alphabetized listing of the words that were found, one word per line, and next to each word 
    will be a list of line numbers of where that word was found in the input.
    A word, for the purpose of this program, is defined as a series of non-blank characters, with leading and trailing punctuation characters
    (-,.;:?"'!@#$%^&*[]{}|) removed (note that embedded punctuation characters, such as Bob's and ten-thirty should be left in the word). 
    The words are to be saved without case-sensitivity; for example: Concordance ConCorDance CONCORDance concordance are all to be considered the same word.
    
    The words are to be stored in a statically-declared array. You can assume that the maximum number of unique words that will be submitted is 200.
     The words are to be stored in the array in sorted order, and you are to use the array-based binary search method as described in our course notes to locate words in the array.
    
    For each word in the array, the list of line numbers is to be maintained by using a Linked-List Queue data structure, similar to what you used for Program 4. 
    Although the Queue isn't necessarily the most-appropriate data structure for this job, based on what we've already done with it, it should provide a simple interface to use.

    and here is my code
    Code:
    #include <iostream>
    #include <cstdlib>
    #include <sstream>
    
    
    
    using namespace std;
    
    
    struct WORD{
      string word;
      int line;
    }aword[200];
    
    int binarySearch (string sortedArray[], int first, int last, string key)
    {
      while (first <= last) {
        int mid = (first + last) / 2;  // compute mid point.
        if (key > sortedArray[mid])
          first = mid + 1;  // repeat search in top half.
        else if (key < sortedArray[mid])
          last = mid - 1; // repeat search in bottom half.
        else
          return mid;     // found it. return position
        }
      return -(first + 1);    // failed to find key
    } // end binarySearch
    
    
    int main() {
    
      istringstream strLine;
      string line, word;
      int currentLine=0;
      int i=0;
    
      while (getline(cin,line)) {
        ++currentLine;
        
        // clear the strstream and copy the entered line to it
        strLine.clear();
        strLine.str(line);
    
        // now get each word-sequence from the strLine stream
         while (strLine >> word)
         {
           //cout << currentLine << ": " << word << endl;
           aword[i].word=word;
           aword[i].line=currentLine;
           i++;
         }
        }
        for(i=0;aword[i].word!=""; i++)
        {
          cout<<aword[i].word<<endl;
          
        } 
    
    // _________________________________
    
       string word26[]={"a","f","j","z"};
       int sizeValues = sizeof(word26) / sizeof (string);
    
      for(int counter=0;counter<i;counter++)
      {
        cout << "Searching for " << aword[counter].word<< ": ";
        int index = binarySearch(word26,0,sizeValues-1,aword[counter].word);
      
        if (index >=0)
          cout << "FOUND " << aword[counter].word << " in position " << index;
        else{
          cout << "Did not find " << aword[counter].word << "; it should go in position "
          << (-index-1);
          //word26[-index-1]=aword[counter].word;
        }
        cout << endl << endl;
      }
      
      return 0;
      
    }//end main
    I created a second array word26[] and used to tell me where the values on my structure should go. but i'm stuck.

    here is the output I get.

    Code:
    a
    is
    b
    car
    house
    zeus
    
    Searching for a: FOUND a in position 0
    
    Searching for is: Did not find is; it should go in position 2
    
    Searching for b: Did not find b; it should go in position 1
    
    Searching for car: Did not find car; it should go in position 1
    
    Searching for house: Did not find house; it should go in position 2
    
    Searching for zeus: Did not find zeus; it should go in position 4

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    1) When they say a queue, I imagine they mean a queue; "int line" is not a queue.

    2) You need to add words to your array. You have code to start this process but you have commented it out. Note that if you need to insert into the middle of an array, that will involve moving all the later elements down one spot in your array.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    67
    Quote Originally Posted by tabstop View Post
    1) When they say a queue, I imagine they mean a queue; "int line" is not a queue.

    2) You need to add words to your array. You have code to start this process but you have commented it out. Note that if you need to insert into the middle of an array, that will involve moving all the later elements down one spot in your array.
    about question one. yes I will add them to a queue latter on.

    Question #2) since
    Code:
    string word26[]={"a","f","j","z"};
    has been declared like this can I really add more strings to it. What do you think my teacher means by using the binary search to sort the items, because that is where I can not understand what he really means.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by newbc View Post
    Question #2) since
    Code:
    string word26[]={"a","f","j","z"};
    has been declared like this can I really add more strings to it.
    That cannot have any more strings added to it, no. That's why you're not supposed to do that. That is why you built an array of 200 WORDS at the top of your program. Use that.
    What do you think my teacher means by using the binary search to sort the items, because that is where I can not understand what he really means.
    He doesn't. He doesn't say you should, and you don't. He says you should use binary search to locate items in the array, which is fine because that is what the word "search" means. Now binary search can (and this implementation of it does) tell you where, if something isn't found, it would be if it were there. But searching does not put the data in the array; that is your job. You can use the information provided to you by the search function to save yourself a bit of work (i.e., re-locating the insertion point), but it is up to you to do the inserting.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    67
    can someboy tell me why my while loop will not exucte in the red text.

    Code:
    //test sample code
    //
    
    
    #include <iostream>
    #include <cstdlib>
    #include <sstream>
    
    
    
    using namespace std;
    
    
    struct WORD{
      string word;
      int line;
    }aword[200];
    
    int binarySearch (string sortedArray[], int first, int last, string key)
    {
      while (first <= last) {
        int mid = (first + last) / 2;  // compute mid point.
        if (key > sortedArray[mid])
          first = mid + 1;  // repeat search in top half.
        else if (key < sortedArray[mid])
          last = mid - 1; // repeat search in bottom half.
        else
          return mid;     // found it. return position
        }
      return -(first + 1);    // failed to find key
    } // end binarySearch
    
    
    int main() {
    
      istringstream strLine;
      string line, word;
      int currentLine=0;
      int i=0;
      int wordsToprocess=0;
    
      while (getline(cin,line)) {
        ++currentLine;
        
        // clear the strstream and copy the entered line to it
        strLine.clear();
        strLine.str(line);
    
        // now get each word-sequence from the strLine stream
         while (strLine >> word)
         {
           //cout << currentLine << ": " << word << endl;
           aword[i].word=word;
           aword[i].line=currentLine;
           i++;
         }
        }
    wordsToprocess=i;
    cout<<wordsToprocess<<endl;
    
        for(i=0;i<wordsToprocess; i++)
        {
          cout<<aword[i].word<<endl;
          
        } 
    
    // _________________________________
    
       string word26[wordsToprocess];
       int counter2;
    
    
    
       int sizeValues = sizeof(word26) / sizeof (string);
    
      for(int counter=0;counter<wordsToprocess;counter++)
      {
        cout << "Searching for " << aword[counter].word<< ": ";
        int index = binarySearch(word26,0,sizeValues-1,aword[counter].word);
      
        if (index >=0)
        {
          cout << "FOUND " << aword[counter].word << " in position " << index;
        }
        index=-index-1;
    
        if(index+1>wordsToprocess && word26[wordsToprocess-1]=="")
        {
          word26[index-1]=aword[counter].word;
        }//end if
    
    
       if(index+1>wordsToprocess && word26[1]!="")
       {
          counter2=index-1;
    
         while( word26[counter2]!="")
         {
          counter2--;
         }//end while
    
         while(counter2<index-1)
         {
         word26[counter2]=word26[counter2+1];
         counter2++;
         }
    
         word26[index-1]=aword[counter].word;
    
       }//end if
    
       
        cout << endl << endl;
      }
      
    
        for(i=0;i<wordsToprocess; i++)
        {
          cout<<word26[i]<<"..."<<endl;
          
        } 
    
    
      return 0;
      
    }//end main
    ok im trying to sort 5 words in a new array.

    I just started with five words, for example:

    house is red

    is adds house but it does not add the second word which is (is) and it has something
    to do with the while loops in red text.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You are always doing index = -index-1. That might be deliberate (turning "found" into "negative"), but who knows?

    This statement
    Code:
    index+1>wordsToprocess
    is syntactically impeccable and utterly meaningless. What value is there in comparing index (which is either negative if the word was found or positive if it was not) with wordsToprocess, which is the number of words typed in by the user? You seem to be using index as both the result value of your search and the number of words in your array, all at the same time. It cannot be both; you must choose one, and then create another variable for the other. (And for that matter, even if index was the number of words in your array, that still wouldn't help one tiny bit, as there is no reason for index and wordsToprocess to be even slightly related at any time.)

  7. #7
    Registered User
    Join Date
    Nov 2010
    Posts
    67
    Quote Originally Posted by tabstop View Post
    You are always doing index = -index-1. That might be deliberate (turning "found" into "negative"), but who knows?

    This statement
    Code:
    index+1>wordsToprocess
    is syntactically impeccable and utterly meaningless. What value is there in comparing index (which is either negative if the word was found or positive if it was not) with wordsToprocess, which is the number of words typed in by the user? You seem to be using index as both the result value of your search and the number of words in your array, all at the same time. It cannot be both; you must choose one, and then create another variable for the other. (And for that matter, even if index was the number of words in your array, that still wouldn't help one tiny bit, as there is no reason for index and wordsToprocess to be even slightly related at any time.)
    im just lost and out of ideas my plan for this was create an array with empty strings (""). and start adding the words in the end of the array that is why I did
    if(index+1>wordsToprocess && word26[1]!="")

    beaucuse since the string was empty it will say that I need to put it one space value after my are values: like if I had 100 empty strings it will say to put it in the 101 space.
    the is what the > wordsToprocces checks then word26(1) is not "" made sure the last item was empty so I can add the first word there but now I don't know what to do.

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    my plan for this was create an array with empty strings (""). and start adding the words in the end of the array
    Then you've already driven off the cliff. You need to build the list in sorted order. As words come in, if they are not found (i.e. when index comes up negative), you need to put the word in the right spot. This also means you need to keep track of how many words are already in the array, because you need to pass that to binarysearch (in other words, sizeValues - 1 is NOT NOT NOT what goes there).

  9. #9
    Registered User
    Join Date
    Nov 2010
    Posts
    67
    Quote Originally Posted by tabstop View Post
    Then you've already driven off the cliff. You need to build the list in sorted order. As words come in, if they are not found (i.e. when index comes up negative), you need to put the word in the right spot. This also means you need to keep track of how many words are already in the array, because you need to pass that to binarysearch (in other words, sizeValues - 1 is NOT NOT NOT what goes there).
    let me just ask you the last set of questions after this I promise I won't ask you anymore.

    you said "build the list in sorted order. " what do you mean by already being sorted, and are you talking about the first array when I take in the user input or the array word26?

    do you not want me to put (in other words, sizeValues - 1 ) in the array im looking for? isn't that the size of the array, that im the looking for the words? thats what I understood from my teacher.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You need to build the list in sorted order, not build the list in any old way and then sort it later. Do not put all the new words at the beginning, or the end. As you get a new word, put it in its proper place in the list.

    You do not put the size of the physical array in your binarysearch function. You put the size of the array as it actually is; that is, how much of it you have filled. If you only have words in slots 1 through 12, don't tell your binary search to search through all 200 spots.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by newbc View Post
    can someboy tell me why my while loop will not exucte
    Because the truth test fails.
    Name:  200px-Trollface.png
Views: 794
Size:  16.9 KB


    Quzah.
    AndrewHunter likes this.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Any teachers here?
    By John_ in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 02-15-2006, 06:03 PM
  2. Best way of organizing.
    By jrahhali in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2003, 07:50 PM
  3. Teachers code aint right
    By RoD in forum C++ Programming
    Replies: 20
    Last Post: 03-16-2003, 08:13 AM
  4. Verbal abuse from school teachers -- how to get them caught or busted?
    By deltabird in forum A Brief History of Cprogramming.com
    Replies: 17
    Last Post: 02-13-2003, 06:26 AM
  5. My teachers are so thick!!
    By face_master in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 12-14-2002, 12:49 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21