Thread: failure to write a circular list

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    662

    failure to write a circular list

    i have the following code (with some extra bits i haven't programmed yet as the first half isn't working)

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    enum DAY {MON = 1, TUES, WED, THURS, FRI, SAT, SUN};
    enum MONTH {JAN = 1, FEB, MARCH, JUNE, JULY, AUG, SEPT, OCT, NOV, DEC};
    
    typedef struct Days_Node
    {
        int day_num;
        char *weekday;
        struct Days_Node *next;
    }Days_Node;
    
    typedef struct Months_Node
    {
        int month_num;
        char *month;
        struct Months_Node *next;
    }Months_Node;
    
    
    typedef struct Lists
    {
        struct Days_Node *current_day;
        struct Months_Node *current_month;
    }Lists;
    
    Days_Node *get_day_memory(void);
    Months_Node *get_month_memory(void);
    char *get_string_memory(int x);
    void add_day_node(Lists *calender);
    void add_month_node(Lists *calender);
    void free_list(Lists *calender);
    int main()
    {
        int i;
        Lists calender;
    
        calender.current_day = NULL;
        calender.current_month = NULL;
        add_day_node(&calender);
        while (calender.current_day->day_num != MON)
        {
            calender.current_day = calender.current_day->next;
        }
    
        for (i = 1; i < 15; i++)
        {
            printf("day of the week is %s\n", calender.current_day->weekday);
            calender.current_day = calender.current_day->next;
            if (calender.current_day->next == NULL)
            {
                printf("not circular\n");
            }
        }
        free_list(&calender);
    
        return 0;
    }
    
    Days_Node *get_day_memory(void)
    {
        return malloc(sizeof(Days_Node));
    }
    
    Months_Node *get_month_memory(void)
    {
        return malloc(sizeof(Months_Node));
    }
    
    char *get_string_memory(int x)
    {
        return (char *)malloc(x + 1);
    }
    
    void add_day_node(Lists *calender)
    {
        int i;
        char *days[] = {"", "Monday", "Tuesday", "Wendnesday", "Thursday", "Friday", "Saturday", "Sunday"};
        Days_Node *current_tmp = NULL;
    
        for (i = 1; i < 8; i++)
        {
            Days_Node *tmp_node = get_day_memory();
    
            if (!tmp_node)
            {
                fprintf(stderr, "unable to allocate memory");
                exit(EXIT_FAILURE);
            }
            calender->current_day = tmp_node;
            if (i == 1)
            {
                current_tmp = tmp_node;
            }
            tmp_node->day_num = i;
            tmp_node->weekday = get_string_memory(strlen(days[i]));
            strcpy(tmp_node->weekday, days[i]);
            tmp_node->next = NULL;
            tmp_node->next = calender->current_day;
            calender->current_day = tmp_node;
        }
        calender->current_day->next = current_tmp;
    }
    void add_month_node(Lists *calender);
    void free_list(Lists *calender)
    {
        Days_Node *tmp_node = calender->current_day->next;
    
        calender->current_day->next = NULL;
        calender->current_day = tmp_node;
    
        while(calender->current_day->next)
        {
            tmp_node = calender->current_day->next;
            free(calender->current_day->weekday);
            free(calender->current_day);
            calender->current_day = tmp_node;
            printf("freed memory\n");
        }
    }
    im sure im doing something screwy with linking the head node to the tail node (current_tmp) but cant for the life of me figure out how else to do it.
    coop

  2. #2
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    sorry all the gets printed out is Monday 14 times.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,253
    Well did you check the structure of the circular list after adding just ONE node?

    What about after adding two nodes?

    99% of the time, your algorithm will be broken on one of those cases.
    If you can add two successfully, then chances are good that you can add 7.

    Put the actual add_node into a separate function that just adds a node to the circular list.
    The loop, and the data copying is a separate task.
    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.

  4. #4
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    enum DAY {MON = 1, TUES, WED, THURS, FRI, SAT, SUN};
    enum MONTH {JAN = 1, FEB, MARCH, JUNE, JULY, AUG, SEPT, OCT, NOV, DEC};
    
    typedef struct Days_Node
    {
        int day_num;
        char *weekday;
        struct Days_Node *next;
    }Days_Node;
    
    typedef struct Months_Node
    {
        int month_num;
        char *month;
        struct Months_Node *next;
    }Months_Node;
    
    
    typedef struct Lists
    {
        struct Days_Node *current_day;
        struct Months_Node *current_month;
    }Lists;
    
    Days_Node *get_day_memory(void);
    Months_Node *get_month_memory(void);
    char *get_string_memory(int x);
    void add_day_node(Lists *calender);
    void set_day_data(Days_Node *node, int x);
    void add_month_node(Lists *calender);
    void free_list(Lists *calender);
    int main()
    {
        int i;
        Lists calender;
    
        calender.current_day = NULL;
        calender.current_month = NULL;
        add_day_node(&calender);
        while (calender.current_day->day_num != MON)
        {
            calender.current_day = calender.current_day->next;
        }
    
        for (i = 1; i < 5; i++)
        {
            printf("day of the week is %s\n", calender.current_day->weekday);
            calender.current_day = calender.current_day->next;
            if (calender.current_day->next == NULL)
            {
                printf("not circular\n");
            }
        }
        free_list(&calender);
    
        return 0;
    }
    
    Days_Node *get_day_memory(void)
    {
        return malloc(sizeof(Days_Node));
    }
    
    Months_Node *get_month_memory(void)
    {
        return malloc(sizeof(Months_Node));
    }
    
    char *get_string_memory(int x)
    {
        return (char *)malloc(x + 1);
    }
    
    void add_day_node(Lists *calender)
    {
        int i;
        Days_Node *current_tmp = NULL;
    
        for (i = 1; i < 3; i++)
        {
            Days_Node *tmp_node = get_day_memory();
            calender->current_day = tmp_node;
            if (i == 1)
            {
                current_tmp = tmp_node;
            }
            set_day_data(tmp_node, i);
            tmp_node->next = NULL;
            tmp_node->next = calender->current_day;
            calender->current_day = tmp_node;
        }
        calender->current_day->next = current_tmp;
        current_tmp->next = calender->current_day;
    }
    
    void set_day_data(Days_Node *node, int x)
    {
        char *days[] = {"", "Monday", "Tuesday", "Wendnesday", "Thursday", "Friday", "Saturday", "Sunday"};
    
        if (!node)
        {
            fprintf(stderr, "unable to allocate memory");
            exit(EXIT_FAILURE);
        }
        node->day_num = x;
        node->weekday = get_string_memory(strlen(days[x]));
        strcpy(node->weekday, days[x]);
    }
    
    void add_month_node(Lists *calender);
    void free_list(Lists *calender)
    {
        Days_Node *tmp_node = calender->current_day->next;
    
        calender->current_day->next = NULL;
        calender->current_day = tmp_node;
    
        while(calender->current_day->next)
        {
            tmp_node = calender->current_day->next;
            free(calender->current_day->weekday);
            free(calender->current_day);
            calender->current_day = tmp_node;
            printf("freed memory\n");
        }
    }
    1 node prints out monday 4 times
    2 nodes prints out monday tuesday twice
    3 nodes prints out monday wednesday twice. it looses the tuesday

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,253
    Code:
    (gdb) run
    Starting program: a.out 
    
    Breakpoint 1, add_day_node (calender=0x7fffffffde40) at foo.c:94
    94	        calender->current_day = tmp_node;
    (gdb) p tmp_node 
    $1 = (Days_Node *) 0x603010
    (gdb) p *tmp_node 
    $2 = {day_num = 1, weekday = 0x603030 "Monday", next = 0x603010}
    (gdb) c
    Continuing.
    
    Breakpoint 1, add_day_node (calender=0x7fffffffde40) at foo.c:94
    94	        calender->current_day = tmp_node;
    (gdb) p tmp_node 
    $3 = (Days_Node *) 0x603050
    (gdb) p *tmp_node 
    $4 = {day_num = 2, weekday = 0x603070 "Tuesday", next = 0x603050}
    (gdb) c
    Continuing.
    
    Breakpoint 1, add_day_node (calender=0x7fffffffde40) at foo.c:94
    94	        calender->current_day = tmp_node;
    (gdb) p tmp_node 
    $5 = (Days_Node *) 0x603090
    (gdb) p *tmp_node 
    $6 = {day_num = 3, weekday = 0x6030b0 "Wendnesday", next = 0x603090}
    Every node points to itself.

    If you're not drawing diagrams like this, then start doing so.failure to write a circular list-circular_list-jpg
    It will help you figure out what needs to be assigned, and in what order.

    Here is some new code for you to study.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    enum DAY {MON = 1, TUES, WED, THURS, FRI, SAT, SUN};
    enum MONTH {JAN = 1, FEB, MARCH, JUNE, JULY, AUG, SEPT, OCT, NOV, DEC};
    
    typedef struct Days_Node
    {
        int day_num;
        char *weekday;
        struct Days_Node *next;
    }Days_Node;
    
    typedef struct Months_Node
    {
        int month_num;
        char *month;
        struct Months_Node *next;
    }Months_Node;
    
    
    typedef struct Lists
    {
        struct Days_Node *current_day;
        struct Months_Node *current_month;
    }Lists;
    
    struct Days_Node  *debugDays[100];
    int                ndebugDays = 0;
    
    
    Days_Node *get_day_memory(void);
    Months_Node *get_month_memory(void);
    char *get_string_memory(int x);
    void add_day_node(Lists *calender);
    void set_day_data(Days_Node *node, int x);
    void add_month_node(Lists *calender);
    void free_list(Lists *calender);
    int main()
    {
        int i;
        Lists calender;
    
        calender.current_day = NULL;
        calender.current_month = NULL;
        add_day_node(&calender);
        for ( i = 0 ; i < ndebugDays ; i++ ) {
            printf("self=%p next=%p\n", debugDays[i], debugDays[i]->next);
        }
        while (calender.current_day->day_num != MON)
        {
            calender.current_day = calender.current_day->next;
        }
    
        for (i = 1; i < 5; i++)
        {
            printf("day of the week is %s\n", calender.current_day->weekday);
            calender.current_day = calender.current_day->next;
            if (calender.current_day->next == NULL)
            {
                printf("not circular\n");
            }
        }
        free_list(&calender);
    
        return 0;
    }
    
    Days_Node *get_day_memory(void)
    {
        Days_Node *result = malloc(sizeof(Days_Node));
        debugDays[ndebugDays++] = result;
        return result;
    }
    
    Months_Node *get_month_memory(void)
    {
        return malloc(sizeof(Months_Node));
    }
    
    char *get_string_memory(int x)
    {
        return (char *)malloc(x + 1);
    }
    
    void adder(Lists *calender, Days_Node *node)
    {
        if ( calender->current_day == NULL )
        {
            // empty
            calender->current_day = node;
            node->next = node;
        }
        else
        {
            // more than one node
            node->next = calender->current_day->next; // A
            calender->current_day->next = node;       // B
            calender->current_day = node;             // C
        }
    }
    
    void add_day_node(Lists *calender)
    {
        int i;
        for (i = 1; i < 4; i++)
        {
            Days_Node *tmp_node = get_day_memory();
            set_day_data(tmp_node, i);
            tmp_node->next = NULL;
            adder(calender, tmp_node);
        }
    }
    
    void set_day_data(Days_Node *node, int x)
    {
        char *days[] = {"", "Monday", "Tuesday", "Wendnesday", "Thursday", "Friday", "Saturday", "Sunday"};
    
        if (!node)
        {
            fprintf(stderr, "unable to allocate memory");
            exit(EXIT_FAILURE);
        }
        node->day_num = x;
        node->weekday = get_string_memory(strlen(days[x]));
        strcpy(node->weekday, days[x]);
    }
    
    void add_month_node(Lists *calender);
    void free_list(Lists *calender)
    {
        Days_Node *tmp_node = calender->current_day->next;
    
        calender->current_day->next = NULL;
        calender->current_day = tmp_node;
    
        while(calender->current_day->next)
        {
            tmp_node = calender->current_day->next;
            free(calender->current_day->weekday);
            free(calender->current_day);
            calender->current_day = tmp_node;
            printf("freed memory\n");
        }
    }
    Key points.
    1. The adder does exactly ONE thing, and one thing only! You need to stop trying to do too much in each function.
    2. The ABC comments in the code of adder() relate to the picture.
    3. Don't be afraid to add debug code such as the debugDays. You can do anything you like if you think it will add clarity or insight into what is going on.

    Code:
    $ ./a.out 
    self=0x1615010 next=0x1615050
    self=0x1615050 next=0x1615090
    self=0x1615090 next=0x1615010
    day of the week is Monday
    day of the week is Tuesday
    day of the week is Wendnesday
    day of the week is Monday
    freed memory
    freed memory
    You can see in the debug each .next does point to the next self, and the last one points back to the start.


    I'll leave you to fix your free loop.
    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.

  6. #6
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    wow thank you. i was trying to watch the address's of the nodes in the watch window with breakpoints in my ide and was tying myself up in knots your way is so much clearer.

  7. #7
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    may i just check that im getting the pointer for the string (week day) correctly on line 84

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,253
    That's fine.
    The cast is redundant though.
    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.

  9. #9
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i wasnt sure if as i was using "integers" ie x + 1 to denote the size of the block of memory i needed to cast it to it knew i wanted char rather than int. i suppose if i had thought about it i could of said sizeof(char) * (x+1)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help on circular list!
    By flexo87 in forum C Programming
    Replies: 2
    Last Post: 01-30-2009, 02:35 PM
  2. Circular linked list
    By campermama in forum C++ Programming
    Replies: 7
    Last Post: 06-15-2004, 11:53 AM
  3. Again, Circular Linked list ???
    By yescha in forum C Programming
    Replies: 2
    Last Post: 11-16-2001, 08:35 PM
  4. Circular Linked List ??
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-14-2001, 02:12 PM
  5. Is it circular link list?
    By BigAl in forum C Programming
    Replies: 5
    Last Post: 11-01-2001, 06:48 PM

Tags for this Thread