Спонсоры сайта:

Наличие этой страницы в поиске?

Информеры ТИЦ и PR

  Yandex ТИЦ:  
   Google PR:  

Путешественникам, меломанам, бизнесменам, вебмастерам, новости.

Содержание | <<< | >>>

Сортировка других структур данных





До сих пор мы сортировали только массивы символов. Очевидно, что приведенные выше функции можно переделать для сортировки массивов любого из встроенных типов данных, просто поменяв типы параметров и переменных. Тем не менее, обычно возникает необходимость сортировать составные типы данных, например строки, или агрегированные данные, например структуры. Большинство задач сортировки имеют дело с ключом и информацией, связанной с этим ключом. Чтобы адаптировать алгоритмы для обработки подобных данных, необходимо модифицировать код сравнения, код обмена или оба фрагмента. Сам алгоритм при этом не меняется.

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

Сортировка строк

Сортировка строк является распространенной задачей программирования. Строки легче всего сортировать, когда они хранятся в таблице строк. Таблица строк — это просто массив строк. А массив строк — это двумерный массив символов, в котором количество строк в таблице определяется размером левого измерения, а максимальная длина строки — размером правого измерения. (О массивах строк рассказывалось в главе 4.) Нижеследующая строковая версия быстрой сортировки принимает массив строк, в котором размер каждой строки ограничен десятью символами. (Можете изменить эту длину, если хотите.) Данная версия сортирует строки в лексикографическом порядке.

/* Быстрая сортировка строк. */
void quick_string(char items[][10], int count)
{
  qs_string(items, 0, count-1);
}

void qs_string(char items[][10], int left, int right)
{
  register int i, j;
  char *x;
  char temp[10];

  i = left; j = right;
  x = items[(left+right)/2];

  do {
    while((strcmp(items[i],x) < 0) && (i < right)) i++;
    while((strcmp(items[j],x) > 0) && (j > left)) j--;
    if(i <= j) {
      strcpy(temp, items[i]);
      strcpy(items[i], items[j]);
      strcpy(items[j], temp);
      i++; j--;
   }
  } while(i <= j);

  if(left < j) qs_string(items, left, j);
  if(i < right) qs_string(items, i, right);
}

Обратите внимание, что во фрагменте сравнения теперь используется функция strcmp(). Эта функция возвращает отрицательное число, если первая строка лексикографически меньше второй, возвращает ноль, если строки равны, и положительное число, если первая строка лексикографически больше второй. Также следует отметить, что для обмена двух строк требуется три вызова функции strcpy().

Имейте в виду, что функция strcmp() замедляет сортировку по двум причинам. Во-первых, в программе появляется вызов функции, что всегда отнимает время. Во-вторых, сама функция strcmp() выполняет несколько сравнений, чтобы определить, какая из двух строк больше. В первом случае, если скорость очень важна, можно поместить код сравнения строк непосредственно в функцию сортировки, продублировав код функции strcmp(). Во втором случае нет никакого способа избежать сравнения строк, поскольку по определению это именно то, что требуется в данной задаче. Те же рассуждения относятся и к функции strcpy(). Обмен двух строк с помощью strcpy() включает в себя вызов функции и посимвольный обмен содержимого строк — каждая из этих операций занимает время. Накладные расходы на вызов функции можно устранить, вставив код копирования прямо в алгоритм сортировки. Однако тот факт, что обмен двух строк означает обмен отдельных символов (один за другим), изменить невозможно.

Ниже приведена простая функция main(), демонстрирующая работу функции быстрой сортировки строк quick_string():

#include <stdio.h>
#include <string.h>

void quick_string(char items[][10], int count);
void qs_string(char items[][10], int left, int right);

char str[][10] = { "один",
                   "два",
                   "три",
                   "четыре"
                 };

int main(void)
{
  int i;

  quick_string(str, 4);

  for(i=0; i<4; i++) printf("%s ", str[i]);

  return 0;
}

Сортировка структур

В большинстве прикладных программ, в которых используется сортировка, предусмотрена сортировка совокупностей данных. Например, списки почтовой рассыпки, складские базы данных и журналы сотрудников содержат наборы разнотипных данных. Как вам известно, в программах на языке С совокупности данных обычно хранятся в структурах. Хотя структура обычно содержит несколько членов, структуры, как правило, сортируются только по одному полю-члену, который используется в качестве ключа сортировки. За исключением выбора ключа, приемы сортировки структур ничем не отличаются от приемов сортировки других типов данных.

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

struct address {
  char name[40];   /* имя */
  char street[40]; /* улица */
  char city[20];   /* город */
  char state[3];   /* штат */
  char zip[11];    /* индекс */
};

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

/* Быстрая сортировка структур типа фвкуыы. */
void quick_struct(struct address items[], int count)
{
  qs_struct(items,0,count-1);
}

void qs_struct(struct address items[], int left, int right)
{

  register int i, j;
  char *x;
  struct address temp;

  i = left; j = right;
  x = items[(left+right)/2].zip;

  do {
    while((strcmp(items[i].zip,x) < 0) && (i < right)) i++;
    while((strcmp(items[j].zip,x) > 0) && (j > left)) j--;
    if(i <= j) {
      temp = items[i];
      items[i] = items[j];
      items[j] = temp;
      i++; j--;
    }
  } while(i <= j);

  if(left < j) qs_struct(items, left, j);
  if(i < right) qs_struct(items, i, right);
}

Содержание | <<< | >>>

C++ исходники. Все примеры - рабочие:

часы:

Dev C++ WinAPI Стрелочные часы Analog Clock

Dev C++ WinAPI Цифровые прозрачные часы. Текст на рабочем столе. Digital transparent clock. Text on desktop

Dev C++ OLE WinApi CALENDAR and DIGITAL CLOCK (15kb). Календарь и цифровые часы

Dev C++ OLE WinAPI Календарь и цифровые часы почти Vista SideBar всего 21kb

плееры:

Microsoft Visual C++ 2008 Direct Show DVD Mini Player 10.5kb

Dev C++ WinAPI Микро медиа плеер 3.5kb

Dev C++ WinAPI Мини медиа плеер 4.5kb

Dev C++ WinAPI Hint Всплывающая подсказка

Dev C++ WinAPI RECT - имитатор кнопки

Dev C++ WinAPI Заполнить ListBox

Dev C++ WinAPI Заполнить, редактировать, сохранить, загрузить ListBox (PlayList)

Dev C++ WinAPI Индикатор уровня

Dev C++ WinAPI MP3 Микро плеер Открыть с помощью...

Dev C++ WinAPI Своя кнопка

изображения:

Dev C++ GDI+ WinAPI Mini FotoResizer (16kb), изменяет размеры всех фото (JPG) до указанного размера в выбраной папке и её подпапках

Dev C++ WinAPI Сохранить BITMAP экрана, десктопа, окна, клиентской области.

Dev C++ WinAPI Изменить размер изображения BMP RESIZE. Загрузка изображений из ФАЙЛА, вывод на экран и сохранение в файл.

Dev C++ WinAPI Загрузка изображений из РЕСУРСОВ и вывод на экран.

Dev C++ GDI+ WinAPI. Преобразовать изображения из одного формата в другой (JPG в BMP, GIF, PNG и обратно ), используя дополнительные библиотеки GDI+. Загрузка изображений из файла и сохранение в файл.

Dev C++ GDI+ WinAPI масштабирование JPG RESIZE

Dev C++ OLE WinAPI. Преобразовать изображения из JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из РЕСУРСОВ и сохранение в файл.

Dev C++ OLE WinAPI преобразовать JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из ФАЙЛА и сохранение в файл.

Dev C++ OLE WinAPI масштабирование BMP RESIZE

разное:

Dev C++ WinAPI Dev C++ Преобразовать цвет точки экрана в HTML код

Dev C++ WinAPI NOTIFYICONDATA WS_EX_TOOLWINDOW Иконка в области уведомлений (notification area, tray, трей). Удалить с панели задач (taskbar).

Dev C++ WinAPI ShellExecute Создать ссылку на WEB сайт

Dev C++ WinAPI ShellExecute Создать окно со ссылкой на WEB сайт

Dev C++ WinAPI CreateProcess ShellExecute WinExec Запуск приложения из приложения

Dev C++ OLE WinAPI Создать регион Regions PopUp Меню Menu

Dev C++ FindFiles. Поиск файлов заданного типа (в примере *.JPG) в папке и её подпапках

библиотеки:

Скачать библиотеку GDI+ для Dev C++

Скачать справочнник с примерами языка C.