русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Библиотеки


Дата добавления: 2013-12-23; просмотров: 974; Нарушение авторских прав


 

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

 

Библиотечные функции написаны так, что они могут сортировать данные любого типа, но мы в свою очередь должны адаптироваться к их интерфейсу, что может быть несколько сложнее, чем в рассмотренном выше примере. В языке С библиотечная функция называется qso rt, и ей нужно предоставлять функцию сравнения двух значений. Поскольку значения могут быть любых типов, то функции сравнения передаются два нетипизированных указателя (void *) на сравниваемые значения. Функция преобразует указатели к нужному типу, извлекает значения данных, сравнивает их и возвращает результат (отрицательный, нуль или положительный в зависимости от того, меньше ли первый элемент, равен ли второму или больше его).

 

Рассмотрим реализацию функции сравнения для сортировки массива строк, случая, встречающегося довольно часто. Мы написали функцию scmp, которая -преобразует параметры к другому типу и затем вызывает st rcmp для выполнения самого сравнения:

 

/* scmp: сравнение строк *р1 и *р2 */

int scmp(const void *p1, const void *p2)

{

char *v1, *v2;

v1 = *(char **) p1; v2 = *(char **) p2;

return strcmp(v1, v2); }

 

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

 

Мы не можем напрямую использовать strcmp как функцию сравнения, поскольку qsort передает адрес каждого элемента в массиве &s t г [ i ] (типаспаг **), ане str[i] (типа char *), как показано на рисунке:

 

 

Для сортировки элементов массива строк с st r[0] по st r[N-1 ] функция qsort должна получить массив, его длину, размер сортируемых элементов и функцию сравнения:



char *str[N];

qsort(str, N, sizeof(str[OJ), scmp);

 

А вот аналогичная функция icmp для сравнения целых:

{

int v1, v2;

v1 = *(int *) p1; v2 = *(int *.) p2;

if (v1 < v2)

return -1; else

if (v1 == v2)

return 0; else

return 1; >

}

Мы могли бы написать

? return v1-v2;

 

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

 

И здесь при вызове qsort нужно передать массив, его длину, размер сортируемых элементов и функцию сравнения:

int arr[N];

qsort(arr, N, sizeof(arr[0]), icmp);

 

В стандарте ANSI С определена также функция двоичного поиска bsea rch. Как и qso rt, этой функции нужен указатель на функцию сравнения (часто на ту же, что используется для qsort); bsearch возвращает указатель на найденный элемент или на NULL, если такого элемента нет. Вот наша программа для поиска имен в HTML-файле, переписанная с использованием bsearch:

/* lookup: использует bsearch для поиска name в таблице tab,

возвращает индекс */

int lookup(char *name, Nameval tab[],

int ntab) {

Nameval key, *np;

 

 

key.value = 0; /* не используется;

годится любое значение */

np = (Nameval *) bsearch(&key, tab, ntab,

sizeof(tab[0]), nvcmp); if (np == NULL)

return -1; else

return np-tab;

Как и в случае qsort, функция сравнения получает адреса сравниваемых значений, поэтому ключевое (искомое) значение должно иметь этот же тип; в данном примере нам пришлось создать фиктивный элемент типа Nameval для передачи в функцию сравнения. Сама функция сравнения nvcmp сравнивает два значения типа Nameval, вызывая st rcmp для их строковых компонентов, полностью игнорируя численные компоненты:

 

 

/* nvcmp: сравнивает два вначения типа

Nameval */

int nvcmp(const void *va, const void *vb)

{

const Nameval *a, *b;

a = (Nameval *) va;* b = (Nameval *) vb;

return strcmp(a->name, b->name); }

Это похоже на scmp, только с тем отличием, что строки хранятся как члены структуры.

 

Неудобство передачи ключевого значения показывает, что bsearch предоставляет меньше возможностей, чем qso rt. Хорошая многоцелевая функция сортировки занимает одну-две страницы кода, а двоичный поиск — ненамного больше, чем код для интерфейса с bsearch. Тем не менее лучше использовать bsearch, чем писать свою собственную версию. Как показывает опыт, программистам на удивление трудно написать двоичный поиск без ошибок.

 

В стандартной библиотеке C++ имеется обобщенная функция sort, которая обеспечивает время работы 0(п log n). Код для ее вызова проще, потому что нет необходимости в преобразовании типов и размеров элементов. Кроме того, для порядковых типов не требуется задавать функцию сравнения:

int arr[N]; sort(arr, arr+N);

 

Эта библиотека содержит также обобщенные функции двоичного поиска, с теми же преимуществами в вызове.

 

Упражнение 2-1

 

Алгоритм быстрой сортировки проще всего выразить рекурсивно. Реализуйте его итеративно и сравните две версии. (Хоар рассказывает, как было трудно разработать итеративный вавариант быстрой сортировки и как легко все оказалось, когда он сделал ее рекурсивной.)

 

 



<== предыдущая лекция | следующая лекция ==>
Сортировка | Динамически расширяемые массивы


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.