Searching a Linked List.

Question

mcap61 0 Newbie Poster

16 Years Ago

Hey guys,
I have to write a program to check the ranking of the top 1000 boy and girl baby names using linked lists and pointers.

The POINT of the PROGRAM is if you enter a name it will tell you what the name ranks among the list if it is ranked at all.

Result cout should look like this.
Jacob is ranked #1 in popularity among boys.
Jacob is not ranked in the top 1000 girl names.

My problem is in my void check_name() function... the function that checks if the name is in the list and then displays it as well. When the program runs for some reason it only works for the first set of names (the #1 boy and girl) but in an infinite loop.

I have based most of my work off a tutorial from this website

And here is the link to the list of names. You probably have to save it to a file named babynames2004.txt for the program to work.

Sorry if this is confusing Ive been working on this program for way too long.

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

struct name
       { int rank;
         string boy_name;
         string girl_name;
         name *nxt;
         };
         
name *start_ptr = NULL;
name *current;

void add_names();
void check_name();

string enter_name;

int main()
{
    start_ptr = new name;
    cout << "Please enter a first name to see its ranking" << endl;
    cout << "among the top 1000 baby names." << endl;
    cin >> enter_name;
    cout << endl;
    add_names();
    
    system("PAUSE");
    return 0;
}

    

void add_names()
{   //name *temp, *temp2;
    //temp = new name;
    name * prior = new name;// * temp;
    int ranking;
    int i=0;
    string male_name, female_name;
    ifstream in_stream("babynames2004.txt");
    
    //in_stream.open; //opens and loads names & ranks from file
    if (in_stream.fail())
   {
    cout << "File failed to open." << endl;
    cout << "Program will now close." << endl;
    system("PAUSE");
    exit(0);
   }
    
    in_stream >> ranking>> male_name >> female_name;
	
    
    prior = start_ptr;
    prior->rank = ranking;

    prior->boy_name = male_name;
    prior->girl_name = female_name;
    prior->nxt = NULL;
    
    name *temp;
	while(in_stream >> ranking >> male_name >> female_name)
    {
    
    temp = new name;
    prior->nxt = temp;
    
    temp->rank = ranking;
    temp->boy_name = male_name;
    temp->girl_name = female_name;
    temp->nxt = NULL;
    prior = temp;
    
    }
    temp->nxt = NULL;
}

void check_name()
{   name *strt;
    strt = start_ptr;
    cout << endl;
          
          for (name * strt = start_ptr;strt->nxt !=NULL;strt=strt->nxt)
          {      
            if (enter_name == strt->boy_name && enter_name != strt->girl_name)
            {
                cout << enter_name << " is ranked #" << strt->rank;
                cout << " in popularity among boys.\n" << endl;
               }
            else (enter_name != strt->boy_name && enter_name != strt->girl_name) 
            {
                 cout << enter_name << " is not ranked among the";
                 cout << " top 1000 boy names." << endl;
                 }
            if (enter_name == strt->girl_name && enter_name != strt->boy_name)
            {
                cout << enter_name << " is ranked #" << strt->rank;
                cout << " in popularity among boys.\n" << endl;
               }
            else (enter_name != strt->girl_name && enter_name != strt->boy_name)
            {
                cout << enter_name << " is not ranked among the";
                cout << " top 1000 girl names." << endl << endl;
                }
          }
}

c++ linked-list

Edited 16 Years Ago by mcap61 because: n/a

4 Contributors
8 Replies
407 Views
7 Hours Discussion Span
Latest Post 16 Years Ago Latest Post by programmersbook

Dani AI

Generated 9 Months Ago

Brief diagnosis (why the loop only handles the first entry and behaves oddly)

The traversal condition in the search loop uses node->nxt != NULL instead of node != NULL, so the final node is never checked.
The function prints “not ranked” inside the loop on every iteration, producing repeated output (or appears to hang). Output must be done once after the full search.
The posted code redeclares/hides strt and mixes responsibilities; splitting “find” and “display” removes that confusion (as suggested).
There are copy/paste errors (the girl case prints “boys”) and a stray temp->nxt = NULL after the loop that can dereference an uninitialized pointer if the file has only one line.
’s suggestion to use STL is sound for real work, but for a pointer/linked-list assignment the fixes below are the safer route.

Minimal, safe approach (find + report)

Implement a small finder that walks nodes until NULL, returning the node and which side matched:

name * find_name(const string &key, bool &matchedBoy, bool &matchedGirl)
{
    matchedBoy = matchedGirl = false;
    for (name *cur = start_ptr; cur != NULL; cur = cur->nxt) {
        if (cur->boy_name == key) matchedBoy = true;
        if (cur->girl_name == key) matchedGirl = true;
        if (matchedBoy || matchedGirl) return cur;
    }
    return NULL;
}

After construction, call the finder once and print results only once (use separate messages for boys/girls and correct labels). For case-insensitive search, compare lowercased copies of both strings.

Quick checklist to fix add_names and avoid UB

Initialize pointers to NULL; don’t allocate a node then immediately overwrite its pointer.
Build the list with a head/tail pattern so tail->nxt is set exactly once when a new node is appended.
Remove any temp->nxt = NULL that runs when temp may be uninitialized.
Verify the list by printing the first and last node after load, then run the finder.

This follows ’s split-function advice and keeps the linked-list solution required by the assignment while avoiding the common pointer/loop pitfalls discussed above.

All 8 Replies

programmersbook 17 Junior Poster

16 Years Ago

Hi!

Sorry the doesnt work.

I think you should use std::list, and no pointers if it's not neccessary! It will make your wile easier ;)

jonsca 1,059 Quantitative Phrenologist

16 Years Ago

It's :
(I helped him on the other post -- mcap, I think you got the abbreviated URL when you cut and pasted)

I think you should use std::list, and no pointers if it's not neccessary!

We can probably do some "duck typing" (go against the C++ grain for a second) on it and find it's an assignment

Edited 16 Years Ago by jonsca because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

mcap61 0 Newbie Poster · Answer 1 · 2009-12-12T03:40:35+00:00

sorry here is the link

mcap61 0 Newbie Poster · Answer 2 · 2009-12-12T03:43:51+00:00

oh yeah and one more thing...
The assignment was we are supposed to use pointers and linked lists. But at this point I just want this program to work so yea I'll give std::list a try.

nezachem 616 Practically a Posting Shark · Answer 3 · 2009-12-12T04:00:24+00:00

My problem is in my void check_name() function... the function that checks if the name is in the list and then displays it as well. When the program runs for some reason it only works for the first set of names (the #1 boy and girl) but in an infinite loop.
void check_name()
{   name *strt;
    strt = start_ptr;
    cout << endl;
          
          for (name * strt = start_ptr;strt->nxt !=NULL;strt=strt->nxt)
          {      
                if (enter_name == strt->boy_name && enter_name != strt->girl_name) {}
                // etc
          }
}

In this code, the next search starts from the point where the previous search ended. You need to start each search from the very beginning of the list.

This mistake stems from the wrong design decision: the function that checks if the name is in the list and then displays it as well is a bad function. Split the functionality into "find the record" and "display the (found) record".

programmersbook 17 Junior Poster · Answer 4 · 2009-12-12T04:04:20+00:00

i would do it like this: no pointers, better to understand.

mcap61 0 Newbie Poster · Answer 5 · 2009-12-12T04:31:41+00:00

thanks for that programmersbook,
i understand that way better than what i have now, but I still have to use a linked list with pointers.

how would you change the 'for' expression so that it starts at the beginning of the list everytime? i thought i had it with strt=strt->next... guess not.

programmersbook 17 Junior Poster · Answer 6 · 2009-12-12T04:46:05+00:00

i see, well when i will do it like this:

void check_name()
{   name *strt;
    strt = start_ptr;
    cout << endl;
          
          for (name * strt = start_ptr;strt->nxt !=NULL;strt=strt->nxt)
          {      
          
            if (enter_name == strt->boy_name )
            {
                cout << enter_name << " is ranked #" << strt->rank;
                cout << " in popularity among boys.\n" << endl;
                break;
            }
            else if (enter_name == strt->girl_name) 
            {
                 cout << enter_name << " is ranked #" << strt->rank;
                cout << " in popularity among boys.\n" << endl;
                 break;
                              
            }
          }
    cout << enter_name << " is not ranked among the";
      cout << " top 1000 names." << endl;
}

call check_name() after add_names();

Full code:

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

struct name
       { int rank;
         string boy_name;
         string girl_name;
         name *nxt;
         };
         
name *start_ptr = NULL;
name *current;

void add_names();
void check_name();

string enter_name;

int main()
{
    start_ptr = new name;
    cout << "Please enter a first name to see its ranking" << endl;
    cout << "among the top 1000 baby names." << endl;
    cin >> enter_name;
    cout << endl;
    add_names();
    check_name();
    
    system("PAUSE");
    return 0;
}

    

void add_names()
{   //name *temp, *temp2;
    //temp = new name;
    name * prior = new name;// * temp;
    int ranking;
    //int i=0;
    string male_name, female_name;
    ifstream in_stream("babynames2004.txt");
    
    //in_stream.open; //opens and loads names & ranks from file
    if (in_stream.fail())
   {
    cout << "File failed to open." << endl;
    cout << "Program will now close." << endl;
    system("PAUSE");
    exit(0);
   }
    
    in_stream >> ranking>> male_name >> female_name;
	
    
    prior = start_ptr;
    prior->rank = ranking;

    prior->boy_name = male_name;
    prior->girl_name = female_name;
    prior->nxt = NULL;
    
    name *temp;
	while(in_stream >> ranking >> male_name >> female_name)
    {
    
    temp = new name;
    prior->nxt = temp;
    
    temp->rank = ranking;
    temp->boy_name = male_name;
    temp->girl_name = female_name;
    temp->nxt = NULL;
    prior = temp;
    
    }
    temp->nxt = NULL;
}

void check_name()
{   name *strt;
    strt = start_ptr;
    cout << endl;
          
          for (name * strt = start_ptr;strt->nxt !=NULL;strt=strt->nxt)
          {      
          
            if (enter_name == strt->boy_name )
            {
                cout << enter_name << " is ranked #" << strt->rank;
                cout << " in popularity among boys.\n" << endl;
                break;
            }
            else if (enter_name == strt->girl_name) 
            {
                 cout << enter_name << " is ranked #" << strt->rank;
                cout << " in popularity among boys.\n" << endl;
                 break;
                              
            }
          }
    cout << enter_name << " is not ranked among the";
      cout << " top 1000 names." << endl;
}

Saved my a$$. Thanks for your help, I wish i could return the favor.

Searching a Linked List.

Dani AI

Recommended Answers Collapse Answers

All 8 Replies

Recommended Answers