Thread: pointers and linked lists in place of arrays

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    28

    pointers and linked lists in place of arrays

    So im trying to convert this program, to use pointers and linked list. I really have not done anything with them so im here to ask for help!


    Here to read and pop the array.
    Code:
        // Read names and pop
        for (i=0; i < NUMNAMES; i++)
        {
            // input
            in_stream >> popularity >> boyName >> girlName;   
            // store all data in array
            boyNames[i] = boyName;
            girlNames[i] = girlName;   
        }
        in_stream.close();
    Here is my array for search

    Code:
        // Search for name in arrays
        boyPopularity = -1;
        girlPopularity = -1;
        
        for (i=0; i < NUMNAMES; i++)
        {
            if (boyNames[i] == targetName)
            {
                  boyPopularity = i+1;          
            }
            if (girlNames[i] == targetName)
            {
                  girlPopularity = i+1;
            }
        }
    Here is my output, would i need to rewrite this completely for use with pointers and linked lists?
    Code:
        // Output results if matched
        cout << targetName << " is ";
        if (boyPopularity > 0)
        {
        cout << "ranked " << boyPopularity << " in popularity among boys.\n";
        }
        
        else
        {
            cout << "not ranked among the top 1000 boy names.\n";
        }
        cout << targetName << " is ";
        if (girlPopularity > 0)
        {
            cout << "ranked " << girlPopularity << " in popularity among girls.\n";
        }
        else
        {
            cout << "not ranked among the top 1000 girl names.\n";
        }
        system("PAUSE");
        return 0;
    }
    So really im not sure what to do to start ive never used pointers before and would like some help converting what i have, thanks!

  2. #2
    Registered User
    Join Date
    Apr 2008
    Posts
    890

  3. #3
    Registered User
    Join Date
    May 2008
    Posts
    4
    Forgive me as I'm more of a C coder and am learning C++ but here's a quick side-by-side of arrays vs. linked lists:

    Array (using chars for example)

    Code:
    char charArr[] = "Test String";
    int i = 0;
    for(i=0;i<11;i++){ cout << "char " << i << "is " << charArr[i] << endl; }

    Same thing in a linked list: (It's more complicated as we need to define the data structure, populate the list, use the list, and then free the memory we populated)
    Code:
    // Define the data structure
    typedef struct _charStruct {
      char c;
      struct _charStruct *next;
    } charStruct;
    
    // populate the data structure
    char str[] = "Test String";
    int i = 0;
    charStruct *firstCharStruct = NULL;
    charStruct *ptr = NULL;
    charStruct *new = NULL;
    
    for(i=0; i<11;i++){
      new = malloc(sizeof(charStruct));
      new->c = str[i];
      new->next = NULL;
      if(ptr){
        ptr->next = new;
      }
      ptr = new;
      if(!firstCharStruct){ firstCharStruct = new; }
    }
    
    // Now that it's populated, loop through it and print each character
    for(ptr=firstCharStruct;ptr;ptr=ptr->next){
      cout << "Character: " << ptr->c << endl;
    }
    
    // We also need to delete the dynamically allocated memory:
    ptr = firstCharStruct;
    while(ptr){
      new = ptr; // Might as well re-use the new pointer we declared before
      ptr = ptr->next; //pointer will eventually hit the last member of the list whose "next"
                                // member will be NULL, ending the loop
      free(new);
    }

    Yes, the code for linked lists is more complicated but linked lists are great for lists of complex data structures of unknown variable sizes. For very simple or static things they are total overkill.

    If your code already works, why are you trying to map it to linked lists?

    In any event, sorry for all the code. I hope that helps!

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you are asking for the best way to tackle this task, then no, implementing your own linked list is not a good idea (unless you really want to practice writing a linked list).

    Rather you might use a std::vector (which is essentially an array, but you can add as many items to it as you like) to store the names, or you might try a std::map<std::string, int> to store both the name and the popularity together. map provides faster lookups for this kind of task.


    However, an area where you might improve your code is doing away with repetitious code. As it is, there is separate code for boy and girl names, yet the only difference between them is the array they work with and the fact that one uses a literal noun "boy" where the other has "girl".

    If you used a 2-element array that holds the list of boy and the list of girl names, and perhaps a 2-string array that holds the strings "boy" and "girl", you might be able to let a loop handle the repetitions.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by samblack View Post
    Forgive me as I'm more of a C coder and am learning C++ but here's a quick side-by-side of arrays vs. linked lists:

    Code:
    // Define the data structure
    typedef struct _charStruct {
      char c;
      struct _charStruct *next;
    } charStruct;
    
    // populate the data structure
    char str[] = "Test String";
    int i = 0;
    charStruct *firstCharStruct = NULL;
    charStruct *ptr = NULL;
    charStruct *new = NULL;
    
    for(i=0; i<11;i++){
      new = malloc(sizeof(charStruct));
      new->c = str[i];
      new->next = NULL;
      if(ptr){
        ptr->next = new;
      }
      ptr = new;
      if(!firstCharStruct){ firstCharStruct = new; }
    }
    
    // Now that it's populated, loop through it and print each character
    for(ptr=firstCharStruct;ptr;ptr=ptr->next){
      cout << "Character: " << ptr->c << endl;
    }
    
    // We also need to delete the dynamically allocated memory:
    ptr = firstCharStruct;
    while(ptr){
      new = ptr; // Might as well re-use the new pointer we declared before
      ptr = ptr->next; //pointer will eventually hit the last member of the list whose "next"
                                // member will be NULL, ending the loop
      free(new);
    }
    That is neither C++ code, nor C code and cannot compile as either one. ('new' cannot be used as a variable name in C++, and 'cout' cannot be used in C)

    For a list in C++ you use std::list.
    If you want to implement your own linked list then you're best getting a book or other reference source, possibly a web tutorial, and writing your own as you learn from it. Copying someone else's from here wont teach you how to do it, and it may teach you bad habbits.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Mar 2008
    Posts
    28
    My goal here is to convert this into a linked list, I really am trying to understand all the different aspects, and this is what im trying to learn right now. This is why i was asking specifically for linked list.

    Its not that i wish to copy but gain ideas on how to implment it, with the same sort of basis that i used on the arrays.

  7. #7
    Registered User
    Join Date
    Mar 2008
    Posts
    28
    Okay i need some help, with my original code using arrays i got this:

    Code:
    Enter the first name, to see popularity:
    Justice
    
    Justice is ranked 406 in popularity among boys.
    Justice is ranked 497 in popularity among girls.
    Press any key to continue . . .
    Now my new code i want it to do the same thing.
    Heres what i have so far.
    Code:
    	bool terminate = false;
    	while (!terminate)
    	{
    		cout << "Please enter a name or type 'done' to finshes searching.\nName: ";
    		string target;
    		cin  >> target;
    		
    		tempPtr = topList;
    
    		while ((tempPtr->boysName != target) && (tempPtr->girlsName != target) &&
    			(tempPtr->link != NULL))
    		{
    			tempPtr = tempPtr->link;
    		}
    		
    		if (target == "done")
    			terminate = true;
    			
    		
    		else if (tempPtr->boysName == target)
    		{
    			cout << target << " is ranked " << tempPtr->rank << " among boys' names.\n" << endl;
            }
            
        	else if (tempPtr->girlsName == target)
        	{
                 
    			cout << target << " is ranked " << tempPtr->rank << " among girls' names.\n" << endl;
            }
    		else
    			cout << "baby name not found in databaase\n" << endl;
    	}
    Obviously right now it outputs the last found name and displays its rank. But i need to have it search the list for boys names first display, then clear, and search again for girls. This is only using linked lists and pointers.

    Thanks!

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If you are planning to search for "names that can be both boys and girls", then you could solve that by keeping track of "boy" and "girl" pointers, so when you find the name, either boy or girl, then you store that in "boy" or "girl" pointer, then continue until you've either found the end of the list or both boy and girl names.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Mar 2008
    Posts
    28
    How would i make it continue i can only seem to get it to go all the way through and used the last one it found.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with linked lists/ pointers
    By anything25 in forum C Programming
    Replies: 14
    Last Post: 06-26-2009, 02:41 PM
  2. Pointers to pointers in linked lists
    By G4B3 in forum C++ Programming
    Replies: 2
    Last Post: 07-23-2008, 03:54 AM
  3. Double pointers and linked lists.
    By simo_r in forum C Programming
    Replies: 2
    Last Post: 05-06-2008, 04:25 AM
  4. Linked Lists & Pointers
    By fkheng in forum C Programming
    Replies: 4
    Last Post: 06-10-2003, 07:26 AM
  5. Problem with pointers and linked lists
    By bsimbeck in forum C Programming
    Replies: 2
    Last Post: 02-21-2003, 11:05 AM

Tags for this Thread