Sign in to follow this  

Problem with accessing data in a node

This topic is 4385 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, so I'm making my own linked list system. I've come a long way I think, and so I finally decided to test it just to see if it was working. When looking at this code, please be aware that it's basically just consisting of hacks that I've made along the way. What I'm trying to do is that I'm trying to access the integer "i" in the test struct that I've made. Linked List System.cpp:
#include "Linked List System.h"
#include <iostream.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

ListNode CreateNode(ptr p, LinkedList List)
{
	ListNode Node;
	ptr MemPtr = NULL;
	ListNode *FirstNodePtr = List.FirstNode; //Pointer to the first node of the linked list.

	MemPtr = malloc(sizeof(p)); //Make a space in memory the size of p.
	MemPtr = memcpy(MemPtr, p, sizeof(p)); //Copy the data in p to the new memory area. 
	Node.p = MemPtr; //Make Node.p point to the new memory area.

	if(List.FirstNode == NULL)
	{
		List.FirstNode = &Node; //Make this the first node if a first node doesn't exist.
	}
	
	while(FirstNodePtr != NULL)
	{
		FirstNodePtr = FirstNodePtr -> NextNode; 
		
		if(FirstNodePtr == NULL)
		{
			FirstNodePtr -> NextNode = &Node;
			FirstNodePtr = List.FirstNode; //Reset the pointer to the first node in the list.
		}	
	}

	return Node;
}

LinkedList CreateList(void)
{
	LinkedList List;

	List.capacity = 0;
	List.FirstNode = NULL;

	return List;
}

void DeleteNode(ListNode Node)
{
	//Make sure that the last node's NextNode pointer points to this node's next node.
	Node.LastNode -> NextNode = Node.NextNode;
	Node.LastNode = NULL;
	Node.NextNode = NULL;
	free(Node.p);
}

typedef struct _TEST
{
	int i;
} Test;

int main()
{
	LinkedList List = CreateList();
	Test t;
	ptr p = &t;
	ListNode *FirstNodePtr = List.FirstNode; //Pointer to the first node of the linked list.
	
	for(int i=0;i<3;i++)
	{
		ListNode Node = CreateNode(p, List);
	}

	while(FirstNodePtr != NULL)
	{
		FirstNodePtr = FirstNodePtr -> NextNode;
		cout << "t.i = " << FirstNodePtr -> p -> i;  
	}

	return 0;
}

Linked List System.h:
#ifndef LIST_H
#define LIST_H

typedef void * ptr;

typedef struct _LISTNODE
{
	struct _LISTNODE *NextNode;
	struct _LISTNODE *LastNode;
	ptr p;
} ListNode; //This is a typedef for the struct.

typedef struct _LINKEDLIST
{
	ListNode *FirstNode;
	int capacity;
} LinkedList;

#endif
Ok, so what I'm having problems with is this part, that actually tries to access the data:
	cout << "t.i = " << FirstNodePtr -> p -> i;  
That line gives me this error:
--------------------Configuration: Linked List System - Win32 Debug--------------------
Compiling...
Linked List System.cpp
C:\Programs\C++\Linked List System\Linked List System\Linked List System.cpp(75) : error C2227: left of '->i' must point to class/struct/union
Error executing cl.exe.

Linked List System.exe - 1 error(s), 0 warning(s)

Any idea why? BTW: Should I stop posting in the "For beginners" forum now? [cool]

Share this post


Link to post
Share on other sites
p is a void * which means you can't dereference it with operator-> as it has no type. You need to cast p to a type before you can dereference it.

Share this post


Link to post
Share on other sites
Not to be offensive, but that question indicates that you should probably still be posting in For Beginners. Since you added a Test object you should use a cast to a Test pointer. ex: static_cast<Test *>(FirstNodePtr->p)

Share this post


Link to post
Share on other sites
Thanks!

Changed to this now:

[source lang="	while(FirstNodePtr != NULL)
{
FirstNodePtr = FirstNodePtr -> NextNode;
static_cast<Test *>(FirstNodePtr -> p) -> i++;
cout << "t.i = " << static_cast<Test *>(FirstNodePtr -> p) -> i;
}"


Problem is that the program still doesn't print anything! Seriously, it doesn't even print the text in the cout statement! [bawling]

Share this post


Link to post
Share on other sites
You have some problems with your code

Quote:

LinkedList CreateList(void)
{
LinkedList List;

List.capacity = 0;
List.FirstNode = NULL;

return List;
}


This will probably not work as you intended.
The List object is both created and destroyed (automatically) inside the CreateList function, so the return value is undefined.

I have a small C-style list if you want to take a look

#include <stdio.h>
#include <malloc.h>

typedef struct _NODE {
int *val;
_NODE *next;
} NODE;

typedef struct _LIST {
NODE *head, *tail;
} LIST;

void list_insert_front(LIST *lst, int value)
{
NODE *new_node = (NODE*)malloc(sizeof(NODE));
new_node->val = (int*)malloc(sizeof(int));
*new_node->val = value;

// inserting at front (easy)
new_node->next = lst->head;
lst->head = new_node;
}

void list_print(LIST *lst)
{
NODE *n = lst->head;
while(n) {
printf("%d ", *n->val);
n = n->next;
}
printf("\n");
}

void list_destroy(LIST *lst)
{
NODE *n = lst->head;
while(n) {
NODE *doe = n;
n = n->next;
free(doe->val);
free(doe);
}
lst->head = lst->tail = NULL;
}

int main()
{
LIST list;
list.head = list.tail = NULL;

for(int i=0; i<8; i++)
list_insert_front(&list, i);

list_print(&list);

list_destroy(&list);
return 0;
}

Share this post


Link to post
Share on other sites
Thanks!

You seem to not have a createlist function.. how come? I tried not using my CreateList function in the main function, but that made the compiler complain about "Local variable 'List' used without having been initialized!". I also tried modifying the CreateList function so that List was passed a parameter, but that resulted in a program that didn't print anything. What on earth is wrong? :\

Share this post


Link to post
Share on other sites
If you want the CreateList function to work, you could change it to something like this


LinkedList* CreateList(void)
{
LinkedList *List = (LinkedList*)malloc(sizeof(LinkedList));

List->capacity = 0;
List->FirstNode = NULL;

return List;
}

and a DeleteList function to go along with it

void DeleteList(LinkedList* &lst)
{
// delete each node in the list...
// delete the list itself, and set it to NULL...
}


By using C++ some of these "syntactic acrobatics" can be avoided, for example


#include <iostream>
using namespace std;

template<class T>
class Node {
public:
Node() : next(NULL), val(NULL) {}
~Node() {}

Node *next;
T *val;
};

template<class T>
class List
{
Node<T> *head, *tail;

public:
List() : head(NULL), tail(NULL) {}
~List() { remove_all(); }

void insert_front(const T& value)
{
Node<T> *new_node = new Node<T>;
new_node->val = new T;
*new_node->val = value;

new_node->next = head;
head = new_node;
}

void remove_all()
{
Node<T> *n = head;
while(n)
{
Node<T> *doe = n;
n = n->next;
delete doe->val;
delete doe;
}
head = tail = NULL;
}

friend ostream& operator << (ostream &out, const List<int>& list);
};

ostream& operator << (ostream &out, const List<int>& list)
{
Node<int> *n = list.head;
while(n) {
out << *n->val << " ";
n = n->next;
}
out << endl;
return out;
}

int main()
{
List<int> ilist;

for(int i=0; i<8; i++)
ilist.insert_front(i);

cout << ilist << endl;
return 0;
}



Quote:

What on earth is wrong? :

You have a few errors in your code, so
Ill rather show you my own list and let you discover them yourself.
(My examples are very simplistic though, and should have atleast one way to remove a single node from the list to be somewhat complete)

Hope it helps ^^

[Edited by - pulpfist on December 5, 2005 10:38:14 AM]

Share this post


Link to post
Share on other sites
Of course, in C++ it is normal and sane to just use std::list :) Here are a few of the design things that are done differently by the std::list and normal implementations thereof:

- Templates are used to avoid having to cast from void*. This also implies that you can make a list to hold any type you like, but for any given list, all contents are of the same type. It also implies that code is basically generated for each type of list that actually gets used within the code. In well-designed C++ code, meaningful use of void* is exceedingly rare. It is basically a request to take all of the improvements that C++ makes over C's type system and throw them out the window.

- Everything is done in new, proper, "modern" style instead of working with ancient libraries and methods that only still exist for "bend-over-backwards compatibility" with C. So for example, the node struct is declared *without* the "typedef struct idiom" (which is meaningless in C++), nodes are allocated using new and deallocated using delete (which allows for constructors and destructors to be called - copying objects bitwise via memcpy() is not safe for objects that contain pointers or which are designed for polymorphism), and stuff is done to a list using member functions of the list object.

Also, while the headers in your project aren't needed for the list implementation really (except stdlib.h for malloc() - note that including malloc.h explicitly is redundant) but just for testing, you should be aware that:

- "iostream.h" is now properly spelled "iostream", and the necessary symbols should be imported from the std namespace.
- "stdlib.h", similarly, is now properly spelled "cstdlib", but you should hardly ever need it in good C++ code.
- "string.h" isn't actually used for anything you're doing, and furthermore has nothing to do with what good C++ developers call a "string". It is properly spelled "cstring" and provides access to strcpy() and all of that, but it is a better idea to use "string" - a modern header - and the C++ std::string object to represent text. It will save many, many headaches in the long run.

- The code is written in such a way that users do not need to know about the existance of list nodes. If you tell the list to "add" some value, it will create a node to store that value, and then append the node to the list. This is the concept of "encapsulation", and it is a very good thing. It prevents having to do lots of work all over the code, by doing it in the one place where it ought to be done.

The example code can be written as follows:


// No .h file of our own.
#include <iostream>
#include <list>
#include <iterator>
using namespace std;

struct test {
int i;
};

int main() {
list<test> myList; // we don't need to write an initializer; we use the
// default constructor here.
test t;
// Put a value into our test struct so that there is something valid to
// print out. BTW, just in case you weren't aware - the 'i' in your loop
// from before has nothing to do with the 'i' member of any given instance
// of the test struct.
t.i = 1;
// Insert three copies of that struct into the list.
for (int i = 0; i < 3; ++i) {
myList.push_back(t);
}
// Iterate through the list and print each value.
for (list<test>::iterator it = myList.begin(); it != myList.end(); ++it) {
cout << "t.i = " << it->i;
}
// All the memory is automatically cleaned up at this point by the
// destructor of the list object - something your code does not attempt.
}

Share this post


Link to post
Share on other sites
Thanks guys this has gotten me a step closer! Zahlman, if I can't get my code to work, I'll look into STL, for sure. But I'd really like to get my code to work because I think it's important to learn about data structures since I'm looking for a job in the industry. Thanks anyway though!

Share this post


Link to post
Share on other sites
Ok guys I have another problem! :( Thanks to a companion and VC2005's outstanding debugger, I've managed to fix the code so that it compiles and runs perfectly. However, I am supposed to get a printout that looks something like this:

"t.i = 1
t.i = 2
t.i = 3"

However I just get this:

"t.i = 1
t.i = 1
t.i = 1"

And I've no idea why this is! :\ Maybe there's just something wrong with my test code or maybe with the actual linked list system itself. :( I've tried to fix this problem for a long time but now I've given up. Could someone please help? Here's the updated source:

	#include "Linked List System.h"
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

using namespace std;

ListNode& CreateNode(ptr p, LinkedList& List)
{
ListNode& Node = *(new ListNode);
memset( &Node, 0, sizeof( ListNode ) );
ptr MemPtr = NULL;
ListNode *FirstNodePtr = List.FirstNode; //Pointer to the first node of the linked list.

MemPtr = malloc(sizeof(p)); //Make a space in memory the size of p.
MemPtr = memcpy(MemPtr, p, sizeof(p)); //Copy the data in p to the new memory area.
Node.p = MemPtr; //Make Node.p point to the new memory area.

if(List.FirstNode == NULL)
{
List.FirstNode = &Node; //Make this the first node if a first node doesn't exist.
return Node;
}

while(FirstNodePtr != NULL)
{
if(FirstNodePtr -> NextNode == NULL)
{
FirstNodePtr -> NextNode = &Node;
return Node;
}
FirstNodePtr = FirstNodePtr -> NextNode;
}
}

LinkedList& CreateList()
{
LinkedList& List = *(new LinkedList);
memset( &List, 0, sizeof( ListNode ) );

return List;
}

void DeleteNode(ListNode& Node)
{
//Make sure that the last node's NextNode pointer points to this node's next node.
if ( Node.LastNode )
Node.LastNode -> NextNode = Node.NextNode;
if ( Node.NextNode )
Node.NextNode -> LastNode = Node.LastNode;
free(Node.p);
}

typedef struct _TEST
{
int i;
} Test;

int main()
{
LinkedList List = CreateList();
Test t;
ptr p = &t;

t.i = 0;

for(int i=0;i<3;i++)
{
CreateNode(p, List);
}

ListNode *FirstNodePtr = List.FirstNode; //Pointer to the first node of the linked list.

while(FirstNodePtr != NULL)
{
static_cast<Test *>(FirstNodePtr -> p) -> i++;
cout << "t.i = " << static_cast<Test *>(FirstNodePtr -> p) -> i;
cout << "\n";
FirstNodePtr = FirstNodePtr -> NextNode;
}

system("PAUSE");
return 0;
}

Share this post


Link to post
Share on other sites
Can I recommend that you re-read Zahlman's post. It is good advice.

OK. Done? Now let me throw in my £0.0114179. Stop using void *. Seriously. At this stage it will only teach you bad habbits. Either learn how to write typesafe generic code using templates, or write datastructures hardcoded for specific types (for learning data structures) or just use the standard library. void *s are evil. Here's an example from your code as to why:

MemPtr = malloc(sizeof(p)); //Make a space in memory the size of p.
MemPtr = memcpy(MemPtr, p, sizeof(p)); //Copy the data in p to the new memory area.


You're trying to allocate sufficient memory to store an object of whatever type. You're not. You're allocating exactly four bytes on a 32bit machine. If your object is really eight bytes is size then all you're doing is allocating four bytes and copying the first half of your object into it. void * does not know about type. Are you convinced about void * yet?

Finally, to answer your question: The reason your code is printing three '1's is because that's what you asked it to do. You insert three Test objects into the list, all with value zero (fortunately sizeof(Test) happens to equal sizeof(void *)). You then increment each element once. So the first element is incremented from '0' to '1' and then printed. Then the second element is incremented from '0' to '1' and then printed, etc.

Enigma

Share this post


Link to post
Share on other sites
Thanks for that answer, Enigma! I was having problems following the test code's logical progression. Anyhow, I really don't like to waste code. I read Zahlman's post and looked into STD but I chose to go with this in the end since I was so close to finishing it. So... is there a way to pass whatever p is pointing to as an argument to malloc(), or have I bumped into an inpenetrable wall? I don't care if it's difficult to understand.. I will learn to understand it if need be. I just need an answer. I tried doing malloc(*p), but that gave me an error. :(

Share this post


Link to post
Share on other sites
Quote:
Original post by Afr0m@n
Thanks for that answer, Enigma! I was having problems following the test code's logical progression. Anyhow, I really don't like to waste code. I read Zahlman's post and looked into STD but I chose to go with this in the end since I was so close to finishing it. So... is there a way to pass whatever p is pointing to as an argument to malloc(), or have I bumped into an inpenetrable wall? I don't care if it's difficult to understand.. I will learn to understand it if need be. I just need an answer. I tried doing malloc(*p), but that gave me an error. :(


No. There is no accessible run-time information about the size of the data involved unless you track it yourself, and making use of void* obliterates all compile-time information about the data size.

Share this post


Link to post
Share on other sites
Heh.. was with my grandfather till today, and had a bit of a chillout. So, apparently there doesn't seem to be a way to do what I want "directly" (thanks again, Zahlman!). However, I found a neat little hack while chilling out at grandpa's house. What I'll do is that I'll pass a buf variable to the CreateNode function, so that the "equation" becomes:

MemPtr = malloc(sizeof(buf));


instead of the aforementioned:

MemPtr = malloc(sizeof(p));


This way, before using the function, I can do something like:

buf = sizeof(test_struct);


Now there's really only one question left. Does the size of a struct increase when adding data to it? The answer may be obvious, but I've no idea of the answer. If the answer is yes, I'll have to add a few bytes to the size of the buf variable. This will give me a small overhead because I'll never have the exact amounts of bytes needed, but it shouldn't be that bad, because I know more or less the amount of bytes I will need for each type of struct. Could anyone please answer this?

Share this post


Link to post
Share on other sites
Yes

If you add a pointer to the struct/class the size will increase 4 bytes in size (regardless of what if points to, and if it points to allocated memory or not)
The sizeof operator is a hot topic around here so I wont advice you to use it for testing purposes ^^

Share this post


Link to post
Share on other sites

This topic is 4385 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this