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

Список с указателями.Список с указателями является мощной структурой данных, которая может быть создана, вставлена в программу или удалена из нее динамически в процессе выполнения программы. Список связей состоит из узлов, содержащих две части: часть данных и часть поля связи. Часть данных хранится информация об узле (или пункте) списка. Например, если мы должны были создать список автомобилей, готовых к продаже, частью данных для узла будет структура (или запись) car, которую мы разработали в предыдущем разделе. Полем связи был бы указатель (адрес памяти) следующую запись в списке. Начало списка названо головой (head). Конец списка называется хвостом (tail) и обозначается символом нуля (?) в поле связи. Это построение списка иллюстрируется на рис. 8.5. Здесь приведено объявление различных списков, позволяющих автомобильным дилерам проследить за состоянием парка автомобилей.

car_temp_ptr head_ptr; /*начало списка состояния автомобилей */

car_temp_ptr in_stock_list; / *автомобили в наличии */

car_temp_ptr repair_list; /*автомобили в ремонтных мастерских - не предназначены для продажи */

car_temp_ptr paint_shop_list; /*автомобили в мастерских покраски - не предназначены для продажи */

car_temp_ptr sold_list; /*проданные автомобили - не предназначены для продажи */

Мир автомобильных продаж очень динамичен. Автомобильные дилеры постоянно продают автомобили, занимаются их обменом, размещают автомобили в мастерских для ремонта, или даже производят перекрашивание автомобилей. Если нам необходимо создать список для каждого из этих действий, мы будем постоянно добавлять и удалять элементы в каждом из списков. Эти действия иллюстрируются на рис. 8.5в и 8.5г.

Рис. 8.5.Операции со списком a) список состоит из узла с данными и указателя, мента в список, г) удаление элемента

Чтобы вставить новый автомобиль в список, мы были бы должны найти соответствующее место для автомобиля в существующем списке. Например, если мы размещаем автомобили в алфавитном порядок, мы должны просматривать список, пока мы не найдем, соответствующее место чтобы вставить автомобиль в список, как показано на рис. 8.6. Как только соответствующая точка ввода найдена, указатель предшествующего узла должен быть изменен, чтобы указать на новый автомобиль, и указатель нового автомобиля должен быть изменен, чтобы указать на следующий автомобиль в списке.

Рис. 8.6.Список с указателями для текущего учета автомобилей

Когда автомобиль продан, он больше не доступен для продажи. Он должно быть затем быть удален из списка «для продажи». Для этого связь предшествующего автомобиля должна теперь указывать на последующий автомобиль. Автомобиль, который был продан, будет теперь действительно исключен из списка «для продажи» и может быть добавлен в список «проданные». Если бы у нас не было списка «проданные», мы могли бы освободить динамическую память, выделенную для этого автомобиля. Это осуществляется с помощью команды free(argument).

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

Рис. 8.7.Общие функции, связанные со списками с указателями

На рис. 8.7 показаны общие функции, связанные со списком с указателями. Код для каждой из этих функций приведен ниже:

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

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

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

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

*include /*стандартная библиотека ввода - вывода */

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

/*распределения*/

/*global variables - глобальные переменные. Объявление этих переменных */

/*помещают в файл заголовка (header file). Они приведены здесь, */

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

/*определение структуры "автомобиль"*/

struct car {

int year; /* год производства */

char make[10]; /*BWM, Hummer, Saturn */

char model[12]; /*купе, обратимый, SUV, пикап */

char VTN[10]; /*комбинация цифр, букв */

float mileage; /*показания спидометра: от 0 до 500,000+*/

struct car *next; /*указатель на следующий автомобиль в списке */

};

/*определение указателя на автомобиль */

typedef struct car ELEMENT;

typedef ELEMENT *car_temp_ptr;

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

void initialize_link_list(void);

void print_link_list(car_temp_ptr);

void insert_link_list(car_temp_ptr);

void delete_link_list(car_temp_ptr);

void search_link_list(car_temp_ptr);

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

/ " Создают списки, чтобы следить за состоянием автомобильного сервиса*/

car_temp_ptr in_stock_list; /* автомобили в продаже */

car_temp_ptr repair_list; /* автомобили в ремонт - не подлежат продаже*/

car_temp_ptr paint_shop_list;/*автомобили в покраске - не подлежат продаже*/

car_temp_ptr sold_list; /*проданные автомобили -- не подлежат продаже*/

car_temp_ptr new_car_entry; /*новый автомобиль для введения в список*/

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

void main(void) {

/*заполняет пустой список переменными NULL */

in_stock_list = NULL; /* автомобили в продаже */

repair_list = NULL; /* автомобили в ремонте - не подлежат продаже */

paint_shop_list = NULL; /* автомобили в покраске - не подлежат продаже*/

sold_list = NULL; /*проданные автомобили -- не подлежат продаже * /

new_car_entry = NULL;

initialize_link_list(); /*составление списка для продажи */

print_link_list(in_stock_list); /*print the list */

insert_link_list(in_stock_list); /*вставить новый автомобиль в список*/

print_link_list(in_stock_list); /*распечатать список */

delete_link_list(in_stock_list); /*удалить автомобиль из списка */

print_link_list(in_stock_list); /*распечатать список */

search_link_list(in_stock_list); /*поиск определенного пункта в списке */

}

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

/*void initialize_link_list (car_temp_ptr): инициализирует автомобиль */

/* для списка продаж используя список.Отметим, что этот список */

/* с указателями был объявлен как глобальная переменная. */

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

void initialize_link_list(void) {

car_temp_ptr new_car_entry1, new_car_entry2;

/*создает вход в список автомобилей */

new_car_entry = (car_temp_ptr)malloc(sizeof(ELEMENT));