Solved

Self Organizing LinkedList

Posted on 1998-08-21
8
404 Views
Last Modified: 2010-04-01
I am working on a self organizing insert function for a linked list.  This is what I have so far can you please help me?

void LinkedList::Insert(char firstname[], char lastname[])
{
  Node * l = new Node(firstname, lastname);
  Node * p = first;
  Node * z;
  Node * x;

  assert(l !=0 );

  if(first == NULL)
    first = l;


   while(p != NULL && first -> next != NULL)
   {
      if(strcmp(p -> next -> r.First_Name,
         p -> r.First_Name) < 0)
         {
            l = p -> next;
            p -> next = l;

            p = p -> next;
         }

      else
      {
         z = p;
         z -> next = p -> next;
         x = p -> next;
         x -> next = p -> next -> next;
         p -> next = x -> next;
         x -> next = p;
         z = x = NULL;
      }
   }
}
0
Comment
Question by:hawhite
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
8 Comments
 
LVL 8

Accepted Solution

by:
Answers2000 earned 50 total points
ID: 1170929
Code in the comment below
0
 
LVL 8

Expert Comment

by:Answers2000
ID: 1170930
#include <stdio.h>
#include <string.h>

class member ;

class member
{
public:
      char first[256] ;
      char last[256] ;
      member * next ;
} ;

class mylist
{
private:
      member * head ;
public:
      mylist()
      {
            head = NULL ;
      }

      void Insert( const char * first, const char * last )
      {
            // allocate new member
            member * newmember = new member ;
            strcpy( newmember->first, first ) ;
            strcpy( newmember->last, last ) ;

            // find position
            member * prev = NULL ;
            member * current = head ;

            while ( current != NULL )
            {
                  // sort by first name as in your sample
                  // you may want a more sophisticated comparison to sort by first + last name
                  if ( strcmp( first, current->first ) < 0 )
                  {
                        if ( prev != NULL )
                        {
                              prev->next = newmember ;
                        } else
                        {
                              // may first item in list
                              head = newmember ;
                        }
                        newmember->next = current ;
                        return ;
                  }
                  prev = current ;
                  current = current->next ;
            }

            // insert at the end if last in list
            if ( prev != NULL )
            {
                  prev->next = newmember ;
            }
            newmember->next = NULL ;

            // this may be the only (first) item in the list,
            if ( head == NULL )
            {
                  head = newmember ;
            }
      }


      void DeleteAll()
      {
            member * temp = head ;

            while ( temp != NULL )
            {
                  member * temp2 = temp->next ;
                  delete temp ;
                  temp = temp2 ;
            }
      }

      void ListAll()
      {
            member * temp = head ;

            while ( temp != NULL )
            {
                  printf( "%s %s\n", temp->first, temp->last ) ;
                  temp = temp->next ;
            }
      }

      virtual ~mylist()
      {
            DeleteAll() ;
      }

} ;


int main( int * argc, char * argv[] )
{
      mylist alist ;
      alist.Insert( "John", "Smith" ) ;
      alist.Insert( "John", "Doe" ) ;
      alist.Insert( "Fred", "Flintstone" ) ;
      alist.Insert( "Zack", "Taylor" ) ;
      alist.ListAll() ;

      return 0 ;
}
0
 
LVL 8

Expert Comment

by:Answers2000
ID: 1170931
You can nest the member class into mylist if you only want one class.

I used strcpy, char[] and printf, you may wish to change to STL strings and cout - but that's up to you
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 8

Expert Comment

by:Answers2000
ID: 1170932
Sorry about the indents, it lost em when I copied from VC.

My biggest tips is
1. Use descriptive variable names
2. Declare variables near where you use them where-ever possible, especially temporaries.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1170933
Answers2000, this is probably a schoolwork assignment.  You might want to consider providing HELP not an exact answer on this type of question.
0
 
LVL 11

Expert Comment

by:alexo
ID: 1170934
Answers2000, EE swallows tabs.  Use spaces for indents.
BTW, I agree with nietod's comment.
0
 
LVL 8

Expert Comment

by:Answers2000
ID: 1170935
MMm u could be right

had a look at the guy's Q history and there's a couple of things in there that make me a bit suspicious, and also a couple of things that don't.

I'll watch what he posts next time.

BTW I posted code (not my preference) rather than a correction because I couldn't follow his variable names :-)
0
 
LVL 8

Expert Comment

by:Answers2000
ID: 1170936
One other thought, if it is maybe the prof might ask him why

virtual ~mylist()

rather than

~mylist()

which could be interesting...
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

690 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question