C Lists

rubadub · 03-22-2008, 10:42 AM

Hi, i'm revising my old self referential structures, basically a two way list. I'm at a point where i'm rewriting 'add' into 'append' and i'm thinking I can avoid returning a structure. However if I do and then try to access the last element it returns the one before, yet if I print the whole list then the last element is there... (why?)

main.c

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rclist.h"

int main()
{
	int i;
	struct rclist *root;
	root = NULL;
	char *directions[64] = { "N", "NE", "E", "SE", "S", "SW", "W", "NW" };
	
	//	ADD MORE NODES
	for(i=0;i<8;i++)
	{
		root = add_node(directions[i], root);
	}
	
	//	PRINT LIST
	struct rclist *r = find_first_node(root);
	print_list(r);
	printf("\n");
	
	r = find_last_node(root);
	print_node(r);
	printf("\n");
	
	r = find_first_node(root);
	print_node(r);
	printf("\n");
	
	r = find_node_at(root, 3);
	print_node(r);
	printf("\n");
	
	//root = rclist_append("hello", root);
	rclist_append("hello", r);
	r = find_last_node(r);
	printf("> ");
	print_node(r);
	printf("\n");
	
	/*
	r = find_first_node(root);
	print_list(r);
	printf("\n");
	*/
	
	return 0;
}

rclist.h

Code:

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

struct rclist
{
	char *s;
	struct rclist *down;
	struct rclist *up;
};

struct rclist *add_node(char * s, struct rclist *last);

void rclist_append(char *s, struct rclist *root);
//struct rclist *rclist_append(char *s, struct rclist *root);

struct rclist *find_next_node(struct rclist *root);
struct rclist *find_node_at(struct rclist *root, int pos);
struct rclist *find_first_node(struct rclist *root);
struct rclist *find_last_node(struct rclist *root);

void print_node(struct rclist *root);
void print_list(struct rclist *root);

void rclist_append(char *s, struct rclist *root)
//struct rclist *rclist_append(char *s, struct rclist *root)
{
	root = find_last_node(root);
	struct rclist *r;
	if((r = (struct rclist*) malloc(sizeof(struct rclist))) != NULL)
	{
		if((r->s = (char*) malloc(strlen(s) + 1)) != NULL)
		{
			strcpy(r->s, s);
			r->up = NULL;
			root->up = r;
			r->down = root;
		}
	}
	//return r;
}

struct rclist *add_node(char *s, struct rclist *last)
{
	struct rclist *this;
	if((this = (struct rclist*) malloc(sizeof(struct rclist))) != NULL)
	{
		if((this->s = (char*) malloc(strlen(s) + 1)) != NULL)
		{
			strcpy(this->s, s);
			if(last != NULL)
			{
				this->up = NULL;
				last->up = this;
				
				this->down = last;
				
				//struct rclist *x = this->up;
				//x->down = this;
			}
			else
			{
				this->down = NULL;
				this->up = this;
			}
		}
		else
		{
			printf("Memory allocation error!\n");
			exit(-1);
		}
	}
	else
	{
		printf("Memory allocation error!\n");
		exit(-1);
	}
	
	return this;
}

struct rclist *find_next_node(struct rclist *root)
{
	if ( (root != NULL) )
	{
		if (root->up == NULL)
		{
			return NULL;
		}
		return root->up;
	}
}

struct rclist *find_node_at(struct rclist *root, int pos)
{
	int i = 0;
	root = find_first_node(root);
	while( (root) != NULL)
	{
		if(pos==i)
		{
			return root;
		}
		root = root->up;
		i++;
	}
	return NULL;
}

struct rclist *find_first_node(struct rclist *root)
{
	if ( (root != NULL) )
	{
		if (root->down == NULL)
		{
			return root;
		}
		root = find_first_node(root->down);
	}
	return root;
}

struct rclist *find_last_node(struct rclist *root)
{
	if ( (root != NULL) )
	{
		if (root->up == NULL)
		{
			return root;
		}
		root = find_first_node(root->up);
	}
	return root;
}

void print_node(struct rclist *root)
{
	if ( (root != NULL) )
	{
		printf("%s \n", root->s);
	}
}

void print_list(struct rclist *root)
{
	if ( (root != NULL) )
	{
		printf("%s \n", root->s);
		if (root->up == NULL)
		{
			return;
		}
		print_list(root->up);
	}
}

rubadub · 03-22-2008, 11:20 AM

Yip, a copy typo!
This function now reads as:

Code:

struct rclist *find_last_node(struct rclist *root)
{
	if ( (root != NULL) )
	{
		if (root->up == NULL)
		{
			return root;
		}
		root = find_last_node(root->up);
	}
	return root;
}

dmail · 03-22-2008, 11:21 AM

Code:

void rclist_append(char *s, struct rclist *root)
//struct rclist *rclist_append(char *s, struct rclist *root)
{
	root = find_last_node(root);
	struct rclist *r;
	if((r = (struct rclist*) malloc(sizeof(struct rclist))) != NULL)
	{
		if((r->s = (char*) malloc(strlen(s) + 1)) != NULL)
		{
			strcpy(r->s, s);
			r->up = NULL;
			root->up = r;
			r->down = root;
		}
	}
	//return r;
}

Why are you finding the last node and then inserting at the head?

rubadub · 03-22-2008, 11:23 AM

It's surely not? It creates new, then points last to it!

dmail · 03-22-2008, 11:31 AM

Sorry that was incorrect but it does look funky.

Code:

void rclist_append(char *s, struct rclist *root)
//struct rclist *rclist_append(char *s, struct rclist *root)
{
        /*root becomes the last node or null as root may have been null*/
	root = find_last_node(root);
	struct rclist *r;
	if((r = (struct rclist*) malloc(sizeof(struct rclist))) != NULL)
	{
		if((r->s = (char*) malloc(strlen(s) + 1)) != NULL)
		{
			strcpy(r->s, s);
                        /*new node's previous is null*/
                        /*which says to me that it is now the root*/
			r->up = NULL;
                        /*old last node previous is now the new*/
                        /*what happened to it previous that was there before*/
			root->up = r;
                        /*new node which has no previous now sets its next as the node which was the last */
			r->down = root;
		}
                else/*oops memory leak need to free r*/
                {
                   
                }
	}
	//return r;
}

rubadub · 03-22-2008, 11:36 AM

Yes, the error checking will be similar to 'add_node()' (in original e.g.).

Cheers

dmail · 03-22-2008, 11:41 AM

Maybe it is just me or you can not see what i am saying. If I rename the nodes maybe it will help

Code:

void rclist_append(char *s, struct rclist *root)
{
	struct rclist * old_end_node = find_last_node(root);
	struct rclist *new_node;
...
			new_node->up = NULL;
			old_end_node->up = new_node;
			new_node->down = old_end_node;
...
}

edit: anyway why traverse list to insert at the end when a list is an unsorted structure, just take pass the address of the head of the list and insert at the head.

rubadub · 03-22-2008, 11:54 AM

That's basically the same code as it is?

The append will also have an alias named 'push', and other functions such as pop, insert_at, remove_at, foreach(funcp), qsort. Maybe this doesn't fit the true name of a list, but since i'm self taught it's descriptive, what would you call it? P.S. This is very loosely based on the glist.h spec...

dmail · 03-22-2008, 12:03 PM

Quote:

That's basically the same code as it is?

REALLY? (yes caps are meant)

Quote:

Maybe this doesn't fit the true name of a list, but since i'm self taught it's descriptive, what would you call it

Personally I would call it a "messed up list which drops nodes for no good reason, is meant to be a double linked yet will not get to the root if you traverse from the end node".
Reread what you first said:

Quote:

However if I do and then try to access the last element it returns the one before

Hmmm I wonder why that could be????

Code:

...
			old_end_node->up = new_node;
...

rubadub · 03-22-2008, 12:16 PM

Quote:

Personally I would call it a "messed up list which drops nodes for no good reason, is meant to be a double linked yet will not get to the root if you traverse from the end node".

For that I have a looped list, also have a specific stack and tree.

Also:

Quote:

old_end_node->up = new_node;

Is the same as:

Code:

root->up = r;

The actual error (solution) was as stated somewhere between here and there, all works fine now! I'd added a 'count' function which after appending told me a nine element list only had two elements.

dmail · 03-22-2008, 12:22 PM

Quote:

Originally Posted by rubadub

For that I have a looped list, also have a specific stack and tree.

Also:

Is the same as:

Code:

root->up = r;

The actual error (solution) was as stated somewhere between here and there, all works fine now! I'd added a 'count' function which after appending told me a nine element list only had two elements.

Ok here is a tip for you, actually read what is being posted. I have not posted any new code until this point, it has just been your code which I have just "...rename(d) the nodes..."

Psuedo for what you want

Code:

append at end(node*)
old_end = find last node
new_end
fill new_end with details
set the old end nodes next pointer to the new node
set the new end node previous pointer to the old end node
set the new ends node to NULL

and the actual code without error checking

Code:

void rclist_append_to_end(char *s, struct rclist *root)
{
	struct rclist *old_end = find_last_node(root);
	struct rclist *new_end =  malloc(sizeof(struct rclist));
	new_end->s = malloc(strlen(s) + 1));
	strcpy(new_end->s, s);
	old_end->down = new_end;
	new_end->up = old_end;
	new_end->down = 0;
}

rubadub · 03-22-2008, 12:43 PM

The only difference I can see between your code and mine is that you go down and I build up, which beyond semantics is irrelevant? I first used lists with gl transform lists (which are basically stacks) so I find it natural to build up and not build down. Or is there another difference that i'm missing?