How do you search for a specific string in a linked list and return that value?

Viewed 215

I have a program that takes in input with 5 parameters. The inputs are video title, url, comment, length, and rating. Then sorts them based on title. The user will need to specify insert (to enter the video information), lookup (look up a video by title and print ONLY that video and its information associated with it), or print (just simply print everything).

for example

input:

insert
Arthur Benjamin: Lightning calculation and other "Mathemagic"
http://www.youtube.com/watch?v=M4vqr3_ROIk
Hard to believe.
15.25  
4  
lookup  
Arthur Benjamin: Lightning calculation and other "Mathemagic"

output:

Arthur Benjamin: Lightning calculation and other "Mathemagic" , http://www.youtube.com/watch?v=M4vqr3_ROIk, Hard to believe., 15.25, 4

my problem is dealing with lookup in main

if(user == "lookup")
        {
            getline(cin, title);
            if(vlistObj -> lookup(videoObj))
            {
                vlistObj->print();
            }
        }

and also lookup in my linked list

bool Vlist::lookup(Video *other)
{
  Node *node = m_head;
  return node->m_next -> m_video->GetTitle() == other-> GetTitle();
}

I am honestly very lost on how to make lookup search for a specific title (assuming lots of video title/info has been given) and only print what I ask (assuming it's in the list).

Here is the complete code:

#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;

class Video {

  public:
    Video(string video_title, string video_link, string video_comment, double video_length, int video_number);
    void print();
    const string& GetTitle() const { return title; }

  private:

    std::string title;
    string link;
    string comment;
    double length;
    int rating;

};


Video::Video(string video_title, string video_link, string video_comment, double video_length, int video_number)
  : title(video_title), link(video_link), comment(video_comment), length(video_length), rating(video_number)
{
}

void Video::print(){

  cout << title << ", " << link << ", " << comment << ", " << length << ", " << rating << endl;

}


class Vlist {
 public:
  Vlist() {m_head = nullptr; }
  bool lookup(Video *other);
  void Insert(Video *video);
  void print();
 private:
 class Node {
        public:
                Node(Video *video, Node *next) {m_video = video; m_next = next; }
                Video *m_video;
                Node *m_next;
            };
            Node *m_head;
 };


void Vlist::Insert(Video* video)
{
    if (m_head == NULL || m_head->m_video -> GetTitle() > video->GetTitle())
    {
        m_head = new Node(video, m_head);

    }
    else
    {
        Node *node = m_head;
        while (node->m_next != NULL && node->m_next -> m_video->GetTitle() < video->GetTitle())
        {
            node = node->m_next;
        }
        node->m_next = new Node(video, node->m_next);
    }
 }

bool Vlist::lookup(Video *other)
{
  Node *node = m_head;
  return node->m_next -> m_video->GetTitle() == other-> GetTitle();
}

 void Vlist::print()
 {
     Video *video;
     Node *node = m_head;

     while(node != NULL)
     {
        node -> m_video-> Video::print();
        node = node->m_next;
     }
 }


int main()
{
  string sort_type, url, comment, title, user;
    int rating;
    double length;
    int initial = 0, last = 0, number;

    Vlist *vlistObj= new Vlist();
    Video *videoObj;

    while (getline(cin,user)) {

        if(user == "insert")
        {
        getline(cin,title);
        getline(cin, url);
        getline(cin, comment);
        cin >> length;
        cin >> rating;
        cin.ignore();

        videoObj = new Video(title,url, comment, length, rating);
        vlistObj->Insert(videoObj);
        }

        if(user == "lookup")
        {
            getline(cin, title);
            if(vlistObj -> lookup(videoObj))
            {
                vlistObj->print();
            }
        }
        if(user == "print")
        {
            vlistObj->print();
        }
    }

}

Also I do want to note that I am receiving a segmentation fault. But I do know that it is because of my code in lookup. The program runs and output correctly if I do not type lookup

2 Answers

Error is in the Vlist::lookup function, where the current node pointer points to m_next which then points to m_video: m_next is not required, m_head should point directly to m_video.

Here below the complete working code, I also changed something here and there to eliminate all warnings from my compiler

#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;

class Video {

  public:
    Video(string video_title, string video_link, string video_comment, double video_length, int video_number);
    void print();
    const string& GetTitle() const { return title; }

  private:

    string title;
    string link;
    string comment;
    double length;
    int rating;

};


Video::Video(string video_title, string video_link, string video_comment, double video_length, int video_number)
  : title(video_title), link(video_link), comment(video_comment), length(video_length), rating(video_number)
{
}

void Video::print(){

  cout << title << ", " << link << ", " << comment << ", " << length << ", " << rating << endl;

}


class Vlist {
 public:
  Vlist():m_head(nullptr) {}     // init_list
  bool lookup(const string& title);  // gets user input directly
  void Insert(Video *video);
  void print();
  Video* get(const string& title);   // new:returns pointer in list with given title
 private:
 class Node {
        public:
                Node(Video *video, Node *next):m_video(video), m_next(next) {}   // init_list
                Video *m_video;
                Node *m_next;
            } *m_head;    // declared directly together with class definition
 };


void Vlist::Insert(Video* video)
{
    if (m_head == NULL || m_head->m_video -> GetTitle() > video->GetTitle())
    {
        m_head = new Node(video, m_head);
    }
    else
    {
        Node *node = m_head;
        while (node->m_next != NULL && node->m_next -> m_video->GetTitle() < video->GetTitle())
        {
            node = node->m_next;
        }
        node->m_next = new Node(video, node->m_next);
    }
 }

bool Vlist::lookup(const string& title)
{
  Node *node = m_head;
  while (node->m_next != NULL && node-> m_video->GetTitle() != title)
  {
    node = node->m_next;
  }

  return node-> m_video->GetTitle() == title; // there was one pointer too many here
}

 void Vlist::print()
 {
     Node *node = m_head;

     while(node != NULL)
     {
        node -> m_video-> Video::print();
        node = node->m_next;
     }
 }

Video* Vlist::get(const string& title) // returns required item from list
{
    Node *node = m_head;
    while (node != NULL) {
        if (node->m_video->GetTitle() == title)
            return node->m_video;
        node = node->m_next;
    }

return nullptr;
}


int main()
{
  string sort_type, url, comment, title, user;
    int rating;
    double length;

    Vlist *vlistObj= new Vlist;
    Video *videoObj;

    while (getline(cin,user)) {

        if(user == "insert")
        {
        getline(cin,title);
        getline(cin, url);
        getline(cin, comment);
        cin >> length;
        cin >> rating;
        cin.ignore();

        videoObj = new Video(title, url, comment, length, rating);
        vlistObj->Insert(videoObj);
        }

        if(user == "lookup")   // more than a few changes here
        {
            getline(cin, title);

            if (vlistObj -> lookup(title))
            {
                videoObj = vlistObj->get(title);
                videoObj->print();
            } else {
                cout << "not found!\n";
            }
        }
        if(user == "print")
        {
            vlistObj->print();
        }
    }

}

BIG EDIT

Previous version did not traverse the Vlist correctly.

Now Vlist is properly searched by the lookup command, that thus finally prints the correct Video.

Overview

Before looking at the specific issues, your code shows you are struggling with putting all the pieces together and are, in a sense, guessing and not paying particular attention to every line in your code. You can't code by just "trying things and see if it works", that will just make you old, gray and frustrated. Take the time to know just exactly what your next lines of code needs to do, craft the line, and then craft a test to ensure it succeeds (or make friends with gdb and check there -- you indicated you are using g++)

Examples:

#include <iostream>
#include <limits>
// #include <stdlib.h>
// #include <cstring>

What were stdlib.h and cstring included for? And:

void Vlist::print()
{
    // Video *video;        /* unused */

and

    // int initial = 0, last = 0, number = 0;   /* unused */

How is other initialized? If you are passing a pointer to a Video object, that object must at minimum have the title initialized, so GetTitle() returns a meaningful value...

bool Vlist::lookup(Video *other)
{
  Node *node = m_head;
  return node->m_next -> m_video->GetTitle() == other-> GetTitle();
}

That doesn't really make much sense?

Take your time and slow-down, understand what you need to do, and then pick up the keyboard (not the other way around)

Be consistent with your use of syntax. You include std::string in places and then simply string in others relying on using namespace std;. See Why is “using namespace std;” considered bad practice?

Further, under no conditions in C++ is there ever a space surrounding ->. That is an operator that joins an object and its member, with nothing in between.

Specific Issues

It is clear that what you have will not output the Video object that matches a lookup when you are attempting to print a Vlist. (doesn't make much sense to print the entire list in response to finding one title of interest). Your lookup() function cannot return bool, instead it must return a pointer to the node containing the title (if found) or nullptr if not found. That means you must save and validate the return in order to know which Node contains the record you want to print. Within main() that looks like:

        else if (user == "lookup") {
            if (getline(std::cin, title)) {
                videoObj = new Video (title);   /* you must construct a new videoObj */
                Video *video = nullptr;         /* you want a Video* pointer returned */
                if ((video = vlistObj->lookup(videoObj))) { /* lookup & assign return */
                    video->print();             /* output the video, not list */
                }
                else {
                    std::cout << "title not found: '" << title << "'.\n";
                }
            }
        }

Now that videoObj points to a Video object that has title initialized, the lookup() function can do it's job -- returning a pointer to the node within the list that contains that title (and all the rest of the information) or returning nullptr if the title isn't found. (note the else indicating to the user that condition)

A rewrite of lookup() that does just that would be:

Video *Vlist::lookup (Video *other)
{
    Node *node = m_head;
    
    while (node) {  /* iterate over nodes in list looking for title */
        if (node->m_video->GetTitle() == other->GetTitle())
            return node->m_video;           /* return pointer to node if found */
        node = node->m_next;
    }
    return nullptr;                         /* nullptr if not */
}

(Note: simply passing other as std::string makes more sense, but in case you need a Video object -- this is a minimal way to do it)

There were a litany of other cleanups needed, tweaks to initializations, syntax fixes -- removing spaces around ->, etc... that are too numerous to mention. Not to mention to need to ensure you are not leaking memory -- that is left to you (and your properly written destructors) Use valgrind to verify you are freeing all memory before your program exits.

Putting the syntax clean ups and initializations together, you could do something like:

#include <iostream>
#include <limits>

class Video {

  public:
    Video ( std::string video_title, std::string video_link, std::string video_comment, 
            double video_length, int video_number );
    void print();
    const std::string& GetTitle() const { return title; }

  private:
    std::string title {}, link {}, comment {};
    double length;
    int rating;
};


Video::Video ( std::string video_title = "", 
                std::string video_link = "", 
                std::string video_comment = "", 
                double video_length = 0, int video_number = 0)
                : title(video_title), link(video_link), comment(video_comment), 
                length(video_length), rating(video_number)
{
}

void Video::print()
{
    std::cout << title << ", " << link << ", " << comment << ", " << 
                length << ", " << rating << '\n';
}


class Vlist {
    
  public:
    Vlist() { m_head = nullptr; }
    Video *lookup (Video *other);
    void Insert (Video *video);
    void print();
  
  private:
    class Node {
      public:
        Node (Video *video = nullptr, Node *next = nullptr) {
            m_video = video; m_next = next;
        }
        Video *m_video;
        Node *m_next;
    };
    Node *m_head;
};

void Vlist::Insert (Video* video)
{
    if (m_head == nullptr || m_head->m_video->GetTitle() > video->GetTitle()) {
        m_head = new Node (video, m_head);
    }
    else {
        Node *node = m_head;
        while (node->m_next != nullptr &&
                node->m_next->m_video->GetTitle() < video->GetTitle()) {
            node = node->m_next;
        }
        node->m_next = new Node(video, node->m_next);
    }
 }

Video *Vlist::lookup (Video *other)
{
    Node *node = m_head;
    
    while (node) {  /* iterate over nodes in list looking for title */
        if (node->m_video->GetTitle() == other->GetTitle())
            return node->m_video;           /* return pointer to node if found */
        node = node->m_next;
    }
    return nullptr;                         /* nullptr if not */
}

void Vlist::print()
{
    Node *node = m_head;

    while (node != nullptr) {
        node->m_video->Video::print();
        node = node->m_next;
    }
}


int main (void) {
    
    std::string sort_type {}, url {}, comment {}, title {}, user {};
    int rating = 0;
    double length = 0;

    Vlist *vlistObj = new Vlist();
    Video *videoObj = nullptr;

    while (getline(std::cin, user)) {
        if (user == "insert") {
            if (getline (std::cin, title) &&
                getline (std::cin, url) &&
                getline (std::cin, comment) &&
                std::cin >> length &&
                std::cin >> rating) {
                    std::cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');
                    videoObj = new Video (title, url, comment, length, rating);
                    vlistObj->Insert(videoObj);
            }
        }
        else if (user == "lookup") {
            if (getline(std::cin, title)) {
                videoObj = new Video (title);   /* you must construct a new videoObj */
                Video *video = nullptr;         /* you want a Video* pointer returned */
                if ((video = vlistObj->lookup(videoObj))) { /* lookup & assign return */
                    video->print();             /* output the video, not list */
                }
                else {
                    std::cout << "title not found: '" << title << "'.\n";
                }
            }
        }
        else if (user == "print") {
            std::cout << "\nlist content:\n";
            vlistObj->print();
        }
    }
}

Example Input File

To minimally exercise your code you need more than one node in your linked list. What about attempting to lookup a node that does not exist -- validate that code-path?

$ cat dat/ll_video2.txt
insert
Arthur Benjamin: Lightning calculation and other "Mathemagic"
http://www.youtube.com/watch?v=M4vqr3_ROIk
Hard to believe.
15.25
4
insert
Arthur Benjamin: Some Other "Mathemagic"
http://www.youtube.com/watch?v=SomeOther
Hard to swallow.
25.25
7
lookup
Arthur Benjamin: Lightning calculation and other "Mathemagic"
lookup
Arthur Benjamin: Some Other "Mathemagic"
lookup
Mickey & Minnie do Disney
print

Example Use/Output

The results of the three lookups are handled correctly and the list contents print as they should in result to the print command input as the last line of input above:

$ ./bin/ll_video <dat/ll_video2.txt
Arthur Benjamin: Lightning calculation and other "Mathemagic", http://www.youtube.com/watch?v=M4vqr3_ROIk, Hard to believe., 15.25, 4
Arthur Benjamin: Some Other "Mathemagic", http://www.youtube.com/watch?v=SomeOther, Hard to swallow., 25.25, 7
title not found: 'Mickey & Minnie do Disney'.

list content:
Arthur Benjamin: Lightning calculation and other "Mathemagic", http://www.youtube.com/watch?v=M4vqr3_ROIk, Hard to believe., 15.25, 4
Arthur Benjamin: Some Other "Mathemagic", http://www.youtube.com/watch?v=SomeOther, Hard to swallow., 25.25, 7

Look things over and let me know if you have further questions.

Related