every C learner's nightmare: linked lists

Hi all.

I am getting errors, but I can't understand. h is the address of a pointer, and I am returning the address of a pointer, so why are the types incompatible? Also, is it better to create new links recursively, or iteratively? Thanks.

Code:

main.c||In function ‘main’:|
main.c|16|error: incompatible types when assigning to type ‘struct node *’ from type ‘node’|
main.c|14|warning: variable ‘h’ set but not used [-Wunused-but-set-variable]|
main.c||In function ‘get_list’:|
main.c|34|error: incompatible types when assigning to type ‘struct element *’ from type ‘node’|
main.c|36|error: incompatible types when returning type ‘struct node *’ but ‘node’ was expected|
main.c|37|warning: control reaches end of non-void function [-Wreturn-type]|
||=== Build finished: 3 errors, 2 warnings ===|

Code:

// linkedlist.c: creates a linked list from a string, counts the number of nodes, and prints the list
// 3 functions: get_list(), count_list(), print_list()

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

node get_list(char s[]);
int count_list();
void printlist();

int main(void)
{
    node *h;

    h = get_list("ABC");

    return 0;
}

node get_list(char s[])
{
    node *h;

    if(s[0] == '\0')
    {
        puts("Empty string");
        exit(1);
    }
    else
    {
        h = malloc(sizeof(node));
        h->data = s[0];
        h->next = get_list(s + 1);
    }
    return h;
}

list.h

Code:

struct element {
    char data;
    struct element *next;
};

typedef struct element node;

Try making get_list return a node*

You call get_list recursively, so you need a better way of handling the empty string case.

Code:

// linkedlist.c: creates a linked list from a string, counts the number of nodes, and prints the list
// 3 functions: get_list(), count_list(), print_list()

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

node *get_list(char s[]);
int count_list(node *h);
void print_list();

int main(void)
{
    node *h;

    h = get_list("ABC");
    printf("The resulting list is:\n");
    print_list(h);
    printf("\nThis list has %d elements.\n", count_list(h));

    return 0;
}

node *get_list(char s[])
{
    node *h;
    int ctr = 0;

    if(s[ctr] == '\0')
    {
        return NULL;
    }
    else
    {
        h = malloc(sizeof(node));
        h->data = s[ctr];
        h->next = get_list(s + 1);
    }
    return h;
}

int count_list(node *h)
{
    int ctr;

    if(h == NULL)
    {
        return 0;
    }
    else
    {
        ctr = (1 + count_list(h->next));
    }
    return ctr;
}

void print_list(node *h)
{
    if(h == NULL)
    {
        printf("NULL");
    }
    else
    {
        printf("%c --> ", h->data);
        print_list(h->next);
    }
}

It would really help if you told people whether their advice worked, instead of just posting some code with no comments about it. You should know that after 2 months and 100+ posts. Looks like it works though. A couple other little tips:

1. Use include guards in all your header files. When you move on to bigger projects where you have several .c files that all include one .h file (say your interface to a linked list module/library), it will avoid lots of problems with redefinition.

2. ctr is not necessary in get_list or count_list. In get_list, you can just use *s everywhere, it's the same as s[ctr] since ctr is always 0. In count_list, just return 1 + count_list(h->next).

Originally Posted by anduril462

1. Use include guards in all your header files. When you move on to bigger projects where you have several .c files that all include one .h file (say your interface to a linked list module/library), it will avoid lots of problems with redefinition.

Or rather, when you have several header files that include a certain header file, and which are themselves included in a source file, it will avoid lots of problems with redefinition.

Originally Posted by laserlight

Or rather, when you have several header files that include a certain header file, and which are themselves included in a source file, it will avoid lots of problems with redefinition.

Yes, you're right. Multiple .c files including the same header is only an issue if you define non-static globals in your header files, which is a problem not fixed by include guards.

Hmm...something odd. Why doesn't the compiler give any warnings or errors when the function prototype is:

Code:

void print_list();

and the function definition is:

Code:

void print_list(node *h)

The program seems to work fine. Shouldn't there be an error message about incompatible arguments?

Code:

// linkedlist.c: creates a linked list from a string, counts the number of nodes, and prints the list
// 3 functions: get_list(), count_list(), print_list()

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

node *get_list(char s[]);
int count_list(node *h);
void print_list();

int main(void)
{
    node *h;

    h = get_list("ABC");
    printf("The resulting list is:\n");
    print_list(h);
    printf("\nThis list has %d elements.\n", count_list(h));

    return 0;
}

node *get_list(char s[])
{
    node *h;

    if(*s == '\0')
    {
        return NULL;
    }
    else
    {
        h = malloc(sizeof(node));
        h->data = *s;
        h->next = get_list(s + 1);
    }
    return h;
}

int count_list(node *h)
{
    if(h == NULL)
    {
        return 0;
    }
    else
    {
        return (1 + count_list(h->next));
    }
}

void print_list(node *h)
{
    if(h == NULL)
    {
        printf("NULL");
    }
    else
    {
        printf("%c --> ", h->data);
        print_list(h->next);
    }
}

Originally Posted by cfanatic

Hmm...something odd. Why doesn't the compiler give any warnings or errors when the function prototype is:

Code:

void print_list();

and the function definition is:

Code:

void print_list(node *h)

That's C, albeit a deprecated feature. The declaration tells the compiler that there is a function named print_list(), but tells it nothing about how many argument it accepts. The () does not mean "no arguments", it means "any arguments may be passed".

An effect of that is that (within reason) any code calling link_list() will compile.

Code:

     print_list(some_list);
     print_list(some_list, some_other_list);

except that the second line here will only print out some_list (if extra arguments are supplied to a function, they are generally ignored in practice).

The danger of this is that is also allows the caller to forget to supply an argument, so

Code:

     print_list();

will also compile, but (probably) crash at run time, since the called function expects an argument, and tries to access something that does not exist.

It is generally considered poor form in C to write a function declaration that doesn't match the function definition, because it is easy to introduce bugs that are hard to find (like the above). If you want to declare a function with no arguments use "void whatever_name(void)".

I'll leave an explanation of why this happens in C to another day.

Instead of

Code:

void print_list();

Compare to this as the prototype.

Code:

void print_list(void);

In "C", the empty () does NOT mean it takes no parameters.
IIRC, it means it takes an unknown amount of int parameters.

Tim S.