Solved

Self Organizing LinkedList

Posted on 1998-08-21
8
377 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
  • 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
Optimizing Cloud Backup for Low Bandwidth

With cloud storage prices going down a growing number of SMBs start to use it for backup storage. Unfortunately, business data volume rarely fits the average Internet speed. This article provides an overview of main Internet speed challenges and reveals backup best practices.

 
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

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Implementing a ResolveEventHandler in C++ 13 133
C Language combined operators 28 109
c++ syntax question 9 49
passing data from one form to another form in c++ 27 80
Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

777 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