Sorting while inserting

This is a discussion on Sorting while inserting within the C++ Programming forums, part of the General Programming Boards category; I am trying to insert names alphabetically into a linked list. It is compiling but I am getting runtime errors ...

  1. #1
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22

    Sorting while inserting

    I am trying to insert names alphabetically into a linked list. It is compiling but I am getting runtime errors when I test it. Can anyone see where I'm going wrong?

    Code:
    int list::add(char firstname[30], char lastname[30])
    {
        node * prev = NULL; 
        node * curr = head;  
        
        //find position of last name
        while(curr != NULL && (strcmp(curr->lname, lastname) < 0))
        {
            prev = curr;
            curr = curr->next;
        }
    
        if(prev == NULL)
        {
        
        head = new node;
    
        head->fname = new char[strlen(firstname)+1];
        strcpy(head->fname, firstname);
    
        head->lname = new char[strlen(lastname)+1];
        strcpy(head->lname, lastname);
             
        head->next = curr;
    
        ++num_in_list;
    
        return 0;
        }
    
        else
        {
        
            //if last names are equal, order by firstname
            while(strcmp(curr->lname, lastname) == 0 && 
                      strcmp(curr->fname, firstname) < 0)
            {
                prev = curr;
                curr = curr->next;
            }		
    		
            prev->next = new node;
            prev = prev->next;
    	    
            head->fname = new char[strlen(firstname)+1];
            strcpy(head->fname, firstname);
    
            head->lname = new char[strlen(lastname)+1];
            strcpy(head->lname, lastname);
    
            prev->next = curr;
    
            ++ num_in_list;
    
            return 0;
            }
    
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    I am getting runtime errors when I test it.
    before looking at the code, what ARE the errors?

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    25
    out of curiosity what is head equal in the begining of your code

  4. #4
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22
    When I try to display the list after adding names a pop-up tells me that a unhandled win32 exception occured.

    Head is initialized to NULL in the constructor. Is this what you ask?
    Last edited by StevenGarcia; 11-10-2006 at 08:34 PM.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    can you post the whole code if its not excessively long? is anything NOT working? or is it just this message that you get?

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    The first thing I see is if(prev == NULL). If there is a single element in the list that doesn't match the last name, then at that point prev will point to the element in the list and curr will be null. So I don't think checking prev for null is what you wanted. That bug will cause the crash you are seeing.

  7. #7
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22
    Thanks for the input. I've changed "if(prev == NULL)" to "if(!prev && !curr)" for checking if the list is empty. I am now getting the same error when I add more than one name. I think I've been staring at this for too long. Here is the updated whole code:

    Ack! My spacing got all screwy when i pasted it. I'm fixing it now, sorry.
    Code:
    #include <iostream>
    #include <string.h>
    
    using namespace std;
    
    #include "list.h"
    
    //=========================================================
    // Constructor
    //=========================================================
    
    list::list()
    {
    	num_in_list = 0;
    	head = NULL;
    }
    
    //==========================================================
    // Destructor
    //==========================================================
    
    list::~list()
    {
    	node * curr; //temporary pointer for deleting
    	
        //deletes vacation photo list
        while(head)
        {
    	   curr = head->next;
    	   delete [] head->fname;
    	   delete [] head->lname;
    	   delete head;
    	   head = curr;
        }
    
    }
    
    
    //==========================================================
    // Add
    //==========================================================
      
    int list::add(char firstname[30], char lastname[30])
    {
        node * prev = NULL; 
        node * curr = head;  
    
        //find position of last name
        while(curr != NULL && (strcmp(curr->lname, lastname) < 0))
        {
            prev = curr;
            curr = curr->next;
        }
    
        if(!curr && !prev)
        {
            head = new node;
    
            head->fname = new char[strlen(firstname)+1];
            strcpy(head->fname, firstname);
    
            head->lname = new char[strlen(lastname)+1];
            strcpy(head->lname, lastname);
             
            head->next = curr;
     
            ++num_in_list;
    
            return 0;
        }
    
        else
        {
            //if last names are equal, order by firstname
            while(strcmp(curr->lname, lastname) == 0  &&
                     strcmp(curr->fname, firstname) < 0)
            {
                prev = curr;
                curr = curr->next;
            }		
    		
            prev->next = new node;
            prev = prev->next;
    	    
            head->fname = new char[strlen(firstname)+1];
            strcpy(head->fname, firstname);
        
            head->lname = new char[strlen(lastname)+1];
            strcpy(head->lname, lastname);
    
            prev->next = curr;
    
            ++ num_in_list;
    
            return 0;
            }
    
            return 0;
    }
    
    //==========================================================
    // Remove
    //==========================================================
    
    int list::remove(char firstname[30], char lastname[30])
    {
    
    	node * curr;
    	node * prev;
    
    	curr = head;
    
    	while((curr != NULL) && ((strcmp(curr->lname, lastname) + strcmp(curr->fname, firstname) != 0)))
    	{
    		curr = curr->next;
    	}
    
    	if(curr == NULL)
    	{
    		cout << "NO MATCH FOUND" << endl;
    		
    		return 0;
    	}
    
    	if(curr == head)
    	{
    		head = curr->next;
    		delete [] curr->fname;
    		delete [] curr->lname;
    		delete curr;
    		curr = NULL;
    
    		-- num_in_list;
    	}
    	else
    	{
    		prev = head;
    
    		while(prev->next != curr)
    		{
    			prev = prev->next;
    		}
    
    		prev->next = curr->next;
    
    		delete [] curr->fname;
    		delete [] curr->lname;
            delete curr;
    		curr = NULL;
    
    		-- num_in_list;
    	}
    
    
    	return 0;
    }
    
    //==========================================================
    // Display
    //==========================================================
    
    int list::display()
    {
      node * curr;      
    
      curr = head;
    
      while(curr)
      {
        cout << curr->fname << " " << curr->lname << endl;
        curr = curr->next;
      }
    
      return 0;
    }
    Last edited by StevenGarcia; 11-10-2006 at 09:02 PM.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    Ok, but follow the code when the list has a name that doesn't match. As I said before, prev will be the item in the list, and curr will be null (since it reached the end without a match).

    Follow the flow of the function and notice what happens in that specific instance. Maybe even write things down as you go so you can visualize it. You will find where you are using a null pointer and where you need more logic.

    >> (strcmp(curr->lname, lastname) + strcmp(curr->fname, firstname) != 0)
    On a separate note, that code is cute, but what if the first compare returns -1 and the second returns positive 1?
    Last edited by Daved; 11-10-2006 at 09:12 PM.

  9. #9
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    also since this is C++, why not include string (instead of string.h) and use 'string' objects rather than char*? or maybe your just practicing with char*s?

  10. #10
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22
    I see the problem now. Thanks for the input. = )

  11. #11
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22
    Quote Originally Posted by nadroj
    also since this is C++, why not include string (instead of string.h) and use 'string' objects rather than char*? or maybe your just practicing with char*s?
    I'm not sure how that works. In my spare time I am relearning the limited amount of programming knowledge I had at one time. It wasn't much. Thank you for the suggestion.

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    Writing a linked list is a great learning device. In practice, though, you use an existing container like the standard list or vector classes, in addition to the standard C++ string class. They are much less error prone and actually easier to use after you get over the initial hump.

  13. #13
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    search around for how to use the string class, or see http://www.fredosaurus.com/notes-cpp...er-string.html here for a quick link.

    with c++ strings you dont have to worry about nulls or out of bounds errors.. plus there are many handy methods to check the size, etc etc.

    they are really easy to use. good luck!

    however, if you are trying to 'relearn' programming then i do suggest continuing working with char*s for now because it makes you think a little more and is better practice!

  14. #14
    Registered User StevenGarcia's Avatar
    Join Date
    Nov 2006
    Posts
    22
    Thanks for the advice guys. I will definately check that out after I get a little more comfortable with C++.

  15. #15
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Ack! My spacing got all screwy when i pasted it.
    Said it before, say it again: different applications and fonts use vastly different tab-to-space ratios. A tab-and-space potpourri lining up in your editor is no guarantee that it'll line up your code elsewhere. This forum itself contains many painful illustrations of what can go wrong. Use spaces or tabs exclusively; don't intermix.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 06-11-2009, 11:27 AM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Replies: 2
    Last Post: 02-23-2004, 05:34 AM
  5. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21