0
\$\begingroup\$

This is from an exercise I've done:

We want to implement a priority queue system to plan the execution of the system processes. An array of MAXPRI represents the priorities of the system, where 0 is the highest priority and MAXPRI-1 is the lowest priority. Each position i in the array will contain a dynamic linked list where the first element of this is the priority i process that must be executed (provided there are no processes available in the previous i-1 positions). Implement the following operations:

Create. Initialize array.

AddProcess. Given a priority and a process identifier, it adds the process to the end of the corresponding list.

ExecuteProcess. Remove from the list the most priority process. If there are no processes to execute, it will be indicated with a warning message.

Search. Given a process identifier it returns the priority of this one. If the id of the process does not exist, -1 will be returned.

Display. Go through the structure to show the existing processes that are available for execution sorted by priority (highest first).

main.c, linkedListArray.c, linkedListArray.h

#include "linkedListArray.h"

void Create(Node **queue)
{
    for (int i = 0; i < MAXPRI; i++) {
        queue[i] = NULL;
    }
}

void Push(Node **queue, int pri, int id)
{
    Node *new_node = malloc(sizeof(Node));
    if (new_node != NULL) {
        new_node->id = id;
        new_node->next = NULL;
        if (queue[pri] == NULL) {
            queue[pri] = new_node;
        }
        else {
            Node *aux = queue[pri];
            while (aux->next != NULL) {
                aux = aux->next;
            }
            aux->next = new_node;
        }
    }
}

void Execute(Node **queue)
{
    bool end = false;
    int i = 0;

    while (!end && i < MAXPRI) {
        if (queue[i] != NULL) {
            Node *aux = queue[i];
            queue[i] = queue[i]->next;
            free(aux);
            end = true;
        }
        i++;
    }
    if (!end) {
        printf("There are no processes\n");
    }
}

int Search(Node **queue, unsigned int id)
{
    int pri = -1;
    Node *aux;

    for (int i = 0; i < MAXPRI  &&  pri == -1; ++i) {
        aux = queue[i];
        while (aux != NULL  &&  pri == -1) {
            if (aux->id == id) {
                pri = i;
            }
            else
                aux = aux->next;
        }
    }
    return pri;
}

void Output(Node *head)
{
    for (Node *current = head; current != NULL; current = current->next) {
        if (current->next != NULL)
            printf ("%d -> ", current->id);
        else
            printf ("%d", current->id);
    }
}

void Display(Node **queue)
{
    for (int i = 0; i < MAXPRI; i++) {
        printf ("Priority queue %d: ", i);
        Output(queue[i]);
        putchar('\n');
    }
    putchar('\n');
}
\$\endgroup\$
1
\$\begingroup\$
  • An if clause of Output is only executed once, on the very first node. You may avoid this logic altogether by making it explicit:

    if (!head)
        return;
    printf("%d", head->id);
    
    for (head = head->next; head; head = head->next) {
        printf(" -> %d", head->id);
    }
    

    A missing

    printf("\n");
    

    seems like a bug (I hope it is a copy-paste error).

  • An early return helps to avoid unnecessary variables. Consider Search:

    for (int i = 0; i < MAXPRI; i++)
        for (Node * aux = queue[i]; aux; aux = aux->next) {
            if (aux->id == id) {
                return i;
            }
        }
    }
    return -1;
    

    A perk benefit is that now you can rename meaningless i to a more reasonable pri.

    Similarly, if Execute returns as soon as a process is found, you wouldn't need bool end.

  • I strongly recommend to factor the

        while (aux->next != NULL) {
            aux = aux->next;
        }
    

    loop into a function (say, get_tail), and streamline Push:

    Node * node = new_node(id);
    Node * tail = get_tail(pri);
    if (tail) {
        tail->next = node;
    } else {
        queue[pri] = node;
    }
    
  • Using extra memory may significantly reduce the run time. In your case, the

    struct list {
        Node * head;
        Node * tail;
    };
    

    would reduce looking for tail complexity from linear to \$O(1)\$.

  • linkedListArray.h shall only export the names defined in linkedListArray.c. The #include files required for linkedListArray.c compilation should be included directly in linkedListArray.c.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.