Thread: someone please eplain the logic here

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

    someone please eplain the logic here

    here is the code
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        int number;
        struct Node *next;
    }Node;
    
    typedef struct Linkedlist
    {
        struct Node *head;
        struct Node *tail;
    }Linkedlist;
    
    int main()
    {
        int i, numbers[7] = {1,4,2,5,7,9,3};
        Node *tmp_node = NULL, *current;
        Linkedlist mylist, sortedlist;
    
        mylist.head = NULL;
        mylist.tail = NULL;
        sortedlist.head = NULL;
        sortedlist.tail = NULL;
    
        for (i = 0; i < 7; i++)
        {
            tmp_node = malloc(sizeof(tmp_node));
            if (!tmp_node)
            {
                printf("error aquiring memory\n");
                break;
            }
    
            tmp_node->number = numbers[i];
    
            if (!mylist.head) // list empty
            {
                mylist.head = tmp_node;
                mylist.tail = mylist.head;
            }
            else if (!mylist.head->next) //second node
            {
                mylist.head->next = tmp_node;
                mylist.tail = tmp_node;
                mylist.tail->next = NULL;
            }
            else // another node to append
            {
                tmp_node->next = NULL;
                mylist.tail->next = tmp_node;
                mylist.tail = tmp_node;
            }
        }
    
        //print list
        current = mylist.head;
        while (current)
        {
            printf("number = %d\n", current->number);
            current = current->next;
        }
    
        //sort list
        int youngest;
        Node *current_loop = mylist.head, *previous = NULL, *young_current, *young_previous;
    
        while (current_loop)
        {
            current = current_loop;
            previous = NULL;
            youngest = current_loop->number;
            young_current = current;
            young_previous = previous;
    
            while (current)
            {
                if (youngest > current->number)
                {
                    youngest = current->number;
                    young_current = current;
                    young_previous = previous;
                }
                previous = current;
                current = current->next;
            }
            //remove node from list
            if (young_current == mylist.head) //young current is the head
            {
                mylist.head = young_current->next;
                young_current->next = NULL;
            }
            else if (!young_current->next) //young current is the tail
            {
                young_previous->next = NULL;
            }
            else //middle node
            {
                young_previous->next = young_current->next;
                young_current->next = NULL;
            }
    
            //add node to sorted list
            if (!sortedlist.head) // list empty
            {
                sortedlist.head = young_current;
                sortedlist.tail = sortedlist.head;
            }
            else if (!sortedlist.head->next) //second node
            {
                sortedlist.head->next = young_current;
                sortedlist.tail = young_current;
                sortedlist.tail->next = NULL;
            }
            else // another node to append
            {
                tmp_node->next = NULL;
                sortedlist.tail->next = young_current;
                sortedlist.tail = young_current;
            }
    
            current_loop = current_loop->next;
        }
    
        //print list
        current = sortedlist.head;
        while (current)
        {
            printf("number = %d\n", current->number);
            current = current->next;
        }
    
        current = sortedlist.head;
        while (current)
        {
            tmp_node = current->next;
            free(current);
            printf("node freed\n");
            current = tmp_node;
        }
        return 0;
    }
    now what i cant fathom out is why when i set mylist.head = young_current->next (line 91) it sets the head pointer to the address pointed to by young_current->next as it should however the next line sets the pointer young_current->next to NULL (line 92) why the dickens does it change what sorted_list.head points at????????

    many thanks
    coop

  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
    > tmp_node = malloc(sizeof(tmp_node));
    Well this should be
    tmp_node = malloc(sizeof(*tmp_node));

    You're not allocating enough memory, and likely getting garbage or crashes as a result.

    Edit:
    So why the bloated main?
    Your previous threads had nice functions which performed specific tasks, and was working.
    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
    Apr 2019
    Posts
    808
    it was just a toy example trying out your idea of putting the values into another list in order
    thanks for the tip on malloc
    coop

  4. #4
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    its just dawned on me what the issue is with current_loop
    i set current_loop = to the head node then when the node to remove is the head node i set its next pointer to Null so i am setting current_loops next pointer to null so at the end of the loop the loop ends

  5. #5
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    here is the finished article all working
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    typedef struct Node
    {
        int number;
        struct Node *next;
    }Node;
    
    typedef struct Linkedlist
    {
        struct Node *head;
        struct Node *tail;
    }Linkedlist;
    
    void initializelists(Linkedlist *mylist, Linkedlist *sortedlist);
    void populatelist(Linkedlist *mylist);
    void appendlist(Linkedlist **list, Node *tmp_node);
    Node *getmemory(void);
    void sortlist(Linkedlist *mylist, Linkedlist *sortedlist);
    void removenode(Linkedlist **mylist, Node *tmp_current, Node *tmp_previous);
    void printlist(const Linkedlist list);
    void deletelist(Linkedlist *list);
    
    int main()
    {
        Linkedlist mylist, sortedlist;
    
        srand(time(NULL));
        initializelists(&mylist, &sortedlist);
        populatelist(&mylist);
        printlist(mylist);
        sortlist(&mylist, &sortedlist);
        printlist(sortedlist);
        deletelist(&sortedlist);
        return 0;
    }
    
    void initializelists(Linkedlist *mylist, Linkedlist *sortedlist)
    {
        mylist->head = NULL;
        mylist->tail = NULL;
        sortedlist->head = NULL;
        sortedlist->tail = NULL;
    }
    
    Node *getmemory(void)
    {
        Node *tmp_node = NULL;
    
        tmp_node = malloc(sizeof(*tmp_node));
        if (!tmp_node)
        {
            printf("error aquiring memory\n");
            exit(EXIT_FAILURE);
        }
        return tmp_node;
    }
    
    void appendlist(Linkedlist **list, Node *tmp_node)
    {
        if (!(*list)->head) // list empty
        {
            (*list)->head = tmp_node;
            (*list)->tail = (*list)->head;
        }
        else if (!(*list)->head->next) //second node
        {
            (*list)->head->next = tmp_node;
            (*list)->tail = tmp_node;
            (*list)->tail->next = NULL;
        }
        else // another node to append
        {
            tmp_node->next = NULL;
            (*list)->tail->next = tmp_node;
            (*list)->tail = tmp_node;
        }
    }
    
    void populatelist(Linkedlist *mylist)
    {
        int i;
        Node *tmp_node = NULL;
    
        for (i = 20; i < 90; i += 10)
        {
            tmp_node = getmemory();
            tmp_node->number = rand() % i * 10 + 1;
            appendlist(&mylist, tmp_node);
        }
    }
    
    void printlist(const Linkedlist list)
    {
        Node *current = list.head;
    
        while (current)
        {
            printf("number = %d\n", current->number);
            current = current->next;
        }
    }
    void deletelist(Linkedlist *list)
    {
        Node *current = list->head, *tmp_node;
        while (current)
        {
            tmp_node = current->next;
            free(current);
            printf("node freed\n");
            current = tmp_node;
        }
    }
    
    void removenode(Linkedlist **mylist, Node *tmp_current, Node *tmp_previous)
    {
        if (tmp_current == (*mylist)->head)//smallest current is the head
        {
            (*mylist)->head = (*mylist)->head->next;
            tmp_current->next = NULL;
        }
        else if (!tmp_current->next) //smallest current is the tail
        {
            (*mylist)->tail = tmp_previous;
            tmp_previous->next = NULL;
        }
        else //middle node
        {
            tmp_previous->next = tmp_current->next;
            tmp_current->next = NULL;
        }
    }
    
    void sortlist(Linkedlist *mylist, Linkedlist *sortedlist)
    {
        int smallest;
        Node *current = NULL, *previous = NULL, *smallest_current, *smallest_previous;
        while (mylist->head)
        {
            current = mylist->head;
            previous = NULL;
            smallest = current->number;
            smallest_current = current;
            smallest_previous = previous;
    
            while (current)
            {
                if (smallest > current->number)
                {
                    smallest = current->number;
                    smallest_current = current;
                    smallest_previous = previous;
                }
                previous = current;
                current = current->next;
            }
            //remove node from list
            printf("removing %d\n", smallest_current->number);
            removenode(&mylist, smallest_current, smallest_previous);
            //add node to sorted list
            appendlist(&sortedlist, smallest_current);
        }
    }
    coop
    Last edited by cooper1200; 05-28-2019 at 05:13 AM.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Consider something like this:
    Code:
    Node *createNode(int value)
    {
        Node *tmp_node = NULL;
        tmp_node = malloc(sizeof(*tmp_node));
        if (!tmp_node)
        {
            printf("error acquiring memory\n");
            exit(EXIT_FAILURE);
        }
        else
        {
            node->number = value;
            node->next = NULL;
        }
        return tmp_node;
    }
    That is, your node is either fully initialised, or it isn't created at all.

    Also, appendlist() has only two cases.
    If there is at least one element, then appending only affects the tail. The head doesn't change.
    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.

  7. #7
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    Quote Originally Posted by Salem View Post
    Consider something like this:
    Code:
    Node *createNode(int value)
    {
        Node *tmp_node = NULL;
        tmp_node = malloc(sizeof(*tmp_node));
        if (!tmp_node)
        {
            printf("error acquiring memory\n");
            exit(EXIT_FAILURE);
        }
        else
        {
            node->number = value;
            node->next = NULL;
        }
        return tmp_node;
    }
    That is, your node is either fully initialised, or it isn't created at all.

    Also, appendlist() has only two cases.
    If there is at least one element, then appending only affects the tail. The head doesn't change.
    i take your point with the create node function as it is the program quits if it cant get any memory however if i took the program further i would have to change that so might as well sort it from the start.

    appendlist () it too me a moment but your right the elseif clause is the same as the else just worded differently.

    i did notice in one of the other if / else if / else i had a clause !(some node -> next) then in the code for that clause i had written somenode -> next = null duh!!!! thing is though i didn't just do it once i had it a couple of times

    coop

  8. #8
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    This might be something that you look at in the future, but it is good to think of now - What to do when things go wrong...


    Imagine that you are someone who has been tasked to enter in the ages for all the students in the school - They have chosen your programme because they liked the colour of your font.

    They have spent 4 hours entering data and all of the sudden there is a malloc error... They then see a message appear on the screen saying, "error acquiring memory" and it closes.


    You might get a phone call that won't go well, because to them your programme has a bug that lost half a day's work.


    It would be better to display to the user something like, "Error 101 - Could not get more memory. Please try to shut other programmes and try again. (A)bort, (R)etry, (C)ancel?"
    The user could at least try again, or cancel the operation and save the data.


    This is maybe not something that you need to worry about now, but it's good to keep it in the back of your mind
    Fact - Beethoven wrote his first symphony in C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. What is the logic?
    By beycan in forum C Programming
    Replies: 3
    Last Post: 10-23-2010, 05:10 AM
  2. Logic, Else If, Else and If
    By ScoutDavid in forum C Programming
    Replies: 6
    Last Post: 09-26-2010, 08:32 AM
  3. Logic help...
    By csharp100 in forum C Programming
    Replies: 8
    Last Post: 09-14-2010, 11:29 PM
  4. War Logic
    By Dr Saucie in forum C Programming
    Replies: 3
    Last Post: 02-16-2010, 10:00 PM
  5. Logic
    By LordBronz in forum C++ Programming
    Replies: 6
    Last Post: 05-23-2006, 05:41 PM

Tags for this Thread