Thread: Linked List Problems

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    48

    Linked List Problems

    Could someone please tell me what is wrong with my code.
    Code:
    // poddriver.cpp
    
    //Adapted from Roger Priebe
    //CS2308 11/17/08
    
    #include <stdlib.h>
    #include <iostream>
    #include "bobcatPod.h"
    
    using namespace std;
    
    int main()
    {
        
        Song s1("Frank Sinatra", "My way", 14);
        Song s2("Beatles", "Act Naturally", 5);
        Song s3;
        
        BobCatPod p(256);
        BobCatPod q(512);
        BobCatPod r(25);
    
        cout << "pod p" << endl << p << endl;
        cout << "pod q, size 512 exceeds max, should be reset to 256 " << endl
             << q << endl;
        cout << "pod r, size should be 25 " << endl << r << endl;
    
    
        cout << "Song 1" << s1 << endl;
        cout << "Song 2" << s2 << endl;
        cout << "Song 3" << s3 << endl;
    
        s3.setArtist("Buck Owens");
        s3.setTitle("Act Naturally");
        s3.setSize(20);
    
        cout << "Song 3 updated " << s3 << endl;
        cout << "Artist 1 (Frank Sinatra)  " << s1.getArtist() << endl;
        cout << "Title 2 (Act Naturally)  " << s2.getTitle() << endl;
    //    s1.setSize(7);
    //    cout << "Size 1 (7) " << s1.getSize() << endl;
    
    //test relational operators
    
        if (s1 < s3 ) cout << endl << "s1 < s3" << endl;
          else cout << endl << "s1 >= s3" << endl;
        if (s1 == s2) cout << endl << "s1 == s2" << endl;
          else cout << endl << "s1 != s2"  << endl;
        
    // test addnode
        cout << "add song 1, size 14 " << r.addSong(s1)  
             << "   memory left = "  << r.getRemainingMemory() <<endl;
        cout << "add song 2, size 5 " << r.addSong(s2) 
              << "   memory left = "  << r.getRemainingMemory() << endl;
        cout << "add song 3, size 20 should fail " << r.addSong(s3) 
             << "   memory left = "  << r.getRemainingMemory() << endl;
      
        s3.setSize(2);
        cout << "Size 3 (2) " << s3.getSize() << endl;
        cout << "add song 3, size 2 should succeed " << r.addSong(s3) 
             << "   memory left = "  << r.getRemainingMemory() << endl;
    
    
    // test output
        cout << r << endl;
    
    //test delete
    
        r.removeSong(s1);
        cout << r << endl;
        r.removeSong(s3);
        cout << r << endl;
    
        cout << "Total Memory"<< r.getTotalMemory() << endl;
    
    
    
    
    
        return 0;
    }
    Code:
    //song.h
    #ifndef SONG_H
    #define SONGT_H
    #include <stdlib.h>
    #include <iostream>
    #include <ostream>
    #include <string>
    
    using namespace std;
    
    
    class Song
    {
      
       public:
          Song::Song ();
          Song::Song(string , string , int ); // constructor
          void setSize(int s);
          double getSize(); // access or
          void setTitle (string t);
          string getTitle();
          void setArtist (string a);
          string getArtist();
          void addSong (int);
          friend ostream& operator<<(ostream & os, Song & s);
       private:
          string title;    //dynamic allocation
          string artist;
          int size;
    };
    #endif
    Code:
    // file song.cpp
    #include "song.h"
    #include "bobcatPod.h"
    
     ostream & operator << ( ostream & os, Song & s)
     {
          os << s.getTitle();
          os  << s.getArtist();
          return os;
     }
    //constructor
    Song::Song ()
    {
        title=" ";
        artist=" ";
        size = 0;
    }
    Song::Song(string a, string t, int s) // constructor
    {
        size = s;
        title = t;
        
        artist = a ;
        
    }
    //accessor for name
    string Song :: getTitle()
    {
          return title;
    }
    //mutator
    void Song :: setTitle (string t)
    {
         title = t;
         
    }
    string Song :: getArtist()
    {
          return artist;
    }
    //mutator
    void Song :: setArtist (string a)
    {
         artist = a;
         
    }
    void Song::setSize(int s)
    {
        size = s;
    }
    double Song::getSize()
    {
        return size;
    }

    Code:
    #define BOBCATPOD_H
    
    class bobcatPod
    {
          private:
                  //Declare a structure for the list
                  struct SongNode
          {
                 Song s;                  //value in this node
                 SongNode *next;      //To point to the next node
          };
          SongNode *head;
          
          public:
                 //Constructor
                 bobcatPod()
                    {head = NULL;}
                    
                 //Destructor
                 ~bobcatPod();
                 
                 //Linked list operations
                 void appendNode (Song s);
                 int addSong (Song s);
                 int removeSong (Song s);
                 void showSongList ();
                 int getTotalMemory();
                 int getRemainingMemory();
    };
    #endif
    Code:
    #include "song.h"
    #include "bobcatPod.h"
    void bobcatPod::appendNode (Song num)
    {
         SongNode *newNode;   //to point to a new node
         SongNode *nodePtr;   //to move through the list
         //allocate a new node and stor num there.
         newNode = new SongNode;
         newNode->s = num;
         newNode->next = NULL;
         
         //if there are no nodes in the list
         //make newNode the first node
         if (!head)
             head = newNode;
         else     //otherwise, insert newNOde at end
         {
                  //initialize nodePtr to head of list
                  nodePtr = head;
                  
                  //find the last node in the list
                  while (nodePtr->next)
                     nodePtr = nodePtr->next;
                     
                  //insert newNode as the last node.
                  nodePtr->next = newNode;
         }
    }
    
    
    int bobcatPod::addSong(Song s)
    {
         Song *newSong;     //a new node
         Song *nodePrt;     //to traverse the list
         Song *previousSong = NULL;       //The previous node
         
         // Allocate a new node and stor num there.
         newSong = new Song;
         
         newSong->next = NULL;
         
         
         //If ther are no nodes in the list
         //make newSong the first node
         if (!head)
         {
                   head = newSong;
                   newSong -> next = NULL;
         }
         else      //Otherwise, insert newSong
         {
                   //Position nodePtr at the head of list.
                   nodePtr = head;
                   //Initialize prefiousSong to NULL.
                   previousSong = NULL
                   
                   //skip all nodes whose value is less than num.
                   while (nodePtr != NULL && nodePtr ->value <num)
                   {
                         previousSong = nodePtr;
                         nodePtr = nodePtr->next;
                   }
                   //If the new Song is to be the 1s in the list,
                   //insert it before all other nodes.
                   if (previousSong ==NULL)
                   {
                                    head = newSong;
                                    newSong ->next = nodePtr;
                   }
                   else             //Otherwise insert after the previous node.
                   {
                                    previousSong->next = newSong;
                                    newSong-> next = nodePrt;
                   }
         }
    }
    The driver and song files work, but there is something wrong with bobpod files.

  2. #2
    ‡ †hë Ö†hÈr sîÐè ‡ Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    What type of problem are you having?.

    Also look at the "BOBCATPOD.H" file.
    Code:
    #define BOBCATPOD_H
    ....
    #endif //<< what are you endif ing????
    Code:
    void bobcatPod::appendNode (Song num)
    {
         SongNode *newNode;   //to point to a new node
         SongNode *nodePtr;   //to move through the list
         //allocate a new node and stor num there.
         newNode = new SongNode;
         newNode->s = num;//<<<<<NEVER use new memory without error checking.
    Vistas Biggest Problem

    Code:
    #define BOBCATPOD_H
    class bobcatPod
    {
         ....
                 //Constructor
                 bobcatPod()
                    {head = NULL;}
                    
                 //Destructor
                 ~bobcatPod();//You need to delete all the entrys of the list here.
                 //or else you get leaks.
    Last edited by Nor; 11-20-2008 at 08:26 PM.
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    48
    I do have a #ifndef BOBCATPOD_H
    #define BOBCATPOD_H
    I just missed it on the copy paste
    What do you mean by delete all the entrys of the list? The operations?
    and how do I error check? I have tried to follow the instruction in my book for linked lists, but I don't understand them and I have like 4 more files to write for them by Monday.
    I appreciate the help

  4. #4
    ‡ †hë Ö†hÈr sîÐè ‡ Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    Code:
    int*  pNumber = new int;
    if(pNumber){
        //Memory is good
    }
    or ...
    Code:
    if( !pNumber ){
        //Memory is BAD
    }
    In your constructor you setup the linked list and get it ready to add items, right?

    In your main() function you add items using the 'new' operator.
    At no point in your program do you delete the items you add to your list.

    You need to delete all the items you added to your list in the destructor.
    I'd make a function called EmptyList() and simply call it in the destructor.
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    48

    BobCatPod

    if I have
    Code:
    class BobCatPod
    in my .h
    why does this say BobCatPod is undelcared in
    Code:
    void BobCatPod::appendNode (Song num)

  6. #6
    ‡ †hë Ö†hÈr sîÐè ‡ Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    First, what compiler are you using?
    Next,
    Code:
                bobcatPod()
                    {head = NULL;}
    You should only declare things in header ( *.h ) files.
    try
    Code:
    //bobcatPod.h file
    class bobcatPod
    {
          private:
         ...
          public:
                bobcatPod();
          ...
    
    //bobcatPod.cpp file
    bobcatPod::bobcatPod(){
          ....
    }
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    48
    Im using dev c++
    so instead of
    Code:
    //BobCatPod.cpp
    void BobCatPod::appendNode (Song num)
    I should use
    Code:
    void BobCatPod::BobCatPod (Song num)

  8. #8
    Registered User
    Join Date
    Nov 2008
    Posts
    48
    here are my current codes
    Code:
    //BobCatPod.h
    
    //Specification files for the SongList class
    
    #ifndef BOBCATPOD_H
    #define BOBCATPOD_H
    #include "song.h"
    
    class BobCatPod
    {
          private:
                  //Declare a structure for the list
                  struct SongNode
          {
                 Song s;                  //value in this node
                 SongNode *next;      //To point to the next node
          };
          SongNode *head;
          
          public:
                 //Constructor
                 BobCatPod()
                    {head = NULL;}
                    
                 //Destructor
                 ~BobCatPod();
                 if( !pNumber )
                 {
                     //Memory is BAD
                 }
                 
                 //Linked list operations
                 void appendNode (Song s);
                 int addSong (Song s);
                 int removeSong (Song s);
                 void showSongList ();
                 int getTotalMemory();
                 int getRemainingMemory();
                 friend ostream& operator<<(ostream & os, Song & s);
    };
    #endif
    Code:
    //BobCatPod.cpp
    #include "song.h"
    
    void BobCatPod::appendNode (Song num)
    {
         SongNode *newNode;   //to point to a new node
         SongNode *nodePtr;   //to move through the list
         //allocate a new node and stor num there.
         newNode = new SongNode;
         newNode->s = num;
         newNode->next = NULL;
         
         //if there are no nodes in the list
         //make newNode the first node
         if (!head)
             head = newNode;
         else     //otherwise, insert newNOde at end
         {
                  //initialize nodePtr to head of list
                  nodePtr = head;
                  
                  //find the last node in the list
                  while (nodePtr->next)
                     nodePtr = nodePtr->next;
                     
                  //insert newNode as the last node.
                  nodePtr->next = newNode;
         }
    }
    
    
    int BobCatPod::addSong(Song s)
    {
         Song *newSong;     //a new node
         Song *nodePrt;     //to traverse the list
         Song *previousSong = NULL;       //The previous node
         
         // Allocate a new node and stor num there.
         newSong = new Song;
         
         newSong->next = NULL;
         
         
         //If ther are no nodes in the list
         //make newSong the first node
         if (!head)
         {
                   head = newSong;
                   newSong -> next = NULL;
         }
         else      //Otherwise, insert newSong
         {
                   //Position nodePtr at the head of list.
                   nodePtr = head;
                   //Initialize prefiousSong to NULL.
                   previousSong = NULL
                   
                   //skip all nodes whose value is less than num.
                   while (nodePtr != NULL && nodePtr ->value <num)
                   {
                         previousSong = nodePtr;
                         nodePtr = nodePtr->next;
                   }
                   //If the new Song is to be the 1s in the list,
                   //insert it before all other nodes.
                   if (previousSong ==NULL)
                   {
                                    head = newSong;
                                    newSong ->next = nodePtr;
                   }
                   else             //Otherwise insert after the previous node.
                   {
                                    previousSong->next = newSong;
                                    newSong-> next = nodePrt;
                   }
         }
    }

  9. #9
    ‡ †hë Ö†hÈr sîÐè ‡ Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    nope.
    I'm saying you need to only 'Declare' the function prototype in the header file.
    Then you need to Define the function in your cpp file.
    When I did this in ms Visual Studios 2003, the file compiled.
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  10. #10
    Registered User
    Join Date
    Nov 2008
    Posts
    48
    so it works if i add #include "BobCatPod.h"
    but
    it says expected unqualified id before "if"
    Code:
    //Destructor
                 ~BobCatPod();
                 
                 if( !pNumber )
                 {
                     //Memory is BAD
                 }
    is there a problem with ~BobCatPod(); ?

  11. #11
    ‡ †hë Ö†hÈr sîÐè ‡ Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    Move the struct outside your class for easy reading.
    Then remove the Red and add the Green.
    Code:
    //Declare a structure for the list
          struct SongNode
          {
                 Song s;                  //value in this node
                 SongNode *next;      //To point to the next node
          };
    
    class BobCatPod
    {
          private:
                  
          SongNode *head;
          
          public:
                 //Constructor
                 BobCatPod();
                    {head = NULL;}                
                 //Destructor
                 ~BobCatPod();
                 if( !pNumber )
                 {
                     //Memory is BAD
                 }
                 
                 //Linked list operations
                 void appendNode (Song s);
                 int addSong (Song s);
                 int removeSong (Song s);
                 void showSongList ();
                 int getTotalMemory();
                 int getRemainingMemory();
                 friend ostream& operator<<(ostream & os, Song & s);
    };
    Code:
    //BobCatPod.cpp
    #include "song.h"
    void BobCatPod::BobCatPod(){
    head = NULL;
    }
    
    void BobCatPod::appendNode (Song num)
    {
         SongNode *newNode;   //to point to a new node
         SongNode *nodePtr;   //to move through the list
         //allocate a new node and stor num there.
         newNode = new SongNode;
        if(!newNode){
                //ERROR
          }
         newNode->s = num;
         newNode->next = NULL;
         
         //if there are no nodes in the list
    sorry about the hard to see color
    bed time. i'll show you some more in the morning before work.
    Last edited by Nor; 11-20-2008 at 10:07 PM.
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  12. #12
    Registered User
    Join Date
    Nov 2008
    Posts
    48
    thanks so much i really appreciate it

  13. #13
    ‡ †hë Ö†hÈr sîÐè ‡ Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    OK. here is a quick layout for you. Please don't think i'm being rude but you need a lot of practice.
    Typos KILL in programming.
    I've colored some for you along with other errors.
    Code:
    int BobCatPod::addSong(Song s)
    {
    
         //Song *newSong;     //a new node
         //Song *nodePrt;     //to traverse the list
         //Song *previousSong = NULL;       //The previous node
         //
         //The above is all wrong.
         SongNode *newSong		= NULL;
         SongNode *nodePrt		= NULL;
         SongNode *previousSong     = NULL;
    	
        // Allocate a new node and stor num there.
         newSong = new Song;
         /*EDIT*/
    	 if( !newSong )
    		 exit(1); //error
         /*EDIT*/
    	 newSong->next = NULL;  //LINE 56
         
         //If ther are no nodes in the list
         //make newSong the first node
         if (!head)
         {
                   head = newSong;
                   newSong -> next = NULL; //<<THIS is done on line 56.     }
         else      //Otherwise, insert newSong
         {
                   //Position nodePtr at the head of list.
                   //nodePtr = head;
    		       nodePrt = head;
    You need to go through your program line by line and try to find these errors. use your compiler to help.
    Start at the first error you get and look at that line good.
    If it is not in that line then it will be before it. Good Luck.
    When you get your code to compile i'll show you the logic error In the addSong routine.
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  14. #14
    ‡ †hë Ö†hÈr sîÐè ‡ Nor's Avatar
    Join Date
    Nov 2001
    Posts
    299
    Another question. Is there any reason you can not use std::list?
    http://www.cprogramming.com/tutorial/stl/stllist.html
    This is a container template. all you have to do is
    Code:
    #include <list>
    std::list<Song> MyList;
    Try to help all less knowledgeable than yourself, within
    the limits provided by time, complexity and tolerance.
    - Nor

  15. #15
    Registered User
    Join Date
    Nov 2008
    Posts
    48
    Ok I have reworked some things, but I am still haveing trouble. Here is what I have now
    Code:
    //BobCatPod.h
    
    //Specification files for the SongList class
    
    #ifndef BOBCATPOD_H
    #define BOBCATPOD_H
    #include "song.h"
    
    
    
    class BobCatPod
    {
          
          private:
          struct SongNode
          {
                 Song s;                  //value in this node
                 SongNode *next;
          
                             
          };
          SongNode *head;
          static const int MAX_SIZE = 256;
          
          
          public:
                 
                 //Constructor
                 BobCatPod();
    
           
                    
                 //Destructor
                 ~BobCatPod();
    
                 
                 
                 //Linked list operations
                 
                 bool isfull ();
                 bool addSong (Song s);
                 int removeSong (Song s);
                 void showSongList ();
                 int getTotalMemory();
                 int getRemainingMemory();
                 friend ostream& operator<<(ostream & os, Song & s);
    };
    #endif
    Code:
    //BobCatPod.cpp
    #include "song.h"
    #include "BobCatPod.h"
    
    
    
    BobCatPod::BobCatPod()
    {
         head = NULL;
         
    }
    
    bool BobCatPod::isfull ()
    {
         if (remainingMemory > MAX_MEMORY)
         {
                    return true;
         }
    
    }
    bool BobCatPod::addSong(Song t)
    {
          if (isfull ())
         {
                    return false;
         }
         SongNode *newSong = new SongNode;     //a new node
         
        
         
         // Allocate a new node and stor num there.
         
         newSong->s = t; 
         head = newSong;
         newSong->next = NULL;
         
        
         return true;
    }
                                    
    int BobCatPod::getTotalMemory()
    {
        int totalMemory;
        int usedMemory;
        totalMemory - usedMemory = remainingMemory
        return remainingMemory;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Help!
    By mbk in forum C Programming
    Replies: 3
    Last Post: 01-31-2008, 03:54 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM