Thread: 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

Originally Posted by Salem

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

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