Реализация очереди FIFO в C

Question

Для встроенного приложения я пытаюсь реализовать очередь структур "первым пришел - первым вышел" (FIFO) с использованием ANSI C. Наиболее простой способ сделать это, по-видимому, реализовать связанный список, чтобыкаждая структура содержит указатель на следующий в очереди.Поэтому я определяю саму структуру как:

typedef enum { LED_on, LED_off, etc } Action;
typedef struct Queued_Action QueuedAction;

struct Queued_Action
{
    Action       action;
    int          value;
    QueuedAction *nextAction;
};

Пока все хорошо.Если я определю указатели на первый и последний элементы в очереди как:

QueuedAction *firstAction;
QueuedAction *lastAction;

... тогда я хотел бы иметь возможность добавить новое действие в очередь, указав (например):

if (!add_action_to_queue(LED_on, 100, &lastAction))
     printf("Error!\n);

... поэтому при возврате lastAction будет указателем на только что созданное последнее действие в очереди.Следовательно, процедура добавления действия в очередь будет выглядеть следующим образом:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    *lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    *lastAction = newQueuedAction;
    return 1;
}

Все будет хорошо, но этот код не будет компилироваться.Ошибка находится в строке, говорящей

*lastAction -> nextAction = newQueuedAction;

... где компилятор утверждает, что элемент слева от '->' не является допустимой структурой.Конечно, однако, это должно быть.Если на самом деле я делаю то, что должно быть полностью избыточным приведением:

fakeAction = (QueuedAction *)(*lastAction);
fakeAction -> nextAction = newQueuedAction;

... тогда компилятор вполне доволен.Тем не менее, я обеспокоен тем, что сообщение об ошибке намекает на что-то неуловимое, что я могу ошибаться здесь.Так что (чтобы перейти к сути), может кто-нибудь сказать мне, почему компилятор не устраивает, и есть ли лучший способ сделать то, что я пытаюсь сделать здесь.

Answer 1

Вы пробовали:

(*lastAction) -> nextAction = newQueuedAction;

Answer 2

Вы также могли бы сделать это:

(*lastAction)->nextAction

Я думаю, что это проблема оператора pecedence.

Answer 3

Надеюсь, это поможет вам заранее.Во-первых, извините за мой английский.В нем может быть несколько грамматических или орфографических ошибок.

Проблема, которую я вижу в вашем коде, состоит в основном в том, что вы смешиваете определение указателя и реализацию одного и того же.

От ANSI C до C99, дажев C ++ (не тестировался в C #) существует большой взлом, использование указателей может быть полезно заранее: думаю, что указатель является первым элементом вектора, [0] one .

Отличным сайтом, объясняющим эту концепцию, является: http://boredzo.org/pointers/

Этот хак - простой перевод и хороший инструмент для лучшего понимания указателей.

Начните действовать, парни.

Функция, которую вы используете для добавления элементов в список,

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    *lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    *lastAction = newQueuedAction;
    return 1;
}

Содержит некоторые ошибки.Прежде всего, используйте

*lastAction -> ...;

как

lastAction[0] -> ...;

Как видите, вы не можете использовать оператор -> для доступа к внутренним элементам.

То же самое происходит и здесь:

lastAction[0] = newQueuedAction;

Вы не можете скопировать указатель внутри структуры. lastAction , использующий этот хак для лучшего понимания, больше не является указателем - фактически, это содержимое первого элемента в структуре, назначенной компилятором, поэтому вам также нужно изменить эту строку, чтобы изменить значение указателя:

lastAction = newQueuedAction;

Используя этот перевод и аннотации, ваш код будет теперь:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction[0] -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction[0] = newQueuedAction;
    return 1;
}

Теперь ошибки видны: вы пытаетесьиспользовать оператор -> неправильно.Это означает, что ваш код будет изменен двумя способами:

• Используйте оператор ->

Это выглядит так:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction = newQueuedAction;
    return 1;
}

• Используйте оператор . с [0] hack

Это выглядит так:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction[0].nextAction = newQueuedAction;
    newQueuedAction[0].nextAction = NULL;
    newQueuedAction[0].action = newAction;
    newQueuedAction[0].value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction = newQueuedAction;
    return 1;
}

И не забудьте стереть код == NULL , вы столкнетесь с пассивно-агрессивным программистом, который определяет NULL как что-то еще.Всегда используйте скобки для обеспечения расширяемости.Эта строка - только рекомендация стиля кода.

Надеюсь, это поможет,

Answer 4

Я сделал небольшую библиотеку, которая может обрабатывать очереди." UltraQueue "

Он написан на C ++, но полностью совместим с ANSI C. Его можно легко преобразовать в ANSI C, если вы действительно этого хотите.

Исходный коддоступно через GIT.

Grtz