Like Tree6Likes
  • 1 Post By Salem
  • 1 Post By anduril462
  • 1 Post By laserlight
  • 1 Post By anduril462
  • 1 Post By grumpy
  • 1 Post By stahta01

every C learner's nightmare: linked lists

This is a discussion on every C learner's nightmare: linked lists within the C Programming forums, part of the General Programming Boards category; Hi all. I am getting errors, but I can't understand. h is the address of a pointer, and I am ...

  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 wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,335
    Try making get_list return a node*

    You call get_list recursively, so you need a better way of handling the empty string case.
    cfanatic likes this.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  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,288
    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).
    cfanatic likes this.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    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.
    cfanatic likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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,288
    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.
    cfanatic likes this.

  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
    5,843
    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.
    cfanatic likes this.
    Right 98% of the time, and don't care about the other 3%.

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    2,372
    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.
    cfanatic likes this.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

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, 12: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, 10:50 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21