Thread: every C learner's nightmare: linked lists

  1. #1
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242

    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;
    Last edited by cfanatic; 09-21-2012 at 06:08 AM. Reason: added list.h
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Try making get_list return a node*

    You call get_list recursively, so you need a better way of handling the empty string case.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242
    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);
        }
    }
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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).

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by laserlight View Post
    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.

  7. #7
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242
    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);
        }
    }
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by cfanatic View Post
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  3. double linked-structure nightmare help
    By MalickT in forum C Programming
    Replies: 11
    Last Post: 05-14-2008, 11:33 AM
  4. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM
  5. Replies: 2
    Last Post: 11-28-2003, 11:50 AM