LinuxQuestions.org
Visit the LQ Articles and Editorials section
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 03-22-2008, 10:42 AM   #1
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Rep: Reputation: 33
Question C Lists


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);
	}
}
 
Old 03-22-2008, 11:20 AM   #2
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
Wink

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;
}
 
Old 03-22-2008, 11:21 AM   #3
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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?
 
Old 03-22-2008, 11:23 AM   #4
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
It's surely not? It creates new, then points last to it!
 
Old 03-22-2008, 11:31 AM   #5
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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;
}

Last edited by dmail; 03-22-2008 at 11:32 AM.
 
Old 03-22-2008, 11:36 AM   #6
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
Yes, the error checking will be similar to 'add_node()' (in original e.g.).

Cheers
 
Old 03-22-2008, 11:41 AM   #7
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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.

Last edited by dmail; 03-22-2008 at 11:44 AM.
 
Old 03-22-2008, 11:54 AM   #8
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
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...
 
Old 03-22-2008, 12:03 PM   #9
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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;
...
 
Old 03-22-2008, 12:16 PM   #10
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
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.
 
Old 03-22-2008, 12:22 PM   #11
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
Quote:
Originally Posted by rubadub View Post
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;
}

Last edited by dmail; 03-22-2008 at 12:23 PM.
 
Old 03-22-2008, 12:43 PM   #12
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
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?
 
  


Reply

Tags
list, structure


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
linked lists Natasl Programming 5 08-04-2006 12:02 PM
I need lists deathbyswiftwin Linux - General 4 04-21-2006 07:10 PM
Linked Lists - What and Why? scuzzman Programming 9 12-31-2004 10:51 AM
Bug Lists backne Mandriva 0 10-20-2004 07:25 AM
Mailing Lists... Nezar Linux - Networking 0 03-25-2002 01:11 AM


All times are GMT -5. The time now is 05:29 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration