Thread: Linked list probs

  1. #1
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49

    Linked list probs

    Hey all,
    I'm including my telephone linked list code.
    I am having major problems trying to insert (or add)
    my new node in the appropriate alphabetical order.
    I tried to overload the > op to compare
    the first letters of the names -enterd last,first.
    but i keep crashing when the print function calls.
    (I know the menu can look better, I am just trying to get func-tionality down first).
    I suspect what I am trying to do by inserting alphabetically
    will also have something to do with my searchfor function?
    any comment on that would be helpful.
    thanks very much!
    Michele
    Code:
    #include<iostream>
    using namespace std;
     
     
    #define MAX  40
    
    struct TeleEntry
    {
     
     char EntryName[40];
     char EntryNumber[40];
     bool TeleEntry::operator > (const char* &TeleEntryA) const
     {
         if (strcmp(this->EntryName, TeleEntryA) > 0)
         {return true;}
         else
         {return false;}
     }
     
     TeleEntry* Next;
    
    
    
    
    };
     
    
    class ListofTeles
    {
     
    public:
    
     ListofTeles();
     int count();
     TeleEntry* Head;
     
    
     int Add(TeleEntry* Item);
     TeleEntry *Retrieve(int pos);
     bool Delete();
     bool Delete(int pos);
     void Print();
    
    
    private:
     
     int size;
    };
     
     
     
     
     
    
    //constructor__________________________________
     
    ListofTeles::ListofTeles():size(0), Head(NULL)
    {
    }
     
    //initialize count by size_____________________
     
    int ListofTeles::count()
    {
     return size;
    }
     
    //ADD_____________________________________________
     
    int ListofTeles::Add(TeleEntry *NewItem)
    {
    
     TeleEntry *Sample = new TeleEntry;
     Sample   = NewItem;
    
     if (Head==NULL)
     {
     Head  = Sample;
     }//if
     else
     {
         while((Sample->EntryName) > (Head->EntryName))
     {
                 Head = Sample->Next;
         }//while
    
                  Head  = Sample;
            
                
     }
     return size++;
    }//add
     
    //ITEM RETRIEVAL__________________________________
     
    TeleEntry *ListofTeles::Retrieve(int Position)
    {
     
     TeleEntry *Current = Head;
     for (int i=0; i<Position && Current !=NULL; i++)
     {
      Current=Current->Next;
     }
     
     return Current;
     
    
    }
     
    //ITEM DELETION______________________________________
     
    
    bool ListofTeles::Delete()
    {
     if (Head == NULL)
     {
      std::cout<<"The list is empty\n"<< endl;
      return false;
      
     }
     else
     {
      TeleEntry *Current;
      Current = Head->Next;
      Head->Next=Current->Next;
      size--;
      return true;
     }
      
    }
     
    //ITEM DELETION WITH ARGUEMENT__________________________
     
    bool ListofTeles::Delete(int position)
    {
     if (Retrieve(position) == NULL)
      return false;
     else
     {
      Retrieve(position -1)->Next = Retrieve (position +1);
      size--;
      return true;
     }
      
    }
    //PRINT LIST
    void ListofTeles::Print()
    {
    
     cout << "Print Telephone List" << endl;
     
     if (Head == NULL)
     {
      std::cout<<"The list is empty\n"<< endl;
     }
    else
    {
    TeleEntry *Current;
    
    Current = Head;
    
    while (Head!=NULL)
    {
    
      cout<<"\nName:     "<<Current->EntryName << "  " <<"Tele #:   "<< Current->EntryNumber << endl;;
    
      Current = Current->Next;
      Head = Current;
    
            }//while
        }//else
    }//Print
     
    //___________________________________________________
     
    int main()
    {
     
     ListofTeles *Teles= new ListofTeles();
     
     TeleEntry     *Tele;
    
     char Name [MAX];
     char Number[MAX];
     bool b;
    
     cout << "would you like to enter a name/number?"<< endl;
     cout << "enter 1 for yes 0 for no" << endl;
     cin >> b;
     
    
     while(b==1){
    cout << "Enter Name (Last,First) :"<< endl;
    cin >> Name;
    cout << "Enter Number :"<< endl;
    cin >> Number;
    
     Tele = new TeleEntry;
     strcpy (Tele->EntryNumber, Number);
     strcpy (Tele->EntryName, Name);
     
     Teles->Add(Tele);
    
     cout << "would you like to enter a name/number?"<< endl;
     cout << "enter 1 for yes 0 for no" << endl;
     cin >> b;
    
     }
    
     
    cout<<"Qty Telephone Numbers: " << Teles->count() << endl;
    
    
    Teles->Print();
     
     
    
    
    
     
     
    
    
    return 0;
     
    }

  2. #2
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    but i keep crashing when the print function calls.
    void ListofTeles::Print()
    {

    cout << "Print Telephone List" << endl;

    if (Head == NULL)
    {
    std::cout<<"The list is empty\n"<< endl;
    }
    else
    {
    TeleEntry *Current;

    Current = Head;

    while (Head!=NULL)
    {

    cout<<"\nName: "<<Current->EntryName << " " <<"Tele #: "<< Current->EntryNumber << endl;;

    Current = Current->Next;
    Head = Current;

    }//while
    }//else
    }//Print
    I believe this should be:
    Code:
    while (Current!=NULL)
    Last edited by andyhunter; 02-19-2005 at 03:57 PM.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  3. #3
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49
    Thanks,
    I don't think that's the problem-I believe the problem is in my Add function.
    If i added straight to the back print() worked fine.
    but thanks

  4. #4
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    Wow, I didn't even see this:
    Code:
    Head = Current;
    Why do you keep moving the head of your list?

    You do it in your add function here:
    Code:
        while((Sample->EntryName) > (Head->EntryName))
     {
                 Head = Sample->Next;
         }//while
    
                  Head  = Sample;
            
                
     }
    The head of your list always points to the element added in your list, not the first element.

    Maybe you should take a look at this tutorial or reread the section on linked lists in whatever book you have.
    Last edited by andyhunter; 02-19-2005 at 05:11 PM.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  5. #5
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540

    Understanding Linked Lists

    Now this is in C, but it should help you see what is going on.


    A linked list is simply a group of structures (containers to be exact, you can have a series of class objects) that have at least one member that is a pointer to the next object in the list. Now this isn’t as complicated as it may sound, lets take a look at it piece by piece.

    1. A linked list is a group of structures; thus one element in the linked list(often referred to as a node) would be a structure. So an example of this node would be similar to:
    Code:
    struct myNode {
        char name[10];
        char phoneNumber[13];
    };
    2. These nodes must contain at least one member that is a pointer to the next structure. Now we say at least one member because often it is more convenient to have 2 pointers; one pointing to the next node and one pointing to the previous node. So we know we need a pointer that is of type of our structure, thus something like this:
    Code:
    struct myNode* nextNode;
    So putting this together we get the definition of our node:
    Code:
    struct myNode {
        char name[10];
        char phoneNumber[12];
        struct myNode* nextNode;
    };
    Now that we understand the concept of what a node is lets move onto the implementation of the linked list. As stated previously a linked list is a group or chain of nodes. As with all chains we need to define an anchor or starting point. This starting point is simply a pointer that is of type of our structure. So our implementation of this anchor would be like:
    Code:
    struct myNode* firstNode;
    You define the end of a linked list by having the last node’s next pointer set to NULL. Now in the beginning of our program to signify an initially empty list we will set firstNode to NULL. Thus you will usually see something along the lines of:
    Code:
    firstNode = NULL;
    Alright the remaining concept to grasp the fundamentals of linked lists lies in successfully adding and removing nodes from our list. These topics revolve around dynamic memory allocation, using malloc() and free().This topic is as easy to understand as the previous topics however it seems to be the hardest for new programmers to grasp so we’ll spend some time here. The prototype for malloc() is:
    Code:
    void* malloc(size_t size);
    All malloc() does is allocate size bytes and returns a pointer of type void to that memory, or NULL if an error occured. So you are probably asking, well that’s great but how do I use it? Well the standard convention for using malloc is:
    Code:
    pointer = malloc(n * sizeof(*pointer));
    where n is the number of elements you need and *pointer (the dereferenced pointer) is used to determine the size of the individual element. So if I wanted to create 1 new node (our node we have been using) I would do it like so:
    Code:
    //allocate space for our node
    newNode = malloc(1 * sizeof(*newNode));
    //check for error
    if(newNode == NULL){
         printf("Error allocating memory");
         return;
    }
    *Note, the ISO standard dictates there is no need to cast the return from malloc(), however some compilers may complain about being unable to convert the types. If this happens you can still use malloc, simply cast the return*

    Now that we understand how to allocate the memory, lets take a look at how we add the node to our list. Remember that we signify the end of our list by having the last node’s next node pointer be NULL. Thus to add a new node we simply “walk through” our linked list until we find the last node. Once we are there we set the last node’s next node pointer to our newly created node. Thus the implementation would look like:
    Code:
    //first check if the linked list is empty
    //if it is make the new node the first node
    if(firstNode == NULL) {
         firstNode = newNode;
         return;
    }
    //if not find the last node
    walker = firstNode;
    while(walker->nextNode != NULL){
         walker = walker->nextNode;
    }
    //set last node's next node to our new node
    walker->nextNode = newNode;
    To delete a node is just as easy as adding a node but before we dive into that lets take a look at how we free the memory we allocated with malloc(). The function is conveniently called free() and its prototype is:
    Code:
    void free(void* mem);
    where mem is a pointer to the block of memory allocated dynamically. Note that there is no return value and free does not ask for nor want a size to free. It simply releases the amount of memory pointed to by mem. Pretty easy, right?

    So now you are probably asking, well that’s great but how do I delete my node from the list? Remember that these lists are chained together simply by the pointers that each element has. So to remove an element from the list all you need to do is:
    1. Find the node to delete and the previous node
    2. Make the previous node’s next node pointer point to the node following the node to delete (aka set the previous node’s next node member equal to the node to delete’s next node member).
    3. free the memory allocated for the node to delete.

    So lets look at this 1 step at a time:
    1. Find the node to delete and the previous node
    Code:
    //if deleting the first node
    if(nodeNumber == 1){
         nodeToDelete = firstNode;
         firstNode = firstNode->nextNode;
    }else{
         //start at the begginning
         nodeToDelete = firstNode;
         prevNode = NULL;
         //find the previous node and node to delete
         for(int i = 0; i < nodeNumber - 1; i++){
              prevNode = nodeToDelete;
              nodeToDelete = nodeToDelete->nextNode;
         }
    2. Make the previous node’s next node pointer point to the node
    Code:
    prevNode->nextNode = nodeToDelete->nextNode;
    3. free the memory allocated for the node to delete.
    Code:
    free(nodeToDelete);
    And that is all there is to removing a node from a linked list and about all the basics for a linked list. Normally you would sort your linked list but that is a matter for another lesson, or the interested individual to figure out. Hopefully this will help you hit the ground running. Attached below is a full sample program that displays the principles explained above. Additionally I have included another prog that does this whole phone list thing. Again this is in C so I am not giving you the answer, just trying to point you in the right direction.
    Last edited by andyhunter; 02-19-2005 at 06:59 PM.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  6. #6
    Registered User mouse163's Avatar
    Join Date
    Dec 2002
    Posts
    49
    thank you so much for taking the time to go thru all that for me-
    I am going to punch through your tips and the tutorial
    (believe me i have done a few!)

    I'm very grateful for your time-
    Michele

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM