CAA: Christian Anime Alliance

argh, ok, another C++ question, relating to link lists.

So, I have a class that looks like... this...

Code: Select all

class cLinkedStrings
   {
   public:
      cLinkedStrings ();
      bool readString (ifstream * f);
      void add (cLinkedStrings ** phead);
      cLinkedStrings * next;
      void printString();
        const cLinkedStrings operator +(const cLinkedStrings& CLS2) const;
        const cLinkedStrings operator =(const cLinkedStrings& CLS2) const;
        bool operator ==(const cLinkedStrings& CLS2) const;
        bool operator <(const cLinkedStrings& CLS2) const;
        bool operator <=(const cLinkedStrings& CLS2) const;
        bool operator >(const cLinkedStrings& CLS2) const;
        bool operator >=(const cLinkedStrings& CLS2) const;
        bool operator !=(const cLinkedStrings& CLS2) const;
        void append(cLinkedStrings ** head);
        void insert(cLinkedStrings ** head);
       
   private:
      string s;
   };

note cLinkedStrings * next, the overloaded operators, insert, and the private string s.
next is the pointer to the next object in the list.
The overloaded operators work on strings in the object, exactly as the string class uses them.
s is the string of the object.
insert is my headache. See, I'm supposed to write a function that inserts a new node into a linked list alphabetically (read: alphanumerically).

The best I have come up with is this.

Code: Select all

void cLinkedStrings::insert(cLinkedStrings ** point)
{   
     cLinkedStrings * pt = *point;
     
     while ((pt != NULL) && !(*this <= *pt))
     {
           pt = pt->next;
     }

     if ((pt == NULL) || !(*this <= *pt))
     {
         next = NULL;
         *point = this;
     }

     else if ((*this <= *pt) && (pt != NULL))
     {
         next = *point;
         *point = this;
     }
}

Now, I get my nodes by reading individual lines from a file. This file looks like this.

Code: Select all

a
c
f
b
k
j
z
y
m
d

Yes, just single characters on each line. Now, when I run the program, it only adds 4 nodes to this list, in the following order: z, y, m, d
The last 4 letters alone. Argh... any ideas on what's wrong with my insert method?

I can't quite follow what your insert method is doing. But to insert an object into a linked list, you need the pointer to the head of the list, as well as the object to insert. In this case, it seems you have the object (string) in a link class. Presumably that link with have a NULL next pointer.

You need to start with the head link, and step along that, comparing the value to the one you want to insert. To me, it seems you're keeping the current link the same and stepping along to the next of the link you want to insert (hope that made sense).

An insert algorithm would be:

Code: Select all

ins = link you want to insert
currp = stepping through pointer.
lastp = last pointer.

currp = head
lastp = currpt
// special case for head
if(head == NULL || head.val >= ins.val) {  // can also be head.val > ins.val
  if(head != NULL) {
    ins.next = head.null
  } else {
    ins.next = NULL
  }
  head = ins
} else {
  // normal cases
  while (currp != NULL && currp.val < ins.val) {  // can also be currp.val <= ins.val
    lastp=currp
    currp = currp.next
  }
  ins.next = currp
  lastp.next = ins
}

Even though I wrote the algorithm just then, I'm fairly certain it should work. This relies on the fact that once the first condition is met (or not met) in an if or while loop, it continues without evaluating the other one. This now just needs to be adapted to your specific case of cLinkedStrings with C++ pointers.

HINT: There are two ways of doing this. One with knowing the head link of this list (external-type insert), or by passing the value down the link by using a the insert method that belongs to an individual link class (internal-type insert). The individual link class doesn't have access to the head link, it would be not a good idea to pass it as a parameter for the internal insert.

EDIT: just added the internal-type insert algorithm (it's a bit easier).
You still need to be careful to the case that head = NULL (use a sentinel?)

Code: Select all

insert(LinkClass ins) {
  if(this.next == NULL || this.next.val >= ins.val) {  // can also be this.next.val > ins.val
    ins.next = this.next
    this.next = ins
  } else {
    this.next.insert(ins)
  }
}