Стивен Барретт - Встраиваемые системы. Проектирование приложений на микроконтроллерах семейства 68HC12/HCS12 с применением языка С

year: 1981

make: Chevy

model: Camaro

VIN: 12Z367

mileage: 37456

year: 1974

make: Ford

model: Mustang11

VIN: 3L265ST

mileage: 122456

year: 1997

make: Saturn

model: SL1

VIN: 234TH67

mileage: 140512

Найден автомобиль в списке продаж.

Введенное поле make для поиска – Saturn

year: 1997

make: Saturn

model: SL1

VIN: 234TH67

mileage: 140512

Этот очень простой пример был придуман, чтобы показать основные действия, связанные обработкой списка с указателями. Мы намеренно выбрали скелетную программу, чтобы концентрироваться на работе списков с указателями. Если бы мы разрабатывали фактическую программу описи, основанную на списках с указателями, мы разработали бы дружественное меню, которое позволило бы вызывать функции в любом порядке. Кроме того, мы сформировали бы исходный список загрузив данные из файла. Мы обеспечили бы также возможность сохранять данные списка в файле.

Очередь.Очередь представляет собой особым образом сконфигурированный список с указателями. Она называется также буфером первым-вошел-первым-вышел (first-in first out — FIFO). Элементы добавляются в хвост очереди и извлекаются с головы, как показано на рис. 8.8. Вернемся к нашей автомобильной коммерческой аналогии. Как только вы приобретаете автомобиль, вы должны зарегистрировать его в департаменте транспортных средств. Я был там недавно с моим сыном, которому нужны было заменить водительские права. После нашего прихода мы встали в хвост очереди и стали ждать, пока нас обслужат. После короткого ожидания, мы достигли головы очереди и смогли получить требуемые права. Нас обслуживали в порядке прохождения очереди. Во время пика занятости, например, в утренние часы, в конце месяца — очередь в департаменте может быть очень длинной. В более свободное время она может быть совсем короткой. В обоих случаях мы видим, что очередь не имеет фиксированного числа элементов. Длина очереди или число элементов в ней, является переменной величиной и изменяется, в зависимости от действия программы.

Рис. 8.8.Структура данных очередь — «первым вошел–первым вышел»

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

Рис. 8.9.Круговая очередь

Стек.Стек — это структура данных последним вошел — первым вышел (last-in-first-out — LIFO), показанная на рис. 8.10. Она также может быть создана с помощью методов списка с указателями. Во встроенных контроллерных системах на базе 68HC12, стек — определенная пользователем часть RAM, в которой в течение нормального выполнения программы временно хранятся переменные, например содержимое какого-либо регистра. Верхняя часть стека в 68HC12 обычно определяется последней позицией RAM плюс один. Указатель вершины стека для 68HC12 содержит адрес последнего используемого расположения стека. Когда элемент помещают в стек, указатель вершины стека уменьшается на 1 (проводится операция декремента). Когда элемент извлекается из стека, указатель вершины стека увеличивается на 1 (операция инкремента). Когда программирование проводится на языке C, положение вершины стека является опцией компилятора. Если встроенная контроллерная система содержит только один стек, лучше всего просто использовать свойства, встроенные в процессор. Однако, как мы скоро увидим, в ОСРВ можем потребоваться несколько стеков, по одному для каждой задачи. В этом случае разработчику системы необходимо, чтобы обеспечить работу нескольких стеков. Если используются динамические методы распределения памяти, то несколько стеков создаются и используются в динамической памяти. Мы оставим разработку структуры данных стека, использующей динамические методы распределения памяти в качестве вашей домашней работы (задача 1 для самостоятельного исследования). Вместо этого, мы разработаем структуру стека с фиксированный размером массива. Стек с фиксированным массивом используется, когда размер стека известен и неизменен. Как мы скоро увидим, стеки с успехом могут используются в блоках управления задачами.

Рис. 8.10.Стек

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

• initialize_stack: инициализация стека;

• push: поместить элемент в стек;

• pull: извлечь элемент из стека;

• stack_empty: выяснить, не пуст ли стек. Это необходимо сделать до использования функции pull;

• stack_full: выяснить, не полон ли стек. Это необходимо сделать до использования функции push;

• print_stack: распечатать содержимое стека.

Основные операции стека показаны на рис. 8.11.

Рис. 8.11.Операции со стеком

Следующий программный код реализует стек с фиксированным массивом.

/********************************************************************/

/* имя файла: stack.с */

/********************************************************************/

/*включенные файлы*/

#include /*стандартная библиотека I/O */

#include /*стандартная библиотека динамического распределения*/

/*global variables - объявляет глобальные переменные в header file. */

/* Они приведены здесь, чтобы иллюстрировать общее построение программы.*/

/*определение структуры*/

struct stack_struct {

int stack_top; /*следующая используемая позиция в стеке*/

int stack_item[10]; /*элемент, сохраненный в стеке с фиксированным размером */

}

typedef struct stack_struct stack; /*массив для распознавания имен различных переменных*/

typedef stack *stack_ptr; /*определение указателей на стек */

/*функции-прототипы*/

void initialize_stack(stack);

void push(stack*, int); /*Используется метод передачи параметра по ссылке*/

int pull(stack *); /* когда содержимое стека должно измениться */

int stack_empty(stack);

int stack_full(stack);

void print_stack(stack);

/*переменные*/

int YES=1,NO=0; /*логические флаги */