Программирование AVR Использование стандартной функции qsort в AVR-GCC Wed, October 23 2019  

Поделиться

Нашли опечатку?

Пожалуйста, сообщите об этом - просто выделите ошибочное слово или фразу и нажмите Shift Enter.

Использование стандартной функции qsort в AVR-GCC Печать
Добавил(а) microsin   

Иногда может потребоваться отсортировать какой-либо массив данных, для этого предназначена функция qsort. Она относится к стандартным библиотечным функциям языков C и C++, и подключается заголовочным файлом stdlib.h. Сортировка происходит по выбранным Вами критериям. Здесь приведен простой пример, как использовать эту функцию с помощью указателя на функцию для сортировки.

Предположим, что есть следующая структура данных с 4 полями:

struct persons
{
   char First_Name[31];
   char Last_name[50];
   uint8_t age;
   uint8_t Address[50];
}

Требуется отсортировать массив экземпляров таких структур по возрасту (age) или по имени (First_Name, Last_name). Обычно Вы написали бы две отдельные функции, одна из которых сортирует по строкам (имя), другая по числовой переменной (возраст). Однако есть более простой вариант - использовать библиотечную функцию qsort():

void qsort (void *buf,
            size_t num,
            size_t size,
            int (*compare)(const void *, const void *));

Функция qsort сортирует массив объектов, на массив указывает buf. Количество объектов в массиве указывается параметром num, размер объекта в массиве параметром size. Указатель на функцию compare задает функцию, которая вернет значение меньшее, равное или большее 0, если первый аргумент соответственно меньше, равен или больше чем второй.

Давайте рассмотрим пример программы, где используется qsort и функция сравнения:

#include < avr/io.h>
#include < stdlib.h>    // этот заголовок декларирует функцию qsort
 
// Декларация структуры для сортируемых объектов:
struct persons
{
   char First_Name[31];
   char Last_name[50];
   uint8_t age;
   uint8_t Address[50];
};
 
// Декларация типа для этой структуры:
typedef struct persons per;
 
// Функция сравнения по полю имени First_Name:
int cmp_names(const void *name1, const void *name2)
{
   const per *tn1 = name1;
   const per *tn2 = name2;
   return strcmp(tn1->First_Name, tn2->First_Name);
}
 
// Функция сравнения по полю возраста age:
int cmp_ages(const void *age1, const void *age2)
{
   const per *te1 = age1;
   const per *te2 = age2;
   return te1->age - te2->age;
}
 
int main(void)
{
   // Массив сортируемых объектов:
   per pers[] =
   {
      {"Jim",  "Johnson",   45, "Laview 25"},
      {"Tony", "Linger",   49, "46 Mountain"},
      {"Sara", "Evans", 12, "River rd"},
      {"Tom",  "Emers",  45, "Next exit"},
      {"Liza", "Anderson", 54, "Wilkes"}
   };
   
   // Сортировка массива структур по возрасту age:
   qsort(pers, 5, sizeof pers[0], cmp_ages);
   // ... В этом месте можно было бы вывести результат сортировки
   // на LCD или в порт UART ...
   // Сортировка массива структур по имени First_Name:
   qsort(pers, 5, sizeof pers[0], cmp_names);
   // ... В этом месте можно было бы вывести результат сортировки
   // на LCD или в порт UART ...
   return 0;
}

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

AVR Memory Usage
----------------
Device: atmega8
 
Program: 4904 bytes (59.9% Full)
(.text + .data + .bootloader)
Data: 656 bytes (64.1% Full)
(.data + .bss + .noinit)

Итого получается, что память программ FLASH заполнена для ATmega8 на 59.9%, и ОЗУ (RAM) занято на 64.1%. Для данных большого размера было бы рациональнее использовать более мощный микроконтроллер, либо внешнюю память наподобие карты SD [2] или памяти DataFlash [3].

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

[Ссылки]

1. Using standard Qsort function in AVR-GCC site:winavr.scienceprog.com.
2. Подключение карт SD через SPI (упрощенное описание стандарта).
3. Использование Atmel Serial DataFlash.

 

Добавить комментарий


Защитный код
Обновить

Top of Page