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

What is your problem exactly? My crystal ball has been decommissioned.

-Prelude

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;

}

---

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.