What am I doing wrong?

The geek forum. PHP, Perl, HTML, hardware questions etc.. it's all in here. Got a techie question? We'll sort you out. Ask your questions or post a link to your own site here!

What am I doing wrong?

Postby Slater » Thu Oct 05, 2006 10:25 pm

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?
Image
User avatar
Slater
 
Posts: 2671
Joined: Sat May 22, 2004 10:00 am
Location: Pacifica, Caliphornia

Postby Warrior4Christ » Sat Oct 07, 2006 12:30 am

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)
  }
}
Everywhere like such as, and MOES.

"Expect great things from God; attempt great things for God." - William Carey
User avatar
Warrior4Christ
 
Posts: 2045
Joined: Sat Aug 20, 2005 8:10 pm
Location: Carefully place an additional prawn on the barbecue


Return to Computing and Links

Who is online

Users browsing this forum: No registered users and 171 guests