+1 (315) 557-6473 

Use Circular Linked List to Simulate a Collection if Objects That Are Removed 1 At A Time Assignment Solution.


Instructions

Objective
Write a c assignment program to use circular linked list to simulate a collection of objects that are removed 1 at a time.

Requirements and Specifications

Use circular linked list to simulate a collection of objects that are removed 1 at a time in C
Use circular linked list to simulate a collection of objects that are removed 1 at a time in C 1

Screenshots of output

Use circular linked list to simulate a collection of objects that are removed 1 at a time in C 2Use circular linked list to simulate a collection of objects that are removed 1 at a time in C 3

Use circular linked list to simulate a collection of objects that are removed 1 at a time in C 4Use circular linked list to simulate a collection of objects that are removed 1 at a time in C 5

Use circular linked list to simulate a collection of objects that are removed 1 at a time in C 6Use circular linked list to simulate a collection of objects that are removed 1 at a time in C 7

Source Code

#include

#include

#include

#include "leak_detector_c.h"

typedef struct failfish_st

{

    int sequence;

    struct failfish_st *prev;

    struct failfish_st *next;

}failfish;

typedef struct

{

    char *name;

    int ni;

    int ei;

    int thi;

    failfish *head;

    failfish *tail;

}failfish_queue;

typedef struct pond_node_st

{

    int n;

    failfish_queue *queue;

    struct pond_node_st *next;

}pond_node;

failfish *create_failfish(int sequence_number);

void destroy_failfish(failfish *fish);

failfish_queue *create_failfish_queue(char *pondname, int n, int e, int th);

void destroy_failfish_queue(failfish_queue *q);

void print_failfish_queue(failfish_queue *q, FILE *output);

pond_node *load_input(FILE *in);

void enqueue(failfish_queue *queue, failfish *fish);

failfish *dequeue(failfish_queue *queue);

failfish *peek(failfish_queue *queue);

int is_empty(failfish_queue *queue);

pond_node *create_pond(int n, failfish_queue *q);

int insert_pond(pond_node **list, int n, failfish_queue *q);

void destroy_ponds(pond_node *list);

void print_ponds(pond_node *list, FILE *output);

int main()

{

    FILE *input, *output;

    pond_node *ponds, *node, *nmax;

    failfish_queue *pond, *qmax;

    failfish *fish;

    int i, totalfish;

    /* open input file */

    input = fopen("cop3502-as2-input.txt", "rt");

    if (input == NULL)

    {

        fprintf(stderr, "Unable to open input file\n");

        return 1;

    }

    /* open output file */

    output = fopen("cop3502-as2-output.txt", "wt");

    if (output == NULL)

    {

        fclose(output);

        fprintf(stderr, "Unable to open output file\n");

        return 1;

    }

    /* load queues into the ponds */

    ponds = load_input(input);

    if (ponds == NULL)

    {

        fprintf(stderr, "Error reading input file\n");

        return 1;

    }

    fclose(input);

    /* print initial ponds */

    fprintf(output, "Initial Pond Status\n");

    print_ponds(ponds, output);

    fprintf(output, "\nFirst Course\n\n");

    for (node = ponds; node != NULL; node = node->next)

    {

        pond = node->queue;

        fprintf(output, "Pond %d: %s\n", node->n, pond->name);

        /* repeat while number is above the threshold */

        while (pond->ni > pond->thi)

        {

            for (i = 0; i < pond->ei - 1; i++) /* skip e-1 fishes */

            {

                fish = dequeue(pond); /* dequeue and enqueue to skip */

                enqueue(pond, fish);

            }

            fish = dequeue(pond); /* last one is simply dequeued and freed */

            fprintf(output, "Failfish %d eaten\n", fish->sequence);

            destroy_failfish(fish);

        }

        fprintf(output, "\n");

    }

    /* put smallest sequence fish at head in all ponds */

    totalfish = 0;

    for (node = ponds; node != NULL; node = node->next)

    {

        pond = node->queue;

        /* repeat while previous of head is smaller*/

        while (peek(pond)->prev->sequence < peek(pond)->sequence)

        {

            fish = dequeue(pond); /* dequeue and enqueue to reorder */

            enqueue(pond, fish);

        }

        totalfish += pond->ni;

    }

    /* print end ponds */

    fprintf(output, "End of Course Pond Status\n");

    print_ponds(ponds, output);

    fprintf(output, "\nSecond Course\n\n");

    while (totalfish > 1)

    {

        /* find the highest numbered failfish at the head of the pond queues */

        for (nmax = NULL, node = ponds; node != NULL; node = node->next)

        {

            pond = node->queue;

            if (!is_empty(pond))

            {

                if (nmax == NULL)

                    nmax = node;

                else

                {

                    qmax = nmax->queue;

                    if (peek(pond)->sequence > peek(qmax)->sequence /* if head is bigger than max */

                        || (peek(pond)->sequence == peek(qmax)->sequence && pond->ni < qmax->ni)) /* if there's a tie, use smallest queue */

                    {

                        nmax = node; /* use current pond node as max */

                    }

                }

            }

        }

        fish = dequeue(nmax->queue); /* dequeue fish */

        fprintf(output, "Eaten: Failfish %d from pond %d\n", fish->sequence, nmax->n);

        destroy_failfish(fish);

        totalfish--;

    }

    /* print remaining fish */

    for (node = ponds; node != NULL; node = node->next)

    {

        pond = node->queue;

        if (!is_empty(pond))

        {

            fprintf(output, "\nFailfish %d from pond %d remains\n", peek(pond)->sequence, node->n);

            break;

        }

    }

    /* free all memory used for queues */

    destroy_ponds(ponds);

    atexit(report_mem_leak);

    return 0;

}

/* Loads the failfish queue information from the given file, makes a list of ponds and creates

    the queues in the ponds, returns the list of ponds or NULL if there is an error */

pond_node *load_input(FILE *in)

{

    failfish_queue *q;

    pond_node *ponds;

    char buffer[128];

    int i, n;

    int gi;

    char name[100];

    int ni;

    int ei;

    int thi;

    ponds = NULL;

    if (fgets(buffer, 128, in) == NULL) /* read number of failgroups */

        return NULL;

    if (sscanf(buffer, "%d", &n) != 1)

        return NULL;

    i = 0;

    while (fgets(buffer, 128, in) != NULL) /* read number of failgroups */

    {

        if (buffer[0] == '\n' || buffer[0] == 0) /* ignore empty lines */

            continue;

        if (sscanf(buffer, "%d %s %d %d %d", &gi, name, &ni, &ei, &thi) != 5)

        {

            destroy_ponds(ponds);

            return NULL;

        }

        if (gi < 1 || gi > 10 /* if not a valid pond */

            || ni < 2 || ni > 10000 /* if not a valid n */

            || ei < 1 || ei >= ni /* if not a valid ei */

            || thi < 1 || thi >= ni) /* if not a valid thi */

        {

            destroy_ponds(ponds);

            return NULL;

        }

        q = create_failfish_queue(strdup(name), ni, ei, thi);

        if (q == NULL)

        {

            destroy_ponds(ponds);

            return NULL;

        }

        if (insert_pond(&ponds, gi, q) == 0) /* insert pond to the list */

        {

            destroy_ponds(ponds);

            return NULL;

        }

        i++;

    }

    if (i < n)

    {

        destroy_ponds(ponds);

        return NULL;

    }

    return ponds;

}

/* Creates a new failfish queue with the given arguments */

failfish_queue *create_failfish_queue(char *pondname, int n, int e, int th)

{

    failfish_queue *fq;

    failfish *fish;

    int i;

    fq = (failfish_queue *) malloc(sizeof(failfish_queue));

    if (fq == NULL)

        return NULL;

    fq->name = pondname;

    fq->ni = 0;

    fq->ei = e;

    fq->thi = th;

    fq->head = NULL;

    fq->tail = NULL;

    for (i = 1; i <= n; i++)

    {

        fish = create_failfish(i);

        enqueue(fq, fish);

    }

    return fq;

}

/* Deallocates all the memory used by the failfish queue */

void destroy_failfish_queue(failfish_queue *q)

{

    if (q != NULL)

    {

        while (!is_empty(q))

            destroy_failfish(dequeue(q));

        if (q->name != NULL)

            free(q->name);

        free(q);

    }

}

/* Creates a new failfish with the given sequence number */

failfish *create_failfish(int sequence_number)

{

    failfish *fish;

    fish = (failfish *) malloc(sizeof(failfish *));

    if (fish == NULL)

        return NULL;

    fish->sequence = sequence_number;

    fish->prev = NULL;

    fish->next = NULL;

    return fish;

}

/* Deallocates all the memory used by the failfish */

void destroy_failfish(failfish *fish)

{

    if (fish != NULL)

        free(fish);

}

/* prints the queue name and all the failfishes in the queue */

void print_failfish_queue(failfish_queue *q, FILE *output)

{

    failfish *fish;

    int i;

    fprintf(output, "%s ", q->name);

    fish = q->head;

    for (i = 0; i < q->ni; i++)

    {

        fprintf(output, "%d ", fish->sequence);

        fish = fish->next;

    }

}

/* Adds a new failfish to the tail of the queue */

void enqueue(failfish_queue *queue, failfish *fish)

{

    if (queue->ni == 0) /* if the queue was empty */

    {

        queue->head = fish; /* use same node for head and tail */

        queue->tail = fish;

        fish->next = fish; /* loop next and prev pointers */

        fish->prev = fish;

    }

    else /* there are 1 or more nodes */

    {

        fish->prev = queue->tail; /* connect fish pointers */

        fish->next = queue->tail->next;

        queue->tail->next->prev = fish; /* correct tail pointers */

        queue->tail->next = fish;

        queue->tail = fish;

    }

    queue->ni++;

}

/* Removes a failfish from the front of the queue */

failfish *dequeue(failfish_queue *queue)

{

    failfish *fish;

    if (queue->ni == 0) /* if the queue is empty */

        return NULL;

    fish = queue->head;

    if (queue->ni > 1)

    {

        queue->head->next->prev = queue->head->prev; /* remove node from queue */

        queue->head->prev->next = queue->head->next;

        queue->head = queue->head->next;

    }

    else

    {

        queue->head = NULL;

        queue->tail = NULL;

    }

    queue->ni--;

    return fish;

}

/* Returns the failfish at the head of the queue */

failfish *peek(failfish_queue *queue)

{

    return queue->head;

}

/* Returns 1 if the queue is empty, 0 otherwise */

int is_empty(failfish_queue *queue)

{

    if (queue == NULL)

        return 1;

    return (queue->ni == 0);

}

/* Creates a new pond node with the given queue */

pond_node *create_pond(int n, failfish_queue *q)

{

    pond_node *pond;

    pond = (pond_node *) malloc(sizeof(pond_node));

    if (pond == NULL)

        return NULL;

    pond->n = n;

    pond->queue = q;

    pond->next = NULL;

    return pond;

}

/* Adds a new pond on the list, returns 0 in error */

int insert_pond(pond_node **list, int n, failfish_queue *q)

{

    pond_node *curnode, *prevnode;

    pond_node *node;

    node = create_pond(n, q);

    if (node == NULL)

        return 0;

    if (*list == NULL) /* empty list */

        *list = node;

    else

    {

        curnode = *list;

        prevnode = NULL;

        while (curnode && curnode->n < n) /* insert in order */

        {

            prevnode = curnode;

            curnode = curnode->next;

        }

        if (prevnode == NULL) /* inserting at the start */

        {

            node->next = *list;

            *list = node;

        }

        else

        {

            node->next = prevnode->next;

            prevnode->next = node;

        }

    }

    return 1;

}

/* prints all the ponds in the list */

void print_ponds(pond_node *list, FILE *output)

{

    pond_node *pond;

    pond = list;

    while(pond != NULL)

    {

        fprintf(output, "%d ", pond->n);

        print_failfish_queue(pond->queue, output);

        fprintf(output, "\n");

        pond = pond->next;

    }

}

/* Deallocates all memory used by the pond list */

void destroy_ponds(pond_node *list)

{

    pond_node *pond, *temp;

    pond = list;

    while(pond != NULL)

    {

        temp = pond;

        pond = pond->next;

        destroy_failfish_queue(temp->queue);

        free(temp);

    }

}