Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.8 kB
1
Indexable
Never
/* week3 honor homework: doubly linked list */
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
typedef struct list{int data; struct list* previous; struct list* next;} list;
list* create_list(int d)
{
    list* head = malloc(sizeof(list));
    head->data = d; 
    head->next = NULL;
    head->previous = NULL;
    return head;
}
list* add_to_front(int data, list* h)
{
    list* head = create_list(data);
    head->next = h;
    head->previous = NULL;
    (head->next)->previous = head;
    return head;
}
void print_list(list* l)
{   
    int i = 0;
    while(l != NULL)
    {
        printf("%d\t", l->data);
        i++;
        l = l->next;
        if(i % 5 == 0) printf("\n");
    }
}
void print_list_back_forth(list* l)
{
    // int i = 0;
    // int max = 10;
    int direction = 1;
    while(l != NULL)
    {
        printf("%d\t", l->data);
        // i++;
        // if(l->next;
        // l = l->next ? l->next != NULL : l->previous;
        if(l->next == NULL) // reach end
        {
            printf("\nswitch direction\n");
            direction = 0;
        }
        if(direction == 1)
            l = l->next;
        else
            l = l->previous;
        // if(i % 5 == 0) printf("\n");
        
    }
}
void swap_list(list* l1, list* l2)
{
    int temp = l2->data;
    l2->data = l1->data;
    l1->data = temp;
}
void delete_element(list* l)
{
    if(l->next == NULL)
        (l->previous)->next = NULL;
    else if(l->previous == NULL)
        (l->next)->previous = NULL;
    else
    {
        (l->next)->previous = l->previous;
        (l->previous)->next = l->next;
    }
    // free up memory: TBD
}
void main(void)
{
    // generate random list
    int size = 100;
    int range = 49;
    srand((unsigned)time(NULL));
    list* head = create_list(rand() % range);
    for(int i = 1; i < size; i++)
    {
        head = add_to_front(rand() % range, head);
    }
    printf("random generated list\n");
    print_list(head);
    printf("\n");
    // sort
    for(int i = 0; i < size - 1; i++)
    {
        int swaped = 0;
        list* cursor = head;
        for(int j = 0; j < size - i - 1; j++)
        {
            if(cursor->data > (cursor->next)->data)
            {
                swap_list(cursor, cursor->next);
                swaped = 1;
            }
            cursor = cursor->next;
        }
        if(swaped == 0) break;
    }
    printf("sorted list\n");
    print_list(head);
    printf("\n");
    // remove dublicated
    // method 1
    list* current_element = head;
    list* element_to_compare = head->next;    
    while(element_to_compare != NULL)
    {
        if(current_element->data == element_to_compare->data)
        {
            delete_element(element_to_compare);
            element_to_compare = element_to_compare->next;
        }
        else
        {
            current_element = current_element->next;
            element_to_compare = element_to_compare->next;
        }
    }
    /* method 2
    list* current_element = head;
    while(current_element != NULL)
    {
        list* element_to_compare = current_element->next;
        while(element_to_compare != NULL)
        {
            // printf("current element %d <-> element_to_compare %d\n", current_element->data, element_to_compare->data);
            if(element_to_compare->data == current_element->data)
            {
                delete_element(element_to_compare);
                // if element_to_compare is leftmost element, break
                if(element_to_compare->next == NULL)
                    break;
            }
            element_to_compare = element_to_compare->next;
        }
        current_element=current_element->next;
    }
    */
    printf("sorted duplicate removed list\n");
    print_list(head);
    printf("\n");
}