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!

std::list

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!

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.

Quote:

---

Originally Posted by samblack

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 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.

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!

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

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.