Thread: singly linked list finished with a cheating sort

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

    singly linked list finished with a cheating sort

    here is the code
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        int age;
        struct Node *next;
    }Node;
    
    typedef struct LinkedList
    {
        struct Node *head;
        struct Node *tail;
    }LinkedList;
    
    enum Flag {FALSE = 0, TRUE = 1};
    
    void initalize_list(LinkedList *list);
    struct Node *create_head(void);
    struct Node *get_memory(void);
    int get_age(void);
    void print_list(const LinkedList list);
    void delete_list(LinkedList *list);
    void append_to_list(LinkedList *list);
    void prepend_to_list(LinkedList *list);
    void delete_node(LinkedList *list);
    int find_node(int age, Node **current, Node **previous);
    void remove_node(Node *current, Node *previous, LinkedList **list);
    void insert_node_in_middle(int index, LinkedList *list);
    void insert_node(int index, LinkedList **list, Node **tmp_node);
    void cheating_sorted_list(LinkedList *list);
    
    int main()
    {
        //declare my lists
        LinkedList list;
    
        initalize_list(&list);
        //prepend_to_list(&list);
        append_to_list(&list);
        //append_to_list(&list);
        //prepend_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        delete_node(&list);
        print_list(list);
        append_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        printf("\n inserting a node\n");
        insert_node_in_middle(0, &list);
        print_list(list);
        printf("\nsorting list......\n");
        cheating_sorted_list(&list);
        printf("\nprinting sorted list.....\n");
        print_list(list);
        //delete_node(&list);
        delete_list(&list);
    
        return 0;
    }
    
    void initalize_list(LinkedList *list)
    {
        list->head = NULL;
        list->tail = NULL;
    
        list->head = create_head();
        list->head->next = NULL;
        list->tail = list->head;
    
        list->head->age = get_age();
    }
    
    struct Node *create_head(void)
    {
        Node *head_tmp;
    
        head_tmp = get_memory();
        if (!head_tmp)
        {
            fprintf(stderr, "error allocating memory\n");
            exit(EXIT_FAILURE);// if it cant allocate memory for the head node at startup somthing really wrong so bug out
        }
    
        return head_tmp;
    }
    
    struct Node *get_memory(void)
    {
        return malloc(sizeof(Node));
    }
    
    int get_age(void)
    {
        int age;
    
        printf("PLease enter an age: ");
        scanf(" %d", &age);
    
        return age;
    }
    
    void print_list(const LinkedList list)
    {
        int count = 1;
        Node *tmp = list.head;
    
        while (tmp)
        {
            printf("person%d's age is %d\n", count, tmp->age);
            count++;
            tmp = tmp->next;
        }
    }
    
    void delete_list(LinkedList *list)
    {
        int count = 1;
        Node *tmp;
    
        printf("freeing memory.....\n");
        while (list->head)
        {
            tmp = list->head->next;
            printf("freeing element %d\n", count);
            free(list->head);
            list->head = tmp;
            count++;
        }
        printf("memory freed\n");
    }
    
    void append_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to append\n");
            return;
        }
    
        tmp_node->age = get_age();
        list->tail->next = tmp_node; //set the tail's next pointer to point at the new node
        list->tail = tmp_node; //set tail to the new node;
    
        // if its the second node in the list list->head->next will be NULL so set the next pointer to point at tmp_node as well
        if (!list->head->next)
        {
            list->head->next = tmp_node;
        }
    }
    
    void prepend_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to prepend\n");
            return;
        }
    
        tmp_node->age = get_age();
        tmp_node->next = list->head; //set tmp_node's next pointer to point at the current head pointer
        list->head = tmp_node; //set head to point to the new head/node
    }
    void insert_node_in_middle(int index, LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to prepend\n");
            return;
        }
    
        tmp_node->age = get_age();
        insert_node(index, &list, &tmp_node);
    }
    
    void insert_node(int index, LinkedList **list, Node **tmp_node)
    {
        int count = 0;
        Node *current_node = (*list)->head, *previous_node = NULL;
    
        if (index == 0)
        {
    
            (*tmp_node)->next = (*list)->head;
            (*list)->head = (*tmp_node);
            return;
        }
        while (current_node)
        {
            if (count == index)
            {
                break;
            }
            previous_node = current_node;
            current_node = current_node->next;
            count++;
        }
    
        if (!current_node)
        {
            (*list)->tail->next = (*tmp_node);
            (*list)->tail = (*tmp_node);
            return;
        }
    
        (*tmp_node)->next = previous_node->next;
        previous_node->next = (*tmp_node);
        (*tmp_node)->next = current_node;
    }
    
    void delete_node(LinkedList *list)
    {
        int age;
        Node *current = list->head, *previous = NULL;
    
        printf("Please enter the age you wish to delete: ");
        scanf(" %d", &age);
    
        if (find_node(age, &current, &previous))
        {
            remove_node(current, previous, &list);
            free(current);
            printf("node deleted\n");
        }
        else
        {
            printf("Invalid age as no node found!\n");
        }
    }
    
    int find_node(int age, Node **current, Node **previous)
    {
        while (*current)
        {
            if ((*current)->age == age)
            {
                return TRUE;
            }
            *previous = *current;
            *current = (*current)->next;
        }
    
        return FALSE;
    }
    
    void remove_node(Node *current, Node *previous, LinkedList **list)
    {
        if (!previous) // current is pointing at the head
        {
            (*list)->head = current->next;
            current->next = NULL;
            printf("freeing head node\n");
        }
        else if(!current->next) // current is pointing at the tail (the last node)
        {
            (*list)->tail = previous;
            (*list)->tail->next = NULL;
            printf("freeing tail node\n");
        }
        else //its somewhere in the middle of the list
        {
            previous->next = current->next;
            current->next = NULL;
            printf("freeing middle node\n");
        }
    }
    
    void cheating_sorted_list(LinkedList *list)
    {
        int swap_found = 1, tmp_age;
        Node *current, *previous;
    
        while (swap_found)
        {
            swap_found = 0;
            current = list->head->next;
            previous = list->head;
            while (current)
            {
                if (previous->age > current->age)
                {
                    tmp_age = previous->age;
                    previous->age = current->age;
                    current->age = tmp_age;
                    swap_found = 1;
                }
                current = current->next;
                previous = previous->next;
            }
    
        }
    }
    the sorting method is a cop out really as if i had a lot of data held in the node struct rather than just one int it would take forever to transpose it all across

    any suggestions on anything else i can do with it most welcome
    coop

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,530
    Like I said in your other thread, it's often easier to just remove items from one list and insert them in the correct position in another list.

    Try creating a sorted_insert function.
    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
    662
    Quote Originally Posted by Salem View Post
    Like I said in your other thread, it's often easier to just remove items from one list and insert them in the correct position in another list.

    Try creating a sorted_insert function.
    i did and things started to go wrong badly somehow i had next pointers pointing at address x08 with out even altering the list so i left well alone before it decided to write where it really shouldn't

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    For an efficient sort, you could write a merge function and then a merge sort function. Bottom up approach using a small (26 to 32) array of pointers is faster than top down approach which scans lists to split them and then pushes the pointers onto a stack.

    Merge sort - Wikipedia

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 05-16-2016, 01:15 PM
  2. Need help with selection sort for singly linked lists
    By mhroseh in forum C Programming
    Replies: 1
    Last Post: 02-24-2013, 11:51 AM
  3. Replies: 11
    Last Post: 02-20-2012, 10:38 PM
  4. Bubble Sort on a Singly Linked List
    By bigmac(rexdale) in forum C++ Programming
    Replies: 9
    Last Post: 03-23-2011, 10:13 AM
  5. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM

Tags for this Thread