LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (http://www.linuxquestions.org/questions/programming-9/)
-   -   C Lists (http://www.linuxquestions.org/questions/programming-9/c-lists-629865/)

rubadub 03-22-2008 10:42 AM

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);
        }
}


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 (Post 3097028)
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?


All times are GMT -5. The time now is 07:39 PM.