C++ Problem

12-31-2006, 08:48 PM

I was experimenting with linked lists, and ended up making a class for using them. Its use is specifically to add/find values stored in it. The finding function is working perfectly fine, my problem is with the adding function. Here is my linked list struct:

Code:

struct node{
    char* value;
    node* next;
};

Now, with my insert function (to add a string to a list), it works perfectly fine if I give it a constant string like "text", but if I insert a character array, the first time it works fine. After that, if I add another, it turns all the values in the linked list to the value just added. If you still don't understand, here's the code:

Hidden information:

Code:

#include <stdio.h>
#include <stdlib.h>

struct node{
       char* value;
       node *next;
};

class LinkedList{
      public:
             int Find(char* ID);
             void Insert(char* ID);
             LinkedList();
             ~LinkedList();
      private:
             node *root;
};

int LinkedList::Find(char* ID)
{
     node *current;
     current = root;
     while( current != NULL )
     {
            printf("\nComparing: %s to %s",  current->value, ID);
            if( current->value[0] == ID[0] && current->value[1] == ID[1] && current->value[2] == ID[2] && current->value[3] == ID[3])
                                  return 0;
            current = current->next;
     }
     current = NULL;
     return 1;
}

void LinkedList::Insert(char* ID)
{
     if( root == NULL)
     {
         root = (node*)malloc(sizeof(node));
         root->value = ID;
         root->next = NULL;
     }
     else
     {
         node *current = root;
         while(current->next != NULL)
         {
                       current = current->next;
         }
         current->next = (node*)malloc(sizeof(node));
         current = current->next;
         current->value = ID;
         current->next = NULL;
     }
}

LinkedList::LinkedList()
{
     root = NULL;
}

void DeleteList(node *a_node)
{
     if (a_node != NULL)
     {
                DeleteList(a_node->next);
                free(a_node);
     }
}

LinkedList::~LinkedList()
{
     DeleteList(root);
}                    

int main()
{
    LinkedList ll;
    
    char temp[4];
    
    temp[0] = 'r';
    temp[1] = 'k';
    temp[2] = 'g';
    temp[3] = 'b';

    ll.Insert(temp);
    
    temp[0] = 'h';
    temp[1] = 'f';
    temp[2] = 'a';
    temp[3] = 'd';
    
    ll.Insert(temp);
    
    ll.Insert("aqdf");
    ll.Insert("qsdf");
    ll.Insert("a7df");
    ll.Insert("ashf");
    ll.Insert("asdL");
    ll.Insert("as1f");
    ll.Insert("fWdf");
    ll.Insert("asaf");
    
    printf("\nReturn Value: %d", ll.Find("rkgb"));
    getchar();
}

Any ideas on what the problem is?

12-31-2006, 09:24 PM

PitzerMike

It's not a problem in your list implementation, but you're overwriting the characters of your temp-variable in the main function.
Since you're just passing pointers to the first character of your id (and not copying the values), both nodes will point to the same temp-variable.

Also why reinvent the wheel, when the STL already offers a wide variety of generic container classes?

On another note you shouldn't be using a linked list if you have to call the find-operation often because it performs poorly on a list.
Better use a hashtable or search tree.

I'd recommend using a set< ID > from the STL.
Make ID a struct or class, you'll have to implement the ==operator for it to work smooth.
Good Luck.

12-31-2006, 09:39 PM

wyrmlord

I don't want to use the namespace std because it multiplies the size of my program using my compiler. A simple hello world program on my compiler compiled to something like 200kb on Dev C++ and 40kb on Visual C++. My program is currently about 8-9kb in size. Anyways, as you said it was referring to the address of a variable instead of the actual value. What I'm doing in my main file is reading from a file and then adding that value to the list (I could probably change the data structure later). I figured that I needed a variable to read the data into the list, so I did that.

Now, I really just want to be able to refer to the value stored in the variable instead of the address. You mentioned having the variable in a struct or class, how exactly would that work in this situation?

Another guess I have would be to just malloc new memory for each string I want to add, and then free all that memory when destroying the list. How well would this work?

12-31-2006, 09:46 PM	#4
Vexorian	200Kb is almost nothing, and you'd eventually have to use std anyways.

12-31-2006, 09:49 PM	#5
karukef	Amazing how some people are still trying to save the most insignificant amount of bytes at the cost of multiplying the time it takes to develop something by a factor of hundreds.

12-31-2006, 09:51 PM	#6
wyrmlord	I guess, but for this simple of a program I don't think that's entirely needed. The malloc for each string I want to add is working fine. EDIT: I'm going to clock the speed of the program. Okay, the speed of the program on a small file that was about 19kb was 15ms for the entire program. Now, on a 239kb .doo file, it took 200ms which I see as perfectly fast enough.