Массив связанных списков в C


Это упражнение я делал:

Мы хотим внедрить систему приоритетов очередей планировать выполнение системных процессов. Массив MAXPRI отражает приоритеты системы, где 0 соответствует наивысшему приоритету и MAXPRI-1-самый низкий приоритет. Каждой позиции i в массив будет содержать список динамически связаны, где первый элемент это приоритет процесса, который должен быть выполнен (при условии отсутствия процессов, имеющихся в предыдущие i-1 позиции). Реализовать следующие операции:

Создавать. Инициализировать массив.

AddProcess. Учитывая приоритет и идентификатор процесса, он добавляет процесс в конец соответствующего списка.

Мыши файл executeprocess. Удалить из списка наиболее приоритетный процесс. Если нет никаких процессов для выполнения, оно будет показано предупреждающее сообщение.

Поиск. Заданному идентификатору процесса он возвращает приоритет это одно. Если идентификатор процесса не существует, то будет возвращено значение -1.

Дисплей. Пройти через структуру, чтобы показать существующие процессы, которые доступны для выполнения отсортированный по приоритету (высокий первый).

главная.с, linkedListArray.с, linkedListArray.ч

#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');
}


1787
0
задан 1 марта 2018 в 11:03 Источник Поделиться
Комментарии
1 ответ


  • В if пункт Output выполняется только один раз, на самый первый узел. Вы можете избежать этой логике, сделав его явным:

    if (!head)
    return;
    printf("%d", head->id);

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

    Отсутствует

    printf("\n");

    похоже, баг (я надеюсь, что это копипаст ошибки).


  • Рано return помогает избежать ненужных переменных. Рассмотрим 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;

    Перк преимуществом является то, что теперь вы можете переименовывать бессмысленно i для более разумной pri.

    Аналогично, если Execute возвращается, как только процесс будет найден, вам не нужно bool end.


  • Я настоятельно рекомендую фактора

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

    цикл в функцию (скажем, get_tail), и упорядочения Push:

    Node * node = new_node(id);
    Node * tail = get_tail(pri);
    if (tail) {
    tail->next = node;
    } else {
    queue[pri] = node;
    }

  • Используя дополнительной памяти может существенно уменьшить время выполнения. В вашем случае

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

    сократит ищу сложность хвост от линейных до \$О(1)\$.


  • linkedListArray.h будем экспортировать только имена, определенные в linkedListArray.c. В #include файлы, необходимые для linkedListArray.c компиляция должна быть включена непосредственно в linkedListArray.c.

1
ответ дан 1 марта 2018 в 07:03 Источник Поделиться