sorting apstring help

This is a discussion on sorting apstring help within the C++ Programming forums, part of the General Programming Boards category; I have a linked list of several US capitals in which I need to put in alpha order. Each node ...

  1. #1
    Unregistered
    Guest

    sorting apstring help

    I have a linked list of several US capitals in which I need to put in alpha order. Each node of my linked list looks like this....

    struct node
    {
    apstring capital;
    node *next;
    };


    and the capitals are....

    Richmond
    Hartford
    Annapolis
    Montgomery
    Albany
    Harrisburg
    Sacramento
    Atlanta
    Bizmark
    Providence


    any help would be GREATLY appreciated

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    What is your problem exactly? My crystal ball has been decommissioned.

    -Prelude
    My best code is written with the delete key.

  3. #3
    Unregistered
    Guest
    how to do it depends on what type of list you are using and what methods are available in apstring.

    If you are using a list which is an instance of the STL list class, then you can use the generic STL function called sort() or a list member function called sort(), I belive. If you have an aplist class it might have similar functionality.

    Otherwise, you can write your own sorting function. I prefer to sort at time of insertion. But you could develop your own "bubble sort" to work with a list too, I suppose. It might look something like this (code not compiled or tried):

    Code:
    //use a node called current nd previous to help keep your place
    node * current;
    node * previous;
    
    //if your list's head node is not already a "blank" holding node, make it so.
    node * blank = new node;
    blank->next = head;
    head = blank;
    delete blank;
    blank = NULL;
    
    //likewise create a blank end node 
    node * end = new node;
    end->next = NULL;
    
    //and put it in place
    current = head->next;
    while(current-next != NULL)
    {
      current = current->next;
    }
    current->next = end;
    
    //now bubble the "largest" node capital to the spot before end
    while(end != head->next->next)//need two nodes to compare!
    {
    
      //each time through list (re)set current and previous
      current = head->next;
      previous = head;
    
      while(current->next != end) //need two nodes to compare!
      {
    
        //compare nodes using the > operator if available in apstring 
        if(current->capital > current->next->capital)
    
        //if > not overloaded in apstring use strcmp()
        //if(strcmp(current->capital, current->next->capital) > 0)
        {
    
          //switch nodes current and current-next to get bubble effect
    
          blank = current->next->next;
          previous->next = current->next;
          current->next->next = current;
          current->next = blank;
        }
        else
        {
          current = current->next;
        }
      }
    
      //advance end one to the left
      end = current->next;
    
    }

  4. #4
    Unregistered
    Guest
    after posting my code above, I've had the nagging feeling I left something out. Now I know what it is. You should put a blank node called tail at the end of the list, and assign tail to end before you start sorting the list. That way there will always be a tail with NULL at the last pointer called next. If you just keep shifting end to the left each time through the outer loop, then there won't be a NULL at the "tail end" of the list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. fatal error LNK1104
    By DMH in forum C++ Programming
    Replies: 2
    Last Post: 11-16-2005, 02:46 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Sorting words with a fast, effincient sorting method
    By Unregistered in forum C++ Programming
    Replies: 19
    Last Post: 07-12-2002, 04:21 PM
  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